summaryrefslogtreecommitdiffstats
path: root/lib/libc
diff options
context:
space:
mode:
authorache <ache@FreeBSD.org>2008-07-22 11:33:49 +0000
committerache <ache@FreeBSD.org>2008-07-22 11:33:49 +0000
commit06e39c3b3642e5c3f83618f9864d21117278b68f (patch)
tree374d7148320af4df512b9186deb03fbb60ef34de /lib/libc
parent31393d8a077bd95c3fa9ef23a427ae3c2c7860e6 (diff)
downloadFreeBSD-src-06e39c3b3642e5c3f83618f9864d21117278b68f.zip
FreeBSD-src-06e39c3b3642e5c3f83618f9864d21117278b68f.tar.gz
Add arc4random_uniform() function (to avoid "modulo bias")
Obtained from: OpenBSD
Diffstat (limited to 'lib/libc')
-rw-r--r--lib/libc/gen/Makefile.inc2
-rw-r--r--lib/libc/gen/Symbol.map1
-rw-r--r--lib/libc/gen/arc4random.311
-rw-r--r--lib/libc/gen/arc4random.c45
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>
OpenPOWER on IntegriCloud