diff options
| -rw-r--r-- | ChangeLog | 14 | ||||
| -rw-r--r-- | mpi-patches/add-mp-hash | 35 | ||||
| -rw-r--r-- | mpi-patches/add-mpi-toradix-with-case | 14 | ||||
| -rw-r--r-- | mpi-patches/fix-mult-bug | 6 |
4 files changed, 37 insertions, 32 deletions
@@ -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++) { |