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