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

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

#include "Python.h"

#include "longintrepr.h"

#include <ctype.h>

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

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

/* Forward */

static PyLongObject *long_normalize(PyLongObject *);

static PyLongObject *mul1(PyLongObject *, wdigit);

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

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

static PyObject *long_format(PyObject *aa, int base, int addL);

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

{

int j = ABS(v->ob_size);

register int i = j;

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

--i;

if (i != j)

v->ob_size = (v->ob_size < 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(int size)

{

return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);

}

PyObject *

_PyLong_Copy(PyLongObject *src)

{

PyLongObject *result;

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

}

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

PyObject *

PyLong_FromLong(long ival)

{

PyLongObject *v;

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

int ndigits = 0;

int negative = 0;

if (ival < 0) {

ival = -ival;

negative = 1;

}

/* Count the number of Python digits.

We used to pick 5 ("big enough for anything"), but that's a

waste of time and space given that 5*15 = 75 bits are rarely

needed. */

t = (unsigned long)ival;

while (t) {

++ndigits;

t >>= SHIFT;

}

v = _PyLong_New(ndigits);

if (v != NULL) {

digit *p = v->ob_digit;

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

t = (unsigned long)ival;

while (t) {

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

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

/* Count the number of Python digits. */

t = (unsigned long)ival;

while (t) {

++ndigits;

t >>= SHIFT;

}

v = _PyLong_New(ndigits);

if (v != NULL) {

digit *p = v->ob_digit;

v->ob_size = ndigits;

while (ival) {

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

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

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) / SHIFT + 1; /* Number of 'digits' in result */

v = _PyLong_New(ndig);

if (v == NULL)

return NULL;

frac = ldexp(frac, (expo-1) % SHIFT + 1);

for (i = ndig; --i >= 0; ) {

long bits = (long)frac;

v->ob_digit[i] = (digit) bits;

frac = frac - (double)bits;

frac = ldexp(frac, SHIFT);

}

if (neg)

v->ob_size = -(v->ob_size);

return (PyObject *)v;

}

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

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

long

PyLong_AsLong(PyObject *vv)

{

/* This version by Tim Peters */

register PyLongObject *v;

unsigned long x, prev;

int i, 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 << SHIFT) + v->ob_digit[i];

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

goto overflow;

}

/* Haven't lost any bits, but if the sign bit is set we're in

* trouble *unless* this is the min negative number. So,

* trouble iff sign bit set && (positive || some bit set other

* than the sign bit).

*/

if ((long)x < 0 && (sign > 0 || (x << 1) != 0))

goto overflow;

return (long)x * sign;

overflow:

PyErr_SetString(PyExc_OverflowError,

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

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;

int i;

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

PyErr_BadInternalCall();

return (unsigned long) -1;

}

v = (PyLongObject *)vv;

i = v->ob_size;

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 << SHIFT) + v->ob_digit[i];

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

PyErr_SetString(PyExc_OverflowError,

"long int too large to convert");

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

unsigned long

PyLong_AsUnsignedLongMask(PyObject *vv)

{

register PyLongObject *v;

unsigned long x;

int i, sign;

if (vv == NULL || !PyLong_Check(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 << SHIFT) + v->ob_digit[i];

}

return x * sign;

}

int

_PyLong_Sign(PyObject *vv)

{

PyLongObject *v = (PyLongObject *)vv;

assert(v != NULL);

assert(PyLong_Check(v));

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

}

size_t

_PyLong_NumBits(PyObject *vv)

{

PyLongObject *v = (PyLongObject *)vv;

size_t result = 0;

int ndigits;

assert(v != NULL);

assert(PyLong_Check(v));

ndigits = ABS(v->ob_size);

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

if (ndigits > 0) {

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

result = (ndigits - 1) * SHIFT;

if (result / 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

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 SHIFT

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

ndigits = (numsignificantbytes * 8 + SHIFT - 1) / 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 |= thisbyte << accumbits;

accumbits += 8;

if (accumbits >= SHIFT) {

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

assert(idigit < (int)ndigits);

v->ob_digit[idigit] = (digit)(accum & MASK);

++idigit;

accum >>= SHIFT;

accumbits -= SHIFT;

assert(accumbits < SHIFT);

}

}

assert(accumbits < SHIFT);

if (accumbits) {

assert(idigit < (int)ndigits);

v->ob_digit[idigit] = (digit)accum;

++idigit;

}

}

v->ob_size = 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)

{

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

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

twodigits 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 (v->ob_size < 0) {

ndigits = -(v->ob_size);

if (!is_signed) {

PyErr_SetString(PyExc_TypeError,

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

return -1;

}

do_twos_comp = 1;

}

else {

ndigits = v->ob_size;

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

twodigits thisdigit = v->ob_digit[i];

if (do_twos_comp) {

thisdigit = (thisdigit ^ MASK) + carry;

carry = thisdigit >> SHIFT;

thisdigit &= 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 |= thisdigit << accumbits;

accumbits += SHIFT;

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

* First shift conceptual sign bit to real sign bit.

*/

stwodigits s = (stwodigits)(thisdigit <<

(8*sizeof(stwodigits) - SHIFT));

unsigned int nsignbits = 0;

while ((s < 0) == do_twos_comp && nsignbits < SHIFT) {

++nsignbits;

s <<= 1;

}

accumbits -= nsignbits;

}

/* 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, "long 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 << SHIFT);

int i, sign;

int nbitsneeded;

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

PyErr_BadInternalCall();

return -1;

}

v = (PyLongObject *)vv;

i = v->ob_size;

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

}

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

zeroes, the true value is x * 2**(i*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;

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;

if (e > INT_MAX / SHIFT)

goto overflow;

errno = 0;

x = ldexp(x, e * 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;

}

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

PyObject *

PyLong_FromVoidPtr(void *p)

{

#if SIZEOF_VOID_P <= SIZEOF_LONG

return PyInt_FromLong((long)p);

#else

#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

/* optimize null pointers */

if (p == NULL)

return PyInt_FromLong(0);

return PyLong_FromLongLong((PY_LONG_LONG)p);

#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */

}

/* Get a C pointer from a long object (or an int object in some cases) */

void *

PyLong_AsVoidPtr(PyObject *vv)

{

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

then the PyLong_AsLong*() functions will raise the exception:

PyExc_SystemError, "bad argument to internal function"

*/

#if SIZEOF_VOID_P <= SIZEOF_LONG

long x;

if (PyInt_Check(vv))

x = PyInt_AS_LONG(vv);

else

x = PyLong_AsLong(vv);

#else

#ifndef HAVE_LONG_LONG

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

#endif

#if SIZEOF_LONG_LONG < SIZEOF_VOID_P

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

#endif

PY_LONG_LONG x;

if (PyInt_Check(vv))

x = PyInt_AS_LONG(vv);

else

x = PyLong_AsLongLong(vv);

#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */

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

return NULL;

return (void *)x;

}

#ifdef HAVE_LONG_LONG

/* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later

* rewritten to use the newer PyLong_{As,From}ByteArray API.

*/

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

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

PyObject *

PyLong_FromLongLong(PY_LONG_LONG ival)

{

PY_LONG_LONG bytes = ival;

int one = 1;

return _PyLong_FromByteArray(

(unsigned char *)&bytes,

SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);

}

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

PyObject *

PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)

{

unsigned PY_LONG_LONG bytes = ival;

int one = 1;

return _PyLong_FromByteArray(

(unsigned char *)&bytes,

SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);

}

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

Return -1 and set an error if overflow occurs. */

PY_LONG_LONG

PyLong_AsLongLong(PyObject *vv)

{

PY_LONG_LONG bytes;

int one = 1;

int res;

if (vv == NULL) {

PyErr_BadInternalCall();

return -1;

}

if (!PyLong_Check(vv)) {

if (PyInt_Check(vv))

return (PY_LONG_LONG)PyInt_AsLong(vv);

PyErr_BadInternalCall();

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;

}

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

Return -1 and set an error if overflow occurs. */

unsigned PY_LONG_LONG

PyLong_AsUnsignedLongLong(PyObject *vv)

{

unsigned PY_LONG_LONG bytes;

int one = 1;

int res;

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

PyErr_BadInternalCall();

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

if (res < 0)

return (unsigned PY_LONG_LONG)res;

else

return bytes;

}

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

unsigned PY_LONG_LONG

PyLong_AsUnsignedLongLongMask(PyObject *vv)

{

register PyLongObject *v;

unsigned PY_LONG_LONG x;

int i, sign;

if (vv == NULL || !PyLong_Check(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 << SHIFT) + v->ob_digit[i];

}

return x * sign;

}

#undef IS_LITTLE_ENDIAN

#endif /* HAVE_LONG_LONG */

static int

convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {

if (PyLong_Check(v)) {

*a = (PyLongObject *) v;

Py_INCREF(v);

}

else if (PyInt_Check(v)) {

*a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));

}

else {

return 0;

}

if (PyLong_Check(w)) {

*b = (PyLongObject *) w;

Py_INCREF(w);

}

else if (PyInt_Check(w)) {

*b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));

}

else {

Py_DECREF(*a);

return 0;

}

return 1;

}

#define CONVERT_BINOP(v, w, a, b) \

if (!convert_binop(v, w, a, b)) { \

Py_INCREF(Py_NotImplemented); \

return Py_NotImplemented; \

}

/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]

* is modified in place, by adding y to it. Carries are propagated as far as

* x[m-1], and the remaining carry (0 or 1) is returned.

*/

static digit

v_iadd(digit *x, int m, digit *y, int n)

{

int i;

digit carry = 0;

assert(m >= n);

for (i = 0; i < n; ++i) {

carry += x[i] + y[i];

x[i] = carry & MASK;

carry >>= SHIFT;

assert((carry & 1) == carry);

}

for (; carry && i < m; ++i) {

carry += x[i];

x[i] = carry & MASK;

carry >>= SHIFT;

assert((carry & 1) == carry);

}

return carry;

}

/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]

* is modified in place, by subtracting y from it. Borrows are propagated as

* far as x[m-1], and the remaining borrow (0 or 1) is returned.

*/

static digit

v_isub(digit *x, int m, digit *y, int n)

{

int i;

digit borrow = 0;

assert(m >= n);

for (i = 0; i < n; ++i) {

borrow = x[i] - y[i] - borrow;

x[i] = borrow & MASK;

borrow >>= SHIFT;

borrow &= 1; /* keep only 1 sign bit */

}

for (; borrow && i < m; ++i) {

borrow = x[i] - borrow;

x[i] = borrow & MASK;

borrow >>= SHIFT;

borrow &= 1;

}

return borrow;

}

/* Multiply by a single digit, ignoring the sign. */

static PyLongObject *

mul1(PyLongObject *a, wdigit n)

{

return muladd1(a, n, (digit)0);

}

/* Multiply by a single digit and add a single digit, ignoring the sign. */

static PyLongObject *

muladd1(PyLongObject *a, wdigit n, wdigit extra)

{

int size_a = ABS(a->ob_size);

PyLongObject *z = _PyLong_New(size_a+1);

twodigits carry = extra;

int i;

if (z == NULL)

return NULL;

for (i = 0; i < size_a; ++i) {

carry += (twodigits)a->ob_digit[i] * n;

z->ob_digit[i] = (digit) (carry & MASK);

carry >>= SHIFT;

}

z->ob_digit[i] = (digit) carry;

return long_normalize(z);

}

/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient

in pout, and returning the remainder. pin and pout point at the LSD.

It's OK for pin == pout on entry, which saves oodles of mallocs/frees in

long_format, but that should be done with great care since longs are

immutable. */

static digit

inplace_divrem1(digit *pout, digit *pin, int size, digit n)

{

twodigits rem = 0;

assert(n > 0 && n <= MASK);

pin += size;

pout += size;

while (--size >= 0) {

digit hi;

rem = (rem << SHIFT) + *--pin;

*--pout = hi = (digit)(rem / n);

rem -= hi * n;

}

return (digit)rem;

}

/* Divide a long integer by a digit, returning both the quotient

(as function result) and the remainder (through *prem).

The sign of a is ignored; n should not be zero. */

static PyLongObject *

divrem1(PyLongObject *a, digit n, digit *prem)

{

const int size = ABS(a->ob_size);

PyLongObject *z;

assert(n > 0 && n <= MASK);

z = _PyLong_New(size);

if (z == NULL)

return NULL;

*prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);

return long_normalize(z);

}

/* Convert a long int object to a string, using a given conversion base.

Return a string object.

If base is 8 or 16, add the proper prefix '0' or '0x'. */

static PyObject *