randen_engine.h (9787B)
1 // Copyright 2017 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_RANDEN_ENGINE_H_ 16 #define ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_ 17 18 #include <algorithm> 19 #include <cinttypes> 20 #include <cstdlib> 21 #include <istream> 22 #include <iterator> 23 #include <limits> 24 #include <ostream> 25 #include <type_traits> 26 27 #include "absl/base/internal/endian.h" 28 #include "absl/meta/type_traits.h" 29 #include "absl/random/internal/iostream_state_saver.h" 30 #include "absl/random/internal/randen.h" 31 32 namespace absl { 33 ABSL_NAMESPACE_BEGIN 34 namespace random_internal { 35 36 // Deterministic pseudorandom byte generator with backtracking resistance 37 // (leaking the state does not compromise prior outputs). Based on Reverie 38 // (see "A Robust and Sponge-Like PRNG with Improved Efficiency") instantiated 39 // with an improved Simpira-like permutation. 40 // Returns values of type "T" (must be a built-in unsigned integer type). 41 // 42 // RANDen = RANDom generator or beetroots in Swiss High German. 43 // 'Strong' (well-distributed, unpredictable, backtracking-resistant) random 44 // generator, faster in some benchmarks than std::mt19937_64 and pcg64_c32. 45 template <typename T> 46 class alignas(8) randen_engine { 47 public: 48 // C++11 URBG interface: 49 using result_type = T; 50 static_assert(std::is_unsigned<result_type>::value, 51 "randen_engine template argument must be a built-in unsigned " 52 "integer type"); 53 54 static constexpr result_type(min)() { 55 return (std::numeric_limits<result_type>::min)(); 56 } 57 58 static constexpr result_type(max)() { 59 return (std::numeric_limits<result_type>::max)(); 60 } 61 62 randen_engine() : randen_engine(0) {} 63 explicit randen_engine(result_type seed_value) { seed(seed_value); } 64 65 template <class SeedSequence, 66 typename = typename absl::enable_if_t< 67 !std::is_same<SeedSequence, randen_engine>::value>> 68 explicit randen_engine(SeedSequence&& seq) { 69 seed(seq); 70 } 71 72 // alignment requirements dictate custom copy and move constructors. 73 randen_engine(const randen_engine& other) 74 : next_(other.next_), impl_(other.impl_) { 75 std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type)); 76 } 77 randen_engine& operator=(const randen_engine& other) { 78 next_ = other.next_; 79 impl_ = other.impl_; 80 std::memcpy(state(), other.state(), kStateSizeT * sizeof(result_type)); 81 return *this; 82 } 83 84 // Returns random bits from the buffer in units of result_type. 85 result_type operator()() { 86 // Refill the buffer if needed (unlikely). 87 auto* begin = state(); 88 if (next_ >= kStateSizeT) { 89 next_ = kCapacityT; 90 impl_.Generate(begin); 91 } 92 return little_endian::ToHost(begin[next_++]); 93 } 94 95 template <class SeedSequence> 96 typename absl::enable_if_t< 97 !std::is_convertible<SeedSequence, result_type>::value> 98 seed(SeedSequence&& seq) { 99 // Zeroes the state. 100 seed(); 101 reseed(seq); 102 } 103 104 void seed(result_type seed_value = 0) { 105 next_ = kStateSizeT; 106 // Zeroes the inner state and fills the outer state with seed_value to 107 // mimic the behaviour of reseed 108 auto* begin = state(); 109 std::fill(begin, begin + kCapacityT, 0); 110 std::fill(begin + kCapacityT, begin + kStateSizeT, seed_value); 111 } 112 113 // Inserts entropy into (part of) the state. Calling this periodically with 114 // sufficient entropy ensures prediction resistance (attackers cannot predict 115 // future outputs even if state is compromised). 116 template <class SeedSequence> 117 void reseed(SeedSequence& seq) { 118 using sequence_result_type = typename SeedSequence::result_type; 119 static_assert(sizeof(sequence_result_type) == 4, 120 "SeedSequence::result_type must be 32-bit"); 121 constexpr size_t kBufferSize = 122 Randen::kSeedBytes / sizeof(sequence_result_type); 123 alignas(16) sequence_result_type buffer[kBufferSize]; 124 125 // Randen::Absorb XORs the seed into state, which is then mixed by a call 126 // to Randen::Generate. Seeding with only the provided entropy is preferred 127 // to using an arbitrary generate() call, so use [rand.req.seed_seq] 128 // size as a proxy for the number of entropy units that can be generated 129 // without relying on seed sequence mixing... 130 const size_t entropy_size = seq.size(); 131 if (entropy_size < kBufferSize) { 132 // ... and only request that many values, or 256-bits, when unspecified. 133 const size_t requested_entropy = (entropy_size == 0) ? 8u : entropy_size; 134 std::fill(buffer + requested_entropy, buffer + kBufferSize, 0); 135 seq.generate(buffer, buffer + requested_entropy); 136 #ifdef ABSL_IS_BIG_ENDIAN 137 // Randen expects the seed buffer to be in Little Endian; reverse it on 138 // Big Endian platforms. 139 for (sequence_result_type& e : buffer) { 140 e = absl::little_endian::FromHost(e); 141 } 142 #endif 143 // The Randen paper suggests preferentially initializing even-numbered 144 // 128-bit vectors of the randen state (there are 16 such vectors). 145 // The seed data is merged into the state offset by 128-bits, which 146 // implies preferring seed bytes [16..31, ..., 208..223]. Since the 147 // buffer is 32-bit values, we swap the corresponding buffer positions in 148 // 128-bit chunks. 149 size_t dst = kBufferSize; 150 while (dst > 7) { 151 // leave the odd bucket as-is. 152 dst -= 4; 153 size_t src = dst >> 1; 154 // swap 128-bits into the even bucket 155 std::swap(buffer[--dst], buffer[--src]); 156 std::swap(buffer[--dst], buffer[--src]); 157 std::swap(buffer[--dst], buffer[--src]); 158 std::swap(buffer[--dst], buffer[--src]); 159 } 160 } else { 161 seq.generate(buffer, buffer + kBufferSize); 162 } 163 impl_.Absorb(buffer, state()); 164 165 // Generate will be called when operator() is called 166 next_ = kStateSizeT; 167 } 168 169 void discard(uint64_t count) { 170 uint64_t step = std::min<uint64_t>(kStateSizeT - next_, count); 171 count -= step; 172 173 constexpr uint64_t kRateT = kStateSizeT - kCapacityT; 174 auto* begin = state(); 175 while (count > 0) { 176 next_ = kCapacityT; 177 impl_.Generate(*reinterpret_cast<result_type(*)[kStateSizeT]>(begin)); 178 step = std::min<uint64_t>(kRateT, count); 179 count -= step; 180 } 181 next_ += step; 182 } 183 184 bool operator==(const randen_engine& other) const { 185 const auto* begin = state(); 186 return next_ == other.next_ && 187 std::equal(begin, begin + kStateSizeT, other.state()); 188 } 189 190 bool operator!=(const randen_engine& other) const { 191 return !(*this == other); 192 } 193 194 template <class CharT, class Traits> 195 friend std::basic_ostream<CharT, Traits>& operator<<( 196 std::basic_ostream<CharT, Traits>& os, // NOLINT(runtime/references) 197 const randen_engine<T>& engine) { // NOLINT(runtime/references) 198 using numeric_type = 199 typename random_internal::stream_format_type<result_type>::type; 200 auto saver = random_internal::make_ostream_state_saver(os); 201 auto* it = engine.state(); 202 for (auto* end = it + kStateSizeT; it < end; ++it) { 203 // In the case that `elem` is `uint8_t`, it must be cast to something 204 // larger so that it prints as an integer rather than a character. For 205 // simplicity, apply the cast all circumstances. 206 os << static_cast<numeric_type>(little_endian::FromHost(*it)) 207 << os.fill(); 208 } 209 os << engine.next_; 210 return os; 211 } 212 213 template <class CharT, class Traits> 214 friend std::basic_istream<CharT, Traits>& operator>>( 215 std::basic_istream<CharT, Traits>& is, // NOLINT(runtime/references) 216 randen_engine<T>& engine) { // NOLINT(runtime/references) 217 using numeric_type = 218 typename random_internal::stream_format_type<result_type>::type; 219 result_type state[kStateSizeT]; 220 size_t next; 221 for (auto& elem : state) { 222 // It is not possible to read uint8_t from wide streams, so it is 223 // necessary to read a wider type and then cast it to uint8_t. 224 numeric_type value; 225 is >> value; 226 elem = little_endian::ToHost(static_cast<result_type>(value)); 227 } 228 is >> next; 229 if (is.fail()) { 230 return is; 231 } 232 std::memcpy(engine.state(), state, sizeof(state)); 233 engine.next_ = next; 234 return is; 235 } 236 237 private: 238 static constexpr size_t kStateSizeT = 239 Randen::kStateBytes / sizeof(result_type); 240 static constexpr size_t kCapacityT = 241 Randen::kCapacityBytes / sizeof(result_type); 242 243 // Returns the state array pointer, which is aligned to 16 bytes. 244 // The first kCapacityT are the `inner' sponge; the remainder are available. 245 result_type* state() { 246 return reinterpret_cast<result_type*>( 247 (reinterpret_cast<uintptr_t>(&raw_state_) & 0xf) ? (raw_state_ + 8) 248 : raw_state_); 249 } 250 const result_type* state() const { 251 return const_cast<randen_engine*>(this)->state(); 252 } 253 254 // raw state array, manually aligned in state(). This overallocates 255 // by 8 bytes since C++ does not guarantee extended heap alignment. 256 alignas(8) char raw_state_[Randen::kStateBytes + 8]; 257 size_t next_; // index within state() 258 Randen impl_; 259 }; 260 261 } // namespace random_internal 262 ABSL_NAMESPACE_END 263 } // namespace absl 264 265 #endif // ABSL_RANDOM_INTERNAL_RANDEN_ENGINE_H_