third_party/pigweed/repo/pw_random/public/pw_random/xor_shift.h

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