/* Long (arbitrary precision) integer object implementation */
/* XXX The functional organization of this file is terrible */
#include "Python.h"
#include "pycore_bitutils.h" // _Py_popcount32()
#include "pycore_interp.h" // _PY_NSMALLPOSINTS
#include "pycore_pystate.h" // _Py_IsMainInterpreter()
#include "longintrepr.h"
#include
#include
#include
#include "clinic/longobject.c.h"
/*[clinic input]
class int "PyObject *" "&PyLong_Type"
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=ec0275e3422a36e3]*/
#define NSMALLPOSINTS _PY_NSMALLPOSINTS
#define NSMALLNEGINTS _PY_NSMALLNEGINTS
_Py_IDENTIFIER(little);
_Py_IDENTIFIER(big);
/* convert a PyLong of size 1, 0 or -1 to an sdigit */
#define MEDIUM_VALUE(x) (assert(-1 ob_digit[0]))
PyObject *_PyLong_Zero = NULL;
PyObject *_PyLong_One = NULL;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
#define IS_SMALL_INT(ival) (-NSMALLNEGINTS small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
return v;
}
static PyLongObject *
maybe_small_long(PyLongObject *v)
{
if (v && Py_ABS(Py_SIZE(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 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 ob_digit[0];
}
while (--i >= 0) {
prev = x;
x = (x 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 size_t from an int object. Returns (size_t)-1 and sets
an error condition if overflow occurs. */
size_t
PyLong_AsSize_t(PyObject *vv)
{
PyLongObject *v;
size_t x, prev;
Py_ssize_t i;
if (vv == NULL) {
PyErr_BadInternalCall();
return (size_t) -1;
}
if (!PyLong_Check(vv)) {
PyErr_SetString(PyExc_TypeError, "an integer is required");
return (size_t)-1;
}
v = (PyLongObject *)vv;
i = Py_SIZE(v);
x = 0;
if (i < 0) {
PyErr_SetString(PyExc_OverflowError,
"can't convert negative value to size_t");
return (size_t) -1;
}
switch (i) {
case 0: return 0;
case 1: return v->ob_digit[0];
}
while (--i >= 0) {
prev = x;
x = (x ob_digit[i];
if ((x >> PyLong_SHIFT) != prev) {
PyErr_SetString(PyExc_OverflowError,
"Python int too large to convert to C size_t");
return (size_t) -1;
}
}
return x;
}
/* Get a C unsigned long int from an int object, ignoring the high bits.
Returns -1 and sets an error condition if an error occurs. */
static unsigned long
_PyLong_AsUnsignedLongMask(PyObject *vv)
{
PyLongObject *v;
unsigned long x;
Py_ssize_t i;
int sign;
if (vv == NULL || !PyLong_Check(vv)) {
PyErr_BadInternalCall();
return (unsigned long) -1;
}
v = (PyLongObject *)vv;
i = Py_SIZE(v);
switch (i) {
case 0: return 0;
case 1: return v->ob_digit[0];
}
sign = 1;
x = 0;
if (i < 0) {
sign = -1;
i = -i;
}
while (--i >= 0) {
x = (x ob_digit[i];
}
return x * sign;
}
unsigned long
PyLong_AsUnsignedLongMask(PyObject *op)
{
PyLongObject *lo;
unsigned long val;
if (op == NULL) {
PyErr_BadInternalCall();
return (unsigned long)-1;
}
if (PyLong_Check(op)) {
return _PyLong_AsUnsignedLongMask(op);
}
lo = (PyLongObject *)_PyNumber_Index(op);
if (lo == NULL)
return (unsigned long)-1;
val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
Py_DECREF(lo);
return val;
}
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;
int msd_bits;
assert(v != NULL);
assert(PyLong_Check(v));
ndigits = Py_ABS(Py_SIZE(v));
assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
if (ndigits > 0) {
digit msd = v->ob_digit[ndigits - 1];
if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)
goto Overflow;
result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
msd_bits = _Py_bit_length(msd);
if (SIZE_MAX - msd_bits < result)
goto Overflow;
result += msd_bits;
}
return result;
Overflow:
PyErr_SetString(PyExc_OverflowError, "int has too many bits "
"to express in a platform size_t");
return (size_t)-1;
}
PyObject *
_PyLong_FromByteArray(const unsigned char* bytes, size_t n,
int little_endian, int is_signed)
{
const unsigned char* pstartbyte; /* LSB of bytes */
int incr; /* direction to move pstartbyte */
const unsigned char* pendbyte; /* MSB of bytes */
size_t numsignificantbytes; /* number of bytes that matter */
Py_ssize_t ndigits; /* number of Python int digits */
PyLongObject* v; /* result */
Py_ssize_t idigit = 0; /* next free index in v->ob_digit */
if (n == 0)
return PyLong_FromLong(0L);
if (little_endian) {
pstartbyte = bytes;
pendbyte = bytes + n - 1;
incr = 1;
}
else {
pstartbyte = bytes + n - 1;
pendbyte = bytes;
incr = -1;
}
if (is_signed)
is_signed = *pendbyte >= 0x80;
/* Compute numsignificantbytes. This consists of finding the most
significant byte. Leading 0 bytes are insignificant 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 insignificant = is_signed ? 0xff : 0x00;
for (i = 0; i < n; ++i, p += pincr) {
if (*p != insignificant)
break;
}
numsignificantbytes = n - i;
/* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
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 int digits do we need? We have
8*numsignificantbytes bits, and each Python int digit has
PyLong_SHIFT bits, so it's the ceiling of the quotient. */
/* catch overflow before it happens */
if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
PyErr_SetString(PyExc_OverflowError,
"byte array too long to convert to int");
return NULL;
}
ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
v = _PyLong_New(ndigits);
if (v == NULL)
return NULL;
/* Copy the bits over. The tricky parts are computing 2's-comp on
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 = PyLong_SHIFT) {
/* There's enough to fill a Python digit. */
assert(idigit < ndigits);
v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
++idigit;
accum >>= PyLong_SHIFT;
accumbits -= PyLong_SHIFT;
assert(accumbits < PyLong_SHIFT);
}
}
assert(accumbits < PyLong_SHIFT);
if (accumbits) {
assert(idigit < ndigits);
v->ob_digit[idigit] = (digit)accum;
++idigit;
}
}
Py_SET_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_OverflowError,
"can't convert negative int to unsigned");
return -1;
}
do_twos_comp = 1;
}
else {
ndigits = Py_SIZE(v);
do_twos_comp = 0;
}
if (little_endian) {
p = bytes;
pincr = 1;
}
else {
p = bytes + n - 1;
pincr = -1;
}
/* Copy over all the Python digits.
It's crucial that every Python digit except for the MSD contribute
exactly PyLong_SHIFT bits to the total, so first assert that the int 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, "int too big to convert");
return -1;
}
/* Create a new 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_SET_SIZE(v, negative ? -ndigits : ndigits);
t = abs_ival;
while (t) {
*p++ = (digit)(t & PyLong_MASK);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
/* Create a new int object from a C Py_ssize_t. */
PyObject *
PyLong_FromSsize_t(Py_ssize_t ival)
{
PyLongObject *v;
size_t abs_ival;
size_t t; /* unsigned so >> doesn't propagate sign bit */
int ndigits = 0;
int negative = 0;
if (IS_SMALL_INT(ival)) {
return get_small_int((sdigit)ival);
}
if (ival < 0) {
/* avoid signed overflow when ival = SIZE_T_MIN */
abs_ival = (size_t)(-1-ival)+1;
negative = 1;
}
else {
abs_ival = (size_t)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_SET_SIZE(v, negative ? -ndigits : ndigits);
t = abs_ival;
while (t) {
*p++ = (digit)(t & PyLong_MASK);
t >>= PyLong_SHIFT;
}
}
return (PyObject *)v;
}
/* Get a C long long int from an int object or any object that has an
__index__ method. Return -1 and set an error if overflow occurs. */
long long
PyLong_AsLongLong(PyObject *vv)
{
PyLongObject *v;
long long bytes;
int res;
int do_decref = 0; /* if PyNumber_Index was called */
if (vv == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (PyLong_Check(vv)) {
v = (PyLongObject *)vv;
}
else {
v = (PyLongObject *)_PyNumber_Index(vv);
if (v == NULL)
return -1;
do_decref = 1;
}
res = 0;
switch(Py_SIZE(v)) {
case -1:
bytes = -(sdigit)v->ob_digit[0];
break;
case 0:
bytes = 0;
break;
case 1:
bytes = v->ob_digit[0];
break;
default:
res = _PyLong_AsByteArray((PyLongObject *)v, (unsigned char *)&bytes,
SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 1);
}
if (do_decref) {
Py_DECREF(v);
}
/* Plan 9 can't handle long long in ? : expressions */
if (res < 0)
return (long long)-1;
else
return bytes;
}
/* Get a C unsigned long long int from an int object.
Return -1 and set an error if overflow occurs. */
unsigned long long
PyLong_AsUnsignedLongLong(PyObject *vv)
{
PyLongObject *v;
unsigned long long bytes;
int res;
if (vv == NULL) {
PyErr_BadInternalCall();
return (unsigned long long)-1;
}
if (!PyLong_Check(vv)) {
PyErr_SetString(PyExc_TypeError, "an integer is required");
return (unsigned long long)-1;
}
v = (PyLongObject*)vv;
switch(Py_SIZE(v)) {
case 0: return 0;
case 1: return v->ob_digit[0];
}
res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 0);
/* Plan 9 can't handle long long in ? : expressions */
if (res < 0)
return (unsigned long long)res;
else
return bytes;
}
/* Get a C unsigned long int from an int object, ignoring the high bits.
Returns -1 and sets an error condition if an error occurs. */
static unsigned long long
_PyLong_AsUnsignedLongLongMask(PyObject *vv)
{
PyLongObject *v;
unsigned long long x;
Py_ssize_t i;
int sign;
if (vv == NULL || !PyLong_Check(vv)) {
PyErr_BadInternalCall();
return (unsigned long long) -1;
}
v = (PyLongObject *)vv;
switch(Py_SIZE(v)) {
case 0: return 0;
case 1: return v->ob_digit[0];
}
i = Py_SIZE(v);
sign = 1;
x = 0;
if (i < 0) {
sign = -1;
i = -i;
}
while (--i >= 0) {
x = (x ob_digit[i];
}
return x * sign;
}
unsigned long long
PyLong_AsUnsignedLongLongMask(PyObject *op)
{
PyLongObject *lo;
unsigned long long val;
if (op == NULL) {
PyErr_BadInternalCall();
return (unsigned long long)-1;
}
if (PyLong_Check(op)) {
return _PyLong_AsUnsignedLongLongMask(op);
}
lo = (PyLongObject *)_PyNumber_Index(op);
if (lo == NULL)
return (unsigned long long)-1;
val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
Py_DECREF(lo);
return val;
}
/* Get a C long long int from an int object or any object that has an
__index__ method.
On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
the result. Otherwise *overflow is 0.
For other errors (e.g., TypeError), return -1 and set an error condition.
In this case *overflow will be 0.
*/
long long
PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow)
{
/* This version by Tim Peters */
PyLongObject *v;
unsigned long long x, prev;
long long res;
Py_ssize_t i;
int sign;
int do_decref = 0; /* if PyNumber_Index was called */
*overflow = 0;
if (vv == NULL) {
PyErr_BadInternalCall();
return -1;
}
if (PyLong_Check(vv)) {
v = (PyLongObject *)vv;
}
else {
v = (PyLongObject *)_PyNumber_Index(vv);
if (v == NULL)
return -1;
do_decref = 1;
}
res = -1;
i = Py_SIZE(v);
switch (i) {
case -1:
res = -(sdigit)v->ob_digit[0];
break;
case 0:
res = 0;
break;
case 1:
res = v->ob_digit[0];
break;
default:
sign = 1;
x = 0;
if (i < 0) {
sign = -1;
i = -(i);
}
while (--i >= 0) {
prev = x;
x = (x ob_digit[i];
if ((x >> PyLong_SHIFT) != prev) {
*overflow = sign;
goto exit;
}
}
/* Haven't lost any bits, but casting to long requires extra
* care (see comment above).
*/
if (x USHRT_MAX) {
PyErr_SetString(PyExc_OverflowError,
"Python int too large for C unsigned short");
return 0;
}
*(unsigned short *)ptr = Py_SAFE_DOWNCAST(uval, unsigned long, unsigned short);
return 1;
}
int
_PyLong_UnsignedInt_Converter(PyObject *obj, void *ptr)
{
unsigned long uval;
if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsUnsignedLong(obj);
if (uval == (unsigned long)-1 && PyErr_Occurred())
return 0;
if (uval > UINT_MAX) {
PyErr_SetString(PyExc_OverflowError,
"Python int too large for C unsigned int");
return 0;
}
*(unsigned int *)ptr = Py_SAFE_DOWNCAST(uval, unsigned long, unsigned int);
return 1;
}
int
_PyLong_UnsignedLong_Converter(PyObject *obj, void *ptr)
{
unsigned long uval;
if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsUnsignedLong(obj);
if (uval == (unsigned long)-1 && PyErr_Occurred())
return 0;
*(unsigned long *)ptr = uval;
return 1;
}
int
_PyLong_UnsignedLongLong_Converter(PyObject *obj, void *ptr)
{
unsigned long long uval;
if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsUnsignedLongLong(obj);
if (uval == (unsigned long long)-1 && PyErr_Occurred())
return 0;
*(unsigned long long *)ptr = uval;
return 1;
}
int
_PyLong_Size_t_Converter(PyObject *obj, void *ptr)
{
size_t uval;
if (PyLong_Check(obj) && _PyLong_Sign(obj) < 0) {
PyErr_SetString(PyExc_ValueError, "value must be positive");
return 0;
}
uval = PyLong_AsSize_t(obj);
if (uval == (size_t)-1 && PyErr_Occurred())
return 0;
*(size_t *)ptr = uval;
return 1;
}
#define CHECK_BINOP(v,w) \
do { \
if (!PyLong_Check(v) || !PyLong_Check(w)) \
Py_RETURN_NOTIMPLEMENTED; \
} while(0)
/* 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;
}
/* Shift digit vector a[0:m] d bits left, with 0 buffer) + writer->pos)); \
else \
assert(p == (TYPE*)PyUnicode_DATA(str)); \
} while (0)
/* fill the string right-to-left */
if (bytes_writer) {
char *p = *bytes_str + strlen;
WRITE_DIGITS(p);
assert(p == *bytes_str);
}
else if (kind == PyUnicode_1BYTE_KIND) {
Py_UCS1 *p;
WRITE_UNICODE_DIGITS(Py_UCS1);
}
else if (kind == PyUnicode_2BYTE_KIND) {
Py_UCS2 *p;
WRITE_UNICODE_DIGITS(Py_UCS2);
}
else {
Py_UCS4 *p;
assert (kind == PyUnicode_4BYTE_KIND);
WRITE_UNICODE_DIGITS(Py_UCS4);
}
#undef WRITE_DIGITS
#undef WRITE_UNICODE_DIGITS
Py_DECREF(scratch);
if (writer) {
writer->pos += strlen;
}
else if (bytes_writer) {
(*bytes_str) += strlen;
}
else {
assert(_PyUnicode_CheckConsistency(str, 1));
*p_output = (PyObject *)str;
}
return 0;
}
static PyObject *
long_to_decimal_string(PyObject *aa)
{
PyObject *v;
if (long_to_decimal_string_internal(aa, &v, NULL, NULL, NULL) == -1)
return NULL;
return v;
}
/* Convert an int object to a string, using a given conversion base,
which should be one of 2, 8 or 16. Return a string object.
If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'
if alternate is nonzero. */
static int
long_format_binary(PyObject *aa, int base, int alternate,
PyObject **p_output, _PyUnicodeWriter *writer,
_PyBytesWriter *bytes_writer, char **bytes_str)
{
PyLongObject *a = (PyLongObject *)aa;
PyObject *v = NULL;
Py_ssize_t sz;
Py_ssize_t size_a;
enum PyUnicode_Kind kind;
int negative;
int bits;
assert(base == 2 || base == 8 || base == 16);
if (a == NULL || !PyLong_Check(a)) {
PyErr_BadInternalCall();
return -1;
}
size_a = Py_ABS(Py_SIZE(a));
negative = Py_SIZE(a) < 0;
/* Compute a rough upper bound for the length of the string */
switch (base) {
case 16:
bits = 4;
break;
case 8:
bits = 3;
break;
case 2:
bits = 1;
break;
default:
Py_UNREACHABLE();
}
/* Compute exact length 'sz' of output string. */
if (size_a == 0) {
sz = 1;
}
else {
Py_ssize_t size_a_in_bits;
/* Ensure overflow doesn't occur during computation of sz. */
if (size_a > (PY_SSIZE_T_MAX - 3) / PyLong_SHIFT) {
PyErr_SetString(PyExc_OverflowError,
"int too large to format");
return -1;
}
size_a_in_bits = (size_a - 1) * PyLong_SHIFT +
_Py_bit_length(a->ob_digit[size_a - 1]);
/* Allow 1 character for a '-' sign. */
sz = negative + (size_a_in_bits + (bits - 1)) / bits;
}
if (alternate) {
/* 2 characters for prefix */
sz += 2;
}
if (writer) {
if (_PyUnicodeWriter_Prepare(writer, sz, 'x') == -1)
return -1;
kind = writer->kind;
}
else if (bytes_writer) {
*bytes_str = _PyBytesWriter_Prepare(bytes_writer, *bytes_str, sz);
if (*bytes_str == NULL)
return -1;
}
else {
v = PyUnicode_New(sz, 'x');
if (v == NULL)
return -1;
kind = PyUnicode_KIND(v);
}
#define WRITE_DIGITS(p) \
do { \
if (size_a == 0) { \
*--p = '0'; \
} \
else { \
/* JRH: special case for power-of-2 bases */ \
twodigits accum = 0; \
int accumbits = 0; /* # of bits in accum */ \
Py_ssize_t i; \
for (i = 0; i < size_a; ++i) { \
accum |= (twodigits)a->ob_digit[i] = bits); \
do { \
char cdigit; \
cdigit = (char)(accum & (base - 1)); \
cdigit += (cdigit < 10) ? '0' : 'a'-10; \
*--p = cdigit; \
accumbits -= bits; \
accum >>= bits; \
} while (i < size_a-1 ? accumbits >= bits : accum > 0); \
} \
} \
\
if (alternate) { \
if (base == 16) \
*--p = 'x'; \
else if (base == 8) \
*--p = 'o'; \
else /* (base == 2) */ \
*--p = 'b'; \
*--p = '0'; \
} \
if (negative) \
*--p = '-'; \
} while (0)
#define WRITE_UNICODE_DIGITS(TYPE) \
do { \
if (writer) \
p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + sz; \
else \
p = (TYPE*)PyUnicode_DATA(v) + sz; \
\
WRITE_DIGITS(p); \
\
if (writer) \
assert(p == ((TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos)); \
else \
assert(p == (TYPE*)PyUnicode_DATA(v)); \
} while (0)
if (bytes_writer) {
char *p = *bytes_str + sz;
WRITE_DIGITS(p);
assert(p == *bytes_str);
}
else if (kind == PyUnicode_1BYTE_KIND) {
Py_UCS1 *p;
WRITE_UNICODE_DIGITS(Py_UCS1);
}
else if (kind == PyUnicode_2BYTE_KIND) {
Py_UCS2 *p;
WRITE_UNICODE_DIGITS(Py_UCS2);
}
else {
Py_UCS4 *p;
assert (kind == PyUnicode_4BYTE_KIND);
WRITE_UNICODE_DIGITS(Py_UCS4);
}
#undef WRITE_DIGITS
#undef WRITE_UNICODE_DIGITS
if (writer) {
writer->pos += sz;
}
else if (bytes_writer) {
(*bytes_str) += sz;
}
else {
assert(_PyUnicode_CheckConsistency(v, 1));
*p_output = v;
}
return 0;
}
PyObject *
_PyLong_Format(PyObject *obj, int base)
{
PyObject *str;
int err;
if (base == 10)
err = long_to_decimal_string_internal(obj, &str, NULL, NULL, NULL);
else
err = long_format_binary(obj, base, 1, &str, NULL, NULL, NULL);
if (err == -1)
return NULL;
return str;
}
int
_PyLong_FormatWriter(_PyUnicodeWriter *writer,
PyObject *obj,
int base, int alternate)
{
if (base == 10)
return long_to_decimal_string_internal(obj, NULL, writer,
NULL, NULL);
else
return long_format_binary(obj, base, alternate, NULL, writer,
NULL, NULL);
}
char*
_PyLong_FormatBytesWriter(_PyBytesWriter *writer, char *str,
PyObject *obj,
int base, int alternate)
{
char *str2;
int res;
str2 = str;
if (base == 10)
res = long_to_decimal_string_internal(obj, NULL, NULL,
writer, &str2);
else
res = long_format_binary(obj, base, alternate, NULL, NULL,
writer, &str2);
if (res < 0)
return NULL;
assert(str2 != NULL);
return str2;
}
/* 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_CHARPyLong_MASK(c)] < B.
*/
unsigned char _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 int is returned.
* The point to this routine is that it takes time linear in the number of
* string characters.
*
* Return values:
* -1 on syntax error (exception needs to be set, *res is untouched)
* 0 else (exception may be set, in that case *res is set to NULL)
*/
static int
long_from_binary_base(const char **str, int base, PyLongObject **res)
{
const char *p = *str;
const char *start = p;
char prev = 0;
Py_ssize_t digits = 0;
int bits_per_char;
Py_ssize_t n;
PyLongObject *z;
twodigits accum;
int bits_in_accum;
digit *pdigit;
assert(base >= 2 && base >= 1;
}
/* count digits and set p to end-of-string */
while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base || *p == '_') {
if (*p == '_') {
if (prev == '_') {
*str = p - 1;
return -1;
}
} else {
++digits;
}
prev = *p;
++p;
}
if (prev == '_') {
/* Trailing underscore not allowed. */
*str = p - 1;
return -1;
}
*str = p;
/* n (PY_SSIZE_T_MAX - (PyLong_SHIFT - 1)) / bits_per_char) {
PyErr_SetString(PyExc_ValueError,
"int string too large to convert");
*res = NULL;
return 0;
}
n = (digits * bits_per_char + PyLong_SHIFT - 1) / PyLong_SHIFT;
z = _PyLong_New(n);
if (z == NULL) {
*res = NULL;
return 0;
}
/* Read string from right, and fill in int from left; i.e.,
* from least to most significant in both.
*/
accum = 0;
bits_in_accum = 0;
pdigit = z->ob_digit;
while (--p >= start) {
int k;
if (*p == '_') {
continue;
}
k = (int)_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;
*res = long_normalize(z);
return 0;
}
/* Parses an int from a bytestring. Leading and trailing whitespace will be
* ignored.
*
* If successful, a PyLong object will be returned and 'pend' will be pointing
* to the first unused byte unless it's NULL.
*
* If unsuccessful, NULL will be returned.
*/
PyObject *
PyLong_FromString(const char *str, char **pend, int base)
{
int sign = 1, error_if_nonzero = 0;
const char *start, *orig_str = str;
PyLongObject *z = NULL;
PyObject *strobj;
Py_ssize_t slen;
if ((base != 0 && base < 2) || base > 36) {
PyErr_SetString(PyExc_ValueError,
"int() arg 2 must be >= 2 and PY_SSIZE_T_MAX) ..." */
if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&
(a_size > (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 ||
a_bits > (PY_SSIZE_T_MAX - 1) % PyLong_SHIFT + 1))
goto overflow;
a_bits = (a_size - 1) * PyLong_SHIFT + a_bits;
/* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size]
(shifting left if a_bits b, return a positive number */
static Py_ssize_t
long_compare(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t sign = Py_SIZE(a) - Py_SIZE(b);
if (sign == 0) {
Py_ssize_t i = Py_ABS(Py_SIZE(a));
sdigit diff = 0;
while (--i >= 0) {
diff = (sdigit) a->ob_digit[i] - (sdigit) b->ob_digit[i];
if (diff) {
break;
}
}
sign = Py_SIZE(a) < 0 ? -diff : diff;
}
return sign;
}
static PyObject *
long_richcompare(PyObject *self, PyObject *other, int op)
{
Py_ssize_t result;
CHECK_BINOP(self, other);
if (self == other)
result = 0;
else
result = long_compare((PyLongObject*)self, (PyLongObject*)other);
Py_RETURN_RICHCOMPARE(result, 0, op);
}
static Py_hash_t
long_hash(PyLongObject *v)
{
Py_uhash_t x;
Py_ssize_t i;
int sign;
i = Py_SIZE(v);
switch(i) {
case -1: return v->ob_digit[0]==1 ? -2 : -(sdigit)v->ob_digit[0];
case 0: return 0;
case 1: return v->ob_digit[0];
}
sign = 1;
x = 0;
if (i < 0) {
sign = -1;
i = -(i);
}
while (--i >= 0) {
/* Here x is a quantity in the range [0, _PyHASH_MODULUS); we
want to compute x * 2**PyLong_SHIFT + v->ob_digit[i] modulo
_PyHASH_MODULUS.
The computation of x * 2**PyLong_SHIFT % _PyHASH_MODULUS
amounts to a rotation of the bits of x. To see this, write
x * 2**PyLong_SHIFT = y * 2**_PyHASH_BITS + z
where y = x >> (_PyHASH_BITS - PyLong_SHIFT) gives the top
PyLong_SHIFT bits of x (those that are shifted out of the
original _PyHASH_BITS bits, and z = (x ob_digit[i];
if (x >= _PyHASH_MODULUS)
x -= _PyHASH_MODULUS;
}
x = x * sign;
if (x == (Py_uhash_t)-1)
x = (Py_uhash_t)-2;
return (Py_hash_t)x;
}
/* Add the absolute values of two integers. */
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
PyLongObject *z;
Py_ssize_t i;
digit carry = 0;
/* Ensure a is the larger of the two: */
if (size_a < size_b) {
{ PyLongObject *temp = a; a = b; b = temp; }
{ Py_ssize_t size_temp = size_a;
size_a = size_b;
size_b = size_temp; }
}
z = _PyLong_New(size_a+1);
if (z == NULL)
return NULL;
for (i = 0; i < size_b; ++i) {
carry += a->ob_digit[i] + b->ob_digit[i];
z->ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
for (; i < size_a; ++i) {
carry += a->ob_digit[i];
z->ob_digit[i] = carry & PyLong_MASK;
carry >>= PyLong_SHIFT;
}
z->ob_digit[i] = carry;
return long_normalize(z);
}
/* Subtract the absolute values of two integers. */
static PyLongObject *
x_sub(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
PyLongObject *z;
Py_ssize_t i;
int sign = 1;
digit borrow = 0;
/* Ensure a is the larger of the two: */
if (size_a < size_b) {
sign = -1;
{ PyLongObject *temp = a; a = b; b = temp; }
{ Py_ssize_t size_temp = size_a;
size_a = size_b;
size_b = size_temp; }
}
else if (size_a == size_b) {
/* Find highest digit where a and b differ: */
i = size_a;
while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
;
if (i < 0)
return (PyLongObject *)PyLong_FromLong(0);
if (a->ob_digit[i] < b->ob_digit[i]) {
sign = -1;
{ PyLongObject *temp = a; a = b; b = temp; }
}
size_a = size_b = i+1;
}
z = _PyLong_New(size_a);
if (z == NULL)
return NULL;
for (i = 0; i < size_b; ++i) {
/* The following assumes unsigned arithmetic
works module 2**N for some N>PyLong_SHIFT. */
borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
z->ob_digit[i] = borrow & PyLong_MASK;
borrow >>= PyLong_SHIFT;
borrow &= 1; /* Keep only one sign bit */
}
for (; i < size_a; ++i) {
borrow = a->ob_digit[i] - borrow;
z->ob_digit[i] = borrow & PyLong_MASK;
borrow >>= PyLong_SHIFT;
borrow &= 1; /* Keep only one sign bit */
}
assert(borrow == 0);
if (sign < 0) {
Py_SET_SIZE(z, -Py_SIZE(z));
}
return maybe_small_long(long_normalize(z));
}
static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
CHECK_BINOP(a, b);
if (Py_ABS(Py_SIZE(a)) ob_digit + size_a;
SIGCHECK({
Py_DECREF(z);
return NULL;
});
carry = *pz + f * f;
*pz++ = (digit)(carry & PyLong_MASK);
carry >>= PyLong_SHIFT;
assert(carry ob_digit[i];
digit *pz = z->ob_digit + i;
digit *pb = b->ob_digit;
digit *pbend = b->ob_digit + size_b;
SIGCHECK({
Py_DECREF(z);
return NULL;
});
while (pb < pbend) {
carry += *pz + *pb++ * f;
*pz++ = (digit)(carry & PyLong_MASK);
carry >>= PyLong_SHIFT;
assert(carry > PyLong_SHIFT) == 0);
}
}
return long_normalize(z);
}
/* A helper for Karatsuba multiplication (k_mul).
Takes an int "n" and an integer "size" representing the place to
split, and sets low and high such that abs(n) == (high = 0.
Returns 0 on success, -1 on failure.
*/
static int
kmul_split(PyLongObject *n,
Py_ssize_t size,
PyLongObject **high,
PyLongObject **low)
{
PyLongObject *hi, *lo;
Py_ssize_t size_lo, size_hi;
const Py_ssize_t size_n = Py_ABS(Py_SIZE(n));
size_lo = Py_MIN(size_n, size);
size_hi = size_n - size_lo;
if ((hi = _PyLong_New(size_hi)) == NULL)
return -1;
if ((lo = _PyLong_New(size_lo)) == NULL) {
Py_DECREF(hi);
return -1;
}
memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
*high = long_normalize(hi);
*low = long_normalize(lo);
return 0;
}
static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
/* Karatsuba multiplication. Ignores the input signs, and returns the
* absolute value of the product (or NULL if error).
* See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
*/
static PyLongObject *
k_mul(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t asize = Py_ABS(Py_SIZE(a));
Py_ssize_t bsize = Py_ABS(Py_SIZE(b));
PyLongObject *ah = NULL;
PyLongObject *al = NULL;
PyLongObject *bh = NULL;
PyLongObject *bl = NULL;
PyLongObject *ret = NULL;
PyLongObject *t1, *t2, *t3;
Py_ssize_t shift; /* the number of digits we split off */
Py_ssize_t i;
/* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
* Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
* Then the original product is
* ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
* By picking X to be a power of 2, "*X" is just shifting, and it's
* been reduced to 3 multiplies on numbers half the size.
*/
/* We want to split based on the larger number; fiddle so that b
* is largest.
*/
if (asize > bsize) {
t1 = a;
a = b;
b = t1;
i = asize;
asize = bsize;
bsize = i;
}
/* Use gradeschool math when either number is too small. */
i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
if (asize ob_size. That
* leads to a sequence of balanced calls to k_mul.
*/
if (2 * asize > 1;
if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */
if (a == b) {
bh = ah;
bl = al;
Py_INCREF(bh);
Py_INCREF(bl);
}
else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
/* The plan:
* 1. Allocate result space (asize + bsize digits: that's always
* enough).
* 2. Compute ah*bh, and copy into result at 2*shift.
* 3. Compute al*bl, and copy into result at 0. Note that this
* can't overlap with #2.
* 4. Subtract al*bl from the result, starting at shift. This may
* underflow (borrow out of the high digit), but we don't care:
* we're effectively doing unsigned arithmetic mod
* BASE**(sizea + sizeb), and so long as the *final* result fits,
* borrows and carries out of the high digit can be ignored.
* 5. Subtract ah*bh from the result, starting at shift.
* 6. Compute (ah+al)*(bh+bl), and add it into the result starting
* at shift.
*/
/* 1. Allocate result space. */
ret = _PyLong_New(asize + bsize);
if (ret == NULL) goto fail;
#ifdef Py_DEBUG
/* Fill with trash, to catch reference to uninitialized digits. */
memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
#endif
/* 2. t1 = 0);
assert(2*shift + Py_SIZE(t1) ob_digit + 2*shift, t1->ob_digit,
Py_SIZE(t1) * sizeof(digit));
/* Zero-out the digits higher than the ah*bh copy. */
i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
if (i)
memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
i * sizeof(digit));
/* 3. t2 = 0);
assert(Py_SIZE(t2) ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));
/* Zero out remaining digits. */
i = 2*shift - Py_SIZE(t2); /* number of uninitialized digits */
if (i)
memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
/* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
* because it's fresher in cache.
*/
i = Py_SIZE(ret) - shift; /* # digits after shift */
(void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
Py_DECREF(t2);
(void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
Py_DECREF(t1);
/* 6. t3 = 0);
/* Add t3. It's not obvious why we can't run out of room here.
* See the (*) comment after this function.
*/
(void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
Py_DECREF(t3);
return long_normalize(ret);
fail:
Py_XDECREF(ret);
Py_XDECREF(ah);
Py_XDECREF(al);
Py_XDECREF(bh);
Py_XDECREF(bl);
return NULL;
}
/* (*) Why adding t3 can't "run out of room" above.
Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
to start with:
1. For any integer i, i = c(i/2) + f(i/2). In particular,
bsize = c(bsize/2) + f(bsize/2).
2. shift = f(bsize/2)
3. asize bsize/2 >= f(bsize/2) in this routine.
We allocated asize + bsize result digits, and add t3 into them at an offset
of shift. This leaves asize+bsize-shift allocated digit positions for t3
to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
asize + c(bsize/2) available digit positions.
bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
at most c(bsize/2) digits + 1 bit.
If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
The product (ah+al)*(bh+bl) therefore has at most
c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
and we have asize + c(bsize/2) available digit positions. We need to show
this is always enough. An instance of c(bsize/2) cancels out in both, so
the question reduces to whether asize digits is enough to hold
(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If
asize == bsize, then we're asking whether bsize digits is enough to hold
c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
is enough to hold 2 bits. This is so if bsize >= 2, which holds because
bsize >= KARATSUBA_CUTOFF >= 2.
Note that since there's always enough room for (ah+al)*(bh+bl), and that's
clearly >= each of ah*bh and al*bl, there's always enough room to subtract
ah*bh and al*bl too.
*/
/* b has at least twice the digits of a, and a is big enough that Karatsuba
* would pay off *if* the inputs had balanced sizes. View b as a sequence
* of slices, each with a->ob_size digits, and multiply the slices by a,
* one at a time. This gives k_mul balanced inputs to work with, and is
* also cache-friendly (we compute one double-width slice of the result
* at a time, then move on, never backtracking except for the helpful
* single-width slice overlap between successive partial sums).
*/
static PyLongObject *
k_lopsided_mul(PyLongObject *a, PyLongObject *b)
{
const Py_ssize_t asize = Py_ABS(Py_SIZE(a));
Py_ssize_t bsize = Py_ABS(Py_SIZE(b));
Py_ssize_t nbdone; /* # of b digits already multiplied */
PyLongObject *ret;
PyLongObject *bslice = NULL;
assert(asize > KARATSUBA_CUTOFF);
assert(2 * asize ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
/* Successive slices of b are copied into bslice. */
bslice = _PyLong_New(asize);
if (bslice == NULL)
goto fail;
nbdone = 0;
while (bsize > 0) {
PyLongObject *product;
const Py_ssize_t nbtouse = Py_MIN(bsize, asize);
/* Multiply the next slice of b by a. */
memcpy(bslice->ob_digit, b->ob_digit + nbdone,
nbtouse * sizeof(digit));
Py_SET_SIZE(bslice, nbtouse);
product = k_mul(a, bslice);
if (product == NULL)
goto fail;
/* Add into result. */
(void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
product->ob_digit, Py_SIZE(product));
Py_DECREF(product);
bsize -= nbtouse;
nbdone += nbtouse;
}
Py_DECREF(bslice);
return long_normalize(ret);
fail:
Py_DECREF(ret);
Py_XDECREF(bslice);
return NULL;
}
static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
PyLongObject *z;
CHECK_BINOP(a, b);
/* fast path for single-digit multiplication */
if (Py_ABS(Py_SIZE(a)) ob_digit[0];
sdigit mod;
assert(Py_ABS(Py_SIZE(a)) == 1);
assert(Py_ABS(Py_SIZE(b)) == 1);
if (Py_SIZE(a) == Py_SIZE(b)) {
/* 'a' and 'b' have the same sign. */
mod = left % right;
}
else {
/* Either 'a' or 'b' is negative. */
mod = right - 1 - (left - 1) % right;
}
return PyLong_FromLong(mod * (sdigit)Py_SIZE(b));
}
/* Fast floor division for single-digit longs. */
static PyObject *
fast_floor_div(PyLongObject *a, PyLongObject *b)
{
sdigit left = a->ob_digit[0];
sdigit right = b->ob_digit[0];
sdigit div;
assert(Py_ABS(Py_SIZE(a)) == 1);
assert(Py_ABS(Py_SIZE(b)) == 1);
if (Py_SIZE(a) == Py_SIZE(b)) {
/* 'a' and 'b' have the same sign. */
div = left / right;
}
else {
/* Either 'a' or 'b' is negative. */
div = -1 - (left - 1) / right;
}
return PyLong_FromLong(div);
}
/* The / and % operators are now defined in terms of divmod().
The expression a mod b has the value a - b*floor(a/b).
The long_divrem function gives the remainder after division of
|a| by |b|, with the sign of a. This is also expressed
as a - b*trunc(a/b), if trunc truncates towards zero.
Some examples:
a b a rem b a mod b
13 10 3 3
-13 10 -3 7
13 -10 3 -7
-13 -10 -3 -3
So, to get from rem to mod, we have to add b if a and b
have different signs. We then subtract one from the 'div'
part of the outcome to keep the invariant intact. */
/* Compute
* *pdiv, *pmod = divmod(v, w)
* NULL can be passed for pdiv or pmod, in which case that part of
* the result is simply thrown away. The caller owns a reference to
* each of these it requests (does not pass NULL for).
*/
static int
l_divmod(PyLongObject *v, PyLongObject *w,
PyLongObject **pdiv, PyLongObject **pmod)
{
PyLongObject *div, *mod;
if (Py_ABS(Py_SIZE(v)) == 1 && Py_ABS(Py_SIZE(w)) == 1) {
/* Fast path for single-digit longs */
div = NULL;
if (pdiv != NULL) {
div = (PyLongObject *)fast_floor_div(v, w);
if (div == NULL) {
return -1;
}
}
if (pmod != NULL) {
mod = (PyLongObject *)fast_mod(v, w);
if (mod == NULL) {
Py_XDECREF(div);
return -1;
}
*pmod = mod;
}
if (pdiv != NULL) {
/* We only want to set `*pdiv` when `*pmod` is
set successfully. */
*pdiv = div;
}
return 0;
}
if (long_divrem(v, w, &div, &mod) < 0)
return -1;
if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
(Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
PyLongObject *temp;
temp = (PyLongObject *) long_add(mod, w);
Py_DECREF(mod);
mod = temp;
if (mod == NULL) {
Py_DECREF(div);
return -1;
}
temp = (PyLongObject *) long_sub(div, (PyLongObject *)_PyLong_One);
if (temp == NULL) {
Py_DECREF(mod);
Py_DECREF(div);
return -1;
}
Py_DECREF(div);
div = temp;
}
if (pdiv != NULL)
*pdiv = div;
else
Py_DECREF(div);
if (pmod != NULL)
*pmod = mod;
else
Py_DECREF(mod);
return 0;
}
static PyObject *
long_div(PyObject *a, PyObject *b)
{
PyLongObject *div;
CHECK_BINOP(a, b);
if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) {
return fast_floor_div((PyLongObject*)a, (PyLongObject*)b);
}
if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
div = NULL;
return (PyObject *)div;
}
/* PyLong/PyLong -> float, with correctly rounded result. */
#define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT)
#define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT)
static PyObject *
long_true_divide(PyObject *v, PyObject *w)
{
PyLongObject *a, *b, *x;
Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits;
digit mask, low;
int inexact, negate, a_is_small, b_is_small;
double dx, result;
CHECK_BINOP(v, w);
a = (PyLongObject *)v;
b = (PyLongObject *)w;
/*
Method in a nutshell:
0. reduce to case a, b > 0; filter out obvious underflow/overflow
1. choose a suitable integer 'shift'
2. use integer arithmetic to compute x = floor(2**-shift*a/b)
3. adjust x for correct rounding
4. convert x to a double dx with the same value
5. return ldexp(dx, shift).
In more detail:
0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b
returns either 0.0 or -0.0, depending on the sign of b. For a and
b both nonzero, ignore signs of a and b, and add the sign back in
at the end. Now write a_bits and b_bits for the bit lengths of a
and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise
for b). Then
2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1).
So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and
so overflows. Similarly, if a_bits - b_bits < DBL_MIN_EXP -
DBL_MANT_DIG - 1 then a/b underflows to 0. With these cases out of
the way, we can assume that
DBL_MIN_EXP - DBL_MANT_DIG - 1 = 1.
3. Now x * 2**shift = DBL_MIN_EXP -
DBL_MANT_DIG. This translates to the condition:
extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG
To round, we just modify the bottom digit of x in-place; this can
end up giving a digit with value > PyLONG_MASK, but that's not a
problem since digits can hold values up to 2*PyLONG_MASK+1.
With the original choices for shift above, extra_bits will always
be 2 or 3. Then rounding under the round-half-to-even rule, we
round up iff the most significant of the extra bits is 1, and
either: (a) the computation of x in step 2 had an inexact result,
or (b) at least one other of the extra bits is 1, or (c) the least
significant bit of x (above those to be rounded) is 1.
4. Conversion to a double is straightforward; all floating-point
operations involved in the conversion are exact, so there's no
danger of rounding errors.
5. Use ldexp(x, shift) to compute x*2**shift, the final result.
The result will always be exactly representable as a double, except
in the case that it overflows. To avoid dependence on the exact
behaviour of ldexp on overflow, we check for overflow before
applying ldexp. The result of ldexp is adjusted for sign before
returning.
*/
/* Reduce to case where a and b are both positive. */
a_size = Py_ABS(Py_SIZE(a));
b_size = Py_ABS(Py_SIZE(b));
negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0);
if (b_size == 0) {
PyErr_SetString(PyExc_ZeroDivisionError,
"division by zero");
goto error;
}
if (a_size == 0)
goto underflow_or_zero;
/* Fast path for a and b small (exactly representable in a double).
Relies on floating-point division being correctly rounded; results
may be subject to double rounding on x86 machines that operate with
the x87 FPU set to 64-bit precision. */
a_is_small = a_size ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
b_is_small = b_size ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
if (a_is_small && b_is_small) {
double da, db;
da = a->ob_digit[--a_size];
while (a_size > 0)
da = da * PyLong_BASE + a->ob_digit[--a_size];
db = b->ob_digit[--b_size];
while (b_size > 0)
db = db * PyLong_BASE + b->ob_digit[--b_size];
result = da / db;
goto success;
}
/* Catch obvious cases of underflow and overflow */
diff = a_size - b_size;
if (diff > PY_SSIZE_T_MAX/PyLong_SHIFT - 1)
/* Extreme overflow */
goto overflow;
else if (diff < 1 - PY_SSIZE_T_MAX/PyLong_SHIFT)
/* Extreme underflow */
goto underflow_or_zero;
/* Next line is now safe from overflowing a Py_ssize_t */
diff = diff * PyLong_SHIFT + _Py_bit_length(a->ob_digit[a_size - 1]) -
_Py_bit_length(b->ob_digit[b_size - 1]);
/* Now diff = a_bits - b_bits. */
if (diff > DBL_MAX_EXP)
goto overflow;
else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1)
goto underflow_or_zero;
/* Choose value for shift; see comments for step 1 above. */
shift = Py_MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2;
inexact = 0;
/* x = abs(a * 2**-shift) */
if (shift ob_digit, x->ob_digit, x_size,
b->ob_digit[0]);
long_normalize(x);
if (rem)
inexact = 1;
}
else {
PyLongObject *div, *rem;
div = x_divrem(x, b, &rem);
Py_DECREF(x);
x = div;
if (x == NULL)
goto error;
if (Py_SIZE(rem))
inexact = 1;
Py_DECREF(rem);
}
x_size = Py_ABS(Py_SIZE(x));
assert(x_size > 0); /* result of division is never zero */
x_bits = (x_size-1)*PyLong_SHIFT+_Py_bit_length(x->ob_digit[x_size-1]);
/* The number of extra bits that have to be rounded away. */
extra_bits = Py_MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;
assert(extra_bits == 2 || extra_bits == 3);
/* Round by directly modifying the low digit of x. */
mask = (digit)1 ob_digit[0] | inexact;
if ((low & mask) && (low & (3U*mask-1U)))
low += mask;
x->ob_digit[0] = low & ~(2U*mask-1U);
/* Convert x to a double dx; the conversion is exact. */
dx = x->ob_digit[--x_size];
while (x_size > 0)
dx = dx * PyLong_BASE + x->ob_digit[--x_size];
Py_DECREF(x);
/* Check whether ldexp result will overflow a double. */
if (shift + x_bits >= DBL_MAX_EXP &&
(shift + x_bits > DBL_MAX_EXP || dx == ldexp(1.0, (int)x_bits)))
goto overflow;
result = ldexp(dx, (int)shift);
success:
return PyFloat_FromDouble(negate ? -result : result);
underflow_or_zero:
return PyFloat_FromDouble(negate ? -0.0 : 0.0);
overflow:
PyErr_SetString(PyExc_OverflowError,
"integer division result too large for a float");
error:
return NULL;
}
static PyObject *
long_mod(PyObject *a, PyObject *b)
{
PyLongObject *mod;
CHECK_BINOP(a, b);
if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) {
return fast_mod((PyLongObject*)a, (PyLongObject*)b);
}
if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0)
mod = NULL;
return (PyObject *)mod;
}
static PyObject *
long_divmod(PyObject *a, PyObject *b)
{
PyLongObject *div, *mod;
PyObject *z;
CHECK_BINOP(a, b);
if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, &mod) < 0) {
return NULL;
}
z = PyTuple_New(2);
if (z != NULL) {
PyTuple_SET_ITEM(z, 0, (PyObject *) div);
PyTuple_SET_ITEM(z, 1, (PyObject *) mod);
}
else {
Py_DECREF(div);
Py_DECREF(mod);
}
return z;
}
/* Compute an inverse to a modulo n, or raise ValueError if a is not
invertible modulo n. Assumes n is positive. The inverse returned
is whatever falls out of the extended Euclidean algorithm: it may
be either positive or negative, but will be smaller than n in
absolute value.
Pure Python equivalent for long_invmod:
def invmod(a, n):
b, c = 1, 0
while n:
q, r = divmod(a, n)
a, b, c, n = n, c, b - q*c, r
# at this point a is the gcd of the original inputs
if a == 1:
return b
raise ValueError("Not invertible")
*/
static PyLongObject *
long_invmod(PyLongObject *a, PyLongObject *n)
{
PyLongObject *b, *c;
/* Should only ever be called for positive n */
assert(Py_SIZE(n) > 0);
b = (PyLongObject *)PyLong_FromLong(1L);
if (b == NULL) {
return NULL;
}
c = (PyLongObject *)PyLong_FromLong(0L);
if (c == NULL) {
Py_DECREF(b);
return NULL;
}
Py_INCREF(a);
Py_INCREF(n);
/* references now owned: a, b, c, n */
while (Py_SIZE(n) != 0) {
PyLongObject *q, *r, *s, *t;
if (l_divmod(a, n, &q, &r) == -1) {
goto Error;
}
Py_DECREF(a);
a = n;
n = r;
t = (PyLongObject *)long_mul(q, c);
Py_DECREF(q);
if (t == NULL) {
goto Error;
}
s = (PyLongObject *)long_sub(b, t);
Py_DECREF(t);
if (s == NULL) {
goto Error;
}
Py_DECREF(b);
b = c;
c = s;
}
/* references now owned: a, b, c, n */
Py_DECREF(c);
Py_DECREF(n);
if (long_compare(a, (PyLongObject *)_PyLong_One)) {
/* a != 1; we don't have an inverse. */
Py_DECREF(a);
Py_DECREF(b);
PyErr_SetString(PyExc_ValueError,
"base is not invertible for the given modulus");
return NULL;
}
else {
/* a == 1; b gives an inverse modulo n */
Py_DECREF(a);
return b;
}
Error:
Py_DECREF(a);
Py_DECREF(b);
Py_DECREF(c);
Py_DECREF(n);
return NULL;
}
/* pow(v, w, x) */
static PyObject *
long_pow(PyObject *v, PyObject *w, PyObject *x)
{
PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
int negativeOutput = 0; /* if x Py_SIZE(c)) {
if (l_divmod(a, c, NULL, &temp) < 0)
goto Error;
Py_DECREF(a);
a = temp;
temp = NULL;
}
}
/* At this point a, b, and c are guaranteed non-negative UNLESS
c is NULL, in which case a may be negative. */
z = (PyLongObject *)PyLong_FromLong(1L);
if (z == NULL)
goto Error;
/* Perform a modular reduction, X = X % c, but leave X alone if c
* is NULL.
*/
#define REDUCE(X) \
do { \
if (c != NULL) { \
if (l_divmod(X, c, NULL, &temp) < 0) \
goto Error; \
Py_XDECREF(X); \
X = temp; \
temp = NULL; \
} \
} while(0)
/* Multiply two values, then reduce the result:
result = X*Y % c. If c is NULL, skip the mod. */
#define MULT(X, Y, result) \
do { \
temp = (PyLongObject *)long_mul(X, Y); \
if (temp == NULL) \
goto Error; \
Py_XDECREF(result); \
result = temp; \
temp = NULL; \
REDUCE(result); \
} while(0)
if (Py_SIZE(b) = 0; --i) {
digit bi = b->ob_digit[i];
for (j = (digit)1 >= 1) {
MULT(z, z, z);
if (bi & j)
MULT(z, a, z);
}
}
}
else {
/* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
Py_INCREF(z); /* still holds 1L */
table[0] = z;
for (i = 1; i < 32; ++i)
MULT(table[i-1], a, table[i]);
for (i = Py_SIZE(b) - 1; i >= 0; --i) {
const digit bi = b->ob_digit[i];
for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
const int index = (bi >> j) & 0x1f;
for (k = 0; k < 5; ++k)
MULT(z, z, z);
if (index)
MULT(z, table[index], z);
}
}
}
if (negativeOutput && (Py_SIZE(z) != 0)) {
temp = (PyLongObject *)long_sub(z, c);
if (temp == NULL)
goto Error;
Py_DECREF(z);
z = temp;
temp = NULL;
}
goto Done;
Error:
Py_CLEAR(z);
/* fall through */
Done:
if (Py_SIZE(b) > FIVEARY_CUTOFF) {
for (i = 0; i < 32; ++i)
Py_XDECREF(table[i]);
}
Py_DECREF(a);
Py_DECREF(b);
Py_XDECREF(c);
Py_XDECREF(temp);
return (PyObject *)z;
}
static PyObject *
long_invert(PyLongObject *v)
{
/* Implement ~x as -(x+1) */
PyLongObject *x;
if (Py_ABS(Py_SIZE(v)) = 0, so it must
be that PyLong_AsSsize_t raised an OverflowError. */
assert(PyErr_ExceptionMatches(PyExc_OverflowError));
PyErr_Clear();
PyLongObject *wordshift_obj = divrem1((PyLongObject *)shiftby, PyLong_SHIFT, remshift);
if (wordshift_obj == NULL) {
return -1;
}
*wordshift = PyLong_AsSsize_t((PyObject *)wordshift_obj);
Py_DECREF(wordshift_obj);
if (*wordshift >= 0 && *wordshift < PY_SSIZE_T_MAX / (Py_ssize_t)sizeof(digit)) {
return 0;
}
PyErr_Clear();
/* Clip the value. With such large wordshift the right shift
returns 0 and the left shift raises an error in _PyLong_New(). */
*wordshift = PY_SSIZE_T_MAX / sizeof(digit);
*remshift = 0;
return 0;
}
static PyObject *
long_rshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift)
{
PyLongObject *z = NULL;
Py_ssize_t newsize, hishift, i, j;
digit lomask, himask;
if (Py_SIZE(a) < 0) {
/* Right shifting negative numbers is harder */
PyLongObject *a1, *a2;
a1 = (PyLongObject *) long_invert(a);
if (a1 == NULL)
return NULL;
a2 = (PyLongObject *) long_rshift1(a1, wordshift, remshift);
Py_DECREF(a1);
if (a2 == NULL)
return NULL;
z = (PyLongObject *) long_invert(a2);
Py_DECREF(a2);
}
else {
newsize = Py_SIZE(a) - wordshift;
if (newsize ob_digit[j] >> remshift) & lomask;
if (i+1 < newsize)
z->ob_digit[i] |= (a->ob_digit[j+1] > shiftby. */
PyObject *
_PyLong_Rshift(PyObject *a, size_t shiftby)
{
Py_ssize_t wordshift;
digit remshift;
assert(PyLong_Check(a));
if (Py_SIZE(a) == 0) {
return PyLong_FromLong(0);
}
wordshift = shiftby / PyLong_SHIFT;
remshift = shiftby % PyLong_SHIFT;
return long_rshift1((PyLongObject *)a, wordshift, remshift);
}
static PyObject *
long_lshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift)
{
/* This version due to Tim Peters */
PyLongObject *z = NULL;
Py_ssize_t oldsize, newsize, i, j;
twodigits accum;
oldsize = Py_ABS(Py_SIZE(a));
newsize = oldsize + wordshift;
if (remshift)
++newsize;
z = _PyLong_New(newsize);
if (z == NULL)
return NULL;
if (Py_SIZE(a) < 0) {
assert(Py_REFCNT(z) == 1);
Py_SET_SIZE(z, -Py_SIZE(z));
}
for (i = 0; i < wordshift; i++)
z->ob_digit[i] = 0;
accum = 0;
for (i = wordshift, j = 0; j < oldsize; i++, j++) {
accum |= (twodigits)a->ob_digit[j] ob_digit[i] = (digit)(accum & PyLong_MASK);
accum >>= PyLong_SHIFT;
}
if (remshift)
z->ob_digit[newsize-1] = (digit)accum;
else
assert(!accum);
z = long_normalize(z);
return (PyObject *) maybe_small_long(z);
}
static PyObject *
long_lshift(PyObject *a, PyObject *b)
{
Py_ssize_t wordshift;
digit remshift;
CHECK_BINOP(a, b);
if (Py_SIZE(b) < 0) {
PyErr_SetString(PyExc_ValueError, "negative shift count");
return NULL;
}
if (Py_SIZE(a) == 0) {
return PyLong_FromLong(0);
}
if (divmod_shift(b, &wordshift, &remshift) < 0)
return NULL;
return long_lshift1((PyLongObject *)a, wordshift, remshift);
}
/* Return a ob_digit, a->ob_digit, size_a);
a = z;
}
else
/* Keep reference count consistent. */
Py_INCREF(a);
/* Same for b. */
size_b = Py_ABS(Py_SIZE(b));
negb = Py_SIZE(b) < 0;
if (negb) {
z = _PyLong_New(size_b);
if (z == NULL) {
Py_DECREF(a);
return NULL;
}
v_complement(z->ob_digit, b->ob_digit, size_b);
b = z;
}
else
Py_INCREF(b);
/* Swap a and b if necessary to ensure size_a >= size_b. */
if (size_a < size_b) {
z = a; a = b; b = z;
size_z = size_a; size_a = size_b; size_b = size_z;
negz = nega; nega = negb; negb = negz;
}
/* JRH: The original logic here was to allocate the result value (z)
as the longer of the two operands. However, there are some cases
where the result is guaranteed to be shorter than that: AND of two
positives, OR of two negatives: use the shorter number. AND with
mixed signs: use the positive number. OR with mixed signs: use the
negative number.
*/
switch (op) {
case '^':
negz = nega ^ negb;
size_z = size_a;
break;
case '&':
negz = nega & negb;
size_z = negb ? size_a : size_b;
break;
case '|':
negz = nega | negb;
size_z = negb ? size_b : size_a;
break;
default:
Py_UNREACHABLE();
}
/* We allow an extra digit if z is negative, to make sure that
the final two's complement of z doesn't overflow. */
z = _PyLong_New(size_z + negz);
if (z == NULL) {
Py_DECREF(a);
Py_DECREF(b);
return NULL;
}
/* Compute digits for overlap of a and b. */
switch(op) {
case '&':
for (i = 0; i < size_b; ++i)
z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i];
break;
case '|':
for (i = 0; i < size_b; ++i)
z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i];
break;
case '^':
for (i = 0; i < size_b; ++i)
z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i];
break;
default:
Py_UNREACHABLE();
}
/* Copy any remaining digits of a, inverting if necessary. */
if (op == '^' && negb)
for (; i < size_z; ++i)
z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK;
else if (i < size_z)
memcpy(&z->ob_digit[i], &a->ob_digit[i],
(size_z-i)*sizeof(digit));
/* Complement result if negative. */
if (negz) {
Py_SET_SIZE(z, -(Py_SIZE(z)));
z->ob_digit[size_z] = PyLong_MASK;
v_complement(z->ob_digit, z->ob_digit, size_z+1);
}
Py_DECREF(a);
Py_DECREF(b);
return (PyObject *)maybe_small_long(long_normalize(z));
}
static PyObject *
long_and(PyObject *a, PyObject *b)
{
PyObject *c;
CHECK_BINOP(a, b);
c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b);
return c;
}
static PyObject *
long_xor(PyObject *a, PyObject *b)
{
PyObject *c;
CHECK_BINOP(a, b);
c = long_bitwise((PyLongObject*)a, '^', (PyLongObject*)b);
return c;
}
static PyObject *
long_or(PyObject *a, PyObject *b)
{
PyObject *c;
CHECK_BINOP(a, b);
c = long_bitwise((PyLongObject*)a, '|', (PyLongObject*)b);
return c;
}
static PyObject *
long_long(PyObject *v)
{
if (PyLong_CheckExact(v))
Py_INCREF(v);
else
v = _PyLong_Copy((PyLongObject *)v);
return v;
}
PyObject *
_PyLong_GCD(PyObject *aarg, PyObject *barg)
{
PyLongObject *a, *b, *c = NULL, *d = NULL, *r;
stwodigits x, y, q, s, t, c_carry, d_carry;
stwodigits A, B, C, D, T;
int nbits, k;
Py_ssize_t size_a, size_b, alloc_a, alloc_b;
digit *a_digit, *b_digit, *c_digit, *d_digit, *a_end, *b_end;
a = (PyLongObject *)aarg;
b = (PyLongObject *)barg;
size_a = Py_SIZE(a);
size_b = Py_SIZE(b);
if (-2 ob_digit[size_a-3] >> nbits : 0) |
(size_b >= size_a - 1 ? (twodigits)b->ob_digit[size_a-2] = size_a ? (twodigits)b->ob_digit[size_a-1] integer\n\
int(x, base=10) -> integer\n\
\n\
Convert a number or string to an integer, or return 0 if no arguments\n\
are given. If x is a number, return x.__int__(). For floating point\n\
numbers, this truncates towards zero.\n\
\n\
If x is not a number or if base is given, then x must be a string,\n\
bytes, or bytearray instance representing an integer literal in the\n\
given base. The literal can be preceded by '+' or '-' and be surrounded\n\
by whitespace. The base defaults to 10. Valid bases are 0 and 2-36.\n\
Base 0 means to interpret the base from the string as an integer literal.\n\
>>> int('0b100', base=0)\n\
4");
static PyNumberMethods long_as_number = {
(binaryfunc)long_add, /*nb_add*/
(binaryfunc)long_sub, /*nb_subtract*/
(binaryfunc)long_mul, /*nb_multiply*/
long_mod, /*nb_remainder*/
long_divmod, /*nb_divmod*/
long_pow, /*nb_power*/
(unaryfunc)long_neg, /*nb_negative*/
long_long, /*tp_positive*/
(unaryfunc)long_abs, /*tp_absolute*/
(inquiry)long_bool, /*tp_bool*/
(unaryfunc)long_invert, /*nb_invert*/
long_lshift, /*nb_lshift*/
long_rshift, /*nb_rshift*/
long_and, /*nb_and*/
long_xor, /*nb_xor*/
long_or, /*nb_or*/
long_long, /*nb_int*/
0, /*nb_reserved*/
long_float, /*nb_float*/
0, /* nb_inplace_add */
0, /* nb_inplace_subtract */
0, /* nb_inplace_multiply */
0, /* nb_inplace_remainder */
0, /* nb_inplace_power */
0, /* nb_inplace_lshift */
0, /* nb_inplace_rshift */
0, /* nb_inplace_and */
0, /* nb_inplace_xor */
0, /* nb_inplace_or */
long_div, /* nb_floor_divide */
long_true_divide, /* nb_true_divide */
0, /* nb_inplace_floor_divide */
0, /* nb_inplace_true_divide */
long_long, /* nb_index */
};
PyTypeObject PyLong_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int", /* tp_name */
offsetof(PyLongObject, ob_digit), /* tp_basicsize */
sizeof(digit), /* tp_itemsize */
0, /* tp_dealloc */
0, /* tp_vectorcall_offset */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_as_async */
long_to_decimal_string, /* tp_repr */
&long_as_number, /* tp_as_number */
0, /* tp_as_sequence */
0, /* tp_as_mapping */
(hashfunc)long_hash, /* tp_hash */
0, /* tp_call */
0, /* tp_str */
PyObject_GenericGetAttr, /* tp_getattro */
0, /* tp_setattro */
0, /* tp_as_buffer */
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE |
Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */
long_doc, /* tp_doc */
0, /* tp_traverse */
0, /* tp_clear */
long_richcompare, /* tp_richcompare */
0, /* tp_weaklistoffset */
0, /* tp_iter */
0, /* tp_iternext */
long_methods, /* tp_methods */
0, /* tp_members */
long_getset, /* tp_getset */
0, /* tp_base */
0, /* tp_dict */
0, /* tp_descr_get */
0, /* tp_descr_set */
0, /* tp_dictoffset */
0, /* tp_init */
0, /* tp_alloc */
long_new, /* tp_new */
PyObject_Del, /* tp_free */
};
static PyTypeObject Int_InfoType;
PyDoc_STRVAR(int_info__doc__,
"sys.int_info\n\
\n\
A named tuple that holds information about Python's\n\
internal representation of integers. The attributes are read only.");
static PyStructSequence_Field int_info_fields[] = {
{"bits_per_digit", "size of a digit in bits"},
{"sizeof_digit", "size in bytes of the C type used to represent a digit"},
{NULL, NULL}
};
static PyStructSequence_Desc int_info_desc = {
"sys.int_info", /* name */
int_info__doc__, /* doc */
int_info_fields, /* fields */
2 /* number of fields */
};
PyObject *
PyLong_GetInfo(void)
{
PyObject* int_info;
int field = 0;
int_info = PyStructSequence_New(&Int_InfoType);
if (int_info == NULL)
return NULL;
PyStructSequence_SET_ITEM(int_info, field++,
PyLong_FromLong(PyLong_SHIFT));
PyStructSequence_SET_ITEM(int_info, field++,
PyLong_FromLong(sizeof(digit)));
if (PyErr_Occurred()) {
Py_CLEAR(int_info);
return NULL;
}
return int_info;
}
int
_PyLong_Init(PyThreadState *tstate)
{
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
for (Py_ssize_t i=0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++) {
sdigit ival = (sdigit)i - NSMALLNEGINTS;
int size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
PyLongObject *v = _PyLong_New(1);
if (!v) {
return -1;
}
Py_SET_SIZE(v, size);
v->ob_digit[0] = (digit)abs(ival);
tstate->interp->small_ints[i] = v;
}
#endif
if (_Py_IsMainInterpreter(tstate)) {
_PyLong_Zero = PyLong_FromLong(0);
if (_PyLong_Zero == NULL) {
return 0;
}
_PyLong_One = PyLong_FromLong(1);
if (_PyLong_One == NULL) {
return 0;
}
/* initialize int_info */
if (Int_InfoType.tp_name == NULL) {
if (PyStructSequence_InitType2(&Int_InfoType, &int_info_desc) < 0) {
return 0;
}
}
}
return 1;
}
void
_PyLong_Fini(PyThreadState *tstate)
{
if (_Py_IsMainInterpreter(tstate)) {
Py_CLEAR(_PyLong_One);
Py_CLEAR(_PyLong_Zero);
}
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
for (Py_ssize_t i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++) {
Py_CLEAR(tstate->interp->small_ints[i]);
}
#endif
}