folly/Random.h

   1 /*
   2  * Copyright 2011-present 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   using result_type = uint32_t;
  54
  55   result_type 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 class Random {
  79  private:
  80   template <class RNG>
  81   using ValidRNG = typename std::enable_if<
  82       std::is_unsigned<typename std::result_of<RNG&()>::type>::value,
  83       RNG>::type;
  84
  85   template <class T>
  86   class SecureRNG {
  87    public:
  88     using result_type = typename std::enable_if<
  89         std::is_integral<T>::value && !std::is_same<T, bool>::value,
  90         T>::type;
  91
  92     result_type operator()() {
  93       return Random::secureRandom<result_type>();
  94     }
  95
  96     static constexpr result_type min() {
  97       return std::numeric_limits<result_type>::min();
  98     }
  99
 100     static constexpr result_type max() {
 101       return std::numeric_limits<result_type>::max();
 102     }
 103   };
 104
 105  public:
 106   // Default generator type.
 107 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
 108   typedef __gnu_cxx::sfmt19937 DefaultGenerator;
 109 #else
 110   typedef std::mt19937 DefaultGenerator;
 111 #endif
 112
 113   /**
 114    * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
 115    */
 116   static void secureRandom(void* data, size_t len);
 117
 118   /**
 119    * Shortcut to get a secure random value of integral type.
 120    */
 121   template <class T>
 122   static typename std::enable_if<
 123       std::is_integral<T>::value && !std::is_same<T, bool>::value,
 124       T>::type
 125   secureRandom() {
 126     T val;
 127     secureRandom(&val, sizeof(val));
 128     return val;
 129   }
 130
 131   /**
 132    * Returns a secure random uint32_t
 133    */
 134   static uint32_t secureRand32() {
 135     return secureRandom<uint32_t>();
 136   }
 137
 138   /**
 139    * Returns a secure random uint32_t in [0, max). If max == 0, returns 0.
 140    */
 141   static uint32_t secureRand32(uint32_t max) {
 142     SecureRNG<uint32_t> srng;
 143     return rand32(max, srng);
 144   }
 145
 146   /**
 147    * Returns a secure random uint32_t in [min, max). If min == max, returns 0.
 148    */
 149   static uint32_t secureRand32(uint32_t min, uint32_t max) {
 150     SecureRNG<uint32_t> srng;
 151     return rand32(min, max, srng);
 152   }
 153
 154   /**
 155    * Returns a secure random uint64_t
 156    */
 157   static uint64_t secureRand64() {
 158     return secureRandom<uint64_t>();
 159   }
 160
 161   /**
 162    * Returns a secure random uint64_t in [0, max). If max == 0, returns 0.
 163    */
 164   static uint64_t secureRand64(uint64_t max) {
 165     SecureRNG<uint64_t> srng;
 166     return rand64(max, srng);
 167   }
 168
 169   /**
 170    * Returns a secure random uint64_t in [min, max). If min == max, returns 0.
 171    */
 172   static uint64_t secureRand64(uint64_t min, uint64_t max) {
 173     SecureRNG<uint64_t> srng;
 174     return rand64(min, max, srng);
 175   }
 176
 177   /**
 178    * Returns true 1/n of the time. If n == 0, always returns false
 179    */
 180   static bool secureOneIn(uint32_t n) {
 181     SecureRNG<uint32_t> srng;
 182     return rand32(0, n, srng) == 0;
 183   }
 184
 185   /**
 186    * Returns a secure double in [0, 1)
 187    */
 188   static double secureRandDouble01() {
 189     SecureRNG<uint64_t> srng;
 190     return randDouble01(srng);
 191   }
 192
 193   /**
 194    * Returns a secure double in [min, max), if min == max, returns 0.
 195    */
 196   static double secureRandDouble(double min, double max) {
 197     SecureRNG<uint64_t> srng;
 198     return randDouble(min, max, srng);
 199   }
 200
 201   /**
 202    * (Re-)Seed an existing RNG with a good seed.
 203    *
 204    * Note that you should usually use ThreadLocalPRNG unless you need
 205    * reproducibility (such as during a test), in which case you'd want
 206    * to create a RNG with a good seed in production, and seed it yourself
 207    * in test.
 208    */
 209   template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
 210   static void seed(RNG& rng);
 211
 212   /**
 213    * Create a new RNG, seeded with a good seed.
 214    *
 215    * Note that you should usually use ThreadLocalPRNG unless you need
 216    * reproducibility (such as during a test), in which case you'd want
 217    * to create a RNG with a good seed in production, and seed it yourself
 218    * in test.
 219    */
 220   template <class RNG = DefaultGenerator, class /* EnableIf */ = ValidRNG<RNG>>
 221   static RNG create();
 222
 223   /**
 224    * Returns a random uint32_t
 225    */
 226   static uint32_t rand32() {
 227     return rand32(ThreadLocalPRNG());
 228   }
 229
 230   /**
 231    * Returns a random uint32_t given a specific RNG
 232    */
 233   template <class RNG, class /* EnableIf */ = ValidRNG<RNG>>
 234   static uint32_t rand32(RNG&& rng) {
 235     return rng();
 236   }
 237
 238   /**
 239    * Returns a random uint32_t in [0, max). If max == 0, returns 0.
 240    */
 241   static uint32_t rand32(uint32_t max) {
 242     return rand32(0, max, ThreadLocalPRNG());
 243   }
 244
 245   /**
 246    * Returns a random uint32_t in [0, max) given a specific RNG.
 247    * If max == 0, returns 0.
 248    */
 249   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
 250   static uint32_t rand32(uint32_t max, RNG&& rng) {
 251     return rand32(0, max, rng);
 252   }
 253
 254   /**
 255    * Returns a random uint32_t in [min, max). If min == max, returns 0.
 256    */
 257   static uint32_t rand32(uint32_t min, uint32_t max) {
 258     return rand32(min, max, ThreadLocalPRNG());
 259   }
 260
 261   /**
 262    * Returns a random uint32_t in [min, max) given a specific RNG.
 263    * If min == max, returns 0.
 264    */
 265   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
 266   static uint32_t rand32(uint32_t min, uint32_t max, RNG&& rng) {
 267     if (min == max) {
 268       return 0;
 269     }
 270     return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
 271   }
 272
 273   /**
 274    * Returns a random uint64_t
 275    */
 276   static uint64_t rand64() {
 277     return rand64(ThreadLocalPRNG());
 278   }
 279
 280   /**
 281    * Returns a random uint64_t
 282    */
 283   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
 284   static uint64_t rand64(RNG&& rng) {
 285     return ((uint64_t)rng() << 32) | rng();
 286   }
 287
 288   /**
 289    * Returns a random uint64_t in [0, max). If max == 0, returns 0.
 290    */
 291   static uint64_t rand64(uint64_t max) {
 292     return rand64(0, max, ThreadLocalPRNG());
 293   }
 294
 295   /**
 296    * Returns a random uint64_t in [0, max). If max == 0, returns 0.
 297    */
 298   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
 299   static uint64_t rand64(uint64_t max, RNG&& rng) {
 300     return rand64(0, max, rng);
 301   }
 302
 303   /**
 304    * Returns a random uint64_t in [min, max). If min == max, returns 0.
 305    */
 306   static uint64_t rand64(uint64_t min, uint64_t max) {
 307     return rand64(min, max, ThreadLocalPRNG());
 308   }
 309
 310   /**
 311    * Returns a random uint64_t in [min, max). If min == max, returns 0.
 312    */
 313   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
 314   static uint64_t rand64(uint64_t min, uint64_t max, RNG&& rng) {
 315     if (min == max) {
 316       return 0;
 317     }
 318     return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
 319   }
 320
 321   /**
 322    * Returns true 1/n of the time. If n == 0, always returns false
 323    */
 324   static bool oneIn(uint32_t n) {
 325     return oneIn(n, ThreadLocalPRNG());
 326   }
 327
 328   /**
 329    * Returns true 1/n of the time. If n == 0, always returns false
 330    */
 331   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
 332   static bool oneIn(uint32_t n, RNG&& rng) {
 333     if (n == 0) {
 334       return false;
 335     }
 336     return rand32(0, n, rng) == 0;
 337   }
 338
 339   /**
 340    * Returns a double in [0, 1)
 341    */
 342   static double randDouble01() {
 343     return randDouble01(ThreadLocalPRNG());
 344   }
 345
 346   /**
 347    * Returns a double in [0, 1)
 348    */
 349   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
 350   static double randDouble01(RNG&& rng) {
 351     return std::generate_canonical<double, std::numeric_limits<double>::digits>(
 352         rng);
 353   }
 354
 355   /**
 356    * Returns a double in [min, max), if min == max, returns 0.
 357    */
 358   static double randDouble(double min, double max) {
 359     return randDouble(min, max, ThreadLocalPRNG());
 360   }
 361
 362   /**
 363    * Returns a double in [min, max), if min == max, returns 0.
 364    */
 365   template <class RNG = ThreadLocalPRNG, class /* EnableIf */ = ValidRNG<RNG>>
 366   static double randDouble(double min, double max, RNG&& rng) {
 367     if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
 368       return 0;
 369     }
 370     return std::uniform_real_distribution<double>(min, max)(rng);
 371   }
 372 };
 373
 374 /*
 375  * Return a good seed for a random number generator.
 376  * Note that this is a legacy function, as it returns a 32-bit value, which
 377  * is too small to be useful as a "real" RNG seed. Use the functions in class
 378  * Random instead.
 379  */
 380 inline uint32_t randomNumberSeed() {
 381   return Random::rand32();
 382 }
 383
 384 } // namespace folly
 385
 386 #include <folly/Random-inl.h>