summaryrefslogtreecommitdiffstats
path: root/Objects/longobject.c
diff options
context:
space:
mode:
authorMark Dickinson <dickinsm@gmail.com>2009-09-17 19:39:12 (GMT)
committerMark Dickinson <dickinsm@gmail.com>2009-09-17 19:39:12 (GMT)
commit8accd6b38efb1246fbf4d0378f3ca46c1d0780b8 (patch)
tree17f3779b0b1bfa18a9d035e11d8873fe842bd314 /Objects/longobject.c
parent2e72b0d603b81a38ecbcb9c257aa3ba202ae7b76 (diff)
downloadcpython-8accd6b38efb1246fbf4d0378f3ca46c1d0780b8.zip
cpython-8accd6b38efb1246fbf4d0378f3ca46c1d0780b8.tar.gz
cpython-8accd6b38efb1246fbf4d0378f3ca46c1d0780b8.tar.bz2
Revert accidental changes to Objects/longobject.c
Diffstat (limited to 'Objects/longobject.c')
-rw-r--r--Objects/longobject.c148
1 files changed, 104 insertions, 44 deletions
diff --git a/Objects/longobject.c b/Objects/longobject.c
index 814ef64..9f414ca 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -1775,9 +1775,9 @@ _PyLong_Format(PyObject *aa, int base)
Py_ssize_t i, sz;
Py_ssize_t size_a;
Py_UNICODE *p;
- int bits, negative;
+ int bits;
+ char sign = '\0';
- assert(base == 2 || base == 8 || base == 10 || base == 16);
if (base == 10)
return long_to_decimal_string((PyObject *)a);
@@ -1785,34 +1785,23 @@ _PyLong_Format(PyObject *aa, int base)
PyErr_BadInternalCall();
return NULL;
}
+ assert(base >= 2 && base <= 36);
size_a = ABS(Py_SIZE(a));
- negative = Py_SIZE(a) < 0;
/* Compute a rough upper bound for the length of the string */
- switch (base) {
- case 2:
- bits = 1;
- break;
- case 8:
- bits = 3;
- break;
- case 16:
- bits = 4;
- break;
- default:
- assert(0); /* never get here */
+ i = base;
+ bits = 0;
+ while (i > 1) {
+ ++bits;
+ i >>= 1;
}
-
- /* length of string required: +1 for negative sign, +2 for prefix */
i = 5;
/* ensure we don't get signed overflow in sz calculation */
- if (size_a > (PY_SSIZE_T_MAX - 4) / PyLong_SHIFT) {
+ if (size_a > (PY_SSIZE_T_MAX - i) / PyLong_SHIFT) {
PyErr_SetString(PyExc_OverflowError,
"int is too large to format");
return NULL;
}
- sz = 3 + negative + (size_a * PyLong_SHIFT - 1) / bits;
-
sz = i + 1 + (size_a * PyLong_SHIFT - 1) / bits;
assert(sz >= 0);
str = PyUnicode_FromUnicode(NULL, sz);
@@ -1820,41 +1809,112 @@ _PyLong_Format(PyObject *aa, int base)
return NULL;
p = PyUnicode_AS_UNICODE(str) + sz;
*p = '\0';
+ if (Py_SIZE(a) < 0)
+ sign = '-';
if (Py_SIZE(a) == 0) {
*--p = '0';
}
- assert((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;
+ 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 += PyLong_SHIFT;
+ assert(accumbits >= basebits);
+ do {
+ char cdigit = (char)(accum & (base - 1));
+ cdigit += (cdigit < 10) ? '0' : 'a'-10;
+ assert(p > PyUnicode_AS_UNICODE(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 (;;) {
+ 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);
+ if (scratch == NULL) {
+ Py_DECREF(str);
+ return NULL;
+ }
- for (i = 0; i < size_a; ++i) {
- accum |= (twodigits)a->ob_digit[i] << accumbits;
- accumbits += PyLong_SHIFT;
- assert(accumbits >= basebits);
+ /* Repeatedly divide by powbase. */
do {
- char cdigit = (char)(accum & (base - 1));
- cdigit += (cdigit < 10) ? '0' : 'a'-10;
- assert(p > PyUnicode_AS_UNICODE(str));
- *--p = cdigit;
- accumbits -= basebits;
- accum >>= basebits;
- } while (i < size_a-1 ? accumbits >= basebits :
- accum > 0);
+ 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 > PyUnicode_AS_UNICODE(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 == 16)
+ if (base == 16) {
*--p = 'x';
- else if (base == 8)
+ *--p = '0';
+ }
+ else if (base == 8) {
*--p = 'o';
- else /* base == 2 */
+ *--p = '0';
+ }
+ else if (base == 2) {
*--p = 'b';
- *--p = '0';
+ *--p = '0';
+ }
+ else if (base != 10) {
+ *--p = '#';
+ *--p = '0' + base%10;
+ if (base > 10)
+ *--p = '0' + base/10;
+ }
if (sign)
*--p = sign;
if (p != PyUnicode_AS_UNICODE(str)) {