1/*
2 * Copyright 2011-present Facebook, Inc.
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
33namespace 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 */
52class ThreadLocalPRNG {
53 public:
54 using result_type = uint32_t;
55
56 result_type operator()();
57
58 static constexpr result_type min() {
59 return std::numeric_limits<result_type>::min();
60 }
61 static constexpr result_type max() {
62 return std::numeric_limits<result_type>::max();
63 }
64};
65
66class 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
79 result_type operator()() {
80 return Random::secureRandom<result_type>();
81 }
82
83 static constexpr result_type min() {
84 return std::numeric_limits<result_type>::min();
85 }
86
87 static constexpr result_type max() {
88 return std::numeric_limits<result_type>::max();
89 }
90 };
91
92 public:
93 // Default generator type.
94#if FOLLY_HAVE_EXTRANDOM_SFMT19937
95 typedef __gnu_cxx::sfmt19937 DefaultGenerator;
96#else
97 typedef std::mt19937 DefaultGenerator;
98#endif
99
100 /**
101 * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
102 */
103 static void secureRandom(void* data, size_t len);
104
105 /**
106 * Shortcut to get a secure random value of integral type.
107 */
108 template <class T>
109 static typename std::enable_if<
110 std::is_integral<T>::value && !std::is_same<T, bool>::value,
111 T>::type
112 secureRandom() {
113 T val;
114 secureRandom(&val, sizeof(val));
115 return val;
116 }
117
118 /**
119 * Returns a secure random uint32_t
120 */
121 static uint32_t secureRand32() {
122 return secureRandom<uint32_t>();
123 }
124
125 /**
126 * Returns a secure random uint32_t in [0, max). If max == 0, returns 0.
127 */
128 static uint32_t secureRand32(uint32_t max) {
129 SecureRNG<uint32_t> srng;
130 return rand32(max, srng);
131 }
132
133 /**
134 * Returns a secure random uint32_t in [min, max). If min == max, returns 0.
135 */
136 static uint32_t secureRand32(uint32_t min, uint32_t max) {
137 SecureRNG<uint32_t> srng;
138 return rand32(min, max, srng);
139 }
140
141 /**
142 * Returns a secure random uint64_t
143 */
144 static uint64_t secureRand64() {
145 return secureRandom<uint64_t>();
146 }
147
148 /**
149 * Returns a secure random uint64_t in [0, max). If max == 0, returns 0.
150 */
151 static uint64_t secureRand64(uint64_t max) {
152 SecureRNG<uint64_t> srng;
153 return rand64(max, srng);
154 }
155
156 /**
157 * Returns a secure random uint64_t in [min, max). If min == max, returns 0.
158 */
159 static uint64_t secureRand64(uint64_t min, uint64_t max) {
160 SecureRNG<uint64_t> srng;
161 return rand64(min, max, srng);
162 }
163
164 /**
165 * Returns true 1/n of the time. If n == 0, always returns false
166 */
167 static bool secureOneIn(uint32_t n) {
168 SecureRNG<uint32_t> srng;
169 return rand32(0, n, srng) == 0;
170 }
171
172 /**
173 * Returns a secure double in [0, 1)
174 */
175 static double secureRandDouble01() {
176 SecureRNG<uint64_t> srng;
177 return randDouble01(srng);
178 }
179
180 /**
181 * Returns a secure double in [min, max), if min == max, returns 0.
182 */
183 static double secureRandDouble(double min, double max) {
184 SecureRNG<uint64_t> srng;
185 return randDouble(min, max, srng);
186 }
187
188 /**
189 * (Re-)Seed an existing RNG with a good seed.
190 *
191 * Note that you should usually use ThreadLocalPRNG unless you need
192 * reproducibility (such as during a test), in which case you'd want
193 * to create a RNG with a good seed in production, and seed it yourself
194 * in test.
195 */
196 template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
197 static void seed(RNG& rng);
198
199 /**
200 * Create a new RNG, seeded with a good seed.
201 *
202 * Note that you should usually use ThreadLocalPRNG unless you need
203 * reproducibility (such as during a test), in which case you'd want
204 * to create a RNG with a good seed in production, and seed it yourself
205 * in test.
206 */
207 template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
208 static RNG create();
209
210 /**
211 * Returns a random uint32_t
212 */
213 static uint32_t rand32() {
214 return rand32(ThreadLocalPRNG());
215 }
216
217 /**
218 * Returns a random uint32_t given a specific RNG
219 */
220 template <class RNG, class /* EnableIf */ = ValidRNG<RNG>>
221 static uint32_t rand32(RNG&& rng) {
222 return rng();
223 }
224
225 /**
226 * Returns a random uint32_t in [0, max). If max == 0, returns 0.
227 */
228 static uint32_t rand32(uint32_t max) {
229 return rand32(0, max, ThreadLocalPRNG());
230 }
231
232 /**
233 * Returns a random uint32_t in [0, max) given a specific RNG.
234 * If max == 0, returns 0.
235 */
236 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
237 static uint32_t rand32(uint32_t max, RNG&& rng) {
238 return rand32(0, max, rng);
239 }
240
241 /**
242 * Returns a random uint32_t in [min, max). If min == max, returns 0.
243 */
244 static uint32_t rand32(uint32_t min, uint32_t max) {
245 return rand32(min, max, ThreadLocalPRNG());
246 }
247
248 /**
249 * Returns a random uint32_t in [min, max) given a specific RNG.
250 * If min == max, returns 0.
251 */
252 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
253 static uint32_t rand32(uint32_t min, uint32_t max, RNG&& rng) {
254 if (min == max) {
255 return 0;
256 }
257 return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
258 }
259
260 /**
261 * Returns a random uint64_t
262 */
263 static uint64_t rand64() {
264 return rand64(ThreadLocalPRNG());
265 }
266
267 /**
268 * Returns a random uint64_t
269 */
270 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
271 static uint64_t rand64(RNG&& rng) {
272 return ((uint64_t)rng() << 32) | rng();
273 }
274
275 /**
276 * Returns a random uint64_t in [0, max). If max == 0, returns 0.
277 */
278 static uint64_t rand64(uint64_t max) {
279 return rand64(0, max, ThreadLocalPRNG());
280 }
281
282 /**
283 * Returns a random uint64_t in [0, max). If max == 0, returns 0.
284 */
285 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
286 static uint64_t rand64(uint64_t max, RNG&& rng) {
287 return rand64(0, max, rng);
288 }
289
290 /**
291 * Returns a random uint64_t in [min, max). If min == max, returns 0.
292 */
293 static uint64_t rand64(uint64_t min, uint64_t max) {
294 return rand64(min, max, ThreadLocalPRNG());
295 }
296
297 /**
298 * Returns a random uint64_t in [min, max). If min == max, returns 0.
299 */
300 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
301 static uint64_t rand64(uint64_t min, uint64_t max, RNG&& rng) {
302 if (min == max) {
303 return 0;
304 }
305 return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
306 }
307
308 /**
309 * Returns true 1/n of the time. If n == 0, always returns false
310 */
311 static bool oneIn(uint32_t n) {
312 return oneIn(n, ThreadLocalPRNG());
313 }
314
315 /**
316 * Returns true 1/n of the time. If n == 0, always returns false
317 */
318 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
319 static bool oneIn(uint32_t n, RNG&& rng) {
320 if (n == 0) {
321 return false;
322 }
323 return rand32(0, n, rng) == 0;
324 }
325
326 /**
327 * Returns a double in [0, 1)
328 */
329 static double randDouble01() {
330 return randDouble01(ThreadLocalPRNG());
331 }
332
333 /**
334 * Returns a double in [0, 1)
335 */
336 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
337 static double randDouble01(RNG&& rng) {
338 return std::generate_canonical<double, std::numeric_limits<double>::digits>(
339 rng);
340 }
341
342 /**
343 * Returns a double in [min, max), if min == max, returns 0.
344 */
345 static double randDouble(double min, double max) {
346 return randDouble(min, max, ThreadLocalPRNG());
347 }
348
349 /**
350 * Returns a double in [min, max), if min == max, returns 0.
351 */
352 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
353 static double randDouble(double min, double max, RNG&& rng) {
354 if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
355 return 0;
356 }
357 return std::uniform_real_distribution<double>(min, max)(rng);
358 }
359};
360
361/*
362 * Return a good seed for a random number generator.
363 * Note that this is a legacy function, as it returns a 32-bit value, which
364 * is too small to be useful as a "real" RNG seed. Use the functions in class
365 * Random instead.
366 */
367inline uint32_t randomNumberSeed() {
368 return Random::rand32();
369}
370
371} // namespace folly
372
373#include <folly/Random-inl.h>
374