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