1 /*	$OpenBSD: arc4random_uniform.c,v 1.3 2019/01/20 02:59:07 bcook Exp $	*/
2 
3 /*
4  * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18 
19 #include <sys/types.h>
20 #include <sys/libkern.h>
21 
22 /*
23  * Calculate a uniformly distributed random number less than upper_bound
24  * avoiding "modulo bias".
25  *
26  * Uniformity is achieved by generating new random numbers until the one
27  * returned is outside the range [0, 2**32 % upper_bound).  This
28  * guarantees the selected random number will be inside
29  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
30  * after reduction modulo upper_bound.
31  */
32 uint32_t
karc4random_uniform(uint32_t upper_bound)33 karc4random_uniform(uint32_t upper_bound)
34 {
35 	uint32_t r, min;
36 
37 	if (upper_bound < 2)
38 		return 0;
39 
40 	/* 2**32 % x == (2**32 - x) % x */
41 	min = -upper_bound % upper_bound;
42 
43 	/*
44 	 * This could theoretically loop forever but each retry has
45 	 * p > 0.5 (worst case, usually far better) of selecting a
46 	 * number inside the range we need, so it should rarely need
47 	 * to re-roll.
48 	 */
49 	for (;;) {
50 		r = karc4random();
51 		if (r >= min)
52 			break;
53 	}
54 
55 	return r % upper_bound;
56 }
57