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 | |
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')
-rw-r--r-- | lib/libc/gen/Makefile.inc | 2 | ||||
-rw-r--r-- | lib/libc/gen/Symbol.map | 1 | ||||
-rw-r--r-- | lib/libc/gen/arc4random.3 | 11 | ||||
-rw-r--r-- | lib/libc/gen/arc4random.c | 45 |
4 files changed, 58 insertions, 1 deletions
diff --git a/lib/libc/gen/Makefile.inc b/lib/libc/gen/Makefile.inc index 33f666b..a0db9a7 100644 --- a/lib/libc/gen/Makefile.inc +++ b/lib/libc/gen/Makefile.inc @@ -69,7 +69,7 @@ MAN+= alarm.3 arc4random.3 \ unvis.3 usleep.3 utime.3 valloc.3 vis.3 wordexp.3 MLINKS+=arc4random.3 arc4random_addrandom.3 arc4random.3 arc4random_stir.3 \ - arc4random.3 arc4random_buf.3 + arc4random.3 arc4random_buf.3 arc4random.3 arc4random_uniform.3 MLINKS+=ctermid.3 ctermid_r.3 MLINKS+=devname.3 devname_r.3 MLINKS+=directory.3 closedir.3 directory.3 dirfd.3 directory.3 opendir.3 \ diff --git a/lib/libc/gen/Symbol.map b/lib/libc/gen/Symbol.map index b6cf313..6e8bfce 100644 --- a/lib/libc/gen/Symbol.map +++ b/lib/libc/gen/Symbol.map @@ -330,6 +330,7 @@ FBSD_1.0 { FBSD_1.1 { arc4random_buf; + arc4random_uniform; fdopendir; feature_present; fts_open; diff --git a/lib/libc/gen/arc4random.3 b/lib/libc/gen/arc4random.3 index 5af38ce..be1f690 100644 --- a/lib/libc/gen/arc4random.3 +++ b/lib/libc/gen/arc4random.3 @@ -36,6 +36,7 @@ .Sh NAME .Nm arc4random , .Nm arc4random_buf , +.Nm arc4random_uniform , .Nm arc4random_stir , .Nm arc4random_addrandom .Nd arc4 random number generator @@ -47,6 +48,8 @@ .Fn arc4random "void" .Ft void .Fn arc4random_buf "void *buf" "size_t nbytes" +.Ft u_int32_t +.Fn arc4random_uniform "u_int32_t upper_bound" .Ft void .Fn arc4random_stir "void" .Ft void @@ -78,6 +81,14 @@ of length .Fa nbytes with ARC4-derived random data. .Pp +.Fn arc4random_uniform +will return a uniformly distributed random number less than +.Fa upper_bound . +.Fn arc4random_uniform +is recommended over constructions like +.Dq Li arc4random() % upper_bound +as it avoids "modulo bias" when the upper bound is not a power of two. +.Pp The .Fn arc4random_stir function reads data from 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> |