diff options
| author | Kaz Kylheku <kaz@kylheku.com> | 2011-12-10 12:09:27 -0800 |
|---|---|---|
| committer | Kaz Kylheku <kaz@kylheku.com> | 2011-12-10 12:09:27 -0800 |
| commit | 64eb78436c46c1c6eecba1093a9072ff829209c4 (patch) | |
| tree | 1f9cb01221dab25bc633f9ea6d7c592d429d558d /mpi-patches/add-mp-hash | |
| parent | 17928334e0b80cf009df2a5838d6778fe23cf64f (diff) | |
| download | txr-64eb78436c46c1c6eecba1093a9072ff829209c4.tar.gz txr-64eb78436c46c1c6eecba1093a9072ff829209c4.tar.bz2 txr-64eb78436c46c1c6eecba1093a9072ff829209c4.zip | |
* mpi-patches/add-mp-hash: Rewrote mp_hash to only hash enough
low-order bit material from the bignum to fill an unsigned long.
We don't need to walk the entire bignum. If the low order
digit of the bignum is at least as large as an unsigned long,
we just take that as the hash, otherwise we take enough of the
digits to fill an unsigned long. For negative numbers, we just
invert the bits of the hash.
* mpi-patches/add-mpi-toradix-with-case: Refreshed.
* mpi-patches/fix-mult-bug: Refreshed.
Diffstat (limited to 'mpi-patches/add-mp-hash')
| -rw-r--r-- | mpi-patches/add-mp-hash | 35 |
1 files changed, 13 insertions, 22 deletions
diff --git a/mpi-patches/add-mp-hash b/mpi-patches/add-mp-hash index 8a2cd585..f2ae5f5f 100644 --- a/mpi-patches/add-mp-hash +++ b/mpi-patches/add-mp-hash @@ -1,33 +1,24 @@ Index: mpi-1.8.6/mpi.c =================================================================== ---- mpi-1.8.6.orig/mpi.c 2011-12-09 14:10:41.000000000 -0800 -+++ mpi-1.8.6/mpi.c 2011-12-09 14:26:02.000000000 -0800 -@@ -1960,6 +1960,30 @@ +--- mpi-1.8.6.orig/mpi.c 2011-12-10 09:13:23.000000000 -0800 ++++ mpi-1.8.6/mpi.c 2011-12-10 12:03:30.000000000 -0800 +@@ -1960,6 +1960,21 @@ /* }}} */ +unsigned long mp_hash(mp_int *a) +{ -+ unsigned long hash = 0; ++ unsigned long hash; ++ mp_digit d = DIGIT(a, 0); ++#if SIZEOF_LONG > MP_DIGIT_SIZE + int ix; -+ for (ix = 0; ix < USED(a); ix++) { -+ mp_digit d = DIGIT(a, ix); -+#if SIZEOF_LONG < MP_DIGIT_SIZE -+ int j; -+ for (j = 0; j < MP_DIGIT_SIZE / SIZEOF_LONG; j++) { -+ hash ^= d; -+ d >> (SIZEOF_LONG * CHAR_BIT); -+ } -+#elif SIZEOF_LONG == MP_DIGIT_SIZE -+ hash ^= d; ++ for (ix = 0; ix < SIZEOF_LONG / MP_DIGIT_SIZE && ix < USED(a); ix++) { ++ hash = (hash << MP_DIGIT_BIT) | DIGIT(a, ix); ++ } +#else -+ hash <<= MP_DIGIT_BITS; -+ hash ^= d; ++ hash = d; +#endif -+ } -+ if (SIGN(a) == MP_NEG) -+ hash = (hash << 16 | hash >> (SIZEOF_LONG * CHAR_BIT - 16)); -+ return hash; ++ return SIGN(a) == MP_NEG ? ~hash : hash; +} + /*------------------------------------------------------------------------*/ @@ -35,8 +26,8 @@ Index: mpi-1.8.6/mpi.c Index: mpi-1.8.6/mpi.h =================================================================== ---- mpi-1.8.6.orig/mpi.h 2011-12-09 14:10:41.000000000 -0800 -+++ mpi-1.8.6/mpi.h 2011-12-09 14:10:41.000000000 -0800 +--- mpi-1.8.6.orig/mpi.h 2011-12-10 09:13:23.000000000 -0800 ++++ mpi-1.8.6/mpi.h 2011-12-10 12:03:23.000000000 -0800 @@ -165,6 +165,8 @@ int mp_isodd(mp_int *a); int mp_iseven(mp_int *a); |