/* Long (arbitrary precision) integer object implementation */

/* XXX The functional organization of this file is terrible */

#include "Python.h"

#include "longintrepr.h"

#include <ctype.h>

#ifndef NSMALLPOSINTS

#define NSMALLPOSINTS 257

#endif

#ifndef NSMALLNEGINTS

#define NSMALLNEGINTS 5

#endif

#define MEDIUM_VALUE(x) (Py_SIZE(x) < 0 ? -(x)->ob_digit[0] : \

(Py_SIZE(x) == 0 ? 0 : (x)->ob_digit[0]))

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

#if NSMALLNEGINTS + NSMALLPOSINTS > 0

/* Small integers are preallocated in this array so that they

can be shared.

The integers that are preallocated are those in the range

-NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).

*/

static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];

#ifdef COUNT_ALLOCS

int quick_int_allocs, quick_neg_int_allocs;

#endif

static PyObject *

get_small_int(int ival)

{

PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS);

Py_INCREF(v);

#ifdef COUNT_ALLOCS

if (ival >= 0)

quick_int_allocs++;

else

quick_neg_int_allocs++;

#endif

return v;

}

#define CHECK_SMALL_INT(ival) \

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

return get_small_int((int)ival); \

} while(0)

static PyLongObject *

maybe_small_long(PyLongObject *v)

{

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

int ival = MEDIUM_VALUE(v);

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

Py_DECREF(v);

return (PyLongObject *)get_small_int(ival);

}

}

return v;

}

#else

#define CHECK_SMALL_INT(ival)

#define maybe_small_long(val) (val)

#endif

/* If a freshly-allocated long is already shared, it must

be a small integer, so negating it must go to PyLong_FromLong */

#define NEGATE(x) \

do if (Py_REFCNT(x) == 1) Py_SIZE(x) = -Py_SIZE(x); \

else { PyObject* tmp=PyLong_FromLong(-MEDIUM_VALUE(x)); \

Py_DECREF(x); (x) = (PyLongObject*)tmp; } \

while(0)

/* For long multiplication, use the O(N**2) school algorithm unless

* both operands contain more than KARATSUBA_CUTOFF digits (this

* being an internal Python long 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 FIVEARY_CUTOFF digits.

* In that case, do 5 bits at a time. The potential drawback is that

* a table of 2**5 intermediate results is computed.

*/

#define FIVEARY_CUTOFF 8

#undef MIN

#undef MAX

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

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

/* Forward */

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 \

}

/* Normalize (remove leading zeros from) a long 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(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;

}

/* Allocate a new long int object with size digits.

Return NULL and set exception if we run out of memory. */

PyLongObject *

_PyLong_New(Py_ssize_t size)

{

PyLongObject *result;

/* Can't use sizeof(PyLongObject) here, since the

compiler takes padding at the end into account.

As the consequence, this would waste 2 bytes on

a 32-bit system, and 6 bytes on a 64-bit system.

This computation would be incorrect on systems

which have padding before the digits; with 16-bit

digits this should not happen. */

result = PyObject_MALLOC(sizeof(PyVarObject) +

size*sizeof(digit));

if (!result) {

PyErr_NoMemory();

return NULL;

}

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

PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect overflow */

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

int ival = src->ob_digit[0];

if (Py_SIZE(src) < 0)

ival = -ival;

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;

}

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

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 = 1;

CHECK_SMALL_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-(unsigned long)ival;

sign = -1;

}

else {

abs_ival = (unsigned long)ival;

}

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

}

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

}

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

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 = (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;

}

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

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;

}

/* 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 postive 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 a long int object.

Returns -1 and sets an error condition if overflow occurs. */

long

PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)

{

/* This version by Tim Peters */

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

PyNumberMethods *nb;

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

nb->nb_int == NULL) {

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

return -1;

}

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

if (vv == NULL)

return -1;

do_decref = 1;

if (!PyLong_Check(vv)) {

Py_DECREF(vv);

PyErr_SetString(PyExc_TypeError,

"nb_int should return int object");

return -1;

}

}

res = -1;

v = (PyLongObject *)vv;

i = Py_SIZE(v);

switch (i) {

case -1:

res = -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 = Py_SIZE(v) > 0 ? 1 : -1;

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

/* res is already set to -1 */

}

}

exit:

if (do_decref) {

Py_DECREF(vv);

}

return res;

}

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 Py_ssize_t from a long int object.

Returns -1 and sets an error condition if overflow occurs. */

Py_ssize_t

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

switch (i) {

case -1: return -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

* 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 a long int object.

Returns -1 and sets an error condition if overflow occurs. */

unsigned long

PyLong_AsUnsignedLong(PyObject *vv)

{

register PyLongObject *v;

unsigned long x, prev;

Py_ssize_t i;

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

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

}

/* Get a C unsigned long int from a long int object.

Returns -1 and sets an error condition if overflow occurs. */

size_t

PyLong_AsSize_t(PyObject *vv)

{

register PyLongObject *v;

size_t x, prev;

Py_ssize_t i;

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

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 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 (unsigned long) -1;

}

}

return x;

}

/* Get a C unsigned long int from a long int object, ignoring the high bits.

Returns -1 and sets an error condition if an error occurs. */

static unsigned long

_PyLong_AsUnsignedLongMask(PyObject *vv)

{

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

}

unsigned long

PyLong_AsUnsignedLongMask(register PyObject *op)

{

PyNumberMethods *nb;

PyLongObject *lo;

unsigned long val;

if (op && PyLong_Check(op))

return _PyLong_AsUnsignedLongMask(op);

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

nb->nb_int == NULL) {

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

return (unsigned long)-1;

}

lo = (PyLongObject*) (*nb->nb_int) (op);

if (lo == NULL)

return (unsigned long)-1;

if (PyLong_Check(lo)) {

val = _PyLong_AsUnsignedLongMask((PyObject *)lo);

Py_DECREF(lo);

if (PyErr_Occurred())

return (unsigned long)-1;

return val;

}

else

{

Py_DECREF(lo);

PyErr_SetString(PyExc_TypeError,

"nb_int should return int object");

return (unsigned long)-1;

}

}

int

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

}

size_t

_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, "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 */

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

significant byte. Leading 0 bytes are insignficant 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 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

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

8*numsignificantbytes bits, and each Python long digit has PyLong_SHIFT

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

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

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

}

int

_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 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.

It's crucial that every Python digit except for the MSD contribute

exactly PyLong_SHIFT bits to the total, so first assert that the long is

normalized. */

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

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

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

(appropriately pretending that the long had an

infinite supply of 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

just above didn't get to ensure there's a sign bit, and the

loop below wouldn't add one either. Make sure a sign bit

exists. */

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;

}

double

_PyLong_AsScaledDouble(PyObject *vv, int *exponent)

{

/* NBITS_WANTED should be > the number of bits in a double's precision,

but small enough so that 2**NBITS_WANTED is within the normal double

range. nbitsneeded is set to 1 less than that because the most-significant

Python digit contains at least 1 significant bit, but we don't want to

bother counting them (catering to the worst case cheaply).

57 is one more than VAX-D double precision; I (Tim) don't know of a double

format with more precision than that; it's 1 larger so that we add in at

least one round bit to stand in for the ignored least-significant bits.

*/

#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

zeroes, the true value is x * 2**(i*PyLong_SHIFT). */

*exponent = i;

assert(x > 0.0);

return x * sign;

#undef NBITS_WANTED

}

/* Get a C double from a long int object. */

double

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

set correctly after a successful _PyLong_AsScaledDouble() call */

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,

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

return -1.0;

}

/* Create a new long (or int) object from a C pointer */

PyObject *

PyLong_FromVoidPtr(void *p)

{

#ifndef HAVE_LONG_LONG

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

#endif

#if SIZEOF_LONG_LONG < SIZEOF_VOID_P

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

#endif

/* special-case null pointer */

if (!p)