/* Long (arbitrary precision) integer object implementation */
/* XXX The functional organization of this file is terrible */
#include "Python.h"
#include "longintrepr.h"
#include
/* 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 PyLong_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
#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 *);
#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)
{
if (size > PY_SSIZE_T_MAX) {
PyErr_NoMemory();
return NULL;
}
/* coverity[ampersand_in_size] */
/* XXX(nnorwitz): This can overflow --
PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect 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;
}
/* 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 negative = 0;
if (ival < 0) {
/* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then
ANSI C says that the result of -ival is undefined when ival
== LONG_MIN. Hence the following workaround. */
abs_ival = (unsigned long)(-1-ival) + 1;
negative = 1;
}
else {
abs_ival = (unsigned long)ival;
}
/* 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 = 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;
}
/* 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 >>= 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 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_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 ob_digit[i];
if ((x >> PyLong_SHIFT) != prev)
goto overflow;
}
/* Haven't lost any bits, but casting to long requires extra care
* (see comment above).
*/
if (x ob_size;
sign = 1;
x = 0;
if (i < 0) {
sign = -1;
i = -(i);
}
while (--i >= 0) {
prev = x;
x = (x 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 = 0) {
prev = x;
x = (x ob_digit[i];
if ((x >> PyLong_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;
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 ob_digit[i];
}
return x * sign;
}
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, "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 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 = 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 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.
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 = 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 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,
"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 >= 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;
}
/* Create a new long int object from a C unsigned PY_LONG_LONG int. */
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;
}
/* Create a new long int object from a C Py_ssize_t. */
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);
}
/* Create a new long int object from a C size_t. */
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);
}
/* 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)) {
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;
}
/* 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 (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 */
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;
Py_ssize_t i;
int 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 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, Py_ssize_t m, digit *y, Py_ssize_t n)
{
Py_ssize_t i;
digit carry = 0;
assert(m >= n);
for (i = 0; i < n; ++i) {
carry += x[i] + y[i];
x[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
assert((carry & 1) == carry);
}
for (; carry && i < m; ++i) {
carry += x[i];
x[i] = carry & PyLong_MASK;
carry >>= PyLong_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, Py_ssize_t m, digit *y, Py_ssize_t n)
{
Py_ssize_t i;
digit borrow = 0;
assert(m >= n);
for (i = 0; i < n; ++i) {
borrow = x[i] - y[i] - borrow;
x[i] = borrow & PyLong_MASK;
borrow >>= PyLong_SHIFT;
borrow &= 1; /* keep only 1 sign bit */
}
for (; borrow && i < m; ++i) {
borrow = x[i] - borrow;
x[i] = borrow & PyLong_MASK;
borrow >>= PyLong_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)
{
Py_ssize_t size_a = ABS(Py_SIZE(a));
PyLongObject *z = _PyLong_New(size_a+1);
twodigits carry = extra;
Py_ssize_t 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 & PyLong_MASK);
carry >>= PyLong_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
_PyLong_Format, but that should be done with great care since longs are
immutable. */
static digit
inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
{
twodigits rem = 0;
assert(n > 0 && n = 0) {
digit hi;
rem = (rem 0 && n ob_digit, a->ob_digit, size, n);
return long_normalize(z);
}
/* Convert the long to a string object with given base,
appending a base prefix of 0[box] if base is 2, 8 or 16.
Add a trailing "L" if addL is non-zero.
If newstyle is zero, then use the pre-2.6 behavior of octal having
a leading "0", instead of the prefix "0o" */
PyAPI_FUNC(PyObject *)
_PyLong_Format(PyObject *aa, int base, int addL, int newstyle)
{
register PyLongObject *a = (PyLongObject *)aa;
PyStringObject *str;
Py_ssize_t i, j, sz;
Py_ssize_t size_a;
char *p;
int bits;
char sign = '\0';
if (a == NULL || !PyLong_Check(a)) {
PyErr_BadInternalCall();
return NULL;
}
assert(base >= 2 && base 1) {
++bits;
i >>= 1;
}
i = 5 + (addL ? 1 : 0);
j = size_a*PyLong_SHIFT + bits-1;
sz = i + j / bits;
if (j / PyLong_SHIFT < size_a || sz < i) {
PyErr_SetString(PyExc_OverflowError,
"long is too large to format");
return NULL;
}
str = (PyStringObject *) PyString_FromStringAndSize((char *)0, sz);
if (str == NULL)
return NULL;
p = PyString_AS_STRING(str) + sz;
*p = '\0';
if (addL)
*--p = 'L';
if (a->ob_size < 0)
sign = '-';
if (a->ob_size == 0) {
*--p = '0';
}
else if ((base & (base - 1)) == 0) {
/* JRH: special case for power-of-2 bases */
twodigits accum = 0;
int accumbits = 0; /* # of bits in accum */
int basebits = 1; /* # of bits in base-1 */
i = base;
while ((i >>= 1) > 1)
++basebits;
for (i = 0; i < size_a; ++i) {
accum |= (twodigits)a->ob_digit[i] = basebits);
do {
char cdigit = (char)(accum & (base - 1));
cdigit += (cdigit < 10) ? '0' : 'a'-10;
assert(p > PyString_AS_STRING(str));
*--p = cdigit;
accumbits -= basebits;
accum >>= basebits;
} while (i < size_a-1 ? accumbits >= basebits :
accum > 0);
}
}
else {
/* Not 0, and base not a power of 2. Divide repeatedly by
base, but for speed use the highest power of base that
fits in a digit. */
Py_ssize_t size = size_a;
digit *pin = a->ob_digit;
PyLongObject *scratch;
/* powbasw > PyLong_SHIFT) /* doesn't fit in a digit */
break;
powbase = (digit)newpow;
++power;
}
/* Get a scratch area for repeated division. */
scratch = _PyLong_New(size);
if (scratch == NULL) {
Py_DECREF(str);
return NULL;
}
/* Repeatedly divide by powbase. */
do {
int ntostore = power;
digit rem = inplace_divrem1(scratch->ob_digit,
pin, size, powbase);
pin = scratch->ob_digit; /* no need to use a again */
if (pin[size - 1] == 0)
--size;
SIGCHECK({
Py_DECREF(scratch);
Py_DECREF(str);
return NULL;
})
/* Break rem into digits. */
assert(ntostore > 0);
do {
digit nextrem = (digit)(rem / base);
char c = (char)(rem - nextrem * base);
assert(p > PyString_AS_STRING(str));
c += (c < 10) ? '0' : 'a'-10;
*--p = c;
rem = nextrem;
--ntostore;
/* Termination is a bit delicate: must not
store leading zeroes, so must get out if
remaining quotient and rem are both 0. */
} while (ntostore && (size || rem));
} while (size != 0);
Py_DECREF(scratch);
}
if (base == 2) {
*--p = 'b';
*--p = '0';
}
else if (base == 8) {
if (newstyle) {
*--p = 'o';
*--p = '0';
}
else
if (size_a != 0)
*--p = '0';
}
else if (base == 16) {
*--p = 'x';
*--p = '0';
}
else if (base != 10) {
*--p = '#';
*--p = '0' + base%10;
if (base > 10)
*--p = '0' + base/10;
}
if (sign)
*--p = sign;
if (p != PyString_AS_STRING(str)) {
char *q = PyString_AS_STRING(str);
assert(p > q);
do {
} while ((*q++ = *p++) != '\0');
q--;
_PyString_Resize((PyObject **)&str,
(Py_ssize_t) (q - PyString_AS_STRING(str)));
}
return (PyObject *)str;
}
/* Table of digit values for 8-bit string -> integer conversion.
* '0' maps to 0, ..., '9' maps to 9.
* 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
* All other indices map to 37.
* Note that when converting a base B string, a char c is a legitimate
* base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B.
*/
int _PyLong_DigitValue[256] = {
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,
37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
};
/* *str points to the first digit in a string of base `base` digits. base
* is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
* non-digit (which may be *str!). A normalized long is returned.
* The point to this routine is that it takes time linear in the number of
* string characters.
*/
static PyLongObject *
long_from_binary_base(char **str, int base)
{
char *p = *str;
char *start = p;
int bits_per_char;
Py_ssize_t n;
PyLongObject *z;
twodigits accum;
int bits_in_accum;
digit *pdigit;
assert(base >= 2 && base >= 1;
/* n = start) {
int k = _PyLong_DigitValue[Py_CHARMASK(*p)];
assert(k >= 0 && k < base);
accum |= (twodigits)k = PyLong_SHIFT) {
*pdigit++ = (digit)(accum & PyLong_MASK);
assert(pdigit - z->ob_digit >= PyLong_SHIFT;
bits_in_accum -= PyLong_SHIFT;
assert(bits_in_accum < PyLong_SHIFT);
}
}
if (bits_in_accum) {
assert(bits_in_accum ob_digit ob_digit < n)
*pdigit++ = 0;
return long_normalize(z);
}
PyObject *
PyLong_FromString(char *str, char **pend, int base)
{
int sign = 1;
char *start, *orig_str = str;
PyLongObject *z;
PyObject *strobj, *strrepr;
Py_ssize_t slen;
if ((base != 0 && base < 2) || base > 36) {
PyErr_SetString(PyExc_ValueError,
"long() arg 2 must be >= 2 and