* 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.

4 files changed, 37 insertions, 32 deletions

diff --git a/ChangeLog b/ChangeLog
index 64f54f1c..96acf6dd 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,19 @@
 2011-12-10  Kaz Kylheku  <kaz@kylheku.com>
 
+	* 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.
+
+2011-12-10  Kaz Kylheku  <kaz@kylheku.com>
+
 	* lib.c (mulv): Recognize cases to eliminate a wasteful mul call
 	with an initial element of 1.
 
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);
diff --git a/mpi-patches/add-mpi-toradix-with-case b/mpi-patches/add-mpi-toradix-with-case
index 6fe9c191..b94fdb19 100644
--- a/mpi-patches/add-mpi-toradix-with-case
+++ b/mpi-patches/add-mpi-toradix-with-case
@@ -1,8 +1,8 @@
 Index: mpi-1.8.6/mpi.c
 ===================================================================
---- mpi-1.8.6.orig/mpi.c	2011-12-09 19:16:58.000000000 -0800
-+++ mpi-1.8.6/mpi.c	2011-12-09 19:19:23.000000000 -0800
-@@ -2624,9 +2624,9 @@
+--- mpi-1.8.6.orig/mpi.c	2011-12-10 12:05:35.000000000 -0800
++++ mpi-1.8.6/mpi.c	2011-12-10 12:05:39.000000000 -0800
+@@ -2615,9 +2615,9 @@
  
  /* }}} */
  
@@ -14,7 +14,7 @@ Index: mpi-1.8.6/mpi.c
  {
    int  ix, pos = 0;
  
-@@ -2657,7 +2657,7 @@
+@@ -2648,7 +2648,7 @@
        }
  
        /* Generate digits, use capital letters */
@@ -23,7 +23,7 @@ Index: mpi-1.8.6/mpi.c
  
        str[pos++] = ch;
      }
-@@ -2685,10 +2685,15 @@
+@@ -2676,10 +2676,15 @@
  
    return MP_OKAY;
  
@@ -42,8 +42,8 @@ Index: mpi-1.8.6/mpi.c
  int    mp_char2value(char ch, int r)
 Index: mpi-1.8.6/mpi.h
 ===================================================================
---- mpi-1.8.6.orig/mpi.h	2011-12-09 19:16:58.000000000 -0800
-+++ mpi-1.8.6/mpi.h	2011-12-09 19:28:38.000000000 -0800
+--- mpi-1.8.6.orig/mpi.h	2011-12-10 12:05:35.000000000 -0800
++++ mpi-1.8.6/mpi.h	2011-12-10 12:05:39.000000000 -0800
 @@ -213,6 +213,7 @@
  int    mp_radix_size(mp_int *mp, int radix);
  int    mp_value_radix_size(int num, int qty, int radix);
diff --git a/mpi-patches/fix-mult-bug b/mpi-patches/fix-mult-bug
index 691f3334..e86d0363 100644
--- a/mpi-patches/fix-mult-bug
+++ b/mpi-patches/fix-mult-bug
@@ -1,8 +1,8 @@
 Index: mpi-1.8.6/mpi.c
 ===================================================================
---- mpi-1.8.6.orig/mpi.c	2011-12-09 21:11:31.000000000 -0800
-+++ mpi-1.8.6/mpi.c	2011-12-09 21:12:09.000000000 -0800
-@@ -3272,7 +3272,7 @@
+--- mpi-1.8.6.orig/mpi.c	2011-12-10 12:05:39.000000000 -0800
++++ mpi-1.8.6/mpi.c	2011-12-10 12:05:43.000000000 -0800
+@@ -3263,7 +3263,7 @@
    }
  
    for(ix = 0; ix < max; ix++) {