1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #pragma once
18 #define FOLLY_RANDOM_H_
19
20 #include <array>
21 #include <cstdint>
22 #include <random>
23 #include <type_traits>
24
25 #include <folly/Portability.h>
26 #include <folly/Traits.h>
27 #include <folly/functional/Invoke.h>
28
29 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
30 #include <ext/random>
31 #endif
32
33 namespace folly {
34
35 /**
36 * A PRNG with one instance per thread. This PRNG uses a mersenne twister random
37 * number generator and is seeded from /dev/urandom. It should not be used for
38 * anything which requires security, only for statistical randomness.
39 *
40 * An instance of this class represents the current threads PRNG. This means
41 * copying an instance of this class across threads will result in corruption
42 *
43 * Most users will use the Random class which implicitly creates this class.
44 * However, if you are worried about performance, you can memoize the TLS
45 * lookups that get the per thread state by manually using this class:
46 *
47 * ThreadLocalPRNG rng;
48 * for (...) {
49 * Random::rand32(rng);
50 * }
51 */
52 class ThreadLocalPRNG {
53 public:
54 using result_type = uint32_t;
55
56 result_type operator()();
57
min()58 static constexpr result_type min() {
59 return std::numeric_limits<result_type>::min();
60 }
max()61 static constexpr result_type max() {
62 return std::numeric_limits<result_type>::max();
63 }
64 };
65
66 class Random {
67 private:
68 template <class RNG>
69 using ValidRNG = typename std::
70 enable_if<std::is_unsigned<invoke_result_t<RNG&>>::value, RNG>::type;
71
72 template <class T>
73 class SecureRNG {
74 public:
75 using result_type = typename std::enable_if<
76 std::is_integral<T>::value && !std::is_same<T, bool>::value,
77 T>::type;
78
operator()79 result_type operator()() { return Random::secureRandom<result_type>(); }
80
min()81 static constexpr result_type min() {
82 return std::numeric_limits<result_type>::min();
83 }
84
max()85 static constexpr result_type max() {
86 return std::numeric_limits<result_type>::max();
87 }
88 };
89
90 public:
91 // Default generator type.
92 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
93 typedef __gnu_cxx::sfmt19937 DefaultGenerator;
94 #else
95 typedef std::mt19937 DefaultGenerator;
96 #endif
97
98 /**
99 * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
100 */
101 static void secureRandom(void* data, size_t size);
102
103 /**
104 * Shortcut to get a secure random value of integral type.
105 */
106 template <class T>
107 static typename std::enable_if<
108 std::is_integral<T>::value && !std::is_same<T, bool>::value,
109 T>::type
secureRandom()110 secureRandom() {
111 T val;
112 secureRandom(&val, sizeof(val));
113 return val;
114 }
115
116 /**
117 * Returns a secure random uint32_t
118 */
secureRand32()119 static uint32_t secureRand32() { return secureRandom<uint32_t>(); }
120
121 /**
122 * Returns a secure random uint32_t in [0, max). If max == 0, returns 0.
123 */
secureRand32(uint32_t max)124 static uint32_t secureRand32(uint32_t max) {
125 SecureRNG<uint32_t> srng;
126 return rand32(max, srng);
127 }
128
129 /**
130 * Returns a secure random uint32_t in [min, max). If min == max, returns 0.
131 */
secureRand32(uint32_t min,uint32_t max)132 static uint32_t secureRand32(uint32_t min, uint32_t max) {
133 SecureRNG<uint32_t> srng;
134 return rand32(min, max, srng);
135 }
136
137 /**
138 * Returns a secure random uint64_t
139 */
secureRand64()140 static uint64_t secureRand64() { return secureRandom<uint64_t>(); }
141
142 /**
143 * Returns a secure random uint64_t in [0, max). If max == 0, returns 0.
144 */
secureRand64(uint64_t max)145 static uint64_t secureRand64(uint64_t max) {
146 SecureRNG<uint64_t> srng;
147 return rand64(max, srng);
148 }
149
150 /**
151 * Returns a secure random uint64_t in [min, max). If min == max, returns 0.
152 */
secureRand64(uint64_t min,uint64_t max)153 static uint64_t secureRand64(uint64_t min, uint64_t max) {
154 SecureRNG<uint64_t> srng;
155 return rand64(min, max, srng);
156 }
157
158 /**
159 * Returns true 1/n of the time. If n == 0, always returns false
160 */
secureOneIn(uint32_t n)161 static bool secureOneIn(uint32_t n) {
162 if (n < 2) {
163 return n;
164 }
165 SecureRNG<uint32_t> srng;
166 return rand32(0, n, srng) == 0;
167 }
168
169 /**
170 * Returns a secure double in [0, 1)
171 */
secureRandDouble01()172 static double secureRandDouble01() {
173 SecureRNG<uint64_t> srng;
174 return randDouble01(srng);
175 }
176
177 /**
178 * Returns a secure double in [min, max), if min == max, returns 0.
179 */
secureRandDouble(double min,double max)180 static double secureRandDouble(double min, double max) {
181 SecureRNG<uint64_t> srng;
182 return randDouble(min, max, srng);
183 }
184
185 /**
186 * (Re-)Seed an existing RNG with a good seed.
187 *
188 * Note that you should usually use ThreadLocalPRNG unless you need
189 * reproducibility (such as during a test), in which case you'd want
190 * to create a RNG with a good seed in production, and seed it yourself
191 * in test.
192 */
193 template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
194 static void seed(RNG& rng);
195
196 /**
197 * Create a new RNG, seeded with a good seed.
198 *
199 * Note that you should usually use ThreadLocalPRNG unless you need
200 * reproducibility (such as during a test), in which case you'd want
201 * to create a RNG with a good seed in production, and seed it yourself
202 * in test.
203 */
204 template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
205 static RNG create();
206
207 /**
208 * Returns a random uint32_t
209 */
rand32()210 static uint32_t rand32() { return rand32(ThreadLocalPRNG()); }
211
212 /**
213 * Returns a random uint32_t given a specific RNG
214 */
215 template <class RNG, class /* EnableIf */ = ValidRNG<RNG>>
rand32(RNG && rng)216 static uint32_t rand32(RNG&& rng) {
217 return rng();
218 }
219
220 /**
221 * Returns a random uint32_t in [0, max). If max == 0, returns 0.
222 */
rand32(uint32_t max)223 static uint32_t rand32(uint32_t max) {
224 return rand32(0, max, ThreadLocalPRNG());
225 }
226
227 /**
228 * Returns a random uint32_t in [0, max) given a specific RNG.
229 * If max == 0, returns 0.
230 */
231 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
rand32(uint32_t max,RNG && rng)232 static uint32_t rand32(uint32_t max, RNG&& rng) {
233 return rand32(0, max, rng);
234 }
235
236 /**
237 * Returns a random uint32_t in [min, max). If min == max, returns 0.
238 */
rand32(uint32_t min,uint32_t max)239 static uint32_t rand32(uint32_t min, uint32_t max) {
240 return rand32(min, max, ThreadLocalPRNG());
241 }
242
243 /**
244 * Returns a random uint32_t in [min, max) given a specific RNG.
245 * If min == max, returns 0.
246 */
247 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
rand32(uint32_t min,uint32_t max,RNG && rng)248 static uint32_t rand32(uint32_t min, uint32_t max, RNG&& rng) {
249 if (min == max) {
250 return 0;
251 }
252 return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
253 }
254
255 /**
256 * Returns a random uint64_t
257 */
rand64()258 static uint64_t rand64() { return rand64(ThreadLocalPRNG()); }
259
260 /**
261 * Returns a random uint64_t
262 */
263 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
rand64(RNG && rng)264 static uint64_t rand64(RNG&& rng) {
265 return ((uint64_t)rng() << 32) | rng();
266 }
267
268 /**
269 * Returns a random uint64_t in [0, max). If max == 0, returns 0.
270 */
rand64(uint64_t max)271 static uint64_t rand64(uint64_t max) {
272 return rand64(0, max, ThreadLocalPRNG());
273 }
274
275 /**
276 * Returns a random uint64_t in [0, max). If max == 0, returns 0.
277 */
278 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
rand64(uint64_t max,RNG && rng)279 static uint64_t rand64(uint64_t max, RNG&& rng) {
280 return rand64(0, max, rng);
281 }
282
283 /**
284 * Returns a random uint64_t in [min, max). If min == max, returns 0.
285 */
rand64(uint64_t min,uint64_t max)286 static uint64_t rand64(uint64_t min, uint64_t max) {
287 return rand64(min, max, ThreadLocalPRNG());
288 }
289
290 /**
291 * Returns a random uint64_t in [min, max). If min == max, returns 0.
292 */
293 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
rand64(uint64_t min,uint64_t max,RNG && rng)294 static uint64_t rand64(uint64_t min, uint64_t max, RNG&& rng) {
295 if (min == max) {
296 return 0;
297 }
298 return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
299 }
300
301 /**
302 * Returns true 1/n of the time. If n == 0, always returns false
303 */
oneIn(uint32_t n)304 static bool oneIn(uint32_t n) { return oneIn(n, ThreadLocalPRNG()); }
305
306 /**
307 * Returns true 1/n of the time. If n == 0, always returns false
308 */
309 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
oneIn(uint32_t n,RNG && rng)310 static bool oneIn(uint32_t n, RNG&& rng) {
311 if (n < 2) {
312 return n;
313 }
314 return rand32(0, n, rng) == 0;
315 }
316
317 /**
318 * Returns a double in [0, 1)
319 */
randDouble01()320 static double randDouble01() { return randDouble01(ThreadLocalPRNG()); }
321
322 /**
323 * Returns a double in [0, 1)
324 */
325 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
randDouble01(RNG && rng)326 static double randDouble01(RNG&& rng) {
327 return std::generate_canonical<double, std::numeric_limits<double>::digits>(
328 rng);
329 }
330
331 /**
332 * Returns a double in [min, max), if min == max, returns 0.
333 */
randDouble(double min,double max)334 static double randDouble(double min, double max) {
335 return randDouble(min, max, ThreadLocalPRNG());
336 }
337
338 /**
339 * Returns a double in [min, max), if min == max, returns 0.
340 */
341 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
randDouble(double min,double max,RNG && rng)342 static double randDouble(double min, double max, RNG&& rng) {
343 if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
344 return 0;
345 }
346 return std::uniform_real_distribution<double>(min, max)(rng);
347 }
348 };
349
350 /*
351 * Return a good seed for a random number generator.
352 * Note that this is a legacy function, as it returns a 32-bit value, which
353 * is too small to be useful as a "real" RNG seed. Use the functions in class
354 * Random instead.
355 */
randomNumberSeed()356 inline uint32_t randomNumberSeed() {
357 return Random::rand32();
358 }
359
360 } // namespace folly
361
362 #include <folly/Random-inl.h>
363