PostgreSQL Source Code  git master
pg_prng.c
Go to the documentation of this file.
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-2022, PostgreSQL Global Development Group
14  *
15  * src/common/pg_prng.c
16  *
17  *-------------------------------------------------------------------------
18  */
19 
20 #include "c.h"
21 
22 #include <math.h> /* for ldexp() */
23 
24 #include "common/pg_prng.h"
25 #include "port/pg_bitutils.h"
26 
27 /* process-wide state vector */
29 
30 
31 /*
32  * 64-bit rotate left
33  */
34 static inline uint64
35 rotl(uint64 x, int bits)
36 {
37  return (x << bits) | (x >> (64 - bits));
38 }
39 
40 /*
41  * The basic xoroshiro128** algorithm.
42  * Generates and returns a 64-bit uniformly distributed number,
43  * updating the state vector for next time.
44  *
45  * Note: the state vector must not be all-zeroes, as that is a fixed point.
46  */
47 static uint64
49 {
50  uint64 s0 = state->s0,
51  sx = state->s1 ^ s0,
52  val = rotl(s0 * 5, 7) * 9;
53 
54  /* update state */
55  state->s0 = rotl(s0, 24) ^ sx ^ (sx << 16);
56  state->s1 = rotl(sx, 37);
57 
58  return val;
59 }
60 
61 /*
62  * We use this generator just to fill the xoroshiro128** state vector
63  * from a 64-bit seed.
64  */
65 static uint64
66 splitmix64(uint64 *state)
67 {
68  /* state update */
69  uint64 val = (*state += UINT64CONST(0x9E3779B97f4A7C15));
70 
71  /* value extraction */
72  val = (val ^ (val >> 30)) * UINT64CONST(0xBF58476D1CE4E5B9);
73  val = (val ^ (val >> 27)) * UINT64CONST(0x94D049BB133111EB);
74 
75  return val ^ (val >> 31);
76 }
77 
78 /*
79  * Initialize the PRNG state from a 64-bit integer,
80  * taking care that we don't produce all-zeroes.
81  */
82 void
84 {
85  state->s0 = splitmix64(&seed);
86  state->s1 = splitmix64(&seed);
87  /* Let's just make sure we didn't get all-zeroes */
88  (void) pg_prng_seed_check(state);
89 }
90 
91 /*
92  * Initialize the PRNG state from a double in the range [-1.0, 1.0],
93  * taking care that we don't produce all-zeroes.
94  */
95 void
97 {
98  /* Assume there's about 52 mantissa bits; the sign contributes too. */
99  int64 seed = ((double) ((UINT64CONST(1) << 52) - 1)) * fseed;
100 
101  pg_prng_seed(state, (uint64) seed);
102 }
103 
104 /*
105  * Validate a PRNG seed value.
106  */
107 bool
109 {
110  /*
111  * If the seeding mechanism chanced to produce all-zeroes, insert
112  * something nonzero. Anything would do; use Knuth's LCG parameters.
113  */
114  if (unlikely(state->s0 == 0 && state->s1 == 0))
115  {
116  state->s0 = UINT64CONST(0x5851F42D4C957F2D);
117  state->s1 = UINT64CONST(0x14057B7EF767814F);
118  }
119 
120  /* As a convenience for the pg_prng_strong_seed macro, return true */
121  return true;
122 }
123 
124 /*
125  * Select a random uint64 uniformly from the range [0, PG_UINT64_MAX].
126  */
127 uint64
129 {
130  return xoroshiro128ss(state);
131 }
132 
133 /*
134  * Select a random uint64 uniformly from the range [rmin, rmax].
135  * If the range is empty, rmin is always produced.
136  */
137 uint64
138 pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax)
139 {
140  uint64 val;
141 
142  if (likely(rmax > rmin))
143  {
144  /*
145  * Use bitmask rejection method to generate an offset in 0..range.
146  * Each generated val is less than twice "range", so on average we
147  * should not have to iterate more than twice.
148  */
149  uint64 range = rmax - rmin;
150  uint32 rshift = 63 - pg_leftmost_one_pos64(range);
151 
152  do
153  {
154  val = xoroshiro128ss(state) >> rshift;
155  } while (val > range);
156  }
157  else
158  val = 0;
159 
160  return rmin + val;
161 }
162 
163 /*
164  * Select a random int64 uniformly from the range [PG_INT64_MIN, PG_INT64_MAX].
165  */
166 int64
168 {
169  return (int64) xoroshiro128ss(state);
170 }
171 
172 /*
173  * Select a random int64 uniformly from the range [0, PG_INT64_MAX].
174  */
175 int64
177 {
178  return (int64) (xoroshiro128ss(state) & UINT64CONST(0x7FFFFFFFFFFFFFFF));
179 }
180 
181 /*
182  * Select a random uint32 uniformly from the range [0, PG_UINT32_MAX].
183  */
184 uint32
186 {
187  /*
188  * Although xoroshiro128** is not known to have any weaknesses in
189  * randomness of low-order bits, we prefer to use the upper bits of its
190  * result here and below.
191  */
192  uint64 v = xoroshiro128ss(state);
193 
194  return (uint32) (v >> 32);
195 }
196 
197 /*
198  * Select a random int32 uniformly from the range [PG_INT32_MIN, PG_INT32_MAX].
199  */
200 int32
202 {
203  uint64 v = xoroshiro128ss(state);
204 
205  return (int32) (v >> 32);
206 }
207 
208 /*
209  * Select a random int32 uniformly from the range [0, PG_INT32_MAX].
210  */
211 int32
213 {
214  uint64 v = xoroshiro128ss(state);
215 
216  return (int32) (v >> 33);
217 }
218 
219 /*
220  * Select a random double uniformly from the range [0.0, 1.0).
221  *
222  * Note: if you want a result in the range (0.0, 1.0], the standard way
223  * to get that is "1.0 - pg_prng_double(state)".
224  */
225 double
227 {
228  uint64 v = xoroshiro128ss(state);
229 
230  /*
231  * As above, assume there's 52 mantissa bits in a double. This result
232  * could round to 1.0 if double's precision is less than that; but we
233  * assume IEEE float arithmetic elsewhere in Postgres, so this seems OK.
234  */
235  return ldexp((double) (v >> (64 - 52)), -52);
236 }
237 
238 /*
239  * Select a random boolean value.
240  */
241 bool
243 {
244  uint64 v = xoroshiro128ss(state);
245 
246  return (bool) (v >> 63);
247 }
unsigned int uint32
Definition: c.h:441
#define likely(x)
Definition: c.h:272
signed int int32
Definition: c.h:429
#define unlikely(x)
Definition: c.h:273
long val
Definition: informix.c:664
int x
Definition: isn.c:71
static int pg_leftmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:49
double pg_prng_double(pg_prng_state *state)
Definition: pg_prng.c:226
uint64 pg_prng_uint64_range(pg_prng_state *state, uint64 rmin, uint64 rmax)
Definition: pg_prng.c:138
int32 pg_prng_int32(pg_prng_state *state)
Definition: pg_prng.c:201
static uint64 splitmix64(uint64 *state)
Definition: pg_prng.c:66
uint32 pg_prng_uint32(pg_prng_state *state)
Definition: pg_prng.c:185
uint64 pg_prng_uint64(pg_prng_state *state)
Definition: pg_prng.c:128
int32 pg_prng_int32p(pg_prng_state *state)
Definition: pg_prng.c:212
int64 pg_prng_int64(pg_prng_state *state)
Definition: pg_prng.c:167
void pg_prng_seed(pg_prng_state *state, uint64 seed)
Definition: pg_prng.c:83
pg_prng_state pg_global_prng_state
Definition: pg_prng.c:28
int64 pg_prng_int64p(pg_prng_state *state)
Definition: pg_prng.c:176
static uint64 rotl(uint64 x, int bits)
Definition: pg_prng.c:35
bool pg_prng_seed_check(pg_prng_state *state)
Definition: pg_prng.c:108
bool pg_prng_bool(pg_prng_state *state)
Definition: pg_prng.c:242
void pg_prng_fseed(pg_prng_state *state, double fseed)
Definition: pg_prng.c:96
static uint64 xoroshiro128ss(pg_prng_state *state)
Definition: pg_prng.c:48
static struct cvec * range(struct vars *v, chr a, chr b, int cases)
Definition: regc_locale.c:412
Definition: regguts.h:318