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_bytes/span.h" 21 #include "pw_random/random.h" 22 #include "pw_span/span.h" 23 #include "pw_status/status_with_size.h" 24 25 namespace pw::random { 26 27 // This is the "xorshift*" algorithm which is a bit stronger than plain XOR 28 // shift thanks to the nonlinear transformation at the end (multiplication). 29 // 30 // See: https://en.wikipedia.org/wiki/Xorshift 31 // 32 // This random generator is NOT cryptographically secure, and incorporates 33 // pseudo-random generation to extrapolate any true injected entropy. The 34 // distribution is not guaranteed to be uniform. 35 class XorShiftStarRng64 : public RandomGenerator { 36 public: XorShiftStarRng64(uint64_t initial_seed)37 XorShiftStarRng64(uint64_t initial_seed) : state_(initial_seed) {} 38 39 // This generator uses entropy-seeded PRNG to never exhaust its random number 40 // pool. Get(ByteSpan dest)41 void Get(ByteSpan dest) final { 42 while (!dest.empty()) { 43 uint64_t random = Regenerate(); 44 size_t copy_size = std::min(dest.size_bytes(), sizeof(state_)); 45 std::memcpy(dest.data(), &random, copy_size); 46 dest = dest.subspan(copy_size); 47 } 48 } 49 50 // Entropy is injected by rotating the state by the number of entropy bits 51 // before xoring the entropy with the current state. This ensures seeding 52 // the random value with single bits will progressively fill the state with 53 // more entropy. InjectEntropyBits(uint32_t data,uint_fast8_t num_bits)54 void InjectEntropyBits(uint32_t data, uint_fast8_t num_bits) final { 55 if (num_bits == 0) { 56 return; 57 } else if (num_bits > 32) { 58 num_bits = 32; 59 } 60 61 // Rotate state. 62 uint64_t untouched_state = state_ >> (kNumStateBits - num_bits); 63 state_ = untouched_state | (state_ << num_bits); 64 // Zero-out all irrelevant bits, then XOR entropy into state. 65 uint32_t mask = 66 static_cast<uint32_t>((static_cast<uint64_t>(1) << num_bits) - 1); 67 state_ ^= (data & mask); 68 } 69 70 private: 71 // Calculate and return the next value based on the "xorshift*" algorithm Regenerate()72 uint64_t Regenerate() { 73 // State must be nonzero, or the algorithm will get stuck and always return 74 // zero. 75 if (state_ == 0) { 76 state_--; 77 } 78 state_ ^= state_ >> 12; 79 state_ ^= state_ << 25; 80 state_ ^= state_ >> 27; 81 return state_ * kMultConst; 82 } 83 uint64_t state_; 84 static constexpr uint8_t kNumStateBits = sizeof(state_) * 8; 85 86 // For information on why this constant was selected, see: 87 // https://www.jstatsoft.org/article/view/v008i14 88 // http://vigna.di.unimi.it/ftp/papers/xorshift.pdf 89 static constexpr uint64_t kMultConst = 0x2545F4914F6CDD1D; 90 }; 91 92 } // namespace pw::random 93