From 3490dd06c52d5aa7c258f03025a05064837ce1c6 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Sun, 4 Mar 2012 11:55:19 -0800 Subject: * 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. --- ChangeLog | 19 +++++++++++++++++++ mpi-patches/add-mp-hash | 33 +++++++++++++++++++++++---------- mpi-patches/add-mpi-toradix-with-case | 14 +++++++------- mpi-patches/bit-search-optimizations | 12 ++++++------ mpi-patches/faster-square-root | 8 ++++---- mpi-patches/fix-bad-shifts | 12 ++++++------ mpi-patches/fix-mult-bug | 16 ++++++++-------- 7 files changed, 73 insertions(+), 41 deletions(-) diff --git a/ChangeLog b/ChangeLog index 91b45196..f26c4ce5 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,22 @@ +2012-03-04 Kaz Kylheku + + * 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. + 2012-03-04 Kaz Kylheku Version 60 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) { -- cgit v1.2.3