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_BASE_RANDOM_H_
  18 #define FOLLY_BASE_RANDOM_H_
  19
  20 #include <random>
  21 #include <stdint.h>
  22 #include "folly/ThreadLocal.h"
  23
  24 namespace folly {
  25
  26 /*
  27  * Return a good seed for a random number generator.
  28  */
  29 uint32_t randomNumberSeed();
  30
  31 class Random;
  32
  33 /**
  34  * A PRNG with one instance per thread. This PRNG uses a mersenne twister random
  35  * number generator and is seeded from /dev/urandom. It should not be used for
  36  * anything which requires security, only for statistical randomness.
  37  *
  38  * An instance of this class represents the current threads PRNG. This means
  39  * copying an instance of this class across threads will result in corruption
  40  *
  41  * Most users will use the Random class which implicitly creates this class.
  42  * However, if you are worried about performance, you can memoize the TLS
  43  * lookups that get the per thread state by manually using this class:
  44  *
  45  * ThreadLocalPRNG rng = Random::threadLocalPRNG()
  46  * for (...) {
  47  *   Random::rand32(rng);
  48  * }
  49  */
  50 class ThreadLocalPRNG {
  51  public:
  52   typedef uint32_t result_type;
  53
  54   uint32_t operator()() {
  55     // Using a static method allows the compiler to avoid allocating stack space
  56     // for this class.
  57     return getImpl(local_);
  58   }
  59
  60   static constexpr result_type min() {
  61     return std::numeric_limits<result_type>::min();
  62   }
  63   static constexpr result_type max() {
  64     return std::numeric_limits<result_type>::max();
  65   }
  66   friend class Random;
  67
  68   ThreadLocalPRNG() {
  69     local_ = localInstance.get();
  70     if (!local_) {
  71       local_ = initLocal();
  72     }
  73   }
  74
  75  private:
  76   class LocalInstancePRNG;
  77   static LocalInstancePRNG* initLocal();
  78   static folly::ThreadLocalPtr<ThreadLocalPRNG::LocalInstancePRNG>
  79     localInstance;
  80
  81   static result_type getImpl(LocalInstancePRNG* local);
  82   LocalInstancePRNG* local_;
  83 };
  84
  85
  86
  87 class Random {
  88
  89  private:
  90   template<class RNG>
  91   using ValidRNG = typename std::enable_if<
  92    std::is_unsigned<typename std::result_of<RNG&()>::type>::value,
  93    RNG>::type;
  94
  95  public:
  96
  97   /**
  98    * Returns a random uint32_t
  99    */
 100   template<class RNG = ThreadLocalPRNG>
 101   static uint32_t rand32(ValidRNG<RNG>  rrng = RNG()) {
 102     uint32_t r = rrng.operator()();
 103     return r;
 104   }
 105
 106   /**
 107    * Returns a random uint32_t in [0, max). If max == 0, returns 0.
 108    */
 109   template<class RNG = ThreadLocalPRNG>
 110   static uint32_t rand32(uint32_t max, ValidRNG<RNG> rng = RNG()) {
 111     if (max == 0) {
 112       return 0;
 113     }
 114
 115     return std::uniform_int_distribution<uint32_t>(0, max - 1)(rng);
 116   }
 117
 118   /**
 119    * Returns a random uint32_t in [min, max). If min == max, returns 0.
 120    */
 121   template<class RNG = ThreadLocalPRNG>
 122   static uint32_t rand32(uint32_t min,
 123                          uint32_t max,
 124                          ValidRNG<RNG> rng = RNG()) {
 125     if (min == max) {
 126       return 0;
 127     }
 128
 129     return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
 130   }
 131
 132   /**
 133    * Returns a random uint64_t
 134    */
 135   template<class RNG = ThreadLocalPRNG>
 136   static uint64_t rand64(ValidRNG<RNG> rng = RNG()) {
 137     return ((uint64_t) rng() << 32) | rng();
 138   }
 139
 140   /**
 141    * Returns a random uint64_t in [0, max). If max == 0, returns 0.
 142    */
 143   template<class RNG = ThreadLocalPRNG>
 144   static uint64_t rand64(uint64_t max, ValidRNG<RNG> rng = RNG()) {
 145     if (max == 0) {
 146       return 0;
 147     }
 148
 149     return std::uniform_int_distribution<uint64_t>(0, max - 1)(rng);
 150   }
 151
 152   /**
 153    * Returns a random uint64_t in [min, max). If min == max, returns 0.
 154    */
 155   template<class RNG = ThreadLocalPRNG>
 156   static uint64_t rand64(uint64_t min,
 157                          uint64_t max,
 158                          ValidRNG<RNG> rng = RNG()) {
 159     if (min == max) {
 160       return 0;
 161     }
 162
 163     return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
 164   }
 165
 166   /**
 167    * Returns true 1/n of the time. If n == 0, always returns false
 168    */
 169   template<class RNG = ThreadLocalPRNG>
 170   static bool oneIn(uint32_t n, ValidRNG<RNG> rng = RNG()) {
 171     if (n == 0) {
 172       return false;
 173     }
 174
 175     return rand32(n, rng) == 0;
 176   }
 177
 178   /**
 179    * Returns a double in [0, 1)
 180    */
 181   template<class RNG = ThreadLocalPRNG>
 182   static double randDouble01(ValidRNG<RNG> rng = RNG()) {
 183     return std::generate_canonical<double, std::numeric_limits<double>::digits>
 184       (rng);
 185   }
 186
 187   /**
 188     * Returns a double in [min, max), if min == max, returns 0.
 189     */
 190   template<class RNG = ThreadLocalPRNG>
 191   static double randDouble(double min, double max, ValidRNG<RNG> rng = RNG()) {
 192     if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
 193       return 0;
 194     }
 195     return std::uniform_real_distribution<double>(min, max)(rng);
 196   }
 197
 198 };
 199
 200 }
 201
 202 #endif