2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #define FOLLY_RANDOM_H_
23 #include <type_traits>
25 #include <folly/Portability.h>
26 #include <folly/Traits.h>
28 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
35 * A PRNG with one instance per thread. This PRNG uses a mersenne twister random
36 * number generator and is seeded from /dev/urandom. It should not be used for
37 * anything which requires security, only for statistical randomness.
39 * An instance of this class represents the current threads PRNG. This means
40 * copying an instance of this class across threads will result in corruption
42 * Most users will use the Random class which implicitly creates this class.
43 * However, if you are worried about performance, you can memoize the TLS
44 * lookups that get the per thread state by manually using this class:
46 * ThreadLocalPRNG rng;
48 * Random::rand32(rng);
51 class ThreadLocalPRNG {
53 using result_type = uint32_t;
55 result_type operator()() {
56 // Using a static method allows the compiler to avoid allocating stack space
58 return getImpl(local_);
61 static constexpr result_type min() {
62 return std::numeric_limits<result_type>::min();
64 static constexpr result_type max() {
65 return std::numeric_limits<result_type>::max();
71 class LocalInstancePRNG;
74 static result_type getImpl(LocalInstancePRNG* local);
75 LocalInstancePRNG* local_;
81 using ValidRNG = typename std::enable_if<
82 std::is_unsigned<typename std::result_of<RNG&()>::type>::value,
88 using result_type = typename std::enable_if<
89 std::is_integral<T>::value && !std::is_same<T, bool>::value,
92 result_type operator()() {
93 return Random::secureRandom<result_type>();
96 static constexpr result_type min() {
97 return std::numeric_limits<result_type>::min();
100 static constexpr result_type max() {
101 return std::numeric_limits<result_type>::max();
106 // Default generator type.
107 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
108 typedef __gnu_cxx::sfmt19937 DefaultGenerator;
110 typedef std::mt19937 DefaultGenerator;
114 * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
116 static void secureRandom(void* data, size_t len);
119 * Shortcut to get a secure random value of integral type.
122 static typename std::enable_if<
123 std::is_integral<T>::value && !std::is_same<T, bool>::value,
127 secureRandom(&val, sizeof(val));
132 * Returns a secure random uint32_t
134 static uint32_t secureRand32() {
135 return secureRandom<uint32_t>();
139 * Returns a secure random uint32_t in [0, max). If max == 0, returns 0.
141 static uint32_t secureRand32(uint32_t max) {
142 SecureRNG<uint32_t> srng;
143 return rand32(max, srng);
147 * Returns a secure random uint32_t in [min, max). If min == max, returns 0.
149 static uint32_t secureRand32(uint32_t min, uint32_t max) {
150 SecureRNG<uint32_t> srng;
151 return rand32(min, max, srng);
155 * Returns a secure random uint64_t
157 static uint64_t secureRand64() {
158 return secureRandom<uint64_t>();
162 * Returns a secure random uint64_t in [0, max). If max == 0, returns 0.
164 static uint64_t secureRand64(uint64_t max) {
165 SecureRNG<uint64_t> srng;
166 return rand64(max, srng);
170 * Returns a secure random uint64_t in [min, max). If min == max, returns 0.
172 static uint64_t secureRand64(uint64_t min, uint64_t max) {
173 SecureRNG<uint64_t> srng;
174 return rand64(min, max, srng);
178 * Returns true 1/n of the time. If n == 0, always returns false
180 static bool secureOneIn(uint32_t n) {
181 SecureRNG<uint32_t> srng;
182 return rand32(0, n, srng) == 0;
186 * Returns a secure double in [0, 1)
188 static double secureRandDouble01() {
189 SecureRNG<uint64_t> srng;
190 return randDouble01(srng);
194 * Returns a secure double in [min, max), if min == max, returns 0.
196 static double secureRandDouble(double min, double max) {
197 SecureRNG<uint64_t> srng;
198 return randDouble(min, max, srng);
202 * (Re-)Seed an existing RNG with a good seed.
204 * Note that you should usually use ThreadLocalPRNG unless you need
205 * reproducibility (such as during a test), in which case you'd want
206 * to create a RNG with a good seed in production, and seed it yourself
209 template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
210 static void seed(RNG& rng);
213 * Create a new RNG, seeded with a good seed.
215 * Note that you should usually use ThreadLocalPRNG unless you need
216 * reproducibility (such as during a test), in which case you'd want
217 * to create a RNG with a good seed in production, and seed it yourself
220 template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
224 * Returns a random uint32_t
226 static uint32_t rand32() {
227 return rand32(ThreadLocalPRNG());
231 * Returns a random uint32_t given a specific RNG
233 template <class RNG, class /* EnableIf */ = ValidRNG<RNG>>
234 static uint32_t rand32(RNG&& rng) {
239 * Returns a random uint32_t in [0, max). If max == 0, returns 0.
241 static uint32_t rand32(uint32_t max) {
242 return rand32(0, max, ThreadLocalPRNG());
246 * Returns a random uint32_t in [0, max) given a specific RNG.
247 * If max == 0, returns 0.
249 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
250 static uint32_t rand32(uint32_t max, RNG&& rng) {
251 return rand32(0, max, rng);
255 * Returns a random uint32_t in [min, max). If min == max, returns 0.
257 static uint32_t rand32(uint32_t min, uint32_t max) {
258 return rand32(min, max, ThreadLocalPRNG());
262 * Returns a random uint32_t in [min, max) given a specific RNG.
263 * If min == max, returns 0.
265 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
266 static uint32_t rand32(uint32_t min, uint32_t max, RNG&& rng) {
270 return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
274 * Returns a random uint64_t
276 static uint64_t rand64() {
277 return rand64(ThreadLocalPRNG());
281 * Returns a random uint64_t
283 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
284 static uint64_t rand64(RNG&& rng) {
285 return ((uint64_t)rng() << 32) | rng();
289 * Returns a random uint64_t in [0, max). If max == 0, returns 0.
291 static uint64_t rand64(uint64_t max) {
292 return rand64(0, max, ThreadLocalPRNG());
296 * Returns a random uint64_t in [0, max). If max == 0, returns 0.
298 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
299 static uint64_t rand64(uint64_t max, RNG&& rng) {
300 return rand64(0, max, rng);
304 * Returns a random uint64_t in [min, max). If min == max, returns 0.
306 static uint64_t rand64(uint64_t min, uint64_t max) {
307 return rand64(min, max, ThreadLocalPRNG());
311 * Returns a random uint64_t in [min, max). If min == max, returns 0.
313 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
314 static uint64_t rand64(uint64_t min, uint64_t max, RNG&& rng) {
318 return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
322 * Returns true 1/n of the time. If n == 0, always returns false
324 static bool oneIn(uint32_t n) {
325 return oneIn(n, ThreadLocalPRNG());
329 * Returns true 1/n of the time. If n == 0, always returns false
331 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
332 static bool oneIn(uint32_t n, RNG&& rng) {
336 return rand32(0, n, rng) == 0;
340 * Returns a double in [0, 1)
342 static double randDouble01() {
343 return randDouble01(ThreadLocalPRNG());
347 * Returns a double in [0, 1)
349 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
350 static double randDouble01(RNG&& rng) {
351 return std::generate_canonical<double, std::numeric_limits<double>::digits>(
356 * Returns a double in [min, max), if min == max, returns 0.
358 static double randDouble(double min, double max) {
359 return randDouble(min, max, ThreadLocalPRNG());
363 * Returns a double in [min, max), if min == max, returns 0.
365 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
366 static double randDouble(double min, double max, RNG&& rng) {
367 if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
370 return std::uniform_real_distribution<double>(min, max)(rng);
375 * Return a good seed for a random number generator.
376 * Note that this is a legacy function, as it returns a 32-bit value, which
377 * is too small to be useful as a "real" RNG seed. Use the functions in class
380 inline uint32_t randomNumberSeed() {
381 return Random::rand32();
386 #include <folly/Random-inl.h>