AppPkg/.../Python-2.7.10: AppPkg.dsc, pyconfig.h, PyMod-2.7.10

[mirror_edk2.git] / AppPkg / Applications / Python / Python-2.7.10 / PyMod-2.7.10 / Objects / longobject.c

/** @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