diff options
| author | Kaz Kylheku <kaz@kylheku.com> | 2012-03-04 11:55:19 -0800 |
|---|---|---|
| committer | Kaz Kylheku <kaz@kylheku.com> | 2012-03-04 11:55:19 -0800 |
| commit | 3490dd06c52d5aa7c258f03025a05064837ce1c6 (patch) | |
| tree | 23f4ef5380a7863f1ef290c9c309af4529689a0f /mpi-patches/add-mp-hash | |
| parent | f75994545cb88c6625e4122afa61fbbe1adeb081 (diff) | |
| download | txr-3490dd06c52d5aa7c258f03025a05064837ce1c6.tar.gz txr-3490dd06c52d5aa7c258f03025a05064837ce1c6.tar.bz2 txr-3490dd06c52d5aa7c258f03025a05064837ce1c6.zip | |
* 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.
Diffstat (limited to 'mpi-patches/add-mp-hash')
| -rw-r--r-- | mpi-patches/add-mp-hash | 33 |
1 files changed, 23 insertions, 10 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); |