pcg_engine.h (10067B)
1 // Copyright 2018 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ABSL_RANDOM_INTERNAL_PCG_ENGINE_H_ 16 #define ABSL_RANDOM_INTERNAL_PCG_ENGINE_H_ 17 18 #include <type_traits> 19 20 #include "absl/base/config.h" 21 #include "absl/meta/type_traits.h" 22 #include "absl/numeric/bits.h" 23 #include "absl/numeric/int128.h" 24 #include "absl/random/internal/fastmath.h" 25 #include "absl/random/internal/iostream_state_saver.h" 26 27 namespace absl { 28 ABSL_NAMESPACE_BEGIN 29 namespace random_internal { 30 31 // pcg_engine is a simplified implementation of Melissa O'Neil's PCG engine in 32 // C++. PCG combines a linear congruential generator (LCG) with output state 33 // mixing functions to generate each random variate. pcg_engine supports only a 34 // single sequence (oneseq), and does not support streams. 35 // 36 // pcg_engine is parameterized by two types: 37 // Params, which provides the multiplier and increment values; 38 // Mix, which mixes the state into the result. 39 // 40 template <typename Params, typename Mix> 41 class pcg_engine { 42 static_assert(std::is_same<typename Params::state_type, 43 typename Mix::state_type>::value, 44 "Class-template absl::pcg_engine must be parameterized by " 45 "Params and Mix with identical state_type"); 46 47 static_assert(std::is_unsigned<typename Mix::result_type>::value, 48 "Class-template absl::pcg_engine must be parameterized by " 49 "an unsigned Mix::result_type"); 50 51 using params_type = Params; 52 using mix_type = Mix; 53 using state_type = typename Mix::state_type; 54 55 public: 56 // C++11 URBG interface: 57 using result_type = typename Mix::result_type; 58 59 static constexpr result_type(min)() { 60 return (std::numeric_limits<result_type>::min)(); 61 } 62 63 static constexpr result_type(max)() { 64 return (std::numeric_limits<result_type>::max)(); 65 } 66 67 explicit pcg_engine(uint64_t seed_value = 0) { seed(seed_value); } 68 69 template <class SeedSequence, 70 typename = typename absl::enable_if_t< 71 !std::is_same<SeedSequence, pcg_engine>::value>> 72 explicit pcg_engine(SeedSequence&& seq) { 73 seed(seq); 74 } 75 76 pcg_engine(const pcg_engine&) = default; 77 pcg_engine& operator=(const pcg_engine&) = default; 78 pcg_engine(pcg_engine&&) = default; 79 pcg_engine& operator=(pcg_engine&&) = default; 80 81 result_type operator()() { 82 // Advance the LCG state, always using the new value to generate the output. 83 state_ = lcg(state_); 84 return Mix{}(state_); 85 } 86 87 void seed(uint64_t seed_value = 0) { 88 state_type tmp = seed_value; 89 state_ = lcg(tmp + Params::increment()); 90 } 91 92 template <class SeedSequence> 93 typename absl::enable_if_t< 94 !std::is_convertible<SeedSequence, uint64_t>::value, void> 95 seed(SeedSequence&& seq) { 96 reseed(seq); 97 } 98 99 void discard(uint64_t count) { state_ = advance(state_, count); } 100 101 bool operator==(const pcg_engine& other) const { 102 return state_ == other.state_; 103 } 104 105 bool operator!=(const pcg_engine& other) const { return !(*this == other); } 106 107 template <class CharT, class Traits> 108 friend typename absl::enable_if_t<(sizeof(state_type) == 16), 109 std::basic_ostream<CharT, Traits>&> 110 operator<<( 111 std::basic_ostream<CharT, Traits>& os, // NOLINT(runtime/references) 112 const pcg_engine& engine) { 113 auto saver = random_internal::make_ostream_state_saver(os); 114 random_internal::stream_u128_helper<state_type> helper; 115 helper.write(pcg_engine::params_type::multiplier(), os); 116 os << os.fill(); 117 helper.write(pcg_engine::params_type::increment(), os); 118 os << os.fill(); 119 helper.write(engine.state_, os); 120 return os; 121 } 122 123 template <class CharT, class Traits> 124 friend typename absl::enable_if_t<(sizeof(state_type) <= 8), 125 std::basic_ostream<CharT, Traits>&> 126 operator<<( 127 std::basic_ostream<CharT, Traits>& os, // NOLINT(runtime/references) 128 const pcg_engine& engine) { 129 auto saver = random_internal::make_ostream_state_saver(os); 130 os << pcg_engine::params_type::multiplier() << os.fill(); 131 os << pcg_engine::params_type::increment() << os.fill(); 132 os << engine.state_; 133 return os; 134 } 135 136 template <class CharT, class Traits> 137 friend typename absl::enable_if_t<(sizeof(state_type) == 16), 138 std::basic_istream<CharT, Traits>&> 139 operator>>( 140 std::basic_istream<CharT, Traits>& is, // NOLINT(runtime/references) 141 pcg_engine& engine) { // NOLINT(runtime/references) 142 random_internal::stream_u128_helper<state_type> helper; 143 auto mult = helper.read(is); 144 auto inc = helper.read(is); 145 auto tmp = helper.read(is); 146 if (mult != pcg_engine::params_type::multiplier() || 147 inc != pcg_engine::params_type::increment()) { 148 // signal failure by setting the failbit. 149 is.setstate(is.rdstate() | std::ios_base::failbit); 150 } 151 if (!is.fail()) { 152 engine.state_ = tmp; 153 } 154 return is; 155 } 156 157 template <class CharT, class Traits> 158 friend typename absl::enable_if_t<(sizeof(state_type) <= 8), 159 std::basic_istream<CharT, Traits>&> 160 operator>>( 161 std::basic_istream<CharT, Traits>& is, // NOLINT(runtime/references) 162 pcg_engine& engine) { // NOLINT(runtime/references) 163 state_type mult{}, inc{}, tmp{}; 164 is >> mult >> inc >> tmp; 165 if (mult != pcg_engine::params_type::multiplier() || 166 inc != pcg_engine::params_type::increment()) { 167 // signal failure by setting the failbit. 168 is.setstate(is.rdstate() | std::ios_base::failbit); 169 } 170 if (!is.fail()) { 171 engine.state_ = tmp; 172 } 173 return is; 174 } 175 176 private: 177 state_type state_; 178 179 // Returns the linear-congruential generator next state. 180 static inline constexpr state_type lcg(state_type s) { 181 return s * Params::multiplier() + Params::increment(); 182 } 183 184 // Returns the linear-congruential arbitrary seek state. 185 inline state_type advance(state_type s, uint64_t n) const { 186 state_type mult = Params::multiplier(); 187 state_type inc = Params::increment(); 188 state_type m = 1; 189 state_type i = 0; 190 while (n > 0) { 191 if (n & 1) { 192 m *= mult; 193 i = i * mult + inc; 194 } 195 inc = (mult + 1) * inc; 196 mult *= mult; 197 n >>= 1; 198 } 199 return m * s + i; 200 } 201 202 template <class SeedSequence> 203 void reseed(SeedSequence& seq) { 204 using sequence_result_type = typename SeedSequence::result_type; 205 constexpr size_t kBufferSize = 206 sizeof(state_type) / sizeof(sequence_result_type); 207 sequence_result_type buffer[kBufferSize]; 208 seq.generate(std::begin(buffer), std::end(buffer)); 209 // Convert the seed output to a single state value. 210 state_type tmp = buffer[0]; 211 for (size_t i = 1; i < kBufferSize; i++) { 212 tmp <<= (sizeof(sequence_result_type) * 8); 213 tmp |= buffer[i]; 214 } 215 state_ = lcg(tmp + params_type::increment()); 216 } 217 }; 218 219 // Parameterized implementation of the PCG 128-bit oneseq state. 220 // This provides state_type, multiplier, and increment for pcg_engine. 221 template <uint64_t kMultA, uint64_t kMultB, uint64_t kIncA, uint64_t kIncB> 222 class pcg128_params { 223 public: 224 using state_type = absl::uint128; 225 static inline constexpr state_type multiplier() { 226 return absl::MakeUint128(kMultA, kMultB); 227 } 228 static inline constexpr state_type increment() { 229 return absl::MakeUint128(kIncA, kIncB); 230 } 231 }; 232 233 // Implementation of the PCG xsl_rr_128_64 128-bit mixing function, which 234 // accepts an input of state_type and mixes it into an output of result_type. 235 struct pcg_xsl_rr_128_64 { 236 using state_type = absl::uint128; 237 using result_type = uint64_t; 238 239 inline uint64_t operator()(state_type state) { 240 // This is equivalent to the xsl_rr_128_64 mixing function. 241 uint64_t rotate = static_cast<uint64_t>(state >> 122u); 242 state ^= state >> 64; 243 uint64_t s = static_cast<uint64_t>(state); 244 return rotr(s, static_cast<int>(rotate)); 245 } 246 }; 247 248 // Parameterized implementation of the PCG 64-bit oneseq state. 249 // This provides state_type, multiplier, and increment for pcg_engine. 250 template <uint64_t kMult, uint64_t kInc> 251 class pcg64_params { 252 public: 253 using state_type = uint64_t; 254 static inline constexpr state_type multiplier() { return kMult; } 255 static inline constexpr state_type increment() { return kInc; } 256 }; 257 258 // Implementation of the PCG xsh_rr_64_32 64-bit mixing function, which accepts 259 // an input of state_type and mixes it into an output of result_type. 260 struct pcg_xsh_rr_64_32 { 261 using state_type = uint64_t; 262 using result_type = uint32_t; 263 inline uint32_t operator()(uint64_t state) { 264 return rotr(static_cast<uint32_t>(((state >> 18) ^ state) >> 27), 265 state >> 59); 266 } 267 }; 268 269 // Stable pcg_engine implementations: 270 // This is a 64-bit generator using 128-bits of state. 271 // The output sequence is equivalent to Melissa O'Neil's pcg64_oneseq. 272 using pcg64_2018_engine = pcg_engine< 273 random_internal::pcg128_params<0x2360ed051fc65da4ull, 0x4385df649fccf645ull, 274 0x5851f42d4c957f2d, 0x14057b7ef767814f>, 275 random_internal::pcg_xsl_rr_128_64>; 276 277 // This is a 32-bit generator using 64-bits of state. 278 // This is equivalent to Melissa O'Neil's pcg32_oneseq. 279 using pcg32_2018_engine = pcg_engine< 280 random_internal::pcg64_params<0x5851f42d4c957f2dull, 0x14057b7ef767814full>, 281 random_internal::pcg_xsh_rr_64_32>; 282 283 } // namespace random_internal 284 ABSL_NAMESPACE_END 285 } // namespace absl 286 287 #endif // ABSL_RANDOM_INTERNAL_PCG_ENGINE_H_