folly/Random.h

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