Back to index

python3.2  3.2.2
Defines | Functions | Variables
longobject.c File Reference
#include "Python.h"
#include "longintrepr.h"
#include <float.h>
#include <ctype.h>
#include <stddef.h>

Go to the source code of this file.

Defines

#define NSMALLPOSINTS   257
#define NSMALLNEGINTS   5
#define MEDIUM_VALUE(x)
#define ABS(x)   ((x) < 0 ? -(x) : (x))
#define CHECK_SMALL_INT(ival)
#define NEGATE(x)
#define KARATSUBA_CUTOFF   70
#define KARATSUBA_SQUARE_CUTOFF   (2 * KARATSUBA_CUTOFF)
#define FIVEARY_CUTOFF   8
#define MAX(x, y)   ((x) < (y) ? (y) : (x))
#define MIN(x, y)   ((x) > (y) ? (y) : (x))
#define SIGCHECK(PyTryBlock)
#define MAX_LONG_DIGITS   ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
#define PY_ABS_LONG_MIN   (0-(unsigned long)LONG_MIN)
#define PY_ABS_SSIZE_T_MIN   (0-(size_t)PY_SSIZE_T_MIN)
#define CHECK_BINOP(v, w)
#define EXP2_DBL_MANT_DIG   (ldexp(1.0, DBL_MANT_DIG))
#define TEST_COND(cond)   ((cond) ? Py_True : Py_False)
#define MANT_DIG_DIGITS   (DBL_MANT_DIG / PyLong_SHIFT)
#define MANT_DIG_BITS   (DBL_MANT_DIG % PyLong_SHIFT)
#define REDUCE(X)
#define MULT(X, Y, result)

Functions

static PyObjectget_small_int (sdigit ival)
static PyLongObject * maybe_small_long (PyLongObject *v)
static PyLongObject * long_normalize (register PyLongObject *v)
PyLongObject * _PyLong_New (Py_ssize_t size)
PyObject_PyLong_Copy (PyLongObject *src)
PyObjectPyLong_FromLong (long ival)
PyObjectPyLong_FromUnsignedLong (unsigned long ival)
PyObjectPyLong_FromDouble (double dval)
long PyLong_AsLongAndOverflow (PyObject *vv, int *overflow)
long PyLong_AsLong (PyObject *obj)
Py_ssize_t PyLong_AsSsize_t (PyObject *vv)
unsigned long PyLong_AsUnsignedLong (PyObject *vv)
size_t PyLong_AsSize_t (PyObject *vv)
static unsigned long _PyLong_AsUnsignedLongMask (PyObject *vv)
unsigned long PyLong_AsUnsignedLongMask (register PyObject *op)
int _PyLong_Sign (PyObject *vv)
size_t _PyLong_NumBits (PyObject *vv)
PyObject_PyLong_FromByteArray (const unsigned char *bytes, size_t n, int little_endian, int is_signed)
int _PyLong_AsByteArray (PyLongObject *v, unsigned char *bytes, size_t n, int little_endian, int is_signed)
PyObjectPyLong_FromVoidPtr (void *p)
voidPyLong_AsVoidPtr (PyObject *vv)
static int bits_in_digit (digit d)
static digit v_iadd (digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
static digit v_isub (digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
static digit v_lshift (digit *z, digit *a, Py_ssize_t m, int d)
static digit v_rshift (digit *z, digit *a, Py_ssize_t m, int d)
static digit inplace_divrem1 (digit *pout, digit *pin, Py_ssize_t size, digit n)
static PyLongObject * divrem1 (PyLongObject *a, digit n, digit *prem)
static PyObjectlong_to_decimal_string (PyObject *aa)
PyObject_PyLong_Format (PyObject *aa, int base)
static PyLongObject * long_from_binary_base (char **str, int base)
PyObjectPyLong_FromString (char *str, char **pend, int base)
PyObjectPyLong_FromUnicode (Py_UNICODE *u, Py_ssize_t length, int base)
static PyLongObject * x_divrem (PyLongObject *, PyLongObject *, PyLongObject **)
static PyObjectlong_long (PyObject *v)
static int long_divrem (PyLongObject *a, PyLongObject *b, PyLongObject **pdiv, PyLongObject **prem)
double _PyLong_Frexp (PyLongObject *a, Py_ssize_t *e)
double PyLong_AsDouble (PyObject *v)
static void long_dealloc (PyObject *v)
static int long_compare (PyLongObject *a, PyLongObject *b)
static PyObjectlong_richcompare (PyObject *self, PyObject *other, int op)
static Py_hash_t long_hash (PyLongObject *v)
static PyLongObject * x_add (PyLongObject *a, PyLongObject *b)
static PyLongObject * x_sub (PyLongObject *a, PyLongObject *b)
static PyObjectlong_add (PyLongObject *a, PyLongObject *b)
static PyObjectlong_sub (PyLongObject *a, PyLongObject *b)
static PyLongObject * x_mul (PyLongObject *a, PyLongObject *b)
static int kmul_split (PyLongObject *n, Py_ssize_t size, PyLongObject **high, PyLongObject **low)
static PyLongObject * k_lopsided_mul (PyLongObject *a, PyLongObject *b)
static PyLongObject * k_mul (PyLongObject *a, PyLongObject *b)
static PyObjectlong_mul (PyLongObject *a, PyLongObject *b)
static int l_divmod (PyLongObject *v, PyLongObject *w, PyLongObject **pdiv, PyLongObject **pmod)
static PyObjectlong_div (PyObject *a, PyObject *b)
static PyObjectlong_true_divide (PyObject *v, PyObject *w)
static PyObjectlong_mod (PyObject *a, PyObject *b)
static PyObjectlong_divmod (PyObject *a, PyObject *b)
static PyObjectlong_pow (PyObject *v, PyObject *w, PyObject *x)
static PyObjectlong_invert (PyLongObject *v)
static PyObjectlong_neg (PyLongObject *v)
static PyObjectlong_abs (PyLongObject *v)
static int long_bool (PyLongObject *v)
static PyObjectlong_rshift (PyLongObject *a, PyLongObject *b)
static PyObjectlong_lshift (PyObject *v, PyObject *w)
static void v_complement (digit *z, digit *a, Py_ssize_t m)
static PyObjectlong_bitwise (PyLongObject *a, int op, PyLongObject *b)
static PyObjectlong_and (PyObject *a, PyObject *b)
static PyObjectlong_xor (PyObject *a, PyObject *b)
static PyObjectlong_or (PyObject *a, PyObject *b)
static PyObjectlong_float (PyObject *v)
static PyObjectlong_subtype_new (PyTypeObject *type, PyObject *args, PyObject *kwds)
static PyObjectlong_new (PyTypeObject *type, PyObject *args, PyObject *kwds)
static PyObjectlong_getnewargs (PyLongObject *v)
static PyObjectlong_get0 (PyLongObject *v, void *context)
static PyObjectlong_get1 (PyLongObject *v, void *context)
static PyObjectlong__format__ (PyObject *self, PyObject *args)
PyObject_PyLong_DivmodNear (PyObject *a, PyObject *b)
static PyObjectlong_round (PyObject *self, PyObject *args)
static PyObjectlong_sizeof (PyLongObject *v)
static PyObjectlong_bit_length (PyLongObject *v)
 PyDoc_STRVAR (long_bit_length_doc,"int.bit_length() -> int\n\ \n\ Number of bits necessary to represent self in binary.\n\ >>> bin(37)\n\ '0b100101'\n\ >>> (37).bit_length()\n\ 6")
static PyObjectlong_to_bytes (PyLongObject *v, PyObject *args, PyObject *kwds)
 PyDoc_STRVAR (long_to_bytes_doc,"int.to_bytes(length, byteorder, *, signed=False) -> bytes\n\ \n\ Return an array of bytes representing an integer.\n\ \n\ The integer is represented using length bytes. An OverflowError is\n\ raised if the integer is not representable with the given number of\n\ bytes.\n\ \n\ The byteorder argument determines the byte order used to represent the\n\ integer. If byteorder is 'big', the most significant byte is at the\n\ beginning of the byte array. If byteorder is 'little', the most\n\ significant byte is at the end of the byte array. To request the native\n\ byte order of the host system, use `sys.byteorder' as the byte order value.\n\ \n\ The signed keyword-only argument determines whether two's complement is\n\ used to represent the integer. If signed is False and a negative integer\n\ is given, an OverflowError is raised.")
static PyObjectlong_from_bytes (PyTypeObject *type, PyObject *args, PyObject *kwds)
 PyDoc_STRVAR (long_from_bytes_doc,"int.from_bytes(bytes, byteorder, *, signed=False) -> int\n\ \n\ Return the integer represented by the given array of bytes.\n\ \n\ The bytes argument must either support the buffer protocol or be an\n\ iterable object producing bytes. Bytes and bytearray are examples of\n\ built-in objects that support the buffer protocol.\n\ \n\ The byteorder argument determines the byte order used to represent the\n\ integer. If byteorder is 'big', the most significant byte is at the\n\ beginning of the byte array. If byteorder is 'little', the most\n\ significant byte is at the end of the byte array. To request the native\n\ byte order of the host system, use `sys.byteorder' as the byte order value.\n\ \n\ The signed keyword-only argument indicates whether two's complement is\n\ used to represent the integer.")
 PyDoc_STRVAR (long_doc,"int(x[, base]) -> integer\n\ \n\ Convert a string or number to an integer, if possible. A floating\n\ point argument will be truncated towards zero (this does not include a\n\ string representation of a floating point number!) When converting a\n\ string, use the optional base. It is an error to supply a base when\n\ converting a non-string.")
 PyDoc_STRVAR (int_info__doc__,"sys.int_info\n\ \n\ A struct sequence that holds information about Python's\n\ internal representation of integers. The attributes are read only.")
PyObjectPyLong_GetInfo (void)
int _PyLong_Init (void)
void PyLong_Fini (void)

Variables

static PyLongObject small_ints [NSMALLNEGINTS+NSMALLPOSINTS]
static const unsigned char BitLengthTable [32]
unsigned char _PyLong_DigitValue [256]
static PyMethodDef long_methods []
static PyGetSetDef long_getset []
static PyNumberMethods long_as_number
PyTypeObject PyLong_Type
static PyTypeObject Int_InfoType
static PyStructSequence_Field int_info_fields []
static PyStructSequence_Desc int_info_desc

Define Documentation

#define ABS (   x)    ((x) < 0 ? -(x) : (x))

Definition at line 23 of file longobject.c.

#define CHECK_BINOP (   v,
 
)
Value:
do {                                                \
        if (!PyLong_Check(v) || !PyLong_Check(w)) {     \
            Py_INCREF(Py_NotImplemented);               \
            return Py_NotImplemented;                   \
        }                                               \
    } while(0)

Definition at line 1383 of file longobject.c.

#define CHECK_SMALL_INT (   ival)
Value:
do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
        return get_small_int((sdigit)ival); \
    } while(0)

Definition at line 49 of file longobject.c.

#define EXP2_DBL_MANT_DIG   (ldexp(1.0, DBL_MANT_DIG))

Definition at line 2363 of file longobject.c.

#define FIVEARY_CUTOFF   8

Definition at line 90 of file longobject.c.

#define KARATSUBA_CUTOFF   70

Definition at line 82 of file longobject.c.

Definition at line 83 of file longobject.c.

#define MANT_DIG_BITS   (DBL_MANT_DIG % PyLong_SHIFT)

Definition at line 3289 of file longobject.c.

#define MANT_DIG_DIGITS   (DBL_MANT_DIG / PyLong_SHIFT)

Definition at line 3288 of file longobject.c.

#define MAX (   x,
 
)    ((x) < (y) ? (y) : (x))

Definition at line 94 of file longobject.c.

#define MAX_LONG_DIGITS   ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))

Definition at line 122 of file longobject.c.

#define MEDIUM_VALUE (   x)
Value:
(Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] :   \
             (Py_SIZE(x) == 0 ? (sdigit)0 :                             \
              (sdigit)(x)->ob_digit[0]))

Definition at line 20 of file longobject.c.

#define MIN (   x,
 
)    ((x) > (y) ? (y) : (x))

Definition at line 95 of file longobject.c.

#define MULT (   X,
  Y,
  result 
)
Value:
do {                                        \
        temp = (PyLongObject *)long_mul(X, Y);  \
        if (temp == NULL)                       \
            goto Error;                         \
        Py_XDECREF(result);                     \
        result = temp;                          \
        temp = NULL;                            \
        REDUCE(result);                         \
    } while(0)
#define NEGATE (   x)
Value:
do if (Py_REFCNT(x) == 1) Py_SIZE(x) = -Py_SIZE(x);  \
       else { PyObject* tmp=PyLong_FromLong(-MEDIUM_VALUE(x));  \
           Py_DECREF(x); (x) = (PyLongObject*)tmp; }               \
    while(0)

Definition at line 73 of file longobject.c.

#define NSMALLNEGINTS   5

Definition at line 16 of file longobject.c.

#define NSMALLPOSINTS   257

Definition at line 13 of file longobject.c.

#define PY_ABS_LONG_MIN   (0-(unsigned long)LONG_MIN)

Definition at line 322 of file longobject.c.

Definition at line 323 of file longobject.c.

#define REDUCE (   X)
Value:
do {                                                \
        if (c != NULL) {                                \
            if (l_divmod(X, c, NULL, &temp) < 0)        \
                goto Error;                             \
            Py_XDECREF(X);                              \
            X = temp;                                   \
            temp = NULL;                                \
        }                                               \
    } while(0)
#define SIGCHECK (   PyTryBlock)
Value:
do {                                        \
        if (PyErr_CheckSignals()) PyTryBlock    \
    } while(0)

Definition at line 97 of file longobject.c.

#define TEST_COND (   cond)    ((cond) ? Py_True : Py_False)

Definition at line 2530 of file longobject.c.


Function Documentation

int _PyLong_AsByteArray ( PyLongObject *  v,
unsigned char *  bytes,
size_t  n,
int  little_endian,
int  is_signed 
)

Definition at line 794 of file longobject.c.

{
    Py_ssize_t i;               /* index into v->ob_digit */
    Py_ssize_t ndigits;         /* |v->ob_size| */
    twodigits accum;            /* sliding register */
    unsigned int accumbits;     /* # bits in accum */
    int do_twos_comp;           /* store 2's-comp?  is_signed and v < 0 */
    digit carry;                /* for computing 2's-comp */
    size_t j;                   /* # bytes filled */
    unsigned char* p;           /* pointer to next byte in bytes */
    int pincr;                  /* direction to move p */

    assert(v != NULL && PyLong_Check(v));

    if (Py_SIZE(v) < 0) {
        ndigits = -(Py_SIZE(v));
        if (!is_signed) {
            PyErr_SetString(PyExc_OverflowError,
                            "can't convert negative int to unsigned");
            return -1;
        }
        do_twos_comp = 1;
    }
    else {
        ndigits = Py_SIZE(v);
        do_twos_comp = 0;
    }

    if (little_endian) {
        p = bytes;
        pincr = 1;
    }
    else {
        p = bytes + n - 1;
        pincr = -1;
    }

    /* Copy over all the Python digits.
       It's crucial that every Python digit except for the MSD contribute
       exactly PyLong_SHIFT bits to the total, so first assert that the long is
       normalized. */
    assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
    j = 0;
    accum = 0;
    accumbits = 0;
    carry = do_twos_comp ? 1 : 0;
    for (i = 0; i < ndigits; ++i) {
        digit thisdigit = v->ob_digit[i];
        if (do_twos_comp) {
            thisdigit = (thisdigit ^ PyLong_MASK) + carry;
            carry = thisdigit >> PyLong_SHIFT;
            thisdigit &= PyLong_MASK;
        }
        /* Because we're going LSB to MSB, thisdigit is more
           significant than what's already in accum, so needs to be
           prepended to accum. */
        accum |= (twodigits)thisdigit << accumbits;

        /* The most-significant digit may be (probably is) at least
           partly empty. */
        if (i == ndigits - 1) {
            /* Count # of sign bits -- they needn't be stored,
             * although for signed conversion we need later to
             * make sure at least one sign bit gets stored. */
            digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;
            while (s != 0) {
                s >>= 1;
                accumbits++;
            }
        }
        else
            accumbits += PyLong_SHIFT;

        /* Store as many bytes as possible. */
        while (accumbits >= 8) {
            if (j >= n)
                goto Overflow;
            ++j;
            *p = (unsigned char)(accum & 0xff);
            p += pincr;
            accumbits -= 8;
            accum >>= 8;
        }
    }

    /* Store the straggler (if any). */
    assert(accumbits < 8);
    assert(carry == 0);  /* else do_twos_comp and *every* digit was 0 */
    if (accumbits > 0) {
        if (j >= n)
            goto Overflow;
        ++j;
        if (do_twos_comp) {
            /* Fill leading bits of the byte with sign bits
               (appropriately pretending that the long had an
               infinite supply of sign bits). */
            accum |= (~(twodigits)0) << accumbits;
        }
        *p = (unsigned char)(accum & 0xff);
        p += pincr;
    }
    else if (j == n && n > 0 && is_signed) {
        /* The main loop filled the byte array exactly, so the code
           just above didn't get to ensure there's a sign bit, and the
           loop below wouldn't add one either.  Make sure a sign bit
           exists. */
        unsigned char msb = *(p - pincr);
        int sign_bit_set = msb >= 0x80;
        assert(accumbits == 0);
        if (sign_bit_set == do_twos_comp)
            return 0;
        else
            goto Overflow;
    }

    /* Fill remaining bytes with copies of the sign bit. */
    {
        unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
        for ( ; j < n; ++j, p += pincr)
            *p = signbyte;
    }

    return 0;

  Overflow:
    PyErr_SetString(PyExc_OverflowError, "int too big to convert");
    return -1;

}

Here is the call graph for this function:

Here is the caller graph for this function:

static unsigned long _PyLong_AsUnsignedLongMask ( PyObject vv) [static]

Definition at line 575 of file longobject.c.

{
    register PyLongObject *v;
    unsigned long x;
    Py_ssize_t i;
    int sign;

    if (vv == NULL || !PyLong_Check(vv)) {
        PyErr_BadInternalCall();
        return (unsigned long) -1;
    }
    v = (PyLongObject *)vv;
    i = Py_SIZE(v);
    switch (i) {
    case 0: return 0;
    case 1: return v->ob_digit[0];
    }
    sign = 1;
    x = 0;
    if (i < 0) {
        sign = -1;
        i = -i;
    }
    while (--i >= 0) {
        x = (x << PyLong_SHIFT) | v->ob_digit[i];
    }
    return x * sign;
}

Here is the caller graph for this function:

PyObject* _PyLong_Copy ( PyLongObject *  src)

Definition at line 149 of file longobject.c.

{
    PyLongObject *result;
    Py_ssize_t i;

    assert(src != NULL);
    i = Py_SIZE(src);
    if (i < 0)
        i = -(i);
    if (i < 2) {
        sdigit ival = src->ob_digit[0];
        if (Py_SIZE(src) < 0)
            ival = -ival;
        CHECK_SMALL_INT(ival);
    }
    result = _PyLong_New(i);
    if (result != NULL) {
        Py_SIZE(result) = Py_SIZE(src);
        while (--i >= 0)
            result->ob_digit[i] = src->ob_digit[i];
    }
    return (PyObject *)result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 4237 of file longobject.c.

{
    PyLongObject *quo = NULL, *rem = NULL;
    PyObject *one = NULL, *twice_rem, *result, *temp;
    int cmp, quo_is_odd, quo_is_neg;

    /* Equivalent Python code:

       def divmod_near(a, b):
           q, r = divmod(a, b)
           # round up if either r / b > 0.5, or r / b == 0.5 and q is odd.
           # The expression r / b > 0.5 is equivalent to 2 * r > b if b is
           # positive, 2 * r < b if b negative.
           greater_than_half = 2*r > b if b > 0 else 2*r < b
           exactly_half = 2*r == b
           if greater_than_half or exactly_half and q % 2 == 1:
               q += 1
               r -= b
           return q, r

    */
    if (!PyLong_Check(a) || !PyLong_Check(b)) {
        PyErr_SetString(PyExc_TypeError,
                        "non-integer arguments in division");
        return NULL;
    }

    /* Do a and b have different signs?  If so, quotient is negative. */
    quo_is_neg = (Py_SIZE(a) < 0) != (Py_SIZE(b) < 0);

    one = PyLong_FromLong(1L);
    if (one == NULL)
        return NULL;

    if (long_divrem((PyLongObject*)a, (PyLongObject*)b, &quo, &rem) < 0)
        goto error;

    /* compare twice the remainder with the divisor, to see
       if we need to adjust the quotient and remainder */
    twice_rem = long_lshift((PyObject *)rem, one);
    if (twice_rem == NULL)
        goto error;
    if (quo_is_neg) {
        temp = long_neg((PyLongObject*)twice_rem);
        Py_DECREF(twice_rem);
        twice_rem = temp;
        if (twice_rem == NULL)
            goto error;
    }
    cmp = long_compare((PyLongObject *)twice_rem, (PyLongObject *)b);
    Py_DECREF(twice_rem);

    quo_is_odd = Py_SIZE(quo) != 0 && ((quo->ob_digit[0] & 1) != 0);
    if ((Py_SIZE(b) < 0 ? cmp < 0 : cmp > 0) || (cmp == 0 && quo_is_odd)) {
        /* fix up quotient */
        if (quo_is_neg)
            temp = long_sub(quo, (PyLongObject *)one);
        else
            temp = long_add(quo, (PyLongObject *)one);
        Py_DECREF(quo);
        quo = (PyLongObject *)temp;
        if (quo == NULL)
            goto error;
        /* and remainder */
        if (quo_is_neg)
            temp = long_add(rem, (PyLongObject *)b);
        else
            temp = long_sub(rem, (PyLongObject *)b);
        Py_DECREF(rem);
        rem = (PyLongObject *)temp;
        if (rem == NULL)
            goto error;
    }

    result = PyTuple_New(2);
    if (result == NULL)
        goto error;

    /* PyTuple_SET_ITEM steals references */
    PyTuple_SET_ITEM(result, 0, (PyObject *)quo);
    PyTuple_SET_ITEM(result, 1, (PyObject *)rem);
    Py_DECREF(one);
    return result;

  error:
    Py_XDECREF(quo);
    Py_XDECREF(rem);
    Py_XDECREF(one);
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PyObject* _PyLong_Format ( PyObject aa,
int  base 
)

Definition at line 1660 of file longobject.c.

{
    register PyLongObject *a = (PyLongObject *)aa;
    PyObject *str;
    Py_ssize_t i, sz;
    Py_ssize_t size_a;
    Py_UNICODE *p, sign = '\0';
    int bits;

    assert(base == 2 || base == 8 || base == 10 || base == 16);
    if (base == 10)
        return long_to_decimal_string((PyObject *)a);

    if (a == NULL || !PyLong_Check(a)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    size_a = ABS(Py_SIZE(a));

    /* Compute a rough upper bound for the length of the string */
    switch (base) {
    case 16:
        bits = 4;
        break;
    case 8:
        bits = 3;
        break;
    case 2:
        bits = 1;
        break;
    default:
        assert(0); /* shouldn't ever get here */
        bits = 0; /* to silence gcc warning */
    }
    /* compute length of output string: allow 2 characters for prefix and
       1 for possible '-' sign. */
    if (size_a > (PY_SSIZE_T_MAX - 3) / PyLong_SHIFT) {
        PyErr_SetString(PyExc_OverflowError,
                        "int is too large to format");
        return NULL;
    }
    /* now size_a * PyLong_SHIFT + 3 <= PY_SSIZE_T_MAX, so the RHS below
       is safe from overflow */
    sz = 3 + (size_a * PyLong_SHIFT + (bits - 1)) / bits;
    assert(sz >= 0);
    str = PyUnicode_FromUnicode(NULL, sz);
    if (str == NULL)
        return NULL;
    p = PyUnicode_AS_UNICODE(str) + sz;
    *p = '\0';
    if (Py_SIZE(a) < 0)
        sign = '-';

    if (Py_SIZE(a) == 0) {
        *--p = '0';
    }
    else {
        /* JRH: special case for power-of-2 bases */
        twodigits accum = 0;
        int accumbits = 0;              /* # of bits in accum */
        for (i = 0; i < size_a; ++i) {
            accum |= (twodigits)a->ob_digit[i] << accumbits;
            accumbits += PyLong_SHIFT;
            assert(accumbits >= bits);
            do {
                Py_UNICODE cdigit;
                cdigit = (Py_UNICODE)(accum & (base - 1));
                cdigit += (cdigit < 10) ? '0' : 'a'-10;
                assert(p > PyUnicode_AS_UNICODE(str));
                *--p = cdigit;
                accumbits -= bits;
                accum >>= bits;
            } while (i < size_a-1 ? accumbits >= bits : accum > 0);
        }
    }

    if (base == 16)
        *--p = 'x';
    else if (base == 8)
        *--p = 'o';
    else /* (base == 2) */
        *--p = 'b';
    *--p = '0';
    if (sign)
        *--p = sign;
    if (p != PyUnicode_AS_UNICODE(str)) {
        Py_UNICODE *q = PyUnicode_AS_UNICODE(str);
        assert(p > q);
        do {
        } while ((*q++ = *p++) != '\0');
        q--;
        if (PyUnicode_Resize(&str,(Py_ssize_t) (q -
                                        PyUnicode_AS_UNICODE(str)))) {
            Py_DECREF(str);
            return NULL;
        }
    }
    return (PyObject *)str;
}

Here is the call graph for this function:

Here is the caller graph for this function:

double _PyLong_Frexp ( PyLongObject *  a,
Py_ssize_t e 
)

Definition at line 2367 of file longobject.c.

{
    Py_ssize_t a_size, a_bits, shift_digits, shift_bits, x_size;
    /* See below for why x_digits is always large enough. */
    digit rem, x_digits[2 + (DBL_MANT_DIG + 1) / PyLong_SHIFT];
    double dx;
    /* Correction term for round-half-to-even rounding.  For a digit x,
       "x + half_even_correction[x & 7]" gives x rounded to the nearest
       multiple of 4, rounding ties to a multiple of 8. */
    static const int half_even_correction[8] = {0, -1, -2, 1, 0, -1, 2, 1};

    a_size = ABS(Py_SIZE(a));
    if (a_size == 0) {
        /* Special case for 0: significand 0.0, exponent 0. */
        *e = 0;
        return 0.0;
    }
    a_bits = bits_in_digit(a->ob_digit[a_size-1]);
    /* The following is an overflow-free version of the check
       "if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */
    if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&
        (a_size > (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 ||
         a_bits > (PY_SSIZE_T_MAX - 1) % PyLong_SHIFT + 1))
        goto overflow;
    a_bits = (a_size - 1) * PyLong_SHIFT + a_bits;

    /* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size]
       (shifting left if a_bits <= DBL_MANT_DIG + 2).

       Number of digits needed for result: write // for floor division.
       Then if shifting left, we end up using

         1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT

       digits.  If shifting right, we use

         a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT

       digits.  Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with
       the inequalities

         m // PyLong_SHIFT + n // PyLong_SHIFT <= (m + n) // PyLong_SHIFT
         m // PyLong_SHIFT - n // PyLong_SHIFT <=
                                          1 + (m - n - 1) // PyLong_SHIFT,

       valid for any integers m and n, we find that x_size satisfies

         x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT

       in both cases.
    */
    if (a_bits <= DBL_MANT_DIG + 2) {
        shift_digits = (DBL_MANT_DIG + 2 - a_bits) / PyLong_SHIFT;
        shift_bits = (DBL_MANT_DIG + 2 - a_bits) % PyLong_SHIFT;
        x_size = 0;
        while (x_size < shift_digits)
            x_digits[x_size++] = 0;
        rem = v_lshift(x_digits + x_size, a->ob_digit, a_size,
                       (int)shift_bits);
        x_size += a_size;
        x_digits[x_size++] = rem;
    }
    else {
        shift_digits = (a_bits - DBL_MANT_DIG - 2) / PyLong_SHIFT;
        shift_bits = (a_bits - DBL_MANT_DIG - 2) % PyLong_SHIFT;
        rem = v_rshift(x_digits, a->ob_digit + shift_digits,
                       a_size - shift_digits, (int)shift_bits);
        x_size = a_size - shift_digits;
        /* For correct rounding below, we need the least significant
           bit of x to be 'sticky' for this shift: if any of the bits
           shifted out was nonzero, we set the least significant bit
           of x. */
        if (rem)
            x_digits[0] |= 1;
        else
            while (shift_digits > 0)
                if (a->ob_digit[--shift_digits]) {
                    x_digits[0] |= 1;
                    break;
                }
    }
    assert(1 <= x_size &&
           x_size <= (Py_ssize_t)(sizeof(x_digits)/sizeof(digit)));

    /* Round, and convert to double. */
    x_digits[0] += half_even_correction[x_digits[0] & 7];
    dx = x_digits[--x_size];
    while (x_size > 0)
        dx = dx * PyLong_BASE + x_digits[--x_size];

    /* Rescale;  make correction if result is 1.0. */
    dx /= 4.0 * EXP2_DBL_MANT_DIG;
    if (dx == 1.0) {
        if (a_bits == PY_SSIZE_T_MAX)
            goto overflow;
        dx = 0.5;
        a_bits += 1;
    }

    *e = a_bits;
    return Py_SIZE(a) < 0 ? -dx : dx;

  overflow:
    /* exponent > PY_SSIZE_T_MAX */
    PyErr_SetString(PyExc_OverflowError,
                    "huge integer: number of bits overflows a Py_ssize_t");
    *e = 0;
    return -1.0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PyObject* _PyLong_FromByteArray ( const unsigned char *  bytes,
size_t  n,
int  little_endian,
int  is_signed 
)

Definition at line 683 of file longobject.c.

{
    const unsigned char* pstartbyte;    /* LSB of bytes */
    int incr;                           /* direction to move pstartbyte */
    const unsigned char* pendbyte;      /* MSB of bytes */
    size_t numsignificantbytes;         /* number of bytes that matter */
    Py_ssize_t ndigits;                 /* number of Python long digits */
    PyLongObject* v;                    /* result */
    Py_ssize_t idigit = 0;              /* next free index in v->ob_digit */

    if (n == 0)
        return PyLong_FromLong(0L);

    if (little_endian) {
        pstartbyte = bytes;
        pendbyte = bytes + n - 1;
        incr = 1;
    }
    else {
        pstartbyte = bytes + n - 1;
        pendbyte = bytes;
        incr = -1;
    }

    if (is_signed)
        is_signed = *pendbyte >= 0x80;

    /* Compute numsignificantbytes.  This consists of finding the most
       significant byte.  Leading 0 bytes are insignificant if the number
       is positive, and leading 0xff bytes if negative. */
    {
        size_t i;
        const unsigned char* p = pendbyte;
        const int pincr = -incr;  /* search MSB to LSB */
        const unsigned char insignficant = is_signed ? 0xff : 0x00;

        for (i = 0; i < n; ++i, p += pincr) {
            if (*p != insignficant)
                break;
        }
        numsignificantbytes = n - i;
        /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
           actually has 2 significant bytes.  OTOH, 0xff0001 ==
           -0x00ffff, so we wouldn't *need* to bump it there; but we
           do for 0xffff = -0x0001.  To be safe without bothering to
           check every case, bump it regardless. */
        if (is_signed && numsignificantbytes < n)
            ++numsignificantbytes;
    }

    /* How many Python long digits do we need?  We have
       8*numsignificantbytes bits, and each Python long digit has
       PyLong_SHIFT bits, so it's the ceiling of the quotient. */
    /* catch overflow before it happens */
    if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
        PyErr_SetString(PyExc_OverflowError,
                        "byte array too long to convert to int");
        return NULL;
    }
    ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
    v = _PyLong_New(ndigits);
    if (v == NULL)
        return NULL;

    /* Copy the bits over.  The tricky parts are computing 2's-comp on
       the fly for signed numbers, and dealing with the mismatch between
       8-bit bytes and (probably) 15-bit Python digits.*/
    {
        size_t i;
        twodigits carry = 1;                    /* for 2's-comp calculation */
        twodigits accum = 0;                    /* sliding register */
        unsigned int accumbits = 0;             /* number of bits in accum */
        const unsigned char* p = pstartbyte;

        for (i = 0; i < numsignificantbytes; ++i, p += incr) {
            twodigits thisbyte = *p;
            /* Compute correction for 2's comp, if needed. */
            if (is_signed) {
                thisbyte = (0xff ^ thisbyte) + carry;
                carry = thisbyte >> 8;
                thisbyte &= 0xff;
            }
            /* Because we're going LSB to MSB, thisbyte is
               more significant than what's already in accum,
               so needs to be prepended to accum. */
            accum |= (twodigits)thisbyte << accumbits;
            accumbits += 8;
            if (accumbits >= PyLong_SHIFT) {
                /* There's enough to fill a Python digit. */
                assert(idigit < ndigits);
                v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
                ++idigit;
                accum >>= PyLong_SHIFT;
                accumbits -= PyLong_SHIFT;
                assert(accumbits < PyLong_SHIFT);
            }
        }
        assert(accumbits < PyLong_SHIFT);
        if (accumbits) {
            assert(idigit < ndigits);
            v->ob_digit[idigit] = (digit)accum;
            ++idigit;
        }
    }

    Py_SIZE(v) = is_signed ? -idigit : idigit;
    return (PyObject *)long_normalize(v);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 4837 of file longobject.c.

{
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
    int ival, size;
    PyLongObject *v = small_ints;

    for (ival = -NSMALLNEGINTS; ival <  NSMALLPOSINTS; ival++, v++) {
        size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
        if (Py_TYPE(v) == &PyLong_Type) {
            /* The element is already initialized, most likely
             * the Python interpreter was initialized before.
             */
            Py_ssize_t refcnt;
            PyObject* op = (PyObject*)v;

            refcnt = Py_REFCNT(op) < 0 ? 0 : Py_REFCNT(op);
            _Py_NewReference(op);
            /* _Py_NewReference sets the ref count to 1 but
             * the ref count might be larger. Set the refcnt
             * to the original refcnt + 1 */
            Py_REFCNT(op) = refcnt + 1;
            assert(Py_SIZE(op) == size);
            assert(v->ob_digit[0] == abs(ival));
        }
        else {
            PyObject_INIT(v, &PyLong_Type);
        }
        Py_SIZE(v) = size;
        v->ob_digit[0] = abs(ival);
    }
#endif
    /* initialize int_info */
    if (Int_InfoType.tp_name == 0)
        PyStructSequence_InitType(&Int_InfoType, &int_info_desc);

    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PyLongObject* _PyLong_New ( Py_ssize_t  size)

Definition at line 126 of file longobject.c.

{
    PyLongObject *result;
    /* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
       sizeof(digit)*size.  Previous incarnations of this code used
       sizeof(PyVarObject) instead of the offsetof, but this risks being
       incorrect in the presence of padding between the PyVarObject header
       and the digits. */
    if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
        PyErr_SetString(PyExc_OverflowError,
                        "too many digits in integer");
        return NULL;
    }
    result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
                             size*sizeof(digit));
    if (!result) {
        PyErr_NoMemory();
        return NULL;
    }
    return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 651 of file longobject.c.

{
    PyLongObject *v = (PyLongObject *)vv;
    size_t result = 0;
    Py_ssize_t ndigits;

    assert(v != NULL);
    assert(PyLong_Check(v));
    ndigits = ABS(Py_SIZE(v));
    assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
    if (ndigits > 0) {
        digit msd = v->ob_digit[ndigits - 1];

        result = (ndigits - 1) * PyLong_SHIFT;
        if (result / PyLong_SHIFT != (size_t)(ndigits - 1))
            goto Overflow;
        do {
            ++result;
            if (result == 0)
                goto Overflow;
            msd >>= 1;
        } while (msd);
    }
    return result;

  Overflow:
    PyErr_SetString(PyExc_OverflowError, "int has too many bits "
                    "to express in a platform size_t");
    return (size_t)-1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 640 of file longobject.c.

{
    PyLongObject *v = (PyLongObject *)vv;

    assert(v != NULL);
    assert(PyLong_Check(v));

    return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
}

Here is the caller graph for this function:

static int bits_in_digit ( digit  d) [static]

Definition at line 1400 of file longobject.c.

{
    int d_bits = 0;
    while (d >= 32) {
        d_bits += 6;
        d >>= 6;
    }
    d_bits += (int)BitLengthTable[d];
    return d_bits;
}

Here is the caller graph for this function:

static PyLongObject* divrem1 ( PyLongObject *  a,
digit  n,
digit *  prem 
) [static]

Definition at line 1528 of file longobject.c.

{
    const Py_ssize_t size = ABS(Py_SIZE(a));
    PyLongObject *z;

    assert(n > 0 && n <= PyLong_MASK);
    z = _PyLong_New(size);
    if (z == NULL)
        return NULL;
    *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
    return long_normalize(z);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* get_small_int ( sdigit  ival) [static]

Definition at line 37 of file longobject.c.

{
    PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS);
    Py_INCREF(v);
#ifdef COUNT_ALLOCS
    if (ival >= 0)
        quick_int_allocs++;
    else
        quick_neg_int_allocs++;
#endif
    return v;
}

Here is the caller graph for this function:

static digit inplace_divrem1 ( digit *  pout,
digit *  pin,
Py_ssize_t  size,
digit  n 
) [static]

Definition at line 1507 of file longobject.c.

{
    twodigits rem = 0;

    assert(n > 0 && n <= PyLong_MASK);
    pin += size;
    pout += size;
    while (--size >= 0) {
        digit hi;
        rem = (rem << PyLong_SHIFT) | *--pin;
        *--pout = hi = (digit)(rem / n);
        rem -= (twodigits)hi * n;
    }
    return (digit)rem;
}

Here is the caller graph for this function:

static PyLongObject * k_lopsided_mul ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 3127 of file longobject.c.

{
    const Py_ssize_t asize = ABS(Py_SIZE(a));
    Py_ssize_t bsize = ABS(Py_SIZE(b));
    Py_ssize_t nbdone;          /* # of b digits already multiplied */
    PyLongObject *ret;
    PyLongObject *bslice = NULL;

    assert(asize > KARATSUBA_CUTOFF);
    assert(2 * asize <= bsize);

    /* Allocate result space, and zero it out. */
    ret = _PyLong_New(asize + bsize);
    if (ret == NULL)
        return NULL;
    memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));

    /* Successive slices of b are copied into bslice. */
    bslice = _PyLong_New(asize);
    if (bslice == NULL)
        goto fail;

    nbdone = 0;
    while (bsize > 0) {
        PyLongObject *product;
        const Py_ssize_t nbtouse = MIN(bsize, asize);

        /* Multiply the next slice of b by a. */
        memcpy(bslice->ob_digit, b->ob_digit + nbdone,
               nbtouse * sizeof(digit));
        Py_SIZE(bslice) = nbtouse;
        product = k_mul(a, bslice);
        if (product == NULL)
            goto fail;

        /* Add into result. */
        (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
                     product->ob_digit, Py_SIZE(product));
        Py_DECREF(product);

        bsize -= nbtouse;
        nbdone += nbtouse;
    }

    Py_DECREF(bslice);
    return long_normalize(ret);

  fail:
    Py_DECREF(ret);
    Py_XDECREF(bslice);
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyLongObject* k_mul ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 2906 of file longobject.c.

{
    Py_ssize_t asize = ABS(Py_SIZE(a));
    Py_ssize_t bsize = ABS(Py_SIZE(b));
    PyLongObject *ah = NULL;
    PyLongObject *al = NULL;
    PyLongObject *bh = NULL;
    PyLongObject *bl = NULL;
    PyLongObject *ret = NULL;
    PyLongObject *t1, *t2, *t3;
    Py_ssize_t shift;           /* the number of digits we split off */
    Py_ssize_t i;

    /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
     * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh  + ah*bh + al*bl
     * Then the original product is
     *     ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
     * By picking X to be a power of 2, "*X" is just shifting, and it's
     * been reduced to 3 multiplies on numbers half the size.
     */

    /* We want to split based on the larger number; fiddle so that b
     * is largest.
     */
    if (asize > bsize) {
        t1 = a;
        a = b;
        b = t1;

        i = asize;
        asize = bsize;
        bsize = i;
    }

    /* Use gradeschool math when either number is too small. */
    i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
    if (asize <= i) {
        if (asize == 0)
            return (PyLongObject *)PyLong_FromLong(0);
        else
            return x_mul(a, b);
    }

    /* If a is small compared to b, splitting on b gives a degenerate
     * case with ah==0, and Karatsuba may be (even much) less efficient
     * than "grade school" then.  However, we can still win, by viewing
     * b as a string of "big digits", each of width a->ob_size.  That
     * leads to a sequence of balanced calls to k_mul.
     */
    if (2 * asize <= bsize)
        return k_lopsided_mul(a, b);

    /* Split a & b into hi & lo pieces. */
    shift = bsize >> 1;
    if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
    assert(Py_SIZE(ah) > 0);            /* the split isn't degenerate */

    if (a == b) {
        bh = ah;
        bl = al;
        Py_INCREF(bh);
        Py_INCREF(bl);
    }
    else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;

    /* The plan:
     * 1. Allocate result space (asize + bsize digits:  that's always
     *    enough).
     * 2. Compute ah*bh, and copy into result at 2*shift.
     * 3. Compute al*bl, and copy into result at 0.  Note that this
     *    can't overlap with #2.
     * 4. Subtract al*bl from the result, starting at shift.  This may
     *    underflow (borrow out of the high digit), but we don't care:
     *    we're effectively doing unsigned arithmetic mod
     *    BASE**(sizea + sizeb), and so long as the *final* result fits,
     *    borrows and carries out of the high digit can be ignored.
     * 5. Subtract ah*bh from the result, starting at shift.
     * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
     *    at shift.
     */

    /* 1. Allocate result space. */
    ret = _PyLong_New(asize + bsize);
    if (ret == NULL) goto fail;
#ifdef Py_DEBUG
    /* Fill with trash, to catch reference to uninitialized digits. */
    memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
#endif

    /* 2. t1 <- ah*bh, and copy into high digits of result. */
    if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
    assert(Py_SIZE(t1) >= 0);
    assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
    memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
           Py_SIZE(t1) * sizeof(digit));

    /* Zero-out the digits higher than the ah*bh copy. */
    i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
    if (i)
        memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
               i * sizeof(digit));

    /* 3. t2 <- al*bl, and copy into the low digits. */
    if ((t2 = k_mul(al, bl)) == NULL) {
        Py_DECREF(t1);
        goto fail;
    }
    assert(Py_SIZE(t2) >= 0);
    assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
    memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));

    /* Zero out remaining digits. */
    i = 2*shift - Py_SIZE(t2);          /* number of uninitialized digits */
    if (i)
        memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));

    /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2).  We do al*bl first
     * because it's fresher in cache.
     */
    i = Py_SIZE(ret) - shift;  /* # digits after shift */
    (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
    Py_DECREF(t2);

    (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
    Py_DECREF(t1);

    /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
    if ((t1 = x_add(ah, al)) == NULL) goto fail;
    Py_DECREF(ah);
    Py_DECREF(al);
    ah = al = NULL;

    if (a == b) {
        t2 = t1;
        Py_INCREF(t2);
    }
    else if ((t2 = x_add(bh, bl)) == NULL) {
        Py_DECREF(t1);
        goto fail;
    }
    Py_DECREF(bh);
    Py_DECREF(bl);
    bh = bl = NULL;

    t3 = k_mul(t1, t2);
    Py_DECREF(t1);
    Py_DECREF(t2);
    if (t3 == NULL) goto fail;
    assert(Py_SIZE(t3) >= 0);

    /* Add t3.  It's not obvious why we can't run out of room here.
     * See the (*) comment after this function.
     */
    (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
    Py_DECREF(t3);

    return long_normalize(ret);

  fail:
    Py_XDECREF(ret);
    Py_XDECREF(ah);
    Py_XDECREF(al);
    Py_XDECREF(bh);
    Py_XDECREF(bl);
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int kmul_split ( PyLongObject *  n,
Py_ssize_t  size,
PyLongObject **  high,
PyLongObject **  low 
) [static]

Definition at line 2872 of file longobject.c.

{
    PyLongObject *hi, *lo;
    Py_ssize_t size_lo, size_hi;
    const Py_ssize_t size_n = ABS(Py_SIZE(n));

    size_lo = MIN(size_n, size);
    size_hi = size_n - size_lo;

    if ((hi = _PyLong_New(size_hi)) == NULL)
        return -1;
    if ((lo = _PyLong_New(size_lo)) == NULL) {
        Py_DECREF(hi);
        return -1;
    }

    memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
    memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));

    *high = long_normalize(hi);
    *low = long_normalize(lo);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int l_divmod ( PyLongObject *  v,
PyLongObject *  w,
PyLongObject **  pdiv,
PyLongObject **  pmod 
) [static]

Definition at line 3232 of file longobject.c.

{
    PyLongObject *div, *mod;

    if (long_divrem(v, w, &div, &mod) < 0)
        return -1;
    if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
        (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
        PyLongObject *temp;
        PyLongObject *one;
        temp = (PyLongObject *) long_add(mod, w);
        Py_DECREF(mod);
        mod = temp;
        if (mod == NULL) {
            Py_DECREF(div);
            return -1;
        }
        one = (PyLongObject *) PyLong_FromLong(1L);
        if (one == NULL ||
            (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
            Py_DECREF(mod);
            Py_DECREF(div);
            Py_XDECREF(one);
            return -1;
        }
        Py_DECREF(one);
        Py_DECREF(div);
        div = temp;
    }
    if (pdiv != NULL)
        *pdiv = div;
    else
        Py_DECREF(div);

    if (pmod != NULL)
        *pmod = mod;
    else
        Py_DECREF(mod);

    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long__format__ ( PyObject self,
PyObject args 
) [static]

Definition at line 4220 of file longobject.c.

{
    PyObject *format_spec;

    if (!PyArg_ParseTuple(args, "U:__format__", &format_spec))
        return NULL;
    return _PyLong_FormatAdvanced(self,
                                  PyUnicode_AS_UNICODE(format_spec),
                                  PyUnicode_GET_SIZE(format_spec));
}

Here is the call graph for this function:

static PyObject* long_abs ( PyLongObject *  v) [static]

Definition at line 3803 of file longobject.c.

{
    if (Py_SIZE(v) < 0)
        return long_neg(v);
    else
        return long_long((PyObject *)v);
}

Here is the call graph for this function:

static PyObject* long_add ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 2719 of file longobject.c.

{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
        PyObject *result = PyLong_FromLong(MEDIUM_VALUE(a) +
                                          MEDIUM_VALUE(b));
        return result;
    }
    if (Py_SIZE(a) < 0) {
        if (Py_SIZE(b) < 0) {
            z = x_add(a, b);
            if (z != NULL && Py_SIZE(z) != 0)
                Py_SIZE(z) = -(Py_SIZE(z));
        }
        else
            z = x_sub(b, a);
    }
    else {
        if (Py_SIZE(b) < 0)
            z = x_sub(a, b);
        else
            z = x_add(a, b);
    }
    return (PyObject *)z;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_and ( PyObject a,
PyObject b 
) [static]

Definition at line 4065 of file longobject.c.

{
    PyObject *c;
    CHECK_BINOP(a, b);
    c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b);
    return c;
}

Here is the call graph for this function:

static PyObject* long_bit_length ( PyLongObject *  v) [static]

Definition at line 4406 of file longobject.c.

{
    PyLongObject *result, *x, *y;
    Py_ssize_t ndigits, msd_bits = 0;
    digit msd;

    assert(v != NULL);
    assert(PyLong_Check(v));

    ndigits = ABS(Py_SIZE(v));
    if (ndigits == 0)
        return PyLong_FromLong(0);

    msd = v->ob_digit[ndigits-1];
    while (msd >= 32) {
        msd_bits += 6;
        msd >>= 6;
    }
    msd_bits += (long)(BitLengthTable[msd]);

    if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
        return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);

    /* expression above may overflow; use Python integers instead */
    result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
    if (result == NULL)
        return NULL;
    x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
    if (x == NULL)
        goto error;
    y = (PyLongObject *)long_mul(result, x);
    Py_DECREF(x);
    if (y == NULL)
        goto error;
    Py_DECREF(result);
    result = y;

    x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
    if (x == NULL)
        goto error;
    y = (PyLongObject *)long_add(result, x);
    Py_DECREF(x);
    if (y == NULL)
        goto error;
    Py_DECREF(result);
    result = y;

    return (PyObject *)result;

  error:
    Py_DECREF(result);
    return NULL;
}

Here is the call graph for this function:

static PyObject* long_bitwise ( PyLongObject *  a,
int  op,
PyLongObject *  b 
) [static]

Definition at line 3942 of file longobject.c.

{
    int nega, negb, negz;
    Py_ssize_t size_a, size_b, size_z, i;
    PyLongObject *z;

    /* Bitwise operations for negative numbers operate as though
       on a two's complement representation.  So convert arguments
       from sign-magnitude to two's complement, and convert the
       result back to sign-magnitude at the end. */

    /* If a is negative, replace it by its two's complement. */
    size_a = ABS(Py_SIZE(a));
    nega = Py_SIZE(a) < 0;
    if (nega) {
        z = _PyLong_New(size_a);
        if (z == NULL)
            return NULL;
        v_complement(z->ob_digit, a->ob_digit, size_a);
        a = z;
    }
    else
        /* Keep reference count consistent. */
        Py_INCREF(a);

    /* Same for b. */
    size_b = ABS(Py_SIZE(b));
    negb = Py_SIZE(b) < 0;
    if (negb) {
        z = _PyLong_New(size_b);
        if (z == NULL) {
            Py_DECREF(a);
            return NULL;
        }
        v_complement(z->ob_digit, b->ob_digit, size_b);
        b = z;
    }
    else
        Py_INCREF(b);

    /* Swap a and b if necessary to ensure size_a >= size_b. */
    if (size_a < size_b) {
        z = a; a = b; b = z;
        size_z = size_a; size_a = size_b; size_b = size_z;
        negz = nega; nega = negb; negb = negz;
    }

    /* JRH: The original logic here was to allocate the result value (z)
       as the longer of the two operands.  However, there are some cases
       where the result is guaranteed to be shorter than that: AND of two
       positives, OR of two negatives: use the shorter number.  AND with
       mixed signs: use the positive number.  OR with mixed signs: use the
       negative number.
    */
    switch (op) {
    case '^':
        negz = nega ^ negb;
        size_z = size_a;
        break;
    case '&':
        negz = nega & negb;
        size_z = negb ? size_a : size_b;
        break;
    case '|':
        negz = nega | negb;
        size_z = negb ? size_b : size_a;
        break;
    default:
        PyErr_BadArgument();
        return NULL;
    }

    /* We allow an extra digit if z is negative, to make sure that
       the final two's complement of z doesn't overflow. */
    z = _PyLong_New(size_z + negz);
    if (z == NULL) {
        Py_DECREF(a);
        Py_DECREF(b);
        return NULL;
    }

    /* Compute digits for overlap of a and b. */
    switch(op) {
    case '&':
        for (i = 0; i < size_b; ++i)
            z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i];
        break;
    case '|':
        for (i = 0; i < size_b; ++i)
            z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i];
        break;
    case '^':
        for (i = 0; i < size_b; ++i)
            z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i];
        break;
    default:
        PyErr_BadArgument();
        return NULL;
    }

    /* Copy any remaining digits of a, inverting if necessary. */
    if (op == '^' && negb)
        for (; i < size_z; ++i)
            z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK;
    else if (i < size_z)
        memcpy(&z->ob_digit[i], &a->ob_digit[i],
               (size_z-i)*sizeof(digit));

    /* Complement result if negative. */
    if (negz) {
        Py_SIZE(z) = -(Py_SIZE(z));
        z->ob_digit[size_z] = PyLong_MASK;
        v_complement(z->ob_digit, z->ob_digit, size_z+1);
    }

    Py_DECREF(a);
    Py_DECREF(b);
    return (PyObject *)maybe_small_long(long_normalize(z));
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int long_bool ( PyLongObject *  v) [static]

Definition at line 3812 of file longobject.c.

{
    return Py_SIZE(v) != 0;
}
static int long_compare ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 2508 of file longobject.c.

{
    Py_ssize_t sign;

    if (Py_SIZE(a) != Py_SIZE(b)) {
        sign = Py_SIZE(a) - Py_SIZE(b);
    }
    else {
        Py_ssize_t i = ABS(Py_SIZE(a));
        while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
            ;
        if (i < 0)
            sign = 0;
        else {
            sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
            if (Py_SIZE(a) < 0)
                sign = -sign;
        }
    }
    return sign < 0 ? -1 : sign > 0 ? 1 : 0;
}

Here is the caller graph for this function:

static void long_dealloc ( PyObject v) [static]

Definition at line 2502 of file longobject.c.

{
    Py_TYPE(v)->tp_free(v);
}
static PyObject* long_div ( PyObject a,
PyObject b 
) [static]

Definition at line 3276 of file longobject.c.

{
    PyLongObject *div;

    CHECK_BINOP(a, b);
    if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, NULL) < 0)
        div = NULL;
    return (PyObject *)div;
}

Here is the call graph for this function:

static PyObject* long_divmod ( PyObject a,
PyObject b 
) [static]

Definition at line 3562 of file longobject.c.

{
    PyLongObject *div, *mod;
    PyObject *z;

    CHECK_BINOP(a, b);

    if (l_divmod((PyLongObject*)a, (PyLongObject*)b, &div, &mod) < 0) {
        return NULL;
    }
    z = PyTuple_New(2);
    if (z != NULL) {
        PyTuple_SetItem(z, 0, (PyObject *) div);
        PyTuple_SetItem(z, 1, (PyObject *) mod);
    }
    else {
        Py_DECREF(div);
        Py_DECREF(mod);
    }
    return z;
}

Here is the call graph for this function:

static int long_divrem ( PyLongObject *  a,
PyLongObject *  b,
PyLongObject **  pdiv,
PyLongObject **  prem 
) [static]

Definition at line 2175 of file longobject.c.

{
    Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
    PyLongObject *z;

    if (size_b == 0) {
        PyErr_SetString(PyExc_ZeroDivisionError,
                        "integer division or modulo by zero");
        return -1;
    }
    if (size_a < size_b ||
        (size_a == size_b &&
         a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
        /* |a| < |b|. */
        *pdiv = (PyLongObject*)PyLong_FromLong(0);
        if (*pdiv == NULL)
            return -1;
        Py_INCREF(a);
        *prem = (PyLongObject *) a;
        return 0;
    }
    if (size_b == 1) {
        digit rem = 0;
        z = divrem1(a, b->ob_digit[0], &rem);
        if (z == NULL)
            return -1;
        *prem = (PyLongObject *) PyLong_FromLong((long)rem);
        if (*prem == NULL) {
            Py_DECREF(z);
            return -1;
        }
    }
    else {
        z = x_divrem(a, b, prem);
        if (z == NULL)
            return -1;
    }
    /* Set the signs.
       The quotient z has the sign of a*b;
       the remainder r has the sign of a,
       so a = b*z + r. */
    if ((Py_SIZE(a) < 0) != (Py_SIZE(b) < 0))
        NEGATE(z);
    if (Py_SIZE(a) < 0 && Py_SIZE(*prem) != 0)
        NEGATE(*prem);
    *pdiv = maybe_small_long(z);
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_float ( PyObject v) [static]

Definition at line 4102 of file longobject.c.

{
    double result;
    result = PyLong_AsDouble(v);
    if (result == -1.0 && PyErr_Occurred())
        return NULL;
    return PyFloat_FromDouble(result);
}

Here is the call graph for this function:

static PyLongObject* long_from_binary_base ( char **  str,
int  base 
) [static]

Definition at line 1793 of file longobject.c.

{
    char *p = *str;
    char *start = p;
    int bits_per_char;
    Py_ssize_t n;
    PyLongObject *z;
    twodigits accum;
    int bits_in_accum;
    digit *pdigit;

    assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
    n = base;
    for (bits_per_char = -1; n; ++bits_per_char)
        n >>= 1;
    /* n <- total # of bits needed, while setting p to end-of-string */
    while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
        ++p;
    *str = p;
    /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
    n = (p - start) * bits_per_char + PyLong_SHIFT - 1;
    if (n / bits_per_char < p - start) {
        PyErr_SetString(PyExc_ValueError,
                        "int string too large to convert");
        return NULL;
    }
    n = n / PyLong_SHIFT;
    z = _PyLong_New(n);
    if (z == NULL)
        return NULL;
    /* Read string from right, and fill in long from left; i.e.,
     * from least to most significant in both.
     */
    accum = 0;
    bits_in_accum = 0;
    pdigit = z->ob_digit;
    while (--p >= start) {
        int k = (int)_PyLong_DigitValue[Py_CHARMASK(*p)];
        assert(k >= 0 && k < base);
        accum |= (twodigits)k << bits_in_accum;
        bits_in_accum += bits_per_char;
        if (bits_in_accum >= PyLong_SHIFT) {
            *pdigit++ = (digit)(accum & PyLong_MASK);
            assert(pdigit - z->ob_digit <= n);
            accum >>= PyLong_SHIFT;
            bits_in_accum -= PyLong_SHIFT;
            assert(bits_in_accum < PyLong_SHIFT);
        }
    }
    if (bits_in_accum) {
        assert(bits_in_accum <= PyLong_SHIFT);
        *pdigit++ = (digit)accum;
        assert(pdigit - z->ob_digit <= n);
    }
    while (pdigit - z->ob_digit < n)
        *pdigit++ = 0;
    return long_normalize(z);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_from_bytes ( PyTypeObject type,
PyObject args,
PyObject kwds 
) [static]

Definition at line 4561 of file longobject.c.

{
    PyObject *byteorder_str;
    PyObject *is_signed_obj = NULL;
    int little_endian;
    int is_signed;
    PyObject *obj;
    PyObject *bytes;
    PyObject *long_obj;
    static char *kwlist[] = {"bytes", "byteorder", "signed", NULL};

    if (!PyArg_ParseTupleAndKeywords(args, kwds, "OU|O:from_bytes", kwlist,
                                     &obj, &byteorder_str,
                                     &is_signed_obj))
        return NULL;

    if (args != NULL && Py_SIZE(args) > 2) {
        PyErr_SetString(PyExc_TypeError,
            "'signed' is a keyword-only argument");
        return NULL;
    }

    if (!PyUnicode_CompareWithASCIIString(byteorder_str, "little"))
        little_endian = 1;
    else if (!PyUnicode_CompareWithASCIIString(byteorder_str, "big"))
        little_endian = 0;
    else {
        PyErr_SetString(PyExc_ValueError,
            "byteorder must be either 'little' or 'big'");
        return NULL;
    }

    if (is_signed_obj != NULL) {
        int cmp = PyObject_IsTrue(is_signed_obj);
        if (cmp < 0)
            return NULL;
        is_signed = cmp ? 1 : 0;
    }
    else {
        /* If the signed argument was omitted, use False as the
           default. */
        is_signed = 0;
    }

    bytes = PyObject_Bytes(obj);
    if (bytes == NULL)
        return NULL;

    long_obj = _PyLong_FromByteArray(
        (unsigned char *)PyBytes_AS_STRING(bytes), Py_SIZE(bytes),
        little_endian, is_signed);
    Py_DECREF(bytes);

    /* If from_bytes() was used on subclass, allocate new subclass
     * instance, initialize it with decoded long value and return it.
     */
    if (type != &PyLong_Type && PyType_IsSubtype(type, &PyLong_Type)) {
        PyLongObject *newobj;
        int i;
        Py_ssize_t n = ABS(Py_SIZE(long_obj));

        newobj = (PyLongObject *)type->tp_alloc(type, n);
        if (newobj == NULL) {
            Py_DECREF(long_obj);
            return NULL;
        }
        assert(PyLong_Check(newobj));
        Py_SIZE(newobj) = Py_SIZE(long_obj);
        for (i = 0; i < n; i++) {
            newobj->ob_digit[i] =
                ((PyLongObject *)long_obj)->ob_digit[i];
        }
        Py_DECREF(long_obj);
        return (PyObject *)newobj;
    }

    return long_obj;
}

Here is the call graph for this function:

static PyObject* long_get0 ( PyLongObject *  v,
void context 
) [static]

Definition at line 4210 of file longobject.c.

                                          {
    return PyLong_FromLong(0L);
}

Here is the call graph for this function:

static PyObject* long_get1 ( PyLongObject *  v,
void context 
) [static]

Definition at line 4215 of file longobject.c.

                                          {
    return PyLong_FromLong(1L);
}

Here is the call graph for this function:

static PyObject* long_getnewargs ( PyLongObject *  v) [static]

Definition at line 4204 of file longobject.c.

{
    return Py_BuildValue("(N)", _PyLong_Copy(v));
}

Here is the call graph for this function:

static Py_hash_t long_hash ( PyLongObject *  v) [static]

Definition at line 2572 of file longobject.c.

{
    Py_uhash_t x;
    Py_ssize_t i;
    int sign;

    i = Py_SIZE(v);
    switch(i) {
    case -1: return v->ob_digit[0]==1 ? -2 : -(sdigit)v->ob_digit[0];
    case 0: return 0;
    case 1: return v->ob_digit[0];
    }
    sign = 1;
    x = 0;
    if (i < 0) {
        sign = -1;
        i = -(i);
    }
    while (--i >= 0) {
        /* Here x is a quantity in the range [0, _PyHASH_MODULUS); we
           want to compute x * 2**PyLong_SHIFT + v->ob_digit[i] modulo
           _PyHASH_MODULUS.

           The computation of x * 2**PyLong_SHIFT % _PyHASH_MODULUS
           amounts to a rotation of the bits of x.  To see this, write

             x * 2**PyLong_SHIFT = y * 2**_PyHASH_BITS + z

           where y = x >> (_PyHASH_BITS - PyLong_SHIFT) gives the top
           PyLong_SHIFT bits of x (those that are shifted out of the
           original _PyHASH_BITS bits, and z = (x << PyLong_SHIFT) &
           _PyHASH_MODULUS gives the bottom _PyHASH_BITS - PyLong_SHIFT
           bits of x, shifted up.  Then since 2**_PyHASH_BITS is
           congruent to 1 modulo _PyHASH_MODULUS, y*2**_PyHASH_BITS is
           congruent to y modulo _PyHASH_MODULUS.  So

             x * 2**PyLong_SHIFT = y + z (mod _PyHASH_MODULUS).

           The right-hand side is just the result of rotating the
           _PyHASH_BITS bits of x left by PyLong_SHIFT places; since
           not all _PyHASH_BITS bits of x are 1s, the same is true
           after rotation, so 0 <= y+z < _PyHASH_MODULUS and y + z is
           the reduction of x*2**PyLong_SHIFT modulo
           _PyHASH_MODULUS. */
        x = ((x << PyLong_SHIFT) & _PyHASH_MODULUS) |
            (x >> (_PyHASH_BITS - PyLong_SHIFT));
        x += v->ob_digit[i];
        if (x >= _PyHASH_MODULUS)
            x -= _PyHASH_MODULUS;
    }
    x = x * sign;
    if (x == (Py_uhash_t)-1)
        x = (Py_uhash_t)-2;
    return (Py_hash_t)x;
}
static PyObject* long_invert ( PyLongObject *  v) [static]

Definition at line 3772 of file longobject.c.

{
    /* Implement ~x as -(x+1) */
    PyLongObject *x;
    PyLongObject *w;
    if (ABS(Py_SIZE(v)) <=1)
        return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
    w = (PyLongObject *)PyLong_FromLong(1L);
    if (w == NULL)
        return NULL;
    x = (PyLongObject *) long_add(v, w);
    Py_DECREF(w);
    if (x == NULL)
        return NULL;
    Py_SIZE(x) = -(Py_SIZE(x));
    return (PyObject *)maybe_small_long(x);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject * long_long ( PyObject v) [static]

Definition at line 4092 of file longobject.c.

{
    if (PyLong_CheckExact(v))
        Py_INCREF(v);
    else
        v = _PyLong_Copy((PyLongObject *)v);
    return v;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_lshift ( PyObject v,
PyObject w 
) [static]

Definition at line 3874 of file longobject.c.

{
    /* This version due to Tim Peters */
    PyLongObject *a = (PyLongObject*)v;
    PyLongObject *b = (PyLongObject*)w;
    PyLongObject *z = NULL;
    Py_ssize_t shiftby, oldsize, newsize, wordshift, remshift, i, j;
    twodigits accum;

    CHECK_BINOP(a, b);

    shiftby = PyLong_AsSsize_t((PyObject *)b);
    if (shiftby == -1L && PyErr_Occurred())
        goto lshift_error;
    if (shiftby < 0) {
        PyErr_SetString(PyExc_ValueError, "negative shift count");
        goto lshift_error;
    }
    /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
    wordshift = shiftby / PyLong_SHIFT;
    remshift  = shiftby - wordshift * PyLong_SHIFT;

    oldsize = ABS(Py_SIZE(a));
    newsize = oldsize + wordshift;
    if (remshift)
        ++newsize;
    z = _PyLong_New(newsize);
    if (z == NULL)
        goto lshift_error;
    if (Py_SIZE(a) < 0)
        NEGATE(z);
    for (i = 0; i < wordshift; i++)
        z->ob_digit[i] = 0;
    accum = 0;
    for (i = wordshift, j = 0; j < oldsize; i++, j++) {
        accum |= (twodigits)a->ob_digit[j] << remshift;
        z->ob_digit[i] = (digit)(accum & PyLong_MASK);
        accum >>= PyLong_SHIFT;
    }
    if (remshift)
        z->ob_digit[newsize-1] = (digit)accum;
    else
        assert(!accum);
    z = long_normalize(z);
  lshift_error:
    return (PyObject *) maybe_small_long(z);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_mod ( PyObject a,
PyObject b 
) [static]

Definition at line 3550 of file longobject.c.

{
    PyLongObject *mod;

    CHECK_BINOP(a, b);

    if (l_divmod((PyLongObject*)a, (PyLongObject*)b, NULL, &mod) < 0)
        mod = NULL;
    return (PyObject *)mod;
}

Here is the call graph for this function:

static PyObject* long_mul ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 3181 of file longobject.c.

{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    /* fast path for single-digit multiplication */
    if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
        stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
        return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
        /* if we don't have long long then we're almost certainly
           using 15-bit digits, so v will fit in a long.  In the
           unlikely event that we're using 30-bit digits on a platform
           without long long, a large v will just cause us to fall
           through to the general multiplication code below. */
        if (v >= LONG_MIN && v <= LONG_MAX)
            return PyLong_FromLong((long)v);
#endif
    }

    z = k_mul(a, b);
    /* Negate if exactly one of the inputs is negative. */
    if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z)
        NEGATE(z);
    return (PyObject *)z;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_neg ( PyLongObject *  v) [static]

Definition at line 3791 of file longobject.c.

{
    PyLongObject *z;
    if (ABS(Py_SIZE(v)) <= 1)
        return PyLong_FromLong(-MEDIUM_VALUE(v));
    z = (PyLongObject *)_PyLong_Copy(v);
    if (z != NULL)
        Py_SIZE(z) = -(Py_SIZE(v));
    return (PyObject *)z;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_new ( PyTypeObject type,
PyObject args,
PyObject kwds 
) [static]

Definition at line 4115 of file longobject.c.

{
    PyObject *obase = NULL, *x = NULL;
    long base;
    int overflow;
    static char *kwlist[] = {"x", "base", 0};

    if (type != &PyLong_Type)
        return long_subtype_new(type, args, kwds); /* Wimp out */
    if (!PyArg_ParseTupleAndKeywords(args, kwds, "|OO:int", kwlist,
                                     &x, &obase))
        return NULL;
    if (x == NULL)
        return PyLong_FromLong(0L);
    if (obase == NULL)
        return PyNumber_Long(x);

    base = PyLong_AsLongAndOverflow(obase, &overflow);
    if (base == -1 && PyErr_Occurred())
        return NULL;
    if (overflow || (base != 0 && base < 2) || base > 36) {
        PyErr_SetString(PyExc_ValueError,
                        "int() arg 2 must be >= 2 and <= 36");
        return NULL;
    }

    if (PyUnicode_Check(x))
        return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
                                  PyUnicode_GET_SIZE(x),
                                  (int)base);
    else if (PyByteArray_Check(x) || PyBytes_Check(x)) {
        /* Since PyLong_FromString doesn't have a length parameter,
         * check here for possible NULs in the string. */
        char *string;
        Py_ssize_t size = Py_SIZE(x);
        if (PyByteArray_Check(x))
            string = PyByteArray_AS_STRING(x);
        else
            string = PyBytes_AS_STRING(x);
        if (strlen(string) != (size_t)size) {
            /* We only see this if there's a null byte in x,
               x is a bytes or buffer, *and* a base is given. */
            PyErr_Format(PyExc_ValueError,
                         "invalid literal for int() with base %d: %R",
                         (int)base, x);
            return NULL;
        }
        return PyLong_FromString(string, NULL, (int)base);
    }
    else {
        PyErr_SetString(PyExc_TypeError,
                        "int() can't convert non-string with explicit base");
        return NULL;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyLongObject* long_normalize ( register PyLongObject *  v) [static]

Definition at line 107 of file longobject.c.

{
    Py_ssize_t j = ABS(Py_SIZE(v));
    Py_ssize_t i = j;

    while (i > 0 && v->ob_digit[i-1] == 0)
        --i;
    if (i != j)
        Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
    return v;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_or ( PyObject a,
PyObject b 
) [static]

Definition at line 4083 of file longobject.c.

{
    PyObject *c;
    CHECK_BINOP(a, b);
    c = long_bitwise((PyLongObject*)a, '|', (PyLongObject*)b);
    return c;
}

Here is the call graph for this function:

static PyObject* long_pow ( PyObject v,
PyObject w,
PyObject x 
) [static]

Definition at line 3586 of file longobject.c.

{
    PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
    int negativeOutput = 0;  /* if x<0 return negative output */

    PyLongObject *z = NULL;  /* accumulated result */
    Py_ssize_t i, j, k;             /* counters */
    PyLongObject *temp = NULL;

    /* 5-ary values.  If the exponent is large enough, table is
     * precomputed so that table[i] == a**i % c for i in range(32).
     */
    PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                               0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    /* a, b, c = v, w, x */
    CHECK_BINOP(v, w);
    a = (PyLongObject*)v; Py_INCREF(a);
    b = (PyLongObject*)w; Py_INCREF(b);
    if (PyLong_Check(x)) {
        c = (PyLongObject *)x;
        Py_INCREF(x);
    }
    else if (x == Py_None)
        c = NULL;
    else {
        Py_DECREF(a);
        Py_DECREF(b);
        Py_INCREF(Py_NotImplemented);
        return Py_NotImplemented;
    }

    if (Py_SIZE(b) < 0) {  /* if exponent is negative */
        if (c) {
            PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
                            "cannot be negative when 3rd argument specified");
            goto Error;
        }
        else {
            /* else return a float.  This works because we know
               that this calls float_pow() which converts its
               arguments to double. */
            Py_DECREF(a);
            Py_DECREF(b);
            return PyFloat_Type.tp_as_number->nb_power(v, w, x);
        }
    }

    if (c) {
        /* if modulus == 0:
               raise ValueError() */
        if (Py_SIZE(c) == 0) {
            PyErr_SetString(PyExc_ValueError,
                            "pow() 3rd argument cannot be 0");
            goto Error;
        }

        /* if modulus < 0:
               negativeOutput = True
               modulus = -modulus */
        if (Py_SIZE(c) < 0) {
            negativeOutput = 1;
            temp = (PyLongObject *)_PyLong_Copy(c);
            if (temp == NULL)
                goto Error;
            Py_DECREF(c);
            c = temp;
            temp = NULL;
            NEGATE(c);
        }

        /* if modulus == 1:
               return 0 */
        if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
            z = (PyLongObject *)PyLong_FromLong(0L);
            goto Done;
        }

        /* if base < 0:
               base = base % modulus
           Having the base positive just makes things easier. */
        if (Py_SIZE(a) < 0) {
            if (l_divmod(a, c, NULL, &temp) < 0)
                goto Error;
            Py_DECREF(a);
            a = temp;
            temp = NULL;
        }
    }

    /* At this point a, b, and c are guaranteed non-negative UNLESS
       c is NULL, in which case a may be negative. */

    z = (PyLongObject *)PyLong_FromLong(1L);
    if (z == NULL)
        goto Error;

    /* Perform a modular reduction, X = X % c, but leave X alone if c
     * is NULL.
     */
#define REDUCE(X)                                       \
    do {                                                \
        if (c != NULL) {                                \
            if (l_divmod(X, c, NULL, &temp) < 0)        \
                goto Error;                             \
            Py_XDECREF(X);                              \
            X = temp;                                   \
            temp = NULL;                                \
        }                                               \
    } while(0)

    /* Multiply two values, then reduce the result:
       result = X*Y % c.  If c is NULL, skip the mod. */
#define MULT(X, Y, result)                      \
    do {                                        \
        temp = (PyLongObject *)long_mul(X, Y);  \
        if (temp == NULL)                       \
            goto Error;                         \
        Py_XDECREF(result);                     \
        result = temp;                          \
        temp = NULL;                            \
        REDUCE(result);                         \
    } while(0)

    if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
        /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
        /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf    */
        for (i = Py_SIZE(b) - 1; i >= 0; --i) {
            digit bi = b->ob_digit[i];

            for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
                MULT(z, z, z);
                if (bi & j)
                    MULT(z, a, z);
            }
        }
    }
    else {
        /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
        Py_INCREF(z);           /* still holds 1L */
        table[0] = z;
        for (i = 1; i < 32; ++i)
            MULT(table[i-1], a, table[i]);

        for (i = Py_SIZE(b) - 1; i >= 0; --i) {
            const digit bi = b->ob_digit[i];

            for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
                const int index = (bi >> j) & 0x1f;
                for (k = 0; k < 5; ++k)
                    MULT(z, z, z);
                if (index)
                    MULT(z, table[index], z);
            }
        }
    }

    if (negativeOutput && (Py_SIZE(z) != 0)) {
        temp = (PyLongObject *)long_sub(z, c);
        if (temp == NULL)
            goto Error;
        Py_DECREF(z);
        z = temp;
        temp = NULL;
    }
    goto Done;

  Error:
    if (z != NULL) {
        Py_DECREF(z);
        z = NULL;
    }
    /* fall through */
  Done:
    if (Py_SIZE(b) > FIVEARY_CUTOFF) {
        for (i = 0; i < 32; ++i)
            Py_XDECREF(table[i]);
    }
    Py_DECREF(a);
    Py_DECREF(b);
    Py_XDECREF(c);
    Py_XDECREF(temp);
    return (PyObject *)z;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_richcompare ( PyObject self,
PyObject other,
int  op 
) [static]

Definition at line 2534 of file longobject.c.

{
    int result;
    PyObject *v;
    CHECK_BINOP(self, other);
    if (self == other)
        result = 0;
    else
        result = long_compare((PyLongObject*)self, (PyLongObject*)other);
    /* Convert the return value to a Boolean */
    switch (op) {
    case Py_EQ:
        v = TEST_COND(result == 0);
        break;
    case Py_NE:
        v = TEST_COND(result != 0);
        break;
    case Py_LE:
        v = TEST_COND(result <= 0);
        break;
    case Py_GE:
        v = TEST_COND(result >= 0);
        break;
    case Py_LT:
        v = TEST_COND(result == -1);
        break;
    case Py_GT:
        v = TEST_COND(result == 1);
        break;
    default:
        PyErr_BadArgument();
        return NULL;
    }
    Py_INCREF(v);
    return v;
}

Here is the call graph for this function:

static PyObject* long_round ( PyObject self,
PyObject args 
) [static]

Definition at line 4329 of file longobject.c.

{
    PyObject *o_ndigits=NULL, *temp, *result, *ndigits;

    /* To round an integer m to the nearest 10**n (n positive), we make use of
     * the divmod_near operation, defined by:
     *
     *   divmod_near(a, b) = (q, r)
     *
     * where q is the nearest integer to the quotient a / b (the
     * nearest even integer in the case of a tie) and r == a - q * b.
     * Hence q * b = a - r is the nearest multiple of b to a,
     * preferring even multiples in the case of a tie.
     *
     * So the nearest multiple of 10**n to m is:
     *
     *   m - divmod_near(m, 10**n)[1].
     */
    if (!PyArg_ParseTuple(args, "|O", &o_ndigits))
        return NULL;
    if (o_ndigits == NULL)
        return long_long(self);

    ndigits = PyNumber_Index(o_ndigits);
    if (ndigits == NULL)
        return NULL;

    /* if ndigits >= 0 then no rounding is necessary; return self unchanged */
    if (Py_SIZE(ndigits) >= 0) {
        Py_DECREF(ndigits);
        return long_long(self);
    }

    /* result = self - divmod_near(self, 10 ** -ndigits)[1] */
    temp = long_neg((PyLongObject*)ndigits);
    Py_DECREF(ndigits);
    ndigits = temp;
    if (ndigits == NULL)
        return NULL;

    result = PyLong_FromLong(10L);
    if (result == NULL) {
        Py_DECREF(ndigits);
        return NULL;
    }

    temp = long_pow(result, ndigits, Py_None);
    Py_DECREF(ndigits);
    Py_DECREF(result);
    result = temp;
    if (result == NULL)
        return NULL;

    temp = _PyLong_DivmodNear(self, result);
    Py_DECREF(result);
    result = temp;
    if (result == NULL)
        return NULL;

    temp = long_sub((PyLongObject *)self,
                    (PyLongObject *)PyTuple_GET_ITEM(result, 1));
    Py_DECREF(result);
    result = temp;

    return result;
}

Here is the call graph for this function:

static PyObject* long_rshift ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 3818 of file longobject.c.

{
    PyLongObject *z = NULL;
    Py_ssize_t shiftby, newsize, wordshift, loshift, hishift, i, j;
    digit lomask, himask;

    CHECK_BINOP(a, b);

    if (Py_SIZE(a) < 0) {
        /* Right shifting negative numbers is harder */
        PyLongObject *a1, *a2;
        a1 = (PyLongObject *) long_invert(a);
        if (a1 == NULL)
            goto rshift_error;
        a2 = (PyLongObject *) long_rshift(a1, b);
        Py_DECREF(a1);
        if (a2 == NULL)
            goto rshift_error;
        z = (PyLongObject *) long_invert(a2);
        Py_DECREF(a2);
    }
    else {
        shiftby = PyLong_AsSsize_t((PyObject *)b);
        if (shiftby == -1L && PyErr_Occurred())
            goto rshift_error;
        if (shiftby < 0) {
            PyErr_SetString(PyExc_ValueError,
                            "negative shift count");
            goto rshift_error;
        }
        wordshift = shiftby / PyLong_SHIFT;
        newsize = ABS(Py_SIZE(a)) - wordshift;
        if (newsize <= 0)
            return PyLong_FromLong(0);
        loshift = shiftby % PyLong_SHIFT;
        hishift = PyLong_SHIFT - loshift;
        lomask = ((digit)1 << hishift) - 1;
        himask = PyLong_MASK ^ lomask;
        z = _PyLong_New(newsize);
        if (z == NULL)
            goto rshift_error;
        if (Py_SIZE(a) < 0)
            Py_SIZE(z) = -(Py_SIZE(z));
        for (i = 0, j = wordshift; i < newsize; i++, j++) {
            z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
            if (i+1 < newsize)
                z->ob_digit[i] |= (a->ob_digit[j+1] << hishift) & himask;
        }
        z = long_normalize(z);
    }
  rshift_error:
    return (PyObject *) maybe_small_long(z);

}

Here is the call graph for this function:

static PyObject* long_sizeof ( PyLongObject *  v) [static]

Definition at line 4397 of file longobject.c.

{
    Py_ssize_t res;

    res = offsetof(PyLongObject, ob_digit) + ABS(Py_SIZE(v))*sizeof(digit);
    return PyLong_FromSsize_t(res);
}
static PyObject* long_sub ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 2749 of file longobject.c.

{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    if (ABS(Py_SIZE(a)) <= 1 && ABS(Py_SIZE(b)) <= 1) {
        PyObject* r;
        r = PyLong_FromLong(MEDIUM_VALUE(a)-MEDIUM_VALUE(b));
        return r;
    }
    if (Py_SIZE(a) < 0) {
        if (Py_SIZE(b) < 0)
            z = x_sub(a, b);
        else
            z = x_add(a, b);
        if (z != NULL && Py_SIZE(z) != 0)
            Py_SIZE(z) = -(Py_SIZE(z));
    }
    else {
        if (Py_SIZE(b) < 0)
            z = x_add(a, b);
        else
            z = x_sub(a, b);
    }
    return (PyObject *)z;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject * long_subtype_new ( PyTypeObject type,
PyObject args,
PyObject kwds 
) [static]

Definition at line 4177 of file longobject.c.

{
    PyLongObject *tmp, *newobj;
    Py_ssize_t i, n;

    assert(PyType_IsSubtype(type, &PyLong_Type));
    tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
    if (tmp == NULL)
        return NULL;
    assert(PyLong_CheckExact(tmp));
    n = Py_SIZE(tmp);
    if (n < 0)
        n = -n;
    newobj = (PyLongObject *)type->tp_alloc(type, n);
    if (newobj == NULL) {
        Py_DECREF(tmp);
        return NULL;
    }
    assert(PyLong_Check(newobj));
    Py_SIZE(newobj) = Py_SIZE(tmp);
    for (i = 0; i < n; i++)
        newobj->ob_digit[i] = tmp->ob_digit[i];
    Py_DECREF(tmp);
    return (PyObject *)newobj;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_to_bytes ( PyLongObject *  v,
PyObject args,
PyObject kwds 
) [static]

Definition at line 4479 of file longobject.c.

{
    PyObject *byteorder_str;
    PyObject *is_signed_obj = NULL;
    Py_ssize_t length;
    int little_endian;
    int is_signed;
    PyObject *bytes;
    static char *kwlist[] = {"length", "byteorder", "signed", NULL};

    if (!PyArg_ParseTupleAndKeywords(args, kwds, "nU|O:to_bytes", kwlist,
                                     &length, &byteorder_str,
                                     &is_signed_obj))
        return NULL;

    if (args != NULL && Py_SIZE(args) > 2) {
        PyErr_SetString(PyExc_TypeError,
            "'signed' is a keyword-only argument");
        return NULL;
    }

    if (!PyUnicode_CompareWithASCIIString(byteorder_str, "little"))
        little_endian = 1;
    else if (!PyUnicode_CompareWithASCIIString(byteorder_str, "big"))
        little_endian = 0;
    else {
        PyErr_SetString(PyExc_ValueError,
            "byteorder must be either 'little' or 'big'");
        return NULL;
    }

    if (is_signed_obj != NULL) {
        int cmp = PyObject_IsTrue(is_signed_obj);
        if (cmp < 0)
            return NULL;
        is_signed = cmp ? 1 : 0;
    }
    else {
        /* If the signed argument was omitted, use False as the
           default. */
        is_signed = 0;
    }

    if (length < 0) {
        PyErr_SetString(PyExc_ValueError,
                        "length argument must be non-negative");
        return NULL;
    }

    bytes = PyBytes_FromStringAndSize(NULL, length);
    if (bytes == NULL)
        return NULL;

    if (_PyLong_AsByteArray(v, (unsigned char *)PyBytes_AS_STRING(bytes),
                            length, little_endian, is_signed) < 0) {
        Py_DECREF(bytes);
        return NULL;
    }

    return bytes;
}

Here is the call graph for this function:

static PyObject* long_to_decimal_string ( PyObject aa) [static]

Definition at line 1546 of file longobject.c.

{
    PyLongObject *scratch, *a;
    PyObject *str;
    Py_ssize_t size, strlen, size_a, i, j;
    digit *pout, *pin, rem, tenpow;
    Py_UNICODE *p;
    int negative;

    a = (PyLongObject *)aa;
    if (a == NULL || !PyLong_Check(a)) {
        PyErr_BadInternalCall();
        return NULL;
    }
    size_a = ABS(Py_SIZE(a));
    negative = Py_SIZE(a) < 0;

    /* quick and dirty upper bound for the number of digits
       required to express a in base _PyLong_DECIMAL_BASE:

         #digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))

       But log2(a) < size_a * PyLong_SHIFT, and
       log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
                                  > 3 * _PyLong_DECIMAL_SHIFT
    */
    if (size_a > PY_SSIZE_T_MAX / PyLong_SHIFT) {
        PyErr_SetString(PyExc_OverflowError,
                        "long is too large to format");
        return NULL;
    }
    /* the expression size_a * PyLong_SHIFT is now safe from overflow */
    size = 1 + size_a * PyLong_SHIFT / (3 * _PyLong_DECIMAL_SHIFT);
    scratch = _PyLong_New(size);
    if (scratch == NULL)
        return NULL;

    /* convert array of base _PyLong_BASE digits in pin to an array of
       base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,
       Volume 2 (3rd edn), section 4.4, Method 1b). */
    pin = a->ob_digit;
    pout = scratch->ob_digit;
    size = 0;
    for (i = size_a; --i >= 0; ) {
        digit hi = pin[i];
        for (j = 0; j < size; j++) {
            twodigits z = (twodigits)pout[j] << PyLong_SHIFT | hi;
            hi = (digit)(z / _PyLong_DECIMAL_BASE);
            pout[j] = (digit)(z - (twodigits)hi *
                              _PyLong_DECIMAL_BASE);
        }
        while (hi) {
            pout[size++] = hi % _PyLong_DECIMAL_BASE;
            hi /= _PyLong_DECIMAL_BASE;
        }
        /* check for keyboard interrupt */
        SIGCHECK({
                Py_DECREF(scratch);
                return NULL;
            });
    }
    /* pout should have at least one digit, so that the case when a = 0
       works correctly */
    if (size == 0)
        pout[size++] = 0;

    /* calculate exact length of output string, and allocate */
    strlen = negative + 1 + (size - 1) * _PyLong_DECIMAL_SHIFT;
    tenpow = 10;
    rem = pout[size-1];
    while (rem >= tenpow) {
        tenpow *= 10;
        strlen++;
    }
    str = PyUnicode_FromUnicode(NULL, strlen);
    if (str == NULL) {
        Py_DECREF(scratch);
        return NULL;
    }

    /* fill the string right-to-left */
    p = PyUnicode_AS_UNICODE(str) + strlen;
    *p = '\0';
    /* pout[0] through pout[size-2] contribute exactly
       _PyLong_DECIMAL_SHIFT digits each */
    for (i=0; i < size - 1; i++) {
        rem = pout[i];
        for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) {
            *--p = '0' + rem % 10;
            rem /= 10;
        }
    }
    /* pout[size-1]: always produce at least one decimal digit */
    rem = pout[i];
    do {
        *--p = '0' + rem % 10;
        rem /= 10;
    } while (rem != 0);

    /* and sign */
    if (negative)
        *--p = '-';

    /* check we've counted correctly */
    assert(p == PyUnicode_AS_UNICODE(str));
    Py_DECREF(scratch);
    return (PyObject *)str;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyObject* long_true_divide ( PyObject v,
PyObject w 
) [static]

Definition at line 3292 of file longobject.c.

{
    PyLongObject *a, *b, *x;
    Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits;
    digit mask, low;
    int inexact, negate, a_is_small, b_is_small;
    double dx, result;

    CHECK_BINOP(v, w);
    a = (PyLongObject *)v;
    b = (PyLongObject *)w;

    /*
       Method in a nutshell:

         0. reduce to case a, b > 0; filter out obvious underflow/overflow
         1. choose a suitable integer 'shift'
         2. use integer arithmetic to compute x = floor(2**-shift*a/b)
         3. adjust x for correct rounding
         4. convert x to a double dx with the same value
         5. return ldexp(dx, shift).

       In more detail:

       0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b
       returns either 0.0 or -0.0, depending on the sign of b.  For a and
       b both nonzero, ignore signs of a and b, and add the sign back in
       at the end.  Now write a_bits and b_bits for the bit lengths of a
       and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise
       for b).  Then

          2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1).

       So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and
       so overflows.  Similarly, if a_bits - b_bits < DBL_MIN_EXP -
       DBL_MANT_DIG - 1 then a/b underflows to 0.  With these cases out of
       the way, we can assume that

          DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP.

       1. The integer 'shift' is chosen so that x has the right number of
       bits for a double, plus two or three extra bits that will be used
       in the rounding decisions.  Writing a_bits and b_bits for the
       number of significant bits in a and b respectively, a
       straightforward formula for shift is:

          shift = a_bits - b_bits - DBL_MANT_DIG - 2

       This is fine in the usual case, but if a/b is smaller than the
       smallest normal float then it can lead to double rounding on an
       IEEE 754 platform, giving incorrectly rounded results.  So we
       adjust the formula slightly.  The actual formula used is:

           shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2

       2. The quantity x is computed by first shifting a (left -shift bits
       if shift <= 0, right shift bits if shift > 0) and then dividing by
       b.  For both the shift and the division, we keep track of whether
       the result is inexact, in a flag 'inexact'; this information is
       needed at the rounding stage.

       With the choice of shift above, together with our assumption that
       a_bits - b_bits >= DBL_MIN_EXP - DBL_MANT_DIG - 1, it follows
       that x >= 1.

       3. Now x * 2**shift <= a/b < (x+1) * 2**shift.  We want to replace
       this with an exactly representable float of the form

          round(x/2**extra_bits) * 2**(extra_bits+shift).

       For float representability, we need x/2**extra_bits <
       2**DBL_MANT_DIG and extra_bits + shift >= DBL_MIN_EXP -
       DBL_MANT_DIG.  This translates to the condition:

          extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG

       To round, we just modify the bottom digit of x in-place; this can
       end up giving a digit with value > PyLONG_MASK, but that's not a
       problem since digits can hold values up to 2*PyLONG_MASK+1.

       With the original choices for shift above, extra_bits will always
       be 2 or 3.  Then rounding under the round-half-to-even rule, we
       round up iff the most significant of the extra bits is 1, and
       either: (a) the computation of x in step 2 had an inexact result,
       or (b) at least one other of the extra bits is 1, or (c) the least
       significant bit of x (above those to be rounded) is 1.

       4. Conversion to a double is straightforward; all floating-point
       operations involved in the conversion are exact, so there's no
       danger of rounding errors.

       5. Use ldexp(x, shift) to compute x*2**shift, the final result.
       The result will always be exactly representable as a double, except
       in the case that it overflows.  To avoid dependence on the exact
       behaviour of ldexp on overflow, we check for overflow before
       applying ldexp.  The result of ldexp is adjusted for sign before
       returning.
    */

    /* Reduce to case where a and b are both positive. */
    a_size = ABS(Py_SIZE(a));
    b_size = ABS(Py_SIZE(b));
    negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0);
    if (b_size == 0) {
        PyErr_SetString(PyExc_ZeroDivisionError,
                        "division by zero");
        goto error;
    }
    if (a_size == 0)
        goto underflow_or_zero;

    /* Fast path for a and b small (exactly representable in a double).
       Relies on floating-point division being correctly rounded; results
       may be subject to double rounding on x86 machines that operate with
       the x87 FPU set to 64-bit precision. */
    a_is_small = a_size <= MANT_DIG_DIGITS ||
        (a_size == MANT_DIG_DIGITS+1 &&
         a->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
    b_is_small = b_size <= MANT_DIG_DIGITS ||
        (b_size == MANT_DIG_DIGITS+1 &&
         b->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
    if (a_is_small && b_is_small) {
        double da, db;
        da = a->ob_digit[--a_size];
        while (a_size > 0)
            da = da * PyLong_BASE + a->ob_digit[--a_size];
        db = b->ob_digit[--b_size];
        while (b_size > 0)
            db = db * PyLong_BASE + b->ob_digit[--b_size];
        result = da / db;
        goto success;
    }

    /* Catch obvious cases of underflow and overflow */
    diff = a_size - b_size;
    if (diff > PY_SSIZE_T_MAX/PyLong_SHIFT - 1)
        /* Extreme overflow */
        goto overflow;
    else if (diff < 1 - PY_SSIZE_T_MAX/PyLong_SHIFT)
        /* Extreme underflow */
        goto underflow_or_zero;
    /* Next line is now safe from overflowing a Py_ssize_t */
    diff = diff * PyLong_SHIFT + bits_in_digit(a->ob_digit[a_size - 1]) -
        bits_in_digit(b->ob_digit[b_size - 1]);
    /* Now diff = a_bits - b_bits. */
    if (diff > DBL_MAX_EXP)
        goto overflow;
    else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1)
        goto underflow_or_zero;

    /* Choose value for shift; see comments for step 1 above. */
    shift = MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2;

    inexact = 0;

    /* x = abs(a * 2**-shift) */
    if (shift <= 0) {
        Py_ssize_t i, shift_digits = -shift / PyLong_SHIFT;
        digit rem;
        /* x = a << -shift */
        if (a_size >= PY_SSIZE_T_MAX - 1 - shift_digits) {
            /* In practice, it's probably impossible to end up
               here.  Both a and b would have to be enormous,
               using close to SIZE_T_MAX bytes of memory each. */
            PyErr_SetString(PyExc_OverflowError,
                            "intermediate overflow during division");
            goto error;
        }
        x = _PyLong_New(a_size + shift_digits + 1);
        if (x == NULL)
            goto error;
        for (i = 0; i < shift_digits; i++)
            x->ob_digit[i] = 0;
        rem = v_lshift(x->ob_digit + shift_digits, a->ob_digit,
                       a_size, -shift % PyLong_SHIFT);
        x->ob_digit[a_size + shift_digits] = rem;
    }
    else {
        Py_ssize_t shift_digits = shift / PyLong_SHIFT;
        digit rem;
        /* x = a >> shift */
        assert(a_size >= shift_digits);
        x = _PyLong_New(a_size - shift_digits);
        if (x == NULL)
            goto error;
        rem = v_rshift(x->ob_digit, a->ob_digit + shift_digits,
                       a_size - shift_digits, shift % PyLong_SHIFT);
        /* set inexact if any of the bits shifted out is nonzero */
        if (rem)
            inexact = 1;
        while (!inexact && shift_digits > 0)
            if (a->ob_digit[--shift_digits])
                inexact = 1;
    }
    long_normalize(x);
    x_size = Py_SIZE(x);

    /* x //= b. If the remainder is nonzero, set inexact.  We own the only
       reference to x, so it's safe to modify it in-place. */
    if (b_size == 1) {
        digit rem = inplace_divrem1(x->ob_digit, x->ob_digit, x_size,
                              b->ob_digit[0]);
        long_normalize(x);
        if (rem)
            inexact = 1;
    }
    else {
        PyLongObject *div, *rem;
        div = x_divrem(x, b, &rem);
        Py_DECREF(x);
        x = div;
        if (x == NULL)
            goto error;
        if (Py_SIZE(rem))
            inexact = 1;
        Py_DECREF(rem);
    }
    x_size = ABS(Py_SIZE(x));
    assert(x_size > 0); /* result of division is never zero */
    x_bits = (x_size-1)*PyLong_SHIFT+bits_in_digit(x->ob_digit[x_size-1]);

    /* The number of extra bits that have to be rounded away. */
    extra_bits = MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;
    assert(extra_bits == 2 || extra_bits == 3);

    /* Round by directly modifying the low digit of x. */
    mask = (digit)1 << (extra_bits - 1);
    low = x->ob_digit[0] | inexact;
    if (low & mask && low & (3*mask-1))
        low += mask;
    x->ob_digit[0] = low & ~(mask-1U);

    /* Convert x to a double dx; the conversion is exact. */
    dx = x->ob_digit[--x_size];
    while (x_size > 0)
        dx = dx * PyLong_BASE + x->ob_digit[--x_size];
    Py_DECREF(x);

    /* Check whether ldexp result will overflow a double. */
    if (shift + x_bits >= DBL_MAX_EXP &&
        (shift + x_bits > DBL_MAX_EXP || dx == ldexp(1.0, (int)x_bits)))
        goto overflow;
    result = ldexp(dx, (int)shift);

  success:
    return PyFloat_FromDouble(negate ? -result : result);

  underflow_or_zero:
    return PyFloat_FromDouble(negate ? -0.0 : 0.0);

  overflow:
    PyErr_SetString(PyExc_OverflowError,
                    "integer division result too large for a float");
  error:
    return NULL;
}

Here is the call graph for this function:

static PyObject* long_xor ( PyObject a,
PyObject b 
) [static]

Definition at line 4074 of file longobject.c.

{
    PyObject *c;
    CHECK_BINOP(a, b);
    c = long_bitwise((PyLongObject*)a, '^', (PyLongObject*)b);
    return c;
}

Here is the call graph for this function:

static PyLongObject* maybe_small_long ( PyLongObject *  v) [static]

Definition at line 55 of file longobject.c.

{
    if (v && ABS(Py_SIZE(v)) <= 1) {
        sdigit ival = MEDIUM_VALUE(v);
        if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
            Py_DECREF(v);
            return (PyLongObject *)get_small_int(ival);
        }
    }
    return v;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PyDoc_STRVAR ( long_bit_length_doc  ,
"int.bit_length() -> int\n\\n\Number of bits necessary to represent self in binary.\n\>>  ,
bin(37)\n\'0b100101'\n>>  ,
(37).bit_length()\n\6"   
)
PyDoc_STRVAR ( long_to_bytes_doc  ,
"int.to_bytes(length, byteorder, *, signed=False) -> bytes\n\\n\Return an array of bytes representing an integer.\n\\n\The integer is represented using length bytes. An OverflowError is\n\raised if the integer is not representable with the given number of\n\bytes.\n\\n\The byteorder argument determines the byte order used to represent the\n\integer. If byteorder is 'big'  ,
the most significant byte is at the\n\beginning of the byte array.If byteorder is 'little'  ,
the most\n\significant byte is at the end of the byte array.To request the native\n\byte order of the host  system,
use`sys.byteorder'as the byte order value.\n\\n\The signed keyword-only argument determines whether two's complement is\n\used to represent the integer.If signed is False and a negative integer\n\is  given,
an OverflowError is raised."   
)
PyDoc_STRVAR ( long_from_bytes_doc  ,
"int.from_bytes(bytes, byteorder, *, signed=False) -> int\n\\n\Return the integer represented by the given array of bytes.\n\\n\The bytes argument must either support the buffer protocol or be an\n\iterable object producing bytes. Bytes and bytearray are examples of\n\built-in objects that support the buffer protocol.\n\\n\The byteorder argument determines the byte order used to represent the\n\integer. If byteorder is 'big'  ,
the most significant byte is at the\n\beginning of the byte array.If byteorder is 'little'  ,
the most\n\significant byte is at the end of the byte array.To request the native\n\byte order of the host  system,
use`sys.byteorder'as the byte order value.\n\\n\The signed keyword-only argument indicates whether two's complement is\n\used to represent the integer."   
)
PyDoc_STRVAR ( long_doc  ,
"int(x[, base]) -> integer\n\\n\Convert a string or number to an  integer,
if possible.A floating\n\point argument will be truncated towards zero(this does not include a\n\string representation of a floating point number!) When converting a\n\  string,
use the optional base.It is an error to supply a base when\n\converting a non-string."   
)
PyDoc_STRVAR ( int_info__doc__  ,
"sys.int_info\n\\n\A struct sequence that holds information about Python's\n\internal representation of integers. The attributes are read only."   
)
double PyLong_AsDouble ( PyObject v)

Definition at line 2481 of file longobject.c.

{
    Py_ssize_t exponent;
    double x;

    if (v == NULL || !PyLong_Check(v)) {
        PyErr_BadInternalCall();
        return -1.0;
    }
    x = _PyLong_Frexp((PyLongObject *)v, &exponent);
    if ((x == -1.0 && PyErr_Occurred()) || exponent > DBL_MAX_EXP) {
        PyErr_SetString(PyExc_OverflowError,
                        "long int too large to convert to float");
        return -1.0;
    }
    return ldexp(x, (int)exponent);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 416 of file longobject.c.

{
    int overflow;
    long result = PyLong_AsLongAndOverflow(obj, &overflow);
    if (overflow) {
        /* XXX: could be cute and give a different
           message for overflow == -1 */
        PyErr_SetString(PyExc_OverflowError,
                        "Python int too large to convert to C long");
    }
    return result;
}

Here is the call graph for this function:

long PyLong_AsLongAndOverflow ( PyObject vv,
int overflow 
)

Definition at line 329 of file longobject.c.

{
    /* This version by Tim Peters */
    register PyLongObject *v;
    unsigned long x, prev;
    long res;
    Py_ssize_t i;
    int sign;
    int do_decref = 0; /* if nb_int was called */

    *overflow = 0;
    if (vv == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }

    if (!PyLong_Check(vv)) {
        PyNumberMethods *nb;
        nb = vv->ob_type->tp_as_number;
        if (nb == NULL || nb->nb_int == NULL) {
            PyErr_SetString(PyExc_TypeError,
                            "an integer is required");
            return -1;
        }
        vv = (*nb->nb_int) (vv);
        if (vv == NULL)
            return -1;
        do_decref = 1;
        if (!PyLong_Check(vv)) {
            Py_DECREF(vv);
            PyErr_SetString(PyExc_TypeError,
                            "nb_int should return int object");
            return -1;
        }
    }

    res = -1;
    v = (PyLongObject *)vv;
    i = Py_SIZE(v);

    switch (i) {
    case -1:
        res = -(sdigit)v->ob_digit[0];
        break;
    case 0:
        res = 0;
        break;
    case 1:
        res = v->ob_digit[0];
        break;
    default:
        sign = 1;
        x = 0;
        if (i < 0) {
            sign = -1;
            i = -(i);
        }
        while (--i >= 0) {
            prev = x;
            x = (x << PyLong_SHIFT) | v->ob_digit[i];
            if ((x >> PyLong_SHIFT) != prev) {
                *overflow = sign;
                goto exit;
            }
        }
        /* Haven't lost any bits, but casting to long requires extra
         * care (see comment above).
         */
        if (x <= (unsigned long)LONG_MAX) {
            res = (long)x * sign;
        }
        else if (sign < 0 && x == PY_ABS_LONG_MIN) {
            res = LONG_MIN;
        }
        else {
            *overflow = sign;
            /* res is already set to -1 */
        }
    }
  exit:
    if (do_decref) {
        Py_DECREF(vv);
    }
    return res;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 532 of file longobject.c.

{
    register PyLongObject *v;
    size_t x, prev;
    Py_ssize_t i;

    if (vv == NULL) {
        PyErr_BadInternalCall();
        return (size_t) -1;
    }
    if (!PyLong_Check(vv)) {
        PyErr_SetString(PyExc_TypeError, "an integer is required");
        return (size_t)-1;
    }

    v = (PyLongObject *)vv;
    i = Py_SIZE(v);
    x = 0;
    if (i < 0) {
        PyErr_SetString(PyExc_OverflowError,
                   "can't convert negative value to size_t");
        return (size_t) -1;
    }
    switch (i) {
    case 0: return 0;
    case 1: return v->ob_digit[0];
    }
    while (--i >= 0) {
        prev = x;
        x = (x << PyLong_SHIFT) | v->ob_digit[i];
        if ((x >> PyLong_SHIFT) != prev) {
            PyErr_SetString(PyExc_OverflowError,
                "Python int too large to convert to C size_t");
            return (unsigned long) -1;
        }
    }
    return x;
}

Here is the call graph for this function:

Definition at line 433 of file longobject.c.

                               {
    register PyLongObject *v;
    size_t x, prev;
    Py_ssize_t i;
    int sign;

    if (vv == NULL) {
        PyErr_BadInternalCall();
        return -1;
    }
    if (!PyLong_Check(vv)) {
        PyErr_SetString(PyExc_TypeError, "an integer is required");
        return -1;
    }

    v = (PyLongObject *)vv;
    i = Py_SIZE(v);
    switch (i) {
    case -1: return -(sdigit)v->ob_digit[0];
    case 0: return 0;
    case 1: return v->ob_digit[0];
    }
    sign = 1;
    x = 0;
    if (i < 0) {
        sign = -1;
        i = -(i);
    }
    while (--i >= 0) {
        prev = x;
        x = (x << PyLong_SHIFT) | v->ob_digit[i];
        if ((x >> PyLong_SHIFT) != prev)
            goto overflow;
    }
    /* Haven't lost any bits, but casting to a signed type requires
     * extra care (see comment above).
     */
    if (x <= (size_t)PY_SSIZE_T_MAX) {
        return (Py_ssize_t)x * sign;
    }
    else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
        return PY_SSIZE_T_MIN;
    }
    /* else overflow */

  overflow:
    PyErr_SetString(PyExc_OverflowError,
                    "Python int too large to convert to C ssize_t");
    return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned long PyLong_AsUnsignedLong ( PyObject vv)

Definition at line 488 of file longobject.c.

{
    register PyLongObject *v;
    unsigned long x, prev;
    Py_ssize_t i;

    if (vv == NULL) {
        PyErr_BadInternalCall();
        return (unsigned long)-1;
    }
    if (!PyLong_Check(vv)) {
        PyErr_SetString(PyExc_TypeError, "an integer is required");
        return (unsigned long)-1;
    }

    v = (PyLongObject *)vv;
    i = Py_SIZE(v);
    x = 0;
    if (i < 0) {
        PyErr_SetString(PyExc_OverflowError,
                        "can't convert negative value to unsigned int");
        return (unsigned long) -1;
    }
    switch (i) {
    case 0: return 0;
    case 1: return v->ob_digit[0];
    }
    while (--i >= 0) {
        prev = x;
        x = (x << PyLong_SHIFT) | v->ob_digit[i];
        if ((x >> PyLong_SHIFT) != prev) {
            PyErr_SetString(PyExc_OverflowError,
                            "python int too large to convert "
                            "to C unsigned long");
            return (unsigned long) -1;
        }
    }
    return x;
}

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned long PyLong_AsUnsignedLongMask ( register PyObject op)

Definition at line 605 of file longobject.c.

{
    PyNumberMethods *nb;
    PyLongObject *lo;
    unsigned long val;

    if (op && PyLong_Check(op))
        return _PyLong_AsUnsignedLongMask(op);

    if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
        nb->nb_int == NULL) {
        PyErr_SetString(PyExc_TypeError, "an integer is required");
        return (unsigned long)-1;
    }

    lo = (PyLongObject*) (*nb->nb_int) (op);
    if (lo == NULL)
        return (unsigned long)-1;
    if (PyLong_Check(lo)) {
        val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
        Py_DECREF(lo);
        if (PyErr_Occurred())
            return (unsigned long)-1;
        return val;
    }
    else
    {
        Py_DECREF(lo);
        PyErr_SetString(PyExc_TypeError,
                        "nb_int should return int object");
        return (unsigned long)-1;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 947 of file longobject.c.

{
    /* This function will allow int or long objects. If vv is neither,
       then the PyLong_AsLong*() functions will raise the exception:
       PyExc_SystemError, "bad argument to internal function"
    */
#if SIZEOF_VOID_P <= SIZEOF_LONG
    long x;

    if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
        x = PyLong_AsLong(vv);
    else
        x = PyLong_AsUnsignedLong(vv);
#else

#ifndef HAVE_LONG_LONG
#   error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
#endif
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
#   error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
#endif
    PY_LONG_LONG x;

    if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
        x = PyLong_AsLongLong(vv);
    else
        x = PyLong_AsUnsignedLongLong(vv);

#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */

    if (x == -1 && PyErr_Occurred())
        return NULL;
    return (void *)x;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 4876 of file longobject.c.

{
    /* Integers are currently statically allocated. Py_DECREF is not
       needed, but Python must forget about the reference or multiple
       reinitializations will fail. */
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
    int i;
    PyLongObject *v = small_ints;
    for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) {
        _Py_DEC_REFTOTAL;
        _Py_ForgetReference((PyObject*)v);
    }
#endif
}

Here is the caller graph for this function:

PyObject* PyLong_FromDouble ( double  dval)

Definition at line 274 of file longobject.c.

{
    PyLongObject *v;
    double frac;
    int i, ndig, expo, neg;
    neg = 0;
    if (Py_IS_INFINITY(dval)) {
        PyErr_SetString(PyExc_OverflowError,
                        "cannot convert float infinity to integer");
        return NULL;
    }
    if (Py_IS_NAN(dval)) {
        PyErr_SetString(PyExc_ValueError,
                        "cannot convert float NaN to integer");
        return NULL;
    }
    if (dval < 0.0) {
        neg = 1;
        dval = -dval;
    }
    frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
    if (expo <= 0)
        return PyLong_FromLong(0L);
    ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
    v = _PyLong_New(ndig);
    if (v == NULL)
        return NULL;
    frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
    for (i = ndig; --i >= 0; ) {
        digit bits = (digit)frac;
        v->ob_digit[i] = bits;
        frac = frac - (double)bits;
        frac = ldexp(frac, PyLong_SHIFT);
    }
    if (neg)
        Py_SIZE(v) = -(Py_SIZE(v));
    return (PyObject *)v;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 176 of file longobject.c.

{
    PyLongObject *v;
    unsigned long abs_ival;
    unsigned long t;  /* unsigned so >> doesn't propagate sign bit */
    int ndigits = 0;
    int sign = 1;

    CHECK_SMALL_INT(ival);

    if (ival < 0) {
        /* negate: can't write this as abs_ival = -ival since that
           invokes undefined behaviour when ival is LONG_MIN */
        abs_ival = 0U-(unsigned long)ival;
        sign = -1;
    }
    else {
        abs_ival = (unsigned long)ival;
    }

    /* Fast path for single-digit ints */
    if (!(abs_ival >> PyLong_SHIFT)) {
        v = _PyLong_New(1);
        if (v) {
            Py_SIZE(v) = sign;
            v->ob_digit[0] = Py_SAFE_DOWNCAST(
                abs_ival, unsigned long, digit);
        }
        return (PyObject*)v;
    }

#if PyLong_SHIFT==15
    /* 2 digits */
    if (!(abs_ival >> 2*PyLong_SHIFT)) {
        v = _PyLong_New(2);
        if (v) {
            Py_SIZE(v) = 2*sign;
            v->ob_digit[0] = Py_SAFE_DOWNCAST(
                abs_ival & PyLong_MASK, unsigned long, digit);
            v->ob_digit[1] = Py_SAFE_DOWNCAST(
                  abs_ival >> PyLong_SHIFT, unsigned long, digit);
        }
        return (PyObject*)v;
    }
#endif

    /* Larger numbers: loop to determine number of digits */
    t = abs_ival;
    while (t) {
        ++ndigits;
        t >>= PyLong_SHIFT;
    }
    v = _PyLong_New(ndigits);
    if (v != NULL) {
        digit *p = v->ob_digit;
        Py_SIZE(v) = ndigits*sign;
        t = abs_ival;
        while (t) {
            *p++ = Py_SAFE_DOWNCAST(
                t & PyLong_MASK, unsigned long, digit);
            t >>= PyLong_SHIFT;
        }
    }
    return (PyObject *)v;
}

Here is the call graph for this function:

PyObject* PyLong_FromString ( char *  str,
char **  pend,
int  base 
)

Definition at line 1853 of file longobject.c.

{
    int sign = 1, error_if_nonzero = 0;
    char *start, *orig_str = str;
    PyLongObject *z = NULL;
    PyObject *strobj;
    Py_ssize_t slen;

    if ((base != 0 && base < 2) || base > 36) {
        PyErr_SetString(PyExc_ValueError,
                        "int() arg 2 must be >= 2 and <= 36");
        return NULL;
    }
    while (*str != '\0' && isspace(Py_CHARMASK(*str)))
        str++;
    if (*str == '+')
        ++str;
    else if (*str == '-') {
        ++str;
        sign = -1;
    }
    if (base == 0) {
        if (str[0] != '0')
            base = 10;
        else if (str[1] == 'x' || str[1] == 'X')
            base = 16;
        else if (str[1] == 'o' || str[1] == 'O')
            base = 8;
        else if (str[1] == 'b' || str[1] == 'B')
            base = 2;
        else {
            /* "old" (C-style) octal literal, now invalid.
               it might still be zero though */
            error_if_nonzero = 1;
            base = 10;
        }
    }
    if (str[0] == '0' &&
        ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
         (base == 8  && (str[1] == 'o' || str[1] == 'O')) ||
         (base == 2  && (str[1] == 'b' || str[1] == 'B'))))
        str += 2;

    start = str;
    if ((base & (base - 1)) == 0)
        z = long_from_binary_base(&str, base);
    else {
/***
Binary bases can be converted in time linear in the number of digits, because
Python's representation base is binary.  Other bases (including decimal!) use
the simple quadratic-time algorithm below, complicated by some speed tricks.

First some math:  the largest integer that can be expressed in N base-B digits
is B**N-1.  Consequently, if we have an N-digit input in base B, the worst-
case number of Python digits needed to hold it is the smallest integer n s.t.

    BASE**n-1 >= B**N-1  [or, adding 1 to both sides]
    BASE**n >= B**N      [taking logs to base BASE]
    n >= log(B**N)/log(BASE) = N * log(B)/log(BASE)

The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
this quickly.  A Python long with that much space is reserved near the start,
and the result is computed into it.

The input string is actually treated as being in base base**i (i.e., i digits
are processed at a time), where two more static arrays hold:

    convwidth_base[base] = the largest integer i such that base**i <= BASE
    convmultmax_base[base] = base ** convwidth_base[base]

The first of these is the largest i such that i consecutive input digits
must fit in a single Python digit.  The second is effectively the input
base we're really using.

Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
convmultmax_base[base], the result is "simply"

   (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1

where B = convmultmax_base[base].

Error analysis:  as above, the number of Python digits `n` needed is worst-
case

    n >= N * log(B)/log(BASE)

where `N` is the number of input digits in base `B`.  This is computed via

    size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;

below.  Two numeric concerns are how much space this can waste, and whether
the computed result can be too small.  To be concrete, assume BASE = 2**15,
which is the default (and it's unlikely anyone changes that).

Waste isn't a problem:  provided the first input digit isn't 0, the difference
between the worst-case input with N digits and the smallest input with N
digits is about a factor of B, but B is small compared to BASE so at most
one allocated Python digit can remain unused on that count.  If
N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
and adding 1 returns a result 1 larger than necessary.  However, that can't
happen:  whenever B is a power of 2, long_from_binary_base() is called
instead, and it's impossible for B**i to be an integer power of 2**15 when
B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
an exact integer when B is not a power of 2, since B**i has a prime factor
other than 2 in that case, but (2**15)**j's only prime factor is 2).

The computed result can be too small if the true value of N*log(B)/log(BASE)
is a little bit larger than an exact integer, but due to roundoff errors (in
computing log(B), log(BASE), their quotient, and/or multiplying that by N)
yields a numeric result a little less than that integer.  Unfortunately, "how
close can a transcendental function get to an integer over some range?"
questions are generally theoretically intractable.  Computer analysis via
continued fractions is practical:  expand log(B)/log(BASE) via continued
fractions, giving a sequence i/j of "the best" rational approximations.  Then
j*log(B)/log(BASE) is approximately equal to (the integer) i.  This shows that
we can get very close to being in trouble, but very rarely.  For example,
76573 is a denominator in one of the continued-fraction approximations to
log(10)/log(2**15), and indeed:

    >>> log(10)/log(2**15)*76573
    16958.000000654003

is very close to an integer.  If we were working with IEEE single-precision,
rounding errors could kill us.  Finding worst cases in IEEE double-precision
requires better-than-double-precision log() functions, and Tim didn't bother.
Instead the code checks to see whether the allocated space is enough as each
new Python digit is added, and copies the whole thing to a larger long if not.
This should happen extremely rarely, and in fact I don't have a test case
that triggers it(!).  Instead the code was tested by artificially allocating
just 1 digit at the start, so that the copying code was exercised for every
digit beyond the first.
***/
        register twodigits c;           /* current input character */
        Py_ssize_t size_z;
        int i;
        int convwidth;
        twodigits convmultmax, convmult;
        digit *pz, *pzstop;
        char* scan;

        static double log_base_BASE[37] = {0.0e0,};
        static int convwidth_base[37] = {0,};
        static twodigits convmultmax_base[37] = {0,};

        if (log_base_BASE[base] == 0.0) {
            twodigits convmax = base;
            int i = 1;

            log_base_BASE[base] = (log((double)base) /
                                   log((double)PyLong_BASE));
            for (;;) {
                twodigits next = convmax * base;
                if (next > PyLong_BASE)
                    break;
                convmax = next;
                ++i;
            }
            convmultmax_base[base] = convmax;
            assert(i > 0);
            convwidth_base[base] = i;
        }

        /* Find length of the string of numeric characters. */
        scan = str;
        while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
            ++scan;

        /* Create a long object that can contain the largest possible
         * integer with this base and length.  Note that there's no
         * need to initialize z->ob_digit -- no slot is read up before
         * being stored into.
         */
        size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
        /* Uncomment next line to test exceedingly rare copy code */
        /* size_z = 1; */
        assert(size_z > 0);
        z = _PyLong_New(size_z);
        if (z == NULL)
            return NULL;
        Py_SIZE(z) = 0;

        /* `convwidth` consecutive input digits are treated as a single
         * digit in base `convmultmax`.
         */
        convwidth = convwidth_base[base];
        convmultmax = convmultmax_base[base];

        /* Work ;-) */
        while (str < scan) {
            /* grab up to convwidth digits from the input string */
            c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
            for (i = 1; i < convwidth && str != scan; ++i, ++str) {
                c = (twodigits)(c *  base +
                                (int)_PyLong_DigitValue[Py_CHARMASK(*str)]);
                assert(c < PyLong_BASE);
            }

            convmult = convmultmax;
            /* Calculate the shift only if we couldn't get
             * convwidth digits.
             */
            if (i != convwidth) {
                convmult = base;
                for ( ; i > 1; --i)
                    convmult *= base;
            }

            /* Multiply z by convmult, and add c. */
            pz = z->ob_digit;
            pzstop = pz + Py_SIZE(z);
            for (; pz < pzstop; ++pz) {
                c += (twodigits)*pz * convmult;
                *pz = (digit)(c & PyLong_MASK);
                c >>= PyLong_SHIFT;
            }
            /* carry off the current end? */
            if (c) {
                assert(c < PyLong_BASE);
                if (Py_SIZE(z) < size_z) {
                    *pz = (digit)c;
                    ++Py_SIZE(z);
                }
                else {
                    PyLongObject *tmp;
                    /* Extremely rare.  Get more space. */
                    assert(Py_SIZE(z) == size_z);
                    tmp = _PyLong_New(size_z + 1);
                    if (tmp == NULL) {
                        Py_DECREF(z);
                        return NULL;
                    }
                    memcpy(tmp->ob_digit,
                           z->ob_digit,
                           sizeof(digit) * size_z);
                    Py_DECREF(z);
                    z = tmp;
                    z->ob_digit[size_z] = (digit)c;
                    ++size_z;
                }
            }
        }
    }
    if (z == NULL)
        return NULL;
    if (error_if_nonzero) {
        /* reset the base to 0, else the exception message
           doesn't make too much sense */
        base = 0;
        if (Py_SIZE(z) != 0)
            goto onError;
        /* there might still be other problems, therefore base
           remains zero here for the same reason */
    }
    if (str == start)
        goto onError;
    if (sign < 0)
        Py_SIZE(z) = -(Py_SIZE(z));
    while (*str && isspace(Py_CHARMASK(*str)))
        str++;
    if (*str != '\0')
        goto onError;
    if (pend)
        *pend = str;
    long_normalize(z);
    return (PyObject *) maybe_small_long(z);

  onError:
    Py_XDECREF(z);
    slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
    strobj = PyUnicode_FromStringAndSize(orig_str, slen);
    if (strobj == NULL)
        return NULL;
    PyErr_Format(PyExc_ValueError,
                 "invalid literal for int() with base %d: %R",
                 base, strobj);
    Py_DECREF(strobj);
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PyObject* PyLong_FromUnicode ( Py_UNICODE u,
Py_ssize_t  length,
int  base 
)

Definition at line 2133 of file longobject.c.

{
    PyObject *result;
    PyObject *asciidig;
    char *buffer, *end;
    Py_ssize_t i, buflen;
    Py_UNICODE *ptr;

    asciidig = PyUnicode_TransformDecimalToASCII(u, length);
    if (asciidig == NULL)
        return NULL;
    /* Replace non-ASCII whitespace with ' ' */
    ptr = PyUnicode_AS_UNICODE(asciidig);
    for (i = 0; i < length; i++) {
        Py_UNICODE ch = ptr[i];
        if (ch > 127 && Py_UNICODE_ISSPACE(ch))
            ptr[i] = ' ';
    }
    buffer = _PyUnicode_AsStringAndSize(asciidig, &buflen);
    if (buffer == NULL) {
        Py_DECREF(asciidig);
        return NULL;
    }
    result = PyLong_FromString(buffer, &end, base);
    if (result != NULL && end != buffer + buflen) {
        PyErr_SetString(PyExc_ValueError,
                        "null byte in argument for int()");
        Py_DECREF(result);
        result = NULL;
    }
    Py_DECREF(asciidig);
    return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PyObject* PyLong_FromUnsignedLong ( unsigned long  ival)

Definition at line 245 of file longobject.c.

{
    PyLongObject *v;
    unsigned long t;
    int ndigits = 0;

    if (ival < PyLong_BASE)
        return PyLong_FromLong(ival);
    /* Count the number of Python digits. */
    t = (unsigned long)ival;
    while (t) {
        ++ndigits;
        t >>= PyLong_SHIFT;
    }
    v = _PyLong_New(ndigits);
    if (v != NULL) {
        digit *p = v->ob_digit;
        Py_SIZE(v) = ndigits;
        while (ival) {
            *p++ = (digit)(ival & PyLong_MASK);
            ival >>= PyLong_SHIFT;
        }
    }
    return (PyObject *)v;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 929 of file longobject.c.

{
#ifndef HAVE_LONG_LONG
#   error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
#endif
#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
#   error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
#endif
    /* special-case null pointer */
    if (!p)
        return PyLong_FromLong(0);
    return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p);

}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 4818 of file longobject.c.

{
    PyObject* int_info;
    int field = 0;
    int_info = PyStructSequence_New(&Int_InfoType);
    if (int_info == NULL)
        return NULL;
    PyStructSequence_SET_ITEM(int_info, field++,
                              PyLong_FromLong(PyLong_SHIFT));
    PyStructSequence_SET_ITEM(int_info, field++,
                              PyLong_FromLong(sizeof(digit)));
    if (PyErr_Occurred()) {
        Py_CLEAR(int_info);
        return NULL;
    }
    return int_info;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void v_complement ( digit *  z,
digit *  a,
Py_ssize_t  m 
) [static]

Definition at line 3927 of file longobject.c.

{
    Py_ssize_t i;
    digit carry = 1;
    for (i = 0; i < m; ++i) {
        carry += a[i] ^ PyLong_MASK;
        z[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    assert(carry == 0);
}

Here is the caller graph for this function:

static digit v_iadd ( digit *  x,
Py_ssize_t  m,
digit *  y,
Py_ssize_t  n 
) [static]

Definition at line 1416 of file longobject.c.

{
    Py_ssize_t i;
    digit carry = 0;

    assert(m >= n);
    for (i = 0; i < n; ++i) {
        carry += x[i] + y[i];
        x[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
        assert((carry & 1) == carry);
    }
    for (; carry && i < m; ++i) {
        carry += x[i];
        x[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
        assert((carry & 1) == carry);
    }
    return carry;
}

Here is the caller graph for this function:

static digit v_isub ( digit *  x,
Py_ssize_t  m,
digit *  y,
Py_ssize_t  n 
) [static]

Definition at line 1442 of file longobject.c.

{
    Py_ssize_t i;
    digit borrow = 0;

    assert(m >= n);
    for (i = 0; i < n; ++i) {
        borrow = x[i] - y[i] - borrow;
        x[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1;            /* keep only 1 sign bit */
    }
    for (; borrow && i < m; ++i) {
        borrow = x[i] - borrow;
        x[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1;
    }
    return borrow;
}

Here is the caller graph for this function:

static digit v_lshift ( digit *  z,
digit *  a,
Py_ssize_t  m,
int  d 
) [static]

Definition at line 1467 of file longobject.c.

{
    Py_ssize_t i;
    digit carry = 0;

    assert(0 <= d && d < PyLong_SHIFT);
    for (i=0; i < m; i++) {
        twodigits acc = (twodigits)a[i] << d | carry;
        z[i] = (digit)acc & PyLong_MASK;
        carry = (digit)(acc >> PyLong_SHIFT);
    }
    return carry;
}

Here is the caller graph for this function:

static digit v_rshift ( digit *  z,
digit *  a,
Py_ssize_t  m,
int  d 
) [static]

Definition at line 1485 of file longobject.c.

{
    Py_ssize_t i;
    digit carry = 0;
    digit mask = ((digit)1 << d) - 1U;

    assert(0 <= d && d < PyLong_SHIFT);
    for (i=m; i-- > 0;) {
        twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i];
        carry = (digit)acc & mask;
        z[i] = (digit)(acc >> d);
    }
    return carry;
}

Here is the caller graph for this function:

static PyLongObject* x_add ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 2632 of file longobject.c.

{
    Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
    PyLongObject *z;
    Py_ssize_t i;
    digit carry = 0;

    /* Ensure a is the larger of the two: */
    if (size_a < size_b) {
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    z = _PyLong_New(size_a+1);
    if (z == NULL)
        return NULL;
    for (i = 0; i < size_b; ++i) {
        carry += a->ob_digit[i] + b->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    for (; i < size_a; ++i) {
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->ob_digit[i] = carry;
    return long_normalize(z);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyLongObject * x_divrem ( PyLongObject *  v1,
PyLongObject *  w1,
PyLongObject **  prem 
) [static]

Definition at line 2229 of file longobject.c.

{
    PyLongObject *v, *w, *a;
    Py_ssize_t i, k, size_v, size_w;
    int d;
    digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;
    twodigits vv;
    sdigit zhi;
    stwodigits z;

    /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
       edn.), section 4.3.1, Algorithm D], except that we don't explicitly
       handle the special case when the initial estimate q for a quotient
       digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
       that won't overflow a digit. */

    /* allocate space; w will also be used to hold the final remainder */
    size_v = ABS(Py_SIZE(v1));
    size_w = ABS(Py_SIZE(w1));
    assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
    v = _PyLong_New(size_v+1);
    if (v == NULL) {
        *prem = NULL;
        return NULL;
    }
    w = _PyLong_New(size_w);
    if (w == NULL) {
        Py_DECREF(v);
        *prem = NULL;
        return NULL;
    }

    /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
       shift v1 left by the same amount.  Results go into w and v. */
    d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);
    carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
    assert(carry == 0);
    carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
    if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {
        v->ob_digit[size_v] = carry;
        size_v++;
    }

    /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
       at most (and usually exactly) k = size_v - size_w digits. */
    k = size_v - size_w;
    assert(k >= 0);
    a = _PyLong_New(k);
    if (a == NULL) {
        Py_DECREF(w);
        Py_DECREF(v);
        *prem = NULL;
        return NULL;
    }
    v0 = v->ob_digit;
    w0 = w->ob_digit;
    wm1 = w0[size_w-1];
    wm2 = w0[size_w-2];
    for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {
        /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
           single-digit quotient q, remainder in vk[0:size_w]. */

        SIGCHECK({
                Py_DECREF(a);
                Py_DECREF(w);
                Py_DECREF(v);
                *prem = NULL;
                return NULL;
            });

        /* estimate quotient digit q; may overestimate by 1 (rare) */
        vtop = vk[size_w];
        assert(vtop <= wm1);
        vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1];
        q = (digit)(vv / wm1);
        r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */
        while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)
                                     | vk[size_w-2])) {
            --q;
            r += wm1;
            if (r >= PyLong_BASE)
                break;
        }
        assert(q <= PyLong_BASE);

        /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
        zhi = 0;
        for (i = 0; i < size_w; ++i) {
            /* invariants: -PyLong_BASE <= -q <= zhi <= 0;
               -PyLong_BASE * q <= z < PyLong_BASE */
            z = (sdigit)vk[i] + zhi -
                (stwodigits)q * (stwodigits)w0[i];
            vk[i] = (digit)z & PyLong_MASK;
            zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
                                                    z, PyLong_SHIFT);
        }

        /* add w back if q was too large (this branch taken rarely) */
        assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0);
        if ((sdigit)vtop + zhi < 0) {
            carry = 0;
            for (i = 0; i < size_w; ++i) {
                carry += vk[i] + w0[i];
                vk[i] = carry & PyLong_MASK;
                carry >>= PyLong_SHIFT;
            }
            --q;
        }

        /* store quotient digit */
        assert(q < PyLong_BASE);
        *--ak = q;
    }

    /* unshift remainder; we reuse w to store the result */
    carry = v_rshift(w0, v0, size_w, d);
    assert(carry==0);
    Py_DECREF(v);

    *prem = long_normalize(w);
    return long_normalize(a);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyLongObject* x_mul ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 2781 of file longobject.c.

{
    PyLongObject *z;
    Py_ssize_t size_a = ABS(Py_SIZE(a));
    Py_ssize_t size_b = ABS(Py_SIZE(b));
    Py_ssize_t i;

    z = _PyLong_New(size_a + size_b);
    if (z == NULL)
        return NULL;

    memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
    if (a == b) {
        /* Efficient squaring per HAC, Algorithm 14.16:
         * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
         * Gives slightly less than a 2x speedup when a == b,
         * via exploiting that each entry in the multiplication
         * pyramid appears twice (except for the size_a squares).
         */
        for (i = 0; i < size_a; ++i) {
            twodigits carry;
            twodigits f = a->ob_digit[i];
            digit *pz = z->ob_digit + (i << 1);
            digit *pa = a->ob_digit + i + 1;
            digit *paend = a->ob_digit + size_a;

            SIGCHECK({
                    Py_DECREF(z);
                    return NULL;
                });

            carry = *pz + f * f;
            *pz++ = (digit)(carry & PyLong_MASK);
            carry >>= PyLong_SHIFT;
            assert(carry <= PyLong_MASK);

            /* Now f is added in twice in each column of the
             * pyramid it appears.  Same as adding f<<1 once.
             */
            f <<= 1;
            while (pa < paend) {
                carry += *pz + *pa++ * f;
                *pz++ = (digit)(carry & PyLong_MASK);
                carry >>= PyLong_SHIFT;
                assert(carry <= (PyLong_MASK << 1));
            }
            if (carry) {
                carry += *pz;
                *pz++ = (digit)(carry & PyLong_MASK);
                carry >>= PyLong_SHIFT;
            }
            if (carry)
                *pz += (digit)(carry & PyLong_MASK);
            assert((carry >> PyLong_SHIFT) == 0);
        }
    }
    else {      /* a is not the same as b -- gradeschool long mult */
        for (i = 0; i < size_a; ++i) {
            twodigits carry = 0;
            twodigits f = a->ob_digit[i];
            digit *pz = z->ob_digit + i;
            digit *pb = b->ob_digit;
            digit *pbend = b->ob_digit + size_b;

            SIGCHECK({
                    Py_DECREF(z);
                    return NULL;
                });

            while (pb < pbend) {
                carry += *pz + *pb++ * f;
                *pz++ = (digit)(carry & PyLong_MASK);
                carry >>= PyLong_SHIFT;
                assert(carry <= PyLong_MASK);
            }
            if (carry)
                *pz += (digit)(carry & PyLong_MASK);
            assert((carry >> PyLong_SHIFT) == 0);
        }
    }
    return long_normalize(z);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static PyLongObject* x_sub ( PyLongObject *  a,
PyLongObject *  b 
) [static]

Definition at line 2666 of file longobject.c.

{
    Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
    PyLongObject *z;
    Py_ssize_t i;
    int sign = 1;
    digit borrow = 0;

    /* Ensure a is the larger of the two: */
    if (size_a < size_b) {
        sign = -1;
        { PyLongObject *temp = a; a = b; b = temp; }
        { Py_ssize_t size_temp = size_a;
            size_a = size_b;
            size_b = size_temp; }
    }
    else if (size_a == size_b) {
        /* Find highest digit where a and b differ: */
        i = size_a;
        while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
            ;
        if (i < 0)
            return (PyLongObject *)PyLong_FromLong(0);
        if (a->ob_digit[i] < b->ob_digit[i]) {
            sign = -1;
            { PyLongObject *temp = a; a = b; b = temp; }
        }
        size_a = size_b = i+1;
    }
    z = _PyLong_New(size_a);
    if (z == NULL)
        return NULL;
    for (i = 0; i < size_b; ++i) {
        /* The following assumes unsigned arithmetic
           works module 2**N for some N>PyLong_SHIFT. */
        borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
    for (; i < size_a; ++i) {
        borrow = a->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
    assert(borrow == 0);
    if (sign < 0)
        NEGATE(z);
    return long_normalize(z);
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

unsigned char _PyLong_DigitValue[256]
Initial value:
 {
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  37, 37, 37, 37, 37, 37,
    37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
    25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
    37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
    25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
    37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
}

Definition at line 1767 of file longobject.c.

const unsigned char BitLengthTable[32] [static]
Initial value:
 {
    0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
}

Definition at line 1394 of file longobject.c.

Initial value:
 {
    "sys.int_info",   
    int_info__doc__,  
    int_info_fields,  
    2                 
}

Definition at line 4810 of file longobject.c.

Initial value:
 {
    {"bits_per_digit", "size of a digit in bits"},
    {"sizeof_digit", "size in bytes of the C type used to represent a digit"},
    {NULL, NULL}
}

Definition at line 4804 of file longobject.c.

Definition at line 4796 of file longobject.c.

Definition at line 4716 of file longobject.c.

Initial value:
 {
    {"real",
     (getter)long_long, (setter)NULL,
     "the real part of a complex number",
     NULL},
    {"imag",
     (getter)long_get0, (setter)NULL,
     "the imaginary part of a complex number",
     NULL},
    {"numerator",
     (getter)long_long, (setter)NULL,
     "the numerator of a rational number in lowest terms",
     NULL},
    {"denominator",
     (getter)long_get1, (setter)NULL,
     "the denominator of a rational number in lowest terms",
     NULL},
    {NULL}  
}

Definition at line 4687 of file longobject.c.

Initial value:
 {
    {"conjugate",       (PyCFunction)long_long, METH_NOARGS,
     "Returns self, the complex conjugate of any int."},
    {"bit_length",      (PyCFunction)long_bit_length, METH_NOARGS,
     long_bit_length_doc},




    {"to_bytes",        (PyCFunction)long_to_bytes,
     METH_VARARGS|METH_KEYWORDS, long_to_bytes_doc},
    {"from_bytes",      (PyCFunction)long_from_bytes,
     METH_VARARGS|METH_KEYWORDS|METH_CLASS, long_from_bytes_doc},
    {"__trunc__",       (PyCFunction)long_long, METH_NOARGS,
     "Truncating an Integral returns itself."},
    {"__floor__",       (PyCFunction)long_long, METH_NOARGS,
     "Flooring an Integral returns itself."},
    {"__ceil__",        (PyCFunction)long_long, METH_NOARGS,
     "Ceiling of an Integral returns itself."},
    {"__round__",       (PyCFunction)long_round, METH_VARARGS,
     "Rounding an Integral returns itself.\n"
     "Rounding with an ndigits argument also returns an integer."},
    {"__getnewargs__",          (PyCFunction)long_getnewargs,   METH_NOARGS},
    {"__format__", (PyCFunction)long__format__, METH_VARARGS},
    {"__sizeof__",      (PyCFunction)long_sizeof, METH_NOARGS,
     "Returns size in memory, in bytes"},
    {NULL,              NULL}           
}

Definition at line 4658 of file longobject.c.

Definition at line 4753 of file longobject.c.

PyLongObject small_ints[NSMALLNEGINTS+NSMALLPOSINTS] [static]

Definition at line 31 of file longobject.c.