diff options
| author | Kaz Kylheku <kaz@kylheku.com> | 2016-01-18 06:27:52 -0800 |
|---|---|---|
| committer | Kaz Kylheku <kaz@kylheku.com> | 2016-01-18 06:27:52 -0800 |
| commit | 4a9d763799c3f0b3c17182b44e8497e174547120 (patch) | |
| tree | fbf68b87168a68846c94e35a3941b0ab815ef52e | |
| parent | cc8f11bf43842e38f0a515b8070f4a7afe9a716d (diff) | |
| download | txr-4a9d763799c3f0b3c17182b44e8497e174547120.tar.gz txr-4a9d763799c3f0b3c17182b44e8497e174547120.tar.bz2 txr-4a9d763799c3f0b3c17182b44e8497e174547120.zip | |
random: wrong mask width for power-of-two moduli.
This mistake causes wasteful behavior for power-of-two
moduli in the random function, in both the bignum and
fixnum cases. For instance, the modulus 16 is taken
to be 17 bits wide. But we really want the width 16:
the number of bits needed for values in the range [0, 16).
The result isn't wrong, but the loop generates 17-bit
random numbers, and then throws away those which equal
or exceed the modulus, which is wasteful.
* mpi/mpi.c (mp_is_pow_two): New function.
* mpi/mpi.h (mp_is_pow_two): Declared.
* rand.c (random): In bignum case, after counting
bits in the modulus, subtract 1 if the modulus is a power
of two. In the fixnum case, subtract 1 from the modulus
and then count the bits in the reduced value.
* tests/013/maze.expected: regenerate due to different
prng behavior.
| -rw-r--r-- | mpi/mpi.c | 5 | ||||
| -rw-r--r-- | mpi/mpi.h | 1 | ||||
| -rw-r--r-- | rand.c | 4 | ||||
| -rw-r--r-- | tests/013/maze.expected | 118 |
4 files changed, 67 insertions, 61 deletions
@@ -2998,6 +2998,11 @@ int mp_count_bits(mp_int *mp) /* }}} */ +int mp_is_pow_two(mp_int *mp) +{ + return s_mp_ispow2(mp) >= 0; +} + /* {{{ mp_read_radix(mp, str, radix) */ /* @@ -223,6 +223,7 @@ int mp_unsigned_bin_size(mp_int *mp); mp_err mp_to_unsigned_bin(mp_int *mp, unsigned char *str); int mp_count_bits(mp_int *mp); +int mp_is_pow_two(mp_int *mp); #if MP_COMPAT_MACROS #define mp_read_raw(mp, str, len) mp_read_signed_bin((mp), (str), (len)) @@ -185,7 +185,7 @@ val random(val state, val modulus) if (bignump(modulus)) { mp_int *m = mp(modulus); - int bits = mp_count_bits(m); + int bits = mp_count_bits(m) - mp_is_pow_two(m); int rands_needed = (bits + 32 - 1) / 32; int msb_rand_bits = bits % 32; rand32_t msb_rand_mask = convert(rand32_t, -1) >> (32 - msb_rand_bits); @@ -222,10 +222,10 @@ val random(val state, val modulus) return normalize(out); } else if (fixnump(modulus)) { cnum m = c_num(modulus); - int bits = highest_bit(m); if (m == 1) { return zero; } else if (m > 1) { + int bits = highest_bit(m - 1); #if SIZEOF_PTR >= 8 int rands_needed = (bits + 32 - 1) / 32; #endif diff --git a/tests/013/maze.expected b/tests/013/maze.expected index f0a09770..e3cbbf80 100644 --- a/tests/013/maze.expected +++ b/tests/013/maze.expected @@ -1,61 +1,61 @@ + +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ -| | | | | | | -| | | | | | | -+ + + + +----+----+----+----+ + + + + +----+----+----+ + +----+ + -| | | | | | | | | | | -| | | | | | | | | | | -+----+ + + +----+ +----+ +----+----+ +----+----+ +----+ +----+----+ +----+ -| | | | | | | | | | | -| | | | | | | | | | | -+----+----+ + + +----+ +----+----+ + +----+----+----+----+----+ +----+----+ + -| | | | | | | | | | | -| | | | | | | | | | | -+ + + +----+----+----+ + +----+----+ + +----+ + + + + +----+----+ -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ +----+----+ +----+ +----+----+----+ + + + +----+ +----+----+ + + + -| | | | | | | | | | | -| | | | | | | | | | | -+----+----+ + + +----+ +----+ + +----+ + + +----+----+----+----+ + + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ +----+----+----+ +----+----+ + +----+ + + + + + +----+ + + + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ + + + +----+ + +----+----+----+----+ +----+ + + + +----+----+----+ -| | | | | | | | | | -| | | | | | | | | | -+ +----+----+----+----+----+----+----+----+ + +----+----+----+ +----+ +----+----+ + -| | | | | | | | -| | | | | | | | -+ + + +----+----+----+----+ +----+ +----+ +----+ +----+----+----+ +----+ + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ +----+----+----+ + + +----+ +----+ +----+ + + + + +----+ + + -| | | | | | | | | | | -| | | | | | | | | | | -+----+ + + +----+----+ +----+ + +----+ +----+----+----+----+----+ +----+ + -| | | | | | | | | | | | -| | | | | | | | | | | | -+ + +----+ + +----+----+ +----+ + +----+ + + + +----+----+ + + -| | | | | | | | | -| | | | | | | | | -+ + +----+----+----+----+----+----+ +----+----+----+----+----+----+----+ + +----+ + -| | | | | | | | | -| | | | | | | | | -+ + +----+----+ +----+ +----+----+ + + + + +----+ + +----+----+ + -| | | | | | | | | | | | | | | -| | | | | | | | | | | | | | | -+----+ + + +----+ +----+ + + +----+----+ +----+ +----+----+ + + + -| | | | | | | | | | | -| | | | | | | | | | | -+ +----+ +----+ +----+----+ + +----+----+ +----+----+----+----+ +----+----+ + -| | | | | | | | | | -| | | | | | | | | | -+----+----+ + +----+ + +----+----+ +----+----+----+----+ + +----+ + +----+ -| | | | | | | | | | | | -| | | | | | | | | | | | -+ + + + + +----+----+----+ +----+----+----+----+ + +----+ + + + + -| | | | | | | -| | | | | | | +| | | | | | | | | +| | | | | | | | | ++ + + + +----+ + + + +----+ + +----+----+ + + +----+ +----+ +| | | | | | | | | | | | +| | | | | | | | | | | | ++----+----+----+----+ + +----+----+----+----+----+ +----+ + +----+ +----+----+ + +| | | | | | | | | +| | | | | | | | | ++ +----+ + + + +----+ +----+----+ +----+ + +----+ +----+ +----+ + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ +----+----+----+----+ + +----+----+ +----+ + + + +----+----+----+ +----+ +| | | | | | | | | | | +| | | | | | | | | | | ++----+----+ + + +----+ + +----+----+ + + +----+----+----+ + + + + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ +----+ + +----+----+----+ + + + +----+ +----+ + +----+ + + + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ + +----+ + +----+ +----+----+ +----+ + + +----+----+ +----+----+----+ +| | | | | | | | | | | | +| | | | | | | | | | | | ++ +----+ +----+----+ +----+ + + + +----+ + +----+----+----+ + + + +| | | | | | | | | | | | +| | | | | | | | | | | | ++ + +----+ + +----+ + +----+----+----+ +----+----+ +----+ + + + + +| | | | | | | | | | | | | | +| | | | | | | | | | | | | | ++----+ + + +----+ +----+----+ +----+ + + + +----+----+ +----+----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++ +----+----+----+ +----+----+ +----+ + + + +----+----+ + + +----+----+ +| | | | | | | | +| | | | | | | | ++ +----+ +----+----+----+----+----+ +----+----+ + +----+----+----+----+----+----+ + +| | | | | | | | | | +| | | | | | | | | | ++ + +----+ + +----+ + +----+----+----+----+ + +----+ +----+ + +----+ +| | | | | | | | | | | +| | | | | | | | | | | ++ +----+ +----+----+ +----+ +----+----+ + +----+----+ +----+ +----+----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++----+----+ + + + + +----+ +----+----+----+ + + +----+----+----+ +----+ +| | | | | | | | | | +| | | | | | | | | | ++ +----+----+ +----+----+----+----+----+----+ + +----+----+----+ +----+ + +----+ +| | | | | | | | | +| | | | | | | | | ++----+ + + +----+ + +----+----+----+ +----+ + + +----+----+ +----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++ +----+ +----+----+----+----+----+----+ + +----+----+----+ + +----+----+----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++ +----+----+----+ + +----+ +----+ +----+----+ + + + + + + + + +| | | | | | | +| | | | | | | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ + |