summaryrefslogtreecommitdiffstats
path: root/Objects/longobject.c
diff options
context:
space:
mode:
Diffstat (limited to 'Objects/longobject.c')
-rw-r--r--Objects/longobject.c6668
1 files changed, 3334 insertions, 3334 deletions
diff --git a/Objects/longobject.c b/Objects/longobject.c
index e41d06a..f7c2e3a 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -11,16 +11,16 @@
#include <stddef.h>
#ifndef NSMALLPOSINTS
-#define NSMALLPOSINTS 257
+#define NSMALLPOSINTS 257
#endif
#ifndef NSMALLNEGINTS
-#define NSMALLNEGINTS 5
+#define NSMALLNEGINTS 5
#endif
/* convert a PyLong of size 1, 0 or -1 to an sdigit */
-#define MEDIUM_VALUE(x) (Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \
- (Py_SIZE(x) == 0 ? (sdigit)0 : \
- (sdigit)(x)->ob_digit[0]))
+#define MEDIUM_VALUE(x) (Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \
+ (Py_SIZE(x) == 0 ? (sdigit)0 : \
+ (sdigit)(x)->ob_digit[0]))
#define ABS(x) ((x) < 0 ? -(x) : (x))
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
@@ -37,32 +37,32 @@ int quick_int_allocs, quick_neg_int_allocs;
static PyObject *
get_small_int(sdigit ival)
{
- PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS);
- Py_INCREF(v);
+ PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS);
+ Py_INCREF(v);
#ifdef COUNT_ALLOCS
- if (ival >= 0)
- quick_int_allocs++;
- else
- quick_neg_int_allocs++;
+ if (ival >= 0)
+ quick_int_allocs++;
+ else
+ quick_neg_int_allocs++;
#endif
- return v;
+ return v;
}
#define CHECK_SMALL_INT(ival) \
- do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
- return get_small_int((sdigit)ival); \
- } while(0)
+ do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
+ return get_small_int((sdigit)ival); \
+ } while(0)
-static PyLongObject *
+static PyLongObject *
maybe_small_long(PyLongObject *v)
{
- if (v && ABS(Py_SIZE(v)) <= 1) {
- sdigit ival = MEDIUM_VALUE(v);
- if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
- Py_DECREF(v);
- return (PyLongObject *)get_small_int(ival);
- }
- }
- return v;
+ if (v && ABS(Py_SIZE(v)) <= 1) {
+ sdigit ival = MEDIUM_VALUE(v);
+ if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
+ Py_DECREF(v);
+ return (PyLongObject *)get_small_int(ival);
+ }
+ }
+ return v;
}
#else
#define CHECK_SMALL_INT(ival)
@@ -72,10 +72,10 @@ maybe_small_long(PyLongObject *v)
/* If a freshly-allocated long is already shared, it must
be a small integer, so negating it must go to PyLong_FromLong */
#define NEGATE(x) \
- do if (Py_REFCNT(x) == 1) Py_SIZE(x) = -Py_SIZE(x); \
- else { PyObject* tmp=PyLong_FromLong(-MEDIUM_VALUE(x)); \
- Py_DECREF(x); (x) = (PyLongObject*)tmp; } \
- while(0)
+ do if (Py_REFCNT(x) == 1) Py_SIZE(x) = -Py_SIZE(x); \
+ else { PyObject* tmp=PyLong_FromLong(-MEDIUM_VALUE(x)); \
+ Py_DECREF(x); (x) = (PyLongObject*)tmp; } \
+ while(0)
/* For long multiplication, use the O(N**2) school algorithm unless
* both operands contain more than KARATSUBA_CUTOFF digits (this
* being an internal Python long digit, in base BASE).
@@ -96,10 +96,10 @@ maybe_small_long(PyLongObject *v)
#define MIN(x, y) ((x) > (y) ? (y) : (x))
#define SIGCHECK(PyTryBlock) \
- if (--_Py_Ticker < 0) { \
- _Py_Ticker = _Py_CheckInterval; \
- if (PyErr_CheckSignals()) PyTryBlock \
- }
+ if (--_Py_Ticker < 0) { \
+ _Py_Ticker = _Py_CheckInterval; \
+ if (PyErr_CheckSignals()) PyTryBlock \
+ }
/* forward declaration */
static int bits_in_digit(digit d);
@@ -111,68 +111,68 @@ static int bits_in_digit(digit d);
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;
+ 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. */
#define MAX_LONG_DIGITS \
- ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
+ ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
PyLongObject *
_PyLong_New(Py_ssize_t size)
{
- PyLongObject *result;
- /* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
- sizeof(digit)*size. Previous incarnations of this code used
- sizeof(PyVarObject) instead of the offsetof, but this risks being
- incorrect in the presence of padding between the PyVarObject header
- and the digits. */
- if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
- PyErr_SetString(PyExc_OverflowError,
- "too many digits in integer");
- return NULL;
- }
- result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
- size*sizeof(digit));
- if (!result) {
- PyErr_NoMemory();
- return NULL;
- }
- return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
+ PyLongObject *result;
+ /* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
+ sizeof(digit)*size. Previous incarnations of this code used
+ sizeof(PyVarObject) instead of the offsetof, but this risks being
+ incorrect in the presence of padding between the PyVarObject header
+ and the digits. */
+ if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
+ PyErr_SetString(PyExc_OverflowError,
+ "too many digits in integer");
+ return NULL;
+ }
+ result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
+ size*sizeof(digit));
+ if (!result) {
+ PyErr_NoMemory();
+ return NULL;
+ }
+ return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
}
PyObject *
_PyLong_Copy(PyLongObject *src)
{
- PyLongObject *result;
- Py_ssize_t i;
-
- assert(src != NULL);
- i = Py_SIZE(src);
- if (i < 0)
- i = -(i);
- if (i < 2) {
- sdigit ival = src->ob_digit[0];
- if (Py_SIZE(src) < 0)
- ival = -ival;
- CHECK_SMALL_INT(ival);
- }
- result = _PyLong_New(i);
- if (result != NULL) {
- Py_SIZE(result) = Py_SIZE(src);
- while (--i >= 0)
- result->ob_digit[i] = src->ob_digit[i];
- }
- return (PyObject *)result;
+ PyLongObject *result;
+ Py_ssize_t i;
+
+ assert(src != NULL);
+ i = Py_SIZE(src);
+ if (i < 0)
+ i = -(i);
+ if (i < 2) {
+ sdigit ival = src->ob_digit[0];
+ if (Py_SIZE(src) < 0)
+ ival = -ival;
+ CHECK_SMALL_INT(ival);
+ }
+ result = _PyLong_New(i);
+ if (result != NULL) {
+ Py_SIZE(result) = Py_SIZE(src);
+ while (--i >= 0)
+ result->ob_digit[i] = src->ob_digit[i];
+ }
+ return (PyObject *)result;
}
/* Create a new long int object from a C long int */
@@ -180,68 +180,68 @@ _PyLong_Copy(PyLongObject *src)
PyObject *
PyLong_FromLong(long ival)
{
- PyLongObject *v;
- unsigned long abs_ival;
- unsigned long t; /* unsigned so >> doesn't propagate sign bit */
- int ndigits = 0;
- int sign = 1;
-
- CHECK_SMALL_INT(ival);
-
- if (ival < 0) {
- /* negate: can't write this as abs_ival = -ival since that
- invokes undefined behaviour when ival is LONG_MIN */
- abs_ival = 0U-(unsigned long)ival;
- sign = -1;
- }
- else {
- abs_ival = (unsigned long)ival;
- }
-
- /* Fast path for single-digit ints */
- if (!(abs_ival >> PyLong_SHIFT)) {
- v = _PyLong_New(1);
- if (v) {
- Py_SIZE(v) = sign;
- v->ob_digit[0] = Py_SAFE_DOWNCAST(
- abs_ival, unsigned long, digit);
- }
- return (PyObject*)v;
- }
+ PyLongObject *v;
+ unsigned long abs_ival;
+ unsigned long t; /* unsigned so >> doesn't propagate sign bit */
+ int ndigits = 0;
+ int sign = 1;
+
+ CHECK_SMALL_INT(ival);
+
+ if (ival < 0) {
+ /* negate: can't write this as abs_ival = -ival since that
+ invokes undefined behaviour when ival is LONG_MIN */
+ abs_ival = 0U-(unsigned long)ival;
+ sign = -1;
+ }
+ else {
+ abs_ival = (unsigned long)ival;
+ }
+
+ /* Fast path for single-digit ints */
+ if (!(abs_ival >> PyLong_SHIFT)) {
+ v = _PyLong_New(1);
+ if (v) {
+ Py_SIZE(v) = sign;
+ v->ob_digit[0] = Py_SAFE_DOWNCAST(
+ abs_ival, unsigned long, digit);
+ }
+ return (PyObject*)v;
+ }
#if PyLong_SHIFT==15
- /* 2 digits */
- if (!(abs_ival >> 2*PyLong_SHIFT)) {
- v = _PyLong_New(2);
- if (v) {
- Py_SIZE(v) = 2*sign;
- v->ob_digit[0] = Py_SAFE_DOWNCAST(
- abs_ival & PyLong_MASK, unsigned long, digit);
- v->ob_digit[1] = Py_SAFE_DOWNCAST(
- abs_ival >> PyLong_SHIFT, unsigned long, digit);
- }
- return (PyObject*)v;
- }
+ /* 2 digits */
+ if (!(abs_ival >> 2*PyLong_SHIFT)) {
+ v = _PyLong_New(2);
+ if (v) {
+ Py_SIZE(v) = 2*sign;
+ v->ob_digit[0] = Py_SAFE_DOWNCAST(
+ abs_ival & PyLong_MASK, unsigned long, digit);
+ v->ob_digit[1] = Py_SAFE_DOWNCAST(
+ abs_ival >> PyLong_SHIFT, unsigned long, digit);
+ }
+ return (PyObject*)v;
+ }
#endif
- /* Larger numbers: loop to determine number of digits */
- t = abs_ival;
- while (t) {
- ++ndigits;
- t >>= PyLong_SHIFT;
- }
- v = _PyLong_New(ndigits);
- if (v != NULL) {
- digit *p = v->ob_digit;
- Py_SIZE(v) = ndigits*sign;
- t = abs_ival;
- while (t) {
- *p++ = Py_SAFE_DOWNCAST(
- t & PyLong_MASK, unsigned long, digit);
- t >>= PyLong_SHIFT;
- }
- }
- return (PyObject *)v;
+ /* Larger numbers: loop to determine number of digits */
+ t = abs_ival;
+ while (t) {
+ ++ndigits;
+ t >>= PyLong_SHIFT;
+ }
+ v = _PyLong_New(ndigits);
+ if (v != NULL) {
+ digit *p = v->ob_digit;
+ Py_SIZE(v) = ndigits*sign;
+ t = abs_ival;
+ while (t) {
+ *p++ = Py_SAFE_DOWNCAST(
+ t & PyLong_MASK, unsigned long, digit);
+ t >>= PyLong_SHIFT;
+ }
+ }
+ return (PyObject *)v;
}
/* Create a new long int object from a C unsigned long int */
@@ -249,28 +249,28 @@ PyLong_FromLong(long ival)
PyObject *
PyLong_FromUnsignedLong(unsigned long ival)
{
- PyLongObject *v;
- unsigned long t;
- int ndigits = 0;
-
- if (ival < PyLong_BASE)
- return PyLong_FromLong(ival);
- /* Count the number of Python digits. */
- t = (unsigned long)ival;
- while (t) {
- ++ndigits;
- t >>= PyLong_SHIFT;
- }
- v = _PyLong_New(ndigits);
- if (v != NULL) {
- digit *p = v->ob_digit;
- Py_SIZE(v) = ndigits;
- while (ival) {
- *p++ = (digit)(ival & PyLong_MASK);
- ival >>= PyLong_SHIFT;
- }
- }
- return (PyObject *)v;
+ PyLongObject *v;
+ unsigned long t;
+ int ndigits = 0;
+
+ if (ival < PyLong_BASE)
+ return PyLong_FromLong(ival);
+ /* Count the number of Python digits. */
+ t = (unsigned long)ival;
+ while (t) {
+ ++ndigits;
+ t >>= PyLong_SHIFT;
+ }
+ v = _PyLong_New(ndigits);
+ if (v != NULL) {
+ digit *p = v->ob_digit;
+ Py_SIZE(v) = ndigits;
+ while (ival) {
+ *p++ = (digit)(ival & PyLong_MASK);
+ ival >>= PyLong_SHIFT;
+ }
+ }
+ return (PyObject *)v;
}
/* Create a new long int object from a C double */
@@ -278,41 +278,41 @@ PyLong_FromUnsignedLong(unsigned long ival)
PyObject *
PyLong_FromDouble(double dval)
{
- PyLongObject *v;
- double frac;
- int i, ndig, expo, neg;
- neg = 0;
- if (Py_IS_INFINITY(dval)) {
- PyErr_SetString(PyExc_OverflowError,
- "cannot convert float infinity to integer");
- return NULL;
- }
- if (Py_IS_NAN(dval)) {
- PyErr_SetString(PyExc_ValueError,
- "cannot convert float NaN to integer");
- return NULL;
- }
- if (dval < 0.0) {
- neg = 1;
- dval = -dval;
- }
- frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
- if (expo <= 0)
- return PyLong_FromLong(0L);
- ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
- v = _PyLong_New(ndig);
- if (v == NULL)
- return NULL;
- frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
- for (i = ndig; --i >= 0; ) {
- digit bits = (digit)frac;
- v->ob_digit[i] = bits;
- frac = frac - (double)bits;
- frac = ldexp(frac, PyLong_SHIFT);
- }
- if (neg)
- Py_SIZE(v) = -(Py_SIZE(v));
- return (PyObject *)v;
+ PyLongObject *v;
+ double frac;
+ int i, ndig, expo, neg;
+ neg = 0;
+ if (Py_IS_INFINITY(dval)) {
+ PyErr_SetString(PyExc_OverflowError,
+ "cannot convert float infinity to integer");
+ return NULL;
+ }
+ if (Py_IS_NAN(dval)) {
+ PyErr_SetString(PyExc_ValueError,
+ "cannot convert float NaN to integer");
+ return NULL;
+ }
+ if (dval < 0.0) {
+ neg = 1;
+ dval = -dval;
+ }
+ frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
+ if (expo <= 0)
+ return PyLong_FromLong(0L);
+ ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
+ v = _PyLong_New(ndig);
+ if (v == NULL)
+ return NULL;
+ frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
+ for (i = ndig; --i >= 0; ) {
+ digit bits = (digit)frac;
+ v->ob_digit[i] = 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
@@ -324,8 +324,8 @@ PyLong_FromDouble(double dval)
* 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)
+#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. */
@@ -333,101 +333,101 @@ PyLong_FromDouble(double dval)
long
PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
{
- /* This version by Tim Peters */
- register PyLongObject *v;
- unsigned long x, prev;
- long res;
- Py_ssize_t i;
- int sign;
- int do_decref = 0; /* if nb_int was called */
-
- *overflow = 0;
- if (vv == NULL) {
- PyErr_BadInternalCall();
- return -1;
- }
-
- if (!PyLong_Check(vv)) {
- PyNumberMethods *nb;
- if ((nb = vv->ob_type->tp_as_number) == NULL ||
- nb->nb_int == NULL) {
- PyErr_SetString(PyExc_TypeError, "an integer is required");
- return -1;
- }
- vv = (*nb->nb_int) (vv);
- if (vv == NULL)
- return -1;
- do_decref = 1;
- if (!PyLong_Check(vv)) {
- Py_DECREF(vv);
- PyErr_SetString(PyExc_TypeError,
- "nb_int should return int object");
- return -1;
- }
- }
-
- res = -1;
- v = (PyLongObject *)vv;
- i = Py_SIZE(v);
-
- switch (i) {
- case -1:
- res = -(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 << PyLong_SHIFT) + v->ob_digit[i];
- if ((x >> PyLong_SHIFT) != prev) {
- *overflow = Py_SIZE(v) > 0 ? 1 : -1;
- goto exit;
- }
- }
- /* Haven't lost any bits, but casting to long requires extra care
- * (see comment above).
- */
- if (x <= (unsigned long)LONG_MAX) {
- res = (long)x * sign;
- }
- else if (sign < 0 && x == PY_ABS_LONG_MIN) {
- res = LONG_MIN;
- }
- else {
- *overflow = Py_SIZE(v) > 0 ? 1 : -1;
- /* res is already set to -1 */
- }
- }
+ /* This version by Tim Peters */
+ register PyLongObject *v;
+ unsigned long x, prev;
+ long res;
+ Py_ssize_t i;
+ int sign;
+ int do_decref = 0; /* if nb_int was called */
+
+ *overflow = 0;
+ if (vv == NULL) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+
+ if (!PyLong_Check(vv)) {
+ PyNumberMethods *nb;
+ if ((nb = vv->ob_type->tp_as_number) == NULL ||
+ nb->nb_int == NULL) {
+ PyErr_SetString(PyExc_TypeError, "an integer is required");
+ return -1;
+ }
+ vv = (*nb->nb_int) (vv);
+ if (vv == NULL)
+ return -1;
+ do_decref = 1;
+ if (!PyLong_Check(vv)) {
+ Py_DECREF(vv);
+ PyErr_SetString(PyExc_TypeError,
+ "nb_int should return int object");
+ return -1;
+ }
+ }
+
+ res = -1;
+ v = (PyLongObject *)vv;
+ i = Py_SIZE(v);
+
+ switch (i) {
+ case -1:
+ res = -(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 << PyLong_SHIFT) + v->ob_digit[i];
+ if ((x >> PyLong_SHIFT) != prev) {
+ *overflow = Py_SIZE(v) > 0 ? 1 : -1;
+ goto exit;
+ }
+ }
+ /* Haven't lost any bits, but casting to long requires extra care
+ * (see comment above).
+ */
+ if (x <= (unsigned long)LONG_MAX) {
+ res = (long)x * sign;
+ }
+ else if (sign < 0 && x == PY_ABS_LONG_MIN) {
+ res = LONG_MIN;
+ }
+ else {
+ *overflow = Py_SIZE(v) > 0 ? 1 : -1;
+ /* res is already set to -1 */
+ }
+ }
exit:
- if (do_decref) {
- Py_DECREF(vv);
- }
- return res;
+ if (do_decref) {
+ Py_DECREF(vv);
+ }
+ return res;
}
-long
+long
PyLong_AsLong(PyObject *obj)
{
- int overflow;
- long result = PyLong_AsLongAndOverflow(obj, &overflow);
- if (overflow) {
- /* XXX: could be cute and give a different
- message for overflow == -1 */
- PyErr_SetString(PyExc_OverflowError,
- "Python int too large to convert to C long");
- }
- return result;
+ int overflow;
+ long result = PyLong_AsLongAndOverflow(obj, &overflow);
+ if (overflow) {
+ /* XXX: could be cute and give a different
+ message for overflow == -1 */
+ PyErr_SetString(PyExc_OverflowError,
+ "Python int too large to convert to C long");
+ }
+ return result;
}
/* Get a Py_ssize_t from a long int object.
@@ -435,54 +435,54 @@ PyLong_AsLong(PyObject *obj)
Py_ssize_t
PyLong_AsSsize_t(PyObject *vv) {
- register PyLongObject *v;
- size_t x, prev;
- Py_ssize_t i;
- int sign;
-
- if (vv == NULL) {
- PyErr_BadInternalCall();
- return -1;
- }
- if (!PyLong_Check(vv)) {
- PyErr_SetString(PyExc_TypeError, "an integer is required");
- return -1;
- }
-
- v = (PyLongObject *)vv;
- i = Py_SIZE(v);
- switch (i) {
- case -1: return -(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) {
- prev = x;
- x = (x << PyLong_SHIFT) + v->ob_digit[i];
- if ((x >> PyLong_SHIFT) != prev)
- goto overflow;
- }
- /* Haven't lost any bits, but casting to a signed type requires
- * extra care (see comment above).
- */
- if (x <= (size_t)PY_SSIZE_T_MAX) {
- return (Py_ssize_t)x * sign;
- }
- else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
- return PY_SSIZE_T_MIN;
- }
- /* else overflow */
+ register PyLongObject *v;
+ size_t x, prev;
+ Py_ssize_t i;
+ int sign;
+
+ if (vv == NULL) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ if (!PyLong_Check(vv)) {
+ PyErr_SetString(PyExc_TypeError, "an integer is required");
+ return -1;
+ }
+
+ v = (PyLongObject *)vv;
+ i = Py_SIZE(v);
+ switch (i) {
+ case -1: return -(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) {
+ prev = x;
+ x = (x << PyLong_SHIFT) + v->ob_digit[i];
+ if ((x >> PyLong_SHIFT) != prev)
+ goto overflow;
+ }
+ /* Haven't lost any bits, but casting to a signed type requires
+ * extra care (see comment above).
+ */
+ if (x <= (size_t)PY_SSIZE_T_MAX) {
+ return (Py_ssize_t)x * sign;
+ }
+ else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
+ return PY_SSIZE_T_MIN;
+ }
+ /* else overflow */
overflow:
- PyErr_SetString(PyExc_OverflowError,
- "Python int too large to convert to C ssize_t");
- return -1;
+ PyErr_SetString(PyExc_OverflowError,
+ "Python int too large to convert to C ssize_t");
+ return -1;
}
/* Get a C unsigned long int from a long int object.
@@ -491,41 +491,41 @@ PyLong_AsSsize_t(PyObject *vv) {
unsigned long
PyLong_AsUnsignedLong(PyObject *vv)
{
- register PyLongObject *v;
- unsigned long x, prev;
- Py_ssize_t i;
-
- if (vv == NULL) {
- PyErr_BadInternalCall();
- return (unsigned long)-1;
- }
- if (!PyLong_Check(vv)) {
- PyErr_SetString(PyExc_TypeError, "an integer is required");
- return (unsigned long)-1;
- }
-
- v = (PyLongObject *)vv;
- i = Py_SIZE(v);
- x = 0;
- if (i < 0) {
- PyErr_SetString(PyExc_OverflowError,
- "can't convert negative value to unsigned int");
- return (unsigned long) -1;
- }
- switch (i) {
- case 0: return 0;
- case 1: return v->ob_digit[0];
- }
- while (--i >= 0) {
- prev = x;
- x = (x << PyLong_SHIFT) + v->ob_digit[i];
- if ((x >> PyLong_SHIFT) != prev) {
- PyErr_SetString(PyExc_OverflowError,
- "python int too large to convert to C unsigned long");
- return (unsigned long) -1;
- }
- }
- return x;
+ register PyLongObject *v;
+ unsigned long x, prev;
+ Py_ssize_t i;
+
+ if (vv == NULL) {
+ PyErr_BadInternalCall();
+ return (unsigned long)-1;
+ }
+ if (!PyLong_Check(vv)) {
+ PyErr_SetString(PyExc_TypeError, "an integer is required");
+ return (unsigned long)-1;
+ }
+
+ v = (PyLongObject *)vv;
+ i = Py_SIZE(v);
+ x = 0;
+ if (i < 0) {
+ PyErr_SetString(PyExc_OverflowError,
+ "can't convert negative value to unsigned int");
+ return (unsigned long) -1;
+ }
+ switch (i) {
+ case 0: return 0;
+ case 1: return v->ob_digit[0];
+ }
+ while (--i >= 0) {
+ prev = x;
+ x = (x << PyLong_SHIFT) + v->ob_digit[i];
+ if ((x >> PyLong_SHIFT) != prev) {
+ PyErr_SetString(PyExc_OverflowError,
+ "python int too large to convert to C unsigned long");
+ return (unsigned long) -1;
+ }
+ }
+ return x;
}
/* Get a C unsigned long int from a long int object.
@@ -534,41 +534,41 @@ PyLong_AsUnsignedLong(PyObject *vv)
size_t
PyLong_AsSize_t(PyObject *vv)
{
- register 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 << PyLong_SHIFT) + v->ob_digit[i];
- if ((x >> PyLong_SHIFT) != prev) {
- PyErr_SetString(PyExc_OverflowError,
- "Python int too large to convert to C size_t");
- return (unsigned long) -1;
- }
- }
- return x;
+ register 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 << PyLong_SHIFT) + v->ob_digit[i];
+ if ((x >> PyLong_SHIFT) != prev) {
+ PyErr_SetString(PyExc_OverflowError,
+ "Python int too large to convert to C size_t");
+ return (unsigned long) -1;
+ }
+ }
+ return x;
}
/* Get a C unsigned long int from a long int object, ignoring the high bits.
@@ -577,354 +577,354 @@ PyLong_AsSize_t(PyObject *vv)
static unsigned long
_PyLong_AsUnsignedLongMask(PyObject *vv)
{
- register PyLongObject *v;
- unsigned long x;
- Py_ssize_t i;
- int sign;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return (unsigned long) -1;
- }
- v = (PyLongObject *)vv;
- i = Py_SIZE(v);
- switch (i) {
- case 0: return 0;
- case 1: return v->ob_digit[0];
- }
- sign = 1;
- x = 0;
- if (i < 0) {
- sign = -1;
- i = -i;
- }
- while (--i >= 0) {
- x = (x << PyLong_SHIFT) + v->ob_digit[i];
- }
- return x * sign;
+ register PyLongObject *v;
+ unsigned long x;
+ Py_ssize_t i;
+ int sign;
+
+ if (vv == NULL || !PyLong_Check(vv)) {
+ PyErr_BadInternalCall();
+ return (unsigned long) -1;
+ }
+ v = (PyLongObject *)vv;
+ i = Py_SIZE(v);
+ switch (i) {
+ case 0: return 0;
+ case 1: return v->ob_digit[0];
+ }
+ sign = 1;
+ x = 0;
+ if (i < 0) {
+ sign = -1;
+ i = -i;
+ }
+ while (--i >= 0) {
+ x = (x << PyLong_SHIFT) + v->ob_digit[i];
+ }
+ return x * sign;
}
unsigned long
PyLong_AsUnsignedLongMask(register PyObject *op)
{
- PyNumberMethods *nb;
- PyLongObject *lo;
- unsigned long val;
-
- if (op && PyLong_Check(op))
- return _PyLong_AsUnsignedLongMask(op);
-
- if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
- nb->nb_int == NULL) {
- PyErr_SetString(PyExc_TypeError, "an integer is required");
- return (unsigned long)-1;
- }
-
- lo = (PyLongObject*) (*nb->nb_int) (op);
- if (lo == NULL)
- return (unsigned long)-1;
- if (PyLong_Check(lo)) {
- val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
- Py_DECREF(lo);
- if (PyErr_Occurred())
- return (unsigned long)-1;
- return val;
- }
- else
- {
- Py_DECREF(lo);
- PyErr_SetString(PyExc_TypeError,
- "nb_int should return int object");
- return (unsigned long)-1;
- }
+ PyNumberMethods *nb;
+ PyLongObject *lo;
+ unsigned long val;
+
+ if (op && PyLong_Check(op))
+ return _PyLong_AsUnsignedLongMask(op);
+
+ if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
+ nb->nb_int == NULL) {
+ PyErr_SetString(PyExc_TypeError, "an integer is required");
+ return (unsigned long)-1;
+ }
+
+ lo = (PyLongObject*) (*nb->nb_int) (op);
+ if (lo == NULL)
+ return (unsigned long)-1;
+ if (PyLong_Check(lo)) {
+ val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
+ Py_DECREF(lo);
+ if (PyErr_Occurred())
+ return (unsigned long)-1;
+ return val;
+ }
+ else
+ {
+ Py_DECREF(lo);
+ PyErr_SetString(PyExc_TypeError,
+ "nb_int should return int object");
+ return (unsigned long)-1;
+ }
}
int
_PyLong_Sign(PyObject *vv)
{
- PyLongObject *v = (PyLongObject *)vv;
+ PyLongObject *v = (PyLongObject *)vv;
- assert(v != NULL);
- assert(PyLong_Check(v));
+ assert(v != NULL);
+ assert(PyLong_Check(v));
- return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
+ 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;
+ PyLongObject *v = (PyLongObject *)vv;
+ size_t result = 0;
+ Py_ssize_t ndigits;
+
+ assert(v != NULL);
+ assert(PyLong_Check(v));
+ ndigits = ABS(Py_SIZE(v));
+ assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
+ if (ndigits > 0) {
+ digit msd = v->ob_digit[ndigits - 1];
+
+ result = (ndigits - 1) * PyLong_SHIFT;
+ if (result / PyLong_SHIFT != (size_t)(ndigits - 1))
+ goto Overflow;
+ do {
+ ++result;
+ if (result == 0)
+ goto Overflow;
+ msd >>= 1;
+ } while (msd);
+ }
+ return result;
Overflow:
- PyErr_SetString(PyExc_OverflowError, "int has too many bits "
- "to express in a platform size_t");
- return (size_t)-1;
+ 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)
+ 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 long 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 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. */
- /* 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 |= (twodigits)thisbyte << accumbits;
- accumbits += 8;
- if (accumbits >= 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_SIZE(v) = is_signed ? -idigit : idigit;
- return (PyObject *)long_normalize(v);
+ 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 long 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 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. */
+ /* 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 |= (twodigits)thisbyte << accumbits;
+ accumbits += 8;
+ if (accumbits >= 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_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)
+ 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 long is
- normalized. */
- assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
- j = 0;
- accum = 0;
- accumbits = 0;
- carry = do_twos_comp ? 1 : 0;
- for (i = 0; i < ndigits; ++i) {
- digit thisdigit = v->ob_digit[i];
- if (do_twos_comp) {
- thisdigit = (thisdigit ^ PyLong_MASK) + carry;
- carry = thisdigit >> PyLong_SHIFT;
- thisdigit &= PyLong_MASK;
- }
- /* Because we're going LSB to MSB, thisdigit is more
- significant than what's already in accum, so needs to be
- prepended to accum. */
- accum |= (twodigits)thisdigit << accumbits;
-
- /* The most-significant digit may be (probably is) at least
- partly empty. */
- if (i == ndigits - 1) {
- /* Count # of sign bits -- they needn't be stored,
- * although for signed conversion we need later to
- * make sure at least one sign bit gets stored. */
- digit s = do_twos_comp ? thisdigit ^ PyLong_MASK :
- thisdigit;
- while (s != 0) {
- s >>= 1;
- accumbits++;
- }
- }
- else
- accumbits += PyLong_SHIFT;
-
- /* Store as many bytes as possible. */
- while (accumbits >= 8) {
- if (j >= n)
- goto Overflow;
- ++j;
- *p = (unsigned char)(accum & 0xff);
- p += pincr;
- accumbits -= 8;
- accum >>= 8;
- }
- }
-
- /* Store the straggler (if any). */
- assert(accumbits < 8);
- assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
- if (accumbits > 0) {
- if (j >= n)
- goto Overflow;
- ++j;
- if (do_twos_comp) {
- /* Fill leading bits of the byte with sign bits
- (appropriately pretending that the long had an
- infinite supply of sign bits). */
- accum |= (~(twodigits)0) << accumbits;
- }
- *p = (unsigned char)(accum & 0xff);
- p += pincr;
- }
- else if (j == n && n > 0 && is_signed) {
- /* The main loop filled the byte array exactly, so the code
- just above didn't get to ensure there's a sign bit, and the
- loop below wouldn't add one either. Make sure a sign bit
- exists. */
- unsigned char msb = *(p - pincr);
- int sign_bit_set = msb >= 0x80;
- assert(accumbits == 0);
- if (sign_bit_set == do_twos_comp)
- return 0;
- else
- goto Overflow;
- }
-
- /* Fill remaining bytes with copies of the sign bit. */
- {
- unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
- for ( ; j < n; ++j, p += pincr)
- *p = signbyte;
- }
-
- return 0;
+ 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 long is
+ normalized. */
+ assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
+ j = 0;
+ accum = 0;
+ accumbits = 0;
+ carry = do_twos_comp ? 1 : 0;
+ for (i = 0; i < ndigits; ++i) {
+ digit thisdigit = v->ob_digit[i];
+ if (do_twos_comp) {
+ thisdigit = (thisdigit ^ PyLong_MASK) + carry;
+ carry = thisdigit >> PyLong_SHIFT;
+ thisdigit &= PyLong_MASK;
+ }
+ /* Because we're going LSB to MSB, thisdigit is more
+ significant than what's already in accum, so needs to be
+ prepended to accum. */
+ accum |= (twodigits)thisdigit << accumbits;
+
+ /* The most-significant digit may be (probably is) at least
+ partly empty. */
+ if (i == ndigits - 1) {
+ /* Count # of sign bits -- they needn't be stored,
+ * although for signed conversion we need later to
+ * make sure at least one sign bit gets stored. */
+ digit s = do_twos_comp ? thisdigit ^ PyLong_MASK :
+ thisdigit;
+ while (s != 0) {
+ s >>= 1;
+ accumbits++;
+ }
+ }
+ else
+ accumbits += PyLong_SHIFT;
+
+ /* Store as many bytes as possible. */
+ while (accumbits >= 8) {
+ if (j >= n)
+ goto Overflow;
+ ++j;
+ *p = (unsigned char)(accum & 0xff);
+ p += pincr;
+ accumbits -= 8;
+ accum >>= 8;
+ }
+ }
+
+ /* Store the straggler (if any). */
+ assert(accumbits < 8);
+ assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
+ if (accumbits > 0) {
+ if (j >= n)
+ goto Overflow;
+ ++j;
+ if (do_twos_comp) {
+ /* Fill leading bits of the byte with sign bits
+ (appropriately pretending that the long had an
+ infinite supply of sign bits). */
+ accum |= (~(twodigits)0) << accumbits;
+ }
+ *p = (unsigned char)(accum & 0xff);
+ p += pincr;
+ }
+ else if (j == n && n > 0 && is_signed) {
+ /* The main loop filled the byte array exactly, so the code
+ just above didn't get to ensure there's a sign bit, and the
+ loop below wouldn't add one either. Make sure a sign bit
+ exists. */
+ unsigned char msb = *(p - pincr);
+ int sign_bit_set = msb >= 0x80;
+ assert(accumbits == 0);
+ if (sign_bit_set == do_twos_comp)
+ return 0;
+ else
+ goto Overflow;
+ }
+
+ /* Fill remaining bytes with copies of the sign bit. */
+ {
+ unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
+ for ( ; j < n; ++j, p += pincr)
+ *p = signbyte;
+ }
+
+ return 0;
Overflow:
- PyErr_SetString(PyExc_OverflowError, "int too big to convert");
- return -1;
+ PyErr_SetString(PyExc_OverflowError, "int too big to convert");
+ return -1;
}
@@ -942,42 +942,42 @@ _PyLong_AsScaledDouble(PyObject *vv, int *exponent)
least one round bit to stand in for the ignored least-significant bits.
*/
#define NBITS_WANTED 57
- PyLongObject *v;
- double x;
- const double multiplier = (double)(1L << PyLong_SHIFT);
- Py_ssize_t i;
- int sign;
- int nbitsneeded;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return -1;
- }
- v = (PyLongObject *)vv;
- i = Py_SIZE(v);
- sign = 1;
- if (i < 0) {
- sign = -1;
- i = -(i);
- }
- else if (i == 0) {
- *exponent = 0;
- return 0.0;
- }
- --i;
- x = (double)v->ob_digit[i];
- nbitsneeded = NBITS_WANTED - 1;
- /* Invariant: i Python digits remain unaccounted for. */
- while (i > 0 && nbitsneeded > 0) {
- --i;
- x = x * multiplier + (double)v->ob_digit[i];
- nbitsneeded -= PyLong_SHIFT;
- }
- /* There are i digits we didn't shift in. Pretending they're all
- zeroes, the true value is x * 2**(i*PyLong_SHIFT). */
- *exponent = i;
- assert(x > 0.0);
- return x * sign;
+ PyLongObject *v;
+ double x;
+ const double multiplier = (double)(1L << PyLong_SHIFT);
+ Py_ssize_t i;
+ int sign;
+ int nbitsneeded;
+
+ if (vv == NULL || !PyLong_Check(vv)) {
+ PyErr_BadInternalCall();
+ return -1;
+ }
+ v = (PyLongObject *)vv;
+ i = Py_SIZE(v);
+ sign = 1;
+ if (i < 0) {
+ sign = -1;
+ i = -(i);
+ }
+ else if (i == 0) {
+ *exponent = 0;
+ return 0.0;
+ }
+ --i;
+ x = (double)v->ob_digit[i];
+ nbitsneeded = NBITS_WANTED - 1;
+ /* Invariant: i Python digits remain unaccounted for. */
+ while (i > 0 && nbitsneeded > 0) {
+ --i;
+ x = x * multiplier + (double)v->ob_digit[i];
+ nbitsneeded -= PyLong_SHIFT;
+ }
+ /* There are i digits we didn't shift in. Pretending they're all
+ zeroes, the true value is x * 2**(i*PyLong_SHIFT). */
+ *exponent = i;
+ assert(x > 0.0);
+ return x * sign;
#undef NBITS_WANTED
}
@@ -987,163 +987,163 @@ _PyLong_AsScaledDouble(PyObject *vv, int *exponent)
double
PyLong_AsDouble(PyObject *vv)
{
- PyLongObject *v = (PyLongObject *)vv;
- Py_ssize_t rnd_digit, rnd_bit, m, n;
- digit lsb, *d;
- int round_up = 0;
- double x;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return -1.0;
- }
-
- /* Notes on the method: for simplicity, assume v is positive and >=
- 2**DBL_MANT_DIG. (For negative v we just ignore the sign until the
- end; for small v no rounding is necessary.) Write n for the number
- of bits in v, so that 2**(n-1) <= v < 2**n, and n > DBL_MANT_DIG.
-
- Some terminology: the *rounding bit* of v is the 1st bit of v that
- will be rounded away (bit n - DBL_MANT_DIG - 1); the *parity bit*
- is the bit immediately above. The round-half-to-even rule says
- that we round up if the rounding bit is set, unless v is exactly
- halfway between two floats and the parity bit is zero.
-
- Write d[0] ... d[m] for the digits of v, least to most significant.
- Let rnd_bit be the index of the rounding bit, and rnd_digit the
- index of the PyLong digit containing the rounding bit. Then the
- bits of the digit d[rnd_digit] look something like:
-
- rounding bit
- |
- v
- msb -> sssssrttttttttt <- lsb
- ^
- |
- parity bit
-
- where 's' represents a 'significant bit' that will be included in
- the mantissa of the result, 'r' is the rounding bit, and 't'
- represents a 'trailing bit' following the rounding bit. Note that
- if the rounding bit is at the top of d[rnd_digit] then the parity
- bit will be the lsb of d[rnd_digit+1]. If we set
-
- lsb = 1 << (rnd_bit % PyLong_SHIFT)
-
- then d[rnd_digit] & (PyLong_BASE - 2*lsb) selects just the
- significant bits of d[rnd_digit], d[rnd_digit] & (lsb-1) gets the
- trailing bits, and d[rnd_digit] & lsb gives the rounding bit.
-
- We initialize the double x to the integer given by digits
- d[rnd_digit:m-1], but with the rounding bit and trailing bits of
- d[rnd_digit] masked out. So the value of x comes from the top
- DBL_MANT_DIG bits of v, multiplied by 2*lsb. Note that in the loop
- that produces x, all floating-point operations are exact (assuming
- that FLT_RADIX==2). Now if we're rounding down, the value we want
- to return is simply
-
- x * 2**(PyLong_SHIFT * rnd_digit).
-
- and if we're rounding up, it's
-
- (x + 2*lsb) * 2**(PyLong_SHIFT * rnd_digit).
-
- Under the round-half-to-even rule, we round up if, and only
- if, the rounding bit is set *and* at least one of the
- following three conditions is satisfied:
-
- (1) the parity bit is set, or
- (2) at least one of the trailing bits of d[rnd_digit] is set, or
- (3) at least one of the digits d[i], 0 <= i < rnd_digit
- is nonzero.
-
- Finally, we have to worry about overflow. If v >= 2**DBL_MAX_EXP,
- or equivalently n > DBL_MAX_EXP, then overflow occurs. If v <
- 2**DBL_MAX_EXP then we're usually safe, but there's a corner case
- to consider: if v is very close to 2**DBL_MAX_EXP then it's
- possible that v is rounded up to exactly 2**DBL_MAX_EXP, and then
- again overflow occurs.
- */
-
- if (Py_SIZE(v) == 0)
- return 0.0;
- m = ABS(Py_SIZE(v)) - 1;
- d = v->ob_digit;
- assert(d[m]); /* v should be normalized */
-
- /* fast path for case where 0 < abs(v) < 2**DBL_MANT_DIG */
- if (m < DBL_MANT_DIG / PyLong_SHIFT ||
- (m == DBL_MANT_DIG / PyLong_SHIFT &&
- d[m] < (digit)1 << DBL_MANT_DIG%PyLong_SHIFT)) {
- x = d[m];
- while (--m >= 0)
- x = x*PyLong_BASE + d[m];
- return Py_SIZE(v) < 0 ? -x : x;
- }
-
- /* if m is huge then overflow immediately; otherwise, compute the
- number of bits n in v. The condition below implies n (= #bits) >=
- m * PyLong_SHIFT + 1 > DBL_MAX_EXP, hence v >= 2**DBL_MAX_EXP. */
- if (m > (DBL_MAX_EXP-1)/PyLong_SHIFT)
- goto overflow;
- n = m * PyLong_SHIFT + bits_in_digit(d[m]);
- if (n > DBL_MAX_EXP)
- goto overflow;
-
- /* find location of rounding bit */
- assert(n > DBL_MANT_DIG); /* dealt with |v| < 2**DBL_MANT_DIG above */
- rnd_bit = n - DBL_MANT_DIG - 1;
- rnd_digit = rnd_bit/PyLong_SHIFT;
- lsb = (digit)1 << (rnd_bit%PyLong_SHIFT);
-
- /* Get top DBL_MANT_DIG bits of v. Assumes PyLong_SHIFT <
- DBL_MANT_DIG, so we'll need bits from at least 2 digits of v. */
- x = d[m];
- assert(m > rnd_digit);
- while (--m > rnd_digit)
- x = x*PyLong_BASE + d[m];
- x = x*PyLong_BASE + (d[m] & (PyLong_BASE-2*lsb));
-
- /* decide whether to round up, using round-half-to-even */
- assert(m == rnd_digit);
- if (d[m] & lsb) { /* if (rounding bit is set) */
- digit parity_bit;
- if (lsb == PyLong_BASE/2)
- parity_bit = d[m+1] & 1;
- else
- parity_bit = d[m] & 2*lsb;
- if (parity_bit)
- round_up = 1;
- else if (d[m] & (lsb-1))
- round_up = 1;
- else {
- while (--m >= 0) {
- if (d[m]) {
- round_up = 1;
- break;
- }
- }
- }
- }
-
- /* and round up if necessary */
- if (round_up) {
- x += 2*lsb;
- if (n == DBL_MAX_EXP &&
- x == ldexp((double)(2*lsb), DBL_MANT_DIG)) {
- /* overflow corner case */
- goto overflow;
- }
- }
-
- /* shift, adjust for sign, and return */
- x = ldexp(x, rnd_digit*PyLong_SHIFT);
- return Py_SIZE(v) < 0 ? -x : x;
+ PyLongObject *v = (PyLongObject *)vv;
+ Py_ssize_t rnd_digit, rnd_bit, m, n;
+ digit lsb, *d;
+ int round_up = 0;
+ double x;
+
+ if (vv == NULL || !PyLong_Check(vv)) {
+ PyErr_BadInternalCall();
+ return -1.0;
+ }
+
+ /* Notes on the method: for simplicity, assume v is positive and >=
+ 2**DBL_MANT_DIG. (For negative v we just ignore the sign until the
+ end; for small v no rounding is necessary.) Write n for the number
+ of bits in v, so that 2**(n-1) <= v < 2**n, and n > DBL_MANT_DIG.
+
+ Some terminology: the *rounding bit* of v is the 1st bit of v that
+ will be rounded away (bit n - DBL_MANT_DIG - 1); the *parity bit*
+ is the bit immediately above. The round-half-to-even rule says
+ that we round up if the rounding bit is set, unless v is exactly
+ halfway between two floats and the parity bit is zero.
+
+ Write d[0] ... d[m] for the digits of v, least to most significant.
+ Let rnd_bit be the index of the rounding bit, and rnd_digit the
+ index of the PyLong digit containing the rounding bit. Then the
+ bits of the digit d[rnd_digit] look something like:
+
+ rounding bit
+ |
+ v
+ msb -> sssssrttttttttt <- lsb
+ ^
+ |
+ parity bit
+
+ where 's' represents a 'significant bit' that will be included in
+ the mantissa of the result, 'r' is the rounding bit, and 't'
+ represents a 'trailing bit' following the rounding bit. Note that
+ if the rounding bit is at the top of d[rnd_digit] then the parity
+ bit will be the lsb of d[rnd_digit+1]. If we set
+
+ lsb = 1 << (rnd_bit % PyLong_SHIFT)
+
+ then d[rnd_digit] & (PyLong_BASE - 2*lsb) selects just the
+ significant bits of d[rnd_digit], d[rnd_digit] & (lsb-1) gets the
+ trailing bits, and d[rnd_digit] & lsb gives the rounding bit.
+
+ We initialize the double x to the integer given by digits
+ d[rnd_digit:m-1], but with the rounding bit and trailing bits of
+ d[rnd_digit] masked out. So the value of x comes from the top
+ DBL_MANT_DIG bits of v, multiplied by 2*lsb. Note that in the loop
+ that produces x, all floating-point operations are exact (assuming
+ that FLT_RADIX==2). Now if we're rounding down, the value we want
+ to return is simply
+
+ x * 2**(PyLong_SHIFT * rnd_digit).
+
+ and if we're rounding up, it's
+
+ (x + 2*lsb) * 2**(PyLong_SHIFT * rnd_digit).
+
+ Under the round-half-to-even rule, we round up if, and only
+ if, the rounding bit is set *and* at least one of the
+ following three conditions is satisfied:
+
+ (1) the parity bit is set, or
+ (2) at least one of the trailing bits of d[rnd_digit] is set, or
+ (3) at least one of the digits d[i], 0 <= i < rnd_digit
+ is nonzero.
+
+ Finally, we have to worry about overflow. If v >= 2**DBL_MAX_EXP,
+ or equivalently n > DBL_MAX_EXP, then overflow occurs. If v <
+ 2**DBL_MAX_EXP then we're usually safe, but there's a corner case
+ to consider: if v is very close to 2**DBL_MAX_EXP then it's
+ possible that v is rounded up to exactly 2**DBL_MAX_EXP, and then
+ again overflow occurs.
+ */
+
+ if (Py_SIZE(v) == 0)
+ return 0.0;
+ m = ABS(Py_SIZE(v)) - 1;
+ d = v->ob_digit;
+ assert(d[m]); /* v should be normalized */
+
+ /* fast path for case where 0 < abs(v) < 2**DBL_MANT_DIG */
+ if (m < DBL_MANT_DIG / PyLong_SHIFT ||
+ (m == DBL_MANT_DIG / PyLong_SHIFT &&
+ d[m] < (digit)1 << DBL_MANT_DIG%PyLong_SHIFT)) {
+ x = d[m];
+ while (--m >= 0)
+ x = x*PyLong_BASE + d[m];
+ return Py_SIZE(v) < 0 ? -x : x;
+ }
+
+ /* if m is huge then overflow immediately; otherwise, compute the
+ number of bits n in v. The condition below implies n (= #bits) >=
+ m * PyLong_SHIFT + 1 > DBL_MAX_EXP, hence v >= 2**DBL_MAX_EXP. */
+ if (m > (DBL_MAX_EXP-1)/PyLong_SHIFT)
+ goto overflow;
+ n = m * PyLong_SHIFT + bits_in_digit(d[m]);
+ if (n > DBL_MAX_EXP)
+ goto overflow;
+
+ /* find location of rounding bit */
+ assert(n > DBL_MANT_DIG); /* dealt with |v| < 2**DBL_MANT_DIG above */
+ rnd_bit = n - DBL_MANT_DIG - 1;
+ rnd_digit = rnd_bit/PyLong_SHIFT;
+ lsb = (digit)1 << (rnd_bit%PyLong_SHIFT);
+
+ /* Get top DBL_MANT_DIG bits of v. Assumes PyLong_SHIFT <
+ DBL_MANT_DIG, so we'll need bits from at least 2 digits of v. */
+ x = d[m];
+ assert(m > rnd_digit);
+ while (--m > rnd_digit)
+ x = x*PyLong_BASE + d[m];
+ x = x*PyLong_BASE + (d[m] & (PyLong_BASE-2*lsb));
+
+ /* decide whether to round up, using round-half-to-even */
+ assert(m == rnd_digit);
+ if (d[m] & lsb) { /* if (rounding bit is set) */
+ digit parity_bit;
+ if (lsb == PyLong_BASE/2)
+ parity_bit = d[m+1] & 1;
+ else
+ parity_bit = d[m] & 2*lsb;
+ if (parity_bit)
+ round_up = 1;
+ else if (d[m] & (lsb-1))
+ round_up = 1;
+ else {
+ while (--m >= 0) {
+ if (d[m]) {
+ round_up = 1;
+ break;
+ }
+ }
+ }
+ }
+
+ /* and round up if necessary */
+ if (round_up) {
+ x += 2*lsb;
+ if (n == DBL_MAX_EXP &&
+ x == ldexp((double)(2*lsb), DBL_MANT_DIG)) {
+ /* overflow corner case */
+ goto overflow;
+ }
+ }
+
+ /* shift, adjust for sign, and return */
+ x = ldexp(x, rnd_digit*PyLong_SHIFT);
+ return Py_SIZE(v) < 0 ? -x : x;
overflow:
- PyErr_SetString(PyExc_OverflowError,
- "Python int too large to convert to C double");
- return -1.0;
+ PyErr_SetString(PyExc_OverflowError,
+ "Python int too large to convert to C double");
+ return -1.0;
}
/* Create a new long (or int) object from a C pointer */
@@ -1157,10 +1157,10 @@ PyLong_FromVoidPtr(void *p)
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
# error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
#endif
- /* special-case null pointer */
- if (!p)
- return PyLong_FromLong(0);
- return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p);
+ /* special-case null pointer */
+ if (!p)
+ return PyLong_FromLong(0);
+ return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p);
}
@@ -1169,17 +1169,17 @@ PyLong_FromVoidPtr(void *p)
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"
- */
+ /* 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;
+ long x;
- if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
- x = PyLong_AsLong(vv);
- else
- x = PyLong_AsUnsignedLong(vv);
+ if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
+ x = PyLong_AsLong(vv);
+ else
+ x = PyLong_AsUnsignedLong(vv);
#else
#ifndef HAVE_LONG_LONG
@@ -1188,18 +1188,18 @@ PyLong_AsVoidPtr(PyObject *vv)
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
# error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
#endif
- PY_LONG_LONG x;
+ PY_LONG_LONG x;
- if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
- x = PyLong_AsLongLong(vv);
- else
- x = PyLong_AsUnsignedLongLong(vv);
+ if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
+ x = PyLong_AsLongLong(vv);
+ else
+ x = PyLong_AsUnsignedLongLong(vv);
#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
- if (x == -1 && PyErr_Occurred())
- return NULL;
- return (void *)x;
+ if (x == -1 && PyErr_Occurred())
+ return NULL;
+ return (void *)x;
}
#ifdef HAVE_LONG_LONG
@@ -1215,43 +1215,43 @@ PyLong_AsVoidPtr(PyObject *vv)
PyObject *
PyLong_FromLongLong(PY_LONG_LONG ival)
{
- PyLongObject *v;
- unsigned PY_LONG_LONG abs_ival;
- unsigned PY_LONG_LONG t; /* unsigned so >> doesn't propagate sign bit */
- int ndigits = 0;
- int negative = 0;
-
- CHECK_SMALL_INT(ival);
- if (ival < 0) {
- /* avoid signed overflow on negation; see comments
- in PyLong_FromLong above. */
- abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;
- negative = 1;
- }
- else {
- abs_ival = (unsigned PY_LONG_LONG)ival;
- }
-
- /* Count the number of Python digits.
- 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;
- Py_SIZE(v) = negative ? -ndigits : ndigits;
- t = abs_ival;
- while (t) {
- *p++ = (digit)(t & PyLong_MASK);
- t >>= PyLong_SHIFT;
- }
- }
- return (PyObject *)v;
+ PyLongObject *v;
+ unsigned PY_LONG_LONG abs_ival;
+ unsigned PY_LONG_LONG t; /* unsigned so >> doesn't propagate sign bit */
+ int ndigits = 0;
+ int negative = 0;
+
+ CHECK_SMALL_INT(ival);
+ if (ival < 0) {
+ /* avoid signed overflow on negation; see comments
+ in PyLong_FromLong above. */
+ abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;
+ negative = 1;
+ }
+ else {
+ abs_ival = (unsigned PY_LONG_LONG)ival;
+ }
+
+ /* Count the number of Python digits.
+ 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;
+ 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. */
@@ -1259,28 +1259,28 @@ PyLong_FromLongLong(PY_LONG_LONG ival)
PyObject *
PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
{
- PyLongObject *v;
- unsigned PY_LONG_LONG t;
- int ndigits = 0;
-
- if (ival < PyLong_BASE)
- return PyLong_FromLong((long)ival);
- /* 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;
+ PyLongObject *v;
+ unsigned PY_LONG_LONG t;
+ int ndigits = 0;
+
+ if (ival < PyLong_BASE)
+ return PyLong_FromLong((long)ival);
+ /* 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. */
@@ -1288,39 +1288,39 @@ PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
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;
-
- CHECK_SMALL_INT(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_SIZE(v) = negative ? -ndigits : ndigits;
- t = abs_ival;
- while (t) {
- *p++ = (digit)(t & PyLong_MASK);
- t >>= PyLong_SHIFT;
- }
- }
- return (PyObject *)v;
+ PyLongObject *v;
+ size_t abs_ival;
+ size_t t; /* unsigned so >> doesn't propagate sign bit */
+ int ndigits = 0;
+ int negative = 0;
+
+ CHECK_SMALL_INT(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_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 size_t. */
@@ -1328,28 +1328,28 @@ PyLong_FromSsize_t(Py_ssize_t ival)
PyObject *
PyLong_FromSize_t(size_t ival)
{
- PyLongObject *v;
- size_t t;
- int ndigits = 0;
-
- if (ival < PyLong_BASE)
- return PyLong_FromLong((long)ival);
- /* Count the number of Python digits. */
- t = 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;
+ PyLongObject *v;
+ size_t t;
+ int ndigits = 0;
+
+ if (ival < PyLong_BASE)
+ return PyLong_FromLong((long)ival);
+ /* Count the number of Python digits. */
+ t = 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;
}
/* Get a C PY_LONG_LONG int from a long int object.
@@ -1358,51 +1358,51 @@ PyLong_FromSize_t(size_t ival)
PY_LONG_LONG
PyLong_AsLongLong(PyObject *vv)
{
- PyLongObject *v;
- 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 ((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 (PyLong_Check(io)) {
- bytes = PyLong_AsLongLong(io);
- Py_DECREF(io);
- return bytes;
- }
- Py_DECREF(io);
- PyErr_SetString(PyExc_TypeError, "integer conversion failed");
- return -1;
- }
-
- v = (PyLongObject*)vv;
- switch(Py_SIZE(v)) {
- case -1: return -(sdigit)v->ob_digit[0];
- case 0: return 0;
- case 1: return v->ob_digit[0];
- }
- 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;
+ PyLongObject *v;
+ 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 ((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 (PyLong_Check(io)) {
+ bytes = PyLong_AsLongLong(io);
+ Py_DECREF(io);
+ return bytes;
+ }
+ Py_DECREF(io);
+ PyErr_SetString(PyExc_TypeError, "integer conversion failed");
+ return -1;
+ }
+
+ v = (PyLongObject*)vv;
+ switch(Py_SIZE(v)) {
+ case -1: return -(sdigit)v->ob_digit[0];
+ case 0: return 0;
+ case 1: return v->ob_digit[0];
+ }
+ 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.
@@ -1411,31 +1411,31 @@ PyLong_AsLongLong(PyObject *vv)
unsigned PY_LONG_LONG
PyLong_AsUnsignedLongLong(PyObject *vv)
{
- PyLongObject *v;
- unsigned PY_LONG_LONG bytes;
- int one = 1;
- int res;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return (unsigned PY_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, 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;
+ PyLongObject *v;
+ unsigned PY_LONG_LONG bytes;
+ int one = 1;
+ int res;
+
+ if (vv == NULL || !PyLong_Check(vv)) {
+ PyErr_BadInternalCall();
+ return (unsigned PY_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, 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.
@@ -1444,95 +1444,95 @@ PyLong_AsUnsignedLongLong(PyObject *vv)
static 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;
- 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 << PyLong_SHIFT) + v->ob_digit[i];
- }
- return x * sign;
+ 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;
+ 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 << PyLong_SHIFT) + v->ob_digit[i];
+ }
+ return x * sign;
}
unsigned PY_LONG_LONG
PyLong_AsUnsignedLongLongMask(register PyObject *op)
{
- PyNumberMethods *nb;
- PyLongObject *lo;
- unsigned PY_LONG_LONG val;
-
- if (op && PyLong_Check(op))
- return _PyLong_AsUnsignedLongLongMask(op);
-
- if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
- nb->nb_int == NULL) {
- PyErr_SetString(PyExc_TypeError, "an integer is required");
- return (unsigned PY_LONG_LONG)-1;
- }
-
- lo = (PyLongObject*) (*nb->nb_int) (op);
- if (lo == NULL)
- return (unsigned PY_LONG_LONG)-1;
- if (PyLong_Check(lo)) {
- val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
- Py_DECREF(lo);
- if (PyErr_Occurred())
- return (unsigned PY_LONG_LONG)-1;
- return val;
- }
- else
- {
- Py_DECREF(lo);
- PyErr_SetString(PyExc_TypeError,
- "nb_int should return int object");
- return (unsigned PY_LONG_LONG)-1;
- }
+ PyNumberMethods *nb;
+ PyLongObject *lo;
+ unsigned PY_LONG_LONG val;
+
+ if (op && PyLong_Check(op))
+ return _PyLong_AsUnsignedLongLongMask(op);
+
+ if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
+ nb->nb_int == NULL) {
+ PyErr_SetString(PyExc_TypeError, "an integer is required");
+ return (unsigned PY_LONG_LONG)-1;
+ }
+
+ lo = (PyLongObject*) (*nb->nb_int) (op);
+ if (lo == NULL)
+ return (unsigned PY_LONG_LONG)-1;
+ if (PyLong_Check(lo)) {
+ val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
+ Py_DECREF(lo);
+ if (PyErr_Occurred())
+ return (unsigned PY_LONG_LONG)-1;
+ return val;
+ }
+ else
+ {
+ Py_DECREF(lo);
+ PyErr_SetString(PyExc_TypeError,
+ "nb_int should return int object");
+ return (unsigned PY_LONG_LONG)-1;
+ }
}
#undef IS_LITTLE_ENDIAN
#endif /* HAVE_LONG_LONG */
#define CHECK_BINOP(v,w) \
- if (!PyLong_Check(v) || !PyLong_Check(w)) { \
- Py_INCREF(Py_NotImplemented); \
- return Py_NotImplemented; \
- }
+ if (!PyLong_Check(v) || !PyLong_Check(w)) { \
+ Py_INCREF(Py_NotImplemented); \
+ return Py_NotImplemented; \
+ }
/* bits_in_digit(d) returns the unique integer k such that 2**(k-1) <= d <
2**k if d is nonzero, else 0. */
static const unsigned char BitLengthTable[32] = {
- 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
+ 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
};
static int
bits_in_digit(digit d)
{
- int d_bits = 0;
- while (d >= 32) {
- d_bits += 6;
- d >>= 6;
- }
- d_bits += (int)BitLengthTable[d];
- return d_bits;
+ int d_bits = 0;
+ while (d >= 32) {
+ d_bits += 6;
+ d >>= 6;
+ }
+ d_bits += (int)BitLengthTable[d];
+ return d_bits;
}
/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
@@ -1542,23 +1542,23 @@ bits_in_digit(digit d)
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;
+ 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]
@@ -1568,23 +1568,23 @@ v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
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;
+ 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 <= d < PyLong_SHIFT. Put
@@ -1593,16 +1593,16 @@ v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
static digit
v_lshift(digit *z, digit *a, Py_ssize_t m, int d)
{
- Py_ssize_t i;
- digit carry = 0;
-
- assert(0 <= d && d < PyLong_SHIFT);
- for (i=0; i < m; i++) {
- twodigits acc = (twodigits)a[i] << d | carry;
- z[i] = (digit)acc & PyLong_MASK;
- carry = (digit)(acc >> PyLong_SHIFT);
- }
- return carry;
+ Py_ssize_t i;
+ digit carry = 0;
+
+ assert(0 <= d && d < PyLong_SHIFT);
+ for (i=0; i < m; i++) {
+ twodigits acc = (twodigits)a[i] << d | carry;
+ z[i] = (digit)acc & PyLong_MASK;
+ carry = (digit)(acc >> PyLong_SHIFT);
+ }
+ return carry;
}
/* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put
@@ -1611,17 +1611,17 @@ v_lshift(digit *z, digit *a, Py_ssize_t m, int d)
static digit
v_rshift(digit *z, digit *a, Py_ssize_t m, int d)
{
- Py_ssize_t i;
- digit carry = 0;
- digit mask = ((digit)1 << d) - 1U;
-
- assert(0 <= d && d < PyLong_SHIFT);
- for (i=m; i-- > 0;) {
- twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i];
- carry = (digit)acc & mask;
- z[i] = (digit)(acc >> d);
- }
- return carry;
+ Py_ssize_t i;
+ digit carry = 0;
+ digit mask = ((digit)1 << d) - 1U;
+
+ assert(0 <= d && d < PyLong_SHIFT);
+ for (i=m; i-- > 0;) {
+ twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i];
+ carry = (digit)acc & mask;
+ z[i] = (digit)(acc >> d);
+ }
+ return carry;
}
/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
@@ -1633,18 +1633,18 @@ v_rshift(digit *z, digit *a, Py_ssize_t m, int d)
static digit
inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
{
- twodigits rem = 0;
-
- assert(n > 0 && n <= PyLong_MASK);
- pin += size;
- pout += size;
- while (--size >= 0) {
- digit hi;
- rem = (rem << PyLong_SHIFT) + *--pin;
- *--pout = hi = (digit)(rem / n);
- rem -= (twodigits)hi * n;
- }
- return (digit)rem;
+ twodigits rem = 0;
+
+ assert(n > 0 && n <= PyLong_MASK);
+ pin += size;
+ pout += size;
+ while (--size >= 0) {
+ digit hi;
+ rem = (rem << PyLong_SHIFT) + *--pin;
+ *--pout = hi = (digit)(rem / n);
+ rem -= (twodigits)hi * n;
+ }
+ return (digit)rem;
}
/* Divide a long integer by a digit, returning both the quotient
@@ -1654,15 +1654,15 @@ inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
static PyLongObject *
divrem1(PyLongObject *a, digit n, digit *prem)
{
- const Py_ssize_t size = ABS(Py_SIZE(a));
- PyLongObject *z;
-
- assert(n > 0 && n <= PyLong_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);
+ const Py_ssize_t size = ABS(Py_SIZE(a));
+ PyLongObject *z;
+
+ assert(n > 0 && n <= PyLong_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.
@@ -1672,163 +1672,163 @@ divrem1(PyLongObject *a, digit n, digit *prem)
PyObject *
_PyLong_Format(PyObject *aa, int base)
{
- register PyLongObject *a = (PyLongObject *)aa;
- PyObject *str;
- Py_ssize_t i, sz;
- Py_ssize_t size_a;
- Py_UNICODE *p;
- int bits;
- char sign = '\0';
-
- if (a == NULL || !PyLong_Check(a)) {
- PyErr_BadInternalCall();
- return NULL;
- }
- assert(base >= 2 && base <= 36);
- size_a = ABS(Py_SIZE(a));
-
- /* Compute a rough upper bound for the length of the string */
- i = base;
- bits = 0;
- while (i > 1) {
- ++bits;
- i >>= 1;
- }
- i = 5;
- /* ensure we don't get signed overflow in sz calculation */
- if (size_a > (PY_SSIZE_T_MAX - i) / PyLong_SHIFT) {
- PyErr_SetString(PyExc_OverflowError,
- "int is too large to format");
- return NULL;
- }
- sz = i + 1 + (size_a * PyLong_SHIFT - 1) / bits;
- assert(sz >= 0);
- str = PyUnicode_FromUnicode(NULL, sz);
- if (str == NULL)
- return NULL;
- p = PyUnicode_AS_UNICODE(str) + sz;
- *p = '\0';
- if (Py_SIZE(a) < 0)
- sign = '-';
-
- if (Py_SIZE(a) == 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] << accumbits;
- accumbits += PyLong_SHIFT;
- assert(accumbits >= basebits);
- do {
- char cdigit = (char)(accum & (base - 1));
- cdigit += (cdigit < 10) ? '0' : 'a'-10;
- assert(p > PyUnicode_AS_UNICODE(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 <- largest power of base that fits in a digit. */
- digit powbase = base; /* powbase == base ** power */
- int power = 1;
- for (;;) {
- twodigits newpow = powbase * (twodigits)base;
- if (newpow >> 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 > PyUnicode_AS_UNICODE(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 == 16) {
- *--p = 'x';
- *--p = '0';
- }
- else if (base == 8) {
- *--p = 'o';
- *--p = '0';
- }
- else if (base == 2) {
- *--p = 'b';
- *--p = '0';
- }
- else if (base != 10) {
- *--p = '#';
- *--p = '0' + base%10;
- if (base > 10)
- *--p = '0' + base/10;
- }
- if (sign)
- *--p = sign;
- if (p != PyUnicode_AS_UNICODE(str)) {
- Py_UNICODE *q = PyUnicode_AS_UNICODE(str);
- assert(p > q);
- do {
- } while ((*q++ = *p++) != '\0');
- q--;
- if (PyUnicode_Resize(&str,(Py_ssize_t) (q -
- PyUnicode_AS_UNICODE(str)))) {
- Py_DECREF(str);
- return NULL;
- }
- }
- return (PyObject *)str;
+ register PyLongObject *a = (PyLongObject *)aa;
+ PyObject *str;
+ Py_ssize_t i, sz;
+ Py_ssize_t size_a;
+ Py_UNICODE *p;
+ int bits;
+ char sign = '\0';
+
+ if (a == NULL || !PyLong_Check(a)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ assert(base >= 2 && base <= 36);
+ size_a = ABS(Py_SIZE(a));
+
+ /* Compute a rough upper bound for the length of the string */
+ i = base;
+ bits = 0;
+ while (i > 1) {
+ ++bits;
+ i >>= 1;
+ }
+ i = 5;
+ /* ensure we don't get signed overflow in sz calculation */
+ if (size_a > (PY_SSIZE_T_MAX - i) / PyLong_SHIFT) {
+ PyErr_SetString(PyExc_OverflowError,
+ "int is too large to format");
+ return NULL;
+ }
+ sz = i + 1 + (size_a * PyLong_SHIFT - 1) / bits;
+ assert(sz >= 0);
+ str = PyUnicode_FromUnicode(NULL, sz);
+ if (str == NULL)
+ return NULL;
+ p = PyUnicode_AS_UNICODE(str) + sz;
+ *p = '\0';
+ if (Py_SIZE(a) < 0)
+ sign = '-';
+
+ if (Py_SIZE(a) == 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] << accumbits;
+ accumbits += PyLong_SHIFT;
+ assert(accumbits >= basebits);
+ do {
+ char cdigit = (char)(accum & (base - 1));
+ cdigit += (cdigit < 10) ? '0' : 'a'-10;
+ assert(p > PyUnicode_AS_UNICODE(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 <- largest power of base that fits in a digit. */
+ digit powbase = base; /* powbase == base ** power */
+ int power = 1;
+ for (;;) {
+ twodigits newpow = powbase * (twodigits)base;
+ if (newpow >> 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 > PyUnicode_AS_UNICODE(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 == 16) {
+ *--p = 'x';
+ *--p = '0';
+ }
+ else if (base == 8) {
+ *--p = 'o';
+ *--p = '0';
+ }
+ else if (base == 2) {
+ *--p = 'b';
+ *--p = '0';
+ }
+ else if (base != 10) {
+ *--p = '#';
+ *--p = '0' + base%10;
+ if (base > 10)
+ *--p = '0' + base/10;
+ }
+ if (sign)
+ *--p = sign;
+ if (p != PyUnicode_AS_UNICODE(str)) {
+ Py_UNICODE *q = PyUnicode_AS_UNICODE(str);
+ assert(p > q);
+ do {
+ } while ((*q++ = *p++) != '\0');
+ q--;
+ if (PyUnicode_Resize(&str,(Py_ssize_t) (q -
+ PyUnicode_AS_UNICODE(str)))) {
+ Py_DECREF(str);
+ return NULL;
+ }
+ }
+ return (PyObject *)str;
}
/* Table of digit values for 8-bit string -> integer conversion.
@@ -1839,22 +1839,22 @@ _PyLong_Format(PyObject *aa, int base)
* 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,
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
+ 37, 37, 37, 37, 37, 37, 37, 37, 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
@@ -1866,111 +1866,111 @@ unsigned char _PyLong_DigitValue[256] = {
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 <= 32 && (base & (base - 1)) == 0);
- n = base;
- for (bits_per_char = -1; n; ++bits_per_char)
- n >>= 1;
- /* n <- total # of bits needed, while setting p to end-of-string */
- while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
- ++p;
- *str = p;
- /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
- n = (p - start) * bits_per_char + PyLong_SHIFT - 1;
- if (n / bits_per_char < p - start) {
- PyErr_SetString(PyExc_ValueError,
- "int string too large to convert");
- return NULL;
- }
- n = n / PyLong_SHIFT;
- z = _PyLong_New(n);
- if (z == NULL)
- return NULL;
- /* Read string from right, and fill in long 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 = (int)_PyLong_DigitValue[Py_CHARMASK(*p)];
- assert(k >= 0 && k < base);
- accum |= (twodigits)k << bits_in_accum;
- bits_in_accum += bits_per_char;
- if (bits_in_accum >= PyLong_SHIFT) {
- *pdigit++ = (digit)(accum & PyLong_MASK);
- assert(pdigit - z->ob_digit <= n);
- accum >>= PyLong_SHIFT;
- bits_in_accum -= PyLong_SHIFT;
- assert(bits_in_accum < PyLong_SHIFT);
- }
- }
- if (bits_in_accum) {
- assert(bits_in_accum <= PyLong_SHIFT);
- *pdigit++ = (digit)accum;
- assert(pdigit - z->ob_digit <= n);
- }
- while (pdigit - z->ob_digit < n)
- *pdigit++ = 0;
- return long_normalize(z);
+ 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 <= 32 && (base & (base - 1)) == 0);
+ n = base;
+ for (bits_per_char = -1; n; ++bits_per_char)
+ n >>= 1;
+ /* n <- total # of bits needed, while setting p to end-of-string */
+ while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
+ ++p;
+ *str = p;
+ /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
+ n = (p - start) * bits_per_char + PyLong_SHIFT - 1;
+ if (n / bits_per_char < p - start) {
+ PyErr_SetString(PyExc_ValueError,
+ "int string too large to convert");
+ return NULL;
+ }
+ n = n / PyLong_SHIFT;
+ z = _PyLong_New(n);
+ if (z == NULL)
+ return NULL;
+ /* Read string from right, and fill in long 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 = (int)_PyLong_DigitValue[Py_CHARMASK(*p)];
+ assert(k >= 0 && k < base);
+ accum |= (twodigits)k << bits_in_accum;
+ bits_in_accum += bits_per_char;
+ if (bits_in_accum >= PyLong_SHIFT) {
+ *pdigit++ = (digit)(accum & PyLong_MASK);
+ assert(pdigit - z->ob_digit <= n);
+ accum >>= PyLong_SHIFT;
+ bits_in_accum -= PyLong_SHIFT;
+ assert(bits_in_accum < PyLong_SHIFT);
+ }
+ }
+ if (bits_in_accum) {
+ assert(bits_in_accum <= PyLong_SHIFT);
+ *pdigit++ = (digit)accum;
+ assert(pdigit - z->ob_digit <= n);
+ }
+ while (pdigit - z->ob_digit < n)
+ *pdigit++ = 0;
+ return long_normalize(z);
}
PyObject *
PyLong_FromString(char *str, char **pend, int base)
{
- int sign = 1, error_if_nonzero = 0;
- 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 <= 36");
- return NULL;
- }
- while (*str != '\0' && isspace(Py_CHARMASK(*str)))
- str++;
- if (*str == '+')
- ++str;
- else if (*str == '-') {
- ++str;
- sign = -1;
- }
- if (base == 0) {
- if (str[0] != '0')
- base = 10;
- else if (str[1] == 'x' || str[1] == 'X')
- base = 16;
- else if (str[1] == 'o' || str[1] == 'O')
- base = 8;
- else if (str[1] == 'b' || str[1] == 'B')
- base = 2;
- else {
- /* "old" (C-style) octal literal, now invalid.
- it might still be zero though */
- error_if_nonzero = 1;
- base = 10;
- }
- }
- if (str[0] == '0' &&
- ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
- (base == 8 && (str[1] == 'o' || str[1] == 'O')) ||
- (base == 2 && (str[1] == 'b' || str[1] == 'B'))))
- str += 2;
-
- start = str;
- if ((base & (base - 1)) == 0)
- z = long_from_binary_base(&str, base);
- else {
+ int sign = 1, error_if_nonzero = 0;
+ 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 <= 36");
+ return NULL;
+ }
+ while (*str != '\0' && isspace(Py_CHARMASK(*str)))
+ str++;
+ if (*str == '+')
+ ++str;
+ else if (*str == '-') {
+ ++str;
+ sign = -1;
+ }
+ if (base == 0) {
+ if (str[0] != '0')
+ base = 10;
+ else if (str[1] == 'x' || str[1] == 'X')
+ base = 16;
+ else if (str[1] == 'o' || str[1] == 'O')
+ base = 8;
+ else if (str[1] == 'b' || str[1] == 'B')
+ base = 2;
+ else {
+ /* "old" (C-style) octal literal, now invalid.
+ it might still be zero though */
+ error_if_nonzero = 1;
+ base = 10;
+ }
+ }
+ if (str[0] == '0' &&
+ ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
+ (base == 8 && (str[1] == 'o' || str[1] == 'O')) ||
+ (base == 2 && (str[1] == 'b' || str[1] == 'B'))))
+ str += 2;
+
+ start = str;
+ if ((base & (base - 1)) == 0)
+ z = long_from_binary_base(&str, base);
+ else {
/***
Binary bases can be converted in time linear in the number of digits, because
Python's representation base is binary. Other bases (including decimal!) use
@@ -2056,227 +2056,227 @@ that triggers it(!). Instead the code was tested by artificially allocating
just 1 digit at the start, so that the copying code was exercised for every
digit beyond the first.
***/
- register twodigits c; /* current input character */
- Py_ssize_t size_z;
- int i;
- int convwidth;
- twodigits convmultmax, convmult;
- digit *pz, *pzstop;
- char* scan;
-
- static double log_base_BASE[37] = {0.0e0,};
- static int convwidth_base[37] = {0,};
- static twodigits convmultmax_base[37] = {0,};
-
- if (log_base_BASE[base] == 0.0) {
- twodigits convmax = base;
- int i = 1;
-
- log_base_BASE[base] = log((double)base) /
- log((double)PyLong_BASE);
- for (;;) {
- twodigits next = convmax * base;
- if (next > PyLong_BASE)
- break;
- convmax = next;
- ++i;
- }
- convmultmax_base[base] = convmax;
- assert(i > 0);
- convwidth_base[base] = i;
- }
-
- /* Find length of the string of numeric characters. */
- scan = str;
- while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
- ++scan;
-
- /* Create a long object that can contain the largest possible
- * integer with this base and length. Note that there's no
- * need to initialize z->ob_digit -- no slot is read up before
- * being stored into.
- */
- size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
- /* Uncomment next line to test exceedingly rare copy code */
- /* size_z = 1; */
- assert(size_z > 0);
- z = _PyLong_New(size_z);
- if (z == NULL)
- return NULL;
- Py_SIZE(z) = 0;
-
- /* `convwidth` consecutive input digits are treated as a single
- * digit in base `convmultmax`.
- */
- convwidth = convwidth_base[base];
- convmultmax = convmultmax_base[base];
-
- /* Work ;-) */
- while (str < scan) {
- /* grab up to convwidth digits from the input string */
- c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
- for (i = 1; i < convwidth && str != scan; ++i, ++str) {
- c = (twodigits)(c * base +
- (int)_PyLong_DigitValue[Py_CHARMASK(*str)]);
- assert(c < PyLong_BASE);
- }
-
- convmult = convmultmax;
- /* Calculate the shift only if we couldn't get
- * convwidth digits.
- */
- if (i != convwidth) {
- convmult = base;
- for ( ; i > 1; --i)
- convmult *= base;
- }
-
- /* Multiply z by convmult, and add c. */
- pz = z->ob_digit;
- pzstop = pz + Py_SIZE(z);
- for (; pz < pzstop; ++pz) {
- c += (twodigits)*pz * convmult;
- *pz = (digit)(c & PyLong_MASK);
- c >>= PyLong_SHIFT;
- }
- /* carry off the current end? */
- if (c) {
- assert(c < PyLong_BASE);
- if (Py_SIZE(z) < size_z) {
- *pz = (digit)c;
- ++Py_SIZE(z);
- }
- else {
- PyLongObject *tmp;
- /* Extremely rare. Get more space. */
- assert(Py_SIZE(z) == size_z);
- tmp = _PyLong_New(size_z + 1);
- if (tmp == NULL) {
- Py_DECREF(z);
- return NULL;
- }
- memcpy(tmp->ob_digit,
- z->ob_digit,
- sizeof(digit) * size_z);
- Py_DECREF(z);
- z = tmp;
- z->ob_digit[size_z] = (digit)c;
- ++size_z;
- }
- }
- }
- }
- if (z == NULL)
- return NULL;
- if (error_if_nonzero) {
- /* reset the base to 0, else the exception message
- doesn't make too much sense */
- base = 0;
- if (Py_SIZE(z) != 0)
- goto onError;
- /* there might still be other problems, therefore base
- remains zero here for the same reason */
- }
- if (str == start)
- goto onError;
- if (sign < 0)
- Py_SIZE(z) = -(Py_SIZE(z));
- while (*str && isspace(Py_CHARMASK(*str)))
- str++;
- if (*str != '\0')
- goto onError;
- if (pend)
- *pend = str;
- long_normalize(z);
- return (PyObject *) maybe_small_long(z);
+ register twodigits c; /* current input character */
+ Py_ssize_t size_z;
+ int i;
+ int convwidth;
+ twodigits convmultmax, convmult;
+ digit *pz, *pzstop;
+ char* scan;
+
+ static double log_base_BASE[37] = {0.0e0,};
+ static int convwidth_base[37] = {0,};
+ static twodigits convmultmax_base[37] = {0,};
+
+ if (log_base_BASE[base] == 0.0) {
+ twodigits convmax = base;
+ int i = 1;
+
+ log_base_BASE[base] = log((double)base) /
+ log((double)PyLong_BASE);
+ for (;;) {
+ twodigits next = convmax * base;
+ if (next > PyLong_BASE)
+ break;
+ convmax = next;
+ ++i;
+ }
+ convmultmax_base[base] = convmax;
+ assert(i > 0);
+ convwidth_base[base] = i;
+ }
+
+ /* Find length of the string of numeric characters. */
+ scan = str;
+ while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
+ ++scan;
+
+ /* Create a long object that can contain the largest possible
+ * integer with this base and length. Note that there's no
+ * need to initialize z->ob_digit -- no slot is read up before
+ * being stored into.
+ */
+ size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
+ /* Uncomment next line to test exceedingly rare copy code */
+ /* size_z = 1; */
+ assert(size_z > 0);
+ z = _PyLong_New(size_z);
+ if (z == NULL)
+ return NULL;
+ Py_SIZE(z) = 0;
+
+ /* `convwidth` consecutive input digits are treated as a single
+ * digit in base `convmultmax`.
+ */
+ convwidth = convwidth_base[base];
+ convmultmax = convmultmax_base[base];
+
+ /* Work ;-) */
+ while (str < scan) {
+ /* grab up to convwidth digits from the input string */
+ c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
+ for (i = 1; i < convwidth && str != scan; ++i, ++str) {
+ c = (twodigits)(c * base +
+ (int)_PyLong_DigitValue[Py_CHARMASK(*str)]);
+ assert(c < PyLong_BASE);
+ }
+
+ convmult = convmultmax;
+ /* Calculate the shift only if we couldn't get
+ * convwidth digits.
+ */
+ if (i != convwidth) {
+ convmult = base;
+ for ( ; i > 1; --i)
+ convmult *= base;
+ }
+
+ /* Multiply z by convmult, and add c. */
+ pz = z->ob_digit;
+ pzstop = pz + Py_SIZE(z);
+ for (; pz < pzstop; ++pz) {
+ c += (twodigits)*pz * convmult;
+ *pz = (digit)(c & PyLong_MASK);
+ c >>= PyLong_SHIFT;
+ }
+ /* carry off the current end? */
+ if (c) {
+ assert(c < PyLong_BASE);
+ if (Py_SIZE(z) < size_z) {
+ *pz = (digit)c;
+ ++Py_SIZE(z);
+ }
+ else {
+ PyLongObject *tmp;
+ /* Extremely rare. Get more space. */
+ assert(Py_SIZE(z) == size_z);
+ tmp = _PyLong_New(size_z + 1);
+ if (tmp == NULL) {
+ Py_DECREF(z);
+ return NULL;
+ }
+ memcpy(tmp->ob_digit,
+ z->ob_digit,
+ sizeof(digit) * size_z);
+ Py_DECREF(z);
+ z = tmp;
+ z->ob_digit[size_z] = (digit)c;
+ ++size_z;
+ }
+ }
+ }
+ }
+ if (z == NULL)
+ return NULL;
+ if (error_if_nonzero) {
+ /* reset the base to 0, else the exception message
+ doesn't make too much sense */
+ base = 0;
+ if (Py_SIZE(z) != 0)
+ goto onError;
+ /* there might still be other problems, therefore base
+ remains zero here for the same reason */
+ }
+ if (str == start)
+ goto onError;
+ if (sign < 0)
+ Py_SIZE(z) = -(Py_SIZE(z));
+ while (*str && isspace(Py_CHARMASK(*str)))
+ str++;
+ if (*str != '\0')
+ goto onError;
+ if (pend)
+ *pend = str;
+ long_normalize(z);
+ return (PyObject *) maybe_small_long(z);
onError:
- Py_XDECREF(z);
- slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
- strobj = PyUnicode_FromStringAndSize(orig_str, slen);
- if (strobj == NULL)
- return NULL;
- PyErr_Format(PyExc_ValueError,
- "invalid literal for int() with base %d: %R",
- base, strobj);
- Py_DECREF(strobj);
- return NULL;
+ Py_XDECREF(z);
+ slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
+ strobj = PyUnicode_FromStringAndSize(orig_str, slen);
+ if (strobj == NULL)
+ return NULL;
+ PyErr_Format(PyExc_ValueError,
+ "invalid literal for int() with base %d: %R",
+ base, strobj);
+ Py_DECREF(strobj);
+ return NULL;
}
PyObject *
PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
{
- PyObject *result;
- char *buffer = (char *)PyMem_MALLOC(length+1);
-
- if (buffer == NULL)
- return NULL;
-
- if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
- PyMem_FREE(buffer);
- return NULL;
- }
- result = PyLong_FromString(buffer, NULL, base);
- PyMem_FREE(buffer);
- return result;
+ PyObject *result;
+ char *buffer = (char *)PyMem_MALLOC(length+1);
+
+ if (buffer == NULL)
+ return NULL;
+
+ if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
+ PyMem_FREE(buffer);
+ return NULL;
+ }
+ result = PyLong_FromString(buffer, NULL, base);
+ PyMem_FREE(buffer);
+ return result;
}
/* forward */
static PyLongObject *x_divrem
- (PyLongObject *, PyLongObject *, PyLongObject **);
+ (PyLongObject *, PyLongObject *, PyLongObject **);
static PyObject *long_long(PyObject *v);
/* Long division with remainder, top-level routine */
static int
long_divrem(PyLongObject *a, PyLongObject *b,
- PyLongObject **pdiv, PyLongObject **prem)
+ PyLongObject **pdiv, PyLongObject **prem)
{
- Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
- PyLongObject *z;
-
- if (size_b == 0) {
- PyErr_SetString(PyExc_ZeroDivisionError,
- "integer division or modulo by zero");
- return -1;
- }
- if (size_a < size_b ||
- (size_a == size_b &&
- a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
- /* |a| < |b|. */
- *pdiv = (PyLongObject*)PyLong_FromLong(0);
- if (*pdiv == NULL)
- return -1;
- Py_INCREF(a);
- *prem = (PyLongObject *) a;
- return 0;
- }
- if (size_b == 1) {
- digit rem = 0;
- z = divrem1(a, b->ob_digit[0], &rem);
- if (z == NULL)
- return -1;
- *prem = (PyLongObject *) PyLong_FromLong((long)rem);
- if (*prem == NULL) {
- Py_DECREF(z);
- return -1;
- }
- }
- else {
- z = x_divrem(a, b, prem);
- if (z == NULL)
- return -1;
- }
- /* Set the signs.
- The quotient z has the sign of a*b;
- the remainder r has the sign of a,
- so a = b*z + r. */
- if ((Py_SIZE(a) < 0) != (Py_SIZE(b) < 0))
- NEGATE(z);
- if (Py_SIZE(a) < 0 && Py_SIZE(*prem) != 0)
- NEGATE(*prem);
- *pdiv = maybe_small_long(z);
- return 0;
+ Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
+ PyLongObject *z;
+
+ if (size_b == 0) {
+ PyErr_SetString(PyExc_ZeroDivisionError,
+ "integer division or modulo by zero");
+ return -1;
+ }
+ if (size_a < size_b ||
+ (size_a == size_b &&
+ a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
+ /* |a| < |b|. */
+ *pdiv = (PyLongObject*)PyLong_FromLong(0);
+ if (*pdiv == NULL)
+ return -1;
+ Py_INCREF(a);
+ *prem = (PyLongObject *) a;
+ return 0;
+ }
+ if (size_b == 1) {
+ digit rem = 0;
+ z = divrem1(a, b->ob_digit[0], &rem);
+ if (z == NULL)
+ return -1;
+ *prem = (PyLongObject *) PyLong_FromLong((long)rem);
+ if (*prem == NULL) {
+ Py_DECREF(z);
+ return -1;
+ }
+ }
+ else {
+ z = x_divrem(a, b, prem);
+ if (z == NULL)
+ return -1;
+ }
+ /* Set the signs.
+ The quotient z has the sign of a*b;
+ the remainder r has the sign of a,
+ so a = b*z + r. */
+ if ((Py_SIZE(a) < 0) != (Py_SIZE(b) < 0))
+ NEGATE(z);
+ if (Py_SIZE(a) < 0 && Py_SIZE(*prem) != 0)
+ NEGATE(*prem);
+ *pdiv = maybe_small_long(z);
+ return 0;
}
/* Unsigned long division with remainder -- the algorithm. The arguments v1
@@ -2285,125 +2285,125 @@ long_divrem(PyLongObject *a, PyLongObject *b,
static PyLongObject *
x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
{
- PyLongObject *v, *w, *a;
- Py_ssize_t i, k, size_v, size_w;
- int d;
- digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;
- twodigits vv;
- sdigit zhi;
- stwodigits z;
-
- /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
- edn.), section 4.3.1, Algorithm D], except that we don't explicitly
- handle the special case when the initial estimate q for a quotient
- digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
- that won't overflow a digit. */
-
- /* allocate space; w will also be used to hold the final remainder */
- size_v = ABS(Py_SIZE(v1));
- size_w = ABS(Py_SIZE(w1));
- assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
- v = _PyLong_New(size_v+1);
- if (v == NULL) {
- *prem = NULL;
- return NULL;
- }
- w = _PyLong_New(size_w);
- if (w == NULL) {
- Py_DECREF(v);
- *prem = NULL;
- return NULL;
- }
-
- /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
- shift v1 left by the same amount. Results go into w and v. */
- d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);
- carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
- assert(carry == 0);
- carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
- if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {
- v->ob_digit[size_v] = carry;
- size_v++;
- }
-
- /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
- at most (and usually exactly) k = size_v - size_w digits. */
- k = size_v - size_w;
- assert(k >= 0);
- a = _PyLong_New(k);
- if (a == NULL) {
- Py_DECREF(w);
- Py_DECREF(v);
- *prem = NULL;
- return NULL;
- }
- v0 = v->ob_digit;
- w0 = w->ob_digit;
- wm1 = w0[size_w-1];
- wm2 = w0[size_w-2];
- for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {
- /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
- single-digit quotient q, remainder in vk[0:size_w]. */
-
- SIGCHECK({
- Py_DECREF(a);
- Py_DECREF(w);
- Py_DECREF(v);
- *prem = NULL;
- return NULL;
- })
-
- /* estimate quotient digit q; may overestimate by 1 (rare) */
- vtop = vk[size_w];
- assert(vtop <= wm1);
- vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1];
- q = (digit)(vv / wm1);
- r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */
- while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)
- | vk[size_w-2])) {
- --q;
- r += wm1;
- if (r >= PyLong_BASE)
- break;
- }
- assert(q <= PyLong_BASE);
-
- /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
- zhi = 0;
- for (i = 0; i < size_w; ++i) {
- /* invariants: -PyLong_BASE <= -q <= zhi <= 0;
- -PyLong_BASE * q <= z < PyLong_BASE */
- z = (sdigit)vk[i] + zhi -
- (stwodigits)q * (stwodigits)w0[i];
- vk[i] = (digit)z & PyLong_MASK;
- zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
- z, PyLong_SHIFT);
- }
-
- /* add w back if q was too large (this branch taken rarely) */
- assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0);
- if ((sdigit)vtop + zhi < 0) {
- carry = 0;
- for (i = 0; i < size_w; ++i) {
- carry += vk[i] + w0[i];
- vk[i] = carry & PyLong_MASK;
- carry >>= PyLong_SHIFT;
- }
- --q;
- }
-
- /* store quotient digit */
- assert(q < PyLong_BASE);
- *--ak = q;
- }
-
- /* unshift remainder; we reuse w to store the result */
- carry = v_rshift(w0, v0, size_w, d);
- assert(carry==0);
- Py_DECREF(v);
-
- *prem = long_normalize(w);
- return long_normalize(a);
+ PyLongObject *v, *w, *a;
+ Py_ssize_t i, k, size_v, size_w;
+ int d;
+ digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;
+ twodigits vv;
+ sdigit zhi;
+ stwodigits z;
+
+ /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
+ edn.), section 4.3.1, Algorithm D], except that we don't explicitly
+ handle the special case when the initial estimate q for a quotient
+ digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
+ that won't overflow a digit. */
+
+ /* allocate space; w will also be used to hold the final remainder */
+ size_v = ABS(Py_SIZE(v1));
+ size_w = ABS(Py_SIZE(w1));
+ assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
+ v = _PyLong_New(size_v+1);
+ if (v == NULL) {
+ *prem = NULL;
+ return NULL;
+ }
+ w = _PyLong_New(size_w);
+ if (w == NULL) {
+ Py_DECREF(v);
+ *prem = NULL;
+ return NULL;
+ }
+
+ /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
+ shift v1 left by the same amount. Results go into w and v. */
+ d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);
+ carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
+ assert(carry == 0);
+ carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
+ if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {
+ v->ob_digit[size_v] = carry;
+ size_v++;
+ }
+
+ /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
+ at most (and usually exactly) k = size_v - size_w digits. */
+ k = size_v - size_w;
+ assert(k >= 0);
+ a = _PyLong_New(k);
+ if (a == NULL) {
+ Py_DECREF(w);
+ Py_DECREF(v);
+ *prem = NULL;
+ return NULL;
+ }
+ v0 = v->ob_digit;
+ w0 = w->ob_digit;
+ wm1 = w0[size_w-1];
+ wm2 = w0[size_w-2];
+ for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {
+ /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
+ single-digit quotient q, remainder in vk[0:size_w]. */
+
+ SIGCHECK({
+ Py_DECREF(a);
+ Py_DECREF(w);
+ Py_DECREF(v);
+ *prem = NULL;
+ return NULL;
+ })
+
+ /* estimate quotient digit q; may overestimate by 1 (rare) */
+ vtop = vk[size_w];
+ assert(vtop <= wm1);
+ vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1];
+ q = (digit)(vv / wm1);
+ r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */
+ while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)
+ | vk[size_w-2])) {
+ --q;
+ r += wm1;
+ if (r >= PyLong_BASE)
+ break;
+ }
+ assert(q <= PyLong_BASE);
+
+ /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
+ zhi = 0;
+ for (i = 0; i < size_w; ++i) {
+ /* invariants: -PyLong_BASE <= -q <= zhi <= 0;
+ -PyLong_BASE * q <= z < PyLong_BASE */
+ z = (sdigit)vk[i] + zhi -
+ (stwodigits)q * (stwodigits)w0[i];
+ vk[i] = (digit)z & PyLong_MASK;
+ zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
+ z, PyLong_SHIFT);
+ }
+
+ /* add w back if q was too large (this branch taken rarely) */
+ assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0);
+ if ((sdigit)vtop + zhi < 0) {
+ carry = 0;
+ for (i = 0; i < size_w; ++i) {
+ carry += vk[i] + w0[i];
+ vk[i] = carry & PyLong_MASK;
+ carry >>= PyLong_SHIFT;
+ }
+ --q;
+ }
+
+ /* store quotient digit */
+ assert(q < PyLong_BASE);
+ *--ak = q;
+ }
+
+ /* unshift remainder; we reuse w to store the result */
+ carry = v_rshift(w0, v0, size_w, d);
+ assert(carry==0);
+ Py_DECREF(v);
+
+ *prem = long_normalize(w);
+ return long_normalize(a);
}
/* Methods */
@@ -2411,121 +2411,121 @@ x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
static void
long_dealloc(PyObject *v)
{
- Py_TYPE(v)->tp_free(v);
+ Py_TYPE(v)->tp_free(v);
}
static PyObject *
long_repr(PyObject *v)
{
- return _PyLong_Format(v, 10);
+ return _PyLong_Format(v, 10);
}
static int
long_compare(PyLongObject *a, PyLongObject *b)
{
- Py_ssize_t sign;
-
- if (Py_SIZE(a) != Py_SIZE(b)) {
- if (ABS(Py_SIZE(a)) == 0 && ABS(Py_SIZE(b)) == 0)
- sign = 0;
- else
- sign = Py_SIZE(a) - Py_SIZE(b);
- }
- else {
- Py_ssize_t i = ABS(Py_SIZE(a));
- while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
- ;
- if (i < 0)
- sign = 0;
- else {
- sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
- if (Py_SIZE(a) < 0)
- sign = -sign;
- }
- }
- return sign < 0 ? -1 : sign > 0 ? 1 : 0;
+ Py_ssize_t sign;
+
+ if (Py_SIZE(a) != Py_SIZE(b)) {
+ if (ABS(Py_SIZE(a)) == 0 && ABS(Py_SIZE(b)) == 0)
+ sign = 0;
+ else
+ sign = Py_SIZE(a) - Py_SIZE(b);
+ }
+ else {
+ Py_ssize_t i = ABS(Py_SIZE(a));
+ while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
+ ;
+ if (i < 0)
+ sign = 0;
+ else {
+ sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
+ if (Py_SIZE(a) < 0)
+ sign = -sign;
+ }
+ }
+ return sign < 0 ? -1 : sign > 0 ? 1 : 0;
}
#define TEST_COND(cond) \
- ((cond) ? Py_True : Py_False)
+ ((cond) ? Py_True : Py_False)
static PyObject *
long_richcompare(PyObject *self, PyObject *other, int op)
{
- int result;
- PyObject *v;
- CHECK_BINOP(self, other);
- if (self == other)
- result = 0;
- else
- result = long_compare((PyLongObject*)self, (PyLongObject*)other);
- /* Convert the return value to a Boolean */
- switch (op) {
- case Py_EQ:
- v = TEST_COND(result == 0);
- break;
- case Py_NE:
- v = TEST_COND(result != 0);
- break;
- case Py_LE:
- v = TEST_COND(result <= 0);
- break;
- case Py_GE:
- v = TEST_COND(result >= 0);
- break;
- case Py_LT:
- v = TEST_COND(result == -1);
- break;
- case Py_GT:
- v = TEST_COND(result == 1);
- break;
- default:
- PyErr_BadArgument();
- return NULL;
- }
- Py_INCREF(v);
- return v;
+ int result;
+ PyObject *v;
+ CHECK_BINOP(self, other);
+ if (self == other)
+ result = 0;
+ else
+ result = long_compare((PyLongObject*)self, (PyLongObject*)other);
+ /* Convert the return value to a Boolean */
+ switch (op) {
+ case Py_EQ:
+ v = TEST_COND(result == 0);
+ break;
+ case Py_NE:
+ v = TEST_COND(result != 0);
+ break;
+ case Py_LE:
+ v = TEST_COND(result <= 0);
+ break;
+ case Py_GE:
+ v = TEST_COND(result >= 0);
+ break;
+ case Py_LT:
+ v = TEST_COND(result == -1);
+ break;
+ case Py_GT:
+ v = TEST_COND(result == 1);
+ break;
+ default:
+ PyErr_BadArgument();
+ return NULL;
+ }
+ Py_INCREF(v);
+ return v;
}
static long
long_hash(PyLongObject *v)
{
- unsigned long x;
- Py_ssize_t i;
- int sign;
-
- /* This is designed so that Python ints and longs with the
- same value hash to the same value, otherwise comparisons
- of mapping keys will turn out weird */
- 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);
- }
- /* The following loop produces a C unsigned long x such that x is
- congruent to the absolute value of v modulo ULONG_MAX. The
- resulting x is nonzero if and only if v is. */
- while (--i >= 0) {
- /* Force a native long #-bits (32 or 64) circular shift */
- x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);
- x += v->ob_digit[i];
- /* If the addition above overflowed we compensate by
- incrementing. This preserves the value modulo
- ULONG_MAX. */
- if (x < v->ob_digit[i])
- x++;
- }
- x = x * sign;
- if (x == (unsigned long)-1)
- x = (unsigned long)-2;
- return (long)x;
+ unsigned long x;
+ Py_ssize_t i;
+ int sign;
+
+ /* This is designed so that Python ints and longs with the
+ same value hash to the same value, otherwise comparisons
+ of mapping keys will turn out weird */
+ 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);
+ }
+ /* The following loop produces a C unsigned long x such that x is
+ congruent to the absolute value of v modulo ULONG_MAX. The
+ resulting x is nonzero if and only if v is. */
+ while (--i >= 0) {
+ /* Force a native long #-bits (32 or 64) circular shift */
+ x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);
+ x += v->ob_digit[i];
+ /* If the addition above overflowed we compensate by
+ incrementing. This preserves the value modulo
+ ULONG_MAX. */
+ if (x < v->ob_digit[i])
+ x++;
+ }
+ x = x * sign;
+ if (x == (unsigned long)-1)
+ x = (unsigned long)-2;
+ return (long)x;
}
@@ -2534,33 +2534,33 @@ long_hash(PyLongObject *v)
static PyLongObject *
x_add(PyLongObject *a, PyLongObject *b)
{
- Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = 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);
+ Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = 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. */
@@ -2568,113 +2568,113 @@ x_add(PyLongObject *a, PyLongObject *b)
static PyLongObject *
x_sub(PyLongObject *a, PyLongObject *b)
{
- Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = 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)
- NEGATE(z);
- return long_normalize(z);
+ Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = 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)
+ NEGATE(z);
+ return long_normalize(z);
}
static PyObject *
long_add(PyLongObject *a, PyLongObject *b)
{
- PyLongObject *z;
-
- CHECK_BINOP(a, b);
-
- if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
- PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
- MEDIUM_VALUE(b));
- return result;
- }
- if (Py_SIZE(a) < 0) {
- if (Py_SIZE(b) < 0) {
- z = x_add(a, b);
- if (z != NULL && Py_SIZE(z) != 0)
- Py_SIZE(z) = -(Py_SIZE(z));
- }
- else
- z = x_sub(b, a);
- }
- else {
- if (Py_SIZE(b) < 0)
- z = x_sub(a, b);
- else
- z = x_add(a, b);
- }
- return (PyObject *)z;
+ PyLongObject *z;
+
+ CHECK_BINOP(a, b);
+
+ if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
+ PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
+ MEDIUM_VALUE(b));
+ return result;
+ }
+ if (Py_SIZE(a) < 0) {
+ if (Py_SIZE(b) < 0) {
+ z = x_add(a, b);
+ if (z != NULL && Py_SIZE(z) != 0)
+ Py_SIZE(z) = -(Py_SIZE(z));
+ }
+ else
+ z = x_sub(b, a);
+ }
+ else {
+ if (Py_SIZE(b) < 0)
+ z = x_sub(a, b);
+ else
+ z = x_add(a, b);
+ }
+ return (PyObject *)z;
}
static PyObject *
long_sub(PyLongObject *a, PyLongObject *b)
{
- PyLongObject *z;
-
- CHECK_BINOP(a, b);
-
- if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
- PyObject* r;
- r = PyLong_FromLong(MEDIUM_VALUE(a)-MEDIUM_VALUE(b));
- return r;
- }
- if (Py_SIZE(a) < 0) {
- if (Py_SIZE(b) < 0)
- z = x_sub(a, b);
- else
- z = x_add(a, b);
- if (z != NULL && Py_SIZE(z) != 0)
- Py_SIZE(z) = -(Py_SIZE(z));
- }
- else {
- if (Py_SIZE(b) < 0)
- z = x_add(a, b);
- else
- z = x_sub(a, b);
- }
- return (PyObject *)z;
+ PyLongObject *z;
+
+ CHECK_BINOP(a, b);
+
+ if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
+ PyObject* r;
+ r = PyLong_FromLong(MEDIUM_VALUE(a)-MEDIUM_VALUE(b));
+ return r;
+ }
+ if (Py_SIZE(a) < 0) {
+ if (Py_SIZE(b) < 0)
+ z = x_sub(a, b);
+ else
+ z = x_add(a, b);
+ if (z != NULL && Py_SIZE(z) != 0)
+ Py_SIZE(z) = -(Py_SIZE(z));
+ }
+ else {
+ if (Py_SIZE(b) < 0)
+ z = x_add(a, b);
+ else
+ z = x_sub(a, b);
+ }
+ return (PyObject *)z;
}
/* Grade school multiplication, ignoring the signs.
@@ -2683,85 +2683,85 @@ long_sub(PyLongObject *a, PyLongObject *b)
static PyLongObject *
x_mul(PyLongObject *a, PyLongObject *b)
{
- PyLongObject *z;
- Py_ssize_t size_a = ABS(Py_SIZE(a));
- Py_ssize_t size_b = ABS(Py_SIZE(b));
- Py_ssize_t i;
-
- z = _PyLong_New(size_a + size_b);
- if (z == NULL)
- return NULL;
-
- memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
- if (a == b) {
- /* Efficient squaring per HAC, Algorithm 14.16:
- * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
- * Gives slightly less than a 2x speedup when a == b,
- * via exploiting that each entry in the multiplication
- * pyramid appears twice (except for the size_a squares).
- */
- for (i = 0; i < size_a; ++i) {
- twodigits carry;
- twodigits f = a->ob_digit[i];
- digit *pz = z->ob_digit + (i << 1);
- digit *pa = a->ob_digit + i + 1;
- digit *paend = 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 <= PyLong_MASK);
-
- /* Now f is added in twice in each column of the
- * pyramid it appears. Same as adding f<<1 once.
- */
- f <<= 1;
- while (pa < paend) {
- carry += *pz + *pa++ * f;
- *pz++ = (digit)(carry & PyLong_MASK);
- carry >>= PyLong_SHIFT;
- assert(carry <= (PyLong_MASK << 1));
- }
- if (carry) {
- carry += *pz;
- *pz++ = (digit)(carry & PyLong_MASK);
- carry >>= PyLong_SHIFT;
- }
- if (carry)
- *pz += (digit)(carry & PyLong_MASK);
- assert((carry >> PyLong_SHIFT) == 0);
- }
- }
- else { /* a is not the same as b -- gradeschool long mult */
- for (i = 0; i < size_a; ++i) {
- twodigits carry = 0;
- twodigits f = a->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_MASK);
- }
- if (carry)
- *pz += (digit)(carry & PyLong_MASK);
- assert((carry >> PyLong_SHIFT) == 0);
- }
- }
- return long_normalize(z);
+ PyLongObject *z;
+ Py_ssize_t size_a = ABS(Py_SIZE(a));
+ Py_ssize_t size_b = ABS(Py_SIZE(b));
+ Py_ssize_t i;
+
+ z = _PyLong_New(size_a + size_b);
+ if (z == NULL)
+ return NULL;
+
+ memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
+ if (a == b) {
+ /* Efficient squaring per HAC, Algorithm 14.16:
+ * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
+ * Gives slightly less than a 2x speedup when a == b,
+ * via exploiting that each entry in the multiplication
+ * pyramid appears twice (except for the size_a squares).
+ */
+ for (i = 0; i < size_a; ++i) {
+ twodigits carry;
+ twodigits f = a->ob_digit[i];
+ digit *pz = z->ob_digit + (i << 1);
+ digit *pa = a->ob_digit + i + 1;
+ digit *paend = 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 <= PyLong_MASK);
+
+ /* Now f is added in twice in each column of the
+ * pyramid it appears. Same as adding f<<1 once.
+ */
+ f <<= 1;
+ while (pa < paend) {
+ carry += *pz + *pa++ * f;
+ *pz++ = (digit)(carry & PyLong_MASK);
+ carry >>= PyLong_SHIFT;
+ assert(carry <= (PyLong_MASK << 1));
+ }
+ if (carry) {
+ carry += *pz;
+ *pz++ = (digit)(carry & PyLong_MASK);
+ carry >>= PyLong_SHIFT;
+ }
+ if (carry)
+ *pz += (digit)(carry & PyLong_MASK);
+ assert((carry >> PyLong_SHIFT) == 0);
+ }
+ }
+ else { /* a is not the same as b -- gradeschool long mult */
+ for (i = 0; i < size_a; ++i) {
+ twodigits carry = 0;
+ twodigits f = a->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_MASK);
+ }
+ if (carry)
+ *pz += (digit)(carry & PyLong_MASK);
+ assert((carry >> PyLong_SHIFT) == 0);
+ }
+ }
+ return long_normalize(z);
}
/* A helper for Karatsuba multiplication (k_mul).
@@ -2774,26 +2774,26 @@ x_mul(PyLongObject *a, PyLongObject *b)
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 = ABS(Py_SIZE(n));
-
- size_lo = 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;
+ PyLongObject *hi, *lo;
+ Py_ssize_t size_lo, size_hi;
+ const Py_ssize_t size_n = ABS(Py_SIZE(n));
+
+ size_lo = 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);
@@ -2805,169 +2805,169 @@ static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
static PyLongObject *
k_mul(PyLongObject *a, PyLongObject *b)
{
- Py_ssize_t asize = ABS(Py_SIZE(a));
- Py_ssize_t bsize = 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 <= i) {
- if (asize == 0)
- return (PyLongObject *)PyLong_FromLong(0);
- else
- return x_mul(a, b);
- }
-
- /* If a is small compared to b, splitting on b gives a degenerate
- * case with ah==0, and Karatsuba may be (even much) less efficient
- * than "grade school" then. However, we can still win, by viewing
- * b as a string of "big digits", each of width a->ob_size. That
- * leads to a sequence of balanced calls to k_mul.
- */
- if (2 * asize <= bsize)
- return k_lopsided_mul(a, b);
-
- /* Split a & b into hi & lo pieces. */
- shift = bsize >> 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;
+ Py_ssize_t asize = ABS(Py_SIZE(a));
+ Py_ssize_t bsize = 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 <= i) {
+ if (asize == 0)
+ return (PyLongObject *)PyLong_FromLong(0);
+ else
+ return x_mul(a, b);
+ }
+
+ /* If a is small compared to b, splitting on b gives a degenerate
+ * case with ah==0, and Karatsuba may be (even much) less efficient
+ * than "grade school" then. However, we can still win, by viewing
+ * b as a string of "big digits", each of width a->ob_size. That
+ * leads to a sequence of balanced calls to k_mul.
+ */
+ if (2 * asize <= bsize)
+ return k_lopsided_mul(a, b);
+
+ /* Split a & b into hi & lo pieces. */
+ shift = bsize >> 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));
+ /* Fill with trash, to catch reference to uninitialized digits. */
+ memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
#endif
- /* 2. t1 <- ah*bh, and copy into high digits of result. */
- if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
- assert(Py_SIZE(t1) >= 0);
- assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
- memcpy(ret->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 <- al*bl, and copy into the low digits. */
- if ((t2 = k_mul(al, bl)) == NULL) {
- Py_DECREF(t1);
- goto fail;
- }
- assert(Py_SIZE(t2) >= 0);
- assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
- memcpy(ret->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 <- (ah+al)(bh+bl), and add into result. */
- if ((t1 = x_add(ah, al)) == NULL) goto fail;
- Py_DECREF(ah);
- Py_DECREF(al);
- ah = al = NULL;
-
- if (a == b) {
- t2 = t1;
- Py_INCREF(t2);
- }
- else if ((t2 = x_add(bh, bl)) == NULL) {
- Py_DECREF(t1);
- goto fail;
- }
- Py_DECREF(bh);
- Py_DECREF(bl);
- bh = bl = NULL;
-
- t3 = k_mul(t1, t2);
- Py_DECREF(t1);
- Py_DECREF(t2);
- if (t3 == NULL) goto fail;
- assert(Py_SIZE(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);
+ /* 2. t1 <- ah*bh, and copy into high digits of result. */
+ if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
+ assert(Py_SIZE(t1) >= 0);
+ assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
+ memcpy(ret->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 <- al*bl, and copy into the low digits. */
+ if ((t2 = k_mul(al, bl)) == NULL) {
+ Py_DECREF(t1);
+ goto fail;
+ }
+ assert(Py_SIZE(t2) >= 0);
+ assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
+ memcpy(ret->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 <- (ah+al)(bh+bl), and add into result. */
+ if ((t1 = x_add(ah, al)) == NULL) goto fail;
+ Py_DECREF(ah);
+ Py_DECREF(al);
+ ah = al = NULL;
+
+ if (a == b) {
+ t2 = t1;
+ Py_INCREF(t2);
+ }
+ else if ((t2 = x_add(bh, bl)) == NULL) {
+ Py_DECREF(t1);
+ goto fail;
+ }
+ Py_DECREF(bh);
+ Py_DECREF(bl);
+ bh = bl = NULL;
+
+ t3 = k_mul(t1, t2);
+ Py_DECREF(t1);
+ Py_DECREF(t2);
+ if (t3 == NULL) goto fail;
+ assert(Py_SIZE(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;
+ 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.
@@ -3026,85 +3026,85 @@ ah*bh and al*bl too.
static PyLongObject *
k_lopsided_mul(PyLongObject *a, PyLongObject *b)
{
- const Py_ssize_t asize = ABS(Py_SIZE(a));
- Py_ssize_t bsize = 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 <= bsize);
-
- /* Allocate result space, and zero it out. */
- ret = _PyLong_New(asize + bsize);
- if (ret == NULL)
- return NULL;
- memset(ret->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 = MIN(bsize, asize);
-
- /* Multiply the next slice of b by a. */
- memcpy(bslice->ob_digit, b->ob_digit + nbdone,
- nbtouse * sizeof(digit));
- Py_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);
+ const Py_ssize_t asize = ABS(Py_SIZE(a));
+ Py_ssize_t bsize = 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 <= bsize);
+
+ /* Allocate result space, and zero it out. */
+ ret = _PyLong_New(asize + bsize);
+ if (ret == NULL)
+ return NULL;
+ memset(ret->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 = MIN(bsize, asize);
+
+ /* Multiply the next slice of b by a. */
+ memcpy(bslice->ob_digit, b->ob_digit + nbdone,
+ nbtouse * sizeof(digit));
+ Py_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;
+ Py_DECREF(ret);
+ Py_XDECREF(bslice);
+ return NULL;
}
static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
- PyLongObject *z;
+ PyLongObject *z;
- CHECK_BINOP(a, b);
+ CHECK_BINOP(a, b);
- /* fast path for single-digit multiplication */
- if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
- stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
+ /* fast path for single-digit multiplication */
+ if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
+ stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
- return PyLong_FromLongLong((PY_LONG_LONG)v);
+ return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
- /* if we don't have long long then we're almost certainly
- using 15-bit digits, so v will fit in a long. In the
- unlikely event that we're using 30-bit digits on a platform
- without long long, a large v will just cause us to fall
- through to the general multiplication code below. */
- if (v >= LONG_MIN && v <= LONG_MAX)
- return PyLong_FromLong((long)v);
+ /* if we don't have long long then we're almost certainly
+ using 15-bit digits, so v will fit in a long. In the
+ unlikely event that we're using 30-bit digits on a platform
+ without long long, a large v will just cause us to fall
+ through to the general multiplication code below. */
+ if (v >= LONG_MIN && v <= LONG_MAX)
+ return PyLong_FromLong((long)v);
#endif
- }
+ }
- z = k_mul(a, b);
- /* Negate if exactly one of the inputs is negative. */
- if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z)
- NEGATE(z);
- return (PyObject *)z;
+ z = k_mul(a, b);
+ /* Negate if exactly one of the inputs is negative. */
+ if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z)
+ NEGATE(z);
+ return (PyObject *)z;
}
/* The / and % operators are now defined in terms of divmod().
@@ -3113,11 +3113,11 @@ long_mul(PyLongObject *a, PyLongObject *b)
|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
+ 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. */
@@ -3130,480 +3130,480 @@ long_mul(PyLongObject *a, PyLongObject *b)
*/
static int
l_divmod(PyLongObject *v, PyLongObject *w,
- PyLongObject **pdiv, PyLongObject **pmod)
+ PyLongObject **pdiv, PyLongObject **pmod)
{
- PyLongObject *div, *mod;
-
- 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;
- PyLongObject *one;
- temp = (PyLongObject *) long_add(mod, w);
- Py_DECREF(mod);
- mod = temp;
- if (mod == NULL) {
- Py_DECREF(div);
- return -1;
- }
- one = (PyLongObject *) PyLong_FromLong(1L);
- if (one == NULL ||
- (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
- Py_DECREF(mod);
- Py_DECREF(div);
- Py_XDECREF(one);
- return -1;
- }
- Py_DECREF(one);
- 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;
+ PyLongObject *div, *mod;
+
+ 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;
+ PyLongObject *one;
+ temp = (PyLongObject *) long_add(mod, w);
+ Py_DECREF(mod);
+ mod = temp;
+ if (mod == NULL) {
+ Py_DECREF(div);
+ return -1;
+ }
+ one = (PyLongObject *) PyLong_FromLong(1L);
+ if (one == NULL ||
+ (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
+ Py_DECREF(mod);
+ Py_DECREF(div);
+ Py_XDECREF(one);
+ return -1;
+ }
+ Py_DECREF(one);
+ 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;
+ PyLongObject *div;
- CHECK_BINOP(a, b);
- if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
- div = NULL;
- return (PyObject *)div;
+ CHECK_BINOP(a, b);
+ if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
+ div = NULL;
+ return (PyObject *)div;
}
static PyObject *
long_true_divide(PyObject *a, PyObject *b)
{
- double ad, bd;
- int failed, aexp = -1, bexp = -1;
-
- CHECK_BINOP(a, b);
- ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
- bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
- failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
- if (failed)
- return NULL;
- /* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x,
- but should really be set correctly after sucessful calls to
- _PyLong_AsScaledDouble() */
- assert(aexp >= 0 && bexp >= 0);
-
- if (bd == 0.0) {
- PyErr_SetString(PyExc_ZeroDivisionError,
- "int division or modulo by zero");
- return NULL;
- }
-
- /* True value is very close to ad/bd * 2**(PyLong_SHIFT*(aexp-bexp)) */
- ad /= bd; /* overflow/underflow impossible here */
- aexp -= bexp;
- if (aexp > INT_MAX / PyLong_SHIFT)
- goto overflow;
- else if (aexp < -(INT_MAX / PyLong_SHIFT))
- return PyFloat_FromDouble(0.0); /* underflow to 0 */
- errno = 0;
- ad = ldexp(ad, aexp * PyLong_SHIFT);
- if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
- goto overflow;
- return PyFloat_FromDouble(ad);
+ double ad, bd;
+ int failed, aexp = -1, bexp = -1;
+
+ CHECK_BINOP(a, b);
+ ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
+ bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
+ failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
+ if (failed)
+ return NULL;
+ /* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x,
+ but should really be set correctly after sucessful calls to
+ _PyLong_AsScaledDouble() */
+ assert(aexp >= 0 && bexp >= 0);
+
+ if (bd == 0.0) {
+ PyErr_SetString(PyExc_ZeroDivisionError,
+ "int division or modulo by zero");
+ return NULL;
+ }
+
+ /* True value is very close to ad/bd * 2**(PyLong_SHIFT*(aexp-bexp)) */
+ ad /= bd; /* overflow/underflow impossible here */
+ aexp -= bexp;
+ if (aexp > INT_MAX / PyLong_SHIFT)
+ goto overflow;
+ else if (aexp < -(INT_MAX / PyLong_SHIFT))
+ return PyFloat_FromDouble(0.0); /* underflow to 0 */
+ errno = 0;
+ ad = ldexp(ad, aexp * PyLong_SHIFT);
+ if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
+ goto overflow;
+ return PyFloat_FromDouble(ad);
overflow:
- PyErr_SetString(PyExc_OverflowError,
- "int/int too large for a float");
- return NULL;
+ PyErr_SetString(PyExc_OverflowError,
+ "int/int too large for a float");
+ return NULL;
}
static PyObject *
long_mod(PyObject *a, PyObject *b)
{
- PyLongObject *mod;
-
- CHECK_BINOP(a, b);
+ PyLongObject *mod;
+
+ CHECK_BINOP(a, b);
- if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0)
- mod = NULL;
- return (PyObject *)mod;
+ 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_SetItem(z, 0, (PyObject *) div);
- PyTuple_SetItem(z, 1, (PyObject *) mod);
- }
- else {
- Py_DECREF(div);
- Py_DECREF(mod);
- }
- return z;
+ 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_SetItem(z, 0, (PyObject *) div);
+ PyTuple_SetItem(z, 1, (PyObject *) mod);
+ }
+ else {
+ Py_DECREF(div);
+ Py_DECREF(mod);
+ }
+ return z;
}
/* 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<0 return negative output */
-
- PyLongObject *z = NULL; /* accumulated result */
- Py_ssize_t i, j, k; /* counters */
- PyLongObject *temp = NULL;
-
- /* 5-ary values. If the exponent is large enough, table is
- * precomputed so that table[i] == a**i % c for i in range(32).
- */
- PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
- 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
-
- /* a, b, c = v, w, x */
- CHECK_BINOP(v, w);
- a = (PyLongObject*)v; Py_INCREF(a);
- b = (PyLongObject*)w; Py_INCREF(b);
- if (PyLong_Check(x)) {
- c = (PyLongObject *)x;
- Py_INCREF(x);
- }
- else if (x == Py_None)
- c = NULL;
- else {
- Py_DECREF(a);
- Py_DECREF(b);
- Py_INCREF(Py_NotImplemented);
- return Py_NotImplemented;
- }
-
- if (Py_SIZE(b) < 0) { /* if exponent is negative */
- if (c) {
- PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
- "cannot be negative when 3rd argument specified");
- goto Error;
- }
- else {
- /* else return a float. This works because we know
- that this calls float_pow() which converts its
- arguments to double. */
- Py_DECREF(a);
- Py_DECREF(b);
- return PyFloat_Type.tp_as_number->nb_power(v, w, x);
- }
- }
-
- if (c) {
- /* if modulus == 0:
- raise ValueError() */
- if (Py_SIZE(c) == 0) {
- PyErr_SetString(PyExc_ValueError,
- "pow() 3rd argument cannot be 0");
- goto Error;
- }
-
- /* if modulus < 0:
- negativeOutput = True
- modulus = -modulus */
- if (Py_SIZE(c) < 0) {
- negativeOutput = 1;
- temp = (PyLongObject *)_PyLong_Copy(c);
- if (temp == NULL)
- goto Error;
- Py_DECREF(c);
- c = temp;
- temp = NULL;
- NEGATE(c);
- }
-
- /* if modulus == 1:
- return 0 */
- if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
- z = (PyLongObject *)PyLong_FromLong(0L);
- goto Done;
- }
-
- /* if base < 0:
- base = base % modulus
- Having the base positive just makes things easier. */
- if (Py_SIZE(a) < 0) {
- 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) \
- if (c != NULL) { \
- if (l_divmod(X, c, NULL, &temp) < 0) \
- goto Error; \
- Py_XDECREF(X); \
- X = temp; \
- temp = NULL; \
- }
-
- /* Multiply two values, then reduce the result:
- result = X*Y % c. If c is NULL, skip the mod. */
-#define MULT(X, Y, result) \
-{ \
- temp = (PyLongObject *)long_mul(X, Y); \
- if (temp == NULL) \
- goto Error; \
- Py_XDECREF(result); \
- result = temp; \
- temp = NULL; \
- REDUCE(result) \
+ PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
+ int negativeOutput = 0; /* if x<0 return negative output */
+
+ PyLongObject *z = NULL; /* accumulated result */
+ Py_ssize_t i, j, k; /* counters */
+ PyLongObject *temp = NULL;
+
+ /* 5-ary values. If the exponent is large enough, table is
+ * precomputed so that table[i] == a**i % c for i in range(32).
+ */
+ PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
+
+ /* a, b, c = v, w, x */
+ CHECK_BINOP(v, w);
+ a = (PyLongObject*)v; Py_INCREF(a);
+ b = (PyLongObject*)w; Py_INCREF(b);
+ if (PyLong_Check(x)) {
+ c = (PyLongObject *)x;
+ Py_INCREF(x);
+ }
+ else if (x == Py_None)
+ c = NULL;
+ else {
+ Py_DECREF(a);
+ Py_DECREF(b);
+ Py_INCREF(Py_NotImplemented);
+ return Py_NotImplemented;
+ }
+
+ if (Py_SIZE(b) < 0) { /* if exponent is negative */
+ if (c) {
+ PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
+ "cannot be negative when 3rd argument specified");
+ goto Error;
+ }
+ else {
+ /* else return a float. This works because we know
+ that this calls float_pow() which converts its
+ arguments to double. */
+ Py_DECREF(a);
+ Py_DECREF(b);
+ return PyFloat_Type.tp_as_number->nb_power(v, w, x);
+ }
+ }
+
+ if (c) {
+ /* if modulus == 0:
+ raise ValueError() */
+ if (Py_SIZE(c) == 0) {
+ PyErr_SetString(PyExc_ValueError,
+ "pow() 3rd argument cannot be 0");
+ goto Error;
+ }
+
+ /* if modulus < 0:
+ negativeOutput = True
+ modulus = -modulus */
+ if (Py_SIZE(c) < 0) {
+ negativeOutput = 1;
+ temp = (PyLongObject *)_PyLong_Copy(c);
+ if (temp == NULL)
+ goto Error;
+ Py_DECREF(c);
+ c = temp;
+ temp = NULL;
+ NEGATE(c);
+ }
+
+ /* if modulus == 1:
+ return 0 */
+ if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
+ z = (PyLongObject *)PyLong_FromLong(0L);
+ goto Done;
+ }
+
+ /* if base < 0:
+ base = base % modulus
+ Having the base positive just makes things easier. */
+ if (Py_SIZE(a) < 0) {
+ 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) \
+ if (c != NULL) { \
+ if (l_divmod(X, c, NULL, &temp) < 0) \
+ goto Error; \
+ Py_XDECREF(X); \
+ X = temp; \
+ temp = NULL; \
+ }
+
+ /* Multiply two values, then reduce the result:
+ result = X*Y % c. If c is NULL, skip the mod. */
+#define MULT(X, Y, result) \
+{ \
+ temp = (PyLongObject *)long_mul(X, Y); \
+ if (temp == NULL) \
+ goto Error; \
+ Py_XDECREF(result); \
+ result = temp; \
+ temp = NULL; \
+ REDUCE(result) \
}
- if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
- /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
- /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
- for (i = Py_SIZE(b) - 1; i >= 0; --i) {
- digit bi = b->ob_digit[i];
-
- for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 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;
+ if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
+ /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
+ /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
+ for (i = Py_SIZE(b) - 1; i >= 0; --i) {
+ digit bi = b->ob_digit[i];
+
+ for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 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:
- if (z != NULL) {
- Py_DECREF(z);
- z = NULL;
- }
- /* fall through */
+ if (z != NULL) {
+ Py_DECREF(z);
+ z = NULL;
+ }
+ /* 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;
+ 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;
- PyLongObject *w;
- if (ABS(Py_SIZE(v)) <=1)
- return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
- w = (PyLongObject *)PyLong_FromLong(1L);
- if (w == NULL)
- return NULL;
- x = (PyLongObject *) long_add(v, w);
- Py_DECREF(w);
- if (x == NULL)
- return NULL;
- Py_SIZE(x) = -(Py_SIZE(x));
- return (PyObject *)maybe_small_long(x);
+ /* Implement ~x as -(x+1) */
+ PyLongObject *x;
+ PyLongObject *w;
+ if (ABS(Py_SIZE(v)) <=1)
+ return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
+ w = (PyLongObject *)PyLong_FromLong(1L);
+ if (w == NULL)
+ return NULL;
+ x = (PyLongObject *) long_add(v, w);
+ Py_DECREF(w);
+ if (x == NULL)
+ return NULL;
+ Py_SIZE(x) = -(Py_SIZE(x));
+ return (PyObject *)maybe_small_long(x);
}
static PyObject *
long_neg(PyLongObject *v)
{
- PyLongObject *z;
- if (ABS(Py_SIZE(v)) <= 1)
- return PyLong_FromLong(-MEDIUM_VALUE(v));
- z = (PyLongObject *)_PyLong_Copy(v);
- if (z != NULL)
- Py_SIZE(z) = -(Py_SIZE(v));
- return (PyObject *)z;
+ PyLongObject *z;
+ if (ABS(Py_SIZE(v)) <= 1)
+ return PyLong_FromLong(-MEDIUM_VALUE(v));
+ z = (PyLongObject *)_PyLong_Copy(v);
+ if (z != NULL)
+ Py_SIZE(z) = -(Py_SIZE(v));
+ return (PyObject *)z;
}
static PyObject *
long_abs(PyLongObject *v)
{
- if (Py_SIZE(v) < 0)
- return long_neg(v);
- else
- return long_long((PyObject *)v);
+ if (Py_SIZE(v) < 0)
+ return long_neg(v);
+ else
+ return long_long((PyObject *)v);
}
static int
long_bool(PyLongObject *v)
{
- return ABS(Py_SIZE(v)) != 0;
+ return ABS(Py_SIZE(v)) != 0;
}
static PyObject *
long_rshift(PyLongObject *a, PyLongObject *b)
{
- PyLongObject *z = NULL;
- long shiftby;
- Py_ssize_t newsize, wordshift, loshift, hishift, i, j;
- digit lomask, himask;
-
- CHECK_BINOP(a, b);
-
- if (Py_SIZE(a) < 0) {
- /* Right shifting negative numbers is harder */
- PyLongObject *a1, *a2;
- a1 = (PyLongObject *) long_invert(a);
- if (a1 == NULL)
- goto rshift_error;
- a2 = (PyLongObject *) long_rshift(a1, b);
- Py_DECREF(a1);
- if (a2 == NULL)
- goto rshift_error;
- z = (PyLongObject *) long_invert(a2);
- Py_DECREF(a2);
- }
- else {
-
- shiftby = PyLong_AsLong((PyObject *)b);
- if (shiftby == -1L && PyErr_Occurred())
- goto rshift_error;
- if (shiftby < 0) {
- PyErr_SetString(PyExc_ValueError,
- "negative shift count");
- goto rshift_error;
- }
- wordshift = shiftby / PyLong_SHIFT;
- newsize = ABS(Py_SIZE(a)) - wordshift;
- if (newsize <= 0)
- return PyLong_FromLong(0);
- loshift = shiftby % PyLong_SHIFT;
- hishift = PyLong_SHIFT - loshift;
- lomask = ((digit)1 << hishift) - 1;
- himask = PyLong_MASK ^ lomask;
- z = _PyLong_New(newsize);
- if (z == NULL)
- goto rshift_error;
- if (Py_SIZE(a) < 0)
- Py_SIZE(z) = -(Py_SIZE(z));
- for (i = 0, j = wordshift; i < newsize; i++, j++) {
- z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
- if (i+1 < newsize)
- z->ob_digit[i] |=
- (a->ob_digit[j+1] << hishift) & himask;
- }
- z = long_normalize(z);
- }
+ PyLongObject *z = NULL;
+ long shiftby;
+ Py_ssize_t newsize, wordshift, loshift, hishift, i, j;
+ digit lomask, himask;
+
+ CHECK_BINOP(a, b);
+
+ if (Py_SIZE(a) < 0) {
+ /* Right shifting negative numbers is harder */
+ PyLongObject *a1, *a2;
+ a1 = (PyLongObject *) long_invert(a);
+ if (a1 == NULL)
+ goto rshift_error;
+ a2 = (PyLongObject *) long_rshift(a1, b);
+ Py_DECREF(a1);
+ if (a2 == NULL)
+ goto rshift_error;
+ z = (PyLongObject *) long_invert(a2);
+ Py_DECREF(a2);
+ }
+ else {
+
+ shiftby = PyLong_AsLong((PyObject *)b);
+ if (shiftby == -1L && PyErr_Occurred())
+ goto rshift_error;
+ if (shiftby < 0) {
+ PyErr_SetString(PyExc_ValueError,
+ "negative shift count");
+ goto rshift_error;
+ }
+ wordshift = shiftby / PyLong_SHIFT;
+ newsize = ABS(Py_SIZE(a)) - wordshift;
+ if (newsize <= 0)
+ return PyLong_FromLong(0);
+ loshift = shiftby % PyLong_SHIFT;
+ hishift = PyLong_SHIFT - loshift;
+ lomask = ((digit)1 << hishift) - 1;
+ himask = PyLong_MASK ^ lomask;
+ z = _PyLong_New(newsize);
+ if (z == NULL)
+ goto rshift_error;
+ if (Py_SIZE(a) < 0)
+ Py_SIZE(z) = -(Py_SIZE(z));
+ for (i = 0, j = wordshift; i < newsize; i++, j++) {
+ z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
+ if (i+1 < newsize)
+ z->ob_digit[i] |=
+ (a->ob_digit[j+1] << hishift) & himask;
+ }
+ z = long_normalize(z);
+ }
rshift_error:
- return (PyObject *) maybe_small_long(z);
+ return (PyObject *) maybe_small_long(z);
}
static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
- /* This version due to Tim Peters */
- PyLongObject *a = (PyLongObject*)v;
- PyLongObject *b = (PyLongObject*)w;
- PyLongObject *z = NULL;
- long shiftby;
- Py_ssize_t oldsize, newsize, wordshift, remshift, i, j;
- twodigits accum;
-
- CHECK_BINOP(a, b);
-
- shiftby = PyLong_AsLong((PyObject *)b);
- if (shiftby == -1L && PyErr_Occurred())
- goto lshift_error;
- if (shiftby < 0) {
- PyErr_SetString(PyExc_ValueError, "negative shift count");
- goto lshift_error;
- }
- if ((long)(int)shiftby != shiftby) {
- PyErr_SetString(PyExc_ValueError,
- "outrageous left shift count");
- goto lshift_error;
- }
- /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
- wordshift = (int)shiftby / PyLong_SHIFT;
- remshift = (int)shiftby - wordshift * PyLong_SHIFT;
-
- oldsize = ABS(Py_SIZE(a));
- newsize = oldsize + wordshift;
- if (remshift)
- ++newsize;
- z = _PyLong_New(newsize);
- if (z == NULL)
- goto lshift_error;
- if (Py_SIZE(a) < 0)
- NEGATE(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] << remshift;
- z->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);
+ /* This version due to Tim Peters */
+ PyLongObject *a = (PyLongObject*)v;
+ PyLongObject *b = (PyLongObject*)w;
+ PyLongObject *z = NULL;
+ long shiftby;
+ Py_ssize_t oldsize, newsize, wordshift, remshift, i, j;
+ twodigits accum;
+
+ CHECK_BINOP(a, b);
+
+ shiftby = PyLong_AsLong((PyObject *)b);
+ if (shiftby == -1L && PyErr_Occurred())
+ goto lshift_error;
+ if (shiftby < 0) {
+ PyErr_SetString(PyExc_ValueError, "negative shift count");
+ goto lshift_error;
+ }
+ if ((long)(int)shiftby != shiftby) {
+ PyErr_SetString(PyExc_ValueError,
+ "outrageous left shift count");
+ goto lshift_error;
+ }
+ /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
+ wordshift = (int)shiftby / PyLong_SHIFT;
+ remshift = (int)shiftby - wordshift * PyLong_SHIFT;
+
+ oldsize = ABS(Py_SIZE(a));
+ newsize = oldsize + wordshift;
+ if (remshift)
+ ++newsize;
+ z = _PyLong_New(newsize);
+ if (z == NULL)
+ goto lshift_error;
+ if (Py_SIZE(a) < 0)
+ NEGATE(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] << remshift;
+ z->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);
lshift_error:
- return (PyObject *) maybe_small_long(z);
+ return (PyObject *) maybe_small_long(z);
}
@@ -3611,154 +3611,154 @@ lshift_error:
static PyObject *
long_bitwise(PyLongObject *a,
- int op, /* '&', '|', '^' */
- PyLongObject *b)
+ int op, /* '&', '|', '^' */
+ PyLongObject *b)
{
- digit maska, maskb; /* 0 or PyLong_MASK */
- int negz;
- Py_ssize_t size_a, size_b, size_z, i;
- PyLongObject *z;
- digit diga, digb;
- PyObject *v;
-
- if (Py_SIZE(a) < 0) {
- a = (PyLongObject *) long_invert(a);
- if (a == NULL)
- return NULL;
- maska = PyLong_MASK;
- }
- else {
- Py_INCREF(a);
- maska = 0;
- }
- if (Py_SIZE(b) < 0) {
- b = (PyLongObject *) long_invert(b);
- if (b == NULL) {
- Py_DECREF(a);
- return NULL;
- }
- maskb = PyLong_MASK;
- }
- else {
- Py_INCREF(b);
- maskb = 0;
- }
-
- negz = 0;
- switch (op) {
- case '^':
- if (maska != maskb) {
- maska ^= PyLong_MASK;
- negz = -1;
- }
- break;
- case '&':
- if (maska && maskb) {
- op = '|';
- maska ^= PyLong_MASK;
- maskb ^= PyLong_MASK;
- negz = -1;
- }
- break;
- case '|':
- if (maska || maskb) {
- op = '&';
- maska ^= PyLong_MASK;
- maskb ^= PyLong_MASK;
- negz = -1;
- }
- break;
- }
-
- /* 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. After the transformations above, op will be '&'
- iff one of these cases applies, and mask will be non-0 for operands
- whose length should be ignored.
- */
-
- size_a = Py_SIZE(a);
- size_b = Py_SIZE(b);
- size_z = op == '&'
- ? (maska
- ? size_b
- : (maskb ? size_a : MIN(size_a, size_b)))
- : MAX(size_a, size_b);
- z = _PyLong_New(size_z);
- if (z == NULL) {
- Py_DECREF(a);
- Py_DECREF(b);
- return NULL;
- }
-
- for (i = 0; i < size_z; ++i) {
- diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
- digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
- switch (op) {
- case '&': z->ob_digit[i] = diga & digb; break;
- case '|': z->ob_digit[i] = diga | digb; break;
- case '^': z->ob_digit[i] = diga ^ digb; break;
- }
- }
-
- Py_DECREF(a);
- Py_DECREF(b);
- z = long_normalize(z);
- if (negz == 0)
- return (PyObject *) maybe_small_long(z);
- v = long_invert(z);
- Py_DECREF(z);
- return v;
+ digit maska, maskb; /* 0 or PyLong_MASK */
+ int negz;
+ Py_ssize_t size_a, size_b, size_z, i;
+ PyLongObject *z;
+ digit diga, digb;
+ PyObject *v;
+
+ if (Py_SIZE(a) < 0) {
+ a = (PyLongObject *) long_invert(a);
+ if (a == NULL)
+ return NULL;
+ maska = PyLong_MASK;
+ }
+ else {
+ Py_INCREF(a);
+ maska = 0;
+ }
+ if (Py_SIZE(b) < 0) {
+ b = (PyLongObject *) long_invert(b);
+ if (b == NULL) {
+ Py_DECREF(a);
+ return NULL;
+ }
+ maskb = PyLong_MASK;
+ }
+ else {
+ Py_INCREF(b);
+ maskb = 0;
+ }
+
+ negz = 0;
+ switch (op) {
+ case '^':
+ if (maska != maskb) {
+ maska ^= PyLong_MASK;
+ negz = -1;
+ }
+ break;
+ case '&':
+ if (maska && maskb) {
+ op = '|';
+ maska ^= PyLong_MASK;
+ maskb ^= PyLong_MASK;
+ negz = -1;
+ }
+ break;
+ case '|':
+ if (maska || maskb) {
+ op = '&';
+ maska ^= PyLong_MASK;
+ maskb ^= PyLong_MASK;
+ negz = -1;
+ }
+ break;
+ }
+
+ /* 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. After the transformations above, op will be '&'
+ iff one of these cases applies, and mask will be non-0 for operands
+ whose length should be ignored.
+ */
+
+ size_a = Py_SIZE(a);
+ size_b = Py_SIZE(b);
+ size_z = op == '&'
+ ? (maska
+ ? size_b
+ : (maskb ? size_a : MIN(size_a, size_b)))
+ : MAX(size_a, size_b);
+ z = _PyLong_New(size_z);
+ if (z == NULL) {
+ Py_DECREF(a);
+ Py_DECREF(b);
+ return NULL;
+ }
+
+ for (i = 0; i < size_z; ++i) {
+ diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
+ digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
+ switch (op) {
+ case '&': z->ob_digit[i] = diga & digb; break;
+ case '|': z->ob_digit[i] = diga | digb; break;
+ case '^': z->ob_digit[i] = diga ^ digb; break;
+ }
+ }
+
+ Py_DECREF(a);
+ Py_DECREF(b);
+ z = long_normalize(z);
+ if (negz == 0)
+ return (PyObject *) maybe_small_long(z);
+ v = long_invert(z);
+ Py_DECREF(z);
+ return v;
}
static PyObject *
long_and(PyObject *a, PyObject *b)
{
- PyObject *c;
- CHECK_BINOP(a, b);
- c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b);
- return c;
+ 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;
+ 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;
+ 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;
+ if (PyLong_CheckExact(v))
+ Py_INCREF(v);
+ else
+ v = _PyLong_Copy((PyLongObject *)v);
+ return v;
}
static PyObject *
long_float(PyObject *v)
{
- double result;
- result = PyLong_AsDouble(v);
- if (result == -1.0 && PyErr_Occurred())
- return NULL;
- return PyFloat_FromDouble(result);
+ double result;
+ result = PyLong_AsDouble(v);
+ if (result == -1.0 && PyErr_Occurred())
+ return NULL;
+ return PyFloat_FromDouble(result);
}
static PyObject *
@@ -3767,47 +3767,47 @@ long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
static PyObject *
long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
- PyObject *x = NULL;
- int base = -909; /* unlikely! */
- static char *kwlist[] = {"x", "base", 0};
-
- if (type != &PyLong_Type)
- return long_subtype_new(type, args, kwds); /* Wimp out */
- if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
- &x, &base))
- return NULL;
- if (x == NULL)
- return PyLong_FromLong(0L);
- if (base == -909)
- return PyNumber_Long(x);
- else if (PyUnicode_Check(x))
- return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
- PyUnicode_GET_SIZE(x),
- base);
- else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
- /* Since PyLong_FromString doesn't have a length parameter,
- * check here for possible NULs in the string. */
- char *string;
- Py_ssize_t size = Py_SIZE(x);
- if (PyByteArray_Check(x))
- string = PyByteArray_AS_STRING(x);
- else
- string = PyBytes_AS_STRING(x);
- if (strlen(string) != (size_t)size) {
- /* We only see this if there's a null byte in x,
- x is a bytes or buffer, *and* a base is given. */
- PyErr_Format(PyExc_ValueError,
- "invalid literal for int() with base %d: %R",
- base, x);
- return NULL;
- }
- return PyLong_FromString(string, NULL, base);
- }
- else {
- PyErr_SetString(PyExc_TypeError,
- "int() can't convert non-string with explicit base");
- return NULL;
- }
+ PyObject *x = NULL;
+ int base = -909; /* unlikely! */
+ static char *kwlist[] = {"x", "base", 0};
+
+ if (type != &PyLong_Type)
+ return long_subtype_new(type, args, kwds); /* Wimp out */
+ if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist,
+ &x, &base))
+ return NULL;
+ if (x == NULL)
+ return PyLong_FromLong(0L);
+ if (base == -909)
+ return PyNumber_Long(x);
+ else if (PyUnicode_Check(x))
+ return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
+ PyUnicode_GET_SIZE(x),
+ base);
+ else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
+ /* Since PyLong_FromString doesn't have a length parameter,
+ * check here for possible NULs in the string. */
+ char *string;
+ Py_ssize_t size = Py_SIZE(x);
+ if (PyByteArray_Check(x))
+ string = PyByteArray_AS_STRING(x);
+ else
+ string = PyBytes_AS_STRING(x);
+ if (strlen(string) != (size_t)size) {
+ /* We only see this if there's a null byte in x,
+ x is a bytes or buffer, *and* a base is given. */
+ PyErr_Format(PyExc_ValueError,
+ "invalid literal for int() with base %d: %R",
+ base, x);
+ return NULL;
+ }
+ return PyLong_FromString(string, NULL, base);
+ }
+ else {
+ PyErr_SetString(PyExc_TypeError,
+ "int() can't convert non-string with explicit base");
+ return NULL;
+ }
}
/* Wimpy, slow approach to tp_new calls for subtypes of long:
@@ -3818,256 +3818,256 @@ long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
static PyObject *
long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
- PyLongObject *tmp, *newobj;
- Py_ssize_t i, n;
-
- assert(PyType_IsSubtype(type, &PyLong_Type));
- tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
- if (tmp == NULL)
- return NULL;
- assert(PyLong_CheckExact(tmp));
- n = Py_SIZE(tmp);
- if (n < 0)
- n = -n;
- newobj = (PyLongObject *)type->tp_alloc(type, n);
- if (newobj == NULL) {
- Py_DECREF(tmp);
- return NULL;
- }
- assert(PyLong_Check(newobj));
- Py_SIZE(newobj) = Py_SIZE(tmp);
- for (i = 0; i < n; i++)
- newobj->ob_digit[i] = tmp->ob_digit[i];
- Py_DECREF(tmp);
- return (PyObject *)newobj;
+ PyLongObject *tmp, *newobj;
+ Py_ssize_t i, n;
+
+ assert(PyType_IsSubtype(type, &PyLong_Type));
+ tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
+ if (tmp == NULL)
+ return NULL;
+ assert(PyLong_CheckExact(tmp));
+ n = Py_SIZE(tmp);
+ if (n < 0)
+ n = -n;
+ newobj = (PyLongObject *)type->tp_alloc(type, n);
+ if (newobj == NULL) {
+ Py_DECREF(tmp);
+ return NULL;
+ }
+ assert(PyLong_Check(newobj));
+ Py_SIZE(newobj) = Py_SIZE(tmp);
+ for (i = 0; i < n; i++)
+ newobj->ob_digit[i] = tmp->ob_digit[i];
+ Py_DECREF(tmp);
+ return (PyObject *)newobj;
}
static PyObject *
long_getnewargs(PyLongObject *v)
{
- return Py_BuildValue("(N)", _PyLong_Copy(v));
+ return Py_BuildValue("(N)", _PyLong_Copy(v));
}
static PyObject *
long_get0(PyLongObject *v, void *context) {
- return PyLong_FromLong(0L);
+ return PyLong_FromLong(0L);
}
static PyObject *
long_get1(PyLongObject *v, void *context) {
- return PyLong_FromLong(1L);
+ return PyLong_FromLong(1L);
}
static PyObject *
long__format__(PyObject *self, PyObject *args)
{
- PyObject *format_spec;
+ PyObject *format_spec;
- if (!PyArg_ParseTuple(args, "U:__format__", &format_spec))
- return NULL;
- return _PyLong_FormatAdvanced(self,
- PyUnicode_AS_UNICODE(format_spec),
- PyUnicode_GET_SIZE(format_spec));
+ if (!PyArg_ParseTuple(args, "U:__format__", &format_spec))
+ return NULL;
+ return _PyLong_FormatAdvanced(self,
+ PyUnicode_AS_UNICODE(format_spec),
+ PyUnicode_GET_SIZE(format_spec));
}
static PyObject *
long_round(PyObject *self, PyObject *args)
{
- PyObject *o_ndigits=NULL, *temp;
- PyLongObject *pow=NULL, *q=NULL, *r=NULL, *ndigits=NULL, *one;
- int errcode;
- digit q_mod_4;
-
- /* Notes on the algorithm: to round to the nearest 10**n (n positive),
- the straightforward method is:
-
- (1) divide by 10**n
- (2) round to nearest integer (round to even in case of tie)
- (3) multiply result by 10**n.
-
- But the rounding step involves examining the fractional part of the
- quotient to see whether it's greater than 0.5 or not. Since we
- want to do the whole calculation in integer arithmetic, it's
- simpler to do:
-
- (1) divide by (10**n)/2
- (2) round to nearest multiple of 2 (multiple of 4 in case of tie)
- (3) multiply result by (10**n)/2.
-
- Then all we need to know about the fractional part of the quotient
- arising in step (2) is whether it's zero or not.
-
- Doing both a multiplication and division is wasteful, and is easily
- avoided if we just figure out how much to adjust the original input
- by to do the rounding.
-
- Here's the whole algorithm expressed in Python.
-
- def round(self, ndigits = None):
- """round(int, int) -> int"""
- if ndigits is None or ndigits >= 0:
- return self
- pow = 10**-ndigits >> 1
- q, r = divmod(self, pow)
- self -= r
- if (q & 1 != 0):
- if (q & 2 == r == 0):
- self -= pow
- else:
- self += pow
- return self
-
- */
- if (!PyArg_ParseTuple(args, "|O", &o_ndigits))
- return NULL;
- if (o_ndigits == NULL)
- return long_long(self);
-
- ndigits = (PyLongObject *)PyNumber_Index(o_ndigits);
- if (ndigits == NULL)
- return NULL;
-
- if (Py_SIZE(ndigits) >= 0) {
- Py_DECREF(ndigits);
- return long_long(self);
- }
-
- Py_INCREF(self); /* to keep refcounting simple */
- /* we now own references to self, ndigits */
-
- /* pow = 10 ** -ndigits >> 1 */
- pow = (PyLongObject *)PyLong_FromLong(10L);
- if (pow == NULL)
- goto error;
- temp = long_neg(ndigits);
- Py_DECREF(ndigits);
- ndigits = (PyLongObject *)temp;
- if (ndigits == NULL)
- goto error;
- temp = long_pow((PyObject *)pow, (PyObject *)ndigits, Py_None);
- Py_DECREF(pow);
- pow = (PyLongObject *)temp;
- if (pow == NULL)
- goto error;
- assert(PyLong_Check(pow)); /* check long_pow returned a long */
- one = (PyLongObject *)PyLong_FromLong(1L);
- if (one == NULL)
- goto error;
- temp = long_rshift(pow, one);
- Py_DECREF(one);
- Py_DECREF(pow);
- pow = (PyLongObject *)temp;
- if (pow == NULL)
- goto error;
-
- /* q, r = divmod(self, pow) */
- errcode = l_divmod((PyLongObject *)self, pow, &q, &r);
- if (errcode == -1)
- goto error;
-
- /* self -= r */
- temp = long_sub((PyLongObject *)self, r);
- Py_DECREF(self);
- self = temp;
- if (self == NULL)
- goto error;
-
- /* get value of quotient modulo 4 */
- if (Py_SIZE(q) == 0)
- q_mod_4 = 0;
- else if (Py_SIZE(q) > 0)
- q_mod_4 = q->ob_digit[0] & 3;
- else
- q_mod_4 = (PyLong_BASE-q->ob_digit[0]) & 3;
-
- if ((q_mod_4 & 1) == 1) {
- /* q is odd; round self up or down by adding or subtracting pow */
- if (q_mod_4 == 1 && Py_SIZE(r) == 0)
- temp = (PyObject *)long_sub((PyLongObject *)self, pow);
- else
- temp = (PyObject *)long_add((PyLongObject *)self, pow);
- Py_DECREF(self);
- self = temp;
- if (self == NULL)
- goto error;
- }
- Py_DECREF(q);
- Py_DECREF(r);
- Py_DECREF(pow);
- Py_DECREF(ndigits);
- return self;
+ PyObject *o_ndigits=NULL, *temp;
+ PyLongObject *pow=NULL, *q=NULL, *r=NULL, *ndigits=NULL, *one;
+ int errcode;
+ digit q_mod_4;
+
+ /* Notes on the algorithm: to round to the nearest 10**n (n positive),
+ the straightforward method is:
+
+ (1) divide by 10**n
+ (2) round to nearest integer (round to even in case of tie)
+ (3) multiply result by 10**n.
+
+ But the rounding step involves examining the fractional part of the
+ quotient to see whether it's greater than 0.5 or not. Since we
+ want to do the whole calculation in integer arithmetic, it's
+ simpler to do:
+
+ (1) divide by (10**n)/2
+ (2) round to nearest multiple of 2 (multiple of 4 in case of tie)
+ (3) multiply result by (10**n)/2.
+
+ Then all we need to know about the fractional part of the quotient
+ arising in step (2) is whether it's zero or not.
+
+ Doing both a multiplication and division is wasteful, and is easily
+ avoided if we just figure out how much to adjust the original input
+ by to do the rounding.
+
+ Here's the whole algorithm expressed in Python.
+
+ def round(self, ndigits = None):
+ """round(int, int) -> int"""
+ if ndigits is None or ndigits >= 0:
+ return self
+ pow = 10**-ndigits >> 1
+ q, r = divmod(self, pow)
+ self -= r
+ if (q & 1 != 0):
+ if (q & 2 == r == 0):
+ self -= pow
+ else:
+ self += pow
+ return self
+
+ */
+ if (!PyArg_ParseTuple(args, "|O", &o_ndigits))
+ return NULL;
+ if (o_ndigits == NULL)
+ return long_long(self);
+
+ ndigits = (PyLongObject *)PyNumber_Index(o_ndigits);
+ if (ndigits == NULL)
+ return NULL;
+
+ if (Py_SIZE(ndigits) >= 0) {
+ Py_DECREF(ndigits);
+ return long_long(self);
+ }
+
+ Py_INCREF(self); /* to keep refcounting simple */
+ /* we now own references to self, ndigits */
+
+ /* pow = 10 ** -ndigits >> 1 */
+ pow = (PyLongObject *)PyLong_FromLong(10L);
+ if (pow == NULL)
+ goto error;
+ temp = long_neg(ndigits);
+ Py_DECREF(ndigits);
+ ndigits = (PyLongObject *)temp;
+ if (ndigits == NULL)
+ goto error;
+ temp = long_pow((PyObject *)pow, (PyObject *)ndigits, Py_None);
+ Py_DECREF(pow);
+ pow = (PyLongObject *)temp;
+ if (pow == NULL)
+ goto error;
+ assert(PyLong_Check(pow)); /* check long_pow returned a long */
+ one = (PyLongObject *)PyLong_FromLong(1L);
+ if (one == NULL)
+ goto error;
+ temp = long_rshift(pow, one);
+ Py_DECREF(one);
+ Py_DECREF(pow);
+ pow = (PyLongObject *)temp;
+ if (pow == NULL)
+ goto error;
+
+ /* q, r = divmod(self, pow) */
+ errcode = l_divmod((PyLongObject *)self, pow, &q, &r);
+ if (errcode == -1)
+ goto error;
+
+ /* self -= r */
+ temp = long_sub((PyLongObject *)self, r);
+ Py_DECREF(self);
+ self = temp;
+ if (self == NULL)
+ goto error;
+
+ /* get value of quotient modulo 4 */
+ if (Py_SIZE(q) == 0)
+ q_mod_4 = 0;
+ else if (Py_SIZE(q) > 0)
+ q_mod_4 = q->ob_digit[0] & 3;
+ else
+ q_mod_4 = (PyLong_BASE-q->ob_digit[0]) & 3;
+
+ if ((q_mod_4 & 1) == 1) {
+ /* q is odd; round self up or down by adding or subtracting pow */
+ if (q_mod_4 == 1 && Py_SIZE(r) == 0)
+ temp = (PyObject *)long_sub((PyLongObject *)self, pow);
+ else
+ temp = (PyObject *)long_add((PyLongObject *)self, pow);
+ Py_DECREF(self);
+ self = temp;
+ if (self == NULL)
+ goto error;
+ }
+ Py_DECREF(q);
+ Py_DECREF(r);
+ Py_DECREF(pow);
+ Py_DECREF(ndigits);
+ return self;
error:
- Py_XDECREF(q);
- Py_XDECREF(r);
- Py_XDECREF(pow);
- Py_XDECREF(self);
- Py_XDECREF(ndigits);
- return NULL;
+ Py_XDECREF(q);
+ Py_XDECREF(r);
+ Py_XDECREF(pow);
+ Py_XDECREF(self);
+ Py_XDECREF(ndigits);
+ return NULL;
}
static PyObject *
long_sizeof(PyLongObject *v)
{
- Py_ssize_t res;
+ Py_ssize_t res;
- res = offsetof(PyLongObject, ob_digit) + ABS(Py_SIZE(v))*sizeof(digit);
- return PyLong_FromSsize_t(res);
+ res = offsetof(PyLongObject, ob_digit) + ABS(Py_SIZE(v))*sizeof(digit);
+ return PyLong_FromSsize_t(res);
}
static PyObject *
long_bit_length(PyLongObject *v)
{
- PyLongObject *result, *x, *y;
- Py_ssize_t ndigits, msd_bits = 0;
- digit msd;
-
- assert(v != NULL);
- assert(PyLong_Check(v));
-
- ndigits = ABS(Py_SIZE(v));
- if (ndigits == 0)
- return PyLong_FromLong(0);
-
- msd = v->ob_digit[ndigits-1];
- while (msd >= 32) {
- msd_bits += 6;
- msd >>= 6;
- }
- msd_bits += (long)(BitLengthTable[msd]);
-
- if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
- return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
-
- /* expression above may overflow; use Python integers instead */
- result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
- if (result == NULL)
- return NULL;
- x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
- if (x == NULL)
- goto error;
- y = (PyLongObject *)long_mul(result, x);
- Py_DECREF(x);
- if (y == NULL)
- goto error;
- Py_DECREF(result);
- result = y;
-
- x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
- if (x == NULL)
- goto error;
- y = (PyLongObject *)long_add(result, x);
- Py_DECREF(x);
- if (y == NULL)
- goto error;
- Py_DECREF(result);
- result = y;
-
- return (PyObject *)result;
+ PyLongObject *result, *x, *y;
+ Py_ssize_t ndigits, msd_bits = 0;
+ digit msd;
+
+ assert(v != NULL);
+ assert(PyLong_Check(v));
+
+ ndigits = ABS(Py_SIZE(v));
+ if (ndigits == 0)
+ return PyLong_FromLong(0);
+
+ msd = v->ob_digit[ndigits-1];
+ while (msd >= 32) {
+ msd_bits += 6;
+ msd >>= 6;
+ }
+ msd_bits += (long)(BitLengthTable[msd]);
+
+ if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
+ return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
+
+ /* expression above may overflow; use Python integers instead */
+ result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
+ if (result == NULL)
+ return NULL;
+ x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
+ if (x == NULL)
+ goto error;
+ y = (PyLongObject *)long_mul(result, x);
+ Py_DECREF(x);
+ if (y == NULL)
+ goto error;
+ Py_DECREF(result);
+ result = y;
+
+ x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
+ if (x == NULL)
+ goto error;
+ y = (PyLongObject *)long_add(result, x);
+ Py_DECREF(x);
+ if (y == NULL)
+ goto error;
+ Py_DECREF(result);
+ result = y;
+
+ return (PyObject *)result;
error:
- Py_DECREF(result);
- return NULL;
+ Py_DECREF(result);
+ return NULL;
}
PyDoc_STRVAR(long_bit_length_doc,
@@ -4083,33 +4083,33 @@ Number of bits necessary to represent self in binary.\n\
static PyObject *
long_is_finite(PyObject *v)
{
- Py_RETURN_TRUE;
+ Py_RETURN_TRUE;
}
#endif
static PyMethodDef long_methods[] = {
- {"conjugate", (PyCFunction)long_long, METH_NOARGS,
- "Returns self, the complex conjugate of any int."},
- {"bit_length", (PyCFunction)long_bit_length, METH_NOARGS,
- long_bit_length_doc},
+ {"conjugate", (PyCFunction)long_long, METH_NOARGS,
+ "Returns self, the complex conjugate of any int."},
+ {"bit_length", (PyCFunction)long_bit_length, METH_NOARGS,
+ long_bit_length_doc},
#if 0
- {"is_finite", (PyCFunction)long_is_finite, METH_NOARGS,
- "Returns always True."},
+ {"is_finite", (PyCFunction)long_is_finite, METH_NOARGS,
+ "Returns always True."},
#endif
- {"__trunc__", (PyCFunction)long_long, METH_NOARGS,
- "Truncating an Integral returns itself."},
- {"__floor__", (PyCFunction)long_long, METH_NOARGS,
- "Flooring an Integral returns itself."},
- {"__ceil__", (PyCFunction)long_long, METH_NOARGS,
- "Ceiling of an Integral returns itself."},
- {"__round__", (PyCFunction)long_round, METH_VARARGS,
- "Rounding an Integral returns itself.\n"
- "Rounding with an ndigits argument also returns an integer."},
- {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS},
- {"__format__", (PyCFunction)long__format__, METH_VARARGS},
- {"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS,
- "Returns size in memory, in bytes"},
- {NULL, NULL} /* sentinel */
+ {"__trunc__", (PyCFunction)long_long, METH_NOARGS,
+ "Truncating an Integral returns itself."},
+ {"__floor__", (PyCFunction)long_long, METH_NOARGS,
+ "Flooring an Integral returns itself."},
+ {"__ceil__", (PyCFunction)long_long, METH_NOARGS,
+ "Ceiling of an Integral returns itself."},
+ {"__round__", (PyCFunction)long_round, METH_VARARGS,
+ "Rounding an Integral returns itself.\n"
+ "Rounding with an ndigits argument also returns an integer."},
+ {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS},
+ {"__format__", (PyCFunction)long__format__, METH_VARARGS},
+ {"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS,
+ "Returns size in memory, in bytes"},
+ {NULL, NULL} /* sentinel */
};
static PyGetSetDef long_getset[] = {
@@ -4142,83 +4142,83 @@ string, use the optional base. It is an error to supply a base when\n\
converting a non-string.");
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*/
- (unaryfunc) long_long, /*tp_positive*/
- (unaryfunc) long_abs, /*tp_absolute*/
- (inquiry) long_bool, /*tp_bool*/
- (unaryfunc) long_invert, /*nb_invert*/
- long_lshift, /*nb_lshift*/
- (binaryfunc) 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 */
+ (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*/
+ (unaryfunc) long_long, /*tp_positive*/
+ (unaryfunc) long_abs, /*tp_absolute*/
+ (inquiry) long_bool, /*tp_bool*/
+ (unaryfunc) long_invert, /*nb_invert*/
+ long_lshift, /*nb_lshift*/
+ (binaryfunc) 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 */
- long_dealloc, /* tp_dealloc */
- 0, /* tp_print */
- 0, /* tp_getattr */
- 0, /* tp_setattr */
- 0, /* tp_reserved */
- long_repr, /* tp_repr */
- &long_as_number, /* tp_as_number */
- 0, /* tp_as_sequence */
- 0, /* tp_as_mapping */
- (hashfunc)long_hash, /* tp_hash */
- 0, /* tp_call */
- long_repr, /* 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 */
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "int", /* tp_name */
+ offsetof(PyLongObject, ob_digit), /* tp_basicsize */
+ sizeof(digit), /* tp_itemsize */
+ long_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_reserved */
+ long_repr, /* tp_repr */
+ &long_as_number, /* tp_as_number */
+ 0, /* tp_as_sequence */
+ 0, /* tp_as_mapping */
+ (hashfunc)long_hash, /* tp_hash */
+ 0, /* tp_call */
+ long_repr, /* 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;
@@ -4230,89 +4230,89 @@ A struct sequence 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}
+ {"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 */
+ "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;
+ 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(void)
{
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
- int ival, size;
- PyLongObject *v = small_ints;
-
- for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++, v++) {
- size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
- if (Py_TYPE(v) == &PyLong_Type) {
- /* The element is already initialized, most likely
- * the Python interpreter was initialized before.
- */
- Py_ssize_t refcnt;
- PyObject* op = (PyObject*)v;
-
- refcnt = Py_REFCNT(op) < 0 ? 0 : Py_REFCNT(op);
- _Py_NewReference(op);
- /* _Py_NewReference sets the ref count to 1 but
- * the ref count might be larger. Set the refcnt
- * to the original refcnt + 1 */
- Py_REFCNT(op) = refcnt + 1;
- assert(Py_SIZE(op) == size);
- assert(v->ob_digit[0] == abs(ival));
- }
- else {
- PyObject_INIT(v, &PyLong_Type);
- }
- Py_SIZE(v) = size;
- v->ob_digit[0] = abs(ival);
- }
+ int ival, size;
+ PyLongObject *v = small_ints;
+
+ for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++, v++) {
+ size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
+ if (Py_TYPE(v) == &PyLong_Type) {
+ /* The element is already initialized, most likely
+ * the Python interpreter was initialized before.
+ */
+ Py_ssize_t refcnt;
+ PyObject* op = (PyObject*)v;
+
+ refcnt = Py_REFCNT(op) < 0 ? 0 : Py_REFCNT(op);
+ _Py_NewReference(op);
+ /* _Py_NewReference sets the ref count to 1 but
+ * the ref count might be larger. Set the refcnt
+ * to the original refcnt + 1 */
+ Py_REFCNT(op) = refcnt + 1;
+ assert(Py_SIZE(op) == size);
+ assert(v->ob_digit[0] == abs(ival));
+ }
+ else {
+ PyObject_INIT(v, &PyLong_Type);
+ }
+ Py_SIZE(v) = size;
+ v->ob_digit[0] = abs(ival);
+ }
#endif
- /* initialize int_info */
- if (Int_InfoType.tp_name == 0)
- PyStructSequence_InitType(&Int_InfoType, &int_info_desc);
+ /* initialize int_info */
+ if (Int_InfoType.tp_name == 0)
+ PyStructSequence_InitType(&Int_InfoType, &int_info_desc);
- return 1;
+ return 1;
}
void
PyLong_Fini(void)
{
- /* Integers are currently statically allocated. Py_DECREF is not
- needed, but Python must forget about the reference or multiple
- reinitializations will fail. */
+ /* Integers are currently statically allocated. Py_DECREF is not
+ needed, but Python must forget about the reference or multiple
+ reinitializations will fail. */
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
- int i;
- PyLongObject *v = small_ints;
- for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) {
- _Py_DEC_REFTOTAL;
- _Py_ForgetReference((PyObject*)v);
- }
+ int i;
+ PyLongObject *v = small_ints;
+ for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) {
+ _Py_DEC_REFTOTAL;
+ _Py_ForgetReference((PyObject*)v);
+ }
#endif
}