+++ /dev/null
-/** @file\r
- Long (arbitrary precision) integer object implementation.\r
-\r
- Copyright (c) 2015, Daryl McDaniel. All rights reserved.<BR>\r
- This program and the accompanying materials are licensed and made available under\r
- the terms and conditions of the BSD License that accompanies this distribution.\r
- The full text of the license may be found at\r
- http://opensource.org/licenses/bsd-license.\r
-\r
- THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
- WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
-**/\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
-#undef ABS\r
-#define ABS(x) ((x) < 0 ? -(x) : (x))\r
-\r
-#undef MIN\r
-#undef MAX\r
-#define MAX(x, y) ((x) < (y) ? (y) : (x))\r
-#define MIN(x, y) ((x) > (y) ? (y) : (x))\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 C int from a long int object or any object that has an __int__\r
- method. Return -1 and set an error if overflow occurs. */\r
-\r
-int\r
-_PyLong_AsInt(PyObject *obj)\r
-{\r
- int overflow;\r
- long result = PyLong_AsLongAndOverflow(obj, &overflow);\r
- if (overflow || result > INT_MAX || result < INT_MIN) {\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 int");\r
- return -1;\r
- }\r
- return (int)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
- /* Reduce base by modulus in some cases:\r
- 1. If base < 0. Forcing the base non-negative makes things easier.\r
- 2. If base is obviously larger than the modulus. The "small\r
- exponent" case later can multiply directly by base repeatedly,\r
- while the "large exponent" case multiplies directly by base 31\r
- times. It can be unboundedly faster to multiply by\r
- base % modulus instead.\r
- We could _always_ do this reduction, but l_divmod() isn't cheap,\r
- so we only do it when it buys something. */\r
- if (Py_SIZE(a) < 0 || Py_SIZE(a) > Py_SIZE(c)) {\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
- if (base != -909) {\r
- PyErr_SetString(PyExc_TypeError,\r
- "long() missing string argument");\r
- return NULL;\r
- }\r
- return PyLong_FromLong(0L);\r
- }\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=0) -> long\n\\r
-long(x, base=10) -> long\n\\r
-\n\\r
-Convert a number or string to a long integer, or return 0L if no arguments\n\\r
-are given. If x is floating point, the conversion truncates towards zero.\n\\r
-\n\\r
-If x is not a number or if base is given, then x must be a string or\n\\r
-Unicode object representing an integer literal in the given base. The\n\\r
-literal can be preceded by '+' or '-' and be surrounded by whitespace.\n\\r
-The base defaults to 10. Valid bases are 0 and 2-36. Base 0 means to\n\\r
-interpret the base from the string as an integer literal.\n\\r
->>> int('0b100', base=0)\n\\r
-4L");\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 / blobdiff