if (vv == NULL || !PyLong_Check(vv)) { PyErr_BadInternalCall(); return (unsigned long) -1; } v = (PyLongObject *)vv; i = v->ob_size; sign = 1; x = 0; if (i < 0) { sign = -1; i = -i; } while (--i >= 0) { x = (x << SHIFT) + v->ob_digit[i]; } return x * sign;}#undef IS_LITTLE_ENDIAN #endif /* HAVE_LONG_LONG */ static intconvert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) { if (PyLong_Check(v)) { *a = (PyLongObject *) v; Py_INCREF(v); } else if (PyInt_Check(v)) { *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v)); } else { return 0; } if (PyLong_Check(w)) { *b = (PyLongObject *) w; Py_INCREF(w); } else if (PyInt_Check(w)) { *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w)); } else { Py_DECREF(*a); return 0; } return 1;} #define CONVERT_BINOP(v, w, a, b) \ if (!convert_binop(v, w, a, b)) { \ Py_INCREF(Py_NotImplemented); \ return Py_NotImplemented; \ } /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n] * is modified in place, by adding y to it. Carries are propagated as far as * x[m-1], and the remaining carry (0 or 1) is returned. */static digitv_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n){ int i; digit carry = 0; assert(m >= n); for (i = 0; i < n; ++i) { carry += x[i] + y[i]; x[i] = carry & MASK; carry >>= SHIFT; assert((carry & 1) == carry); } for (; carry && i < m; ++i) { carry += x[i]; x[i] = carry & MASK; carry >>= SHIFT; assert((carry & 1) == carry); } return carry;} /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n] * is modified in place, by subtracting y from it. Borrows are propagated as * far as x[m-1], and the remaining borrow (0 or 1) is returned. */static digitv_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n){ int i; digit borrow = 0; assert(m >= n); for (i = 0; i < n; ++i) { borrow = x[i] - y[i] - borrow; x[i] = borrow & MASK; borrow >>= SHIFT; borrow &= 1; /* keep only 1 sign bit */ } for (; borrow && i < m; ++i) { borrow = x[i] - borrow; x[i] = borrow & MASK; borrow >>= SHIFT; borrow &= 1; } return borrow;} /* Multiply by a single digit, ignoring the sign. */ static PyLongObject *mul1(PyLongObject *a, wdigit n){ return muladd1(a, n, (digit)0);} /* Multiply by a single digit and add a single digit, ignoring the sign. */ static PyLongObject *muladd1(PyLongObject *a, wdigit n, wdigit extra){ Py_ssize_t size_a = ABS(a->ob_size); PyLongObject *z = _PyLong_New(size_a+1); twodigits carry = extra; Py_ssize_t i; if (z == NULL) return NULL; for (i = 0; i < size_a; ++i) { carry += (twodigits)a->ob_digit[i] * n; z->ob_digit[i] = (digit) (carry & MASK); carry >>= SHIFT; } z->ob_digit[i] = (digit) carry; return long_normalize(z);} /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient in pout, and returning the remainder. pin and pout point at the LSD. It's OK for pin == pout on entry, which saves oodles of mallocs/frees in long_format, but that should be done with great care since longs are immutable. */ static digitinplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n){ twodigits rem = 0; assert(n > 0 && n <= MASK); pin += size; pout += size; while (--size >= 0) { digit hi; rem = (rem << SHIFT) + *--pin; *--pout = hi = (digit)(rem / n); rem -= hi * n; } return (digit)rem;} /* Divide a long integer by a digit, returning both the quotient (as function result) and the remainder (through *prem). The sign of a is ignored; n should not be zero. */ static PyLongObject *divrem1(PyLongObject *a, digit n, digit *prem){ const Py_ssize_t size = ABS(a->ob_size); PyLongObject *z; assert(n > 0 && n <= 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);} /* Convert a long int object to a string, using a given conversion base. Return a string object. If base is 8 or 16, add the proper prefix '0' or '0x'. */ static PyObject *long_format(PyObject *aa, int base, int addL){ register PyLongObject *a = (PyLongObject *)aa; PyStringObject *str; Py_ssize_t i, j, sz; Py_ssize_t size_a; char *p; int bits; char sign = '\0'; if (a == NULL || !PyLong_Check(a)) { PyErr_BadInternalCall(); return NULL; } assert(base >= 2 && base <= 36); size_a = ABS(a->ob_size); /* Compute a rough upper bound for the length of the string */ i = base; bits = 0; while (i > 1) { ++bits; i >>= 1; } i = 5 + (addL ? 1 : 0); j = size_a*SHIFT + bits-1; sz = i + j / bits; if (j / SHIFT < size_a || sz < i) { PyErr_SetString(PyExc_OverflowError, "long is too large to format"); return NULL; } str = (PyStringObject *) PyString_FromStringAndSize((char *)0, sz); if (str == NULL) return NULL; p = PyString_AS_STRING(str) + sz; *p = '\0'; if (addL) *--p = 'L'; if (a->ob_size < 0) sign = '-'; if (a->ob_size == 0) { *--p = '0'; } else if ((base & (base - 1)) == 0) { /* JRH: special case for power-of-2 bases */ twodigits accum = 0; int accumbits = 0; /* # of bits in accum */ int basebits = 1; /* # of bits in base-1 */ i = base; while ((i >>= 1) > 1) ++basebits; for (i = 0; i < size_a; ++i) { accum |= (twodigits)a->ob_digit[i] << accumbits; accumbits += SHIFT; assert(accumbits >= basebits); do { char cdigit = (char)(accum & (base - 1)); cdigit += (cdigit < 10) ? '0' : 'a'-10; assert(p > PyString_AS_STRING(str)); *--p = cdigit; accumbits -= basebits; accum >>= basebits; } while (i < size_a-1 ? accumbits >= basebits : accum > 0); } } else { /* Not 0, and base not a power of 2. Divide repeatedly by base, but for speed use the highest power of base that fits in a digit. */ Py_ssize_t size = size_a; digit *pin = a->ob_digit; PyLongObject *scratch; /* powbasw <- largest power of base that fits in a digit. */ digit powbase = base; /* powbase == base ** power */ int power = 1; for (;;) { unsigned long newpow = powbase * (unsigned long)base; if (newpow >> SHIFT) /* doesn't fit in a digit */ break; powbase = (digit)newpow; ++power; } /* Get a scratch area for repeated division. */ scratch = _PyLong_New(size); if (scratch == NULL) { Py_DECREF(str); return NULL; } /* Repeatedly divide by powbase. */ do { int ntostore = power; digit rem = inplace_divrem1(scratch->ob_digit, pin, size, powbase); pin = scratch->ob_digit; /* no need to use a again */ if (pin[size - 1] == 0) --size; SIGCHECK({ Py_DECREF(scratch); Py_DECREF(str); return NULL; }) /* Break rem into digits. */ assert(ntostore > 0); do { digit nextrem = (digit)(rem / base); char c = (char)(rem - nextrem * base); assert(p > PyString_AS_STRING(str)); c += (c < 10) ? '0' : 'a'-10; *--p = c; rem = nextrem; --ntostore; /* Termination is a bit delicate: must not store leading zeroes, so must get out if remaining quotient and rem are both 0. */ } while (ntostore && (size || rem)); } while (size != 0); Py_DECREF(scratch); } if (base == 8) { if (size_a != 0) *--p = '0'; } else if (base == 16) { *--p = 'x'; *--p = '0'; } else if (base != 10) { *--p = '#'; *--p = '0' + base%10; if (base > 10) *--p = '0' + base/10; } if (sign) *--p = sign; if (p != PyString_AS_STRING(str)) { char *q = PyString_AS_STRING(str); assert(p > q); do { } while ((*q++ = *p++) != '\0'); q--; _PyString_Resize((PyObject **)&str, (Py_ssize_t) (q - PyString_AS_STRING(str))); } return (PyObject *)str;} /* Table of digit values for 8-bit string -> integer conversion. * '0' maps to 0, ..., '9' maps to 9. * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35. * All other indices map to 37. * Note that when converting a base B string, a char c is a legitimate * base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B. */int _PyLong_DigitValue[256] = { 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,}; /* *str points to the first digit in a string of base `base` digits. base * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first * non-digit (which may be *str!). A normalized long is returned. * The point to this routine is that it takes time linear in the number of * string characters. */static PyLongObject *long_from_binary_base(char **str, int base){ 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 */ n = 0; while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base) ++p; *str = p; /* n <- # of Python digits needed, = ceiling(n/SHIFT). */ n = (p - start) * bits_per_char + SHIFT - 1; if (n / bits_per_char < p - start) { PyErr_SetString(PyExc_ValueError, "long string too large to convert"); return NULL; } n = n / 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 = _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 >= SHIFT) { *pdigit++ = (digit)(accum & MASK); assert(pdigit - z->ob_digit <= (int)n); accum >>= SHIFT; bits_in_accum -= SHIFT; assert(bits_in_accum < SHIFT); } } if (bits_in_accum) { assert(bits_in_accum <= SHIFT); *pdigit++ = (digit)accum; assert(pdigit - z->ob_digit <= (int)n); } while (pdigit - z->ob_digit < n) *pdigit++ = 0; return long_normalize(z);} PyObject *PyLong_FromString(char *str, char **pend, int base){ int sign = 1; char *start, *orig_str = str; PyLongObject *z; PyObject *strobj, *strrepr; Py_ssize_t slen; if ((base != 0 && base < 2) || base > 36) { PyErr_SetString(PyExc_ValueError, "long() 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; } while (*str != '\0' && isspace(Py_CHARMASK(*str))) str++; if (base == 0) { if (str[0] != '0') base = 10; else if (str[1] == 'x' || str[1] == 'X') base = 16; else base = 8; } if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X')) 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, becausePython's representation base is binary. Other bases (including decimal!) usethe simple quadratic-time algorithm below, complicated by some speed tricks. First some math: the largest integer that can be expressed in N base-B digitsis 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 computethis 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 digitsare 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 digitsmust fit in a single Python digit. The second is effectively the inputbase we're really using. Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in baseconvmultmax_base[base], the result is "simply" (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1 where B = convmultmax_base[base].Lines 1001–1500 of 3458. Previous lines Load more
if (vv == NULL || !PyLong_Check(vv)) { PyErr_BadInternalCall(); return (unsigned long) -1; } v = (PyLongObject *)vv; i = v->ob_size; sign = 1; x = 0; if (i < 0) { sign = -1; i = -i; } while (--i >= 0) { x = (x << SHIFT) + v->ob_digit[i]; } return x * sign; } #undef IS_LITTLE_ENDIAN #endif /* HAVE_LONG_LONG */ static int convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) { if (PyLong_Check(v)) { *a = (PyLongObject *) v; Py_INCREF(v); } else if (PyInt_Check(v)) { *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v)); } else { return 0; } if (PyLong_Check(w)) { *b = (PyLongObject *) w; Py_INCREF(w); } else if (PyInt_Check(w)) { *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w)); } else { Py_DECREF(*a); return 0; } return 1; } #define CONVERT_BINOP(v, w, a, b) \ if (!convert_binop(v, w, a, b)) { \ Py_INCREF(Py_NotImplemented); \ return Py_NotImplemented; \ } /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n] * is modified in place, by adding y to it. Carries are propagated as far as * x[m-1], and the remaining carry (0 or 1) is returned. */ static digit v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n) { int i; digit carry = 0; assert(m >= n); for (i = 0; i < n; ++i) { carry += x[i] + y[i]; x[i] = carry & MASK; carry >>= SHIFT; assert((carry & 1) == carry); } for (; carry && i < m; ++i) { carry += x[i]; x[i] = carry & MASK; carry >>= SHIFT; assert((carry & 1) == carry); } return carry; } /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n] * is modified in place, by subtracting y from it. Borrows are propagated as * far as x[m-1], and the remaining borrow (0 or 1) is returned. */ static digit v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n) { int i; digit borrow = 0; assert(m >= n); for (i = 0; i < n; ++i) { borrow = x[i] - y[i] - borrow; x[i] = borrow & MASK; borrow >>= SHIFT; borrow &= 1; /* keep only 1 sign bit */ } for (; borrow && i < m; ++i) { borrow = x[i] - borrow; x[i] = borrow & MASK; borrow >>= SHIFT; borrow &= 1; } return borrow; } /* Multiply by a single digit, ignoring the sign. */ static PyLongObject * mul1(PyLongObject *a, wdigit n) { return muladd1(a, n, (digit)0); } /* Multiply by a single digit and add a single digit, ignoring the sign. */ static PyLongObject * muladd1(PyLongObject *a, wdigit n, wdigit extra) { Py_ssize_t size_a = ABS(a->ob_size); PyLongObject *z = _PyLong_New(size_a+1); twodigits carry = extra; Py_ssize_t i; if (z == NULL) return NULL; for (i = 0; i < size_a; ++i) { carry += (twodigits)a->ob_digit[i] * n; z->ob_digit[i] = (digit) (carry & MASK); carry >>= SHIFT; } z->ob_digit[i] = (digit) carry; return long_normalize(z); } /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient in pout, and returning the remainder. pin and pout point at the LSD. It's OK for pin == pout on entry, which saves oodles of mallocs/frees in long_format, but that should be done with great care since longs are immutable. */ static digit inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n) { twodigits rem = 0; assert(n > 0 && n <= MASK); pin += size; pout += size; while (--size >= 0) { digit hi; rem = (rem << SHIFT) + *--pin; *--pout = hi = (digit)(rem / n); rem -= hi * n; } return (digit)rem; } /* Divide a long integer by a digit, returning both the quotient (as function result) and the remainder (through *prem). The sign of a is ignored; n should not be zero. */ static PyLongObject * divrem1(PyLongObject *a, digit n, digit *prem) { const Py_ssize_t size = ABS(a->ob_size); PyLongObject *z; assert(n > 0 && n <= 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); } /* Convert a long int object to a string, using a given conversion base. Return a string object. If base is 8 or 16, add the proper prefix '0' or '0x'. */ static PyObject * long_format(PyObject *aa, int base, int addL) { register PyLongObject *a = (PyLongObject *)aa; PyStringObject *str; Py_ssize_t i, j, sz; Py_ssize_t size_a; char *p; int bits; char sign = '\0'; if (a == NULL || !PyLong_Check(a)) { PyErr_BadInternalCall(); return NULL; } assert(base >= 2 && base <= 36); size_a = ABS(a->ob_size); /* Compute a rough upper bound for the length of the string */ i = base; bits = 0; while (i > 1) { ++bits; i >>= 1; } i = 5 + (addL ? 1 : 0); j = size_a*SHIFT + bits-1; sz = i + j / bits; if (j / SHIFT < size_a || sz < i) { PyErr_SetString(PyExc_OverflowError, "long is too large to format"); return NULL; } str = (PyStringObject *) PyString_FromStringAndSize((char *)0, sz); if (str == NULL) return NULL; p = PyString_AS_STRING(str) + sz; *p = '\0'; if (addL) *--p = 'L'; if (a->ob_size < 0) sign = '-'; if (a->ob_size == 0) { *--p = '0'; } else if ((base & (base - 1)) == 0) { /* JRH: special case for power-of-2 bases */ twodigits accum = 0; int accumbits = 0; /* # of bits in accum */ int basebits = 1; /* # of bits in base-1 */ i = base; while ((i >>= 1) > 1) ++basebits; for (i = 0; i < size_a; ++i) { accum |= (twodigits)a->ob_digit[i] << accumbits; accumbits += SHIFT; assert(accumbits >= basebits); do { char cdigit = (char)(accum & (base - 1)); cdigit += (cdigit < 10) ? '0' : 'a'-10; assert(p > PyString_AS_STRING(str)); *--p = cdigit; accumbits -= basebits; accum >>= basebits; } while (i < size_a-1 ? accumbits >= basebits : accum > 0); } } else { /* Not 0, and base not a power of 2. Divide repeatedly by base, but for speed use the highest power of base that fits in a digit. */ Py_ssize_t size = size_a; digit *pin = a->ob_digit; PyLongObject *scratch; /* powbasw <- largest power of base that fits in a digit. */ digit powbase = base; /* powbase == base ** power */ int power = 1; for (;;) { unsigned long newpow = powbase * (unsigned long)base; if (newpow >> SHIFT) /* doesn't fit in a digit */ break; powbase = (digit)newpow; ++power; } /* Get a scratch area for repeated division. */ scratch = _PyLong_New(size); if (scratch == NULL) { Py_DECREF(str); return NULL; } /* Repeatedly divide by powbase. */ do { int ntostore = power; digit rem = inplace_divrem1(scratch->ob_digit, pin, size, powbase); pin = scratch->ob_digit; /* no need to use a again */ if (pin[size - 1] == 0) --size; SIGCHECK({ Py_DECREF(scratch); Py_DECREF(str); return NULL; }) /* Break rem into digits. */ assert(ntostore > 0); do { digit nextrem = (digit)(rem / base); char c = (char)(rem - nextrem * base); assert(p > PyString_AS_STRING(str)); c += (c < 10) ? '0' : 'a'-10; *--p = c; rem = nextrem; --ntostore; /* Termination is a bit delicate: must not store leading zeroes, so must get out if remaining quotient and rem are both 0. */ } while (ntostore && (size || rem)); } while (size != 0); Py_DECREF(scratch); } if (base == 8) { if (size_a != 0) *--p = '0'; } else if (base == 16) { *--p = 'x'; *--p = '0'; } else if (base != 10) { *--p = '#'; *--p = '0' + base%10; if (base > 10) *--p = '0' + base/10; } if (sign) *--p = sign; if (p != PyString_AS_STRING(str)) { char *q = PyString_AS_STRING(str); assert(p > q); do { } while ((*q++ = *p++) != '\0'); q--; _PyString_Resize((PyObject **)&str, (Py_ssize_t) (q - PyString_AS_STRING(str))); } return (PyObject *)str; } /* Table of digit values for 8-bit string -> integer conversion. * '0' maps to 0, ..., '9' maps to 9. * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35. * All other indices map to 37. * Note that when converting a base B string, a char c is a legitimate * base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B. */ int _PyLong_DigitValue[256] = { 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, }; /* *str points to the first digit in a string of base `base` digits. base * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first * non-digit (which may be *str!). A normalized long is returned. * The point to this routine is that it takes time linear in the number of * string characters. */ static PyLongObject * long_from_binary_base(char **str, int base) { 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 */ n = 0; while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base) ++p; *str = p; /* n <- # of Python digits needed, = ceiling(n/SHIFT). */ n = (p - start) * bits_per_char + SHIFT - 1; if (n / bits_per_char < p - start) { PyErr_SetString(PyExc_ValueError, "long string too large to convert"); return NULL; } n = n / 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 = _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 >= SHIFT) { *pdigit++ = (digit)(accum & MASK); assert(pdigit - z->ob_digit <= (int)n); accum >>= SHIFT; bits_in_accum -= SHIFT; assert(bits_in_accum < SHIFT); } } if (bits_in_accum) { assert(bits_in_accum <= SHIFT); *pdigit++ = (digit)accum; assert(pdigit - z->ob_digit <= (int)n); } while (pdigit - z->ob_digit < n) *pdigit++ = 0; return long_normalize(z); } PyObject * PyLong_FromString(char *str, char **pend, int base) { int sign = 1; char *start, *orig_str = str; PyLongObject *z; PyObject *strobj, *strrepr; Py_ssize_t slen; if ((base != 0 && base < 2) || base > 36) { PyErr_SetString(PyExc_ValueError, "long() 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; } while (*str != '\0' && isspace(Py_CHARMASK(*str))) str++; if (base == 0) { if (str[0] != '0') base = 10; else if (str[1] == 'x' || str[1] == 'X') base = 16; else base = 8; } if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X')) 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].