* mpi-patches/add-mp-hash (mp_hash): Fixed use of uninitialized

variable on platforms where the MP digit is smaller than a long integer.
(Not anything TXR is known to run on). Changed algorithm to take the
first and last digit and add them together, rather than just taking the
last digit. The last digit will be zeros for numbers that contain 2 as a
factor with a large enough multiplicity.

* mpi-patches/add-mpi-toradix-with-case: Refreshed.

* mpi-patches/bit-search-optimizations: Likewise.

* mpi-patches/faster-square-root: Likewise.

* mpi-patches/fix-bad-shifts: Likewise.

* mpi-patches/fix-mult-bug: Likewise.

6 files changed, 54 insertions, 41 deletions

diff --git a/mpi-patches/add-mp-hash b/mpi-patches/add-mp-hash
index f2ae5f5f..63b137e9 100644
--- a/mpi-patches/add-mp-hash
+++ b/mpi-patches/add-mp-hash
@@ -1,22 +1,35 @@
 Index: mpi-1.8.6/mpi.c
 ===================================================================
---- 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 @@
+--- mpi-1.8.6.orig/mpi.c	2012-03-04 08:51:51.607484757 -0800
++++ mpi-1.8.6/mpi.c	2012-03-04 11:49:32.456841257 -0800
+@@ -1960,6 +1960,34 @@
  
  /* }}} */
  
 +unsigned long mp_hash(mp_int *a)
 +{
-+  unsigned long hash;
-+  mp_digit d = DIGIT(a, 0);
 +#if SIZEOF_LONG > MP_DIGIT_SIZE
++  unsigned long hash;
 +  int ix;
-+  for (ix = 0; ix < SIZEOF_LONG / MP_DIGIT_SIZE && ix < USED(a); ix++) {
-+    hash = (hash << MP_DIGIT_BIT) | DIGIT(a, ix);
++
++  if (USED(a) >= 2 * SIZEOF_LONG / MP_DIGIT_SIZE) {
++    mp_digit omega = 0;
++    mp_digit alpha = 0;
++    for (ix = 0; ix < SIZEOF_LONG / MP_DIGIT_SIZE; ix++)
++	omega = (omega << MP_DIGIT_BIT) | DIGIT(a, ix);
++    for (ix = USED(a) - SIZEOF_LONG / MP_DIGIT_SIZE; ix < USED(a); ix++)
++	alpha = (alpha << MP_DIGIT_BIT) | DIGIT(a, ix);
++    hash = alpha + omega;
++  } else {
++    hash = 0;
++
++    for (ix = 0; ix < USED(a); ix++)
++	hash = (hash << MP_DIGIT_BIT) | DIGIT(a, ix);
 +  }
 +#else
-+  hash = d;
++  mp_digit omega = DIGIT(a, 0);
++  mp_digit alpha = DIGIT(a, USED(a) - 1);
++  unsigned long hash = alpha + omega;
 +#endif
 +  return SIGN(a) == MP_NEG ? ~hash : hash;
 +}
@@ -26,8 +39,8 @@ Index: mpi-1.8.6/mpi.c
  
 Index: mpi-1.8.6/mpi.h
 ===================================================================
---- 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
+--- mpi-1.8.6.orig/mpi.h	2012-03-04 08:51:51.607484757 -0800
++++ mpi-1.8.6/mpi.h	2012-03-04 11:49:32.196695007 -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 b94fdb19..8d5b1e73 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-10 12:05:35.000000000 -0800
-+++ mpi-1.8.6/mpi.c	2011-12-10 12:05:39.000000000 -0800
-@@ -2615,9 +2615,9 @@
+--- mpi-1.8.6.orig/mpi.c	2012-03-04 11:49:32.456841257 -0800
++++ mpi-1.8.6/mpi.c	2012-03-04 11:49:39.720925007 -0800
+@@ -2628,9 +2628,9 @@
  
  /* }}} */
  
@@ -14,7 +14,7 @@ Index: mpi-1.8.6/mpi.c
  {
    int  ix, pos = 0;
  
-@@ -2648,7 +2648,7 @@
+@@ -2661,7 +2661,7 @@
        }
  
        /* Generate digits, use capital letters */
@@ -23,7 +23,7 @@ Index: mpi-1.8.6/mpi.c
  
        str[pos++] = ch;
      }
-@@ -2676,10 +2676,15 @@
+@@ -2689,10 +2689,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-10 12:05:35.000000000 -0800
-+++ mpi-1.8.6/mpi.h	2011-12-10 12:05:39.000000000 -0800
+--- mpi-1.8.6.orig/mpi.h	2012-03-04 11:49:32.196695007 -0800
++++ mpi-1.8.6/mpi.h	2012-03-04 11:49:39.724927257 -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/bit-search-optimizations b/mpi-patches/bit-search-optimizations
index ccbdae79..3dfaaa52 100644
--- a/mpi-patches/bit-search-optimizations
+++ b/mpi-patches/bit-search-optimizations
@@ -1,8 +1,8 @@
 Index: mpi-1.8.6/mpi.c
 ===================================================================
---- mpi-1.8.6.orig/mpi.c	2011-12-21 15:57:17.000000000 -0800
-+++ mpi-1.8.6/mpi.c	2011-12-21 15:57:49.000000000 -0800
-@@ -2908,6 +2908,218 @@
+--- mpi-1.8.6.orig/mpi.c	2012-03-04 11:49:59.676143507 -0800
++++ mpi-1.8.6/mpi.c	2012-03-04 11:50:07.500542257 -0800
+@@ -2921,6 +2921,218 @@
  
  /* }}} */
  
@@ -221,7 +221,7 @@ Index: mpi-1.8.6/mpi.c
  /* {{{ s_mp_exch(a, b) */
  
  /* Exchange the data for a and b; (b, a) = (a, b)                         */
-@@ -3185,10 +3397,9 @@
+@@ -3198,10 +3410,9 @@
    mp_digit  t, d = 0;
  
    t = DIGIT(b, USED(b) - 1);
@@ -235,7 +235,7 @@ Index: mpi-1.8.6/mpi.c
      
    if(d != 0) {
      s_mp_mul_2d(a, d);
-@@ -3971,27 +4182,23 @@
+@@ -3984,27 +4195,23 @@
  
    d = DIGIT(v, uv - 1); /* most significant digit of v */
  
@@ -275,7 +275,7 @@ Index: mpi-1.8.6/mpi.c
  } /* end s_mp_ispow2() */
  
  /* }}} */
-@@ -4000,17 +4207,12 @@
+@@ -4013,17 +4220,12 @@
  
  int      s_mp_ispow2d(mp_digit d)
  {
diff --git a/mpi-patches/faster-square-root b/mpi-patches/faster-square-root
index a19bab03..30f3da91 100644
--- a/mpi-patches/faster-square-root
+++ b/mpi-patches/faster-square-root
@@ -1,7 +1,7 @@
 Index: mpi-1.8.6/mpi.c
 ===================================================================
---- mpi-1.8.6.orig/mpi.c	2011-12-13 15:18:37.000000000 -0800
-+++ mpi-1.8.6/mpi.c	2011-12-13 17:21:59.000000000 -0800
+--- mpi-1.8.6.orig/mpi.c	2012-03-04 11:45:43.071884757 -0800
++++ mpi-1.8.6/mpi.c	2012-03-04 11:45:43.556157007 -0800
 @@ -158,6 +158,9 @@
  mp_err   s_mp_grow(mp_int *mp, mp_size min);   /* increase allocated size */
  mp_err   s_mp_pad(mp_int *mp, mp_size min);    /* left pad with zeroes    */
@@ -130,7 +130,7 @@ Index: mpi-1.8.6/mpi.c
  
  /* }}} */
  
-@@ -2541,21 +2522,9 @@
+@@ -2554,21 +2535,9 @@
  
  int    mp_count_bits(mp_int *mp)
  {
@@ -153,7 +153,7 @@ Index: mpi-1.8.6/mpi.c
  } /* end mp_count_bits() */
  
  /* }}} */
-@@ -3119,6 +3088,27 @@
+@@ -3132,6 +3101,27 @@
    abort();
  }
  
diff --git a/mpi-patches/fix-bad-shifts b/mpi-patches/fix-bad-shifts
index f6e7c979..abe109a2 100644
--- a/mpi-patches/fix-bad-shifts
+++ b/mpi-patches/fix-bad-shifts
@@ -1,7 +1,7 @@
 Index: mpi-1.8.6/mpi.c
 ===================================================================
---- mpi-1.8.6.orig/mpi.c	2011-12-11 19:52:15.000000000 -0800
-+++ mpi-1.8.6/mpi.c	2011-12-11 19:53:09.000000000 -0800
+--- mpi-1.8.6.orig/mpi.c	2012-03-04 11:49:57.142719257 -0800
++++ mpi-1.8.6/mpi.c	2012-03-04 11:49:59.676143507 -0800
 @@ -764,7 +764,7 @@
    if((pow = s_mp_ispow2d(d)) >= 0) {
      mp_digit  mask;
@@ -11,7 +11,7 @@ Index: mpi-1.8.6/mpi.c
      rem = DIGIT(a, 0) & mask;
  
      if(q) {
-@@ -3068,7 +3068,7 @@
+@@ -3081,7 +3081,7 @@
      return;
  
    /* Flush all the bits above 2^d in its digit */
@@ -20,7 +20,7 @@ Index: mpi-1.8.6/mpi.c
    dp[ndig] &= dmask;
  
    /* Flush all digits above the one with 2^d in it */
-@@ -3101,7 +3101,7 @@
+@@ -3114,7 +3114,7 @@
    dp = DIGITS(mp); used = USED(mp);
    d %= DIGIT_BIT;
  
@@ -29,7 +29,7 @@ Index: mpi-1.8.6/mpi.c
  
    /* If the shift requires another digit, make sure we've got one to
       work with */
-@@ -3149,7 +3149,7 @@
+@@ -3162,7 +3162,7 @@
    s_mp_rshd(mp, d / DIGIT_BIT);
    d %= DIGIT_BIT;
  
@@ -38,7 +38,7 @@ Index: mpi-1.8.6/mpi.c
  
    save = 0;
    for(ix = USED(mp) - 1; ix >= 0; ix--) {
-@@ -3829,7 +3829,7 @@
+@@ -3842,7 +3842,7 @@
    if((res = s_mp_pad(a, dig + 1)) != MP_OKAY)
      return res;
    
diff --git a/mpi-patches/fix-mult-bug b/mpi-patches/fix-mult-bug
index a894eefe..a3e375df 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-10 19:43:20.000000000 -0800
-+++ mpi-1.8.6/mpi.c	2011-12-12 21:55:28.000000000 -0800
-@@ -3255,7 +3255,7 @@
+--- mpi-1.8.6.orig/mpi.c	2012-03-04 11:49:39.720925007 -0800
++++ mpi-1.8.6/mpi.c	2012-03-04 11:49:47.661389007 -0800
+@@ -3268,7 +3268,7 @@
      unless absolutely necessary.
     */
    max = USED(a);
@@ -11,7 +11,7 @@ Index: mpi-1.8.6/mpi.c
    if(CARRYOUT(w) != 0) {
      if((res = s_mp_pad(a, max + 1)) != MP_OKAY)
        return res;
-@@ -3263,7 +3263,7 @@
+@@ -3276,7 +3276,7 @@
    }
  
    for(ix = 0; ix < max; ix++) {
@@ -20,7 +20,7 @@ Index: mpi-1.8.6/mpi.c
      dp[ix] = ACCUM(w);
      k = CARRYOUT(w);
    }
-@@ -3480,7 +3480,7 @@
+@@ -3493,7 +3493,7 @@
      pa = DIGITS(a);
      for(jx = 0; jx < ua; ++jx, ++pa) {
        pt = pbt + ix + jx;
@@ -29,7 +29,7 @@ Index: mpi-1.8.6/mpi.c
        *pt = ACCUM(w);
        k = CARRYOUT(w);
      }
-@@ -3562,7 +3562,7 @@
+@@ -3575,7 +3575,7 @@
      if(*pa1 == 0)
        continue;
  
@@ -38,7 +38,7 @@ Index: mpi-1.8.6/mpi.c
  
      pbt[ix + ix] = ACCUM(w);
      k = CARRYOUT(w);
-@@ -3584,7 +3584,7 @@
+@@ -3597,7 +3597,7 @@
        pt = pbt + ix + jx;
  
        /* Compute the multiplicative step */
@@ -47,7 +47,7 @@ Index: mpi-1.8.6/mpi.c
  
        /* If w is more than half MP_WORD_MAX, the doubling will
  	 overflow, and we need to record a carry out into the next
-@@ -3628,7 +3628,7 @@
+@@ -3641,7 +3641,7 @@
       */
      kx = 1;
      while(k) {