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 typedef uint32_t result_type;
55 uint32_t 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_;
83 using ValidRNG = typename std::enable_if<
84 std::is_unsigned<typename std::result_of<RNG&()>::type>::value,
88 // Default generator type.
89 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
90 typedef __gnu_cxx::sfmt19937 DefaultGenerator;
92 typedef std::mt19937 DefaultGenerator;
96 * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
98 static void secureRandom(void* data, size_t len);
101 * Shortcut to get a secure random value of integral type.
104 static typename std::enable_if<
105 std::is_integral<T>::value && !std::is_same<T,bool>::value,
109 secureRandom(&val, sizeof(val));
114 * (Re-)Seed an existing RNG with a good seed.
116 * Note that you should usually use ThreadLocalPRNG unless you need
117 * reproducibility (such as during a test), in which case you'd want
118 * to create a RNG with a good seed in production, and seed it yourself
121 template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
122 static void seed(RNG& rng);
125 * Create a new RNG, seeded with a good seed.
127 * Note that you should usually use ThreadLocalPRNG unless you need
128 * reproducibility (such as during a test), in which case you'd want
129 * to create a RNG with a good seed in production, and seed it yourself
132 template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
136 * Returns a random uint32_t
138 static uint32_t rand32() {
139 return rand32(ThreadLocalPRNG());
143 * Returns a random uint32_t given a specific RNG
145 template <class RNG, class /* EnableIf */ = ValidRNG<RNG>>
146 static uint32_t rand32(RNG&& rng) {
151 * Returns a random uint32_t in [0, max). If max == 0, returns 0.
153 static uint32_t rand32(uint32_t max) {
154 return rand32(0, max, ThreadLocalPRNG());
158 * Returns a random uint32_t in [0, max) given a specific RNG.
159 * If max == 0, returns 0.
161 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
162 static uint32_t rand32(uint32_t max, RNG&& rng) {
163 return rand32(0, max, rng);
167 * Returns a random uint32_t in [min, max). If min == max, returns 0.
169 static uint32_t rand32(uint32_t min, uint32_t max) {
170 return rand32(min, max, ThreadLocalPRNG());
174 * Returns a random uint32_t in [min, max) given a specific RNG.
175 * If min == max, returns 0.
177 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
178 static uint32_t rand32(uint32_t min, uint32_t max, RNG&& rng) {
182 return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
186 * Returns a random uint64_t
188 static uint64_t rand64() {
189 return rand64(ThreadLocalPRNG());
193 * Returns a random uint64_t
195 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
196 static uint64_t rand64(RNG&& rng) {
197 return ((uint64_t)rng() << 32) | rng();
201 * Returns a random uint64_t in [0, max). If max == 0, returns 0.
203 static uint64_t rand64(uint64_t max) {
204 return rand64(0, max, ThreadLocalPRNG());
208 * Returns a random uint64_t in [0, max). If max == 0, returns 0.
210 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
211 static uint64_t rand64(uint64_t max, RNG&& rng) {
212 return rand64(0, max, rng);
216 * Returns a random uint64_t in [min, max). If min == max, returns 0.
218 static uint64_t rand64(uint64_t min, uint64_t max) {
219 return rand64(min, max, ThreadLocalPRNG());
223 * Returns a random uint64_t in [min, max). If min == max, returns 0.
225 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
226 static uint64_t rand64(uint64_t min, uint64_t max, RNG&& rng) {
230 return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
234 * Returns true 1/n of the time. If n == 0, always returns false
236 static bool oneIn(uint32_t n) {
237 return oneIn(n, ThreadLocalPRNG());
241 * Returns true 1/n of the time. If n == 0, always returns false
243 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
244 static bool oneIn(uint32_t n, RNG&& rng) {
248 return rand32(0, n, rng) == 0;
252 * Returns a double in [0, 1)
254 static double randDouble01() {
255 return randDouble01(ThreadLocalPRNG());
259 * Returns a double in [0, 1)
261 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
262 static double randDouble01(RNG&& rng) {
263 return std::generate_canonical<double, std::numeric_limits<double>::digits>(
268 * Returns a double in [min, max), if min == max, returns 0.
270 static double randDouble(double min, double max) {
271 return randDouble(min, max, ThreadLocalPRNG());
275 * Returns a double in [min, max), if min == max, returns 0.
277 template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
278 static double randDouble(double min, double max, RNG&& rng) {
279 if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
282 return std::uniform_real_distribution<double>(min, max)(rng);
288 * Return a good seed for a random number generator.
289 * Note that this is a legacy function, as it returns a 32-bit value, which
290 * is too small to be useful as a "real" RNG seed. Use the functions in class
293 inline uint32_t randomNumberSeed() {
294 return Random::rand32();
299 #include <folly/Random-inl.h>