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 whetherthe 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 differencebetween the worst-case input with N digits and the smallest input with Ndigits is about a factor of B, but B is small compared to BASE so at mostone allocated Python digit can remain unused on that count. IfN*log(B)/log(BASE) is mathematically an exact integer, then truncating thatand adding 1 returns a result 1 larger than necessary. However, that can'thappen: whenever B is a power of 2, long_from_binary_base() is calledinstead, and it's impossible for B**i to be an integer power of 2**15 whenB is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to bean exact integer when B is not a power of 2, since B**i has a prime factorother 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 (incomputing log(B), log(BASE), their quotient, and/or multiplying that by N)yields a numeric result a little less than that integer. Unfortunately, "howclose can a transcendental function get to an integer over some range?"questions are generally theoretically intractable. Computer analysis viacontinued fractions is practical: expand log(B)/log(BASE) via continuedfractions, giving a sequence i/j of "the best" rational approximations. Thenj*log(B)/log(BASE) is approximately equal to (the integer) i. This shows thatwe can get very close to being in trouble, but very rarely. For example,76573 is a denominator in one of the continued-fraction approximations tolog(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-precisionrequires better-than-double-precision log() functions, and Tim didn't bother.Instead the code checks to see whether the allocated space is enough as eachnew 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 casethat triggers it(!). Instead the code was tested by artificially allocatingjust 1 digit at the start, so that the copying code was exercised for everydigit 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)BASE); for (;;) { twodigits next = convmax * base; if (next > 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; z->ob_size = 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 + _PyLong_DigitValue[Py_CHARMASK(*str)]); assert(c < 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 + z->ob_size; for (; pz < pzstop; ++pz) { c += (twodigits)*pz * convmult; *pz = (digit)(c & MASK); c >>= SHIFT; } /* carry off the current end? */ if (c) { assert(c < BASE); if (z->ob_size < size_z) { *pz = (digit)c; ++z->ob_size; } else { PyLongObject *tmp; /* Extremely rare. Get more space. */ assert(z->ob_size == 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 (str == start) goto onError; if (sign < 0) z->ob_size = -(z->ob_size); if (*str == 'L' || *str == 'l') str++; while (*str && isspace(Py_CHARMASK(*str))) str++; if (*str != '\0') goto onError; if (pend) *pend = str; return (PyObject *) z; onError: Py_XDECREF(z); slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200; strobj = PyString_FromStringAndSize(orig_str, slen); if (strobj == NULL) return NULL; strrepr = PyObject_Repr(strobj); Py_DECREF(strobj); if (strrepr == NULL) return NULL; PyErr_Format(PyExc_ValueError, "invalid literal for long() with base %d: %s", base, PyString_AS_STRING(strrepr)); Py_DECREF(strrepr); return NULL;} #ifdef Py_USING_UNICODEPyObject *PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base){ PyObject *result; char *buffer = (char *)PyMem_MALLOC(length+1); if (buffer == NULL) return NULL; if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) { PyMem_FREE(buffer); return NULL; } result = PyLong_FromString(buffer, NULL, base); PyMem_FREE(buffer); return result;}#endif /* forward */static PyLongObject *x_divrem (PyLongObject *, PyLongObject *, PyLongObject **);static PyObject *long_pos(PyLongObject *);static int long_divrem(PyLongObject *, PyLongObject *, PyLongObject **, PyLongObject **); /* Long division with remainder, top-level routine */ static intlong_divrem(PyLongObject *a, PyLongObject *b, PyLongObject **pdiv, PyLongObject **prem){ Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); PyLongObject *z; if (size_b == 0) { PyErr_SetString(PyExc_ZeroDivisionError, "long 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 = _PyLong_New(0); 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); } 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 ((a->ob_size < 0) != (b->ob_size < 0)) z->ob_size = -(z->ob_size); if (a->ob_size < 0 && (*prem)->ob_size != 0) (*prem)->ob_size = -((*prem)->ob_size); *pdiv = z; return 0;} /* Unsigned long division with remainder -- the algorithm */ static PyLongObject *x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem){ Py_ssize_t size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size); digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1)); PyLongObject *v = mul1(v1, d); PyLongObject *w = mul1(w1, d); PyLongObject *a; Py_ssize_t j, k; if (v == NULL || w == NULL) { Py_XDECREF(v); Py_XDECREF(w); return NULL; } assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */ assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */ assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */ size_v = ABS(v->ob_size); k = size_v - size_w; a = _PyLong_New(k + 1); for (j = size_v; a != NULL && k >= 0; --j, --k) { digit vj = (j >= size_v) ? 0 : v->ob_digit[j]; twodigits q; stwodigits carry = 0; int i; SIGCHECK({ Py_DECREF(a); a = NULL; break; }) if (vj == w->ob_digit[size_w-1]) q = MASK; else q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) / w->ob_digit[size_w-1]; while (w->ob_digit[size_w-2]*q > (( ((twodigits)vj << SHIFT) + v->ob_digit[j-1] - q*w->ob_digit[size_w-1] ) << SHIFT) + v->ob_digit[j-2]) --q; for (i = 0; i < size_w && i+k < size_v; ++i) { twodigits z = w->ob_digit[i] * q; digit zz = (digit) (z >> SHIFT); carry += v->ob_digit[i+k] - z + ((twodigits)zz << SHIFT); v->ob_digit[i+k] = (digit)(carry & MASK); carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE, carry, SHIFT); carry -= zz; } if (i+k < size_v) { carry += v->ob_digit[i+k]; v->ob_digit[i+k] = 0; } if (carry == 0) a->ob_digit[k] = (digit) q; else { assert(carry == -1); a->ob_digit[k] = (digit) q-1; carry = 0; for (i = 0; i < size_w && i+k < size_v; ++i) { carry += v->ob_digit[i+k] + w->ob_digit[i]; v->ob_digit[i+k] = (digit)(carry & MASK); carry = Py_ARITHMETIC_RIGHT_SHIFT( BASE_TWODIGITS_TYPE, carry, SHIFT); } } } /* for j, k */ if (a == NULL) *prem = NULL; else { a = long_normalize(a); *prem = divrem1(v, d, &d); /* d receives the (unused) remainder */ if (*prem == NULL) { Py_DECREF(a); a = NULL; } } Py_DECREF(v); Py_DECREF(w); return a;} /* Methods */ static voidlong_dealloc(PyObject *v){ v->ob_type->tp_free(v);} static PyObject *long_repr(PyObject *v){ return long_format(v, 10, 1);} static PyObject *long_str(PyObject *v){ return long_format(v, 10, 0);} static intlong_compare(PyLongObject *a, PyLongObject *b){ Py_ssize_t sign; if (a->ob_size != b->ob_size) { if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0) sign = 0; else sign = a->ob_size - b->ob_size; } else { Py_ssize_t i = ABS(a->ob_size); while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) ; if (i < 0) sign = 0; else { sign = (int)a->ob_digit[i] - (int)b->ob_digit[i]; if (a->ob_size < 0) sign = -sign; } } return sign < 0 ? -1 : sign > 0 ? 1 : 0;} static longlong_hash(PyLongObject *v){ long x; Py_ssize_t i; int sign; /* This is designed so that Python ints and longs with the same value hash to the same value, otherwise comparisons of mapping keys will turn out weird */ i = v->ob_size; sign = 1; x = 0; if (i < 0) { sign = -1; i = -(i); }#define LONG_BIT_SHIFT (8*sizeof(long) - SHIFT) while (--i >= 0) { /* Force a native long #-bits (32 or 64) circular shift */ x = ((x << SHIFT) & ~MASK) | ((x >> LONG_BIT_SHIFT) & MASK); x += v->ob_digit[i]; }#undef LONG_BIT_SHIFT x = x * sign; if (x == -1) x = -2; return x;} /* Add the absolute values of two long integers. */ static PyLongObject *x_add(PyLongObject *a, PyLongObject *b){ Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); PyLongObject *z; int 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 & MASK; carry >>= SHIFT; } for (; i < size_a; ++i) { carry += a->ob_digit[i]; z->ob_digit[i] = carry & MASK; carry >>= SHIFT; } z->ob_digit[i] = carry; return long_normalize(z);} /* Subtract the absolute values of two integers. */ static PyLongObject *x_sub(PyLongObject *a, PyLongObject *b){ Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 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) {Lines 1501–2000 of 3458. Previous lines Load more
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)BASE); for (;;) { twodigits next = convmax * base; if (next > 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; z->ob_size = 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 + _PyLong_DigitValue[Py_CHARMASK(*str)]); assert(c < 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 + z->ob_size; for (; pz < pzstop; ++pz) { c += (twodigits)*pz * convmult; *pz = (digit)(c & MASK); c >>= SHIFT; } /* carry off the current end? */ if (c) { assert(c < BASE); if (z->ob_size < size_z) { *pz = (digit)c; ++z->ob_size; } else { PyLongObject *tmp; /* Extremely rare. Get more space. */ assert(z->ob_size == 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 (str == start) goto onError; if (sign < 0) z->ob_size = -(z->ob_size); if (*str == 'L' || *str == 'l') str++; while (*str && isspace(Py_CHARMASK(*str))) str++; if (*str != '\0') goto onError; if (pend) *pend = str; return (PyObject *) z; onError: Py_XDECREF(z); slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200; strobj = PyString_FromStringAndSize(orig_str, slen); if (strobj == NULL) return NULL; strrepr = PyObject_Repr(strobj); Py_DECREF(strobj); if (strrepr == NULL) return NULL; PyErr_Format(PyExc_ValueError, "invalid literal for long() with base %d: %s", base, PyString_AS_STRING(strrepr)); Py_DECREF(strrepr); return NULL; } #ifdef Py_USING_UNICODE PyObject * PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base) { PyObject *result; char *buffer = (char *)PyMem_MALLOC(length+1); if (buffer == NULL) return NULL; if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) { PyMem_FREE(buffer); return NULL; } result = PyLong_FromString(buffer, NULL, base); PyMem_FREE(buffer); return result; } #endif /* forward */ static PyLongObject *x_divrem (PyLongObject *, PyLongObject *, PyLongObject **); static PyObject *long_pos(PyLongObject *); static int long_divrem(PyLongObject *, PyLongObject *, PyLongObject **, PyLongObject **); /* Long division with remainder, top-level routine */ static int long_divrem(PyLongObject *a, PyLongObject *b, PyLongObject **pdiv, PyLongObject **prem) { Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); PyLongObject *z; if (size_b == 0) { PyErr_SetString(PyExc_ZeroDivisionError, "long 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 = _PyLong_New(0); 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); } 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 ((a->ob_size < 0) != (b->ob_size < 0)) z->ob_size = -(z->ob_size); if (a->ob_size < 0 && (*prem)->ob_size != 0) (*prem)->ob_size = -((*prem)->ob_size); *pdiv = z; return 0; } /* Unsigned long division with remainder -- the algorithm */ static PyLongObject * x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem) { Py_ssize_t size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size); digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1)); PyLongObject *v = mul1(v1, d); PyLongObject *w = mul1(w1, d); PyLongObject *a; Py_ssize_t j, k; if (v == NULL || w == NULL) { Py_XDECREF(v); Py_XDECREF(w); return NULL; } assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */ assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */ assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */ size_v = ABS(v->ob_size); k = size_v - size_w; a = _PyLong_New(k + 1); for (j = size_v; a != NULL && k >= 0; --j, --k) { digit vj = (j >= size_v) ? 0 : v->ob_digit[j]; twodigits q; stwodigits carry = 0; int i; SIGCHECK({ Py_DECREF(a); a = NULL; break; }) if (vj == w->ob_digit[size_w-1]) q = MASK; else q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) / w->ob_digit[size_w-1]; while (w->ob_digit[size_w-2]*q > (( ((twodigits)vj << SHIFT) + v->ob_digit[j-1] - q*w->ob_digit[size_w-1] ) << SHIFT) + v->ob_digit[j-2]) --q; for (i = 0; i < size_w && i+k < size_v; ++i) { twodigits z = w->ob_digit[i] * q; digit zz = (digit) (z >> SHIFT); carry += v->ob_digit[i+k] - z + ((twodigits)zz << SHIFT); v->ob_digit[i+k] = (digit)(carry & MASK); carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE, carry, SHIFT); carry -= zz; } if (i+k < size_v) { carry += v->ob_digit[i+k]; v->ob_digit[i+k] = 0; } if (carry == 0) a->ob_digit[k] = (digit) q; else { assert(carry == -1); a->ob_digit[k] = (digit) q-1; carry = 0; for (i = 0; i < size_w && i+k < size_v; ++i) { carry += v->ob_digit[i+k] + w->ob_digit[i]; v->ob_digit[i+k] = (digit)(carry & MASK); carry = Py_ARITHMETIC_RIGHT_SHIFT( BASE_TWODIGITS_TYPE, carry, SHIFT); } } } /* for j, k */ if (a == NULL) *prem = NULL; else { a = long_normalize(a); *prem = divrem1(v, d, &d); /* d receives the (unused) remainder */ if (*prem == NULL) { Py_DECREF(a); a = NULL; } } Py_DECREF(v); Py_DECREF(w); return a; } /* Methods */ static void long_dealloc(PyObject *v) { v->ob_type->tp_free(v); } static PyObject * long_repr(PyObject *v) { return long_format(v, 10, 1); } static PyObject * long_str(PyObject *v) { return long_format(v, 10, 0); } static int long_compare(PyLongObject *a, PyLongObject *b) { Py_ssize_t sign; if (a->ob_size != b->ob_size) { if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0) sign = 0; else sign = a->ob_size - b->ob_size; } else { Py_ssize_t i = ABS(a->ob_size); while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) ; if (i < 0) sign = 0; else { sign = (int)a->ob_digit[i] - (int)b->ob_digit[i]; if (a->ob_size < 0) sign = -sign; } } return sign < 0 ? -1 : sign > 0 ? 1 : 0; } static long long_hash(PyLongObject *v) { long x; Py_ssize_t i; int sign; /* This is designed so that Python ints and longs with the same value hash to the same value, otherwise comparisons of mapping keys will turn out weird */ i = v->ob_size; sign = 1; x = 0; if (i < 0) { sign = -1; i = -(i); } #define LONG_BIT_SHIFT (8*sizeof(long) - SHIFT) while (--i >= 0) { /* Force a native long #-bits (32 or 64) circular shift */ x = ((x << SHIFT) & ~MASK) | ((x >> LONG_BIT_SHIFT) & MASK); x += v->ob_digit[i]; } #undef LONG_BIT_SHIFT x = x * sign; if (x == -1) x = -2; return x; } /* Add the absolute values of two long integers. */ static PyLongObject * x_add(PyLongObject *a, PyLongObject *b) { Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); PyLongObject *z; int 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 & MASK; carry >>= SHIFT; } for (; i < size_a; ++i) { carry += a->ob_digit[i]; z->ob_digit[i] = carry & MASK; carry >>= SHIFT; } z->ob_digit[i] = carry; return long_normalize(z); } /* Subtract the absolute values of two integers. */ static PyLongObject * x_sub(PyLongObject *a, PyLongObject *b) { Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size); 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) {