Index: sys/libkern/arc4random.c =================================================================== --- sys/libkern/arc4random.c +++ sys/libkern/arc4random.c @@ -217,3 +217,39 @@ arc4rand(ptr, len, 0); } + +/* + * 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. + */ +uint32_t +arc4random_uniform(uint32_t upper_bound) +{ + uint32_t r, min; + + if (upper_bound < 2) + return 0; + + /* 2**32 % x == (2**32 - x) % x */ + min = -upper_bound % upper_bound; + + /* + * 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; +} Index: sys/sys/libkern.h =================================================================== --- sys/sys/libkern.h +++ sys/sys/libkern.h @@ -127,6 +127,7 @@ struct malloc_type; uint32_t arc4random(void); void arc4random_buf(void *, size_t); +uint32_t arc4random_uniform(uint32_t upper_bound); void arc4rand(void *, u_int, int); int timingsafe_bcmp(const void *, const void *, size_t); void *bsearch(const void *, const void *, size_t,