+/* Long (arbitrary precision) integer object implementation */\r
+\r
+/* XXX The functional organization of this file is terrible */\r
+\r
+#include "Python.h"\r
+#include "longintrepr.h"\r
+#include "structseq.h"\r
+\r
+#include <float.h>\r
+#include <ctype.h>\r
+#include <stddef.h>\r
+\r
+/* For long multiplication, use the O(N**2) school algorithm unless\r
+ * both operands contain more than KARATSUBA_CUTOFF digits (this\r
+ * being an internal Python long digit, in base PyLong_BASE).\r
+ */\r
+#define KARATSUBA_CUTOFF 70\r
+#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)\r
+\r
+/* For exponentiation, use the binary left-to-right algorithm\r
+ * unless the exponent contains more than FIVEARY_CUTOFF digits.\r
+ * In that case, do 5 bits at a time. The potential drawback is that\r
+ * a table of 2**5 intermediate results is computed.\r
+ */\r
+#define FIVEARY_CUTOFF 8\r
+\r
+#ifndef ABS\r
+ #define ABS(x) ((x) < 0 ? -(x) : (x))\r
+#endif\r
+\r
+#ifndef MAX\r
+ #define MAX(x, y) ((x) < (y) ? (y) : (x))\r
+#endif\r
+\r
+#ifndef MIN\r
+ #define MIN(x, y) ((x) > (y) ? (y) : (x))\r
+#endif\r
+\r
+#define SIGCHECK(PyTryBlock) \\r
+ do { \\r
+ if (--_Py_Ticker < 0) { \\r
+ _Py_Ticker = _Py_CheckInterval; \\r
+ if (PyErr_CheckSignals()) PyTryBlock \\r
+ } \\r
+ } while(0)\r
+\r
+/* Normalize (remove leading zeros from) a long int object.\r
+ Doesn't attempt to free the storage--in most cases, due to the nature\r
+ of the algorithms used, this could save at most be one word anyway. */\r
+\r
+static PyLongObject *\r
+long_normalize(register PyLongObject *v)\r
+{\r
+ Py_ssize_t j = ABS(Py_SIZE(v));\r
+ Py_ssize_t i = j;\r
+\r
+ while (i > 0 && v->ob_digit[i-1] == 0)\r
+ --i;\r
+ if (i != j)\r
+ Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;\r
+ return v;\r
+}\r
+\r
+/* Allocate a new long int object with size digits.\r
+ Return NULL and set exception if we run out of memory. */\r
+\r
+#define MAX_LONG_DIGITS \\r
+ ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))\r
+\r
+PyLongObject *\r
+_PyLong_New(Py_ssize_t size)\r
+{\r
+ if (size > (Py_ssize_t)MAX_LONG_DIGITS) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "too many digits in integer");\r
+ return NULL;\r
+ }\r
+ /* coverity[ampersand_in_size] */\r
+ /* XXX(nnorwitz): PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect\r
+ overflow */\r
+ return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);\r
+}\r
+\r
+PyObject *\r
+_PyLong_Copy(PyLongObject *src)\r
+{\r
+ PyLongObject *result;\r
+ Py_ssize_t i;\r
+\r
+ assert(src != NULL);\r
+ i = src->ob_size;\r
+ if (i < 0)\r
+ i = -(i);\r
+ result = _PyLong_New(i);\r
+ if (result != NULL) {\r
+ result->ob_size = src->ob_size;\r
+ while (--i >= 0)\r
+ result->ob_digit[i] = src->ob_digit[i];\r
+ }\r
+ return (PyObject *)result;\r
+}\r
+\r
+/* Create a new long int object from a C long int */\r
+\r
+PyObject *\r
+PyLong_FromLong(long ival)\r
+{\r
+ PyLongObject *v;\r
+ unsigned long abs_ival;\r
+ unsigned long t; /* unsigned so >> doesn't propagate sign bit */\r
+ int ndigits = 0;\r
+ int negative = 0;\r
+\r
+ if (ival < 0) {\r
+ /* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then\r
+ ANSI C says that the result of -ival is undefined when ival\r
+ == LONG_MIN. Hence the following workaround. */\r
+ abs_ival = (unsigned long)(-1-ival) + 1;\r
+ negative = 1;\r
+ }\r
+ else {\r
+ abs_ival = (unsigned long)ival;\r
+ }\r
+\r
+ /* Count the number of Python digits.\r
+ We used to pick 5 ("big enough for anything"), but that's a\r
+ waste of time and space given that 5*15 = 75 bits are rarely\r
+ needed. */\r
+ t = abs_ival;\r
+ while (t) {\r
+ ++ndigits;\r
+ t >>= PyLong_SHIFT;\r
+ }\r
+ v = _PyLong_New(ndigits);\r
+ if (v != NULL) {\r
+ digit *p = v->ob_digit;\r
+ v->ob_size = negative ? -ndigits : ndigits;\r
+ t = abs_ival;\r
+ while (t) {\r
+ *p++ = (digit)(t & PyLong_MASK);\r
+ t >>= PyLong_SHIFT;\r
+ }\r
+ }\r
+ return (PyObject *)v;\r
+}\r
+\r
+/* Create a new long int object from a C unsigned long int */\r
+\r
+PyObject *\r
+PyLong_FromUnsignedLong(unsigned long ival)\r
+{\r
+ PyLongObject *v;\r
+ unsigned long t;\r
+ int ndigits = 0;\r
+\r
+ /* Count the number of Python digits. */\r
+ t = (unsigned long)ival;\r
+ while (t) {\r
+ ++ndigits;\r
+ t >>= PyLong_SHIFT;\r
+ }\r
+ v = _PyLong_New(ndigits);\r
+ if (v != NULL) {\r
+ digit *p = v->ob_digit;\r
+ Py_SIZE(v) = ndigits;\r
+ while (ival) {\r
+ *p++ = (digit)(ival & PyLong_MASK);\r
+ ival >>= PyLong_SHIFT;\r
+ }\r
+ }\r
+ return (PyObject *)v;\r
+}\r
+\r
+/* Create a new long int object from a C double */\r
+\r
+PyObject *\r
+PyLong_FromDouble(double dval)\r
+{\r
+ PyLongObject *v;\r
+ double frac;\r
+ int i, ndig, expo, neg;\r
+ neg = 0;\r
+ if (Py_IS_INFINITY(dval)) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "cannot convert float infinity to integer");\r
+ return NULL;\r
+ }\r
+ if (Py_IS_NAN(dval)) {\r
+ PyErr_SetString(PyExc_ValueError,\r
+ "cannot convert float NaN to integer");\r
+ return NULL;\r
+ }\r
+ if (dval < 0.0) {\r
+ neg = 1;\r
+ dval = -dval;\r
+ }\r
+ frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */\r
+ if (expo <= 0)\r
+ return PyLong_FromLong(0L);\r
+ ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */\r
+ v = _PyLong_New(ndig);\r
+ if (v == NULL)\r
+ return NULL;\r
+ frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);\r
+ for (i = ndig; --i >= 0; ) {\r
+ digit bits = (digit)frac;\r
+ v->ob_digit[i] = bits;\r
+ frac = frac - (double)bits;\r
+ frac = ldexp(frac, PyLong_SHIFT);\r
+ }\r
+ if (neg)\r
+ Py_SIZE(v) = -(Py_SIZE(v));\r
+ return (PyObject *)v;\r
+}\r
+\r
+/* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define\r
+ * anything about what happens when a signed integer operation overflows,\r
+ * and some compilers think they're doing you a favor by being "clever"\r
+ * then. The bit pattern for the largest postive signed long is\r
+ * (unsigned long)LONG_MAX, and for the smallest negative signed long\r
+ * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.\r
+ * However, some other compilers warn about applying unary minus to an\r
+ * unsigned operand. Hence the weird "0-".\r
+ */\r
+#define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)\r
+#define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)\r
+\r
+/* Get a C long int from a Python long or Python int object.\r
+ On overflow, returns -1 and sets *overflow to 1 or -1 depending\r
+ on the sign of the result. Otherwise *overflow is 0.\r
+\r
+ For other errors (e.g., type error), returns -1 and sets an error\r
+ condition.\r
+*/\r
+\r
+long\r
+PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)\r
+{\r
+ /* This version by Tim Peters */\r
+ register PyLongObject *v;\r
+ unsigned long x, prev;\r
+ long res;\r
+ Py_ssize_t i;\r
+ int sign;\r
+ int do_decref = 0; /* if nb_int was called */\r
+\r
+ *overflow = 0;\r
+ if (vv == NULL) {\r
+ PyErr_BadInternalCall();\r
+ return -1;\r
+ }\r
+\r
+ if(PyInt_Check(vv))\r
+ return PyInt_AsLong(vv);\r
+\r
+ if (!PyLong_Check(vv)) {\r
+ PyNumberMethods *nb;\r
+ nb = vv->ob_type->tp_as_number;\r
+ if (nb == NULL || nb->nb_int == NULL) {\r
+ PyErr_SetString(PyExc_TypeError,\r
+ "an integer is required");\r
+ return -1;\r
+ }\r
+ vv = (*nb->nb_int) (vv);\r
+ if (vv == NULL)\r
+ return -1;\r
+ do_decref = 1;\r
+ if(PyInt_Check(vv)) {\r
+ res = PyInt_AsLong(vv);\r
+ goto exit;\r
+ }\r
+ if (!PyLong_Check(vv)) {\r
+ Py_DECREF(vv);\r
+ PyErr_SetString(PyExc_TypeError,\r
+ "nb_int should return int object");\r
+ return -1;\r
+ }\r
+ }\r
+\r
+ res = -1;\r
+ v = (PyLongObject *)vv;\r
+ i = Py_SIZE(v);\r
+\r
+ switch (i) {\r
+ case -1:\r
+ res = -(sdigit)v->ob_digit[0];\r
+ break;\r
+ case 0:\r
+ res = 0;\r
+ break;\r
+ case 1:\r
+ res = v->ob_digit[0];\r
+ break;\r
+ default:\r
+ sign = 1;\r
+ x = 0;\r
+ if (i < 0) {\r
+ sign = -1;\r
+ i = -(i);\r
+ }\r
+ while (--i >= 0) {\r
+ prev = x;\r
+ x = (x << PyLong_SHIFT) + v->ob_digit[i];\r
+ if ((x >> PyLong_SHIFT) != prev) {\r
+ *overflow = sign;\r
+ goto exit;\r
+ }\r
+ }\r
+ /* Haven't lost any bits, but casting to long requires extra\r
+ * care (see comment above).\r
+ */\r
+ if (x <= (unsigned long)LONG_MAX) {\r
+ res = (long)x * sign;\r
+ }\r
+ else if (sign < 0 && x == PY_ABS_LONG_MIN) {\r
+ res = LONG_MIN;\r
+ }\r
+ else {\r
+ *overflow = sign;\r
+ /* res is already set to -1 */\r
+ }\r
+ }\r
+ exit:\r
+ if (do_decref) {\r
+ Py_DECREF(vv);\r
+ }\r
+ return res;\r
+}\r
+\r
+/* Get a C long int from a long int object.\r
+ Returns -1 and sets an error condition if overflow occurs. */\r
+\r
+long\r
+PyLong_AsLong(PyObject *obj)\r
+{\r
+ int overflow;\r
+ long result = PyLong_AsLongAndOverflow(obj, &overflow);\r
+ if (overflow) {\r
+ /* XXX: could be cute and give a different\r
+ message for overflow == -1 */\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "Python int too large to convert to C long");\r
+ }\r
+ return result;\r
+}\r
+\r
+/* Get a Py_ssize_t from a long int object.\r
+ Returns -1 and sets an error condition if overflow occurs. */\r
+\r
+Py_ssize_t\r
+PyLong_AsSsize_t(PyObject *vv) {\r
+ register PyLongObject *v;\r
+ size_t x, prev;\r
+ Py_ssize_t i;\r
+ int sign;\r
+\r
+ if (vv == NULL || !PyLong_Check(vv)) {\r
+ PyErr_BadInternalCall();\r
+ return -1;\r
+ }\r
+ v = (PyLongObject *)vv;\r
+ i = v->ob_size;\r
+ sign = 1;\r
+ x = 0;\r
+ if (i < 0) {\r
+ sign = -1;\r
+ i = -(i);\r
+ }\r
+ while (--i >= 0) {\r
+ prev = x;\r
+ x = (x << PyLong_SHIFT) | v->ob_digit[i];\r
+ if ((x >> PyLong_SHIFT) != prev)\r
+ goto overflow;\r
+ }\r
+ /* Haven't lost any bits, but casting to a signed type requires\r
+ * extra care (see comment above).\r
+ */\r
+ if (x <= (size_t)PY_SSIZE_T_MAX) {\r
+ return (Py_ssize_t)x * sign;\r
+ }\r
+ else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {\r
+ return PY_SSIZE_T_MIN;\r
+ }\r
+ /* else overflow */\r
+\r
+ overflow:\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "long int too large to convert to int");\r
+ return -1;\r
+}\r
+\r
+/* Get a C unsigned long int from a long int object.\r
+ Returns -1 and sets an error condition if overflow occurs. */\r
+\r
+unsigned long\r
+PyLong_AsUnsignedLong(PyObject *vv)\r
+{\r
+ register PyLongObject *v;\r
+ unsigned long x, prev;\r
+ Py_ssize_t i;\r
+\r
+ if (vv == NULL || !PyLong_Check(vv)) {\r
+ if (vv != NULL && PyInt_Check(vv)) {\r
+ long val = PyInt_AsLong(vv);\r
+ if (val < 0) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "can't convert negative value "\r
+ "to unsigned long");\r
+ return (unsigned long) -1;\r
+ }\r
+ return val;\r
+ }\r
+ PyErr_BadInternalCall();\r
+ return (unsigned long) -1;\r
+ }\r
+ v = (PyLongObject *)vv;\r
+ i = Py_SIZE(v);\r
+ x = 0;\r
+ if (i < 0) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "can't convert negative value to unsigned long");\r
+ return (unsigned long) -1;\r
+ }\r
+ while (--i >= 0) {\r
+ prev = x;\r
+ x = (x << PyLong_SHIFT) | v->ob_digit[i];\r
+ if ((x >> PyLong_SHIFT) != prev) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "long int too large to convert");\r
+ return (unsigned long) -1;\r
+ }\r
+ }\r
+ return x;\r
+}\r
+\r
+/* Get a C unsigned long int from a long int object, ignoring the high bits.\r
+ Returns -1 and sets an error condition if an error occurs. */\r
+\r
+unsigned long\r
+PyLong_AsUnsignedLongMask(PyObject *vv)\r
+{\r
+ register PyLongObject *v;\r
+ unsigned long x;\r
+ Py_ssize_t i;\r
+ int sign;\r
+\r
+ if (vv == NULL || !PyLong_Check(vv)) {\r
+ if (vv != NULL && PyInt_Check(vv))\r
+ return PyInt_AsUnsignedLongMask(vv);\r
+ PyErr_BadInternalCall();\r
+ return (unsigned long) -1;\r
+ }\r
+ v = (PyLongObject *)vv;\r
+ i = v->ob_size;\r
+ sign = 1;\r
+ x = 0;\r
+ if (i < 0) {\r
+ sign = -1;\r
+ i = -i;\r
+ }\r
+ while (--i >= 0) {\r
+ x = (x << PyLong_SHIFT) | v->ob_digit[i];\r
+ }\r
+ return x * sign;\r
+}\r
+\r
+int\r
+_PyLong_Sign(PyObject *vv)\r
+{\r
+ PyLongObject *v = (PyLongObject *)vv;\r
+\r
+ assert(v != NULL);\r
+ assert(PyLong_Check(v));\r
+\r
+ return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);\r
+}\r
+\r
+size_t\r
+_PyLong_NumBits(PyObject *vv)\r
+{\r
+ PyLongObject *v = (PyLongObject *)vv;\r
+ size_t result = 0;\r
+ Py_ssize_t ndigits;\r
+\r
+ assert(v != NULL);\r
+ assert(PyLong_Check(v));\r
+ ndigits = ABS(Py_SIZE(v));\r
+ assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);\r
+ if (ndigits > 0) {\r
+ digit msd = v->ob_digit[ndigits - 1];\r
+\r
+ result = (ndigits - 1) * PyLong_SHIFT;\r
+ if (result / PyLong_SHIFT != (size_t)(ndigits - 1))\r
+ goto Overflow;\r
+ do {\r
+ ++result;\r
+ if (result == 0)\r
+ goto Overflow;\r
+ msd >>= 1;\r
+ } while (msd);\r
+ }\r
+ return result;\r
+\r
+ Overflow:\r
+ PyErr_SetString(PyExc_OverflowError, "long has too many bits "\r
+ "to express in a platform size_t");\r
+ return (size_t)-1;\r
+}\r
+\r
+PyObject *\r
+_PyLong_FromByteArray(const unsigned char* bytes, size_t n,\r
+ int little_endian, int is_signed)\r
+{\r
+ const unsigned char* pstartbyte; /* LSB of bytes */\r
+ int incr; /* direction to move pstartbyte */\r
+ const unsigned char* pendbyte; /* MSB of bytes */\r
+ size_t numsignificantbytes; /* number of bytes that matter */\r
+ Py_ssize_t ndigits; /* number of Python long digits */\r
+ PyLongObject* v; /* result */\r
+ Py_ssize_t idigit = 0; /* next free index in v->ob_digit */\r
+\r
+ if (n == 0)\r
+ return PyLong_FromLong(0L);\r
+\r
+ if (little_endian) {\r
+ pstartbyte = bytes;\r
+ pendbyte = bytes + n - 1;\r
+ incr = 1;\r
+ }\r
+ else {\r
+ pstartbyte = bytes + n - 1;\r
+ pendbyte = bytes;\r
+ incr = -1;\r
+ }\r
+\r
+ if (is_signed)\r
+ is_signed = *pendbyte >= 0x80;\r
+\r
+ /* Compute numsignificantbytes. This consists of finding the most\r
+ significant byte. Leading 0 bytes are insignificant if the number\r
+ is positive, and leading 0xff bytes if negative. */\r
+ {\r
+ size_t i;\r
+ const unsigned char* p = pendbyte;\r
+ const int pincr = -incr; /* search MSB to LSB */\r
+ const unsigned char insignficant = is_signed ? 0xff : 0x00;\r
+\r
+ for (i = 0; i < n; ++i, p += pincr) {\r
+ if (*p != insignficant)\r
+ break;\r
+ }\r
+ numsignificantbytes = n - i;\r
+ /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so\r
+ actually has 2 significant bytes. OTOH, 0xff0001 ==\r
+ -0x00ffff, so we wouldn't *need* to bump it there; but we\r
+ do for 0xffff = -0x0001. To be safe without bothering to\r
+ check every case, bump it regardless. */\r
+ if (is_signed && numsignificantbytes < n)\r
+ ++numsignificantbytes;\r
+ }\r
+\r
+ /* How many Python long digits do we need? We have\r
+ 8*numsignificantbytes bits, and each Python long digit has\r
+ PyLong_SHIFT bits, so it's the ceiling of the quotient. */\r
+ /* catch overflow before it happens */\r
+ if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "byte array too long to convert to int");\r
+ return NULL;\r
+ }\r
+ ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;\r
+ v = _PyLong_New(ndigits);\r
+ if (v == NULL)\r
+ return NULL;\r
+\r
+ /* Copy the bits over. The tricky parts are computing 2's-comp on\r
+ the fly for signed numbers, and dealing with the mismatch between\r
+ 8-bit bytes and (probably) 15-bit Python digits.*/\r
+ {\r
+ size_t i;\r
+ twodigits carry = 1; /* for 2's-comp calculation */\r
+ twodigits accum = 0; /* sliding register */\r
+ unsigned int accumbits = 0; /* number of bits in accum */\r
+ const unsigned char* p = pstartbyte;\r
+\r
+ for (i = 0; i < numsignificantbytes; ++i, p += incr) {\r
+ twodigits thisbyte = *p;\r
+ /* Compute correction for 2's comp, if needed. */\r
+ if (is_signed) {\r
+ thisbyte = (0xff ^ thisbyte) + carry;\r
+ carry = thisbyte >> 8;\r
+ thisbyte &= 0xff;\r
+ }\r
+ /* Because we're going LSB to MSB, thisbyte is\r
+ more significant than what's already in accum,\r
+ so needs to be prepended to accum. */\r
+ accum |= (twodigits)thisbyte << accumbits;\r
+ accumbits += 8;\r
+ if (accumbits >= PyLong_SHIFT) {\r
+ /* There's enough to fill a Python digit. */\r
+ assert(idigit < ndigits);\r
+ v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);\r
+ ++idigit;\r
+ accum >>= PyLong_SHIFT;\r
+ accumbits -= PyLong_SHIFT;\r
+ assert(accumbits < PyLong_SHIFT);\r
+ }\r
+ }\r
+ assert(accumbits < PyLong_SHIFT);\r
+ if (accumbits) {\r
+ assert(idigit < ndigits);\r
+ v->ob_digit[idigit] = (digit)accum;\r
+ ++idigit;\r
+ }\r
+ }\r
+\r
+ Py_SIZE(v) = is_signed ? -idigit : idigit;\r
+ return (PyObject *)long_normalize(v);\r
+}\r
+\r
+int\r
+_PyLong_AsByteArray(PyLongObject* v,\r
+ unsigned char* bytes, size_t n,\r
+ int little_endian, int is_signed)\r
+{\r
+ Py_ssize_t i; /* index into v->ob_digit */\r
+ Py_ssize_t ndigits; /* |v->ob_size| */\r
+ twodigits accum; /* sliding register */\r
+ unsigned int accumbits; /* # bits in accum */\r
+ int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */\r
+ digit carry; /* for computing 2's-comp */\r
+ size_t j; /* # bytes filled */\r
+ unsigned char* p; /* pointer to next byte in bytes */\r
+ int pincr; /* direction to move p */\r
+\r
+ assert(v != NULL && PyLong_Check(v));\r
+\r
+ if (Py_SIZE(v) < 0) {\r
+ ndigits = -(Py_SIZE(v));\r
+ if (!is_signed) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "can't convert negative long to unsigned");\r
+ return -1;\r
+ }\r
+ do_twos_comp = 1;\r
+ }\r
+ else {\r
+ ndigits = Py_SIZE(v);\r
+ do_twos_comp = 0;\r
+ }\r
+\r
+ if (little_endian) {\r
+ p = bytes;\r
+ pincr = 1;\r
+ }\r
+ else {\r
+ p = bytes + n - 1;\r
+ pincr = -1;\r
+ }\r
+\r
+ /* Copy over all the Python digits.\r
+ It's crucial that every Python digit except for the MSD contribute\r
+ exactly PyLong_SHIFT bits to the total, so first assert that the long is\r
+ normalized. */\r
+ assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);\r
+ j = 0;\r
+ accum = 0;\r
+ accumbits = 0;\r
+ carry = do_twos_comp ? 1 : 0;\r
+ for (i = 0; i < ndigits; ++i) {\r
+ digit thisdigit = v->ob_digit[i];\r
+ if (do_twos_comp) {\r
+ thisdigit = (thisdigit ^ PyLong_MASK) + carry;\r
+ carry = thisdigit >> PyLong_SHIFT;\r
+ thisdigit &= PyLong_MASK;\r
+ }\r
+ /* Because we're going LSB to MSB, thisdigit is more\r
+ significant than what's already in accum, so needs to be\r
+ prepended to accum. */\r
+ accum |= (twodigits)thisdigit << accumbits;\r
+\r
+ /* The most-significant digit may be (probably is) at least\r
+ partly empty. */\r
+ if (i == ndigits - 1) {\r
+ /* Count # of sign bits -- they needn't be stored,\r
+ * although for signed conversion we need later to\r
+ * make sure at least one sign bit gets stored. */\r
+ digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;\r
+ while (s != 0) {\r
+ s >>= 1;\r
+ accumbits++;\r
+ }\r
+ }\r
+ else\r
+ accumbits += PyLong_SHIFT;\r
+\r
+ /* Store as many bytes as possible. */\r
+ while (accumbits >= 8) {\r
+ if (j >= n)\r
+ goto Overflow;\r
+ ++j;\r
+ *p = (unsigned char)(accum & 0xff);\r
+ p += pincr;\r
+ accumbits -= 8;\r
+ accum >>= 8;\r
+ }\r
+ }\r
+\r
+ /* Store the straggler (if any). */\r
+ assert(accumbits < 8);\r
+ assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */\r
+ if (accumbits > 0) {\r
+ if (j >= n)\r
+ goto Overflow;\r
+ ++j;\r
+ if (do_twos_comp) {\r
+ /* Fill leading bits of the byte with sign bits\r
+ (appropriately pretending that the long had an\r
+ infinite supply of sign bits). */\r
+ accum |= (~(twodigits)0) << accumbits;\r
+ }\r
+ *p = (unsigned char)(accum & 0xff);\r
+ p += pincr;\r
+ }\r
+ else if (j == n && n > 0 && is_signed) {\r
+ /* The main loop filled the byte array exactly, so the code\r
+ just above didn't get to ensure there's a sign bit, and the\r
+ loop below wouldn't add one either. Make sure a sign bit\r
+ exists. */\r
+ unsigned char msb = *(p - pincr);\r
+ int sign_bit_set = msb >= 0x80;\r
+ assert(accumbits == 0);\r
+ if (sign_bit_set == do_twos_comp)\r
+ return 0;\r
+ else\r
+ goto Overflow;\r
+ }\r
+\r
+ /* Fill remaining bytes with copies of the sign bit. */\r
+ {\r
+ unsigned char signbyte = do_twos_comp ? 0xffU : 0U;\r
+ for ( ; j < n; ++j, p += pincr)\r
+ *p = signbyte;\r
+ }\r
+\r
+ return 0;\r
+\r
+ Overflow:\r
+ PyErr_SetString(PyExc_OverflowError, "long too big to convert");\r
+ return -1;\r
+\r
+}\r
+\r
+/* Create a new long (or int) object from a C pointer */\r
+\r
+PyObject *\r
+PyLong_FromVoidPtr(void *p)\r
+{\r
+#if SIZEOF_VOID_P <= SIZEOF_LONG\r
+ if ((long)p < 0)\r
+ return PyLong_FromUnsignedLong((unsigned long)p);\r
+ return PyInt_FromLong((long)p);\r
+#else\r
+\r
+#ifndef HAVE_LONG_LONG\r
+# error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"\r
+#endif\r
+#if SIZEOF_LONG_LONG < SIZEOF_VOID_P\r
+# error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"\r
+#endif\r
+ /* optimize null pointers */\r
+ if (p == NULL)\r
+ return PyInt_FromLong(0);\r
+ return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)p);\r
+\r
+#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */\r
+}\r
+\r
+/* Get a C pointer from a long object (or an int object in some cases) */\r
+\r
+void *\r
+PyLong_AsVoidPtr(PyObject *vv)\r
+{\r
+ /* This function will allow int or long objects. If vv is neither,\r
+ then the PyLong_AsLong*() functions will raise the exception:\r
+ PyExc_SystemError, "bad argument to internal function"\r
+ */\r
+#if SIZEOF_VOID_P <= SIZEOF_LONG\r
+ long x;\r
+\r
+ if (PyInt_Check(vv))\r
+ x = PyInt_AS_LONG(vv);\r
+ else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)\r
+ x = PyLong_AsLong(vv);\r
+ else\r
+ x = PyLong_AsUnsignedLong(vv);\r
+#else\r
+\r
+#ifndef HAVE_LONG_LONG\r
+# error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"\r
+#endif\r
+#if SIZEOF_LONG_LONG < SIZEOF_VOID_P\r
+# error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"\r
+#endif\r
+ PY_LONG_LONG x;\r
+\r
+ if (PyInt_Check(vv))\r
+ x = PyInt_AS_LONG(vv);\r
+ else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)\r
+ x = PyLong_AsLongLong(vv);\r
+ else\r
+ x = PyLong_AsUnsignedLongLong(vv);\r
+\r
+#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */\r
+\r
+ if (x == -1 && PyErr_Occurred())\r
+ return NULL;\r
+ return (void *)x;\r
+}\r
+\r
+#ifdef HAVE_LONG_LONG\r
+\r
+/* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later\r
+ * rewritten to use the newer PyLong_{As,From}ByteArray API.\r
+ */\r
+\r
+#define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one\r
+#define PY_ABS_LLONG_MIN (0-(unsigned PY_LONG_LONG)PY_LLONG_MIN)\r
+\r
+/* Create a new long int object from a C PY_LONG_LONG int. */\r
+\r
+PyObject *\r
+PyLong_FromLongLong(PY_LONG_LONG ival)\r
+{\r
+ PyLongObject *v;\r
+ unsigned PY_LONG_LONG abs_ival;\r
+ unsigned PY_LONG_LONG t; /* unsigned so >> doesn't propagate sign bit */\r
+ int ndigits = 0;\r
+ int negative = 0;\r
+\r
+ if (ival < 0) {\r
+ /* avoid signed overflow on negation; see comments\r
+ in PyLong_FromLong above. */\r
+ abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;\r
+ negative = 1;\r
+ }\r
+ else {\r
+ abs_ival = (unsigned PY_LONG_LONG)ival;\r
+ }\r
+\r
+ /* Count the number of Python digits.\r
+ We used to pick 5 ("big enough for anything"), but that's a\r
+ waste of time and space given that 5*15 = 75 bits are rarely\r
+ needed. */\r
+ t = abs_ival;\r
+ while (t) {\r
+ ++ndigits;\r
+ t >>= PyLong_SHIFT;\r
+ }\r
+ v = _PyLong_New(ndigits);\r
+ if (v != NULL) {\r
+ digit *p = v->ob_digit;\r
+ Py_SIZE(v) = negative ? -ndigits : ndigits;\r
+ t = abs_ival;\r
+ while (t) {\r
+ *p++ = (digit)(t & PyLong_MASK);\r
+ t >>= PyLong_SHIFT;\r
+ }\r
+ }\r
+ return (PyObject *)v;\r
+}\r
+\r
+/* Create a new long int object from a C unsigned PY_LONG_LONG int. */\r
+\r
+PyObject *\r
+PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)\r
+{\r
+ PyLongObject *v;\r
+ unsigned PY_LONG_LONG t;\r
+ int ndigits = 0;\r
+\r
+ /* Count the number of Python digits. */\r
+ t = (unsigned PY_LONG_LONG)ival;\r
+ while (t) {\r
+ ++ndigits;\r
+ t >>= PyLong_SHIFT;\r
+ }\r
+ v = _PyLong_New(ndigits);\r
+ if (v != NULL) {\r
+ digit *p = v->ob_digit;\r
+ Py_SIZE(v) = ndigits;\r
+ while (ival) {\r
+ *p++ = (digit)(ival & PyLong_MASK);\r
+ ival >>= PyLong_SHIFT;\r
+ }\r
+ }\r
+ return (PyObject *)v;\r
+}\r
+\r
+/* Create a new long int object from a C Py_ssize_t. */\r
+\r
+PyObject *\r
+PyLong_FromSsize_t(Py_ssize_t ival)\r
+{\r
+ Py_ssize_t bytes = ival;\r
+ int one = 1;\r
+ return _PyLong_FromByteArray((unsigned char *)&bytes,\r
+ SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 1);\r
+}\r
+\r
+/* Create a new long int object from a C size_t. */\r
+\r
+PyObject *\r
+PyLong_FromSize_t(size_t ival)\r
+{\r
+ size_t bytes = ival;\r
+ int one = 1;\r
+ return _PyLong_FromByteArray((unsigned char *)&bytes,\r
+ SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 0);\r
+}\r
+\r
+/* Get a C PY_LONG_LONG int from a long int object.\r
+ Return -1 and set an error if overflow occurs. */\r
+\r
+PY_LONG_LONG\r
+PyLong_AsLongLong(PyObject *vv)\r
+{\r
+ PY_LONG_LONG bytes;\r
+ int one = 1;\r
+ int res;\r
+\r
+ if (vv == NULL) {\r
+ PyErr_BadInternalCall();\r
+ return -1;\r
+ }\r
+ if (!PyLong_Check(vv)) {\r
+ PyNumberMethods *nb;\r
+ PyObject *io;\r
+ if (PyInt_Check(vv))\r
+ return (PY_LONG_LONG)PyInt_AsLong(vv);\r
+ if ((nb = vv->ob_type->tp_as_number) == NULL ||\r
+ nb->nb_int == NULL) {\r
+ PyErr_SetString(PyExc_TypeError, "an integer is required");\r
+ return -1;\r
+ }\r
+ io = (*nb->nb_int) (vv);\r
+ if (io == NULL)\r
+ return -1;\r
+ if (PyInt_Check(io)) {\r
+ bytes = PyInt_AsLong(io);\r
+ Py_DECREF(io);\r
+ return bytes;\r
+ }\r
+ if (PyLong_Check(io)) {\r
+ bytes = PyLong_AsLongLong(io);\r
+ Py_DECREF(io);\r
+ return bytes;\r
+ }\r
+ Py_DECREF(io);\r
+ PyErr_SetString(PyExc_TypeError, "integer conversion failed");\r
+ return -1;\r
+ }\r
+\r
+ res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,\r
+ SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);\r
+\r
+ /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */\r
+ if (res < 0)\r
+ return (PY_LONG_LONG)-1;\r
+ else\r
+ return bytes;\r
+}\r
+\r
+/* Get a C unsigned PY_LONG_LONG int from a long int object.\r
+ Return -1 and set an error if overflow occurs. */\r
+\r
+unsigned PY_LONG_LONG\r
+PyLong_AsUnsignedLongLong(PyObject *vv)\r
+{\r
+ unsigned PY_LONG_LONG bytes;\r
+ int one = 1;\r
+ int res;\r
+\r
+ if (vv == NULL || !PyLong_Check(vv)) {\r
+ PyErr_BadInternalCall();\r
+ return (unsigned PY_LONG_LONG)-1;\r
+ }\r
+\r
+ res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,\r
+ SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);\r
+\r
+ /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */\r
+ if (res < 0)\r
+ return (unsigned PY_LONG_LONG)res;\r
+ else\r
+ return bytes;\r
+}\r
+\r
+/* Get a C unsigned long int from a long int object, ignoring the high bits.\r
+ Returns -1 and sets an error condition if an error occurs. */\r
+\r
+unsigned PY_LONG_LONG\r
+PyLong_AsUnsignedLongLongMask(PyObject *vv)\r
+{\r
+ register PyLongObject *v;\r
+ unsigned PY_LONG_LONG x;\r
+ Py_ssize_t i;\r
+ int sign;\r
+\r
+ if (vv == NULL || !PyLong_Check(vv)) {\r
+ PyErr_BadInternalCall();\r
+ return (unsigned long) -1;\r
+ }\r
+ v = (PyLongObject *)vv;\r
+ i = v->ob_size;\r
+ sign = 1;\r
+ x = 0;\r
+ if (i < 0) {\r
+ sign = -1;\r
+ i = -i;\r
+ }\r
+ while (--i >= 0) {\r
+ x = (x << PyLong_SHIFT) | v->ob_digit[i];\r
+ }\r
+ return x * sign;\r
+}\r
+\r
+/* Get a C long long int from a Python long or Python int object.\r
+ On overflow, returns -1 and sets *overflow to 1 or -1 depending\r
+ on the sign of the result. Otherwise *overflow is 0.\r
+\r
+ For other errors (e.g., type error), returns -1 and sets an error\r
+ condition.\r
+*/\r
+\r
+PY_LONG_LONG\r
+PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow)\r
+{\r
+ /* This version by Tim Peters */\r
+ register PyLongObject *v;\r
+ unsigned PY_LONG_LONG x, prev;\r
+ PY_LONG_LONG res;\r
+ Py_ssize_t i;\r
+ int sign;\r
+ int do_decref = 0; /* if nb_int was called */\r
+\r
+ *overflow = 0;\r
+ if (vv == NULL) {\r
+ PyErr_BadInternalCall();\r
+ return -1;\r
+ }\r
+\r
+ if (PyInt_Check(vv))\r
+ return PyInt_AsLong(vv);\r
+\r
+ if (!PyLong_Check(vv)) {\r
+ PyNumberMethods *nb;\r
+ nb = vv->ob_type->tp_as_number;\r
+ if (nb == NULL || nb->nb_int == NULL) {\r
+ PyErr_SetString(PyExc_TypeError,\r
+ "an integer is required");\r
+ return -1;\r
+ }\r
+ vv = (*nb->nb_int) (vv);\r
+ if (vv == NULL)\r
+ return -1;\r
+ do_decref = 1;\r
+ if(PyInt_Check(vv)) {\r
+ res = PyInt_AsLong(vv);\r
+ goto exit;\r
+ }\r
+ if (!PyLong_Check(vv)) {\r
+ Py_DECREF(vv);\r
+ PyErr_SetString(PyExc_TypeError,\r
+ "nb_int should return int object");\r
+ return -1;\r
+ }\r
+ }\r
+\r
+ res = -1;\r
+ v = (PyLongObject *)vv;\r
+ i = Py_SIZE(v);\r
+\r
+ switch (i) {\r
+ case -1:\r
+ res = -(sdigit)v->ob_digit[0];\r
+ break;\r
+ case 0:\r
+ res = 0;\r
+ break;\r
+ case 1:\r
+ res = v->ob_digit[0];\r
+ break;\r
+ default:\r
+ sign = 1;\r
+ x = 0;\r
+ if (i < 0) {\r
+ sign = -1;\r
+ i = -(i);\r
+ }\r
+ while (--i >= 0) {\r
+ prev = x;\r
+ x = (x << PyLong_SHIFT) + v->ob_digit[i];\r
+ if ((x >> PyLong_SHIFT) != prev) {\r
+ *overflow = sign;\r
+ goto exit;\r
+ }\r
+ }\r
+ /* Haven't lost any bits, but casting to long requires extra\r
+ * care (see comment above).\r
+ */\r
+ if (x <= (unsigned PY_LONG_LONG)PY_LLONG_MAX) {\r
+ res = (PY_LONG_LONG)x * sign;\r
+ }\r
+ else if (sign < 0 && x == PY_ABS_LLONG_MIN) {\r
+ res = PY_LLONG_MIN;\r
+ }\r
+ else {\r
+ *overflow = sign;\r
+ /* res is already set to -1 */\r
+ }\r
+ }\r
+ exit:\r
+ if (do_decref) {\r
+ Py_DECREF(vv);\r
+ }\r
+ return res;\r
+}\r
+\r
+#undef IS_LITTLE_ENDIAN\r
+\r
+#endif /* HAVE_LONG_LONG */\r
+\r
+\r
+static int\r
+convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {\r
+ if (PyLong_Check(v)) {\r
+ *a = (PyLongObject *) v;\r
+ Py_INCREF(v);\r
+ }\r
+ else if (PyInt_Check(v)) {\r
+ *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));\r
+ }\r
+ else {\r
+ return 0;\r
+ }\r
+ if (PyLong_Check(w)) {\r
+ *b = (PyLongObject *) w;\r
+ Py_INCREF(w);\r
+ }\r
+ else if (PyInt_Check(w)) {\r
+ *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));\r
+ }\r
+ else {\r
+ Py_DECREF(*a);\r
+ return 0;\r
+ }\r
+ return 1;\r
+}\r
+\r
+#define CONVERT_BINOP(v, w, a, b) \\r
+ do { \\r
+ if (!convert_binop(v, w, a, b)) { \\r
+ Py_INCREF(Py_NotImplemented); \\r
+ return Py_NotImplemented; \\r
+ } \\r
+ } while(0) \\r
+\r
+/* bits_in_digit(d) returns the unique integer k such that 2**(k-1) <= d <\r
+ 2**k if d is nonzero, else 0. */\r
+\r
+static const unsigned char BitLengthTable[32] = {\r
+ 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,\r
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5\r
+};\r
+\r
+static int\r
+bits_in_digit(digit d)\r
+{\r
+ int d_bits = 0;\r
+ while (d >= 32) {\r
+ d_bits += 6;\r
+ d >>= 6;\r
+ }\r
+ d_bits += (int)BitLengthTable[d];\r
+ return d_bits;\r
+}\r
+\r
+/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]\r
+ * is modified in place, by adding y to it. Carries are propagated as far as\r
+ * x[m-1], and the remaining carry (0 or 1) is returned.\r
+ */\r
+static digit\r
+v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)\r
+{\r
+ Py_ssize_t i;\r
+ digit carry = 0;\r
+\r
+ assert(m >= n);\r
+ for (i = 0; i < n; ++i) {\r
+ carry += x[i] + y[i];\r
+ x[i] = carry & PyLong_MASK;\r
+ carry >>= PyLong_SHIFT;\r
+ assert((carry & 1) == carry);\r
+ }\r
+ for (; carry && i < m; ++i) {\r
+ carry += x[i];\r
+ x[i] = carry & PyLong_MASK;\r
+ carry >>= PyLong_SHIFT;\r
+ assert((carry & 1) == carry);\r
+ }\r
+ return carry;\r
+}\r
+\r
+/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]\r
+ * is modified in place, by subtracting y from it. Borrows are propagated as\r
+ * far as x[m-1], and the remaining borrow (0 or 1) is returned.\r
+ */\r
+static digit\r
+v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)\r
+{\r
+ Py_ssize_t i;\r
+ digit borrow = 0;\r
+\r
+ assert(m >= n);\r
+ for (i = 0; i < n; ++i) {\r
+ borrow = x[i] - y[i] - borrow;\r
+ x[i] = borrow & PyLong_MASK;\r
+ borrow >>= PyLong_SHIFT;\r
+ borrow &= 1; /* keep only 1 sign bit */\r
+ }\r
+ for (; borrow && i < m; ++i) {\r
+ borrow = x[i] - borrow;\r
+ x[i] = borrow & PyLong_MASK;\r
+ borrow >>= PyLong_SHIFT;\r
+ borrow &= 1;\r
+ }\r
+ return borrow;\r
+}\r
+\r
+/* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT. Put\r
+ * result in z[0:m], and return the d bits shifted out of the top.\r
+ */\r
+static digit\r
+v_lshift(digit *z, digit *a, Py_ssize_t m, int d)\r
+{\r
+ Py_ssize_t i;\r
+ digit carry = 0;\r
+\r
+ assert(0 <= d && d < PyLong_SHIFT);\r
+ for (i=0; i < m; i++) {\r
+ twodigits acc = (twodigits)a[i] << d | carry;\r
+ z[i] = (digit)acc & PyLong_MASK;\r
+ carry = (digit)(acc >> PyLong_SHIFT);\r
+ }\r
+ return carry;\r
+}\r
+\r
+/* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put\r
+ * result in z[0:m], and return the d bits shifted out of the bottom.\r
+ */\r
+static digit\r
+v_rshift(digit *z, digit *a, Py_ssize_t m, int d)\r
+{\r
+ Py_ssize_t i;\r
+ digit carry = 0;\r
+ digit mask = ((digit)1 << d) - 1U;\r
+\r
+ assert(0 <= d && d < PyLong_SHIFT);\r
+ for (i=m; i-- > 0;) {\r
+ twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i];\r
+ carry = (digit)acc & mask;\r
+ z[i] = (digit)(acc >> d);\r
+ }\r
+ return carry;\r
+}\r
+\r
+/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient\r
+ in pout, and returning the remainder. pin and pout point at the LSD.\r
+ It's OK for pin == pout on entry, which saves oodles of mallocs/frees in\r
+ _PyLong_Format, but that should be done with great care since longs are\r
+ immutable. */\r
+\r
+static digit\r
+inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)\r
+{\r
+ twodigits rem = 0;\r
+\r
+ assert(n > 0 && n <= PyLong_MASK);\r
+ pin += size;\r
+ pout += size;\r
+ while (--size >= 0) {\r
+ digit hi;\r
+ rem = (rem << PyLong_SHIFT) | *--pin;\r
+ *--pout = hi = (digit)(rem / n);\r
+ rem -= (twodigits)hi * n;\r
+ }\r
+ return (digit)rem;\r
+}\r
+\r
+/* Divide a long integer by a digit, returning both the quotient\r
+ (as function result) and the remainder (through *prem).\r
+ The sign of a is ignored; n should not be zero. */\r
+\r
+static PyLongObject *\r
+divrem1(PyLongObject *a, digit n, digit *prem)\r
+{\r
+ const Py_ssize_t size = ABS(Py_SIZE(a));\r
+ PyLongObject *z;\r
+\r
+ assert(n > 0 && n <= PyLong_MASK);\r
+ z = _PyLong_New(size);\r
+ if (z == NULL)\r
+ return NULL;\r
+ *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);\r
+ return long_normalize(z);\r
+}\r
+\r
+/* Convert a long integer to a base 10 string. Returns a new non-shared\r
+ string. (Return value is non-shared so that callers can modify the\r
+ returned value if necessary.) */\r
+\r
+static PyObject *\r
+long_to_decimal_string(PyObject *aa, int addL)\r
+{\r
+ PyLongObject *scratch, *a;\r
+ PyObject *str;\r
+ Py_ssize_t size, strlen, size_a, i, j;\r
+ digit *pout, *pin, rem, tenpow;\r
+ char *p;\r
+ int negative;\r
+\r
+ a = (PyLongObject *)aa;\r
+ if (a == NULL || !PyLong_Check(a)) {\r
+ PyErr_BadInternalCall();\r
+ return NULL;\r
+ }\r
+ size_a = ABS(Py_SIZE(a));\r
+ negative = Py_SIZE(a) < 0;\r
+\r
+ /* quick and dirty upper bound for the number of digits\r
+ required to express a in base _PyLong_DECIMAL_BASE:\r
+\r
+ #digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))\r
+\r
+ But log2(a) < size_a * PyLong_SHIFT, and\r
+ log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT\r
+ > 3 * _PyLong_DECIMAL_SHIFT\r
+ */\r
+ if (size_a > PY_SSIZE_T_MAX / PyLong_SHIFT) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "long is too large to format");\r
+ return NULL;\r
+ }\r
+ /* the expression size_a * PyLong_SHIFT is now safe from overflow */\r
+ size = 1 + size_a * PyLong_SHIFT / (3 * _PyLong_DECIMAL_SHIFT);\r
+ scratch = _PyLong_New(size);\r
+ if (scratch == NULL)\r
+ return NULL;\r
+\r
+ /* convert array of base _PyLong_BASE digits in pin to an array of\r
+ base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,\r
+ Volume 2 (3rd edn), section 4.4, Method 1b). */\r
+ pin = a->ob_digit;\r
+ pout = scratch->ob_digit;\r
+ size = 0;\r
+ for (i = size_a; --i >= 0; ) {\r
+ digit hi = pin[i];\r
+ for (j = 0; j < size; j++) {\r
+ twodigits z = (twodigits)pout[j] << PyLong_SHIFT | hi;\r
+ hi = (digit)(z / _PyLong_DECIMAL_BASE);\r
+ pout[j] = (digit)(z - (twodigits)hi *\r
+ _PyLong_DECIMAL_BASE);\r
+ }\r
+ while (hi) {\r
+ pout[size++] = hi % _PyLong_DECIMAL_BASE;\r
+ hi /= _PyLong_DECIMAL_BASE;\r
+ }\r
+ /* check for keyboard interrupt */\r
+ SIGCHECK({\r
+ Py_DECREF(scratch);\r
+ return NULL;\r
+ });\r
+ }\r
+ /* pout should have at least one digit, so that the case when a = 0\r
+ works correctly */\r
+ if (size == 0)\r
+ pout[size++] = 0;\r
+\r
+ /* calculate exact length of output string, and allocate */\r
+ strlen = (addL != 0) + negative +\r
+ 1 + (size - 1) * _PyLong_DECIMAL_SHIFT;\r
+ tenpow = 10;\r
+ rem = pout[size-1];\r
+ while (rem >= tenpow) {\r
+ tenpow *= 10;\r
+ strlen++;\r
+ }\r
+ str = PyString_FromStringAndSize(NULL, strlen);\r
+ if (str == NULL) {\r
+ Py_DECREF(scratch);\r
+ return NULL;\r
+ }\r
+\r
+ /* fill the string right-to-left */\r
+ p = PyString_AS_STRING(str) + strlen;\r
+ *p = '\0';\r
+ if (addL)\r
+ *--p = 'L';\r
+ /* pout[0] through pout[size-2] contribute exactly\r
+ _PyLong_DECIMAL_SHIFT digits each */\r
+ for (i=0; i < size - 1; i++) {\r
+ rem = pout[i];\r
+ for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) {\r
+ *--p = '0' + rem % 10;\r
+ rem /= 10;\r
+ }\r
+ }\r
+ /* pout[size-1]: always produce at least one decimal digit */\r
+ rem = pout[i];\r
+ do {\r
+ *--p = '0' + rem % 10;\r
+ rem /= 10;\r
+ } while (rem != 0);\r
+\r
+ /* and sign */\r
+ if (negative)\r
+ *--p = '-';\r
+\r
+ /* check we've counted correctly */\r
+ assert(p == PyString_AS_STRING(str));\r
+ Py_DECREF(scratch);\r
+ return (PyObject *)str;\r
+}\r
+\r
+/* Convert the long to a string object with given base,\r
+ appending a base prefix of 0[box] if base is 2, 8 or 16.\r
+ Add a trailing "L" if addL is non-zero.\r
+ If newstyle is zero, then use the pre-2.6 behavior of octal having\r
+ a leading "0", instead of the prefix "0o" */\r
+PyAPI_FUNC(PyObject *)\r
+_PyLong_Format(PyObject *aa, int base, int addL, int newstyle)\r
+{\r
+ register PyLongObject *a = (PyLongObject *)aa;\r
+ PyStringObject *str;\r
+ Py_ssize_t i, sz;\r
+ Py_ssize_t size_a;\r
+ char *p;\r
+ int bits;\r
+ char sign = '\0';\r
+\r
+ if (base == 10)\r
+ return long_to_decimal_string((PyObject *)a, addL);\r
+\r
+ if (a == NULL || !PyLong_Check(a)) {\r
+ PyErr_BadInternalCall();\r
+ return NULL;\r
+ }\r
+ assert(base >= 2 && base <= 36);\r
+ size_a = ABS(Py_SIZE(a));\r
+\r
+ /* Compute a rough upper bound for the length of the string */\r
+ i = base;\r
+ bits = 0;\r
+ while (i > 1) {\r
+ ++bits;\r
+ i >>= 1;\r
+ }\r
+ i = 5 + (addL ? 1 : 0);\r
+ /* ensure we don't get signed overflow in sz calculation */\r
+ if (size_a > (PY_SSIZE_T_MAX - i) / PyLong_SHIFT) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "long is too large to format");\r
+ return NULL;\r
+ }\r
+ sz = i + 1 + (size_a * PyLong_SHIFT - 1) / bits;\r
+ assert(sz >= 0);\r
+ str = (PyStringObject *) PyString_FromStringAndSize((char *)0, sz);\r
+ if (str == NULL)\r
+ return NULL;\r
+ p = PyString_AS_STRING(str) + sz;\r
+ *p = '\0';\r
+ if (addL)\r
+ *--p = 'L';\r
+ if (a->ob_size < 0)\r
+ sign = '-';\r
+\r
+ if (a->ob_size == 0) {\r
+ *--p = '0';\r
+ }\r
+ else if ((base & (base - 1)) == 0) {\r
+ /* JRH: special case for power-of-2 bases */\r
+ twodigits accum = 0;\r
+ int accumbits = 0; /* # of bits in accum */\r
+ int basebits = 1; /* # of bits in base-1 */\r
+ i = base;\r
+ while ((i >>= 1) > 1)\r
+ ++basebits;\r
+\r
+ for (i = 0; i < size_a; ++i) {\r
+ accum |= (twodigits)a->ob_digit[i] << accumbits;\r
+ accumbits += PyLong_SHIFT;\r
+ assert(accumbits >= basebits);\r
+ do {\r
+ char cdigit = (char)(accum & (base - 1));\r
+ cdigit += (cdigit < 10) ? '0' : 'a'-10;\r
+ assert(p > PyString_AS_STRING(str));\r
+ *--p = cdigit;\r
+ accumbits -= basebits;\r
+ accum >>= basebits;\r
+ } while (i < size_a-1 ? accumbits >= basebits : accum > 0);\r
+ }\r
+ }\r
+ else {\r
+ /* Not 0, and base not a power of 2. Divide repeatedly by\r
+ base, but for speed use the highest power of base that\r
+ fits in a digit. */\r
+ Py_ssize_t size = size_a;\r
+ digit *pin = a->ob_digit;\r
+ PyLongObject *scratch;\r
+ /* powbasw <- largest power of base that fits in a digit. */\r
+ digit powbase = base; /* powbase == base ** power */\r
+ int power = 1;\r
+ for (;;) {\r
+ twodigits newpow = powbase * (twodigits)base;\r
+ if (newpow >> PyLong_SHIFT)\r
+ /* doesn't fit in a digit */\r
+ break;\r
+ powbase = (digit)newpow;\r
+ ++power;\r
+ }\r
+\r
+ /* Get a scratch area for repeated division. */\r
+ scratch = _PyLong_New(size);\r
+ if (scratch == NULL) {\r
+ Py_DECREF(str);\r
+ return NULL;\r
+ }\r
+\r
+ /* Repeatedly divide by powbase. */\r
+ do {\r
+ int ntostore = power;\r
+ digit rem = inplace_divrem1(scratch->ob_digit,\r
+ pin, size, powbase);\r
+ pin = scratch->ob_digit; /* no need to use a again */\r
+ if (pin[size - 1] == 0)\r
+ --size;\r
+ SIGCHECK({\r
+ Py_DECREF(scratch);\r
+ Py_DECREF(str);\r
+ return NULL;\r
+ });\r
+\r
+ /* Break rem into digits. */\r
+ assert(ntostore > 0);\r
+ do {\r
+ digit nextrem = (digit)(rem / base);\r
+ char c = (char)(rem - nextrem * base);\r
+ assert(p > PyString_AS_STRING(str));\r
+ c += (c < 10) ? '0' : 'a'-10;\r
+ *--p = c;\r
+ rem = nextrem;\r
+ --ntostore;\r
+ /* Termination is a bit delicate: must not\r
+ store leading zeroes, so must get out if\r
+ remaining quotient and rem are both 0. */\r
+ } while (ntostore && (size || rem));\r
+ } while (size != 0);\r
+ Py_DECREF(scratch);\r
+ }\r
+\r
+ if (base == 2) {\r
+ *--p = 'b';\r
+ *--p = '0';\r
+ }\r
+ else if (base == 8) {\r
+ if (newstyle) {\r
+ *--p = 'o';\r
+ *--p = '0';\r
+ }\r
+ else\r
+ if (size_a != 0)\r
+ *--p = '0';\r
+ }\r
+ else if (base == 16) {\r
+ *--p = 'x';\r
+ *--p = '0';\r
+ }\r
+ else if (base != 10) {\r
+ *--p = '#';\r
+ *--p = '0' + base%10;\r
+ if (base > 10)\r
+ *--p = '0' + base/10;\r
+ }\r
+ if (sign)\r
+ *--p = sign;\r
+ if (p != PyString_AS_STRING(str)) {\r
+ char *q = PyString_AS_STRING(str);\r
+ assert(p > q);\r
+ do {\r
+ } while ((*q++ = *p++) != '\0');\r
+ q--;\r
+ _PyString_Resize((PyObject **)&str,\r
+ (Py_ssize_t) (q - PyString_AS_STRING(str)));\r
+ }\r
+ return (PyObject *)str;\r
+}\r
+\r
+/* Table of digit values for 8-bit string -> integer conversion.\r
+ * '0' maps to 0, ..., '9' maps to 9.\r
+ * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.\r
+ * All other indices map to 37.\r
+ * Note that when converting a base B string, a char c is a legitimate\r
+ * base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B.\r
+ */\r
+int _PyLong_DigitValue[256] = {\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,\r
+ 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,\r
+ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,\r
+ 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,\r
+ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+ 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,\r
+};\r
+\r
+/* *str points to the first digit in a string of base `base` digits. base\r
+ * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first\r
+ * non-digit (which may be *str!). A normalized long is returned.\r
+ * The point to this routine is that it takes time linear in the number of\r
+ * string characters.\r
+ */\r
+static PyLongObject *\r
+long_from_binary_base(char **str, int base)\r
+{\r
+ char *p = *str;\r
+ char *start = p;\r
+ int bits_per_char;\r
+ Py_ssize_t n;\r
+ PyLongObject *z;\r
+ twodigits accum;\r
+ int bits_in_accum;\r
+ digit *pdigit;\r
+\r
+ assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);\r
+ n = base;\r
+ for (bits_per_char = -1; n; ++bits_per_char)\r
+ n >>= 1;\r
+ /* n <- total # of bits needed, while setting p to end-of-string */\r
+ while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)\r
+ ++p;\r
+ *str = p;\r
+ /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */\r
+ n = (p - start) * bits_per_char + PyLong_SHIFT - 1;\r
+ if (n / bits_per_char < p - start) {\r
+ PyErr_SetString(PyExc_ValueError,\r
+ "long string too large to convert");\r
+ return NULL;\r
+ }\r
+ n = n / PyLong_SHIFT;\r
+ z = _PyLong_New(n);\r
+ if (z == NULL)\r
+ return NULL;\r
+ /* Read string from right, and fill in long from left; i.e.,\r
+ * from least to most significant in both.\r
+ */\r
+ accum = 0;\r
+ bits_in_accum = 0;\r
+ pdigit = z->ob_digit;\r
+ while (--p >= start) {\r
+ int k = _PyLong_DigitValue[Py_CHARMASK(*p)];\r
+ assert(k >= 0 && k < base);\r
+ accum |= (twodigits)k << bits_in_accum;\r
+ bits_in_accum += bits_per_char;\r
+ if (bits_in_accum >= PyLong_SHIFT) {\r
+ *pdigit++ = (digit)(accum & PyLong_MASK);\r
+ assert(pdigit - z->ob_digit <= n);\r
+ accum >>= PyLong_SHIFT;\r
+ bits_in_accum -= PyLong_SHIFT;\r
+ assert(bits_in_accum < PyLong_SHIFT);\r
+ }\r
+ }\r
+ if (bits_in_accum) {\r
+ assert(bits_in_accum <= PyLong_SHIFT);\r
+ *pdigit++ = (digit)accum;\r
+ assert(pdigit - z->ob_digit <= n);\r
+ }\r
+ while (pdigit - z->ob_digit < n)\r
+ *pdigit++ = 0;\r
+ return long_normalize(z);\r
+}\r
+\r
+PyObject *\r
+PyLong_FromString(char *str, char **pend, int base)\r
+{\r
+ int sign = 1;\r
+ char *start, *orig_str = str;\r
+ PyLongObject *z;\r
+ PyObject *strobj, *strrepr;\r
+ Py_ssize_t slen;\r
+\r
+ if ((base != 0 && base < 2) || base > 36) {\r
+ PyErr_SetString(PyExc_ValueError,\r
+ "long() arg 2 must be >= 2 and <= 36");\r
+ return NULL;\r
+ }\r
+ while (*str != '\0' && isspace(Py_CHARMASK(*str)))\r
+ str++;\r
+ if (*str == '+')\r
+ ++str;\r
+ else if (*str == '-') {\r
+ ++str;\r
+ sign = -1;\r
+ }\r
+ while (*str != '\0' && isspace(Py_CHARMASK(*str)))\r
+ str++;\r
+ if (base == 0) {\r
+ /* No base given. Deduce the base from the contents\r
+ of the string */\r
+ if (str[0] != '0')\r
+ base = 10;\r
+ else if (str[1] == 'x' || str[1] == 'X')\r
+ base = 16;\r
+ else if (str[1] == 'o' || str[1] == 'O')\r
+ base = 8;\r
+ else if (str[1] == 'b' || str[1] == 'B')\r
+ base = 2;\r
+ else\r
+ /* "old" (C-style) octal literal, still valid in\r
+ 2.x, although illegal in 3.x */\r
+ base = 8;\r
+ }\r
+ /* Whether or not we were deducing the base, skip leading chars\r
+ as needed */\r
+ if (str[0] == '0' &&\r
+ ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||\r
+ (base == 8 && (str[1] == 'o' || str[1] == 'O')) ||\r
+ (base == 2 && (str[1] == 'b' || str[1] == 'B'))))\r
+ str += 2;\r
+\r
+ start = str;\r
+ if ((base & (base - 1)) == 0)\r
+ z = long_from_binary_base(&str, base);\r
+ else {\r
+/***\r
+Binary bases can be converted in time linear in the number of digits, because\r
+Python's representation base is binary. Other bases (including decimal!) use\r
+the simple quadratic-time algorithm below, complicated by some speed tricks.\r
+\r
+First some math: the largest integer that can be expressed in N base-B digits\r
+is B**N-1. Consequently, if we have an N-digit input in base B, the worst-\r
+case number of Python digits needed to hold it is the smallest integer n s.t.\r
+\r
+ PyLong_BASE**n-1 >= B**N-1 [or, adding 1 to both sides]\r
+ PyLong_BASE**n >= B**N [taking logs to base PyLong_BASE]\r
+ n >= log(B**N)/log(PyLong_BASE) = N * log(B)/log(PyLong_BASE)\r
+\r
+The static array log_base_PyLong_BASE[base] == log(base)/log(PyLong_BASE) so\r
+we can compute this quickly. A Python long with that much space is reserved\r
+near the start, and the result is computed into it.\r
+\r
+The input string is actually treated as being in base base**i (i.e., i digits\r
+are processed at a time), where two more static arrays hold:\r
+\r
+ convwidth_base[base] = the largest integer i such that\r
+ base**i <= PyLong_BASE\r
+ convmultmax_base[base] = base ** convwidth_base[base]\r
+\r
+The first of these is the largest i such that i consecutive input digits\r
+must fit in a single Python digit. The second is effectively the input\r
+base we're really using.\r
+\r
+Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base\r
+convmultmax_base[base], the result is "simply"\r
+\r
+ (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1\r
+\r
+where B = convmultmax_base[base].\r
+\r
+Error analysis: as above, the number of Python digits `n` needed is worst-\r
+case\r
+\r
+ n >= N * log(B)/log(PyLong_BASE)\r
+\r
+where `N` is the number of input digits in base `B`. This is computed via\r
+\r
+ size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;\r
+\r
+below. Two numeric concerns are how much space this can waste, and whether\r
+the computed result can be too small. To be concrete, assume PyLong_BASE =\r
+2**15, which is the default (and it's unlikely anyone changes that).\r
+\r
+Waste isn't a problem: provided the first input digit isn't 0, the difference\r
+between the worst-case input with N digits and the smallest input with N\r
+digits is about a factor of B, but B is small compared to PyLong_BASE so at\r
+most one allocated Python digit can remain unused on that count. If\r
+N*log(B)/log(PyLong_BASE) is mathematically an exact integer, then truncating\r
+that and adding 1 returns a result 1 larger than necessary. However, that\r
+can't happen: whenever B is a power of 2, long_from_binary_base() is called\r
+instead, and it's impossible for B**i to be an integer power of 2**15 when B\r
+is not a power of 2 (i.e., it's impossible for N*log(B)/log(PyLong_BASE) to be\r
+an exact integer when B is not a power of 2, since B**i has a prime factor\r
+other than 2 in that case, but (2**15)**j's only prime factor is 2).\r
+\r
+The computed result can be too small if the true value of\r
+N*log(B)/log(PyLong_BASE) is a little bit larger than an exact integer, but\r
+due to roundoff errors (in computing log(B), log(PyLong_BASE), their quotient,\r
+and/or multiplying that by N) yields a numeric result a little less than that\r
+integer. Unfortunately, "how close can a transcendental function get to an\r
+integer over some range?" questions are generally theoretically intractable.\r
+Computer analysis via continued fractions is practical: expand\r
+log(B)/log(PyLong_BASE) via continued fractions, giving a sequence i/j of "the\r
+best" rational approximations. Then j*log(B)/log(PyLong_BASE) is\r
+approximately equal to (the integer) i. This shows that we can get very close\r
+to being in trouble, but very rarely. For example, 76573 is a denominator in\r
+one of the continued-fraction approximations to log(10)/log(2**15), and\r
+indeed:\r
+\r
+ >>> log(10)/log(2**15)*76573\r
+ 16958.000000654003\r
+\r
+is very close to an integer. If we were working with IEEE single-precision,\r
+rounding errors could kill us. Finding worst cases in IEEE double-precision\r
+requires better-than-double-precision log() functions, and Tim didn't bother.\r
+Instead the code checks to see whether the allocated space is enough as each\r
+new Python digit is added, and copies the whole thing to a larger long if not.\r
+This should happen extremely rarely, and in fact I don't have a test case\r
+that triggers it(!). Instead the code was tested by artificially allocating\r
+just 1 digit at the start, so that the copying code was exercised for every\r
+digit beyond the first.\r
+***/\r
+ register twodigits c; /* current input character */\r
+ Py_ssize_t size_z;\r
+ int i;\r
+ int convwidth;\r
+ twodigits convmultmax, convmult;\r
+ digit *pz, *pzstop;\r
+ char* scan;\r
+\r
+ static double log_base_PyLong_BASE[37] = {0.0e0,};\r
+ static int convwidth_base[37] = {0,};\r
+ static twodigits convmultmax_base[37] = {0,};\r
+\r
+ if (log_base_PyLong_BASE[base] == 0.0) {\r
+ twodigits convmax = base;\r
+ int i = 1;\r
+\r
+ log_base_PyLong_BASE[base] = (log((double)base) /\r
+ log((double)PyLong_BASE));\r
+ for (;;) {\r
+ twodigits next = convmax * base;\r
+ if (next > PyLong_BASE)\r
+ break;\r
+ convmax = next;\r
+ ++i;\r
+ }\r
+ convmultmax_base[base] = convmax;\r
+ assert(i > 0);\r
+ convwidth_base[base] = i;\r
+ }\r
+\r
+ /* Find length of the string of numeric characters. */\r
+ scan = str;\r
+ while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)\r
+ ++scan;\r
+\r
+ /* Create a long object that can contain the largest possible\r
+ * integer with this base and length. Note that there's no\r
+ * need to initialize z->ob_digit -- no slot is read up before\r
+ * being stored into.\r
+ */\r
+ size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;\r
+ /* Uncomment next line to test exceedingly rare copy code */\r
+ /* size_z = 1; */\r
+ assert(size_z > 0);\r
+ z = _PyLong_New(size_z);\r
+ if (z == NULL)\r
+ return NULL;\r
+ Py_SIZE(z) = 0;\r
+\r
+ /* `convwidth` consecutive input digits are treated as a single\r
+ * digit in base `convmultmax`.\r
+ */\r
+ convwidth = convwidth_base[base];\r
+ convmultmax = convmultmax_base[base];\r
+\r
+ /* Work ;-) */\r
+ while (str < scan) {\r
+ /* grab up to convwidth digits from the input string */\r
+ c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];\r
+ for (i = 1; i < convwidth && str != scan; ++i, ++str) {\r
+ c = (twodigits)(c * base +\r
+ _PyLong_DigitValue[Py_CHARMASK(*str)]);\r
+ assert(c < PyLong_BASE);\r
+ }\r
+\r
+ convmult = convmultmax;\r
+ /* Calculate the shift only if we couldn't get\r
+ * convwidth digits.\r
+ */\r
+ if (i != convwidth) {\r
+ convmult = base;\r
+ for ( ; i > 1; --i)\r
+ convmult *= base;\r
+ }\r
+\r
+ /* Multiply z by convmult, and add c. */\r
+ pz = z->ob_digit;\r
+ pzstop = pz + Py_SIZE(z);\r
+ for (; pz < pzstop; ++pz) {\r
+ c += (twodigits)*pz * convmult;\r
+ *pz = (digit)(c & PyLong_MASK);\r
+ c >>= PyLong_SHIFT;\r
+ }\r
+ /* carry off the current end? */\r
+ if (c) {\r
+ assert(c < PyLong_BASE);\r
+ if (Py_SIZE(z) < size_z) {\r
+ *pz = (digit)c;\r
+ ++Py_SIZE(z);\r
+ }\r
+ else {\r
+ PyLongObject *tmp;\r
+ /* Extremely rare. Get more space. */\r
+ assert(Py_SIZE(z) == size_z);\r
+ tmp = _PyLong_New(size_z + 1);\r
+ if (tmp == NULL) {\r
+ Py_DECREF(z);\r
+ return NULL;\r
+ }\r
+ memcpy(tmp->ob_digit,\r
+ z->ob_digit,\r
+ sizeof(digit) * size_z);\r
+ Py_DECREF(z);\r
+ z = tmp;\r
+ z->ob_digit[size_z] = (digit)c;\r
+ ++size_z;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ if (z == NULL)\r
+ return NULL;\r
+ if (str == start)\r
+ goto onError;\r
+ if (sign < 0)\r
+ Py_SIZE(z) = -(Py_SIZE(z));\r
+ if (*str == 'L' || *str == 'l')\r
+ str++;\r
+ while (*str && isspace(Py_CHARMASK(*str)))\r
+ str++;\r
+ if (*str != '\0')\r
+ goto onError;\r
+ if (pend)\r
+ *pend = str;\r
+ return (PyObject *) z;\r
+\r
+ onError:\r
+ Py_XDECREF(z);\r
+ slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;\r
+ strobj = PyString_FromStringAndSize(orig_str, slen);\r
+ if (strobj == NULL)\r
+ return NULL;\r
+ strrepr = PyObject_Repr(strobj);\r
+ Py_DECREF(strobj);\r
+ if (strrepr == NULL)\r
+ return NULL;\r
+ PyErr_Format(PyExc_ValueError,\r
+ "invalid literal for long() with base %d: %s",\r
+ base, PyString_AS_STRING(strrepr));\r
+ Py_DECREF(strrepr);\r
+ return NULL;\r
+}\r
+\r
+#ifdef Py_USING_UNICODE\r
+PyObject *\r
+PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)\r
+{\r
+ PyObject *result;\r
+ char *buffer = (char *)PyMem_MALLOC(length+1);\r
+\r
+ if (buffer == NULL)\r
+ return NULL;\r
+\r
+ if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {\r
+ PyMem_FREE(buffer);\r
+ return NULL;\r
+ }\r
+ result = PyLong_FromString(buffer, NULL, base);\r
+ PyMem_FREE(buffer);\r
+ return result;\r
+}\r
+#endif\r
+\r
+/* forward */\r
+static PyLongObject *x_divrem\r
+ (PyLongObject *, PyLongObject *, PyLongObject **);\r
+static PyObject *long_long(PyObject *v);\r
+\r
+/* Long division with remainder, top-level routine */\r
+\r
+static int\r
+long_divrem(PyLongObject *a, PyLongObject *b,\r
+ PyLongObject **pdiv, PyLongObject **prem)\r
+{\r
+ Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));\r
+ PyLongObject *z;\r
+\r
+ if (size_b == 0) {\r
+ PyErr_SetString(PyExc_ZeroDivisionError,\r
+ "long division or modulo by zero");\r
+ return -1;\r
+ }\r
+ if (size_a < size_b ||\r
+ (size_a == size_b &&\r
+ a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {\r
+ /* |a| < |b|. */\r
+ *pdiv = _PyLong_New(0);\r
+ if (*pdiv == NULL)\r
+ return -1;\r
+ Py_INCREF(a);\r
+ *prem = (PyLongObject *) a;\r
+ return 0;\r
+ }\r
+ if (size_b == 1) {\r
+ digit rem = 0;\r
+ z = divrem1(a, b->ob_digit[0], &rem);\r
+ if (z == NULL)\r
+ return -1;\r
+ *prem = (PyLongObject *) PyLong_FromLong((long)rem);\r
+ if (*prem == NULL) {\r
+ Py_DECREF(z);\r
+ return -1;\r
+ }\r
+ }\r
+ else {\r
+ z = x_divrem(a, b, prem);\r
+ if (z == NULL)\r
+ return -1;\r
+ }\r
+ /* Set the signs.\r
+ The quotient z has the sign of a*b;\r
+ the remainder r has the sign of a,\r
+ so a = b*z + r. */\r
+ if ((a->ob_size < 0) != (b->ob_size < 0))\r
+ z->ob_size = -(z->ob_size);\r
+ if (a->ob_size < 0 && (*prem)->ob_size != 0)\r
+ (*prem)->ob_size = -((*prem)->ob_size);\r
+ *pdiv = z;\r
+ return 0;\r
+}\r
+\r
+/* Unsigned long division with remainder -- the algorithm. The arguments v1\r
+ and w1 should satisfy 2 <= ABS(Py_SIZE(w1)) <= ABS(Py_SIZE(v1)). */\r
+\r
+static PyLongObject *\r
+x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)\r
+{\r
+ PyLongObject *v, *w, *a;\r
+ Py_ssize_t i, k, size_v, size_w;\r
+ int d;\r
+ digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;\r
+ twodigits vv;\r
+ sdigit zhi;\r
+ stwodigits z;\r
+\r
+ /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd\r
+ edn.), section 4.3.1, Algorithm D], except that we don't explicitly\r
+ handle the special case when the initial estimate q for a quotient\r
+ digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and\r
+ that won't overflow a digit. */\r
+\r
+ /* allocate space; w will also be used to hold the final remainder */\r
+ size_v = ABS(Py_SIZE(v1));\r
+ size_w = ABS(Py_SIZE(w1));\r
+ assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */\r
+ v = _PyLong_New(size_v+1);\r
+ if (v == NULL) {\r
+ *prem = NULL;\r
+ return NULL;\r
+ }\r
+ w = _PyLong_New(size_w);\r
+ if (w == NULL) {\r
+ Py_DECREF(v);\r
+ *prem = NULL;\r
+ return NULL;\r
+ }\r
+\r
+ /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.\r
+ shift v1 left by the same amount. Results go into w and v. */\r
+ d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);\r
+ carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);\r
+ assert(carry == 0);\r
+ carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);\r
+ if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {\r
+ v->ob_digit[size_v] = carry;\r
+ size_v++;\r
+ }\r
+\r
+ /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has\r
+ at most (and usually exactly) k = size_v - size_w digits. */\r
+ k = size_v - size_w;\r
+ assert(k >= 0);\r
+ a = _PyLong_New(k);\r
+ if (a == NULL) {\r
+ Py_DECREF(w);\r
+ Py_DECREF(v);\r
+ *prem = NULL;\r
+ return NULL;\r
+ }\r
+ v0 = v->ob_digit;\r
+ w0 = w->ob_digit;\r
+ wm1 = w0[size_w-1];\r
+ wm2 = w0[size_w-2];\r
+ for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {\r
+ /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving\r
+ single-digit quotient q, remainder in vk[0:size_w]. */\r
+\r
+ SIGCHECK({\r
+ Py_DECREF(a);\r
+ Py_DECREF(w);\r
+ Py_DECREF(v);\r
+ *prem = NULL;\r
+ return NULL;\r
+ });\r
+\r
+ /* estimate quotient digit q; may overestimate by 1 (rare) */\r
+ vtop = vk[size_w];\r
+ assert(vtop <= wm1);\r
+ vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1];\r
+ q = (digit)(vv / wm1);\r
+ r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */\r
+ while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)\r
+ | vk[size_w-2])) {\r
+ --q;\r
+ r += wm1;\r
+ if (r >= PyLong_BASE)\r
+ break;\r
+ }\r
+ assert(q <= PyLong_BASE);\r
+\r
+ /* subtract q*w0[0:size_w] from vk[0:size_w+1] */\r
+ zhi = 0;\r
+ for (i = 0; i < size_w; ++i) {\r
+ /* invariants: -PyLong_BASE <= -q <= zhi <= 0;\r
+ -PyLong_BASE * q <= z < PyLong_BASE */\r
+ z = (sdigit)vk[i] + zhi -\r
+ (stwodigits)q * (stwodigits)w0[i];\r
+ vk[i] = (digit)z & PyLong_MASK;\r
+ zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,\r
+ z, PyLong_SHIFT);\r
+ }\r
+\r
+ /* add w back if q was too large (this branch taken rarely) */\r
+ assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0);\r
+ if ((sdigit)vtop + zhi < 0) {\r
+ carry = 0;\r
+ for (i = 0; i < size_w; ++i) {\r
+ carry += vk[i] + w0[i];\r
+ vk[i] = carry & PyLong_MASK;\r
+ carry >>= PyLong_SHIFT;\r
+ }\r
+ --q;\r
+ }\r
+\r
+ /* store quotient digit */\r
+ assert(q < PyLong_BASE);\r
+ *--ak = q;\r
+ }\r
+\r
+ /* unshift remainder; we reuse w to store the result */\r
+ carry = v_rshift(w0, v0, size_w, d);\r
+ assert(carry==0);\r
+ Py_DECREF(v);\r
+\r
+ *prem = long_normalize(w);\r
+ return long_normalize(a);\r
+}\r
+\r
+/* For a nonzero PyLong a, express a in the form x * 2**e, with 0.5 <=\r
+ abs(x) < 1.0 and e >= 0; return x and put e in *e. Here x is\r
+ rounded to DBL_MANT_DIG significant bits using round-half-to-even.\r
+ If a == 0, return 0.0 and set *e = 0. If the resulting exponent\r
+ e is larger than PY_SSIZE_T_MAX, raise OverflowError and return\r
+ -1.0. */\r
+\r
+/* attempt to define 2.0**DBL_MANT_DIG as a compile-time constant */\r
+#if DBL_MANT_DIG == 53\r
+#define EXP2_DBL_MANT_DIG 9007199254740992.0\r
+#else\r
+#define EXP2_DBL_MANT_DIG (ldexp(1.0, DBL_MANT_DIG))\r
+#endif\r
+\r
+double\r
+_PyLong_Frexp(PyLongObject *a, Py_ssize_t *e)\r
+{\r
+ Py_ssize_t a_size, a_bits, shift_digits, shift_bits, x_size;\r
+ /* See below for why x_digits is always large enough. */\r
+ digit rem, x_digits[2 + (DBL_MANT_DIG + 1) / PyLong_SHIFT];\r
+ double dx;\r
+ /* Correction term for round-half-to-even rounding. For a digit x,\r
+ "x + half_even_correction[x & 7]" gives x rounded to the nearest\r
+ multiple of 4, rounding ties to a multiple of 8. */\r
+ static const int half_even_correction[8] = {0, -1, -2, 1, 0, -1, 2, 1};\r
+\r
+ a_size = ABS(Py_SIZE(a));\r
+ if (a_size == 0) {\r
+ /* Special case for 0: significand 0.0, exponent 0. */\r
+ *e = 0;\r
+ return 0.0;\r
+ }\r
+ a_bits = bits_in_digit(a->ob_digit[a_size-1]);\r
+ /* The following is an overflow-free version of the check\r
+ "if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */\r
+ if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&\r
+ (a_size > (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 ||\r
+ a_bits > (PY_SSIZE_T_MAX - 1) % PyLong_SHIFT + 1))\r
+ goto overflow;\r
+ a_bits = (a_size - 1) * PyLong_SHIFT + a_bits;\r
+\r
+ /* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size]\r
+ (shifting left if a_bits <= DBL_MANT_DIG + 2).\r
+\r
+ Number of digits needed for result: write // for floor division.\r
+ Then if shifting left, we end up using\r
+\r
+ 1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT\r
+\r
+ digits. If shifting right, we use\r
+\r
+ a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT\r
+\r
+ digits. Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with\r
+ the inequalities\r
+\r
+ m // PyLong_SHIFT + n // PyLong_SHIFT <= (m + n) // PyLong_SHIFT\r
+ m // PyLong_SHIFT - n // PyLong_SHIFT <=\r
+ 1 + (m - n - 1) // PyLong_SHIFT,\r
+\r
+ valid for any integers m and n, we find that x_size satisfies\r
+\r
+ x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT\r
+\r
+ in both cases.\r
+ */\r
+ if (a_bits <= DBL_MANT_DIG + 2) {\r
+ shift_digits = (DBL_MANT_DIG + 2 - a_bits) / PyLong_SHIFT;\r
+ shift_bits = (DBL_MANT_DIG + 2 - a_bits) % PyLong_SHIFT;\r
+ x_size = 0;\r
+ while (x_size < shift_digits)\r
+ x_digits[x_size++] = 0;\r
+ rem = v_lshift(x_digits + x_size, a->ob_digit, a_size,\r
+ (int)shift_bits);\r
+ x_size += a_size;\r
+ x_digits[x_size++] = rem;\r
+ }\r
+ else {\r
+ shift_digits = (a_bits - DBL_MANT_DIG - 2) / PyLong_SHIFT;\r
+ shift_bits = (a_bits - DBL_MANT_DIG - 2) % PyLong_SHIFT;\r
+ rem = v_rshift(x_digits, a->ob_digit + shift_digits,\r
+ a_size - shift_digits, (int)shift_bits);\r
+ x_size = a_size - shift_digits;\r
+ /* For correct rounding below, we need the least significant\r
+ bit of x to be 'sticky' for this shift: if any of the bits\r
+ shifted out was nonzero, we set the least significant bit\r
+ of x. */\r
+ if (rem)\r
+ x_digits[0] |= 1;\r
+ else\r
+ while (shift_digits > 0)\r
+ if (a->ob_digit[--shift_digits]) {\r
+ x_digits[0] |= 1;\r
+ break;\r
+ }\r
+ }\r
+ assert(1 <= x_size &&\r
+ x_size <= (Py_ssize_t)(sizeof(x_digits)/sizeof(digit)));\r
+\r
+ /* Round, and convert to double. */\r
+ x_digits[0] += half_even_correction[x_digits[0] & 7];\r
+ dx = x_digits[--x_size];\r
+ while (x_size > 0)\r
+ dx = dx * PyLong_BASE + x_digits[--x_size];\r
+\r
+ /* Rescale; make correction if result is 1.0. */\r
+ dx /= 4.0 * EXP2_DBL_MANT_DIG;\r
+ if (dx == 1.0) {\r
+ if (a_bits == PY_SSIZE_T_MAX)\r
+ goto overflow;\r
+ dx = 0.5;\r
+ a_bits += 1;\r
+ }\r
+\r
+ *e = a_bits;\r
+ return Py_SIZE(a) < 0 ? -dx : dx;\r
+\r
+ overflow:\r
+ /* exponent > PY_SSIZE_T_MAX */\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "huge integer: number of bits overflows a Py_ssize_t");\r
+ *e = 0;\r
+ return -1.0;\r
+}\r
+\r
+/* Get a C double from a long int object. Rounds to the nearest double,\r
+ using the round-half-to-even rule in the case of a tie. */\r
+\r
+double\r
+PyLong_AsDouble(PyObject *v)\r
+{\r
+ Py_ssize_t exponent;\r
+ double x;\r
+\r
+ if (v == NULL || !PyLong_Check(v)) {\r
+ PyErr_BadInternalCall();\r
+ return -1.0;\r
+ }\r
+ x = _PyLong_Frexp((PyLongObject *)v, &exponent);\r
+ if ((x == -1.0 && PyErr_Occurred()) || exponent > DBL_MAX_EXP) {\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "long int too large to convert to float");\r
+ return -1.0;\r
+ }\r
+ return ldexp(x, (int)exponent);\r
+}\r
+\r
+/* Methods */\r
+\r
+static void\r
+long_dealloc(PyObject *v)\r
+{\r
+ Py_TYPE(v)->tp_free(v);\r
+}\r
+\r
+static PyObject *\r
+long_repr(PyObject *v)\r
+{\r
+ return _PyLong_Format(v, 10, 1, 0);\r
+}\r
+\r
+static PyObject *\r
+long_str(PyObject *v)\r
+{\r
+ return _PyLong_Format(v, 10, 0, 0);\r
+}\r
+\r
+static int\r
+long_compare(PyLongObject *a, PyLongObject *b)\r
+{\r
+ Py_ssize_t sign;\r
+\r
+ if (Py_SIZE(a) != Py_SIZE(b)) {\r
+ sign = Py_SIZE(a) - Py_SIZE(b);\r
+ }\r
+ else {\r
+ Py_ssize_t i = ABS(Py_SIZE(a));\r
+ while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])\r
+ ;\r
+ if (i < 0)\r
+ sign = 0;\r
+ else {\r
+ sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];\r
+ if (Py_SIZE(a) < 0)\r
+ sign = -sign;\r
+ }\r
+ }\r
+ return sign < 0 ? -1 : sign > 0 ? 1 : 0;\r
+}\r
+\r
+static long\r
+long_hash(PyLongObject *v)\r
+{\r
+ unsigned long x;\r
+ Py_ssize_t i;\r
+ int sign;\r
+\r
+ /* This is designed so that Python ints and longs with the\r
+ same value hash to the same value, otherwise comparisons\r
+ of mapping keys will turn out weird */\r
+ i = v->ob_size;\r
+ sign = 1;\r
+ x = 0;\r
+ if (i < 0) {\r
+ sign = -1;\r
+ i = -(i);\r
+ }\r
+ /* The following loop produces a C unsigned long x such that x is\r
+ congruent to the absolute value of v modulo ULONG_MAX. The\r
+ resulting x is nonzero if and only if v is. */\r
+ while (--i >= 0) {\r
+ /* Force a native long #-bits (32 or 64) circular shift */\r
+ x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);\r
+ x += v->ob_digit[i];\r
+ /* If the addition above overflowed we compensate by\r
+ incrementing. This preserves the value modulo\r
+ ULONG_MAX. */\r
+ if (x < v->ob_digit[i])\r
+ x++;\r
+ }\r
+ x = x * sign;\r
+ if (x == (unsigned long)-1)\r
+ x = (unsigned long)-2;\r
+ return (long)x;\r
+}\r
+\r
+\r
+/* Add the absolute values of two long integers. */\r
+\r
+static PyLongObject *\r
+x_add(PyLongObject *a, PyLongObject *b)\r
+{\r
+ Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));\r
+ PyLongObject *z;\r
+ Py_ssize_t i;\r
+ digit carry = 0;\r
+\r
+ /* Ensure a is the larger of the two: */\r
+ if (size_a < size_b) {\r
+ { PyLongObject *temp = a; a = b; b = temp; }\r
+ { Py_ssize_t size_temp = size_a;\r
+ size_a = size_b;\r
+ size_b = size_temp; }\r
+ }\r
+ z = _PyLong_New(size_a+1);\r
+ if (z == NULL)\r
+ return NULL;\r
+ for (i = 0; i < size_b; ++i) {\r
+ carry += a->ob_digit[i] + b->ob_digit[i];\r
+ z->ob_digit[i] = carry & PyLong_MASK;\r
+ carry >>= PyLong_SHIFT;\r
+ }\r
+ for (; i < size_a; ++i) {\r
+ carry += a->ob_digit[i];\r
+ z->ob_digit[i] = carry & PyLong_MASK;\r
+ carry >>= PyLong_SHIFT;\r
+ }\r
+ z->ob_digit[i] = carry;\r
+ return long_normalize(z);\r
+}\r
+\r
+/* Subtract the absolute values of two integers. */\r
+\r
+static PyLongObject *\r
+x_sub(PyLongObject *a, PyLongObject *b)\r
+{\r
+ Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));\r
+ PyLongObject *z;\r
+ Py_ssize_t i;\r
+ int sign = 1;\r
+ digit borrow = 0;\r
+\r
+ /* Ensure a is the larger of the two: */\r
+ if (size_a < size_b) {\r
+ sign = -1;\r
+ { PyLongObject *temp = a; a = b; b = temp; }\r
+ { Py_ssize_t size_temp = size_a;\r
+ size_a = size_b;\r
+ size_b = size_temp; }\r
+ }\r
+ else if (size_a == size_b) {\r
+ /* Find highest digit where a and b differ: */\r
+ i = size_a;\r
+ while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])\r
+ ;\r
+ if (i < 0)\r
+ return _PyLong_New(0);\r
+ if (a->ob_digit[i] < b->ob_digit[i]) {\r
+ sign = -1;\r
+ { PyLongObject *temp = a; a = b; b = temp; }\r
+ }\r
+ size_a = size_b = i+1;\r
+ }\r
+ z = _PyLong_New(size_a);\r
+ if (z == NULL)\r
+ return NULL;\r
+ for (i = 0; i < size_b; ++i) {\r
+ /* The following assumes unsigned arithmetic\r
+ works module 2**N for some N>PyLong_SHIFT. */\r
+ borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;\r
+ z->ob_digit[i] = borrow & PyLong_MASK;\r
+ borrow >>= PyLong_SHIFT;\r
+ borrow &= 1; /* Keep only one sign bit */\r
+ }\r
+ for (; i < size_a; ++i) {\r
+ borrow = a->ob_digit[i] - borrow;\r
+ z->ob_digit[i] = borrow & PyLong_MASK;\r
+ borrow >>= PyLong_SHIFT;\r
+ borrow &= 1; /* Keep only one sign bit */\r
+ }\r
+ assert(borrow == 0);\r
+ if (sign < 0)\r
+ z->ob_size = -(z->ob_size);\r
+ return long_normalize(z);\r
+}\r
+\r
+static PyObject *\r
+long_add(PyLongObject *v, PyLongObject *w)\r
+{\r
+ PyLongObject *a, *b, *z;\r
+\r
+ CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);\r
+\r
+ if (a->ob_size < 0) {\r
+ if (b->ob_size < 0) {\r
+ z = x_add(a, b);\r
+ if (z != NULL && z->ob_size != 0)\r
+ z->ob_size = -(z->ob_size);\r
+ }\r
+ else\r
+ z = x_sub(b, a);\r
+ }\r
+ else {\r
+ if (b->ob_size < 0)\r
+ z = x_sub(a, b);\r
+ else\r
+ z = x_add(a, b);\r
+ }\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *)z;\r
+}\r
+\r
+static PyObject *\r
+long_sub(PyLongObject *v, PyLongObject *w)\r
+{\r
+ PyLongObject *a, *b, *z;\r
+\r
+ CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);\r
+\r
+ if (a->ob_size < 0) {\r
+ if (b->ob_size < 0)\r
+ z = x_sub(a, b);\r
+ else\r
+ z = x_add(a, b);\r
+ if (z != NULL && z->ob_size != 0)\r
+ z->ob_size = -(z->ob_size);\r
+ }\r
+ else {\r
+ if (b->ob_size < 0)\r
+ z = x_add(a, b);\r
+ else\r
+ z = x_sub(a, b);\r
+ }\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *)z;\r
+}\r
+\r
+/* Grade school multiplication, ignoring the signs.\r
+ * Returns the absolute value of the product, or NULL if error.\r
+ */\r
+static PyLongObject *\r
+x_mul(PyLongObject *a, PyLongObject *b)\r
+{\r
+ PyLongObject *z;\r
+ Py_ssize_t size_a = ABS(Py_SIZE(a));\r
+ Py_ssize_t size_b = ABS(Py_SIZE(b));\r
+ Py_ssize_t i;\r
+\r
+ z = _PyLong_New(size_a + size_b);\r
+ if (z == NULL)\r
+ return NULL;\r
+\r
+ memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));\r
+ if (a == b) {\r
+ /* Efficient squaring per HAC, Algorithm 14.16:\r
+ * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf\r
+ * Gives slightly less than a 2x speedup when a == b,\r
+ * via exploiting that each entry in the multiplication\r
+ * pyramid appears twice (except for the size_a squares).\r
+ */\r
+ for (i = 0; i < size_a; ++i) {\r
+ twodigits carry;\r
+ twodigits f = a->ob_digit[i];\r
+ digit *pz = z->ob_digit + (i << 1);\r
+ digit *pa = a->ob_digit + i + 1;\r
+ digit *paend = a->ob_digit + size_a;\r
+\r
+ SIGCHECK({\r
+ Py_DECREF(z);\r
+ return NULL;\r
+ });\r
+\r
+ carry = *pz + f * f;\r
+ *pz++ = (digit)(carry & PyLong_MASK);\r
+ carry >>= PyLong_SHIFT;\r
+ assert(carry <= PyLong_MASK);\r
+\r
+ /* Now f is added in twice in each column of the\r
+ * pyramid it appears. Same as adding f<<1 once.\r
+ */\r
+ f <<= 1;\r
+ while (pa < paend) {\r
+ carry += *pz + *pa++ * f;\r
+ *pz++ = (digit)(carry & PyLong_MASK);\r
+ carry >>= PyLong_SHIFT;\r
+ assert(carry <= (PyLong_MASK << 1));\r
+ }\r
+ if (carry) {\r
+ carry += *pz;\r
+ *pz++ = (digit)(carry & PyLong_MASK);\r
+ carry >>= PyLong_SHIFT;\r
+ }\r
+ if (carry)\r
+ *pz += (digit)(carry & PyLong_MASK);\r
+ assert((carry >> PyLong_SHIFT) == 0);\r
+ }\r
+ }\r
+ else { /* a is not the same as b -- gradeschool long mult */\r
+ for (i = 0; i < size_a; ++i) {\r
+ twodigits carry = 0;\r
+ twodigits f = a->ob_digit[i];\r
+ digit *pz = z->ob_digit + i;\r
+ digit *pb = b->ob_digit;\r
+ digit *pbend = b->ob_digit + size_b;\r
+\r
+ SIGCHECK({\r
+ Py_DECREF(z);\r
+ return NULL;\r
+ });\r
+\r
+ while (pb < pbend) {\r
+ carry += *pz + *pb++ * f;\r
+ *pz++ = (digit)(carry & PyLong_MASK);\r
+ carry >>= PyLong_SHIFT;\r
+ assert(carry <= PyLong_MASK);\r
+ }\r
+ if (carry)\r
+ *pz += (digit)(carry & PyLong_MASK);\r
+ assert((carry >> PyLong_SHIFT) == 0);\r
+ }\r
+ }\r
+ return long_normalize(z);\r
+}\r
+\r
+/* A helper for Karatsuba multiplication (k_mul).\r
+ Takes a long "n" and an integer "size" representing the place to\r
+ split, and sets low and high such that abs(n) == (high << size) + low,\r
+ viewing the shift as being by digits. The sign bit is ignored, and\r
+ the return values are >= 0.\r
+ Returns 0 on success, -1 on failure.\r
+*/\r
+static int\r
+kmul_split(PyLongObject *n,\r
+ Py_ssize_t size,\r
+ PyLongObject **high,\r
+ PyLongObject **low)\r
+{\r
+ PyLongObject *hi, *lo;\r
+ Py_ssize_t size_lo, size_hi;\r
+ const Py_ssize_t size_n = ABS(Py_SIZE(n));\r
+\r
+ size_lo = MIN(size_n, size);\r
+ size_hi = size_n - size_lo;\r
+\r
+ if ((hi = _PyLong_New(size_hi)) == NULL)\r
+ return -1;\r
+ if ((lo = _PyLong_New(size_lo)) == NULL) {\r
+ Py_DECREF(hi);\r
+ return -1;\r
+ }\r
+\r
+ memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));\r
+ memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));\r
+\r
+ *high = long_normalize(hi);\r
+ *low = long_normalize(lo);\r
+ return 0;\r
+}\r
+\r
+static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);\r
+\r
+/* Karatsuba multiplication. Ignores the input signs, and returns the\r
+ * absolute value of the product (or NULL if error).\r
+ * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).\r
+ */\r
+static PyLongObject *\r
+k_mul(PyLongObject *a, PyLongObject *b)\r
+{\r
+ Py_ssize_t asize = ABS(Py_SIZE(a));\r
+ Py_ssize_t bsize = ABS(Py_SIZE(b));\r
+ PyLongObject *ah = NULL;\r
+ PyLongObject *al = NULL;\r
+ PyLongObject *bh = NULL;\r
+ PyLongObject *bl = NULL;\r
+ PyLongObject *ret = NULL;\r
+ PyLongObject *t1, *t2, *t3;\r
+ Py_ssize_t shift; /* the number of digits we split off */\r
+ Py_ssize_t i;\r
+\r
+ /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl\r
+ * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl\r
+ * Then the original product is\r
+ * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl\r
+ * By picking X to be a power of 2, "*X" is just shifting, and it's\r
+ * been reduced to 3 multiplies on numbers half the size.\r
+ */\r
+\r
+ /* We want to split based on the larger number; fiddle so that b\r
+ * is largest.\r
+ */\r
+ if (asize > bsize) {\r
+ t1 = a;\r
+ a = b;\r
+ b = t1;\r
+\r
+ i = asize;\r
+ asize = bsize;\r
+ bsize = i;\r
+ }\r
+\r
+ /* Use gradeschool math when either number is too small. */\r
+ i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;\r
+ if (asize <= i) {\r
+ if (asize == 0)\r
+ return _PyLong_New(0);\r
+ else\r
+ return x_mul(a, b);\r
+ }\r
+\r
+ /* If a is small compared to b, splitting on b gives a degenerate\r
+ * case with ah==0, and Karatsuba may be (even much) less efficient\r
+ * than "grade school" then. However, we can still win, by viewing\r
+ * b as a string of "big digits", each of width a->ob_size. That\r
+ * leads to a sequence of balanced calls to k_mul.\r
+ */\r
+ if (2 * asize <= bsize)\r
+ return k_lopsided_mul(a, b);\r
+\r
+ /* Split a & b into hi & lo pieces. */\r
+ shift = bsize >> 1;\r
+ if (kmul_split(a, shift, &ah, &al) < 0) goto fail;\r
+ assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */\r
+\r
+ if (a == b) {\r
+ bh = ah;\r
+ bl = al;\r
+ Py_INCREF(bh);\r
+ Py_INCREF(bl);\r
+ }\r
+ else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;\r
+\r
+ /* The plan:\r
+ * 1. Allocate result space (asize + bsize digits: that's always\r
+ * enough).\r
+ * 2. Compute ah*bh, and copy into result at 2*shift.\r
+ * 3. Compute al*bl, and copy into result at 0. Note that this\r
+ * can't overlap with #2.\r
+ * 4. Subtract al*bl from the result, starting at shift. This may\r
+ * underflow (borrow out of the high digit), but we don't care:\r
+ * we're effectively doing unsigned arithmetic mod\r
+ * PyLong_BASE**(sizea + sizeb), and so long as the *final* result fits,\r
+ * borrows and carries out of the high digit can be ignored.\r
+ * 5. Subtract ah*bh from the result, starting at shift.\r
+ * 6. Compute (ah+al)*(bh+bl), and add it into the result starting\r
+ * at shift.\r
+ */\r
+\r
+ /* 1. Allocate result space. */\r
+ ret = _PyLong_New(asize + bsize);\r
+ if (ret == NULL) goto fail;\r
+#ifdef Py_DEBUG\r
+ /* Fill with trash, to catch reference to uninitialized digits. */\r
+ memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));\r
+#endif\r
+\r
+ /* 2. t1 <- ah*bh, and copy into high digits of result. */\r
+ if ((t1 = k_mul(ah, bh)) == NULL) goto fail;\r
+ assert(Py_SIZE(t1) >= 0);\r
+ assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));\r
+ memcpy(ret->ob_digit + 2*shift, t1->ob_digit,\r
+ Py_SIZE(t1) * sizeof(digit));\r
+\r
+ /* Zero-out the digits higher than the ah*bh copy. */\r
+ i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);\r
+ if (i)\r
+ memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,\r
+ i * sizeof(digit));\r
+\r
+ /* 3. t2 <- al*bl, and copy into the low digits. */\r
+ if ((t2 = k_mul(al, bl)) == NULL) {\r
+ Py_DECREF(t1);\r
+ goto fail;\r
+ }\r
+ assert(Py_SIZE(t2) >= 0);\r
+ assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */\r
+ memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));\r
+\r
+ /* Zero out remaining digits. */\r
+ i = 2*shift - Py_SIZE(t2); /* number of uninitialized digits */\r
+ if (i)\r
+ memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));\r
+\r
+ /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first\r
+ * because it's fresher in cache.\r
+ */\r
+ i = Py_SIZE(ret) - shift; /* # digits after shift */\r
+ (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));\r
+ Py_DECREF(t2);\r
+\r
+ (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));\r
+ Py_DECREF(t1);\r
+\r
+ /* 6. t3 <- (ah+al)(bh+bl), and add into result. */\r
+ if ((t1 = x_add(ah, al)) == NULL) goto fail;\r
+ Py_DECREF(ah);\r
+ Py_DECREF(al);\r
+ ah = al = NULL;\r
+\r
+ if (a == b) {\r
+ t2 = t1;\r
+ Py_INCREF(t2);\r
+ }\r
+ else if ((t2 = x_add(bh, bl)) == NULL) {\r
+ Py_DECREF(t1);\r
+ goto fail;\r
+ }\r
+ Py_DECREF(bh);\r
+ Py_DECREF(bl);\r
+ bh = bl = NULL;\r
+\r
+ t3 = k_mul(t1, t2);\r
+ Py_DECREF(t1);\r
+ Py_DECREF(t2);\r
+ if (t3 == NULL) goto fail;\r
+ assert(Py_SIZE(t3) >= 0);\r
+\r
+ /* Add t3. It's not obvious why we can't run out of room here.\r
+ * See the (*) comment after this function.\r
+ */\r
+ (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));\r
+ Py_DECREF(t3);\r
+\r
+ return long_normalize(ret);\r
+\r
+ fail:\r
+ Py_XDECREF(ret);\r
+ Py_XDECREF(ah);\r
+ Py_XDECREF(al);\r
+ Py_XDECREF(bh);\r
+ Py_XDECREF(bl);\r
+ return NULL;\r
+}\r
+\r
+/* (*) Why adding t3 can't "run out of room" above.\r
+\r
+Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts\r
+to start with:\r
+\r
+1. For any integer i, i = c(i/2) + f(i/2). In particular,\r
+ bsize = c(bsize/2) + f(bsize/2).\r
+2. shift = f(bsize/2)\r
+3. asize <= bsize\r
+4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this\r
+ routine, so asize > bsize/2 >= f(bsize/2) in this routine.\r
+\r
+We allocated asize + bsize result digits, and add t3 into them at an offset\r
+of shift. This leaves asize+bsize-shift allocated digit positions for t3\r
+to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =\r
+asize + c(bsize/2) available digit positions.\r
+\r
+bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has\r
+at most c(bsize/2) digits + 1 bit.\r
+\r
+If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)\r
+digits, and al has at most f(bsize/2) digits in any case. So ah+al has at\r
+most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.\r
+\r
+The product (ah+al)*(bh+bl) therefore has at most\r
+\r
+ c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits\r
+\r
+and we have asize + c(bsize/2) available digit positions. We need to show\r
+this is always enough. An instance of c(bsize/2) cancels out in both, so\r
+the question reduces to whether asize digits is enough to hold\r
+(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,\r
+then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,\r
+asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1\r
+digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If\r
+asize == bsize, then we're asking whether bsize digits is enough to hold\r
+c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits\r
+is enough to hold 2 bits. This is so if bsize >= 2, which holds because\r
+bsize >= KARATSUBA_CUTOFF >= 2.\r
+\r
+Note that since there's always enough room for (ah+al)*(bh+bl), and that's\r
+clearly >= each of ah*bh and al*bl, there's always enough room to subtract\r
+ah*bh and al*bl too.\r
+*/\r
+\r
+/* b has at least twice the digits of a, and a is big enough that Karatsuba\r
+ * would pay off *if* the inputs had balanced sizes. View b as a sequence\r
+ * of slices, each with a->ob_size digits, and multiply the slices by a,\r
+ * one at a time. This gives k_mul balanced inputs to work with, and is\r
+ * also cache-friendly (we compute one double-width slice of the result\r
+ * at a time, then move on, never backtracking except for the helpful\r
+ * single-width slice overlap between successive partial sums).\r
+ */\r
+static PyLongObject *\r
+k_lopsided_mul(PyLongObject *a, PyLongObject *b)\r
+{\r
+ const Py_ssize_t asize = ABS(Py_SIZE(a));\r
+ Py_ssize_t bsize = ABS(Py_SIZE(b));\r
+ Py_ssize_t nbdone; /* # of b digits already multiplied */\r
+ PyLongObject *ret;\r
+ PyLongObject *bslice = NULL;\r
+\r
+ assert(asize > KARATSUBA_CUTOFF);\r
+ assert(2 * asize <= bsize);\r
+\r
+ /* Allocate result space, and zero it out. */\r
+ ret = _PyLong_New(asize + bsize);\r
+ if (ret == NULL)\r
+ return NULL;\r
+ memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));\r
+\r
+ /* Successive slices of b are copied into bslice. */\r
+ bslice = _PyLong_New(asize);\r
+ if (bslice == NULL)\r
+ goto fail;\r
+\r
+ nbdone = 0;\r
+ while (bsize > 0) {\r
+ PyLongObject *product;\r
+ const Py_ssize_t nbtouse = MIN(bsize, asize);\r
+\r
+ /* Multiply the next slice of b by a. */\r
+ memcpy(bslice->ob_digit, b->ob_digit + nbdone,\r
+ nbtouse * sizeof(digit));\r
+ Py_SIZE(bslice) = nbtouse;\r
+ product = k_mul(a, bslice);\r
+ if (product == NULL)\r
+ goto fail;\r
+\r
+ /* Add into result. */\r
+ (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,\r
+ product->ob_digit, Py_SIZE(product));\r
+ Py_DECREF(product);\r
+\r
+ bsize -= nbtouse;\r
+ nbdone += nbtouse;\r
+ }\r
+\r
+ Py_DECREF(bslice);\r
+ return long_normalize(ret);\r
+\r
+ fail:\r
+ Py_DECREF(ret);\r
+ Py_XDECREF(bslice);\r
+ return NULL;\r
+}\r
+\r
+static PyObject *\r
+long_mul(PyLongObject *v, PyLongObject *w)\r
+{\r
+ PyLongObject *a, *b, *z;\r
+\r
+ if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) {\r
+ Py_INCREF(Py_NotImplemented);\r
+ return Py_NotImplemented;\r
+ }\r
+\r
+ z = k_mul(a, b);\r
+ /* Negate if exactly one of the inputs is negative. */\r
+ if (((a->ob_size ^ b->ob_size) < 0) && z)\r
+ z->ob_size = -(z->ob_size);\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *)z;\r
+}\r
+\r
+/* The / and % operators are now defined in terms of divmod().\r
+ The expression a mod b has the value a - b*floor(a/b).\r
+ The long_divrem function gives the remainder after division of\r
+ |a| by |b|, with the sign of a. This is also expressed\r
+ as a - b*trunc(a/b), if trunc truncates towards zero.\r
+ Some examples:\r
+ a b a rem b a mod b\r
+ 13 10 3 3\r
+ -13 10 -3 7\r
+ 13 -10 3 -7\r
+ -13 -10 -3 -3\r
+ So, to get from rem to mod, we have to add b if a and b\r
+ have different signs. We then subtract one from the 'div'\r
+ part of the outcome to keep the invariant intact. */\r
+\r
+/* Compute\r
+ * *pdiv, *pmod = divmod(v, w)\r
+ * NULL can be passed for pdiv or pmod, in which case that part of\r
+ * the result is simply thrown away. The caller owns a reference to\r
+ * each of these it requests (does not pass NULL for).\r
+ */\r
+static int\r
+l_divmod(PyLongObject *v, PyLongObject *w,\r
+ PyLongObject **pdiv, PyLongObject **pmod)\r
+{\r
+ PyLongObject *div, *mod;\r
+\r
+ if (long_divrem(v, w, &div, &mod) < 0)\r
+ return -1;\r
+ if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||\r
+ (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {\r
+ PyLongObject *temp;\r
+ PyLongObject *one;\r
+ temp = (PyLongObject *) long_add(mod, w);\r
+ Py_DECREF(mod);\r
+ mod = temp;\r
+ if (mod == NULL) {\r
+ Py_DECREF(div);\r
+ return -1;\r
+ }\r
+ one = (PyLongObject *) PyLong_FromLong(1L);\r
+ if (one == NULL ||\r
+ (temp = (PyLongObject *) long_sub(div, one)) == NULL) {\r
+ Py_DECREF(mod);\r
+ Py_DECREF(div);\r
+ Py_XDECREF(one);\r
+ return -1;\r
+ }\r
+ Py_DECREF(one);\r
+ Py_DECREF(div);\r
+ div = temp;\r
+ }\r
+ if (pdiv != NULL)\r
+ *pdiv = div;\r
+ else\r
+ Py_DECREF(div);\r
+\r
+ if (pmod != NULL)\r
+ *pmod = mod;\r
+ else\r
+ Py_DECREF(mod);\r
+\r
+ return 0;\r
+}\r
+\r
+static PyObject *\r
+long_div(PyObject *v, PyObject *w)\r
+{\r
+ PyLongObject *a, *b, *div;\r
+\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+ if (l_divmod(a, b, &div, NULL) < 0)\r
+ div = NULL;\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *)div;\r
+}\r
+\r
+static PyObject *\r
+long_classic_div(PyObject *v, PyObject *w)\r
+{\r
+ PyLongObject *a, *b, *div;\r
+\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+ if (Py_DivisionWarningFlag &&\r
+ PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)\r
+ div = NULL;\r
+ else if (l_divmod(a, b, &div, NULL) < 0)\r
+ div = NULL;\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *)div;\r
+}\r
+\r
+/* PyLong/PyLong -> float, with correctly rounded result. */\r
+\r
+#define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT)\r
+#define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT)\r
+\r
+static PyObject *\r
+long_true_divide(PyObject *v, PyObject *w)\r
+{\r
+ PyLongObject *a, *b, *x;\r
+ Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits;\r
+ digit mask, low;\r
+ int inexact, negate, a_is_small, b_is_small;\r
+ double dx, result;\r
+\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+\r
+ /*\r
+ Method in a nutshell:\r
+\r
+ 0. reduce to case a, b > 0; filter out obvious underflow/overflow\r
+ 1. choose a suitable integer 'shift'\r
+ 2. use integer arithmetic to compute x = floor(2**-shift*a/b)\r
+ 3. adjust x for correct rounding\r
+ 4. convert x to a double dx with the same value\r
+ 5. return ldexp(dx, shift).\r
+\r
+ In more detail:\r
+\r
+ 0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b\r
+ returns either 0.0 or -0.0, depending on the sign of b. For a and\r
+ b both nonzero, ignore signs of a and b, and add the sign back in\r
+ at the end. Now write a_bits and b_bits for the bit lengths of a\r
+ and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise\r
+ for b). Then\r
+\r
+ 2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1).\r
+\r
+ So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and\r
+ so overflows. Similarly, if a_bits - b_bits < DBL_MIN_EXP -\r
+ DBL_MANT_DIG - 1 then a/b underflows to 0. With these cases out of\r
+ the way, we can assume that\r
+\r
+ DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP.\r
+\r
+ 1. The integer 'shift' is chosen so that x has the right number of\r
+ bits for a double, plus two or three extra bits that will be used\r
+ in the rounding decisions. Writing a_bits and b_bits for the\r
+ number of significant bits in a and b respectively, a\r
+ straightforward formula for shift is:\r
+\r
+ shift = a_bits - b_bits - DBL_MANT_DIG - 2\r
+\r
+ This is fine in the usual case, but if a/b is smaller than the\r
+ smallest normal float then it can lead to double rounding on an\r
+ IEEE 754 platform, giving incorrectly rounded results. So we\r
+ adjust the formula slightly. The actual formula used is:\r
+\r
+ shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2\r
+\r
+ 2. The quantity x is computed by first shifting a (left -shift bits\r
+ if shift <= 0, right shift bits if shift > 0) and then dividing by\r
+ b. For both the shift and the division, we keep track of whether\r
+ the result is inexact, in a flag 'inexact'; this information is\r
+ needed at the rounding stage.\r
+\r
+ With the choice of shift above, together with our assumption that\r
+ a_bits - b_bits >= DBL_MIN_EXP - DBL_MANT_DIG - 1, it follows\r
+ that x >= 1.\r
+\r
+ 3. Now x * 2**shift <= a/b < (x+1) * 2**shift. We want to replace\r
+ this with an exactly representable float of the form\r
+\r
+ round(x/2**extra_bits) * 2**(extra_bits+shift).\r
+\r
+ For float representability, we need x/2**extra_bits <\r
+ 2**DBL_MANT_DIG and extra_bits + shift >= DBL_MIN_EXP -\r
+ DBL_MANT_DIG. This translates to the condition:\r
+\r
+ extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG\r
+\r
+ To round, we just modify the bottom digit of x in-place; this can\r
+ end up giving a digit with value > PyLONG_MASK, but that's not a\r
+ problem since digits can hold values up to 2*PyLONG_MASK+1.\r
+\r
+ With the original choices for shift above, extra_bits will always\r
+ be 2 or 3. Then rounding under the round-half-to-even rule, we\r
+ round up iff the most significant of the extra bits is 1, and\r
+ either: (a) the computation of x in step 2 had an inexact result,\r
+ or (b) at least one other of the extra bits is 1, or (c) the least\r
+ significant bit of x (above those to be rounded) is 1.\r
+\r
+ 4. Conversion to a double is straightforward; all floating-point\r
+ operations involved in the conversion are exact, so there's no\r
+ danger of rounding errors.\r
+\r
+ 5. Use ldexp(x, shift) to compute x*2**shift, the final result.\r
+ The result will always be exactly representable as a double, except\r
+ in the case that it overflows. To avoid dependence on the exact\r
+ behaviour of ldexp on overflow, we check for overflow before\r
+ applying ldexp. The result of ldexp is adjusted for sign before\r
+ returning.\r
+ */\r
+\r
+ /* Reduce to case where a and b are both positive. */\r
+ a_size = ABS(Py_SIZE(a));\r
+ b_size = ABS(Py_SIZE(b));\r
+ negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0);\r
+ if (b_size == 0) {\r
+ PyErr_SetString(PyExc_ZeroDivisionError,\r
+ "division by zero");\r
+ goto error;\r
+ }\r
+ if (a_size == 0)\r
+ goto underflow_or_zero;\r
+\r
+ /* Fast path for a and b small (exactly representable in a double).\r
+ Relies on floating-point division being correctly rounded; results\r
+ may be subject to double rounding on x86 machines that operate with\r
+ the x87 FPU set to 64-bit precision. */\r
+ a_is_small = a_size <= MANT_DIG_DIGITS ||\r
+ (a_size == MANT_DIG_DIGITS+1 &&\r
+ a->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);\r
+ b_is_small = b_size <= MANT_DIG_DIGITS ||\r
+ (b_size == MANT_DIG_DIGITS+1 &&\r
+ b->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);\r
+ if (a_is_small && b_is_small) {\r
+ double da, db;\r
+ da = a->ob_digit[--a_size];\r
+ while (a_size > 0)\r
+ da = da * PyLong_BASE + a->ob_digit[--a_size];\r
+ db = b->ob_digit[--b_size];\r
+ while (b_size > 0)\r
+ db = db * PyLong_BASE + b->ob_digit[--b_size];\r
+ result = da / db;\r
+ goto success;\r
+ }\r
+\r
+ /* Catch obvious cases of underflow and overflow */\r
+ diff = a_size - b_size;\r
+ if (diff > PY_SSIZE_T_MAX/PyLong_SHIFT - 1)\r
+ /* Extreme overflow */\r
+ goto overflow;\r
+ else if (diff < 1 - PY_SSIZE_T_MAX/PyLong_SHIFT)\r
+ /* Extreme underflow */\r
+ goto underflow_or_zero;\r
+ /* Next line is now safe from overflowing a Py_ssize_t */\r
+ diff = diff * PyLong_SHIFT + bits_in_digit(a->ob_digit[a_size - 1]) -\r
+ bits_in_digit(b->ob_digit[b_size - 1]);\r
+ /* Now diff = a_bits - b_bits. */\r
+ if (diff > DBL_MAX_EXP)\r
+ goto overflow;\r
+ else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1)\r
+ goto underflow_or_zero;\r
+\r
+ /* Choose value for shift; see comments for step 1 above. */\r
+ shift = MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2;\r
+\r
+ inexact = 0;\r
+\r
+ /* x = abs(a * 2**-shift) */\r
+ if (shift <= 0) {\r
+ Py_ssize_t i, shift_digits = -shift / PyLong_SHIFT;\r
+ digit rem;\r
+ /* x = a << -shift */\r
+ if (a_size >= PY_SSIZE_T_MAX - 1 - shift_digits) {\r
+ /* In practice, it's probably impossible to end up\r
+ here. Both a and b would have to be enormous,\r
+ using close to SIZE_T_MAX bytes of memory each. */\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "intermediate overflow during division");\r
+ goto error;\r
+ }\r
+ x = _PyLong_New(a_size + shift_digits + 1);\r
+ if (x == NULL)\r
+ goto error;\r
+ for (i = 0; i < shift_digits; i++)\r
+ x->ob_digit[i] = 0;\r
+ rem = v_lshift(x->ob_digit + shift_digits, a->ob_digit,\r
+ a_size, -shift % PyLong_SHIFT);\r
+ x->ob_digit[a_size + shift_digits] = rem;\r
+ }\r
+ else {\r
+ Py_ssize_t shift_digits = shift / PyLong_SHIFT;\r
+ digit rem;\r
+ /* x = a >> shift */\r
+ assert(a_size >= shift_digits);\r
+ x = _PyLong_New(a_size - shift_digits);\r
+ if (x == NULL)\r
+ goto error;\r
+ rem = v_rshift(x->ob_digit, a->ob_digit + shift_digits,\r
+ a_size - shift_digits, shift % PyLong_SHIFT);\r
+ /* set inexact if any of the bits shifted out is nonzero */\r
+ if (rem)\r
+ inexact = 1;\r
+ while (!inexact && shift_digits > 0)\r
+ if (a->ob_digit[--shift_digits])\r
+ inexact = 1;\r
+ }\r
+ long_normalize(x);\r
+ x_size = Py_SIZE(x);\r
+\r
+ /* x //= b. If the remainder is nonzero, set inexact. We own the only\r
+ reference to x, so it's safe to modify it in-place. */\r
+ if (b_size == 1) {\r
+ digit rem = inplace_divrem1(x->ob_digit, x->ob_digit, x_size,\r
+ b->ob_digit[0]);\r
+ long_normalize(x);\r
+ if (rem)\r
+ inexact = 1;\r
+ }\r
+ else {\r
+ PyLongObject *div, *rem;\r
+ div = x_divrem(x, b, &rem);\r
+ Py_DECREF(x);\r
+ x = div;\r
+ if (x == NULL)\r
+ goto error;\r
+ if (Py_SIZE(rem))\r
+ inexact = 1;\r
+ Py_DECREF(rem);\r
+ }\r
+ x_size = ABS(Py_SIZE(x));\r
+ assert(x_size > 0); /* result of division is never zero */\r
+ x_bits = (x_size-1)*PyLong_SHIFT+bits_in_digit(x->ob_digit[x_size-1]);\r
+\r
+ /* The number of extra bits that have to be rounded away. */\r
+ extra_bits = MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;\r
+ assert(extra_bits == 2 || extra_bits == 3);\r
+\r
+ /* Round by directly modifying the low digit of x. */\r
+ mask = (digit)1 << (extra_bits - 1);\r
+ low = x->ob_digit[0] | inexact;\r
+ if (low & mask && low & (3*mask-1))\r
+ low += mask;\r
+ x->ob_digit[0] = low & ~(mask-1U);\r
+\r
+ /* Convert x to a double dx; the conversion is exact. */\r
+ dx = x->ob_digit[--x_size];\r
+ while (x_size > 0)\r
+ dx = dx * PyLong_BASE + x->ob_digit[--x_size];\r
+ Py_DECREF(x);\r
+\r
+ /* Check whether ldexp result will overflow a double. */\r
+ if (shift + x_bits >= DBL_MAX_EXP &&\r
+ (shift + x_bits > DBL_MAX_EXP || dx == ldexp(1.0, (int)x_bits)))\r
+ goto overflow;\r
+ result = ldexp(dx, (int)shift);\r
+\r
+ success:\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return PyFloat_FromDouble(negate ? -result : result);\r
+\r
+ underflow_or_zero:\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return PyFloat_FromDouble(negate ? -0.0 : 0.0);\r
+\r
+ overflow:\r
+ PyErr_SetString(PyExc_OverflowError,\r
+ "integer division result too large for a float");\r
+ error:\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return NULL;\r
+}\r
+\r
+static PyObject *\r
+long_mod(PyObject *v, PyObject *w)\r
+{\r
+ PyLongObject *a, *b, *mod;\r
+\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+\r
+ if (l_divmod(a, b, NULL, &mod) < 0)\r
+ mod = NULL;\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *)mod;\r
+}\r
+\r
+static PyObject *\r
+long_divmod(PyObject *v, PyObject *w)\r
+{\r
+ PyLongObject *a, *b, *div, *mod;\r
+ PyObject *z;\r
+\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+\r
+ if (l_divmod(a, b, &div, &mod) < 0) {\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return NULL;\r
+ }\r
+ z = PyTuple_New(2);\r
+ if (z != NULL) {\r
+ PyTuple_SetItem(z, 0, (PyObject *) div);\r
+ PyTuple_SetItem(z, 1, (PyObject *) mod);\r
+ }\r
+ else {\r
+ Py_DECREF(div);\r
+ Py_DECREF(mod);\r
+ }\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return z;\r
+}\r
+\r
+/* pow(v, w, x) */\r
+static PyObject *\r
+long_pow(PyObject *v, PyObject *w, PyObject *x)\r
+{\r
+ PyLongObject *a, *b, *c; /* a,b,c = v,w,x */\r
+ int negativeOutput = 0; /* if x<0 return negative output */\r
+\r
+ PyLongObject *z = NULL; /* accumulated result */\r
+ Py_ssize_t i, j, k; /* counters */\r
+ PyLongObject *temp = NULL;\r
+\r
+ /* 5-ary values. If the exponent is large enough, table is\r
+ * precomputed so that table[i] == a**i % c for i in range(32).\r
+ */\r
+ PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\r
+ 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};\r
+\r
+ /* a, b, c = v, w, x */\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+ if (PyLong_Check(x)) {\r
+ c = (PyLongObject *)x;\r
+ Py_INCREF(x);\r
+ }\r
+ else if (PyInt_Check(x)) {\r
+ c = (PyLongObject *)PyLong_FromLong(PyInt_AS_LONG(x));\r
+ if (c == NULL)\r
+ goto Error;\r
+ }\r
+ else if (x == Py_None)\r
+ c = NULL;\r
+ else {\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ Py_INCREF(Py_NotImplemented);\r
+ return Py_NotImplemented;\r
+ }\r
+\r
+ if (Py_SIZE(b) < 0) { /* if exponent is negative */\r
+ if (c) {\r
+ PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "\r
+ "cannot be negative when 3rd argument specified");\r
+ goto Error;\r
+ }\r
+ else {\r
+ /* else return a float. This works because we know\r
+ that this calls float_pow() which converts its\r
+ arguments to double. */\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return PyFloat_Type.tp_as_number->nb_power(v, w, x);\r
+ }\r
+ }\r
+\r
+ if (c) {\r
+ /* if modulus == 0:\r
+ raise ValueError() */\r
+ if (Py_SIZE(c) == 0) {\r
+ PyErr_SetString(PyExc_ValueError,\r
+ "pow() 3rd argument cannot be 0");\r
+ goto Error;\r
+ }\r
+\r
+ /* if modulus < 0:\r
+ negativeOutput = True\r
+ modulus = -modulus */\r
+ if (Py_SIZE(c) < 0) {\r
+ negativeOutput = 1;\r
+ temp = (PyLongObject *)_PyLong_Copy(c);\r
+ if (temp == NULL)\r
+ goto Error;\r
+ Py_DECREF(c);\r
+ c = temp;\r
+ temp = NULL;\r
+ c->ob_size = - c->ob_size;\r
+ }\r
+\r
+ /* if modulus == 1:\r
+ return 0 */\r
+ if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {\r
+ z = (PyLongObject *)PyLong_FromLong(0L);\r
+ goto Done;\r
+ }\r
+\r
+ /* if base < 0:\r
+ base = base % modulus\r
+ Having the base positive just makes things easier. */\r
+ if (Py_SIZE(a) < 0) {\r
+ if (l_divmod(a, c, NULL, &temp) < 0)\r
+ goto Error;\r
+ Py_DECREF(a);\r
+ a = temp;\r
+ temp = NULL;\r
+ }\r
+ }\r
+\r
+ /* At this point a, b, and c are guaranteed non-negative UNLESS\r
+ c is NULL, in which case a may be negative. */\r
+\r
+ z = (PyLongObject *)PyLong_FromLong(1L);\r
+ if (z == NULL)\r
+ goto Error;\r
+\r
+ /* Perform a modular reduction, X = X % c, but leave X alone if c\r
+ * is NULL.\r
+ */\r
+#define REDUCE(X) \\r
+ do { \\r
+ if (c != NULL) { \\r
+ if (l_divmod(X, c, NULL, &temp) < 0) \\r
+ goto Error; \\r
+ Py_XDECREF(X); \\r
+ X = temp; \\r
+ temp = NULL; \\r
+ } \\r
+ } while(0)\r
+\r
+ /* Multiply two values, then reduce the result:\r
+ result = X*Y % c. If c is NULL, skip the mod. */\r
+#define MULT(X, Y, result) \\r
+ do { \\r
+ temp = (PyLongObject *)long_mul(X, Y); \\r
+ if (temp == NULL) \\r
+ goto Error; \\r
+ Py_XDECREF(result); \\r
+ result = temp; \\r
+ temp = NULL; \\r
+ REDUCE(result); \\r
+ } while(0)\r
+\r
+ if (Py_SIZE(b) <= FIVEARY_CUTOFF) {\r
+ /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */\r
+ /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */\r
+ for (i = Py_SIZE(b) - 1; i >= 0; --i) {\r
+ digit bi = b->ob_digit[i];\r
+\r
+ for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {\r
+ MULT(z, z, z);\r
+ if (bi & j)\r
+ MULT(z, a, z);\r
+ }\r
+ }\r
+ }\r
+ else {\r
+ /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */\r
+ Py_INCREF(z); /* still holds 1L */\r
+ table[0] = z;\r
+ for (i = 1; i < 32; ++i)\r
+ MULT(table[i-1], a, table[i]);\r
+\r
+ for (i = Py_SIZE(b) - 1; i >= 0; --i) {\r
+ const digit bi = b->ob_digit[i];\r
+\r
+ for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {\r
+ const int index = (bi >> j) & 0x1f;\r
+ for (k = 0; k < 5; ++k)\r
+ MULT(z, z, z);\r
+ if (index)\r
+ MULT(z, table[index], z);\r
+ }\r
+ }\r
+ }\r
+\r
+ if (negativeOutput && (Py_SIZE(z) != 0)) {\r
+ temp = (PyLongObject *)long_sub(z, c);\r
+ if (temp == NULL)\r
+ goto Error;\r
+ Py_DECREF(z);\r
+ z = temp;\r
+ temp = NULL;\r
+ }\r
+ goto Done;\r
+\r
+ Error:\r
+ if (z != NULL) {\r
+ Py_DECREF(z);\r
+ z = NULL;\r
+ }\r
+ /* fall through */\r
+ Done:\r
+ if (Py_SIZE(b) > FIVEARY_CUTOFF) {\r
+ for (i = 0; i < 32; ++i)\r
+ Py_XDECREF(table[i]);\r
+ }\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ Py_XDECREF(c);\r
+ Py_XDECREF(temp);\r
+ return (PyObject *)z;\r
+}\r
+\r
+static PyObject *\r
+long_invert(PyLongObject *v)\r
+{\r
+ /* Implement ~x as -(x+1) */\r
+ PyLongObject *x;\r
+ PyLongObject *w;\r
+ w = (PyLongObject *)PyLong_FromLong(1L);\r
+ if (w == NULL)\r
+ return NULL;\r
+ x = (PyLongObject *) long_add(v, w);\r
+ Py_DECREF(w);\r
+ if (x == NULL)\r
+ return NULL;\r
+ Py_SIZE(x) = -(Py_SIZE(x));\r
+ return (PyObject *)x;\r
+}\r
+\r
+static PyObject *\r
+long_neg(PyLongObject *v)\r
+{\r
+ PyLongObject *z;\r
+ if (v->ob_size == 0 && PyLong_CheckExact(v)) {\r
+ /* -0 == 0 */\r
+ Py_INCREF(v);\r
+ return (PyObject *) v;\r
+ }\r
+ z = (PyLongObject *)_PyLong_Copy(v);\r
+ if (z != NULL)\r
+ z->ob_size = -(v->ob_size);\r
+ return (PyObject *)z;\r
+}\r
+\r
+static PyObject *\r
+long_abs(PyLongObject *v)\r
+{\r
+ if (v->ob_size < 0)\r
+ return long_neg(v);\r
+ else\r
+ return long_long((PyObject *)v);\r
+}\r
+\r
+static int\r
+long_nonzero(PyLongObject *v)\r
+{\r
+ return Py_SIZE(v) != 0;\r
+}\r
+\r
+static PyObject *\r
+long_rshift(PyLongObject *v, PyLongObject *w)\r
+{\r
+ PyLongObject *a, *b;\r
+ PyLongObject *z = NULL;\r
+ Py_ssize_t shiftby, newsize, wordshift, loshift, hishift, i, j;\r
+ digit lomask, himask;\r
+\r
+ CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);\r
+\r
+ if (Py_SIZE(a) < 0) {\r
+ /* Right shifting negative numbers is harder */\r
+ PyLongObject *a1, *a2;\r
+ a1 = (PyLongObject *) long_invert(a);\r
+ if (a1 == NULL)\r
+ goto rshift_error;\r
+ a2 = (PyLongObject *) long_rshift(a1, b);\r
+ Py_DECREF(a1);\r
+ if (a2 == NULL)\r
+ goto rshift_error;\r
+ z = (PyLongObject *) long_invert(a2);\r
+ Py_DECREF(a2);\r
+ }\r
+ else {\r
+ shiftby = PyLong_AsSsize_t((PyObject *)b);\r
+ if (shiftby == -1L && PyErr_Occurred())\r
+ goto rshift_error;\r
+ if (shiftby < 0) {\r
+ PyErr_SetString(PyExc_ValueError,\r
+ "negative shift count");\r
+ goto rshift_error;\r
+ }\r
+ wordshift = shiftby / PyLong_SHIFT;\r
+ newsize = ABS(Py_SIZE(a)) - wordshift;\r
+ if (newsize <= 0) {\r
+ z = _PyLong_New(0);\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *)z;\r
+ }\r
+ loshift = shiftby % PyLong_SHIFT;\r
+ hishift = PyLong_SHIFT - loshift;\r
+ lomask = ((digit)1 << hishift) - 1;\r
+ himask = PyLong_MASK ^ lomask;\r
+ z = _PyLong_New(newsize);\r
+ if (z == NULL)\r
+ goto rshift_error;\r
+ if (Py_SIZE(a) < 0)\r
+ Py_SIZE(z) = -(Py_SIZE(z));\r
+ for (i = 0, j = wordshift; i < newsize; i++, j++) {\r
+ z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;\r
+ if (i+1 < newsize)\r
+ z->ob_digit[i] |= (a->ob_digit[j+1] << hishift) & himask;\r
+ }\r
+ z = long_normalize(z);\r
+ }\r
+ rshift_error:\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *) z;\r
+\r
+}\r
+\r
+static PyObject *\r
+long_lshift(PyObject *v, PyObject *w)\r
+{\r
+ /* This version due to Tim Peters */\r
+ PyLongObject *a, *b;\r
+ PyLongObject *z = NULL;\r
+ Py_ssize_t shiftby, oldsize, newsize, wordshift, remshift, i, j;\r
+ twodigits accum;\r
+\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+\r
+ shiftby = PyLong_AsSsize_t((PyObject *)b);\r
+ if (shiftby == -1L && PyErr_Occurred())\r
+ goto lshift_error;\r
+ if (shiftby < 0) {\r
+ PyErr_SetString(PyExc_ValueError, "negative shift count");\r
+ goto lshift_error;\r
+ }\r
+ /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */\r
+ wordshift = shiftby / PyLong_SHIFT;\r
+ remshift = shiftby - wordshift * PyLong_SHIFT;\r
+\r
+ oldsize = ABS(a->ob_size);\r
+ newsize = oldsize + wordshift;\r
+ if (remshift)\r
+ ++newsize;\r
+ z = _PyLong_New(newsize);\r
+ if (z == NULL)\r
+ goto lshift_error;\r
+ if (a->ob_size < 0)\r
+ z->ob_size = -(z->ob_size);\r
+ for (i = 0; i < wordshift; i++)\r
+ z->ob_digit[i] = 0;\r
+ accum = 0;\r
+ for (i = wordshift, j = 0; j < oldsize; i++, j++) {\r
+ accum |= (twodigits)a->ob_digit[j] << remshift;\r
+ z->ob_digit[i] = (digit)(accum & PyLong_MASK);\r
+ accum >>= PyLong_SHIFT;\r
+ }\r
+ if (remshift)\r
+ z->ob_digit[newsize-1] = (digit)accum;\r
+ else\r
+ assert(!accum);\r
+ z = long_normalize(z);\r
+ lshift_error:\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *) z;\r
+}\r
+\r
+/* Compute two's complement of digit vector a[0:m], writing result to\r
+ z[0:m]. The digit vector a need not be normalized, but should not\r
+ be entirely zero. a and z may point to the same digit vector. */\r
+\r
+static void\r
+v_complement(digit *z, digit *a, Py_ssize_t m)\r
+{\r
+ Py_ssize_t i;\r
+ digit carry = 1;\r
+ for (i = 0; i < m; ++i) {\r
+ carry += a[i] ^ PyLong_MASK;\r
+ z[i] = carry & PyLong_MASK;\r
+ carry >>= PyLong_SHIFT;\r
+ }\r
+ assert(carry == 0);\r
+}\r
+\r
+/* Bitwise and/xor/or operations */\r
+\r
+static PyObject *\r
+long_bitwise(PyLongObject *a,\r
+ int op, /* '&', '|', '^' */\r
+ PyLongObject *b)\r
+{\r
+ int nega, negb, negz;\r
+ Py_ssize_t size_a, size_b, size_z, i;\r
+ PyLongObject *z;\r
+\r
+ /* Bitwise operations for negative numbers operate as though\r
+ on a two's complement representation. So convert arguments\r
+ from sign-magnitude to two's complement, and convert the\r
+ result back to sign-magnitude at the end. */\r
+\r
+ /* If a is negative, replace it by its two's complement. */\r
+ size_a = ABS(Py_SIZE(a));\r
+ nega = Py_SIZE(a) < 0;\r
+ if (nega) {\r
+ z = _PyLong_New(size_a);\r
+ if (z == NULL)\r
+ return NULL;\r
+ v_complement(z->ob_digit, a->ob_digit, size_a);\r
+ a = z;\r
+ }\r
+ else\r
+ /* Keep reference count consistent. */\r
+ Py_INCREF(a);\r
+\r
+ /* Same for b. */\r
+ size_b = ABS(Py_SIZE(b));\r
+ negb = Py_SIZE(b) < 0;\r
+ if (negb) {\r
+ z = _PyLong_New(size_b);\r
+ if (z == NULL) {\r
+ Py_DECREF(a);\r
+ return NULL;\r
+ }\r
+ v_complement(z->ob_digit, b->ob_digit, size_b);\r
+ b = z;\r
+ }\r
+ else\r
+ Py_INCREF(b);\r
+\r
+ /* Swap a and b if necessary to ensure size_a >= size_b. */\r
+ if (size_a < size_b) {\r
+ z = a; a = b; b = z;\r
+ size_z = size_a; size_a = size_b; size_b = size_z;\r
+ negz = nega; nega = negb; negb = negz;\r
+ }\r
+\r
+ /* JRH: The original logic here was to allocate the result value (z)\r
+ as the longer of the two operands. However, there are some cases\r
+ where the result is guaranteed to be shorter than that: AND of two\r
+ positives, OR of two negatives: use the shorter number. AND with\r
+ mixed signs: use the positive number. OR with mixed signs: use the\r
+ negative number.\r
+ */\r
+ switch (op) {\r
+ case '^':\r
+ negz = nega ^ negb;\r
+ size_z = size_a;\r
+ break;\r
+ case '&':\r
+ negz = nega & negb;\r
+ size_z = negb ? size_a : size_b;\r
+ break;\r
+ case '|':\r
+ negz = nega | negb;\r
+ size_z = negb ? size_b : size_a;\r
+ break;\r
+ default:\r
+ PyErr_BadArgument();\r
+ return NULL;\r
+ }\r
+\r
+ /* We allow an extra digit if z is negative, to make sure that\r
+ the final two's complement of z doesn't overflow. */\r
+ z = _PyLong_New(size_z + negz);\r
+ if (z == NULL) {\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return NULL;\r
+ }\r
+\r
+ /* Compute digits for overlap of a and b. */\r
+ switch(op) {\r
+ case '&':\r
+ for (i = 0; i < size_b; ++i)\r
+ z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i];\r
+ break;\r
+ case '|':\r
+ for (i = 0; i < size_b; ++i)\r
+ z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i];\r
+ break;\r
+ case '^':\r
+ for (i = 0; i < size_b; ++i)\r
+ z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i];\r
+ break;\r
+ default:\r
+ PyErr_BadArgument();\r
+ return NULL;\r
+ }\r
+\r
+ /* Copy any remaining digits of a, inverting if necessary. */\r
+ if (op == '^' && negb)\r
+ for (; i < size_z; ++i)\r
+ z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK;\r
+ else if (i < size_z)\r
+ memcpy(&z->ob_digit[i], &a->ob_digit[i],\r
+ (size_z-i)*sizeof(digit));\r
+\r
+ /* Complement result if negative. */\r
+ if (negz) {\r
+ Py_SIZE(z) = -(Py_SIZE(z));\r
+ z->ob_digit[size_z] = PyLong_MASK;\r
+ v_complement(z->ob_digit, z->ob_digit, size_z+1);\r
+ }\r
+\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return (PyObject *)long_normalize(z);\r
+}\r
+\r
+static PyObject *\r
+long_and(PyObject *v, PyObject *w)\r
+{\r
+ PyLongObject *a, *b;\r
+ PyObject *c;\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+ c = long_bitwise(a, '&', b);\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return c;\r
+}\r
+\r
+static PyObject *\r
+long_xor(PyObject *v, PyObject *w)\r
+{\r
+ PyLongObject *a, *b;\r
+ PyObject *c;\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+ c = long_bitwise(a, '^', b);\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return c;\r
+}\r
+\r
+static PyObject *\r
+long_or(PyObject *v, PyObject *w)\r
+{\r
+ PyLongObject *a, *b;\r
+ PyObject *c;\r
+ CONVERT_BINOP(v, w, &a, &b);\r
+ c = long_bitwise(a, '|', b);\r
+ Py_DECREF(a);\r
+ Py_DECREF(b);\r
+ return c;\r
+}\r
+\r
+static int\r
+long_coerce(PyObject **pv, PyObject **pw)\r
+{\r
+ if (PyInt_Check(*pw)) {\r
+ *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));\r
+ if (*pw == NULL)\r
+ return -1;\r
+ Py_INCREF(*pv);\r
+ return 0;\r
+ }\r
+ else if (PyLong_Check(*pw)) {\r
+ Py_INCREF(*pv);\r
+ Py_INCREF(*pw);\r
+ return 0;\r
+ }\r
+ return 1; /* Can't do it */\r
+}\r
+\r
+static PyObject *\r
+long_long(PyObject *v)\r
+{\r
+ if (PyLong_CheckExact(v))\r
+ Py_INCREF(v);\r
+ else\r
+ v = _PyLong_Copy((PyLongObject *)v);\r
+ return v;\r
+}\r
+\r
+static PyObject *\r
+long_int(PyObject *v)\r
+{\r
+ long x;\r
+ x = PyLong_AsLong(v);\r
+ if (PyErr_Occurred()) {\r
+ if (PyErr_ExceptionMatches(PyExc_OverflowError)) {\r
+ PyErr_Clear();\r
+ if (PyLong_CheckExact(v)) {\r
+ Py_INCREF(v);\r
+ return v;\r
+ }\r
+ else\r
+ return _PyLong_Copy((PyLongObject *)v);\r
+ }\r
+ else\r
+ return NULL;\r
+ }\r
+ return PyInt_FromLong(x);\r
+}\r
+\r
+static PyObject *\r
+long_float(PyObject *v)\r
+{\r
+ double result;\r
+ result = PyLong_AsDouble(v);\r
+ if (result == -1.0 && PyErr_Occurred())\r
+ return NULL;\r
+ return PyFloat_FromDouble(result);\r
+}\r
+\r
+static PyObject *\r
+long_oct(PyObject *v)\r
+{\r
+ return _PyLong_Format(v, 8, 1, 0);\r
+}\r
+\r
+static PyObject *\r
+long_hex(PyObject *v)\r
+{\r
+ return _PyLong_Format(v, 16, 1, 0);\r
+}\r
+\r
+static PyObject *\r
+long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);\r
+\r
+static PyObject *\r
+long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)\r
+{\r
+ PyObject *x = NULL;\r
+ int base = -909; /* unlikely! */\r
+ static char *kwlist[] = {"x", "base", 0};\r
+\r
+ if (type != &PyLong_Type)\r
+ return long_subtype_new(type, args, kwds); /* Wimp out */\r
+ if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist,\r
+ &x, &base))\r
+ return NULL;\r
+ if (x == NULL)\r
+ return PyLong_FromLong(0L);\r
+ if (base == -909)\r
+ return PyNumber_Long(x);\r
+ else if (PyString_Check(x)) {\r
+ /* Since PyLong_FromString doesn't have a length parameter,\r
+ * check here for possible NULs in the string. */\r
+ char *string = PyString_AS_STRING(x);\r
+ if (strlen(string) != (size_t)PyString_Size(x)) {\r
+ /* create a repr() of the input string,\r
+ * just like PyLong_FromString does. */\r
+ PyObject *srepr;\r
+ srepr = PyObject_Repr(x);\r
+ if (srepr == NULL)\r
+ return NULL;\r
+ PyErr_Format(PyExc_ValueError,\r
+ "invalid literal for long() with base %d: %s",\r
+ base, PyString_AS_STRING(srepr));\r
+ Py_DECREF(srepr);\r
+ return NULL;\r
+ }\r
+ return PyLong_FromString(PyString_AS_STRING(x), NULL, base);\r
+ }\r
+#ifdef Py_USING_UNICODE\r
+ else if (PyUnicode_Check(x))\r
+ return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),\r
+ PyUnicode_GET_SIZE(x),\r
+ base);\r
+#endif\r
+ else {\r
+ PyErr_SetString(PyExc_TypeError,\r
+ "long() can't convert non-string with explicit base");\r
+ return NULL;\r
+ }\r
+}\r
+\r
+/* Wimpy, slow approach to tp_new calls for subtypes of long:\r
+ first create a regular long from whatever arguments we got,\r
+ then allocate a subtype instance and initialize it from\r
+ the regular long. The regular long is then thrown away.\r
+*/\r
+static PyObject *\r
+long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)\r
+{\r
+ PyLongObject *tmp, *newobj;\r
+ Py_ssize_t i, n;\r
+\r
+ assert(PyType_IsSubtype(type, &PyLong_Type));\r
+ tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);\r
+ if (tmp == NULL)\r
+ return NULL;\r
+ assert(PyLong_CheckExact(tmp));\r
+ n = Py_SIZE(tmp);\r
+ if (n < 0)\r
+ n = -n;\r
+ newobj = (PyLongObject *)type->tp_alloc(type, n);\r
+ if (newobj == NULL) {\r
+ Py_DECREF(tmp);\r
+ return NULL;\r
+ }\r
+ assert(PyLong_Check(newobj));\r
+ Py_SIZE(newobj) = Py_SIZE(tmp);\r
+ for (i = 0; i < n; i++)\r
+ newobj->ob_digit[i] = tmp->ob_digit[i];\r
+ Py_DECREF(tmp);\r
+ return (PyObject *)newobj;\r
+}\r
+\r
+static PyObject *\r
+long_getnewargs(PyLongObject *v)\r
+{\r
+ return Py_BuildValue("(N)", _PyLong_Copy(v));\r
+}\r
+\r
+static PyObject *\r
+long_get0(PyLongObject *v, void *context) {\r
+ return PyLong_FromLong(0L);\r
+}\r
+\r
+static PyObject *\r
+long_get1(PyLongObject *v, void *context) {\r
+ return PyLong_FromLong(1L);\r
+}\r
+\r
+static PyObject *\r
+long__format__(PyObject *self, PyObject *args)\r
+{\r
+ PyObject *format_spec;\r
+\r
+ if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))\r
+ return NULL;\r
+ if (PyBytes_Check(format_spec))\r
+ return _PyLong_FormatAdvanced(self,\r
+ PyBytes_AS_STRING(format_spec),\r
+ PyBytes_GET_SIZE(format_spec));\r
+ if (PyUnicode_Check(format_spec)) {\r
+ /* Convert format_spec to a str */\r
+ PyObject *result;\r
+ PyObject *str_spec = PyObject_Str(format_spec);\r
+\r
+ if (str_spec == NULL)\r
+ return NULL;\r
+\r
+ result = _PyLong_FormatAdvanced(self,\r
+ PyBytes_AS_STRING(str_spec),\r
+ PyBytes_GET_SIZE(str_spec));\r
+\r
+ Py_DECREF(str_spec);\r
+ return result;\r
+ }\r
+ PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");\r
+ return NULL;\r
+}\r
+\r
+static PyObject *\r
+long_sizeof(PyLongObject *v)\r
+{\r
+ Py_ssize_t res;\r
+\r
+ res = v->ob_type->tp_basicsize + ABS(Py_SIZE(v))*sizeof(digit);\r
+ return PyInt_FromSsize_t(res);\r
+}\r
+\r
+static PyObject *\r
+long_bit_length(PyLongObject *v)\r
+{\r
+ PyLongObject *result, *x, *y;\r
+ Py_ssize_t ndigits, msd_bits = 0;\r
+ digit msd;\r
+\r
+ assert(v != NULL);\r
+ assert(PyLong_Check(v));\r
+\r
+ ndigits = ABS(Py_SIZE(v));\r
+ if (ndigits == 0)\r
+ return PyInt_FromLong(0);\r
+\r
+ msd = v->ob_digit[ndigits-1];\r
+ while (msd >= 32) {\r
+ msd_bits += 6;\r
+ msd >>= 6;\r
+ }\r
+ msd_bits += (long)(BitLengthTable[msd]);\r
+\r
+ if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)\r
+ return PyInt_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);\r
+\r
+ /* expression above may overflow; use Python integers instead */\r
+ result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);\r
+ if (result == NULL)\r
+ return NULL;\r
+ x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);\r
+ if (x == NULL)\r
+ goto error;\r
+ y = (PyLongObject *)long_mul(result, x);\r
+ Py_DECREF(x);\r
+ if (y == NULL)\r
+ goto error;\r
+ Py_DECREF(result);\r
+ result = y;\r
+\r
+ x = (PyLongObject *)PyLong_FromLong((long)msd_bits);\r
+ if (x == NULL)\r
+ goto error;\r
+ y = (PyLongObject *)long_add(result, x);\r
+ Py_DECREF(x);\r
+ if (y == NULL)\r
+ goto error;\r
+ Py_DECREF(result);\r
+ result = y;\r
+\r
+ return (PyObject *)result;\r
+\r
+ error:\r
+ Py_DECREF(result);\r
+ return NULL;\r
+}\r
+\r
+PyDoc_STRVAR(long_bit_length_doc,\r
+"long.bit_length() -> int or long\n\\r
+\n\\r
+Number of bits necessary to represent self in binary.\n\\r
+>>> bin(37L)\n\\r
+'0b100101'\n\\r
+>>> (37L).bit_length()\n\\r
+6");\r
+\r
+#if 0\r
+static PyObject *\r
+long_is_finite(PyObject *v)\r
+{\r
+ Py_RETURN_TRUE;\r
+}\r
+#endif\r
+\r
+static PyMethodDef long_methods[] = {\r
+ {"conjugate", (PyCFunction)long_long, METH_NOARGS,\r
+ "Returns self, the complex conjugate of any long."},\r
+ {"bit_length", (PyCFunction)long_bit_length, METH_NOARGS,\r
+ long_bit_length_doc},\r
+#if 0\r
+ {"is_finite", (PyCFunction)long_is_finite, METH_NOARGS,\r
+ "Returns always True."},\r
+#endif\r
+ {"__trunc__", (PyCFunction)long_long, METH_NOARGS,\r
+ "Truncating an Integral returns itself."},\r
+ {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS},\r
+ {"__format__", (PyCFunction)long__format__, METH_VARARGS},\r
+ {"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS,\r
+ "Returns size in memory, in bytes"},\r
+ {NULL, NULL} /* sentinel */\r
+};\r
+\r
+static PyGetSetDef long_getset[] = {\r
+ {"real",\r
+ (getter)long_long, (setter)NULL,\r
+ "the real part of a complex number",\r
+ NULL},\r
+ {"imag",\r
+ (getter)long_get0, (setter)NULL,\r
+ "the imaginary part of a complex number",\r
+ NULL},\r
+ {"numerator",\r
+ (getter)long_long, (setter)NULL,\r
+ "the numerator of a rational number in lowest terms",\r
+ NULL},\r
+ {"denominator",\r
+ (getter)long_get1, (setter)NULL,\r
+ "the denominator of a rational number in lowest terms",\r
+ NULL},\r
+ {NULL} /* Sentinel */\r
+};\r
+\r
+PyDoc_STRVAR(long_doc,\r
+"long(x[, base]) -> integer\n\\r
+\n\\r
+Convert a string or number to a long integer, if possible. A floating\n\\r
+point argument will be truncated towards zero (this does not include a\n\\r
+string representation of a floating point number!) When converting a\n\\r
+string, use the optional base. It is an error to supply a base when\n\\r
+converting a non-string.");\r
+\r
+static PyNumberMethods long_as_number = {\r
+ (binaryfunc)long_add, /*nb_add*/\r
+ (binaryfunc)long_sub, /*nb_subtract*/\r
+ (binaryfunc)long_mul, /*nb_multiply*/\r
+ long_classic_div, /*nb_divide*/\r
+ long_mod, /*nb_remainder*/\r
+ long_divmod, /*nb_divmod*/\r
+ long_pow, /*nb_power*/\r
+ (unaryfunc)long_neg, /*nb_negative*/\r
+ (unaryfunc)long_long, /*tp_positive*/\r
+ (unaryfunc)long_abs, /*tp_absolute*/\r
+ (inquiry)long_nonzero, /*tp_nonzero*/\r
+ (unaryfunc)long_invert, /*nb_invert*/\r
+ long_lshift, /*nb_lshift*/\r
+ (binaryfunc)long_rshift, /*nb_rshift*/\r
+ long_and, /*nb_and*/\r
+ long_xor, /*nb_xor*/\r
+ long_or, /*nb_or*/\r
+ long_coerce, /*nb_coerce*/\r
+ long_int, /*nb_int*/\r
+ long_long, /*nb_long*/\r
+ long_float, /*nb_float*/\r
+ long_oct, /*nb_oct*/\r
+ long_hex, /*nb_hex*/\r
+ 0, /* nb_inplace_add */\r
+ 0, /* nb_inplace_subtract */\r
+ 0, /* nb_inplace_multiply */\r
+ 0, /* nb_inplace_divide */\r
+ 0, /* nb_inplace_remainder */\r
+ 0, /* nb_inplace_power */\r
+ 0, /* nb_inplace_lshift */\r
+ 0, /* nb_inplace_rshift */\r
+ 0, /* nb_inplace_and */\r
+ 0, /* nb_inplace_xor */\r
+ 0, /* nb_inplace_or */\r
+ long_div, /* nb_floor_divide */\r
+ long_true_divide, /* nb_true_divide */\r
+ 0, /* nb_inplace_floor_divide */\r
+ 0, /* nb_inplace_true_divide */\r
+ long_long, /* nb_index */\r
+};\r
+\r
+PyTypeObject PyLong_Type = {\r
+ PyObject_HEAD_INIT(&PyType_Type)\r
+ 0, /* ob_size */\r
+ "long", /* tp_name */\r
+ offsetof(PyLongObject, ob_digit), /* tp_basicsize */\r
+ sizeof(digit), /* tp_itemsize */\r
+ long_dealloc, /* tp_dealloc */\r
+ 0, /* tp_print */\r
+ 0, /* tp_getattr */\r
+ 0, /* tp_setattr */\r
+ (cmpfunc)long_compare, /* tp_compare */\r
+ long_repr, /* tp_repr */\r
+ &long_as_number, /* tp_as_number */\r
+ 0, /* tp_as_sequence */\r
+ 0, /* tp_as_mapping */\r
+ (hashfunc)long_hash, /* tp_hash */\r
+ 0, /* tp_call */\r
+ long_str, /* tp_str */\r
+ PyObject_GenericGetAttr, /* tp_getattro */\r
+ 0, /* tp_setattro */\r
+ 0, /* tp_as_buffer */\r
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |\r
+ Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */\r
+ long_doc, /* tp_doc */\r
+ 0, /* tp_traverse */\r
+ 0, /* tp_clear */\r
+ 0, /* tp_richcompare */\r
+ 0, /* tp_weaklistoffset */\r
+ 0, /* tp_iter */\r
+ 0, /* tp_iternext */\r
+ long_methods, /* tp_methods */\r
+ 0, /* tp_members */\r
+ long_getset, /* tp_getset */\r
+ 0, /* tp_base */\r
+ 0, /* tp_dict */\r
+ 0, /* tp_descr_get */\r
+ 0, /* tp_descr_set */\r
+ 0, /* tp_dictoffset */\r
+ 0, /* tp_init */\r
+ 0, /* tp_alloc */\r
+ long_new, /* tp_new */\r
+ PyObject_Del, /* tp_free */\r
+};\r
+\r
+static PyTypeObject Long_InfoType;\r
+\r
+PyDoc_STRVAR(long_info__doc__,\r
+"sys.long_info\n\\r
+\n\\r
+A struct sequence that holds information about Python's\n\\r
+internal representation of integers. The attributes are read only.");\r
+\r
+static PyStructSequence_Field long_info_fields[] = {\r
+ {"bits_per_digit", "size of a digit in bits"},\r
+ {"sizeof_digit", "size in bytes of the C type used to represent a digit"},\r
+ {NULL, NULL}\r
+};\r
+\r
+static PyStructSequence_Desc long_info_desc = {\r
+ "sys.long_info", /* name */\r
+ long_info__doc__, /* doc */\r
+ long_info_fields, /* fields */\r
+ 2 /* number of fields */\r
+};\r
+\r
+PyObject *\r
+PyLong_GetInfo(void)\r
+{\r
+ PyObject* long_info;\r
+ int field = 0;\r
+ long_info = PyStructSequence_New(&Long_InfoType);\r
+ if (long_info == NULL)\r
+ return NULL;\r
+ PyStructSequence_SET_ITEM(long_info, field++,\r
+ PyInt_FromLong(PyLong_SHIFT));\r
+ PyStructSequence_SET_ITEM(long_info, field++,\r
+ PyInt_FromLong(sizeof(digit)));\r
+ if (PyErr_Occurred()) {\r
+ Py_CLEAR(long_info);\r
+ return NULL;\r
+ }\r
+ return long_info;\r
+}\r
+\r
+int\r
+_PyLong_Init(void)\r
+{\r
+ /* initialize long_info */\r
+ if (Long_InfoType.tp_name == 0)\r
+ PyStructSequence_InitType(&Long_InfoType, &long_info_desc);\r
+ return 1;\r
+}\r
projects / mirror_edk2.git / commitdiff