/* 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_long.h" // _Py_SmallInts

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

#include "pycore_runtime.h" // _PY_NSMALLPOSINTS

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

#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

static inline void

_Py_DECREF_INT(PyLongObject *op)

{

assert(PyLong_CheckExact(op));

_Py_DECREF_SPECIALIZED((PyObject *)op, (destructor)PyObject_Free);

}

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. */

#define MAX_LONG_DIGITS \

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

PyLongObject *

_PyLong_New(Py_ssize_t size)

{

assert(size >= 0);

PyLongObject *result;

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;

/* 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;

}

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

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

/* The digit has to be initialized explicitly to avoid

* use-of-uninitialized-value. */

result->long_value.ob_digit[0] = 0;

return result;

}

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 = _PyLong_New(digit_count);

if (result == NULL) {

PyErr_NoMemory();

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);

if (_PyLong_IsCompact(src)) {

stwodigits ival = medium_value(src);

if (IS_SMALL_INT(ival)) {

return get_small_int((sdigit)ival);

}

}

Py_ssize_t size = _PyLong_DigitCount(src);

return (PyObject *)_PyLong_FromDigits(_PyLong_IsNegative(src), size, src->long_value.ob_digit);

}

static PyObject *

_PyLong_FromMedium(sdigit x)

{

assert(!IS_SMALL_INT(x));

assert(is_medium_int(x));

/* We could use a freelist here */

PyLongObject *v = PyObject_Malloc(sizeof(PyLongObject));

if (v == NULL) {

PyErr_NoMemory();

return NULL;

}

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

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

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

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 = _PyLong_New(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 PyObject *

_PyLong_FromSTwoDigits(stwodigits x)

{

if (IS_SMALL_INT(x)) {

return get_small_int((sdigit)x);

}

assert(x != 0);

if (is_medium_int(x)) {

return _PyLong_FromMedium((sdigit)x);

}

return _PyLong_FromLarge(x);

}

/* 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 (Py_REFCNT(x) == 1) {

_PyLong_FlipSign(x);

return;

}

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

Py_DECREF(x);

}

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

PyObject *

PyLong_FromLong(long ival)

{

PyLongObject *v;

unsigned long abs_ival, t;

int ndigits;

/* Handle small and medium cases. */

if (IS_SMALL_INT(ival)) {

return get_small_int((sdigit)ival);

}

if (-(long)PyLong_MASK <= ival && ival <= (long)PyLong_MASK) {

return _PyLong_FromMedium((sdigit)ival);

}

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

abs_ival = ival < 0 ? 0U-(unsigned long)ival : (unsigned long)ival;

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

t = abs_ival >> PyLong_SHIFT >> PyLong_SHIFT;

ndigits = 2;

while (t) {

++ndigits;

t >>= PyLong_SHIFT;

}

/* Construct output value. */

v = _PyLong_New(ndigits);

if (v != 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;

}

#define PYLONG_FROM_UINT(INT_TYPE, ival) \

do { \

if (IS_SMALL_UINT(ival)) { \

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

} \

/* Count the number of Python digits. */ \

Py_ssize_t ndigits = 0; \

INT_TYPE t = (ival); \

while (t) { \

++ndigits; \

t >>= PyLong_SHIFT; \

} \

PyLongObject *v = _PyLong_New(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 (Py_IS_INFINITY(dval)) {

PyErr_SetString(PyExc_OverflowError,

"cannot convert float infinity to integer");

return NULL;

}

if (Py_IS_NAN(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 = _PyLong_New(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)

/* 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 by Tim Peters */

PyLongObject *v;

unsigned long x, prev;

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);

x = 0;

while (--i >= 0) {

prev = x;

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

if ((x >> PyLong_SHIFT) != prev) {

*overflow = sign;

goto exit;

}

}

/* 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;

size_t x, prev;

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);

x = 0;

while (--i >= 0) {

prev = x;

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

if ((x >> PyLong_SHIFT) != prev)

goto overflow;

}

/* 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;

unsigned long x, prev;

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);

x = 0;

while (--i >= 0) {

prev = x;

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

if ((x >> PyLong_SHIFT) != prev) {

goto overflow;

}

}

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;

size_t x, prev;

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);

x = 0;

while (--i >= 0) {

prev = x;

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

if ((x >> PyLong_SHIFT) != prev) {

PyErr_SetString(PyExc_OverflowError,

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

return (size_t) -1;

}

}

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;

unsigned long x;

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);

x = 0;

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_Sign(PyObject *vv)

{

PyLongObject *v = (PyLongObject *)vv;

assert(v != NULL);

assert(PyLong_Check(v));

if (_PyLong_IsCompact(v)) {

return _PyLong_CompactSign(v);

}

return _PyLong_NonCompactSign(v);

}

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);

}

size_t

_PyLong_NumBits(PyObject *vv)

{

PyLongObject *v = (PyLongObject *)vv;

size_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 ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)

goto Overflow;

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

msd_bits = bit_length_digit(msd);

if (SIZE_MAX - msd_bits < result)

goto Overflow;

result += msd_bits;

}

return result;

Overflow:

PyErr_SetString(PyExc_OverflowError, "int has too many bits "

"to express in a platform size_t");

return (size_t)-1;

}

PyObject *

_PyLong_FromByteArray(const unsigned char* bytes, size_t n,

int little_endian, int is_signed)

{

const unsigned char* pstartbyte; /* LSB of bytes */

int incr; /* direction to move pstartbyte */

const unsigned char* pendbyte; /* MSB of bytes */

size_t numsignificantbytes; /* number of bytes that matter */

Py_ssize_t ndigits; /* number of Python int digits */

PyLongObject* v; /* result */

Py_ssize_t idigit = 0; /* next free index in v->long_value.ob_digit */

if (n == 0)

return PyLong_FromLong(0L);

if (little_endian) {

pstartbyte = bytes;

pendbyte = bytes + n - 1;

incr = 1;

}

else {

pstartbyte = bytes + n - 1;

pendbyte = bytes;

incr = -1;

}

if (is_signed)

is_signed = *pendbyte >= 0x80;

/* Compute numsignificantbytes. This consists of finding the most

significant byte. Leading 0 bytes are insignificant if the number

is positive, and leading 0xff bytes if negative. */

{

size_t i;

const unsigned char* p = pendbyte;

const int pincr = -incr; /* search MSB to LSB */

const unsigned char insignificant = is_signed ? 0xff : 0x00;

for (i = 0; i < n; ++i, p += pincr) {

if (*p != insignificant)

break;

}

numsignificantbytes = n - i;

/* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so

actually has 2 significant bytes. OTOH, 0xff0001 ==

-0x00ffff, so we wouldn't *need* to bump it there; but we

do for 0xffff = -0x0001. To be safe without bothering to

check every case, bump it regardless. */

if (is_signed && numsignificantbytes < n)

++numsignificantbytes;

}

/* avoid integer overflow */

ndigits = numsignificantbytes / PyLong_SHIFT * 8

+ (numsignificantbytes % PyLong_SHIFT * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;

v = _PyLong_New(ndigits);

if (v == NULL)

return NULL;

/* Copy the bits over. The tricky parts are computing 2's-comp on

the fly for signed numbers, and dealing with the mismatch between

8-bit bytes and (probably) 15-bit Python digits.*/

{

size_t i;

twodigits carry = 1; /* for 2's-comp calculation */

twodigits accum = 0; /* sliding register */

unsigned int accumbits = 0; /* number of bits in accum */

const unsigned char* p = pstartbyte;

for (i = 0; i < numsignificantbytes; ++i, p += incr) {

twodigits thisbyte = *p;

/* Compute correction for 2's comp, if needed. */

if (is_signed) {

thisbyte = (0xff ^ thisbyte) + carry;

carry = thisbyte >> 8;

thisbyte &= 0xff;

}

/* Because we're going LSB to MSB, thisbyte is

more significant than what's already in accum,

so needs to be prepended to accum. */

accum |= thisbyte << accumbits;

accumbits += 8;

if (accumbits >= PyLong_SHIFT) {

/* There's enough to fill a Python digit. */

assert(idigit < ndigits);

v->long_value.ob_digit[idigit] = (digit)(accum & PyLong_MASK);

++idigit;

accum >>= PyLong_SHIFT;

accumbits -= PyLong_SHIFT;

assert(accumbits < PyLong_SHIFT);

}

}

assert(accumbits < PyLong_SHIFT);

if (accumbits) {

assert(idigit < ndigits);

v->long_value.ob_digit[idigit] = (digit)accum;

++idigit;

}

}

int sign = is_signed ? -1: 1;

if (idigit == 0) {

sign = 0;

}

_PyLong_SetSignAndDigitCount(v, sign, idigit);

return (PyObject *)maybe_small_long(long_normalize(v));

}

int

_PyLong_AsByteArray(PyLongObject* v,

unsigned char* bytes, size_t n,

int little_endian, int is_signed,

int with_exceptions)

{

Py_ssize_t i; /* index into v->long_value.ob_digit */

Py_ssize_t ndigits; /* number of digits */

twodigits accum; /* sliding register */

unsigned int accumbits; /* # bits in accum */

int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */

digit carry; /* for computing 2's-comp */

size_t j; /* # bytes filled */

unsigned char* p; /* pointer to next byte in bytes */

int pincr; /* direction to move p */

assert(v != NULL && PyLong_Check(v));

ndigits = _PyLong_DigitCount(v);

if (_PyLong_IsNegative(v)) {

if (!is_signed) {

if (with_exceptions) {

PyErr_SetString(PyExc_OverflowError,

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

}

return -1;

}

do_twos_comp = 1;

}

else {

do_twos_comp = 0;

}

if (little_endian) {

p = bytes;

pincr = 1;

}

else {

p = bytes + n - 1;

pincr = -1;

}

/* Copy over all the Python digits.

It's crucial that every Python digit except for the MSD contribute

exactly PyLong_SHIFT bits to the total, so first assert that the int is

normalized.

NOTE: PyLong_AsNativeBytes() assumes that this function will fill in 'n'

bytes even if it eventually fails to convert the whole number. Make sure

you account for that if you are changing this algorithm to return without

doing that.

*/

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

j = 0;

accum = 0;

accumbits = 0;

carry = do_twos_comp ? 1 : 0;

for (i = 0; i < ndigits; ++i) {

digit thisdigit = v->long_value.ob_digit[i];

if (do_twos_comp) {

thisdigit = (thisdigit ^ PyLong_MASK) + carry;

carry = thisdigit >> PyLong_SHIFT;

thisdigit &= PyLong_MASK;

}

/* Because we're going LSB to MSB, thisdigit is more

significant than what's already in accum, so needs to be

prepended to accum. */

accum |= (twodigits)thisdigit << accumbits;