Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * Pseudo-Random Number Generator
4 : *
5 : * We use Blackman and Vigna's xoroshiro128** 1.0 algorithm
6 : * to have a small, fast PRNG suitable for generating reasonably
7 : * good-quality 64-bit data. This should not be considered
8 : * cryptographically strong, however.
9 : *
10 : * About these generators: https://prng.di.unimi.it/
11 : * See also https://en.wikipedia.org/wiki/List_of_random_number_generators
12 : *
13 : * Copyright (c) 2021-2023, PostgreSQL Global Development Group
14 : *
15 : * src/common/pg_prng.c
16 : *
17 : *-------------------------------------------------------------------------
18 : */
19 :
20 : #include "c.h"
21 :
22 : #include <math.h>
23 :
24 : #include "common/pg_prng.h"
25 : #include "port/pg_bitutils.h"
26 :
27 : /* X/Open (XSI) requires <math.h> to provide M_PI, but core POSIX does not */
28 : #ifndef M_PI
29 : #define M_PI 3.14159265358979323846
30 : #endif
31 :
32 :
33 : /* process-wide state vector */
34 : pg_prng_state pg_global_prng_state;
35 :
36 :
37 : /*
38 : * 64-bit rotate left
39 : */
40 : static inline uint64
41 16656564 : rotl(uint64 x, int bits)
42 : {
43 16656564 : return (x << bits) | (x >> (64 - bits));
44 : }
45 :
46 : /*
47 : * The basic xoroshiro128** algorithm.
48 : * Generates and returns a 64-bit uniformly distributed number,
49 : * updating the state vector for next time.
50 : *
51 : * Note: the state vector must not be all-zeroes, as that is a fixed point.
52 : */
53 : static uint64
54 5552188 : xoroshiro128ss(pg_prng_state *state)
55 : {
56 5552188 : uint64 s0 = state->s0,
57 5552188 : sx = state->s1 ^ s0,
58 5552188 : val = rotl(s0 * 5, 7) * 9;
59 :
60 : /* update state */
61 5552188 : state->s0 = rotl(s0, 24) ^ sx ^ (sx << 16);
62 5552188 : state->s1 = rotl(sx, 37);
63 :
64 5552188 : return val;
65 : }
66 :
67 : /*
68 : * We use this generator just to fill the xoroshiro128** state vector
69 : * from a 64-bit seed.
70 : */
71 : static uint64
72 75308 : splitmix64(uint64 *state)
73 : {
74 : /* state update */
75 75308 : uint64 val = (*state += UINT64CONST(0x9E3779B97f4A7C15));
76 :
77 : /* value extraction */
78 75308 : val = (val ^ (val >> 30)) * UINT64CONST(0xBF58476D1CE4E5B9);
79 75308 : val = (val ^ (val >> 27)) * UINT64CONST(0x94D049BB133111EB);
80 :
81 75308 : return val ^ (val >> 31);
82 : }
83 :
84 : /*
85 : * Initialize the PRNG state from a 64-bit integer,
86 : * taking care that we don't produce all-zeroes.
87 : */
88 : void
89 37654 : pg_prng_seed(pg_prng_state *state, uint64 seed)
90 : {
91 37654 : state->s0 = splitmix64(&seed);
92 37654 : state->s1 = splitmix64(&seed);
93 : /* Let's just make sure we didn't get all-zeroes */
94 37654 : (void) pg_prng_seed_check(state);
95 37654 : }
96 :
97 : /*
98 : * Initialize the PRNG state from a double in the range [-1.0, 1.0],
99 : * taking care that we don't produce all-zeroes.
100 : */
101 : void
102 14 : pg_prng_fseed(pg_prng_state *state, double fseed)
103 : {
104 : /* Assume there's about 52 mantissa bits; the sign contributes too. */
105 14 : int64 seed = ((double) ((UINT64CONST(1) << 52) - 1)) * fseed;
106 :
107 14 : pg_prng_seed(state, (uint64) seed);
108 14 : }
109 :
110 : /*
111 : * Validate a PRNG seed value.
112 : */
113 : bool
114 67540 : pg_prng_seed_check(pg_prng_state *state)
115 : {
116 : /*
117 : * If the seeding mechanism chanced to produce all-zeroes, insert
118 : * something nonzero. Anything would do; use Knuth's LCG parameters.
119 : */
120 67540 : if (unlikely(state->s0 == 0 && state->s1 == 0))
121 : {
122 0 : state->s0 = UINT64CONST(0x5851F42D4C957F2D);
123 0 : state->s1 = UINT64CONST(0x14057B7EF767814F);
124 : }
125 :
126 : /* As a convenience for the pg_prng_strong_seed macro, return true */
127 67540 : return true;
128 : }
129 :
130 : /*
131 : * Select a random uint64 uniformly from the range [0, PG_UINT64_MAX].
132 : */
133 : uint64
134 3034 : pg_prng_uint64(pg_prng_state *state)
135 : {
136 3034 : return xoroshiro128ss(state);
137 : }
138 :
139 : /*
140 : * Select a random uint64 uniformly from the range [rmin, rmax].
141 : * If the range is empty, rmin is always produced.
142 : */
143 : uint64
144 2093660 : pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax)
145 : {
146 : uint64 val;
147 :
148 2093660 : if (likely(rmax > rmin))
149 : {
150 : /*
151 : * Use bitmask rejection method to generate an offset in 0..range.
152 : * Each generated val is less than twice "range", so on average we
153 : * should not have to iterate more than twice.
154 : */
155 2093332 : uint64 range = rmax - rmin;
156 2093332 : uint32 rshift = 63 - pg_leftmost_one_pos64(range);
157 :
158 : do
159 : {
160 3281088 : val = xoroshiro128ss(state) >> rshift;
161 3281088 : } while (val > range);
162 : }
163 : else
164 328 : val = 0;
165 :
166 2093660 : return rmin + val;
167 : }
168 :
169 : /*
170 : * Select a random int64 uniformly from the range [PG_INT64_MIN, PG_INT64_MAX].
171 : */
172 : int64
173 0 : pg_prng_int64(pg_prng_state *state)
174 : {
175 0 : return (int64) xoroshiro128ss(state);
176 : }
177 :
178 : /*
179 : * Select a random int64 uniformly from the range [0, PG_INT64_MAX].
180 : */
181 : int64
182 0 : pg_prng_int64p(pg_prng_state *state)
183 : {
184 0 : return (int64) (xoroshiro128ss(state) & UINT64CONST(0x7FFFFFFFFFFFFFFF));
185 : }
186 :
187 : /*
188 : * Select a random uint32 uniformly from the range [0, PG_UINT32_MAX].
189 : */
190 : uint32
191 60254 : pg_prng_uint32(pg_prng_state *state)
192 : {
193 : /*
194 : * Although xoroshiro128** is not known to have any weaknesses in
195 : * randomness of low-order bits, we prefer to use the upper bits of its
196 : * result here and below.
197 : */
198 60254 : uint64 v = xoroshiro128ss(state);
199 :
200 60254 : return (uint32) (v >> 32);
201 : }
202 :
203 : /*
204 : * Select a random int32 uniformly from the range [PG_INT32_MIN, PG_INT32_MAX].
205 : */
206 : int32
207 0 : pg_prng_int32(pg_prng_state *state)
208 : {
209 0 : uint64 v = xoroshiro128ss(state);
210 :
211 0 : return (int32) (v >> 32);
212 : }
213 :
214 : /*
215 : * Select a random int32 uniformly from the range [0, PG_INT32_MAX].
216 : */
217 : int32
218 2 : pg_prng_int32p(pg_prng_state *state)
219 : {
220 2 : uint64 v = xoroshiro128ss(state);
221 :
222 2 : return (int32) (v >> 33);
223 : }
224 :
225 : /*
226 : * Select a random double uniformly from the range [0.0, 1.0).
227 : *
228 : * Note: if you want a result in the range (0.0, 1.0], the standard way
229 : * to get that is "1.0 - pg_prng_double(state)".
230 : */
231 : double
232 1378068 : pg_prng_double(pg_prng_state *state)
233 : {
234 1378068 : uint64 v = xoroshiro128ss(state);
235 :
236 : /*
237 : * As above, assume there's 52 mantissa bits in a double. This result
238 : * could round to 1.0 if double's precision is less than that; but we
239 : * assume IEEE float arithmetic elsewhere in Postgres, so this seems OK.
240 : */
241 1378068 : return ldexp((double) (v >> (64 - 52)), -52);
242 : }
243 :
244 : /*
245 : * Select a random double from the normal distribution with
246 : * mean = 0.0 and stddev = 1.0.
247 : *
248 : * To get a result from a different normal distribution use
249 : * STDDEV * pg_prng_double_normal() + MEAN
250 : *
251 : * Uses https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform
252 : */
253 : double
254 13326 : pg_prng_double_normal(pg_prng_state *state)
255 : {
256 : double u1,
257 : u2,
258 : z0;
259 :
260 : /*
261 : * pg_prng_double generates [0, 1), but for the basic version of the
262 : * Box-Muller transform the two uniformly distributed random numbers are
263 : * expected to be in (0, 1]; in particular we'd better not compute log(0).
264 : */
265 13326 : u1 = 1.0 - pg_prng_double(state);
266 13326 : u2 = 1.0 - pg_prng_double(state);
267 :
268 : /* Apply Box-Muller transform to get one normal-valued output */
269 13326 : z0 = sqrt(-2.0 * log(u1)) * sin(2.0 * M_PI * u2);
270 13326 : return z0;
271 : }
272 :
273 : /*
274 : * Select a random boolean value.
275 : */
276 : bool
277 829742 : pg_prng_bool(pg_prng_state *state)
278 : {
279 829742 : uint64 v = xoroshiro128ss(state);
280 :
281 829742 : return (bool) (v >> 63);
282 : }
|
