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 = 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   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>