Compatible numeric hashes

Objects/longobject.c

 /* Long (arbitrary precision) integer object implementation */
 
 /* XXX The functional organization of this file is terrible */
 
 #include "Python.h"
 #include "longintrepr.h"
 #include "structseq.h"
 
 #include <float.h>
 #include <ctype.h>
@@ skipping 2554 matching lines @@
         case -1: return v->ob_digit[0]==1 ? -2 : -(sdigit)v->ob_digit[0];
         case 0: return 0;
         case 1: return v->ob_digit[0];
         }
         sign = 1;
         x = 0;
         if (i < 0) {
                 sign = -1;
                 i = -(i);
         }
-        /* The following loop produces a C unsigned long x such that x is
-           congruent to the absolute value of v modulo ULONG_MAX.  The
-           resulting x is nonzero if and only if v is. */
         while (--i >= 0) {
-                /* Force a native long #-bits (32 or 64) circular shift */
-                x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);
+                /* Rotate bottom 31 bits left by PyLong_SHIFT bits; in effect,
+                   this multiplies by 2**PyLong_SHIFT modulo 2**31 - 1. */

[GvR, 2010/03/21 17:04:48]

Can't say I understand all this. I guess my number theory is lacking; I don't
get how you can compute modulo a prime by using a shift. ;-(

[dickinsm, 2010/03/23 11:56:56]

I'll add some explanatory comments. (That 2**31 - 1 needs to be changed to
_PyHASH_MASK, too.)  The idea's something like the following:  suppose 0 <= x <
2**31;  you want to multiply x by 2**15 and then reduce the result modulo
2**31-1.  Let y be the portion of x that's shifted out of the top of the
original 31 bits, so that x * 2**15 = y * 2**31 + z for some z.  Then since
2**31 reduces to 1 modulo 2**31-1, y*2**31 reduces to y.  So x*2**15 reduces to
y + z.  IOW, you just take the 15 bits that were shifted out of the top
(y*2**31) and add them back in at the bottom (as y), so you end up with a
rotation.

+                x = ((x << PyLong_SHIFT) & _PyHASH_MASK) |
+                        (x >> (_PyHASH_BITS - PyLong_SHIFT));
                 x += v->ob_digit[i];
                 /* If the addition above overflowed we compensate by
                    incrementing.  This preserves the value modulo

[GvR, 2010/03/21 17:04:48]

incrementing? This comment seems outdated now.

[dickinsm, 2010/03/23 11:56:56]

Agreed.  I'll remove it.

                    ULONG_MAX. */
-                if (x < v->ob_digit[i])
-                        x++;
+                if (x > _PyHASH_MASK)
+                        x -= _PyHASH_MASK;
         }
         x = x * sign;
         if (x == (unsigned long)-1)
                 x = (unsigned long)-2;
         return (long)x;
 }
 
 
 /* Add the absolute values of two long integers. */
 
@@ skipping 2214 matching lines @@
            reinitializations will fail. */
 #if NSMALLNEGINTS + NSMALLPOSINTS > 0
         int i;
         PyLongObject *v = small_ints;
         for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) {
                 _Py_DEC_REFTOTAL;
                 _Py_ForgetReference((PyObject*)v);
         }
 #endif
 }