folly/Random-inl.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 #ifndef FOLLY_RANDOM_H_
  18 #error This file may only be included from folly/Random.h
  19 #endif
  20
  21 #include <array>
  22
  23 namespace folly {
  24
  25 namespace detail {
  26
  27 // Return the state size needed by RNG, expressed as a number of uint32_t
  28 // integers. Specialized for all templates specified in the C++11 standard.
  29 // For some (mersenne_twister_engine), this is exported as a state_size static
  30 // data member; for others, the standard shows formulas.
  31
  32 template <class RNG> struct StateSize {
  33   // A sane default.
  34   static constexpr size_t value = 512;
  35 };
  36
  37 template <class RNG>
  38 constexpr size_t StateSize<RNG>::value;
  39
  40 template <class UIntType, UIntType a, UIntType c, UIntType m>
  41 struct StateSize<std::linear_congruential_engine<UIntType, a, c, m>> {
  42   // From the standard [rand.eng.lcong], this is ceil(log2(m) / 32) + 3,
  43   // which is the same as ceil(ceil(log2(m) / 32) + 3, and
  44   // ceil(log2(m)) <= std::numeric_limits<UIntType>::digits
  45   static constexpr size_t value =
  46     (std::numeric_limits<UIntType>::digits + 31) / 32 + 3;
  47 };
  48
  49 template <class UIntType, UIntType a, UIntType c, UIntType m>
  50 constexpr size_t
  51 StateSize<std::linear_congruential_engine<UIntType, a, c, m>>::value;
  52
  53 template <class UIntType, size_t w, size_t n, size_t m, size_t r,
  54           UIntType a, size_t u, UIntType d, size_t s,
  55           UIntType b, size_t t,
  56           UIntType c, size_t l, UIntType f>
  57 struct StateSize<std::mersenne_twister_engine<UIntType, w, n, m, r,
  58                                               a, u, d, s, b, t, c, l, f>> {
  59   static constexpr size_t value =
  60     std::mersenne_twister_engine<UIntType, w, n, m, r,
  61                                  a, u, d, s, b, t, c, l, f>::state_size;
  62 };
  63
  64 template <class UIntType, size_t w, size_t n, size_t m, size_t r,
  65           UIntType a, size_t u, UIntType d, size_t s,
  66           UIntType b, size_t t,
  67           UIntType c, size_t l, UIntType f>
  68 constexpr size_t
  69 StateSize<std::mersenne_twister_engine<UIntType, w, n, m, r,
  70                                        a, u, d, s, b, t, c, l, f>>::value;
  71
  72 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
  73
  74 template <class UIntType, size_t m, size_t pos1, size_t sl1, size_t sl2,
  75           size_t sr1, size_t sr2, uint32_t msk1, uint32_t msk2, uint32_t msk3,
  76           uint32_t msk4, uint32_t parity1, uint32_t parity2, uint32_t parity3,
  77           uint32_t parity4>
  78 struct StateSize<__gnu_cxx::simd_fast_mersenne_twister_engine<
  79     UIntType, m, pos1, sl1, sl2, sr1, sr2, msk1, msk2, msk3, msk4,
  80     parity1, parity2, parity3, parity4>> {
  81   static constexpr size_t value =
  82     __gnu_cxx::simd_fast_mersenne_twister_engine<
  83         UIntType, m, pos1, sl1, sl2, sr1, sr2,
  84         msk1, msk2, msk3, msk4,
  85         parity1, parity2, parity3, parity4>::state_size;
  86 };
  87
  88 template <class UIntType, size_t m, size_t pos1, size_t sl1, size_t sl2,
  89           size_t sr1, size_t sr2, uint32_t msk1, uint32_t msk2, uint32_t msk3,
  90           uint32_t msk4, uint32_t parity1, uint32_t parity2, uint32_t parity3,
  91           uint32_t parity4>
  92 constexpr size_t
  93 StateSize<__gnu_cxx::simd_fast_mersenne_twister_engine<
  94     UIntType, m, pos1, sl1, sl2, sr1, sr2, msk1, msk2, msk3, msk4,
  95     parity1, parity2, parity3, parity4>>::value;
  96
  97 #endif
  98
  99 template <class UIntType, size_t w, size_t s, size_t r>
 100 struct StateSize<std::subtract_with_carry_engine<UIntType, w, s, r>> {
 101   // [rand.eng.sub]: r * ceil(w / 32)
 102   static constexpr size_t value = r * ((w + 31) / 32);
 103 };
 104
 105 template <class UIntType, size_t w, size_t s, size_t r>
 106 constexpr size_t
 107 StateSize<std::subtract_with_carry_engine<UIntType, w, s, r>>::value;
 108
 109 template <class RNG>
 110 struct SeedData {
 111   SeedData() {
 112     Random::secureRandom(seedData.data(), seedData.size() * sizeof(uint32_t));
 113   }
 114
 115   static constexpr size_t stateSize = StateSize<RNG>::value;
 116   std::array<uint32_t, stateSize> seedData;
 117 };
 118
 119 }  // namespace detail
 120
 121 template <class RNG, class /* EnableIf */>
 122 void Random::seed(RNG& rng) {
 123   detail::SeedData<RNG> sd;
 124   std::seed_seq s(std::begin(sd.seedData), std::end(sd.seedData));
 125   rng.seed(s);
 126 }
 127
 128 template <class RNG, class /* EnableIf */>
 129 auto Random::create() -> RNG {
 130   detail::SeedData<RNG> sd;
 131   std::seed_seq s(std::begin(sd.seedData), std::end(sd.seedData));
 132   return RNG(s);
 133 }
 134
 135 }  // namespaces