/* Long (arbitrary precision) integer object implementation */

/* XXX The functional organization of this file is terrible */

#include "Python.h"

#include "pycore_bitutils.h" // _Py_popcount32()

#include "pycore_initconfig.h" // _PyStatus_OK()

#include "pycore_call.h" // _PyObject_MakeTpCall

#include "pycore_freelist.h" // _Py_FREELIST_FREE, _Py_FREELIST_POP

#include "pycore_long.h" // _Py_SmallInts

#include "pycore_object.h" // _PyObject_Init()

#include "pycore_runtime.h" // _PY_NSMALLPOSINTS

#include "pycore_stackref.h"

#include "pycore_structseq.h" // _PyStructSequence_FiniBuiltin()

#include "pycore_tuple.h" // _PyTuple_FromPairSteal

#include "pycore_unicodeobject.h" // _PyUnicode_Equal()

#include <float.h> // DBL_MANT_DIG

#include <stddef.h> // offsetof

#include "clinic/longobject.c.h"

/*[clinic input]

class int "PyObject *" "&PyLong_Type"

[clinic start generated code]*/

/*[clinic end generated code: output=da39a3ee5e6b4b0d input=ec0275e3422a36e3]*/

#define medium_value(x) ((stwodigits)_PyLong_CompactValue(x))

#define IS_SMALL_INT(ival) _PY_IS_SMALL_INT(ival)

#define IS_SMALL_UINT(ival) ((ival) < _PY_NSMALLPOSINTS)

#define _MAX_STR_DIGITS_ERROR_FMT_TO_INT "Exceeds the limit (%d digits) for integer string conversion: value has %zd digits; use sys.set_int_max_str_digits() to increase the limit"

#define _MAX_STR_DIGITS_ERROR_FMT_TO_STR "Exceeds the limit (%d digits) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit"

/* If defined, use algorithms from the _pylong.py module */

#define WITH_PYLONG_MODULE 1

// Forward declarations

static PyLongObject* long_neg(PyLongObject *v);

static PyLongObject *x_divrem(PyLongObject *, PyLongObject *, PyLongObject **);

static PyObject* long_long(PyObject *v);

static PyObject* long_lshift_int64(PyLongObject *a, int64_t shiftby);

static inline void

_Py_DECREF_INT(PyLongObject *op)

{

assert(PyLong_CheckExact(op));

_Py_DECREF_SPECIALIZED((PyObject *)op, _PyLong_ExactDealloc);

}

static inline int

is_medium_int(stwodigits x)

{

/* Take care that we are comparing unsigned values. */

twodigits x_plus_mask = ((twodigits)x) + PyLong_MASK;

return x_plus_mask < ((twodigits)PyLong_MASK) + PyLong_BASE;

}

static PyObject *

get_small_int(sdigit ival)

{

assert(IS_SMALL_INT(ival));

return (PyObject *)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS + ival];

}

static PyLongObject *

maybe_small_long(PyLongObject *v)

{

if (v && _PyLong_IsCompact(v)) {

stwodigits ival = medium_value(v);

if (IS_SMALL_INT(ival)) {

_Py_DECREF_INT(v);

return (PyLongObject *)get_small_int((sdigit)ival);

}

}

return v;

}

/* For int multiplication, use the O(N**2) school algorithm unless

* both operands contain more than KARATSUBA_CUTOFF digits (this

* being an internal Python int digit, in base BASE).

*/

#define KARATSUBA_CUTOFF 70

#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)

/* For exponentiation, use the binary left-to-right algorithm unless the

^ exponent contains more than HUGE_EXP_CUTOFF bits. In that case, do

* (no more than) EXP_WINDOW_SIZE bits at a time. The potential drawback is

* that a table of 2**(EXP_WINDOW_SIZE - 1) intermediate results is

* precomputed.

*/

#define EXP_WINDOW_SIZE 5

#define EXP_TABLE_LEN (1 << (EXP_WINDOW_SIZE - 1))

/* Suppose the exponent has bit length e. All ways of doing this

* need e squarings. The binary method also needs a multiply for

* each bit set. In a k-ary method with window width w, a multiply

* for each non-zero window, so at worst (and likely!)

* ceiling(e/w). The k-ary sliding window method has the same

* worst case, but the window slides so it can sometimes skip

* over an all-zero window that the fixed-window method can't

* exploit. In addition, the windowing methods need multiplies

* to precompute a table of small powers.

*

* For the sliding window method with width 5, 16 precomputation

* multiplies are needed. Assuming about half the exponent bits

* are set, then, the binary method needs about e/2 extra mults

* and the window method about 16 + e/5.

*

* The latter is smaller for e > 53 1/3. We don't have direct

* access to the bit length, though, so call it 60, which is a

* multiple of a long digit's max bit length (15 or 30 so far).

*/

#define HUGE_EXP_CUTOFF 60

#define SIGCHECK(PyTryBlock) \

do { \

if (PyErr_CheckSignals()) PyTryBlock \

} while(0)

/* Normalize (remove leading zeros from) an int object.

Doesn't attempt to free the storage--in most cases, due to the nature

of the algorithms used, this could save at most be one word anyway. */

static PyLongObject *

long_normalize(PyLongObject *v)

{

Py_ssize_t j = _PyLong_DigitCount(v);

Py_ssize_t i = j;

while (i > 0 && v->long_value.ob_digit[i-1] == 0)

--i;

if (i != j) {

if (i == 0) {

_PyLong_SetSignAndDigitCount(v, 0, 0);

}

else {

_PyLong_SetDigitCount(v, i);

}

}

return v;

}

/* Allocate a new int object with size digits.

Return NULL and set exception if we run out of memory. */

#if SIZEOF_SIZE_T < 8

# define MAX_LONG_DIGITS \

((PY_SSIZE_T_MAX - offsetof(PyLongObject, long_value.ob_digit))/sizeof(digit))

#else

/* Guarantee that the number of bits fits in int64_t.

This is more than an exbibyte, that is more than many of modern

architectures support in principle.

-1 is added to avoid overflow in _PyLong_Frexp(). */

# define MAX_LONG_DIGITS ((INT64_MAX-1) / PyLong_SHIFT)

#endif

static PyLongObject *

long_alloc(Py_ssize_t size)

{

assert(size >= 0);

PyLongObject *result = NULL;

if (size > (Py_ssize_t)MAX_LONG_DIGITS) {

PyErr_SetString(PyExc_OverflowError,

"too many digits in integer");

return NULL;

}

/* Fast operations for single digit integers (including zero)

* assume that there is always at least one digit present. */

Py_ssize_t ndigits = size ? size : 1;

if (ndigits == 1) {

result = (PyLongObject *)_Py_FREELIST_POP(PyLongObject, ints);

}

if (result == NULL) {

/* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +

sizeof(digit)*size. Previous incarnations of this code used

sizeof() instead of the offsetof, but this risks being

incorrect in the presence of padding between the header

and the digits. */

result = PyObject_Malloc(offsetof(PyLongObject, long_value.ob_digit) +

ndigits*sizeof(digit));

if (!result) {

PyErr_NoMemory();

return NULL;

}

_PyObject_Init((PyObject*)result, &PyLong_Type);

_PyLong_InitTag(result);

}

_PyLong_SetSignAndDigitCount(result, size != 0, size);

#ifdef Py_DEBUG

// gh-147988: Fill digits with an invalid pattern to catch usage

// of uninitialized digits.

memset(result->long_value.ob_digit, 0xFF, ndigits * sizeof(digit));

#endif

return result;

}

PyLongObject *

_PyLong_New(Py_ssize_t size)

{

return long_alloc(size);

}

PyLongObject *

_PyLong_FromDigits(int negative, Py_ssize_t digit_count, digit *digits)

{

assert(digit_count >= 0);

if (digit_count == 0) {

return (PyLongObject *)_PyLong_GetZero();

}

PyLongObject *result = long_alloc(digit_count);

if (result == NULL) {

return NULL;

}

_PyLong_SetSignAndDigitCount(result, negative?-1:1, digit_count);

memcpy(result->long_value.ob_digit, digits, digit_count * sizeof(digit));

return result;

}

PyObject *

_PyLong_Copy(PyLongObject *src)

{

assert(src != NULL);

int sign;

if (_PyLong_IsCompact(src)) {

stwodigits ival = medium_value(src);

if (IS_SMALL_INT(ival)) {

return get_small_int((sdigit)ival);

}

sign = _PyLong_CompactSign(src);

}

else {

sign = _PyLong_NonCompactSign(src);

}

Py_ssize_t size = _PyLong_DigitCount(src);

PyLongObject *result = long_alloc(size);

if (result == NULL) {

return NULL;

}

_PyLong_SetSignAndDigitCount(result, sign, size);

memcpy(result->long_value.ob_digit, src->long_value.ob_digit,

size * sizeof(digit));

return (PyObject *)result;

}

static PyObject *

_PyLong_FromMedium(sdigit x)

{

assert(!IS_SMALL_INT(x));

assert(is_medium_int(x));

PyLongObject *v = (PyLongObject *)_Py_FREELIST_POP(PyLongObject, ints);

if (v == NULL) {

v = PyObject_Malloc(sizeof(PyLongObject));

if (v == NULL) {

PyErr_NoMemory();

return NULL;

}

_PyObject_Init((PyObject*)v, &PyLong_Type);

_PyLong_InitTag(v);

}

digit abs_x = x < 0 ? -x : x;

_PyLong_SetSignAndDigitCount(v, x<0?-1:1, 1);

v->long_value.ob_digit[0] = abs_x;

return (PyObject*)v;

}

static PyObject *

_PyLong_FromLarge(stwodigits ival)

{

twodigits abs_ival;

int sign;

assert(!is_medium_int(ival));

if (ival < 0) {

/* negate: can't write this as abs_ival = -ival since that

invokes undefined behaviour when ival is LONG_MIN */

abs_ival = 0U-(twodigits)ival;

sign = -1;

}

else {

abs_ival = (twodigits)ival;

sign = 1;

}

/* Must be at least two digits */

assert(abs_ival >> PyLong_SHIFT != 0);

twodigits t = abs_ival >> (PyLong_SHIFT * 2);

Py_ssize_t ndigits = 2;

while (t) {

++ndigits;

t >>= PyLong_SHIFT;

}

PyLongObject *v = long_alloc(ndigits);

if (v != NULL) {

digit *p = v->long_value.ob_digit;

_PyLong_SetSignAndDigitCount(v, sign, ndigits);

t = abs_ival;

while (t) {

*p++ = Py_SAFE_DOWNCAST(

t & PyLong_MASK, twodigits, digit);

t >>= PyLong_SHIFT;

}

}

return (PyObject *)v;

}

/* Create a new int object from a C word-sized int */

static inline PyLongObject *

_PyLong_FromSTwoDigits(stwodigits x)

{

if (IS_SMALL_INT(x)) {

return (PyLongObject*)get_small_int((sdigit)x);

}

assert(x != 0);

if (is_medium_int(x)) {

return (PyLongObject*)_PyLong_FromMedium((sdigit)x);

}

return (PyLongObject*)_PyLong_FromLarge(x);

}

/* Create a new medium int object from a medium int.

* Do not raise. Return NULL if not medium or can't allocate. */

static inline _PyStackRef

medium_from_stwodigits(stwodigits x)

{

if (IS_SMALL_INT(x)) {

return PyStackRef_FromPyObjectBorrow(get_small_int((sdigit)x));

}

assert(x != 0);

if(!is_medium_int(x)) {

return PyStackRef_NULL;

}

PyLongObject *v = (PyLongObject *)_Py_FREELIST_POP(PyLongObject, ints);

if (v == NULL) {

v = PyObject_Malloc(sizeof(PyLongObject));

if (v == NULL) {

return PyStackRef_NULL;

}

_PyObject_Init((PyObject*)v, &PyLong_Type);

_PyLong_InitTag(v);

}

digit abs_x = x < 0 ? (digit)(-x) : (digit)x;

_PyLong_SetSignAndDigitCount(v, x<0?-1:1, 1);

v->long_value.ob_digit[0] = abs_x;

return PyStackRef_FromPyObjectStealMortal((PyObject *)v);

}

/* If a freshly-allocated int is already shared, it must

be a small integer, so negating it must go to PyLong_FromLong */

Py_LOCAL_INLINE(void)

_PyLong_Negate(PyLongObject **x_p)

{

PyLongObject *x;

x = (PyLongObject *)*x_p;

if (_PyObject_IsUniquelyReferenced((PyObject *)x)) {

_PyLong_FlipSign(x);

return;

}

*x_p = _PyLong_FromSTwoDigits(-medium_value(x));

Py_DECREF(x);

}

#define PYLONG_FROM_INT(UINT_TYPE, INT_TYPE, ival) \

do { \

/* Handle small and medium cases. */ \

if (IS_SMALL_INT(ival)) { \

return get_small_int((sdigit)(ival)); \

} \

if (-(INT_TYPE)PyLong_MASK <= (ival) && (ival) <= (INT_TYPE)PyLong_MASK) { \

return _PyLong_FromMedium((sdigit)(ival)); \

} \

UINT_TYPE abs_ival = (ival) < 0 ? 0U-(UINT_TYPE)(ival) : (UINT_TYPE)(ival); \

/* Do shift in two steps to avoid possible undefined behavior. */ \

UINT_TYPE t = abs_ival >> PyLong_SHIFT >> PyLong_SHIFT; \

/* Count digits (at least two - smaller cases were handled above). */ \

Py_ssize_t ndigits = 2; \

while (t) { \

++ndigits; \

t >>= PyLong_SHIFT; \

} \

/* Construct output value. */ \

PyLongObject *v = long_alloc(ndigits); \

if (v == NULL) { \

return NULL; \

} \

digit *p = v->long_value.ob_digit; \

_PyLong_SetSignAndDigitCount(v, (ival) < 0 ? -1 : 1, ndigits); \

t = abs_ival; \

while (t) { \

*p++ = (digit)(t & PyLong_MASK); \

t >>= PyLong_SHIFT; \

} \

return (PyObject *)v; \

} while(0)

/* Create a new int object from a C long int */

PyObject *

PyLong_FromLong(long ival)

{

PYLONG_FROM_INT(unsigned long, long, ival);

}

#define PYLONG_FROM_UINT(INT_TYPE, ival) \

do { \

/* Handle small and medium cases. */ \

if (IS_SMALL_UINT(ival)) { \

return get_small_int((sdigit)(ival)); \

} \

if ((ival) <= PyLong_MASK) { \

return _PyLong_FromMedium((sdigit)(ival)); \

} \

/* Do shift in two steps to avoid possible undefined behavior. */ \

INT_TYPE t = (ival) >> PyLong_SHIFT >> PyLong_SHIFT; \

/* Count digits (at least two - smaller cases were handled above). */ \

Py_ssize_t ndigits = 2; \

while (t) { \

++ndigits; \

t >>= PyLong_SHIFT; \

} \

/* Construct output value. */ \

PyLongObject *v = long_alloc(ndigits); \

if (v == NULL) { \

return NULL; \

} \

digit *p = v->long_value.ob_digit; \

while ((ival)) { \

*p++ = (digit)((ival) & PyLong_MASK); \

(ival) >>= PyLong_SHIFT; \

} \

return (PyObject *)v; \

} while(0)

/* Create a new int object from a C unsigned long int */

PyObject *

PyLong_FromUnsignedLong(unsigned long ival)

{

PYLONG_FROM_UINT(unsigned long, ival);

}

/* Create a new int object from a C unsigned long long int. */

PyObject *

PyLong_FromUnsignedLongLong(unsigned long long ival)

{

PYLONG_FROM_UINT(unsigned long long, ival);

}

/* Create a new int object from a C size_t. */

PyObject *

PyLong_FromSize_t(size_t ival)

{

PYLONG_FROM_UINT(size_t, ival);

}

/* Create a new int object from a C double */

PyObject *

PyLong_FromDouble(double dval)

{

/* Try to get out cheap if this fits in a long. When a finite value of real

* floating type is converted to an integer type, the value is truncated

* toward zero. If the value of the integral part cannot be represented by

* the integer type, the behavior is undefined. Thus, we must check that

* value is in range (LONG_MIN - 1, LONG_MAX + 1). If a long has more bits

* of precision than a double, casting LONG_MIN - 1 to double may yield an

* approximation, but LONG_MAX + 1 is a power of two and can be represented

* as double exactly (assuming FLT_RADIX is 2 or 16), so for simplicity

* check against [-(LONG_MAX + 1), LONG_MAX + 1).

*/

const double int_max = (unsigned long)LONG_MAX + 1;

if (-int_max < dval && dval < int_max) {

return PyLong_FromLong((long)dval);

}

PyLongObject *v;

double frac;

int i, ndig, expo, neg;

neg = 0;

if (isinf(dval)) {

PyErr_SetString(PyExc_OverflowError,

"cannot convert float infinity to integer");

return NULL;

}

if (isnan(dval)) {

PyErr_SetString(PyExc_ValueError,

"cannot convert float NaN to integer");

return NULL;

}

if (dval < 0.0) {

neg = 1;

dval = -dval;

}

frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */

assert(expo > 0);

ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */

v = long_alloc(ndig);

if (v == NULL)

return NULL;

frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);

for (i = ndig; --i >= 0; ) {

digit bits = (digit)frac;

v->long_value.ob_digit[i] = bits;

frac = frac - (double)bits;

frac = ldexp(frac, PyLong_SHIFT);

}

if (neg) {

_PyLong_FlipSign(v);

}

return (PyObject *)v;

}

/* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define

* anything about what happens when a signed integer operation overflows,

* and some compilers think they're doing you a favor by being "clever"

* then. The bit pattern for the largest positive signed long is

* (unsigned long)LONG_MAX, and for the smallest negative signed long

* it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.

* However, some other compilers warn about applying unary minus to an

* unsigned operand. Hence the weird "0-".

*/

#define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)

#define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)

static inline unsigned long

unroll_digits_ulong(PyLongObject *v, Py_ssize_t *iptr)

{

assert(ULONG_MAX >= ((1UL << PyLong_SHIFT) - 1));

Py_ssize_t i = *iptr;

assert(i >= 2);

/* unroll 1 digit */

--i;

digit *digits = v->long_value.ob_digit;

unsigned long x = digits[i];

#if (ULONG_MAX >> PyLong_SHIFT) >= ((1UL << PyLong_SHIFT) - 1)

/* unroll another digit */

x <<= PyLong_SHIFT;

--i;

x |= digits[i];

#endif

*iptr = i;

return x;

}

static inline size_t

unroll_digits_size_t(PyLongObject *v, Py_ssize_t *iptr)

{

assert(SIZE_MAX >= ((1UL << PyLong_SHIFT) - 1));

Py_ssize_t i = *iptr;

assert(i >= 2);

/* unroll 1 digit */

--i;

digit *digits = v->long_value.ob_digit;

size_t x = digits[i];

#if (SIZE_MAX >> PyLong_SHIFT) >= ((1 << PyLong_SHIFT) - 1)

/* unroll another digit */

x <<= PyLong_SHIFT;

--i;

x |= digits[i];

#endif

*iptr = i;

return x;

}

/* Get a C long int from an int object or any object that has an __index__

method.

On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of

the result. Otherwise *overflow is 0.

For other errors (e.g., TypeError), return -1 and set an error condition.

In this case *overflow will be 0.

*/

long

PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)

{

/* This version originally by Tim Peters */

PyLongObject *v;

long res;

Py_ssize_t i;

int sign;

int do_decref = 0; /* if PyNumber_Index was called */

*overflow = 0;

if (vv == NULL) {

PyErr_BadInternalCall();

return -1;

}

if (PyLong_Check(vv)) {

v = (PyLongObject *)vv;

}

else {

v = (PyLongObject *)_PyNumber_Index(vv);

if (v == NULL)

return -1;

do_decref = 1;

}

if (_PyLong_IsCompact(v)) {

#if SIZEOF_LONG < SIZEOF_SIZE_T

Py_ssize_t tmp = _PyLong_CompactValue(v);

if (tmp < LONG_MIN) {

*overflow = -1;

res = -1;

}

else if (tmp > LONG_MAX) {

*overflow = 1;

res = -1;

}

else {

res = (long)tmp;

}

#else

res = _PyLong_CompactValue(v);

#endif

}

else {

res = -1;

i = _PyLong_DigitCount(v);

sign = _PyLong_NonCompactSign(v);

unsigned long x = unroll_digits_ulong(v, &i);

while (--i >= 0) {

if (x > (ULONG_MAX >> PyLong_SHIFT)) {

*overflow = sign;

goto exit;

}

x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];

}

/* Haven't lost any bits, but casting to long requires extra

* care (see comment above).

*/

if (x <= (unsigned long)LONG_MAX) {

res = (long)x * sign;

}

else if (sign < 0 && x == PY_ABS_LONG_MIN) {

res = LONG_MIN;

}

else {

*overflow = sign;

/* res is already set to -1 */

}

}

exit:

if (do_decref) {

Py_DECREF(v);

}

return res;

}

/* Get a C long int from an int object or any object that has an __index__

method. Return -1 and set an error if overflow occurs. */

long

PyLong_AsLong(PyObject *obj)

{

int overflow;

long result = PyLong_AsLongAndOverflow(obj, &overflow);

if (overflow) {

/* XXX: could be cute and give a different

message for overflow == -1 */

PyErr_SetString(PyExc_OverflowError,

"Python int too large to convert to C long");

}

return result;

}

/* Get a C int from an int object or any object that has an __index__

method. Return -1 and set an error if overflow occurs. */

int

PyLong_AsInt(PyObject *obj)

{

int overflow;

long result = PyLong_AsLongAndOverflow(obj, &overflow);

if (overflow || result > INT_MAX || result < INT_MIN) {

/* XXX: could be cute and give a different

message for overflow == -1 */

PyErr_SetString(PyExc_OverflowError,

"Python int too large to convert to C int");

return -1;

}

return (int)result;

}

/* Get a Py_ssize_t from an int object.

Returns -1 and sets an error condition if overflow occurs. */

Py_ssize_t

PyLong_AsSsize_t(PyObject *vv) {

PyLongObject *v;

Py_ssize_t i;

int sign;

if (vv == NULL) {

PyErr_BadInternalCall();

return -1;

}

if (!PyLong_Check(vv)) {

PyErr_SetString(PyExc_TypeError, "an integer is required");

return -1;

}

v = (PyLongObject *)vv;

if (_PyLong_IsCompact(v)) {

return _PyLong_CompactValue(v);

}

i = _PyLong_DigitCount(v);

sign = _PyLong_NonCompactSign(v);

size_t x = unroll_digits_size_t(v, &i);

while (--i >= 0) {

if (x > (SIZE_MAX >> PyLong_SHIFT)) {

goto overflow;

}

x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];

}

/* Haven't lost any bits, but casting to a signed type requires

* extra care (see comment above).

*/

if (x <= (size_t)PY_SSIZE_T_MAX) {

return (Py_ssize_t)x * sign;

}

else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {

return PY_SSIZE_T_MIN;

}

/* else overflow */

overflow:

PyErr_SetString(PyExc_OverflowError,

"Python int too large to convert to C ssize_t");

return -1;

}

/* Get a C unsigned long int from an int object.

Returns -1 and sets an error condition if overflow occurs. */

unsigned long

PyLong_AsUnsignedLong(PyObject *vv)

{

PyLongObject *v;

Py_ssize_t i;

if (vv == NULL) {

PyErr_BadInternalCall();

return (unsigned long)-1;

}

if (!PyLong_Check(vv)) {

PyErr_SetString(PyExc_TypeError, "an integer is required");

return (unsigned long)-1;

}

v = (PyLongObject *)vv;

if (_PyLong_IsNonNegativeCompact(v)) {

#if SIZEOF_LONG < SIZEOF_SIZE_T

size_t tmp = (size_t)_PyLong_CompactValue(v);

unsigned long res = (unsigned long)tmp;

if (res != tmp) {

goto overflow;

}

return res;

#else

return (unsigned long)(size_t)_PyLong_CompactValue(v);

#endif

}

if (_PyLong_IsNegative(v)) {

PyErr_SetString(PyExc_OverflowError,

"can't convert negative value to unsigned int");

return (unsigned long) -1;

}

i = _PyLong_DigitCount(v);

unsigned long x = unroll_digits_ulong(v, &i);

while (--i >= 0) {

if (x > (ULONG_MAX >> PyLong_SHIFT)) {

goto overflow;

}

x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];

}

return x;

overflow:

PyErr_SetString(PyExc_OverflowError,

"Python int too large to convert "

"to C unsigned long");

return (unsigned long) -1;

}

/* Get a C size_t from an int object. Returns (size_t)-1 and sets

an error condition if overflow occurs. */

size_t

PyLong_AsSize_t(PyObject *vv)

{

PyLongObject *v;

Py_ssize_t i;

if (vv == NULL) {

PyErr_BadInternalCall();

return (size_t) -1;

}

if (!PyLong_Check(vv)) {

PyErr_SetString(PyExc_TypeError, "an integer is required");

return (size_t)-1;

}

v = (PyLongObject *)vv;

if (_PyLong_IsNonNegativeCompact(v)) {

return (size_t)_PyLong_CompactValue(v);

}

if (_PyLong_IsNegative(v)) {

PyErr_SetString(PyExc_OverflowError,

"can't convert negative value to size_t");

return (size_t) -1;

}

i = _PyLong_DigitCount(v);

size_t x = unroll_digits_size_t(v, &i);

while (--i >= 0) {

if (x > (SIZE_MAX >> PyLong_SHIFT)) {

PyErr_SetString(PyExc_OverflowError,

"Python int too large to convert to C size_t");

return (size_t) -1;

}

x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];

}

return x;

}

/* Get a C unsigned long int from an int object, ignoring the high bits.

Returns -1 and sets an error condition if an error occurs. */

static unsigned long

_PyLong_AsUnsignedLongMask(PyObject *vv)

{

PyLongObject *v;

Py_ssize_t i;

if (vv == NULL || !PyLong_Check(vv)) {

PyErr_BadInternalCall();

return (unsigned long) -1;

}

v = (PyLongObject *)vv;

if (_PyLong_IsCompact(v)) {

#if SIZEOF_LONG < SIZEOF_SIZE_T

return (unsigned long)(size_t)_PyLong_CompactValue(v);

#else

return (unsigned long)(long)_PyLong_CompactValue(v);

#endif

}

i = _PyLong_DigitCount(v);

int sign = _PyLong_NonCompactSign(v);

unsigned long x = unroll_digits_ulong(v, &i);

while (--i >= 0) {

x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];

}

return x * sign;

}

unsigned long

PyLong_AsUnsignedLongMask(PyObject *op)

{

PyLongObject *lo;

unsigned long val;

if (op == NULL) {

PyErr_BadInternalCall();

return (unsigned long)-1;

}

if (PyLong_Check(op)) {

return _PyLong_AsUnsignedLongMask(op);

}

lo = (PyLongObject *)_PyNumber_Index(op);

if (lo == NULL)

return (unsigned long)-1;

val = _PyLong_AsUnsignedLongMask((PyObject *)lo);

Py_DECREF(lo);

return val;

}

int

PyLong_IsPositive(PyObject *obj)

{

assert(obj != NULL);

if (!PyLong_Check(obj)) {

PyErr_Format(PyExc_TypeError, "expected int, got %T", obj);

return -1;

}

return _PyLong_IsPositive((PyLongObject *)obj);

}

int

PyLong_IsNegative(PyObject *obj)

{

assert(obj != NULL);

if (!PyLong_Check(obj)) {

PyErr_Format(PyExc_TypeError, "expected int, got %T", obj);

return -1;

}

return _PyLong_IsNegative((PyLongObject *)obj);

}

int

PyLong_IsZero(PyObject *obj)

{

assert(obj != NULL);

if (!PyLong_Check(obj)) {

PyErr_Format(PyExc_TypeError, "expected int, got %T", obj);

return -1;

}

return _PyLong_IsZero((PyLongObject *)obj);

}

static int

long_sign(PyObject *vv)

{

assert(vv != NULL);

assert(PyLong_Check(vv));

PyLongObject *v = (PyLongObject *)vv;

if (_PyLong_IsCompact(v)) {

return _PyLong_CompactSign(v);

}

return _PyLong_NonCompactSign(v);

}

int

_PyLong_Sign(PyObject *vv)

{

return long_sign(vv);

}

int

PyLong_GetSign(PyObject *vv, int *sign)

{

if (!PyLong_Check(vv)) {

PyErr_Format(PyExc_TypeError, "expect int, got %T", vv);

return -1;

}

*sign = long_sign(vv);

return 0;

}

static int

bit_length_digit(digit x)

{

// digit can be larger than unsigned long, but only PyLong_SHIFT bits

// of it will be ever used.

static_assert(PyLong_SHIFT <= sizeof(unsigned long) * 8,

"digit is larger than unsigned long");

return _Py_bit_length((unsigned long)x);

}

int64_t

_PyLong_NumBits(PyObject *vv)

{

PyLongObject *v = (PyLongObject *)vv;

int64_t result = 0;

Py_ssize_t ndigits;

int msd_bits;

assert(v != NULL);

assert(PyLong_Check(v));

ndigits = _PyLong_DigitCount(v);

assert(ndigits == 0 || v->long_value.ob_digit[ndigits - 1] != 0);

if (ndigits > 0) {

digit msd = v->long_value.ob_digit[ndigits - 1];

#if SIZEOF_SIZE_T == 8

assert(ndigits <= INT64_MAX / PyLong_SHIFT);

#endif

result = (int64_t)(ndigits - 1) * PyLong_SHIFT;

msd_bits = bit_length_digit(msd);

result += msd_bits;

}

return result;

}

PyObject *

_PyLong_FromByteArray(const unsigned char* bytes, size_t n,