作者
digoal
日期
2021-12-02
标签
PostgreSQL , PRNG API , Pseudo-Random Number Generator
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=3804539e48e794781c6145c7f988f5d507418fa8
Replace random(), pg_erand48(), etc with a better PRNG API and algorithm.
author Tom Lane <tgl@sss.pgh.pa.us>
Mon, 29 Nov 2021 02:32:36 +0000 (21:32 -0500)
committer Tom Lane <tgl@sss.pgh.pa.us>
Mon, 29 Nov 2021 02:33:07 +0000 (21:33 -0500)
commit 3804539e48e794781c6145c7f988f5d507418fa8
tree 317904b43ca8c1d510b23cb8fdd7b05a75e971bc tree
parent f44ceb46ec2d8da48f6e145bf462d5620c25e079 commit | diff
Replace random(), pg_erand48(), etc with a better PRNG API and algorithm.
Standardize on xoroshiro128** as our basic PRNG algorithm, eliminating
a bunch of platform dependencies as well as fundamentally-obsolete PRNG
code. In addition, this API replacement will ease replacing the
algorithm again in future, should that become necessary.
xoroshiro128** is a few percent slower than the drand48 family,
but it can produce full-width 64-bit random values not only 48-bit,
and it should be much more trustworthy. It's likely to be noticeably
faster than the platform's random(), depending on which platform you
are thinking about; and we can have non-global state vectors easily,
unlike with random(). It is not cryptographically strong, but neither
are the functions it replaces.
Fabien Coelho, reviewed by Dean Rasheed, Aleksander Alekseev, and myself
Discussion: https://postgr.es/m/alpine.DEB.2.22.394.2105241211230.165418@pseudo
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, 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 */
28 pg_prng_state pg_global_prng_state;
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
48 xoroshiro128ss(pg_prng_state *state)
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
83 pg_prng_seed(pg_prng_state *state, uint64 seed)
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
96 pg_prng_fseed(pg_prng_state *state, double fseed)
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
108 pg_prng_seed_check(pg_prng_state *state)
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
128 pg_prng_uint64(pg_prng_state *state)
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
167 pg_prng_int64(pg_prng_state *state)
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
176 pg_prng_int64p(pg_prng_state *state)
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
185 pg_prng_uint32(pg_prng_state *state)
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
201 pg_prng_int32(pg_prng_state *state)
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
212 pg_prng_int32p(pg_prng_state *state)
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
226 pg_prng_double(pg_prng_state *state)
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
242 pg_prng_bool(pg_prng_state *state)
243 {
244 uint64 v = xoroshiro128ss(state);
245
246 return (bool) (v >> 63);
247 }
期望 PostgreSQL 增加什么功能?
类似Oracle RAC架构的PostgreSQL已开源: 阿里云PolarDB for PostgreSQL云原生分布式开源数据库!
PostgreSQL 解决方案集合
德哥 / digoal's github - 公益是一辈子的事.
「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」
关注作者
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文章的来源（墨天轮），文章链接，文章作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
