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