Commits

Philip Jenvey committed 34a0157

modernize int's hash: it's now x modulo the new HASH_MODULUS.
an exact port of CPython's impl is tricky for 64bit because it assumes
HASH_BITS (61) >= rbigint's SHIFT (63), which isn't true on PyPy. so our
algorithm differs and we calculate the hash via the 'wide' type like many
rbigint methods

Comments (0)

Files changed (5)

pypy/module/sys/system.py

 from rpython.rlib import rfloat, rbigint
 from rpython.rtyper.lltypesystem import rffi, lltype
 from pypy.objspace.std.floatobject import HASH_INF, HASH_MODULUS, HASH_NAN
+from pypy.objspace.std.longobject import HASH_MODULUS
 from pypy.objspace.std.complexobject import HASH_IMAG
 
 

pypy/objspace/std/floatobject.py

 import operator
-import sys
 from pypy.interpreter.error import OperationError
 from pypy.objspace.std import model, newformat
 from pypy.objspace.std.floattype import float_typedef, W_AbstractFloatObject
 from pypy.objspace.std.model import registerimplementation, W_Object
 from pypy.objspace.std.register_all import register_all
 from pypy.objspace.std.noneobject import W_NoneObject
-from pypy.objspace.std.longobject import W_LongObject, newlong_from_float
+from pypy.objspace.std.longobject import (
+    HASH_BITS, HASH_MODULUS, W_LongObject, newlong_from_float)
 from rpython.rlib.rarithmetic import (
     LONG_BIT, intmask, ovfcheck_float_to_int, r_uint)
 from rpython.rlib.rfloat import (
 
 HASH_INF  = 314159
 HASH_NAN  = 0
-HASH_BITS = 61 if sys.maxsize > 2 ** 31 - 1 else 31
-HASH_MODULUS = (1 << HASH_BITS) - 1
 
 class W_FloatObject(W_AbstractFloatObject):
     """This is a implementation of the app-level 'float' type.

pypy/objspace/std/longobject.py

 from pypy.objspace.std.multimethod import FailedToImplementArgs
 from pypy.objspace.std.intobject import W_IntObject
 from pypy.objspace.std.noneobject import W_NoneObject
-from rpython.rlib.rbigint import rbigint
+from rpython.rlib.rarithmetic import intmask
+from rpython.rlib.rbigint import SHIFT, _widen_digit, rbigint
 from pypy.objspace.std.longtype import long_typedef, W_AbstractLongObject
 
+HASH_BITS = 61 if sys.maxsize > 2 ** 31 - 1 else 31
+HASH_MODULUS = 2 ** HASH_BITS - 1
 
 class W_LongObject(W_AbstractLongObject):
     """This is a wrapper of rbigint."""
 
 
 def hash__Long(space, w_value):
-    return space.wrap(w_value.num.hash())
+    return space.wrap(_hash_long(space, w_value.num))
+
+def _hash_long(space, v):
+    i = v.numdigits() - 1
+    if i == -1:
+        return 0
+
+    # compute v % HASH_MODULUS
+    x = _widen_digit(0)
+    while i >= 0:
+        x = (x << SHIFT) + v.widedigit(i)
+        # efficient x % HASH_MODULUS: as HASH_MODULUS is a Mersenne
+        # prime
+        x = (x & HASH_MODULUS) + (x >> HASH_BITS)
+        while x >= HASH_MODULUS:
+            x -= HASH_MODULUS
+        i -= 1
+    x = intmask(intmask(x) * v.sign)
+    return -2 if x == -1 else x
+
 
 def add__Long_Long(space, w_long1, w_long2):
     return W_LongObject(w_long1.num.add(w_long2.num))

pypy/objspace/std/test/test_floatobject.py

         assert 42.0 == float(42)
 
     def test_float_hash(self):
-        # these are taken from standard Python, which produces
-        # the same but for -1.
         import math
         import sys
 

pypy/objspace/std/test/test_longobject.py

         assert x ^ 0x555555555 == 0x5FFFFFFFF
 
     def test_hash(self):
-        # ints have the same hash as equal longs
-        for i in range(-4, 14):
-            assert hash(i) == hash(int(i))
-        # might check too much -- it's ok to change the hashing algorithm
-        assert hash(123456789) == 123456789
-        assert hash(1234567890123456789) in (
-            -1895067127,            # with 32-bit platforms
-            1234567890123456789)    # with 64-bit platforms
+        import sys
+        modulus = sys.hash_info.modulus
+        for x in (list(range(200)) +
+                  [1234567890123456789, 18446743523953737727,
+                   987685321987685321987685321987685321987685321]):
+            y = x % modulus
+            assert hash(x) == hash(y)
+            assert hash(-x) == hash(-y)
+        assert hash(modulus - 1) == modulus - 1
+        assert hash(modulus) == 0
+        assert hash(modulus + 1) == 1
+
+        assert hash(-1) == -2
+        value = -(modulus + 1)
+        assert hash(value) == -2
+        assert hash(value * 2 + 1) == -2
+        assert hash(value * 4 + 3) == -2
 
     def test_math_log(self):
         import math