folly/Random.h

   1 /*
   2  * Copyright 2014 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/ThreadLocal.h>
  24
  25 #if __GNUC_PREREQ(4, 8) && !defined(ANDROID)
  26 #include <ext/random>
  27 #define FOLLY_USE_SIMD_PRNG 1
  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 = Random::threadLocalPRNG()
  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     local_ = localInstance.get();
  69     if (!local_) {
  70       local_ = initLocal();
  71     }
  72   }
  73
  74  private:
  75   class LocalInstancePRNG;
  76   static LocalInstancePRNG* initLocal();
  77   static folly::ThreadLocalPtr<ThreadLocalPRNG::LocalInstancePRNG>
  78     localInstance;
  79
  80   static result_type getImpl(LocalInstancePRNG* local);
  81   LocalInstancePRNG* local_;
  82 };
  83
  84
  85 class Random {
  86
  87  private:
  88   template<class RNG>
  89   using ValidRNG = typename std::enable_if<
  90    std::is_unsigned<typename std::result_of<RNG&()>::type>::value,
  91    RNG>::type;
  92
  93  public:
  94   // Default generator type.
  95 #if FOLLY_USE_SIMD_PRNG
  96   typedef __gnu_cxx::sfmt19937 DefaultGenerator;
  97 #else
  98   typedef std::mt19937 DefaultGenerator;
  99 #endif
 100
 101   /**
 102    * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
 103    */
 104   static void secureRandom(void* data, size_t len);
 105
 106   /**
 107    * Shortcut to get a secure random value of integral type.
 108    */
 109   template <class T>
 110   static typename std::enable_if<
 111     std::is_integral<T>::value && !std::is_same<T,bool>::value,
 112     T>::type
 113   secureRandom() {
 114     T val;
 115     secureRandom(&val, sizeof(val));
 116     return val;
 117   }
 118
 119   /**
 120    * (Re-)Seed an existing RNG with a good seed.
 121    *
 122    * Note that you should usually use ThreadLocalPRNG unless you need
 123    * reproducibility (such as during a test), in which case you'd want
 124    * to create a RNG with a good seed in production, and seed it yourself
 125    * in test.
 126    */
 127   template <class RNG = DefaultGenerator>
 128   static void seed(ValidRNG<RNG>& rng);
 129
 130   /**
 131    * Create a new RNG, seeded with a good seed.
 132    *
 133    * Note that you should usually use ThreadLocalPRNG unless you need
 134    * reproducibility (such as during a test), in which case you'd want
 135    * to create a RNG with a good seed in production, and seed it yourself
 136    * in test.
 137    */
 138   template <class RNG = DefaultGenerator>
 139   static ValidRNG<RNG> create();
 140
 141   /**
 142    * Returns a random uint32_t
 143    */
 144   template<class RNG = ThreadLocalPRNG>
 145   static uint32_t rand32(ValidRNG<RNG> rng = RNG()) {
 146     uint32_t r = rng.operator()();
 147     return r;
 148   }
 149
 150   /**
 151    * Returns a random uint32_t in [0, max). If max == 0, returns 0.
 152    */
 153   template<class RNG = ThreadLocalPRNG>
 154   static uint32_t rand32(uint32_t max, ValidRNG<RNG> rng = RNG()) {
 155     if (max == 0) {
 156       return 0;
 157     }
 158
 159     return std::uniform_int_distribution<uint32_t>(0, max - 1)(rng);
 160   }
 161
 162   /**
 163    * Returns a random uint32_t in [min, max). If min == max, returns 0.
 164    */
 165   template<class RNG = ThreadLocalPRNG>
 166   static uint32_t rand32(uint32_t min,
 167                          uint32_t max,
 168                          ValidRNG<RNG> rng = RNG()) {
 169     if (min == max) {
 170       return 0;
 171     }
 172
 173     return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
 174   }
 175
 176   /**
 177    * Returns a random uint64_t
 178    */
 179   template<class RNG = ThreadLocalPRNG>
 180   static uint64_t rand64(ValidRNG<RNG> rng = RNG()) {
 181     return ((uint64_t) rng() << 32) | rng();
 182   }
 183
 184   /**
 185    * Returns a random uint64_t in [0, max). If max == 0, returns 0.
 186    */
 187   template<class RNG = ThreadLocalPRNG>
 188   static uint64_t rand64(uint64_t max, ValidRNG<RNG> rng = RNG()) {
 189     if (max == 0) {
 190       return 0;
 191     }
 192
 193     return std::uniform_int_distribution<uint64_t>(0, max - 1)(rng);
 194   }
 195
 196   /**
 197    * Returns a random uint64_t in [min, max). If min == max, returns 0.
 198    */
 199   template<class RNG = ThreadLocalPRNG>
 200   static uint64_t rand64(uint64_t min,
 201                          uint64_t max,
 202                          ValidRNG<RNG> rng = RNG()) {
 203     if (min == max) {
 204       return 0;
 205     }
 206
 207     return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
 208   }
 209
 210   /**
 211    * Returns true 1/n of the time. If n == 0, always returns false
 212    */
 213   template<class RNG = ThreadLocalPRNG>
 214   static bool oneIn(uint32_t n, ValidRNG<RNG> rng = RNG()) {
 215     if (n == 0) {
 216       return false;
 217     }
 218
 219     return rand32(n, rng) == 0;
 220   }
 221
 222   /**
 223    * Returns a double in [0, 1)
 224    */
 225   template<class RNG = ThreadLocalPRNG>
 226   static double randDouble01(ValidRNG<RNG> rng = RNG()) {
 227     return std::generate_canonical<double, std::numeric_limits<double>::digits>
 228       (rng);
 229   }
 230
 231   /**
 232     * Returns a double in [min, max), if min == max, returns 0.
 233     */
 234   template<class RNG = ThreadLocalPRNG>
 235   static double randDouble(double min, double max, ValidRNG<RNG> rng = RNG()) {
 236     if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
 237       return 0;
 238     }
 239     return std::uniform_real_distribution<double>(min, max)(rng);
 240   }
 241
 242 };
 243
 244 /*
 245  * Return a good seed for a random number generator.
 246  * Note that this is a legacy function, as it returns a 32-bit value, which
 247  * is too small to be useful as a "real" RNG seed. Use the functions in class
 248  * Random instead.
 249  */
 250 inline uint32_t randomNumberSeed() {
 251   return Random::rand32();
 252 }
 253
 254 }
 255
 256 #include <folly/Random-inl.h>
 257
 258 #endif