1*127709d3SRobert Clausecker /*-
2*127709d3SRobert Clausecker * SPDX-License-Identifier: 0BSD
36b97c2e3SConrad Meyer *
4*127709d3SRobert Clausecker * Copyright (c) Robert Clausecker <fuz@FreeBSD.org>
5*127709d3SRobert Clausecker * Based on a publication by Daniel Lemire.
6*127709d3SRobert Clausecker * Public domain where applicable.
76b97c2e3SConrad Meyer *
8*127709d3SRobert Clausecker * Daniel Lemire, "Fast Random Integer Generation in an Interval",
9*127709d3SRobert Clausecker * Association for Computing Machinery, ACM Trans. Model. Comput. Simul.,
10*127709d3SRobert Clausecker * no. 1, vol. 29, pp. 1--12, New York, NY, USA, January 2019.
116b97c2e3SConrad Meyer */
126b97c2e3SConrad Meyer
13d25a1430SXin LI #include <stdint.h>
146b97c2e3SConrad Meyer #include <stdlib.h>
156b97c2e3SConrad Meyer
166b97c2e3SConrad Meyer uint32_t
arc4random_uniform(uint32_t upper_bound)176b97c2e3SConrad Meyer arc4random_uniform(uint32_t upper_bound)
186b97c2e3SConrad Meyer {
19*127709d3SRobert Clausecker uint64_t product;
206b97c2e3SConrad Meyer
216b97c2e3SConrad Meyer /*
22*127709d3SRobert Clausecker * The paper uses these variable names:
23*127709d3SRobert Clausecker *
24*127709d3SRobert Clausecker * L -- log2(UINT32_MAX+1)
25*127709d3SRobert Clausecker * s -- upper_bound
26*127709d3SRobert Clausecker * x -- arc4random() return value
27*127709d3SRobert Clausecker * m -- product
28*127709d3SRobert Clausecker * l -- (uint32_t)product
29*127709d3SRobert Clausecker * t -- threshold
306b97c2e3SConrad Meyer */
31*127709d3SRobert Clausecker
32*127709d3SRobert Clausecker if (upper_bound <= 1)
33*127709d3SRobert Clausecker return (0);
34*127709d3SRobert Clausecker
35*127709d3SRobert Clausecker product = upper_bound * (uint64_t)arc4random();
36*127709d3SRobert Clausecker
37*127709d3SRobert Clausecker if ((uint32_t)product < upper_bound) {
38*127709d3SRobert Clausecker uint32_t threshold;
39*127709d3SRobert Clausecker
40*127709d3SRobert Clausecker /* threshold = (2**32 - upper_bound) % upper_bound */
41*127709d3SRobert Clausecker threshold = -upper_bound % upper_bound;
42*127709d3SRobert Clausecker while ((uint32_t)product < threshold)
43*127709d3SRobert Clausecker product = upper_bound * (uint64_t)arc4random();
446b97c2e3SConrad Meyer }
456b97c2e3SConrad Meyer
46*127709d3SRobert Clausecker return (product >> 32);
476b97c2e3SConrad Meyer }
48