Fixed documentation in folly/Random.h
[folly.git] / folly / Random.h
1 /*
2  * Copyright 2017 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 <type_traits>
21 #include <random>
22 #include <stdint.h>
23 #include <folly/Portability.h>
24
25 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
26 #include <ext/random>
27 #endif
28
29 namespace folly {
30
31 /**
32  * A PRNG with one instance per thread. This PRNG uses a mersenne twister random
33  * number generator and is seeded from /dev/urandom. It should not be used for
34  * anything which requires security, only for statistical randomness.
35  *
36  * An instance of this class represents the current threads PRNG. This means
37  * copying an instance of this class across threads will result in corruption
38  *
39  * Most users will use the Random class which implicitly creates this class.
40  * However, if you are worried about performance, you can memoize the TLS
41  * lookups that get the per thread state by manually using this class:
42  *
43  * ThreadLocalPRNG rng;
44  * for (...) {
45  *   Random::rand32(rng);
46  * }
47  */
48 class ThreadLocalPRNG {
49  public:
50   typedef uint32_t result_type;
51
52   uint32_t operator()() {
53     // Using a static method allows the compiler to avoid allocating stack space
54     // for this class.
55     return getImpl(local_);
56   }
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   friend class Random;
65
66   ThreadLocalPRNG();
67
68   class LocalInstancePRNG;
69
70  private:
71   static result_type getImpl(LocalInstancePRNG* local);
72   LocalInstancePRNG* local_;
73 };
74
75
76 class Random {
77
78  private:
79   template <class RNG>
80   using ValidRNG = typename std::enable_if<
81       std::is_unsigned<typename std::result_of<RNG&()>::type>::value,
82       RNG>::type;
83
84  public:
85   // Default generator type.
86 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
87   typedef __gnu_cxx::sfmt19937 DefaultGenerator;
88 #else
89   typedef std::mt19937 DefaultGenerator;
90 #endif
91
92   /**
93    * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
94    */
95   static void secureRandom(void* data, size_t len);
96
97   /**
98    * Shortcut to get a secure random value of integral type.
99    */
100   template <class T>
101   static typename std::enable_if<
102     std::is_integral<T>::value && !std::is_same<T,bool>::value,
103     T>::type
104   secureRandom() {
105     T val;
106     secureRandom(&val, sizeof(val));
107     return val;
108   }
109
110   /**
111    * (Re-)Seed an existing RNG with a good seed.
112    *
113    * Note that you should usually use ThreadLocalPRNG unless you need
114    * reproducibility (such as during a test), in which case you'd want
115    * to create a RNG with a good seed in production, and seed it yourself
116    * in test.
117    */
118   template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
119   static void seed(RNG& rng);
120
121   /**
122    * Create a new RNG, seeded with a good seed.
123    *
124    * Note that you should usually use ThreadLocalPRNG unless you need
125    * reproducibility (such as during a test), in which case you'd want
126    * to create a RNG with a good seed in production, and seed it yourself
127    * in test.
128    */
129   template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
130   static RNG create();
131
132   /**
133    * Returns a random uint32_t
134    */
135   static uint32_t rand32() {
136     return rand32(ThreadLocalPRNG());
137   }
138
139   /**
140    * Returns a random uint32_t given a specific RNG
141    */
142   template <class RNG, class /* EnableIf */ = ValidRNG<RNG>>
143   static uint32_t rand32(RNG&& rng) {
144     return rng();
145   }
146
147   /**
148    * Returns a random uint32_t in [0, max). If max == 0, returns 0.
149    */
150   static uint32_t rand32(uint32_t max) {
151     return rand32(0, max, ThreadLocalPRNG());
152   }
153
154   /**
155    * Returns a random uint32_t in [0, max) given a specific RNG.
156    * If max == 0, returns 0.
157    */
158   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
159   static uint32_t rand32(uint32_t max, RNG&& rng) {
160     return rand32(0, max, rng);
161   }
162
163   /**
164    * Returns a random uint32_t in [min, max). If min == max, returns 0.
165    */
166   static uint32_t rand32(uint32_t min, uint32_t max) {
167     return rand32(min, max, ThreadLocalPRNG());
168   }
169
170   /**
171    * Returns a random uint32_t in [min, max) given a specific RNG.
172    * If min == max, returns 0.
173    */
174   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
175   static uint32_t rand32(uint32_t min, uint32_t max, RNG&& rng) {
176     if (min == max) {
177       return 0;
178     }
179     return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
180   }
181
182   /**
183    * Returns a random uint64_t
184    */
185   static uint64_t rand64() {
186     return rand64(ThreadLocalPRNG());
187   }
188
189   /**
190    * Returns a random uint64_t
191    */
192   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
193   static uint64_t rand64(RNG&& rng) {
194     return ((uint64_t)rng() << 32) | rng();
195   }
196
197   /**
198    * Returns a random uint64_t in [0, max). If max == 0, returns 0.
199    */
200   static uint64_t rand64(uint64_t max) {
201     return rand64(0, max, ThreadLocalPRNG());
202   }
203
204   /**
205    * Returns a random uint64_t in [0, max). If max == 0, returns 0.
206    */
207   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
208   static uint64_t rand64(uint64_t max, RNG&& rng) {
209     return rand64(0, max, rng);
210   }
211
212   /**
213    * Returns a random uint64_t in [min, max). If min == max, returns 0.
214    */
215   static uint64_t rand64(uint64_t min, uint64_t max) {
216     return rand64(min, max, ThreadLocalPRNG());
217   }
218
219   /**
220    * Returns a random uint64_t in [min, max). If min == max, returns 0.
221    */
222   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
223   static uint64_t rand64(uint64_t min, uint64_t max, RNG&& rng) {
224     if (min == max) {
225       return 0;
226     }
227     return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
228   }
229
230   /**
231    * Returns true 1/n of the time. If n == 0, always returns false
232    */
233   static bool oneIn(uint32_t n) {
234     return oneIn(n, ThreadLocalPRNG());
235   }
236
237   /**
238    * Returns true 1/n of the time. If n == 0, always returns false
239    */
240   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
241   static bool oneIn(uint32_t n, RNG&& rng) {
242     if (n == 0) {
243       return false;
244     }
245     return rand32(0, n, rng) == 0;
246   }
247
248   /**
249    * Returns a double in [0, 1)
250    */
251   static double randDouble01() {
252     return randDouble01(ThreadLocalPRNG());
253   }
254
255   /**
256    * Returns a double in [0, 1)
257    */
258   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
259   static double randDouble01(RNG&& rng) {
260     return std::generate_canonical<double, std::numeric_limits<double>::digits>(
261         rng);
262   }
263
264   /**
265     * Returns a double in [min, max), if min == max, returns 0.
266     */
267   static double randDouble(double min, double max) {
268     return randDouble(min, max, ThreadLocalPRNG());
269   }
270
271   /**
272     * Returns a double in [min, max), if min == max, returns 0.
273     */
274   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
275   static double randDouble(double min, double max, RNG&& rng) {
276     if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
277       return 0;
278     }
279     return std::uniform_real_distribution<double>(min, max)(rng);
280   }
281
282 };
283
284 /*
285  * Return a good seed for a random number generator.
286  * Note that this is a legacy function, as it returns a 32-bit value, which
287  * is too small to be useful as a "real" RNG seed. Use the functions in class
288  * Random instead.
289  */
290 inline uint32_t randomNumberSeed() {
291   return Random::rand32();
292 }
293
294 }
295
296 #include <folly/Random-inl.h>