#include "Python.h"

#include "longintrepr.h"

#include <float.h>

#include <ctype.h>

#include <stddef.h>

#include "clinic/longobject.c.h"

#ifndef NSMALLPOSINTS

#define NSMALLPOSINTS 257

#ifndef NSMALLNEGINTS

#define NSMALLNEGINTS 5

_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

static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

#ifdef COUNT_ALLOCS

Py_ssize_t _Py_quick_int_allocs, _Py_quick_neg_int_allocs;

static PyObject *

get_small_int(sdigit ival)

{

PyObject *v;

assert(-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS);

v = (PyObject *)&small_ints[ival + NSMALLNEGINTS];

Py_INCREF(v);

#ifdef COUNT_ALLOCS

if (ival >= 0)

_Py_quick_int_allocs++;

else

_Py_quick_neg_int_allocs++;

return v;

}

#define CHECK_SMALL_INT(ival) \

do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \

return get_small_int((sdigit)ival); \

} while(0)

static PyLongObject *

maybe_small_long(PyLongObject *v)

{

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

sdigit ival = MEDIUM_VALUE(v);

if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {

Py_DECREF(v);

return (PyLongObject *)get_small_int(ival);

}

}

return v;

}

#define CHECK_SMALL_INT(ival)

#define maybe_small_long(val) (val)

Py_LOCAL_INLINE(void)

_PyLong_Negate(PyLongObject **x_p)

{

PyLongObject *x;

x = (PyLongObject *)*x_p;

if (Py_REFCNT(x) == 1) {

Py_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_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;

return v;

}

PyLongObject *

_PyLong_FromNbInt(PyObject *integral)

{

PyNumberMethods *nb;

PyObject *result;

/* Fast path for the case that we already have an int. */

if (PyLong_CheckExact(integral)) {

Py_INCREF(integral);

return (PyLongObject *)integral;

}

nb = Py_TYPE(integral)->tp_as_number;

if (nb == NULL || nb->nb_int == NULL) {

PyErr_Format(PyExc_TypeError,

"an integer is required (got type %.200s)",

Py_TYPE(integral)->tp_name);

return NULL;

}

/* Convert using the nb_int slot, which should return something

result = nb->nb_int(integral);

if (!result || PyLong_CheckExact(result))

return (PyLongObject *)result;

if (!PyLong_Check(result)) {

PyErr_Format(PyExc_TypeError,

"__int__ returned non-int (type %.200s)",

result->ob_type->tp_name);

Py_DECREF(result);

return NULL;

}

/* Issue #17576: warn if 'result' not of exact type int. */

if (PyErr_WarnFormat(PyExc_DeprecationWarning, 1,

"__int__ returned non-int (type %.200s). "

"The ability to return an instance of a strict subclass of int "

"is deprecated, and may be removed in a future version of Python.",

result->ob_type->tp_name)) {

Py_DECREF(result);

return NULL;

}

return (PyLongObject *)result;

}

#define MAX_LONG_DIGITS \

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

PyLongObject *

_PyLong_New(Py_ssize_t size)

{

PyLongObject *result;

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

}

return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);

}

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

CHECK_SMALL_INT(ival);

}

result = _PyLong_New(i);

if (result != NULL) {

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

CHECK_SMALL_INT(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 >> PyLong_SHIFT)) {

v = _PyLong_New(1);

if (v) {

Py_SIZE(v) = sign;

v->ob_digit[0] = Py_SAFE_DOWNCAST(

abs_ival, unsigned long, digit);

}

return (PyObject*)v;

}

#if PyLong_SHIFT==15

/* 2 digits */

if (!(abs_ival >> 2*PyLong_SHIFT)) {

v = _PyLong_New(2);

if (v) {

Py_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_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;

}

PyObject *

PyLong_FromUnsignedLong(unsigned long ival)

{

PyLongObject *v;

unsigned long t;

int ndigits = 0;

if (ival < PyLong_BASE)

return PyLong_FromLong(ival);

/* Count the number of Python digits. */

t = ival;

while (t) {

++ndigits;

t >>= PyLong_SHIFT;

}

v = _PyLong_New(ndigits);

if (v != NULL) {

digit *p = v->ob_digit;

while (ival) {

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

ival >>= PyLong_SHIFT;

}

}

return (PyObject *)v;

}

PyObject *

PyLong_FromDouble(double 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 */

if (expo <= 0)

return PyLong_FromLong(0L);

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_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 nb_int was called */

*overflow = 0;

if (vv == NULL) {

PyErr_BadInternalCall();

return -1;

}

if (PyLong_Check(vv)) {

v = (PyLongObject *)vv;

}

else {

v = _PyLong_FromNbInt(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 = _PyLong_FromNbInt(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 const unsigned char BitLengthTable[32] = {

0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,

5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5

};

static int

bits_in_digit(digit d)

{

int d_bits = 0;

while (d >= 32) {

d_bits += 6;

d >>= 6;

}

d_bits += (int)BitLengthTable[d];

return d_bits;

}

_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 = bits_in_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_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;

}