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 <stdint.h>
  21 #include "folly/ThreadLocal.h"
  22
  23 namespace folly {
  24
  25 /*
  26  * Return a good seed for a random number generator.
  27  */
  28 uint32_t randomNumberSeed();
  29
  30 class Random;
  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
  86 class Random {
  87
  88  private:
  89   template<class RNG>
  90   using ValidRNG = typename std::enable_if<
  91    std::is_unsigned<typename std::result_of<RNG&()>::type>::value,
  92    RNG>::type;
  93
  94  public:
  95
  96   /**
  97    * Returns a random uint32_t
  98    */
  99   template<class RNG = ThreadLocalPRNG>
 100   static uint32_t rand32(ValidRNG<RNG>  rrng = RNG()) {
 101     uint32_t r = rrng.operator()();
 102     return r;
 103   }
 104
 105   /**
 106    * Returns a random uint32_t in [0, max). If max == 0, returns 0.
 107    */
 108   template<class RNG = ThreadLocalPRNG>
 109   static uint32_t rand32(uint32_t max, ValidRNG<RNG> rng = RNG()) {
 110     if (max == 0) {
 111       return 0;
 112     }
 113
 114     return std::uniform_int_distribution<uint32_t>(0, max - 1)(rng);
 115   }
 116
 117   /**
 118    * Returns a random uint32_t in [min, max). If min == max, returns 0.
 119    */
 120   template<class RNG = ThreadLocalPRNG>
 121   static uint32_t rand32(uint32_t min,
 122                          uint32_t max,
 123                          ValidRNG<RNG> rng = RNG()) {
 124     if (min == max) {
 125       return 0;
 126     }
 127
 128     return std::uniform_int_distribution<uint32_t>(min, max - 1)(rng);
 129   }
 130
 131   /**
 132    * Returns a random uint64_t
 133    */
 134   template<class RNG = ThreadLocalPRNG>
 135   static uint64_t rand64(ValidRNG<RNG> rng = RNG()) {
 136     return ((uint64_t) rng() << 32) | rng();
 137   }
 138
 139   /**
 140    * Returns a random uint64_t in [0, max). If max == 0, returns 0.
 141    */
 142   template<class RNG = ThreadLocalPRNG>
 143   static uint64_t rand64(uint64_t max, ValidRNG<RNG> rng = RNG()) {
 144     if (max == 0) {
 145       return 0;
 146     }
 147
 148     return std::uniform_int_distribution<uint64_t>(0, max - 1)(rng);
 149   }
 150
 151   /**
 152    * Returns a random uint64_t in [min, max). If min == max, returns 0.
 153    */
 154   template<class RNG = ThreadLocalPRNG>
 155   static uint64_t rand64(uint64_t min,
 156                          uint64_t max,
 157                          ValidRNG<RNG> rng = RNG()) {
 158     if (min == max) {
 159       return 0;
 160     }
 161
 162     return std::uniform_int_distribution<uint64_t>(min, max - 1)(rng);
 163   }
 164
 165   /**
 166    * Returns true 1/n of the time. If n == 0, always returns false
 167    */
 168   template<class RNG = ThreadLocalPRNG>
 169   static bool oneIn(uint32_t n, ValidRNG<RNG> rng = RNG()) {
 170     if (n == 0) {
 171       return false;
 172     }
 173
 174     return rand32(n, rng) == 0;
 175   }
 176
 177   /**
 178    * Returns a double in [0, 1)
 179    */
 180   template<class RNG = ThreadLocalPRNG>
 181   static double randDouble01(ValidRNG<RNG> rng = RNG()) {
 182     return std::generate_canonical<double, std::numeric_limits<double>::digits>
 183       (rng);
 184   }
 185
 186   /**
 187     * Returns a double in [min, max), if min == max, returns 0.
 188     */
 189   template<class RNG = ThreadLocalPRNG>
 190   static double randDouble(double min, double max, ValidRNG<RNG> rng = RNG()) {
 191     if (std::fabs(max - min) < std::numeric_limits<double>::epsilon()) {
 192       return 0;
 193     }
 194     return std::uniform_real_distribution<double>(min, max)(rng);
 195   }
 196
 197 };
 198
 199 }
 200
 201 #endif