folly/Random.h

   1 /*
   2  * Copyright 2015 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 #ifndef FOLLY_RANDOM_H_
  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 = Random::threadLocalPRNG()
  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  private:
  69   class LocalInstancePRNG;
  70
  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>
 119   static void seed(ValidRNG<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>
 130   static ValidRNG<RNG> create();
 131
 132   /**
 133    * Returns a random uint32_t
 134    */
 135   template<class RNG = ThreadLocalPRNG>
 136   static uint32_t rand32(ValidRNG<RNG> rng = RNG()) {
 137     uint32_t r = rng.operator()();
 138     return r;
 139   }
 140
 141   /**
 142    * Returns a random uint32_t in [0, max). If max == 0, returns 0.
 143    */
 144   template<class RNG = ThreadLocalPRNG>
 145   static uint32_t rand32(uint32_t max, ValidRNG<RNG> rng = RNG()) {
 146     if (max == 0) {
 147       return 0;
 148     }
 149
 150     return std::uniform_int_distribution<uint32_t>(0, max - 1)(rng);
 151   }
 152
 153   /**
 154    * Returns a random uint32_t in [min, max). If min == max, returns 0.
 155    */
 156   template<class RNG = ThreadLocalPRNG>
 157   static uint32_t rand32(uint32_t min,
 158                          uint32_t max,
 159                          ValidRNG<RNG> rng = RNG()) {
 160     if (min == max) {
 161       return 0;
 162     }
 163
 164     return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
 165   }
 166
 167   /**
 168    * Returns a random uint64_t
 169    */
 170   template<class RNG = ThreadLocalPRNG>
 171   static uint64_t rand64(ValidRNG<RNG> rng = RNG()) {
 172     return ((uint64_t) rng() << 32) | rng();
 173   }
 174
 175   /**
 176    * Returns a random uint64_t in [0, max). If max == 0, returns 0.
 177    */
 178   template<class RNG = ThreadLocalPRNG>
 179   static uint64_t rand64(uint64_t max, ValidRNG<RNG> rng = RNG()) {
 180     if (max == 0) {
 181       return 0;
 182     }
 183
 184     return std::uniform_int_distribution<uint64_t>(0, max - 1)(rng);
 185   }
 186
 187   /**
 188    * Returns a random uint64_t in [min, max). If min == max, returns 0.
 189    */
 190   template<class RNG = ThreadLocalPRNG>
 191   static uint64_t rand64(uint64_t min,
 192                          uint64_t max,
 193                          ValidRNG<RNG> rng = RNG()) {
 194     if (min == max) {
 195       return 0;
 196     }
 197
 198     return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
 199   }
 200
 201   /**
 202    * Returns true 1/n of the time. If n == 0, always returns false
 203    */
 204   template<class RNG = ThreadLocalPRNG>
 205   static bool oneIn(uint32_t n, ValidRNG<RNG> rng = RNG()) {
 206     if (n == 0) {
 207       return false;
 208     }
 209
 210     return rand32(n, rng) == 0;
 211   }
 212
 213   /**
 214    * Returns a double in [0, 1)
 215    */
 216   template<class RNG = ThreadLocalPRNG>
 217   static double randDouble01(ValidRNG<RNG> rng = RNG()) {
 218     return std::generate_canonical<double, std::numeric_limits<double>::digits>
 219       (rng);
 220   }
 221
 222   /**
 223     * Returns a double in [min, max), if min == max, returns 0.
 224     */
 225   template<class RNG = ThreadLocalPRNG>
 226   static double randDouble(double min, double max, ValidRNG<RNG> rng = RNG()) {
 227     if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
 228       return 0;
 229     }
 230     return std::uniform_real_distribution<double>(min, max)(rng);
 231   }
 232
 233 };
 234
 235 /*
 236  * Return a good seed for a random number generator.
 237  * Note that this is a legacy function, as it returns a 32-bit value, which
 238  * is too small to be useful as a "real" RNG seed. Use the functions in class
 239  * Random instead.
 240  */
 241 inline uint32_t randomNumberSeed() {
 242   return Random::rand32();
 243 }
 244
 245 }
 246
 247 #include <folly/Random-inl.h>
 248
 249 #endif