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 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