introduce a isc_random_uniform() function to return a uniformly distributed

number 0 < x <= upper_bound and use it to correct the last tiny bias in the
shuffle initialisation

feedback & ok deraadt@

1 files changed, 46 insertions, 5 deletions

diff --git a/usr.sbin/bind/lib/isc/random.c b/usr.sbin/bind/lib/isc/random.c
index 442d35cd485..4f74f8b6d50 100644
--- a/usr.sbin/bind/lib/isc/random.c
+++ b/usr.sbin/bind/lib/isc/random.c
@@ -1,6 +1,7 @@
 /*
  * Copyright (C) 2004, 2005  Internet Systems Consortium, Inc. ("ISC")
  * Copyright (C) 1999-2003  Internet Software Consortium.
+ * Copyright (C) 2008 Damien Miller
  *
  * Permission to use, copy, modify, and distribute this software for any
  * purpose with or without fee is hereby granted, provided that the above
@@ -91,14 +92,54 @@ isc_random_get(isc_uint32_t *val)
 }
 
 isc_uint32_t
+isc_random_uniform(isc_uint32_t upper_bound)
+{
+	isc_uint32_t r, min;
+
+	/*
+	 * 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.
+	 */
+
+	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 doing this, 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 (;;) {
+		isc_random_get(&r);
+		if (r >= min)
+			break;
+	}
+
+	return r % upper_bound;
+}
+
+isc_uint32_t
 isc_random_jitter(isc_uint32_t max, isc_uint32_t jitter) {
 	REQUIRE(jitter < max);
 	if (jitter == 0)
 		return (max);
 	else
-#ifndef HAVE_ARC4RANDOM
-		return (max - rand() % jitter);
-#else
-		return (max - arc4random() % jitter);
-#endif
+		return max - isc_random_uniform(jitter);
 }
+