Index: Include/longintrepr.h =================================================================== --- Include/longintrepr.h (revision 74738) +++ 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 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 10000 /* 10 ** POWER_BASE */ #else #error "PYLONG_BITS_IN_DIGIT should be 15 or 30" #endif Index: Objects/intobject.c =================================================================== --- Objects/intobject.c (revision 74738) +++ 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 74738) +++ Objects/longobject.c (working copy) @@ -1361,6 +1361,19 @@ return long_normalize(z); } +static const char +_decimal_digit_table[] = \ + "00010203040506070809" \ + "10111213141516171819" \ + "20212223242526272829" \ + "30313233343536373839" \ + "40414243444546474849" \ + "50515253545556575859" \ + "60616263646566676869" \ + "70717273747576777879" \ + "80818283848586878889" \ + "90919293949596979899"; + /* Convert the long to a string object with given base, appending a base prefix of 0[box] if base is 2, 8 or 16. Add a trailing "L" if addL is non-zero. @@ -1381,7 +1394,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 */ @@ -1436,23 +1449,12 @@ 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. */ + else if (base == 10) { + /* 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; + digit *pout, *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 (;;) { - twodigits newpow = powbase * (twodigits)base; - if (newpow >> PyLong_SHIFT) /* doesn't fit in a digit */ - break; - powbase = (digit)newpow; - ++power; - } /* Get a scratch area for repeated division. */ scratch = _PyLong_New(size); @@ -1460,12 +1462,23 @@ 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); + int ntostore = PyLong_POWER_BASE_10; + digit rem; + const char * t; + + rem = 0; + for (i = size; --i >= 0; ) { + digit hi; + twodigits comb; + comb = ((twodigits)rem << PyLong_SHIFT) | pin[i]; + pout[i] = hi = (digit)(comb / PyLong_POWBASE_BASE_10); + rem = (digit)(comb - (twodigits)hi * PyLong_POWBASE_BASE_10); + } + pin = scratch->ob_digit; /* no need to use a again */ if (pin[size - 1] == 0) --size; @@ -1476,24 +1489,38 @@ }) /* 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; + + /* Convert two digits at a time. */ + while (rem > 99) { + const digit nextrem = rem / 100; + + t = &_decimal_digit_table[(rem - nextrem * 100) << 1]; rem = nextrem; + *--p = t[1]; + *--p = t[0]; + ntostore -= 2; + } + /* Convert remaining 1 or 2 digits. */ + t = &_decimal_digit_table[rem << 1]; + *--p = t[1]; + --ntostore; + + if (rem > 9) { + *--p = t[0]; --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)); + } + /* Add any required leading zeros. */ + while ( ntostore && size ) { + *--p = '0'; + --ntostore; + } } while (size != 0); Py_DECREF(scratch); } - - if (base == 2) { + if (base == 10) { + /* No prefix required */ + } + else if (base == 2) { *--p = 'b'; *--p = '0'; } @@ -1510,7 +1537,7 @@ *--p = 'x'; *--p = '0'; } - else if (base != 10) { + else { *--p = '#'; *--p = '0' + base%10; if (base > 10)