diff options
author | ache <ache@FreeBSD.org> | 2008-07-22 11:33:49 +0000 |
---|---|---|
committer | ache <ache@FreeBSD.org> | 2008-07-22 11:33:49 +0000 |
commit | 06e39c3b3642e5c3f83618f9864d21117278b68f (patch) | |
tree | 374d7148320af4df512b9186deb03fbb60ef34de /lib/libc/gen/arc4random.c | |
parent | 31393d8a077bd95c3fa9ef23a427ae3c2c7860e6 (diff) | |
download | FreeBSD-src-06e39c3b3642e5c3f83618f9864d21117278b68f.zip FreeBSD-src-06e39c3b3642e5c3f83618f9864d21117278b68f.tar.gz |
Add arc4random_uniform() function (to avoid "modulo bias")
Obtained from: OpenBSD
Diffstat (limited to 'lib/libc/gen/arc4random.c')
-rw-r--r-- | lib/libc/gen/arc4random.c | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/lib/libc/gen/arc4random.c b/lib/libc/gen/arc4random.c index 2e6ce11..1c7dead 100644 --- a/lib/libc/gen/arc4random.c +++ b/lib/libc/gen/arc4random.c @@ -240,6 +240,51 @@ arc4random_buf(void *_buf, size_t n) THREAD_UNLOCK(); } +/* + * Calculate a uniformly distributed random number less than upper_bound + * avoiding "modulo bias". + * + * Uniformity is achieved by generating new random numbers until the one + * returned is outside the range [0, 2**32 % upper_bound). This + * guarantees the selected random number will be inside + * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) + * after reduction modulo upper_bound. + */ +u_int32_t +arc4random_uniform(u_int32_t upper_bound) +{ + u_int32_t r, min; + + if (upper_bound < 2) + return 0; + +#if (ULONG_MAX > 0xffffffffUL) + min = 0x100000000UL % upper_bound; +#else + /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ + if (upper_bound > 0x80000000) + min = 1 + ~upper_bound; /* 2**32 - upper_bound */ + else { + /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ + min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; + } +#endif + + /* + * This could theoretically loop forever but each retry has + * p > 0.5 (worst case, usually far better) of selecting a + * number inside the range we need, so it should rarely need + * to re-roll. + */ + for (;;) { + r = arc4random(); + if (r >= min) + break; + } + + return (r % upper_bound); +} + #if 0 /*-------- Test code for i386 --------*/ #include <stdio.h> |