Index: Include/longintrepr.h =================================================================== --- Include/longintrepr.h (revision 74735) +++ Include/longintrepr.h (working copy) @@ -47,12 +47,16 @@ typedef PY_UINT64_T twodigits; typedef PY_INT64_T stwodigits; /* signed variant of twodigits */ #define PyLong_SHIFT 30 +#define PyLong_POWER_BASE_10 9 /* log10(2 ** PYLONG_BITS_IN_DIGIT) */ +#define PyLong_POWBASE_BASE_10 ((digit)1000000000) /* 10 ** POWER_BASE */ #elif PYLONG_BITS_IN_DIGIT == 15 typedef unsigned short digit; typedef short sdigit; /* signed variant of digit */ typedef unsigned long twodigits; typedef long stwodigits; /* signed variant of twodigits */ #define PyLong_SHIFT 15 +#define PyLong_POWER_BASE_10 4 /* log10(2 ** PYLONG_BITS_IN_DIGIT) */ +#define PyLong_POWBASE_BASE_10 ((digit)10000) /* 10 ** POWER_BASE */ #else #error "PYLONG_BITS_IN_DIGIT should be 15 or 30" #endif Index: Objects/intobject.c =================================================================== --- Objects/intobject.c (revision 74735) +++ Objects/intobject.c (working copy) @@ -1113,6 +1113,19 @@ return PyInt_FromLong(1L); } +static const char +_decimal_digit_table[] = \ + "00010203040506070809" \ + "10111213141516171819" \ + "20212223242526272829" \ + "30313233343536373839" \ + "40414243444546474849" \ + "50515253545556575859" \ + "60616263646566676869" \ + "70717273747576777879" \ + "80818283848586878889" \ + "90919293949596979899"; + /* Convert an integer to the given base. Returns a string. If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'. If newstyle is zero, then use the pre-2.6 behavior of octal having @@ -1124,7 +1137,6 @@ similar to _PyLong_Format */ long n = v->ob_ival; int negative = n < 0; - int is_zero = n == 0; /* For the reasoning behind this size, see http://c-faq.com/misc/hexio.html. Then, add a few bytes for @@ -1137,6 +1149,32 @@ assert(base >= 2 && base <= 36); + /* Special case for base 10 */ + if (base == 10) { + /* Use absolute value for formatting purposes */ + unsigned long v = n < 0 ? -n : n; + const char * t; + + /* Convert two digits at a time. */ + while (v > 99) { + const unsigned long div = v / 100; + + t = &_decimal_digit_table[(v - div * 100) << 1]; + v = div; + *--p = t[1]; + *--p = t[0]; + } + /* Convert remaining 1 or 2 digits. */ + t = &_decimal_digit_table[v << 1]; + *--p = t[1]; + + if (v > 9) + *--p = t[0]; + } + else + { + const int is_zero = n == 0; + do { /* I'd use i_divmod, except it doesn't produce the results I want when n is negative. So just duplicate the salient @@ -1169,12 +1207,13 @@ *--p = 'x'; *--p = '0'; } - else if (base != 10) { + else { *--p = '#'; *--p = '0' + base%10; if (base > 10) *--p = '0' + base/10; } + } if (negative) *--p = '-'; Index: Objects/longobject.c =================================================================== --- Objects/longobject.c (revision 74735) +++ Objects/longobject.c (working copy) @@ -1381,7 +1381,7 @@ PyErr_BadInternalCall(); return NULL; } - assert(base >= 2 && base <= 36); + assert(base == 2 || base == 8 || base == 16 || base == 10); size_a = ABS(Py_SIZE(a)); /* Compute a rough upper bound for the length of the string */ @@ -1404,8 +1404,8 @@ return NULL; p = PyString_AS_STRING(str) + sz; *p = '\0'; - if (addL) - *--p = 'L'; + if (addL) + *--p = 'L'; if (a->ob_size < 0) sign = '-'; @@ -1436,69 +1436,73 @@ 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; + else if (base == 10) { + /* Divide repeatedly by base, but for speed use the + highest power of base that fits in a digit. */ PyLongObject *scratch; - /* powbasw <- largest power of base that fits in a digit. */ - digit powbase = base; /* powbase == base ** power */ - int power = 1; - for (;;) { - twodigits newpow = powbase * (twodigits)base; - if (newpow >> PyLong_SHIFT) /* doesn't fit in a digit */ - break; - powbase = (digit)newpow; - ++power; - } + Py_ssize_t size; + digit *pout, *pin = a->ob_digit, rem; - /* Get a scratch area for repeated division. */ - scratch = _PyLong_New(size); +#if PyLong_SHIFT == 30 + /* XXX the magic values 291 and 7 would probably + be better off as defines in longintrepr.h */ + scratch = _PyLong_New(size_a + (size_a+290)/291); +#elif PyLong_SHIFT == 15 + scratch = _PyLong_New(size_a + (size_a+6)/7); +#else +#error "Unknown value for PyLong_SHIFT" +#endif if (scratch == NULL) { Py_DECREF(str); return NULL; } + pout = scratch->ob_digit; - /* 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; - }) + /* convert: base 2 in pin -> base 10 in pout */ + for (size=0, i=size_a; --i >= 0; ) { + digit hi = pin[i]; + for (j = 0; j < size; j++) { + twodigits comb = (twodigits)pout[j] << + PyLong_SHIFT | hi; + hi = comb / PyLong_POWBASE_BASE_10; + pout[j] = (digit)(comb - (twodigits)hi * + PyLong_POWBASE_BASE_10); + } + while (hi != 0) { + digit q = hi / PyLong_POWBASE_BASE_10; + pout[size++] = hi - q*PyLong_POWBASE_BASE_10; + hi = q; + } + } - /* 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); + /* low digits give PyLong_POWER_BASE_10 decimal digits each */ + for (i=0; i < size-1; i++) { + rem = pout[i]; + for (j = 0; j < PyLong_POWER_BASE_10; j++) { + digit q = rem/10; + *--p = '0' + (rem-10*q); + rem = q; + } + } + /* top digit */ + rem = pout[i]; + while (rem != 0) { + digit q = rem/10; + *--p = '0' + (rem-10*q); + rem = q; + } + Py_DECREF(scratch); } - - if (base == 2) { + if (base == 10) { + /* No prefix required */ + } + else if (base == 2) { *--p = 'b'; *--p = '0'; } else if (base == 8) { - if (newstyle) { + if (newstyle) { *--p = 'o'; *--p = '0'; } @@ -1510,7 +1514,7 @@ *--p = 'x'; *--p = '0'; } - else if (base != 10) { + else { *--p = '#'; *--p = '0' + base%10; if (base > 10)