Date: Tue, 04 Feb 2003 14:00:27 +0100 From: Dag-Erling Smorgrav <des@ofug.org> To: David Schultz <dschultz@uclink.Berkeley.EDU> Cc: "Andrey A. Chernov" <ache@nagual.pp.ru>, Kris Kennaway <kris@obsecurity.org>, current@FreeBSD.ORG Subject: Re: rand() is broken Message-ID: <xzpfzr4b3pw.fsf@flood.ping.uio.no> In-Reply-To: <20030204115237.GA6483@HAL9000.homeunix.com> (David Schultz's message of "Tue, 4 Feb 2003 03:52:37 -0800") References: <20030202070644.GA9987@rot13.obsecurity.org> <20030202090422.GA59750@nagual.pp.ru> <20030203002639.GB44914@HAL9000.homeunix.com> <20030203100002.GA73386@nagual.pp.ru> <20030204054020.GA2447@HAL9000.homeunix.com> <20030204094659.GA87303@nagual.pp.ru> <20030204115237.GA6483@HAL9000.homeunix.com>
next in thread | previous in thread | raw e-mail | index | archive | help
--=-=-= David Schultz <dschultz@uclink.Berkeley.EDU> writes: > You can do better than the present generator with 32 bits of state. > See the following page by Neal Wagner (not to be confused with David Wagner): > http://www.cs.utsa.edu/~wagner/laws/rng.html The attached patch, based on one of the m/k pairs suggested on that page, results in the following: des@des ~/src% ./rndtest | head 0 b 5 f 8 5 2 c 8 5 1 8 4 9 7 b d 9 e a d 3 8 8 5 9 2 3 e a c f 7 a d b f 0 1 3 6 7 4 f 0 6 0 1 2 3 1 c b a 6 1 e 0 9 c f 7 c 6 6 1 a a d b 3 e b a a 0 e d a f 8 6 3 f f 9 3 7 6 6 d 7 f 6 8 d b d 6 2 b f 2 2 b 1 7 4 4 3 5 5 2 9 6 4 e 1 9 4 7 b f 6 f 7 8 c 1 5 7 e 3 5 d b 8 c c 4 d 1 3 6 e 0 3 3 3 2 e 5 3 b 5 e 7 b c a 0 a 3 2 d 5 f c 9 f c 3 9 a 1 f 3 f 2 c 5 9 4 6 2 d 2 3 e 2 7 5 a 8 8 1 5 7 0 5 4 e c f 6 3 b 0 8 4 d 2 a 8 0 5 7 b 2 1 4 e e 9 7 1 5 5 6 f f e 6 f a 4 e 5 a f 8 d f 7 b 3 8 d e 3 f 5 4 0 2 e 5 c a f 5 a e 5 0 9 4 6 0 0 9 f d 9 6 4 b f 8 2 3 5 e 4 5 9 9 a d 3 4 5 5 0 f 9 9 1 8 6 7 a 5 0 2 0 5 8 b 6 1 6 7 f a 9 a 6 6 d Note that my patch assumes that RAND_MAX fits in 32 bits, which should be acceptable for FreeBSD since it always uses 32-bit ints (all our 32-bit platforms are ILP32, and I believe all our 64-bit platforms are I32LP64) and RAND_MAX is uniformly defined to 0x7fffffff. DES -- Dag-Erling Smorgrav - des@ofug.org --=-=-= Content-Type: text/x-patch Content-Disposition: attachment; filename=rand.diff Index: lib/libc/stdlib/rand.c =================================================================== RCS file: /home/ncvs/src/lib/libc/stdlib/rand.c,v retrieving revision 1.11 diff -u -r1.11 rand.c --- lib/libc/stdlib/rand.c 2 Feb 2003 14:27:51 -0000 1.11 +++ lib/libc/stdlib/rand.c 4 Feb 2003 13:37:03 -0000 @@ -52,7 +52,7 @@ #endif /* TEST */ static int -do_rand(unsigned long *ctx) +do_rand(uint32_t *ctx) { #ifdef USE_WEAK_SEEDING /* @@ -63,21 +63,23 @@ return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1)); #else /* !USE_WEAK_SEEDING */ /* - * Compute x = (7^5 * x) mod (2^31 - 1) - * wihout overflowing 31 bits: - * (2^31 - 1) = 127773 * (7^5) + 2836 - * From "Random number generators: good ones are hard to find", - * Park and Miller, Communications of the ACM, vol. 31, no. 10, - * October 1988, p. 1195. + * New algorithm derived from + * The Laws of Cryptography: Pseudo-random Number Generation + * by Neal R. Wagner + * http://www.cs.utsa.edu/~wagner/laws/rng.html + * which itself is derived from work by Donald E. Knuth. + * + * This is a linear congruence generator using the equation + * + * x(n+1) = (k * x(n) + a) mod m + * + * where m is 2^31 - 1, k is 62089911 and a is 0. */ - long hi, lo, x; + uint64_t tmp; - hi = *ctx / 127773; - lo = *ctx % 127773; - x = 16807 * lo - 2836 * hi; - if (x <= 0) - x += 0x7fffffff; - return ((*ctx = x) % ((u_long)RAND_MAX + 1)); + tmp = *ctx * 62089911; + *ctx = (uint32_t)(tmp % (uint64_t)RAND_MAX); + return (*ctx); #endif /* !USE_WEAK_SEEDING */ } @@ -85,7 +87,7 @@ int rand_r(unsigned int *ctx) { - u_long val = (u_long) *ctx; + uint32_t val = (uint32_t) *ctx; int r = do_rand(&val); *ctx = (unsigned int) val; @@ -93,7 +95,7 @@ } -static u_long next = 1; +static uint32_t next = 1; int rand() --=-=-=-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?xzpfzr4b3pw.fsf>