/* 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_NSMALLNEGINTS <= (ival) && (ival) < _PY_NSMALLPOSINTS)

#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_VOID_P

intptr_t tmp = _PyLong_CompactValue(v);

res = (long)tmp;

if (res != tmp) {

*overflow = tmp < 0 ? -1 : 1;

}

#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_VOID_P

intptr_t tmp = _PyLong_CompactValue(v);

unsigned long res = (unsigned long)tmp;

if (res != tmp) {

goto overflow;

}

#else

return _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 _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)) {

return (unsigned long)_PyLong_CompactValue(v);

}

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;

}

/* How many Python int digits do we need? We have

8*numsignificantbytes bits, and each Python int digit has

PyLong_SHIFT bits, so it's the ceiling of the quotient. */

/* catch overflow before it happens */

if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {

PyErr_SetString(PyExc_OverflowError,

"byte array too long to convert to int");

return NULL;

}

ndigits = (numsignificantbytes * 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)

{

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

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

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;

/* The most-significant digit may be (probably is) at least

partly empty. */

if (i == ndigits - 1) {

/* Count # of sign bits -- they needn't be stored,

* although for signed conversion we need later to

* make sure at least one sign bit gets stored. */

digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;

while (s != 0) {

s >>= 1;

accumbits++;

}

}

else