long(string, base) now takes time linear in len(string) when base is a
power of 2. Enabled the tail end of test_long() in pickletester.py
because it no longer takes forever when run from test_pickle.py.
diff --git a/Lib/pickle.py b/Lib/pickle.py
index ba0e38b..4e80cca 100644
--- a/Lib/pickle.py
+++ b/Lib/pickle.py
@@ -1427,9 +1427,6 @@
binary = _binascii.unhexlify(ashex)
return binary[::-1]
-# XXX OOPS! This is still quadratic-time. While hex(n) is linear-time
-# XXX in the # of digits in n, long(s, 16) is still quadratic-time
-# XXX in len(s).
def decode_long(data):
r"""Decode a long from a two's complement little-endian binary string.
@@ -1453,7 +1450,7 @@
if nbytes == 0:
return 0L
ashex = _binascii.hexlify(data[::-1])
- n = long(ashex, 16) # quadratic time
+ n = long(ashex, 16) # quadratic time before Python 2.3; linear now
if data[-1] >= '\x80':
n -= 1L << (nbytes * 8)
return n
diff --git a/Lib/test/pickletester.py b/Lib/test/pickletester.py
index 6615307..2a1ca17 100644
--- a/Lib/test/pickletester.py
+++ b/Lib/test/pickletester.py
@@ -247,7 +247,7 @@
def test_long(self):
for proto in protocols:
- # 256 bytes is where LONG4 begins
+ # 256 bytes is where LONG4 begins.
for nbits in 1, 8, 8*254, 8*255, 8*256, 8*257:
nbase = 1L << nbits
for npos in nbase-1, nbase, nbase+1:
@@ -257,20 +257,11 @@
self.assertEqual(n, got)
# Try a monster. This is quadratic-time in protos 0 & 1, so don't
# bother with those.
- # XXX Damn. pickle.py is still quadratic-time here, due to
- # XXX long(string, 16). cPickle runs this in an eyeblink, but I
- # XXX gave up waiting for pickle.py to get beyond "loading". Giving
- # XXX up for now.
- return
- print "building long"
nbase = long("deadbeeffeedface", 16)
nbase += nbase << 1000000
for n in nbase, -nbase:
- print "dumping"
p = self.dumps(n, 2)
- print "loading"
got = self.loads(p)
- print "checking"
self.assertEqual(n, got)
def test_reduce(self):
diff --git a/Misc/NEWS b/Misc/NEWS
index 5d3f57c..e9f105b 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -12,6 +12,9 @@
Core and builtins
-----------------
+- long(string, base) takes time linear in len(string) when base is a power
+ of 2 now. It used to take time quadratic in len(string).
+
- filter returns now Unicode results for Unicode arguments.
- raw_input can now return Unicode objects.
diff --git a/Objects/longobject.c b/Objects/longobject.c
index 9d7243f..7ca8244 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -1090,6 +1090,95 @@
return (PyObject *)str;
}
+/* *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;
+ int 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;
+ for (;;) {
+ int k = -1;
+ char ch = *p;
+
+ if (ch <= '9')
+ k = ch - '0';
+ else if (ch >= 'a')
+ k = ch - 'a' + 10;
+ else if (ch >= 'A')
+ k = ch - 'A' + 10;
+ if (k < 0 || k >= base)
+ break;
+ n += bits_per_char;
+ if (n < 0) {
+ PyErr_SetString(PyExc_ValueError,
+ "long string too large to convert");
+ return NULL;
+ }
+ ++p;
+ }
+ *str = p;
+ /* n <- # of Python digits needed, = ceiling(n/SHIFT). */
+ n = (n + SHIFT - 1) / 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) {
+ unsigned char ch = (unsigned char)*p;
+ digit k;
+
+ if (ch <= '9')
+ k = ch - '0';
+ else if (ch >= 'a')
+ k = ch - 'a' + 10;
+ else {
+ assert(ch >= 'A');
+ k = ch - 'A' + 10;
+ }
+ assert(k >= 0 && k <= base);
+ accum |= k << bits_in_accum;
+ bits_in_accum += bits_per_char;
+ if (bits_in_accum >= SHIFT) {
+ *pdigit++ = (digit)(accum & MASK);
+ assert(pdigit - z->ob_digit <= 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 <= n);
+ }
+ while (pdigit - z->ob_digit < n)
+ *pdigit++ = 0;
+ return long_normalize(z);
+}
+
PyObject *
PyLong_FromString(char *str, char **pend, int base)
{
@@ -1122,23 +1211,27 @@
}
if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
str += 2;
- z = _PyLong_New(0);
start = str;
- for ( ; z != NULL; ++str) {
- int k = -1;
- PyLongObject *temp;
+ if ((base & (base - 1)) == 0)
+ z = long_from_binary_base(&str, base);
+ else {
+ z = _PyLong_New(0);
+ for ( ; z != NULL; ++str) {
+ int k = -1;
+ PyLongObject *temp;
- if (*str <= '9')
- k = *str - '0';
- else if (*str >= 'a')
- k = *str - 'a' + 10;
- else if (*str >= 'A')
- k = *str - 'A' + 10;
- if (k < 0 || k >= base)
- break;
- temp = muladd1(z, (digit)base, (digit)k);
- Py_DECREF(z);
- z = temp;
+ if (*str <= '9')
+ k = *str - '0';
+ else if (*str >= 'a')
+ k = *str - 'a' + 10;
+ else if (*str >= 'A')
+ k = *str - 'A' + 10;
+ if (k < 0 || k >= base)
+ break;
+ temp = muladd1(z, (digit)base, (digit)k);
+ Py_DECREF(z);
+ z = temp;
+ }
}
if (z == NULL)
return NULL;