1 /*-
2 * Copyright (c) 2010
3 * Thorsten Glaser <tg@mirbsd.org>
4 * Copyright (c) 2008
5 * Damien Miller <djm@openbsd.org>
6 * With simplifications by Jinmei Tatuya.
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 */
20
21 #include <libckern.h>
22 #include <sys/limits.h>
23
24 __RCSID("$MirOS: src/kern/c/arc4random_uniform.c,v 1.2 2010/09/12 17:10:49 tg Exp $");
25
26 /* u_int32_t in the original API, but we pray they're the same */
27 extern uint32_t arc4random(void);
28
29 /*
30 * Calculate a uniformly distributed random number less than
31 * upper_bound avoiding "modulo bias".
32 *
33 * Uniformity is achieved by generating new random numbers
34 * until the one returned is outside the range
35 * [0, 2^32 % upper_bound[. This guarantees the selected
36 * random number will be inside the range
37 * [2^32 % upper_bound, 2^32[ which maps back to
38 * [0, upper_bound[ after reduction modulo upper_bound.
39 */
40 uint32_t
arc4random_uniform(uint32_t upper_bound)41 arc4random_uniform(uint32_t upper_bound)
42 {
43 uint32_t r, min;
44
45 if (upper_bound < 2)
46 return (0);
47
48 #if defined(ULONG_MAX) && (ULONG_MAX > 0xFFFFFFFFUL)
49 min = 0x100000000UL % upper_bound;
50 #else
51 /* calculate (2^32 % upper_bound) avoiding 64-bit math */
52 if (upper_bound > 0x80000000U)
53 /* 2^32 - upper_bound (only one "value area") */
54 min = 1 + ~upper_bound;
55 else
56 /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */
57 min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound;
58 #endif
59
60 /*
61 * This could theoretically loop forever but each retry has
62 * p > 0.5 (worst case, usually far better) of selecting a
63 * number inside the range we need, so it should rarely need
64 * to re-roll (at all).
65 */
66 do {
67 r = arc4random();
68 } while (r < min);
69
70 return (r % upper_bound);
71 }
72