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