1 /*-
2 * SPDX-License-Identifier: 0BSD
3 *
4 * Copyright (c) Robert Clausecker <fuz@FreeBSD.org>
5 * Based on a publication by Daniel Lemire.
6 * Public domain where applicable.
7 *
8 * Daniel Lemire, "Fast Random Integer Generation in an Interval",
9 * Association for Computing Machinery, ACM Trans. Model. Comput. Simul.,
10 * no. 1, vol. 29, pp. 1--12, New York, NY, USA, January 2019.
11 */
12
13 #include <stdint.h>
14 #include <stdlib.h>
15
16 uint32_t
arc4random_uniform(uint32_t upper_bound)17 arc4random_uniform(uint32_t upper_bound)
18 {
19 uint64_t product;
20
21 /*
22 * The paper uses these variable names:
23 *
24 * L -- log2(UINT32_MAX+1)
25 * s -- upper_bound
26 * x -- arc4random() return value
27 * m -- product
28 * l -- (uint32_t)product
29 * t -- threshold
30 */
31
32 if (upper_bound <= 1)
33 return (0);
34
35 product = upper_bound * (uint64_t)arc4random();
36
37 if ((uint32_t)product < upper_bound) {
38 uint32_t threshold;
39
40 /* threshold = (2**32 - upper_bound) % upper_bound */
41 threshold = -upper_bound % upper_bound;
42 while ((uint32_t)product < threshold)
43 product = upper_bound * (uint64_t)arc4random();
44 }
45
46 return (product >> 32);
47 }
48