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