Python의 큰 정수 표현법 1

/* Long integer representation.
   The absolute value of a number is equal to
        SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i)
   Negative numbers are represented with ob_size < 0;
   zero is represented by ob_size == 0.
   In a normalized number, ob_digit[abs(ob_size)-1] (the most significant
   digit) is never zero.  Also, in all cases, for all valid i,
        0 <= ob_digit[i] <= MASK.
   The allocation function takes care of allocating extra memory
   so that ob_digit[0] ... ob_digit[abs(ob_size)-1] are actually available.
   CAUTION:  Generic code manipulating subtypes of PyVarObject has to
   aware that ints abuse  ob_size's sign bit.
*/

struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

PyAPI_FUNC(PyObject *) PyLong_FromLong(long);
PyAPI_FUNC(PyObject *) PyLong_FromUnsignedLong(unsigned long);
PyAPI_FUNC(PyObject *) PyLong_FromSize_t(size_t);
PyAPI_FUNC(PyObject *) PyLong_FromSsize_t(Py_ssize_t);
PyAPI_FUNC(PyObject *) PyLong_FromDouble(double);
PyAPI_FUNC(long) PyLong_AsLong(PyObject *);
PyAPI_FUNC(long) PyLong_AsLongAndOverflow(PyObject *, int *);

/* 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;
}

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

PyAPI_FUNC(PyObject *) PyLong_FromLongLong(long long);
PyAPI_FUNC(PyObject *) PyLong_FromUnsignedLongLong(unsigned long long);
PyAPI_FUNC(long long) PyLong_AsLongLong(PyObject *);
PyAPI_FUNC(unsigned long long) PyLong_AsUnsignedLongLong(PyObject *);
PyAPI_FUNC(unsigned long long) PyLong_AsUnsignedLongLongMask(PyObject *);
PyAPI_FUNC(long long) PyLong_AsLongLongAndOverflow(PyObject *, int *);

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

...

/* 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 int 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;
    }
}

/* Convert an integer to a base 10 string.  Returns a new non-shared
   string.  (Return value is non-shared so that callers can modify the
   returned value if necessary.) */

static int
long_to_decimal_string_internal(PyObject *aa,
                                PyObject **p_output,
                                _PyUnicodeWriter *writer,
                                _PyBytesWriter *bytes_writer,
                                char **bytes_str)

static int
long_compare(PyLongObject *a, PyLongObject *b)
{
    Py_ssize_t sign;

    if (Py_SIZE(a) != Py_SIZE(b)) {
        sign = Py_SIZE(a) - Py_SIZE(b);
    }
    else {
        Py_ssize_t i = Py_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;
}

#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS           257
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS           5
#endif

...

/* Small integers are preallocated in this array so that they
   can be shared.
   The integers that are preallocated are those in the range
   -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];