From c5174f6fb2af2801895c90122e07139f4de5412d Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 12 Dec 2005 22:43:16 +0000 Subject: [PATCH] (struct irand_state, irand_init, irand32, irand_mod): Moved back here, from rand-isaac.c. --- src/shred.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) diff --git a/src/shred.c b/src/shred.c index 54bc49cb4..3e47aad1c 100644 --- a/src/shred.c +++ b/src/shred.c @@ -227,6 +227,66 @@ to be recovered later.\n\ exit (status); } +/* Single-word RNG built on top of ISAAC */ +struct irand_state +{ + uint32_t r[ISAAC_WORDS]; + unsigned int numleft; + struct isaac_state *s; +}; + +static void +irand_init (struct irand_state *r, struct isaac_state *s) +{ + r->numleft = 0; + r->s = s; +} + +/* + * We take from the end of the block deliberately, so if we need + * only a small number of values, we choose the final ones which are + * marginally better mixed than the initial ones. + */ +static uint32_t +irand32 (struct irand_state *r) +{ + if (!r->numleft) + { + isaac_refill (r->s, r->r); + r->numleft = ISAAC_WORDS; + } + return r->r[--r->numleft]; +} + +/* + * Return a uniformly distributed random number between 0 and n, + * inclusive. Thus, the result is modulo n+1. + * + * Theory of operation: as x steps through every possible 32-bit number, + * x % n takes each value at least 2^32 / n times (rounded down), but + * the values less than 2^32 % n are taken one additional time. Thus, + * x % n is not perfectly uniform. To fix this, the values of x less + * than 2^32 % n are disallowed, and if the RNG produces one, we ask + * for a new value. + */ +static uint32_t +irand_mod (struct irand_state *r, uint32_t n) +{ + uint32_t x; + uint32_t lim; + + if (!++n) + return irand32 (r); + + lim = -n % n; /* == (2**32-n) % n == 2**32 % n */ + do + { + x = irand32 (r); + } + while (x < lim); + return x % n; +} + /* * Fill a buffer with a fixed pattern. * -- 2.34.1