1 /* $NetBSD: random.c,v 1.9 2026/01/29 18:37:54 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 /* 17 * Portions of isc_random_uniform(): 18 * 19 * Copyright (c) 1996, David Mazieres <dm (at) uun.org> 20 * Copyright (c) 2008, Damien Miller <djm (at) openbsd.org> 21 * 22 * Permission to use, copy, modify, and distribute this software for any 23 * purpose with or without fee is hereby granted, provided that the above 24 * copyright notice and this permission notice appear in all copies. 25 * 26 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 27 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 28 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 29 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 30 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 31 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 32 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 33 */ 34 35 #if !HAVE_ARC4RANDOM || defined(__linux__) 36 37 #include <inttypes.h> 38 #include <stdio.h> 39 40 #include <isc/os.h> 41 #include <isc/random.h> 42 #include <isc/thread.h> 43 #include <isc/util.h> 44 #include <isc/uv.h> 45 46 #define ISC_RANDOM_BUFSIZE (ISC_OS_CACHELINE_SIZE / sizeof(uint32_t)) 47 48 thread_local static uint32_t isc__random_pool[ISC_RANDOM_BUFSIZE]; 49 thread_local static size_t isc__random_pos = ISC_RANDOM_BUFSIZE; 50 51 uint32_t 52 isc_random32(void) { 53 #if FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 54 /* 55 * A fixed stream of numbers helps with problem reproduction when 56 * fuzzing. 57 */ 58 return (uint32_t)(isc__random_pos++); 59 #endif /* if FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION */ 60 61 if (isc__random_pos == ISC_RANDOM_BUFSIZE) { 62 isc_random_buf(isc__random_pool, sizeof(isc__random_pool)); 63 isc__random_pos = 0; 64 } 65 66 return isc__random_pool[isc__random_pos++]; 67 } 68 69 void 70 isc_random_buf(void *buf, size_t buflen) { 71 REQUIRE(buflen == 0 || buf != NULL); 72 73 if (buf == NULL || buflen == 0) { 74 return; 75 } 76 77 int r = uv_random(NULL, NULL, buf, buflen, 0, NULL); 78 UV_RUNTIME_CHECK(uv_random, r); 79 } 80 81 uint32_t 82 isc_random_uniform(uint32_t limit) { 83 /* 84 * Daniel Lemire's nearly-divisionless unbiased bounded random numbers. 85 * 86 * https://lemire.me/blog/?p=17551 87 * 88 * The raw random number generator `next()` returns a 32-bit value. 89 * We do a 64-bit multiply `next() * limit` and treat the product as a 90 * 32.32 fixed-point value less than the limit. Our result will be the 91 * integer part (upper 32 bits), and we will use the fraction part 92 * (lower 32 bits) to determine whether or not we need to resample. 93 */ 94 uint64_t num = (uint64_t)isc_random32() * (uint64_t)limit; 95 /* 96 * In the fast path, we avoid doing a division in most cases by 97 * comparing the fraction part of `num` with the limit, which is 98 * a slight over-estimate for the exact resample threshold. 99 */ 100 if ((uint32_t)(num) < limit) { 101 /* 102 * We are in the slow path where we re-do the approximate test 103 * more accurately. The exact threshold for the resample loop 104 * is the remainder after dividing the raw RNG limit `1 << 32` 105 * by the caller's limit. We use a trick to calculate it 106 * within 32 bits: 107 * 108 * (1 << 32) % limit 109 * == ((1 << 32) - limit) % limit 110 * == (uint32_t)(-limit) % limit 111 * 112 * This division is safe: we know that `limit` is strictly 113 * greater than zero because of the slow-path test above. 114 */ 115 uint32_t residue = (uint32_t)(-limit) % limit; 116 /* 117 * Unless we get one of `N = (1 << 32) - residue` valid 118 * values, we reject the sample. This `N` is a multiple of 119 * `limit`, so our results will be unbiased; and `N` is the 120 * largest multiple that fits in 32 bits, so rejections are as 121 * rare as possible. 122 * 123 * There are `limit` possible values for the integer part of 124 * our fixed-point number. Each one corresponds to `N/limit` 125 * or `N/limit + 1` possible fraction parts. For our result to 126 * be unbiased, every possible integer part must have the same 127 * number of possible valid fraction parts. So, when we get 128 * the superfluous value in the `N/limit + 1` cases, we need 129 * to reject and resample. 130 * 131 * Because of the multiplication, the possible values in the 132 * fraction part are equally spaced by `limit`, with varying 133 * gaps at each end of the fraction's 32-bit range. We will 134 * choose a range of size `N` (a multiple of `limit`) into 135 * which valid fraction values must fall, with the rest of the 136 * 32-bit range covered by the `residue`. Lemire's paper says 137 * that exactly `N/limit` possible values spaced apart by 138 * `limit` will fit into our size `N` valid range, regardless 139 * of the size of the end gaps, the phase alignment of the 140 * values, or the position of the range. 141 * 142 * So, when a fraction value falls in the `residue` outside 143 * our valid range, it is superfluous, and we resample. 144 */ 145 while ((uint32_t)(num) < residue) { 146 num = (uint64_t)isc_random32() * (uint64_t)limit; 147 } 148 } 149 /* 150 * Return the integer part (upper 32 bits). 151 */ 152 return (uint32_t)(num >> 32); 153 } 154 155 #endif /* HAVE_ARC4RANDOM && !defined(__linux__) */ 156
Indexes created Mon Mar 02 05:31:46 UTC 2026