Author: Armin Rigo <ar...@tunes.org>
Branch:
Changeset: r67929:837dea310b4d
Date: 2013-11-10 14:48 +0100
http://bitbucket.org/pypy/pypy/changeset/837dea310b4d/
Log: Fix the bogus complexity of marshal dumping "long" objects
diff --git a/pypy/module/marshal/test/test_marshalimpl.py
b/pypy/module/marshal/test/test_marshalimpl.py
--- a/pypy/module/marshal/test/test_marshalimpl.py
+++ b/pypy/module/marshal/test/test_marshalimpl.py
@@ -56,3 +56,29 @@
class AppTestMarshalSmallLong(AppTestMarshalMore):
spaceconfig = dict(usemodules=('array',),
**{"objspace.std.withsmalllong": True})
+
+
+def test_long_more(space):
+ import marshal, struct
+
+ class FakeM:
+ def __init__(self):
+ self.seen = []
+ def start(self, code):
+ self.seen.append(code)
+ def put_int(self, value):
+ self.seen.append(struct.pack("i", value))
+ def put_short(self, value):
+ self.seen.append(struct.pack("h", value))
+
+ def _marshal_check(x):
+ expected = marshal.dumps(long(x))
+ w_obj = space.wraplong(x)
+ m = FakeM()
+ space.marshal_w(w_obj, m)
+ assert ''.join(m.seen) == expected
+
+ for sign in [1L, -1L]:
+ for i in range(100):
+ _marshal_check(sign * ((1L << i) - 1L))
+ _marshal_check(sign * (1L << i))
diff --git a/pypy/objspace/std/marshal_impl.py
b/pypy/objspace/std/marshal_impl.py
--- a/pypy/objspace/std/marshal_impl.py
+++ b/pypy/objspace/std/marshal_impl.py
@@ -207,20 +207,20 @@
def marshal_w__Long(space, w_long, m):
from rpython.rlib.rbigint import rbigint
+ from rpython.rlib.rarithmetic import r_ulonglong
m.start(TYPE_LONG)
SHIFT = 15
MASK = (1 << SHIFT) - 1
num = w_long.num
sign = num.sign
num = num.abs()
- ints = []
- while num.tobool():
- next = intmask(num.uintmask() & MASK)
- ints.append(next)
- num = num.rshift(SHIFT)
- m.put_int(len(ints) * sign)
- for i in ints:
- m.put_short(i)
+ total_length = (num.bit_length() + (SHIFT - 1)) / SHIFT
+ m.put_int(total_length * sign)
+ bigshiftcount = r_ulonglong(0)
+ for i in range(total_length):
+ next = num.abs_rshift_and_mask(bigshiftcount, MASK)
+ m.put_short(next)
+ bigshiftcount += SHIFT
def unmarshal_Long(space, u, tc):
from rpython.rlib.rbigint import rbigint
_______________________________________________
pypy-commit mailing list
pypy-commit@python.org
https://mail.python.org/mailman/listinfo/pypy-commit
