1 // Copyright 2020 The Pigweed Authors 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 4 // use this file except in compliance with the License. You may obtain a copy of 5 // 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, WITHOUT 11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 12 // License for the specific language governing permissions and limitations under 13 // the License. 14 #pragma once 15 16 #include <algorithm> 17 #include <cstdint> 18 #include <cstring> 19 20 #include "pw_assert/check.h" 21 #include "pw_bytes/span.h" 22 #include "pw_random/random.h" 23 #include "pw_span/span.h" 24 #include "pw_status/status_with_size.h" 25 26 namespace pw::random { 27 28 /// A random generator based off the 29 /// [xorshift*](https://en.wikipedia.org/wiki/Xorshift) algorithm. 30 /// 31 /// The state is represented as an integer that, with each generation, performs 32 /// exclusive OR (XOR) operations on different left/right bit shifts of itself. 33 /// The `*` in `xorshift*` refers to a final multiplication that is applied to 34 /// the output value. The final multiplication is essentially a nonlinear 35 /// transformation that makes the algorithm stronger than a plain XOR shift. 36 /// 37 /// Pigweed's implementation augments `xorshift*` with an ability to inject 38 /// entropy to reseed the generator throughout its lifetime. When entropy is 39 /// injected, the results of the generator are no longer completely 40 /// deterministic based on the original seed. 41 /// 42 /// See also [Xorshift RNGs](https://www.jstatsoft.org/article/view/v008i14) 43 /// and [An experimental exploration of Marsaglia's xorshift generators, 44 /// scrambled](https://vigna.di.unimi.it/ftp/papers/xorshift.pdf). 45 /// 46 /// @warning This random generator is **NOT** cryptographically secure. It 47 /// incorporates pseudo-random generation to extrapolate any true injected 48 /// entropy. The distribution is not guaranteed to be uniform. 49 class XorShiftStarRng64 : public RandomGenerator { 50 public: XorShiftStarRng64(uint64_t initial_seed)51 XorShiftStarRng64(uint64_t initial_seed) : state_(initial_seed) {} 52 53 /// Populates the destination buffer with a randomly generated value. 54 /// 55 /// This generator uses entropy-seeded PRNG to never exhaust its random 56 /// number pool. Get(ByteSpan dest)57 void Get(ByteSpan dest) final { 58 while (!dest.empty()) { 59 uint64_t random = Regenerate(); 60 size_t copy_size = std::min(dest.size_bytes(), sizeof(state_)); 61 std::memcpy(dest.data(), &random, copy_size); 62 dest = dest.subspan(copy_size); 63 } 64 } 65 66 /// Injects entropy by rotating the state by the number of entropy bits 67 /// before XORing the entropy with the current state. 68 /// 69 /// This technique ensures that seeding the random value with single bits 70 /// will progressively fill the state with more entropy. InjectEntropyBits(uint32_t data,uint_fast8_t num_bits)71 void InjectEntropyBits(uint32_t data, uint_fast8_t num_bits) final { 72 if (num_bits == 0) { 73 return; 74 } else if (num_bits > 32) { 75 num_bits = 32; 76 } 77 78 // Rotate state. 79 uint64_t untouched_state = state_ >> (kNumStateBits - num_bits); 80 state_ = untouched_state | (state_ << num_bits); 81 // Zero-out all irrelevant bits, then XOR entropy into state. 82 uint32_t mask = 83 static_cast<uint32_t>((static_cast<uint64_t>(1) << num_bits) - 1); 84 state_ ^= (data & mask); 85 } 86 87 private: 88 // Calculate and return the next value based on the "xorshift*" algorithm Regenerate()89 uint64_t Regenerate() { 90 // State must be nonzero, or the algorithm will get stuck and always return 91 // zero. 92 if (state_ == 0) { 93 state_--; 94 } 95 state_ ^= state_ >> 12; 96 state_ ^= state_ << 25; 97 state_ ^= state_ >> 27; 98 return state_ * kMultConst; 99 } 100 uint64_t state_; 101 static constexpr uint8_t kNumStateBits = sizeof(state_) * 8; 102 103 // For information on why this constant was selected, see: 104 // https://www.jstatsoft.org/article/view/v008i14 105 // http://vigna.di.unimi.it/ftp/papers/xorshift.pdf 106 static constexpr uint64_t kMultConst = 0x2545F4914F6CDD1D; 107 }; 108 109 } // namespace pw::random 110