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