longobject.c

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

#definemedium_value(x) ((stwodigits)_PyLong_CompactValue(x))

#defineIS_SMALL_INT(ival) (-_PY_NSMALLNEGINTS <= (ival) && (ival) < _PY_NSMALLPOSINTS)
#defineIS_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 */
#defineWITH_PYLONG_MODULE 1

staticinlinevoid
_Py_DECREF_INT(PyLongObject*op)
{
assert(PyLong_CheckExact(op));
_Py_DECREF_SPECIALIZED((PyObject*)op, (destructor)PyObject_Free);
}

staticinlineint
is_medium_int(stwodigitsx)
{
/* Take care that we are comparing unsigned values. */
twodigitsx_plus_mask= ((twodigits)x) +PyLong_MASK;
returnx_plus_mask< ((twodigits)PyLong_MASK) +PyLong_BASE;
}

staticPyObject*
get_small_int(sdigitival)
{
assert(IS_SMALL_INT(ival));
return (PyObject*)&_PyLong_SMALL_INTS[_PY_NSMALLNEGINTS+ival];
}

staticPyLongObject*
maybe_small_long(PyLongObject*v)
{
if (v&&_PyLong_IsCompact(v)) {
stwodigitsival=medium_value(v);
if (IS_SMALL_INT(ival)) {
_Py_DECREF_INT(v);
return (PyLongObject*)get_small_int((sdigit)ival);
 }
 }
returnv;
}

/* 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).
 */
#defineKARATSUBA_CUTOFF 70
#defineKARATSUBA_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.
 */
#defineEXP_WINDOW_SIZE 5
#defineEXP_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).
 */
#defineHUGE_EXP_CUTOFF 60

#defineSIGCHECK(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. */

staticPyLongObject*
long_normalize(PyLongObject*v)
{
Py_ssize_tj=_PyLong_DigitCount(v);
Py_ssize_ti=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);
 }
 }
returnv;
}

/* Allocate a new int object with size digits.
 Return NULL and set exception if we run out of memory. */

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

PyLongObject*
_PyLong_New(Py_ssize_tsize)
{
assert(size >= 0);
PyLongObject*result;
if (size> (Py_ssize_t)MAX_LONG_DIGITS) {
PyErr_SetString(PyExc_OverflowError,
"too many digits in integer");
returnNULL;
 }
/* Fast operations for single digit integers (including zero)
 * assume that there is always at least one digit present. */
Py_ssize_tndigits=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();
returnNULL;
 }
_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;
returnresult;
}

PyLongObject*
_PyLong_FromDigits(intnegative, Py_ssize_tdigit_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();
returnNULL;
 }
_PyLong_SetSignAndDigitCount(result, negative?-1:1, digit_count);
memcpy(result->long_value.ob_digit, digits, digit_count*sizeof(digit));
returnresult;
}

PyObject*
_PyLong_Copy(PyLongObject*src)
{
assert(src!=NULL);

if (_PyLong_IsCompact(src)) {
stwodigitsival=medium_value(src);
if (IS_SMALL_INT(ival)) {
returnget_small_int((sdigit)ival);
 }
 }
Py_ssize_tsize=_PyLong_DigitCount(src);
return (PyObject*)_PyLong_FromDigits(_PyLong_IsNegative(src), size, src->long_value.ob_digit);
}

staticPyObject*
_PyLong_FromMedium(sdigitx)
{
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();
returnNULL;
 }
digitabs_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;
}

staticPyObject*
_PyLong_FromLarge(stwodigitsival)
{
twodigitsabs_ival;
intsign;
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);
twodigitst=abs_ival >> (PyLong_SHIFT*2);
Py_ssize_tndigits=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 */
staticinlinePyObject*
_PyLong_FromSTwoDigits(stwodigitsx)
{
if (IS_SMALL_INT(x)) {
returnget_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(longival)
{
PyLongObject*v;
unsigned longabs_ival, t;
intndigits;

/* Handle small and medium cases. */
if (IS_SMALL_INT(ival)) {
returnget_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;
}

#definePYLONG_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_tndigits=0; \
INT_TYPEt= (ival); \
while (t) { \
++ndigits; \
t >>= PyLong_SHIFT; \
 } \
PyLongObject*v=_PyLong_New(ndigits); \
if (v==NULL) { \
returnNULL; \
 } \
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(unsignedlongival)
{
PYLONG_FROM_UINT(unsigned long, ival);
}

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

PyObject*
PyLong_FromUnsignedLongLong(unsigned long longival)
{
PYLONG_FROM_UINT(unsigned long long, ival);
}

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

PyObject*
PyLong_FromSize_t(size_tival)
{
PYLONG_FROM_UINT(size_t, ival);
}

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

PyObject*
PyLong_FromDouble(doubledval)
{
/* 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).
 */
constdoubleint_max= (unsigned long)LONG_MAX+1;
if (-int_max<dval&&dval<int_max) {
returnPyLong_FromLong((long)dval);
 }

PyLongObject*v;
doublefrac;
inti, ndig, expo, neg;
neg=0;
if (Py_IS_INFINITY(dval)) {
PyErr_SetString(PyExc_OverflowError,
"cannot convert float infinity to integer");
returnNULL;
 }
if (Py_IS_NAN(dval)) {
PyErr_SetString(PyExc_ValueError,
"cannot convert float NaN to integer");
returnNULL;
 }
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)
returnNULL;
frac=ldexp(frac, (expo-1) % PyLong_SHIFT+1);
for (i=ndig; --i >= 0; ) {
digitbits= (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-".
 */
#definePY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)
#definePY_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 longx, prev;
longres;
Py_ssize_ti;
intsign;
intdo_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)) {
#ifSIZEOF_LONG<SIZEOF_SIZE_T
Py_ssize_ttmp=_PyLong_CompactValue(v);
if (tmp<LONG_MIN) {
*overflow=-1;
res=-1;
 }
elseif (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;
 }
elseif (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);
 }
returnres;
}

/* 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)
{
intoverflow;
longresult=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");
 }
returnresult;
}

/* 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)
{
intoverflow;
longresult=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_tx, prev;
Py_ssize_ti;
intsign;

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;
 }
elseif (sign<0&&x==PY_ABS_SSIZE_T_MIN) {
returnPY_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 longx, prev;
Py_ssize_ti;

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)) {
#ifSIZEOF_LONG<SIZEOF_SIZE_T
size_ttmp= (size_t)_PyLong_CompactValue(v);
unsigned longres= (unsigned long)tmp;
if (res!=tmp) {
 goto overflow;
 }
returnres;
#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;
 }
 }
returnx;
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_tx, prev;
Py_ssize_ti;

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;
 }
 }
returnx;
}

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

staticunsigned long
_PyLong_AsUnsignedLongMask(PyObject*vv)
{
PyLongObject*v;
unsigned longx;
Py_ssize_ti;

if (vv==NULL|| !PyLong_Check(vv)) {
PyErr_BadInternalCall();
return (unsigned long) -1;
 }
v= (PyLongObject*)vv;
if (_PyLong_IsCompact(v)) {
#ifSIZEOF_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);
intsign=_PyLong_NonCompactSign(v);
x=0;
while (--i >= 0) {
x= (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
 }
returnx*sign;
}

unsigned long
PyLong_AsUnsignedLongMask(PyObject*op)
{
PyLongObject*lo;
unsigned longval;

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

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

staticint
bit_length_digit(digitx)
{
// 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_tresult=0;
Py_ssize_tndigits;
intmsd_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) {
digitmsd=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;
 }
returnresult;

Overflow:
PyErr_SetString(PyExc_OverflowError, "int has too many bits "
"to express in a platform size_t");
return (size_t)-1;
}

PyObject*
_PyLong_FromByteArray(constunsigned char*bytes, size_tn,
intlittle_endian, intis_signed)
{
constunsigned char*pstartbyte; /* LSB of bytes */
intincr; /* direction to move pstartbyte */
constunsigned char*pendbyte; /* MSB of bytes */
size_tnumsignificantbytes; /* number of bytes that matter */
Py_ssize_tndigits; /* number of Python int digits */
PyLongObject*v; /* result */
Py_ssize_tidigit=0; /* next free index in v->long_value.ob_digit */

if (n==0)
returnPyLong_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_ti;
constunsigned char*p=pendbyte;
constintpincr=-incr; /* search MSB to LSB */
constunsigned charinsignificant=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");
returnNULL;
 }
ndigits= (numsignificantbytes*8+PyLong_SHIFT-1) / PyLong_SHIFT;
v=_PyLong_New(ndigits);
if (v==NULL)
returnNULL;

/* 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_ti;
twodigitscarry=1; /* for 2's-comp calculation */
twodigitsaccum=0; /* sliding register */
unsigned intaccumbits=0; /* number of bits in accum */
constunsigned char*p=pstartbyte;

for (i=0; i<numsignificantbytes; ++i, p+=incr) {
twodigitsthisbyte=*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;
 }
 }

intsign=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_tn,
intlittle_endian, intis_signed,
intwith_exceptions)
{
Py_ssize_ti; /* index into v->long_value.ob_digit */
Py_ssize_tndigits; /* number of digits */
twodigitsaccum; /* sliding register */
unsigned intaccumbits; /* # bits in accum */
intdo_twos_comp; /* store 2's-comp? is_signed and v < 0 */
digitcarry; /* for computing 2's-comp */
size_tj; /* # bytes filled */
unsigned char*p; /* pointer to next byte in bytes */
intpincr; /* 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) {
digitthisdigit=v->long_value.ob_digit[i];
if (do_twos_comp) {
thisdigit= (thisdigit ^ PyLong_MASK) +carry;
carry=thisdigit >> PyLong_SHIFT;