#include "Python.h"

#include "longintrepr.h"

#include <ctype.h>

#define KARATSUBA_CUTOFF 70

#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)

#define FIVEARY_CUTOFF 8

#define ABS(x) ((x) < 0 ? -(x) : (x))

#undef MIN

#undef MAX

#define MAX(x, y) ((x) < (y) ? (y) : (x))

#define MIN(x, y) ((x) > (y) ? (y) : (x))

static PyLongObject *long_normalize(PyLongObject *);

static PyLongObject *mul1(PyLongObject *, wdigit);

static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);

static PyLongObject *divrem1(PyLongObject *, digit, digit *);

#define SIGCHECK(PyTryBlock) \

if (--_Py_Ticker < 0) { \

_Py_Ticker = _Py_CheckInterval; \

if (PyErr_CheckSignals()) PyTryBlock \

}

static PyLongObject *

long_normalize(register PyLongObject *v)

{

Py_ssize_t j = 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_New(Py_ssize_t size)

{

if (size > PY_SSIZE_T_MAX) {

PyErr_NoMemory();

return NULL;

}

/* coverity[ampersand_in_size] */

/* XXX(nnorwitz): This can overflow --

return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);

}

PyObject *

_PyLong_Copy(PyLongObject *src)

{

PyLongObject *result;

Py_ssize_t i;

assert(src != NULL);

i = src->ob_size;

if (i < 0)

i = -(i);

result = _PyLong_New(i);

if (result != NULL) {

result->ob_size = src->ob_size;

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 negative = 0;

if (ival < 0) {

/* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then

abs_ival = (unsigned long)(-1-ival) + 1;

negative = 1;

}

else {

abs_ival = (unsigned long)ival;

}

/* Count the number of Python digits.

t = abs_ival;

while (t) {

++ndigits;

t >>= PyLong_SHIFT;

}

v = _PyLong_New(ndigits);

if (v != NULL) {

digit *p = v->ob_digit;

v->ob_size = negative ? -ndigits : ndigits;

t = abs_ival;

while (t) {

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

t >>= PyLong_SHIFT;

}

}

return (PyObject *)v;

}

PyObject *

PyLong_FromUnsignedLong(unsigned long ival)

{

PyLongObject *v;

unsigned long t;

int ndigits = 0;

/* Count the number of Python digits. */

t = (unsigned long)ival;

while (t) {

++ndigits;

t >>= PyLong_SHIFT;

}

v = _PyLong_New(ndigits);

if (v != NULL) {

digit *p = v->ob_digit;

Py_SIZE(v) = ndigits;

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

long bits = (long)frac;

v->ob_digit[i] = (digit) 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_AsLong(PyObject *vv)

{

/* This version by Tim Peters */

register PyLongObject *v;

unsigned long x, prev;

Py_ssize_t i;

int sign;

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

if (vv != NULL && PyInt_Check(vv))

return PyInt_AsLong(vv);

PyErr_BadInternalCall();

return -1;

}

v = (PyLongObject *)vv;

i = v->ob_size;

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 long requires extra care

if (x <= (unsigned long)LONG_MAX) {

return (long)x * sign;

}

else if (sign < 0 && x == PY_ABS_LONG_MIN) {

return LONG_MIN;

}

/* else overflow */

overflow:

PyErr_SetString(PyExc_OverflowError,

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

return -1;

}

PyLong_AsSsize_t(PyObject *vv) {

register PyLongObject *v;

size_t x, prev;

Py_ssize_t i;

int sign;

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

PyErr_BadInternalCall();

return -1;

}

v = (PyLongObject *)vv;

i = v->ob_size;

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,

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

return -1;

}

PyLong_AsUnsignedLong(PyObject *vv)

{

register PyLongObject *v;

unsigned long x, prev;

Py_ssize_t i;

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

if (vv != NULL && PyInt_Check(vv)) {

long val = PyInt_AsLong(vv);

if (val < 0) {

PyErr_SetString(PyExc_OverflowError,

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

return (unsigned long) -1;

}

return val;

}

PyErr_BadInternalCall();

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

return (unsigned long) -1;

}

while (--i >= 0) {

prev = x;

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

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

PyErr_SetString(PyExc_OverflowError,

"long int too large to convert");

return (unsigned long) -1;

}

}

return x;

}

PyLong_AsUnsignedLongMask(PyObject *vv)

{

register PyLongObject *v;

unsigned long x;

Py_ssize_t i;

int sign;

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

if (vv != NULL && PyInt_Check(vv))

return PyInt_AsUnsignedLongMask(vv);

PyErr_BadInternalCall();

return (unsigned long) -1;

}

v = (PyLongObject *)vv;

i = v->ob_size;

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

}

_PyLong_NumBits(PyObject *vv)

{

PyLongObject *v = (PyLongObject *)vv;

size_t result = 0;

Py_ssize_t ndigits;

assert(v != NULL);

assert(PyLong_Check(v));

ndigits = ABS(Py_SIZE(v));

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

if (ndigits > 0) {

digit msd = v->ob_digit[ndigits - 1];

result = (ndigits - 1) * PyLong_SHIFT;

if (result / PyLong_SHIFT != (size_t)(ndigits - 1))

goto Overflow;

do {

++result;

if (result == 0)

goto Overflow;

msd >>= 1;

} while (msd);

}

return result;

Overflow:

PyErr_SetString(PyExc_OverflowError, "long 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 */

size_t ndigits; /* number of Python long digits */

PyLongObject* v; /* result */

int 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 insignficant = is_signed ? 0xff : 0x00;

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

if (*p != insignficant)

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 long digits do we need? We have

ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;

if (ndigits > (size_t)INT_MAX)

return PyErr_NoMemory();

v = _PyLong_New((int)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 |= (twodigits)thisbyte << accumbits;

accumbits += 8;

if (accumbits >= PyLong_SHIFT) {

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

assert(idigit < (int)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 < (int)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_TypeError,

"can't convert negative long 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, "long too big to convert");

return -1;

}

_PyLong_AsScaledDouble(PyObject *vv, int *exponent)

{

#define NBITS_WANTED 57

PyLongObject *v;

double x;

const double multiplier = (double)(1L << PyLong_SHIFT);

Py_ssize_t i;

int sign;

int nbitsneeded;

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

PyErr_BadInternalCall();

return -1;

}

v = (PyLongObject *)vv;

i = Py_SIZE(v);

sign = 1;

if (i < 0) {

sign = -1;

i = -(i);

}

else if (i == 0) {

*exponent = 0;

return 0.0;

}

--i;

x = (double)v->ob_digit[i];

nbitsneeded = NBITS_WANTED - 1;

/* Invariant: i Python digits remain unaccounted for. */

while (i > 0 && nbitsneeded > 0) {

--i;

x = x * multiplier + (double)v->ob_digit[i];

nbitsneeded -= PyLong_SHIFT;

}

/* There are i digits we didn't shift in. Pretending they're all

*exponent = i;

assert(x > 0.0);

return x * sign;

#undef NBITS_WANTED

}

PyLong_AsDouble(PyObject *vv)

{

int e = -1;

double x;

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

PyErr_BadInternalCall();

return -1;

}

x = _PyLong_AsScaledDouble(vv, &e);

if (x == -1.0 && PyErr_Occurred())

return -1.0;

/* 'e' initialized to -1 to silence gcc-4.0.x, but it should be

assert(e >= 0);

if (e > INT_MAX / PyLong_SHIFT)

goto overflow;

errno = 0;

x = ldexp(x, e * PyLong_SHIFT);

if (Py_OVERFLOWED(x))

goto overflow;

return x;

overflow:

PyErr_SetString(PyExc_OverflowError,

"long int too large to convert to float");

return -1.0;

}

PyObject *

PyLong_FromVoidPtr(void *p)

{

#if SIZEOF_VOID_P <= SIZEOF_LONG

if ((long)p < 0)

return PyLong_FromUnsignedLong((unsigned long)p);

return PyInt_FromLong((long)p);

#ifndef HAVE_LONG_LONG

# error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"

#if SIZEOF_LONG_LONG < SIZEOF_VOID_P

# error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"

/* optimize null pointers */

if (p == NULL)

return PyInt_FromLong(0);

return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)p);

#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */

}

void *

PyLong_AsVoidPtr(PyObject *vv)

{

/* This function will allow int or long objects. If vv is neither,

#if SIZEOF_VOID_P <= SIZEOF_LONG

long x;

if (PyInt_Check(vv))

x = PyInt_AS_LONG(vv);

else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)

x = PyLong_AsLong(vv);

else

x = PyLong_AsUnsignedLong(vv);

#ifndef HAVE_LONG_LONG

# error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"

#if SIZEOF_LONG_LONG < SIZEOF_VOID_P

# error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"

PY_LONG_LONG x;

if (PyInt_Check(vv))

x = PyInt_AS_LONG(vv);

else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)

x = PyLong_AsLongLong(vv);

else

x = PyLong_AsUnsignedLongLong(vv);

#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */

if (x == -1 && PyErr_Occurred())

return NULL;

return (void *)x;

}

#ifdef HAVE_LONG_LONG

#define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one

PyObject *

PyLong_FromLongLong(PY_LONG_LONG ival)

{

PyLongObject *v;

unsigned PY_LONG_LONG abs_ival;

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

int ndigits = 0;

int negative = 0;

if (ival < 0) {

/* avoid signed overflow on negation; see comments

abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;

negative = 1;

}

else {

abs_ival = (unsigned PY_LONG_LONG)ival;

}

/* Count the number of Python 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) = negative ? -ndigits : ndigits;

t = abs_ival;

while (t) {

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

t >>= PyLong_SHIFT;

}

}

return (PyObject *)v;

}

PyObject *

PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)

{

PyLongObject *v;

unsigned PY_LONG_LONG t;

int ndigits = 0;

/* Count the number of Python digits. */

t = (unsigned PY_LONG_LONG)ival;

while (t) {

++ndigits;

t >>= PyLong_SHIFT;

}

v = _PyLong_New(ndigits);

if (v != NULL) {

digit *p = v->ob_digit;

Py_SIZE(v) = ndigits;

while (ival) {

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

ival >>= PyLong_SHIFT;

}

}

return (PyObject *)v;

}

PyObject *

PyLong_FromSsize_t(Py_ssize_t ival)

{

Py_ssize_t bytes = ival;

int one = 1;

return _PyLong_FromByteArray(

(unsigned char *)&bytes,

SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 1);

}

PyObject *

PyLong_FromSize_t(size_t ival)

{

size_t bytes = ival;

int one = 1;

return _PyLong_FromByteArray(

(unsigned char *)&bytes,

SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 0);

}

PyLong_AsLongLong(PyObject *vv)

{

PY_LONG_LONG bytes;

int one = 1;

int res;

if (vv == NULL) {

PyErr_BadInternalCall();

return -1;

}

if (!PyLong_Check(vv)) {

PyNumberMethods *nb;

PyObject *io;

if (PyInt_Check(vv))

return (PY_LONG_LONG)PyInt_AsLong(vv);

if ((nb = vv->ob_type->tp_as_number) == NULL ||

nb->nb_int == NULL) {

PyErr_SetString(PyExc_TypeError, "an integer is required");

return -1;

}

io = (*nb->nb_int) (vv);

if (io == NULL)

return -1;

if (PyInt_Check(io)) {

bytes = PyInt_AsLong(io);

Py_DECREF(io);

return bytes;

}

if (PyLong_Check(io)) {

bytes = PyLong_AsLongLong(io);

Py_DECREF(io);

return bytes;

}

Py_DECREF(io);

PyErr_SetString(PyExc_TypeError, "integer conversion failed");

return -1;

}

res = _PyLong_AsByteArray(

(PyLongObject *)vv, (unsigned char *)&bytes,

SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);

/* Plan 9 can't handle PY_LONG_LONG in ? : expressions */

if (res < 0)

return (PY_LONG_LONG)-1;

else

return bytes;

}

PyLong_AsUnsignedLongLong(PyObject *vv)

{

unsigned PY_LONG_LONG bytes;

int one = 1;

int res;

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

PyErr_BadInternalCall();

return (unsigned PY_LONG_LONG)-1;

}

res = _PyLong_AsByteArray(

(PyLongObject *)vv, (unsigned char *)&bytes,

SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);

/* Plan 9 can't handle PY_LONG_LONG in ? : expressions */