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