#include "Python.h"

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

#include "pycore_interp.h" // _PY_NSMALLPOSINTS

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

#include "pycore_pystate.h" // _Py_IsMainInterpreter()

#include "longintrepr.h"

#include <float.h>

#include <ctype.h>

#include <stddef.h>

#include "clinic/longobject.c.h"

#define NSMALLPOSINTS _PY_NSMALLPOSINTS

#define NSMALLNEGINTS _PY_NSMALLNEGINTS

_Py_IDENTIFIER(little);

_Py_IDENTIFIER(big);

#define MEDIUM_VALUE(x) (assert(-1 <= Py_SIZE(x) && Py_SIZE(x) <= 1), \

Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \

(Py_SIZE(x) == 0 ? (sdigit)0 : \

(sdigit)(x)->ob_digit[0]))

PyObject *_PyLong_Zero = NULL;

PyObject *_PyLong_One = NULL;

#if NSMALLNEGINTS + NSMALLPOSINTS > 0

#define IS_SMALL_INT(ival) (-NSMALLNEGINTS <= (ival) && (ival) < NSMALLPOSINTS)

#define IS_SMALL_UINT(ival) ((ival) < NSMALLPOSINTS)

static PyObject *

get_small_int(sdigit ival)

{

assert(IS_SMALL_INT(ival));

PyInterpreterState *interp = _PyInterpreterState_GET();

PyObject *v = (PyObject*)interp->small_ints[ival + NSMALLNEGINTS];

Py_INCREF(v);

return v;

}

static PyLongObject *

maybe_small_long(PyLongObject *v)

{

if (v && Py_ABS(Py_SIZE(v)) <= 1) {

sdigit ival = MEDIUM_VALUE(v);

if (IS_SMALL_INT(ival)) {

Py_DECREF(v);

return (PyLongObject *)get_small_int(ival);

}

}

return v;

}

#define IS_SMALL_INT(ival) 0

#define IS_SMALL_UINT(ival) 0

#define get_small_int(ival) (Py_UNREACHABLE(), NULL)

#define maybe_small_long(val) (val)

#ifndef PyLong_MAXFREELIST

# define PyLong_MAXFREELIST 100

Py_LOCAL_INLINE(void)

_PyLong_Negate(PyLongObject **x_p)

{

PyLongObject *x;

x = (PyLongObject *)*x_p;

if (Py_REFCNT(x) == 1) {

Py_SET_SIZE(x, -Py_SIZE(x));

return;

}

*x_p = (PyLongObject *)PyLong_FromLong(-MEDIUM_VALUE(x));

Py_DECREF(x);

}

#define KARATSUBA_CUTOFF 70

#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)

#define FIVEARY_CUTOFF 8

#define SIGCHECK(PyTryBlock) \

do { \

if (PyErr_CheckSignals()) PyTryBlock \

} while(0)

static PyLongObject *

long_normalize(PyLongObject *v)

{

Py_ssize_t j = Py_ABS(Py_SIZE(v));

Py_ssize_t i = j;

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

--i;

if (i != j) {

Py_SET_SIZE(v, (Py_SIZE(v) < 0) ? -(i) : i);

}

return v;

}

#define MAX_LONG_DIGITS \

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

PyLongObject *

_PyLong_New(Py_ssize_t size)

{

struct _Py_long_state *state = &_PyInterpreterState_GET()->long_state;

#ifdef Py_DEBUG

// _PyLong_New() must not be called after _PyLong_Fini()

assert(state->numfree != -1);

PyLongObject *result;

if (size == 1 && (result = (PyLongObject*)state->free_list) != NULL) {

state->free_list = (PyLongObject *)Py_TYPE(result);

state->numfree--;

}

else {

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

if (size > (Py_ssize_t)MAX_LONG_DIGITS) {

PyErr_SetString(PyExc_OverflowError,

"too many digits in integer");

return NULL;

}

result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +

size*sizeof(digit));

if (!result) {

PyErr_NoMemory();

return NULL;

}

}

_PyObject_InitVar((PyVarObject*)result, &PyLong_Type, size);

return result;

}

PyObject *

_PyLong_Copy(PyLongObject *src)

{

PyLongObject *result;

Py_ssize_t i;

assert(src != NULL);

i = Py_SIZE(src);

if (i < 0)

i = -(i);

if (i < 2) {

sdigit ival = MEDIUM_VALUE(src);

if (IS_SMALL_INT(ival)) {

return get_small_int(ival);

}

}

result = _PyLong_New(i);

if (result != NULL) {

Py_SET_SIZE(result, Py_SIZE(src));

while (--i >= 0) {

result->ob_digit[i] = src->ob_digit[i];

}

}

return (PyObject *)result;

}

PyObject *

PyLong_FromLong(long ival)

{

PyLongObject *v;

unsigned long abs_ival;

unsigned long t; /* unsigned so >> doesn't propagate sign bit */

int ndigits = 0;

int sign;

if (IS_SMALL_INT(ival)) {

return get_small_int((sdigit)ival);

}

if (ival < 0) {

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

abs_ival = 0U-(unsigned long)ival;

sign = -1;

}

else {

abs_ival = (unsigned long)ival;

sign = ival == 0 ? 0 : 1;

}

/* Fast path for single-digit ints */

if (abs_ival < (1UL << PyLong_SHIFT)) {

v = _PyLong_New(1);

if (v) {

Py_SET_SIZE(v, sign);

v->ob_digit[0] = Py_SAFE_DOWNCAST(

abs_ival, unsigned long, digit);

}

return (PyObject*)v;

}

#if 2*PyLong_SHIFT < 8*PY_LONG_SIZE

/* 2 digits */

if (abs_ival < (1UL << 2*PyLong_SHIFT)) {

v = _PyLong_New(2);

if (v) {

Py_SET_SIZE(v, 2 * sign);

v->ob_digit[0] = Py_SAFE_DOWNCAST(

abs_ival & PyLong_MASK, unsigned long, digit);

v->ob_digit[1] = Py_SAFE_DOWNCAST(

abs_ival >> PyLong_SHIFT, unsigned long, digit);

}

return (PyObject*)v;

}

/* Larger numbers: loop to determine number of digits */

t = abs_ival;

while (t) {

++ndigits;

t >>= PyLong_SHIFT;

}

v = _PyLong_New(ndigits);

if (v != NULL) {

digit *p = v->ob_digit;

Py_SET_SIZE(v, ndigits * sign);

t = abs_ival;

while (t) {

*p++ = Py_SAFE_DOWNCAST(

t & PyLong_MASK, unsigned long, digit);

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->ob_digit; \

while ((ival)) { \

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

(ival) >>= PyLong_SHIFT; \

} \

return (PyObject *)v; \

} while(0)

PyObject *

PyLong_FromUnsignedLong(unsigned long ival)

{

PYLONG_FROM_UINT(unsigned long, ival);

}

PyObject *

PyLong_FromUnsignedLongLong(unsigned long long ival)

{

PYLONG_FROM_UINT(unsigned long long, ival);

}

PyObject *

PyLong_FromSize_t(size_t ival)

{

PYLONG_FROM_UINT(size_t, ival);

}

PyObject *

PyLong_FromDouble(double dval)

{

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

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->ob_digit[i] = bits;

frac = frac - (double)bits;

frac = ldexp(frac, PyLong_SHIFT);

}

if (neg) {

Py_SET_SIZE(v, -(Py_SIZE(v)));

}

return (PyObject *)v;

}

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

#define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)

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;

}

res = -1;

i = Py_SIZE(v);

switch (i) {

case -1:

res = -(sdigit)v->ob_digit[0];

break;

case 0:

res = 0;

break;

case 1:

res = v->ob_digit[0];

break;

default:

sign = 1;

x = 0;

if (i < 0) {

sign = -1;

i = -(i);

}

while (--i >= 0) {

prev = x;

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

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

*overflow = sign;

goto exit;

}

}

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

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;

}

PyLong_AsLong(PyObject *obj)

{

int overflow;

long result = PyLong_AsLongAndOverflow(obj, &overflow);

if (overflow) {

/* XXX: could be cute and give a different

PyErr_SetString(PyExc_OverflowError,

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

}

return result;

}

_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

PyErr_SetString(PyExc_OverflowError,

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

return -1;

}

return (int)result;

}

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;

i = Py_SIZE(v);

switch (i) {

case -1: return -(sdigit)v->ob_digit[0];

case 0: return 0;

case 1: return v->ob_digit[0];

}

sign = 1;

x = 0;

if (i < 0) {

sign = -1;

i = -(i);

}

while (--i >= 0) {

prev = x;

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

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

goto overflow;

}

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

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;

}

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;

i = Py_SIZE(v);

x = 0;

if (i < 0) {

PyErr_SetString(PyExc_OverflowError,

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

return (unsigned long) -1;

}

switch (i) {

case 0: return 0;

case 1: return v->ob_digit[0];

}

while (--i >= 0) {

prev = x;

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

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

PyErr_SetString(PyExc_OverflowError,

"Python int too large to convert "

"to C unsigned long");

return (unsigned long) -1;

}

}

return x;

}

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;

i = Py_SIZE(v);

x = 0;

if (i < 0) {

PyErr_SetString(PyExc_OverflowError,

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

return (size_t) -1;

}

switch (i) {

case 0: return 0;

case 1: return v->ob_digit[0];

}

while (--i >= 0) {

prev = x;

x = (x << PyLong_SHIFT) | v->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;

}

static unsigned long

_PyLong_AsUnsignedLongMask(PyObject *vv)

{

PyLongObject *v;

unsigned long x;

Py_ssize_t i;

int sign;

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

PyErr_BadInternalCall();

return (unsigned long) -1;

}

v = (PyLongObject *)vv;

i = Py_SIZE(v);

switch (i) {

case 0: return 0;

case 1: return v->ob_digit[0];

}

sign = 1;

x = 0;

if (i < 0) {

sign = -1;

i = -i;

}

while (--i >= 0) {

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

}

return x * sign;

}

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;

}

_PyLong_Sign(PyObject *vv)

{

PyLongObject *v = (PyLongObject *)vv;

assert(v != NULL);

assert(PyLong_Check(v));

return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);

}

static int

bit_length_digit(digit x)

{

Py_BUILD_ASSERT(PyLong_SHIFT <= sizeof(unsigned long) * 8);

return _Py_bit_length((unsigned long)x);

}

_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 = Py_ABS(Py_SIZE(v));

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

if (ndigits > 0) {

digit msd = v->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->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

{

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

if (is_signed && numsignificantbytes < n)

++numsignificantbytes;

}

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

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

{

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

accum |= thisbyte << accumbits;

accumbits += 8;

if (accumbits >= PyLong_SHIFT) {

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

assert(idigit < ndigits);

v->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->ob_digit[idigit] = (digit)accum;

++idigit;

}

}

Py_SET_SIZE(v, is_signed ? -idigit : idigit);

return (PyObject *)long_normalize(v);

}

_PyLong_AsByteArray(PyLongObject* v,

unsigned char* bytes, size_t n,

int little_endian, int is_signed)

{

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

Py_ssize_t ndigits; /* |v->ob_size| */

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

if (Py_SIZE(v) < 0) {

ndigits = -(Py_SIZE(v));

if (!is_signed) {

PyErr_SetString(PyExc_OverflowError,

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

return -1;

}

do_twos_comp = 1;

}

else {

ndigits = Py_SIZE(v);

do_twos_comp = 0;

}

if (little_endian) {

p = bytes;

pincr = 1;

}

else {

p = bytes + n - 1;

pincr = -1;

}

/* Copy over all the Python digits.

assert(ndigits == 0 || v->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->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

accum |= (twodigits)thisdigit << accumbits;

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

if (i == ndigits - 1) {

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

digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;

while (s != 0) {

s >>= 1;

accumbits++;

}

}

else

accumbits += PyLong_SHIFT;

/* Store as many bytes as possible. */

while (accumbits >= 8) {

if (j >= n)

goto Overflow;

++j;

*p = (unsigned char)(accum & 0xff);

p += pincr;

accumbits -= 8;

accum >>= 8;

}

}

/* Store the straggler (if any). */

assert(accumbits < 8);

assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */

if (accumbits > 0) {

if (j >= n)

goto Overflow;

++j;

if (do_twos_comp) {

/* Fill leading bits of the byte with sign bits

accum |= (~(twodigits)0) << accumbits;

}

*p = (unsigned char)(accum & 0xff);

p += pincr;

}

else if (j == n && n > 0 && is_signed) {

/* The main loop filled the byte array exactly, so the code

unsigned char msb = *(p - pincr);

int sign_bit_set = msb >= 0x80;

assert(accumbits == 0);

if (sign_bit_set == do_twos_comp)

return 0;

else

goto Overflow;

}

/* Fill remaining bytes with copies of the sign bit. */

{

unsigned char signbyte = do_twos_comp ? 0xffU : 0U;

for ( ; j < n; ++j, p += pincr)

*p = signbyte;

}

return 0;

Overflow:

PyErr_SetString(PyExc_OverflowError, "int too big to convert");

return -1;

}

PyObject *