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.

2 files changed, 6 insertions, 0 deletions

diff --git a/mpi/mpi.c b/mpi/mpi.c
index 24df7c30..20a48a12 100644
--- a/mpi/mpi.c
+++ b/mpi/mpi.c
@@ -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) */
 
 /*
diff --git a/mpi/mpi.h b/mpi/mpi.h
index 49ccd294..fb9e47e8 100644
--- a/mpi/mpi.h
+++ b/mpi/mpi.h
@@ -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))