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 #include "pw_random/xor_shift.h"
15
16 #include <cinttypes>
17 #include <cstddef>
18 #include <cstdint>
19 #include <cstdio>
20 #include <limits>
21
22 #include "pw_assert/config.h"
23 #include "pw_unit_test/framework.h"
24
25 namespace pw::random {
26 namespace {
27
28 constexpr uint64_t seed1 = 5;
29 constexpr uint64_t result1[] = {
30 0x423212e85fb37474u,
31 0x96051f25a1aadc74u,
32 0x8ac1f520f5595a79u,
33 0x7587fe57095b7c11u,
34 };
35 constexpr int result1_count = sizeof(result1) / sizeof(result1[0]);
36
37 constexpr uint64_t seed2 = 0x21feabcd5fb37474u;
38 constexpr uint64_t result2[] = {
39 0x568ea260a4f3e793u,
40 0x5ea87d669ab04d36u,
41 0x77a8675eec48ae8bu,
42 };
43 constexpr int result2_count = sizeof(result2) / sizeof(result2[0]);
44
TEST(XorShiftStarRng64,ValidateSeries1)45 TEST(XorShiftStarRng64, ValidateSeries1) {
46 XorShiftStarRng64 rng(seed1);
47 for (size_t i = 0; i < result1_count; ++i) {
48 uint64_t val = 0;
49 rng.GetInt(val);
50 EXPECT_EQ(val, result1[i]);
51 }
52 }
53
TEST(XorShiftStarRng64,ValidateSeries2)54 TEST(XorShiftStarRng64, ValidateSeries2) {
55 XorShiftStarRng64 rng(seed2);
56 for (size_t i = 0; i < result2_count; ++i) {
57 uint64_t val = 0;
58 rng.GetInt(val);
59 EXPECT_EQ(val, result2[i]);
60 }
61 }
62
TEST(XorShiftStarRng64,InjectEntropyBits)63 TEST(XorShiftStarRng64, InjectEntropyBits) {
64 XorShiftStarRng64 rng(seed1);
65 uint64_t val = 0;
66 rng.InjectEntropyBits(0x1, 1);
67 rng.GetInt(val);
68 EXPECT_NE(val, result1[0]);
69 }
70
TEST(XorShiftStarRng64,Inject32BitsEntropy)71 TEST(XorShiftStarRng64, Inject32BitsEntropy) {
72 XorShiftStarRng64 rng_1(seed1);
73 uint64_t first_val = 0;
74 rng_1.InjectEntropyBits(0x12345678, 32);
75 rng_1.GetInt(first_val);
76 EXPECT_NE(first_val, result1[0]);
77 }
78
79 // Ensure injecting the same entropy integer, but different bit counts causes
80 // the randomly generated number to differ.
TEST(XorShiftStarRng64,EntropyBitCount)81 TEST(XorShiftStarRng64, EntropyBitCount) {
82 XorShiftStarRng64 rng_1(seed1);
83 uint64_t first_val = 0;
84 rng_1.InjectEntropyBits(0x1, 1);
85 rng_1.GetInt(first_val);
86
87 // Use the same starting seed.
88 XorShiftStarRng64 rng_2(seed1);
89 uint64_t second_val = 0;
90 // Use a different number of entropy bits.
91 rng_2.InjectEntropyBits(0x1, 2);
92 rng_2.GetInt(second_val);
93
94 EXPECT_NE(first_val, second_val);
95 }
96
97 // Ensure injecting the same integer bit-by-bit applies the same transformation
98 // as all in one call. This lets applications decide which is more convenient
99 // without worrying about algorithmic changes.
TEST(XorShiftStarRng64,IncrementalEntropy)100 TEST(XorShiftStarRng64, IncrementalEntropy) {
101 XorShiftStarRng64 rng_1(seed1);
102 uint64_t first_val = 0;
103 rng_1.InjectEntropyBits(0x6, 3);
104 rng_1.GetInt(first_val);
105
106 // Use the same starting seed.
107 XorShiftStarRng64 rng_2(seed1);
108 uint64_t second_val = 0;
109 // Use a different number of injection calls. 6 = 0b110
110 rng_2.InjectEntropyBits(0x1, 1);
111 rng_2.InjectEntropyBits(0x1, 1);
112 rng_2.InjectEntropyBits(0x0, 1);
113 rng_2.GetInt(second_val);
114
115 EXPECT_EQ(first_val, second_val);
116 }
117
TEST(XorShiftStarRng64,InjectEntropy)118 TEST(XorShiftStarRng64, InjectEntropy) {
119 XorShiftStarRng64 rng(seed1);
120 uint64_t val = 0;
121 constexpr std::array<const std::byte, 5> entropy{std::byte(0xaf),
122 std::byte(0x9b),
123 std::byte(0x33),
124 std::byte(0x17),
125 std::byte(0x02)};
126 rng.InjectEntropy(entropy);
127 rng.GetInt(val);
128 EXPECT_NE(val, result1[0]);
129 }
130
TEST(XorShiftStarRng64,GetIntBoundedUint8)131 TEST(XorShiftStarRng64, GetIntBoundedUint8) {
132 XorShiftStarRng64 rng(seed1);
133
134 constexpr uint8_t upper_bound = 150;
135
136 constexpr uint8_t result[] = {
137 116,
138 116,
139 121,
140 17,
141 46,
142 137,
143 121,
144 114,
145 44,
146 };
147 constexpr int result_count = sizeof(result) / sizeof(result[0]);
148
149 uint8_t val8 = 0;
150 for (int i = 0; i < result_count; i++) {
151 rng.GetInt(val8, upper_bound);
152 EXPECT_EQ(val8, result[i]);
153 }
154 }
155
TEST(XorShiftStarRng64,GetIntBoundedUint16)156 TEST(XorShiftStarRng64, GetIntBoundedUint16) {
157 XorShiftStarRng64 rng(seed1);
158
159 constexpr uint16_t upper_bound = 400;
160
161 constexpr uint16_t result[] = {
162 116,
163 116,
164 121,
165 17,
166 302,
167 137,
168 121,
169 370,
170 300,
171 };
172 constexpr int result_count = sizeof(result) / sizeof(result[0]);
173
174 uint16_t val16 = 0;
175 for (int i = 0; i < result_count; i++) {
176 rng.GetInt(val16, upper_bound);
177 EXPECT_EQ(val16, result[i]);
178 }
179 }
180
TEST(XorShiftStarRng64,GetIntBoundedUint32)181 TEST(XorShiftStarRng64, GetIntBoundedUint32) {
182 XorShiftStarRng64 rng(seed1);
183
184 constexpr uint32_t upper_bound = 3'000'000'000;
185
186 constexpr uint32_t result[] = {
187 1'605'596'276,
188 2'712'329'332,
189 156'990'481,
190 2'474'818'862,
191 1'767'009'929,
192 1'239'843'961,
193 2'490'623'346,
194 };
195 constexpr int result_count = sizeof(result) / sizeof(result[0]);
196
197 uint32_t val32 = 0;
198 for (int i = 0; i < result_count; i++) {
199 rng.GetInt(val32, upper_bound);
200 EXPECT_EQ(val32, result[i]);
201 }
202 }
203
TEST(XorShiftStarRng64,GetIntBoundedUint64)204 TEST(XorShiftStarRng64, GetIntBoundedUint64) {
205 XorShiftStarRng64 rng(seed1);
206
207 constexpr uint64_t upper_bound = 10'000'000'000;
208
209 constexpr uint64_t result[] = {
210 1'605'596'276,
211 7'007'296'628,
212 4'116'273'785,
213 6'061'977'225,
214 1'239'843'961,
215 6'785'590'642,
216 4'181'236'647,
217 };
218 constexpr int result_count = sizeof(result) / sizeof(result[0]);
219
220 uint64_t val64 = 0;
221 for (int i = 0; i < result_count; i++) {
222 rng.GetInt(val64, upper_bound);
223 EXPECT_EQ(val64, result[i]);
224 }
225 }
226
TEST(XorShiftStarRng64,GetIntBoundedAt0)227 TEST(XorShiftStarRng64, GetIntBoundedAt0) {
228 if (!PW_ASSERT_ENABLE_DEBUG) {
229 XorShiftStarRng64 rng(seed1);
230 uint64_t val64 = 0;
231 rng.GetInt(val64, static_cast<uint64_t>(0));
232 EXPECT_EQ(val64, 0u);
233 }
234 }
235
TEST(XorShiftStarRng64,GetIntBoundedWith1IsAlways0)236 TEST(XorShiftStarRng64, GetIntBoundedWith1IsAlways0) {
237 XorShiftStarRng64 rng(seed1);
238 uint64_t val64 = 0;
239 for (int i = 0; i < 100; ++i) {
240 rng.GetInt(val64, static_cast<uint64_t>(1));
241 EXPECT_EQ(val64, 0u);
242 }
243 }
244
TEST(XorShiftStarRng64,GetIntBoundedWithBoundOf2MightBeOneOrZero)245 TEST(XorShiftStarRng64, GetIntBoundedWithBoundOf2MightBeOneOrZero) {
246 XorShiftStarRng64 rng(seed1);
247 bool values[] = {false, false, false};
248 for (int i = 0; i < 250; ++i) {
249 size_t values_index = 0;
250 rng.GetInt(values_index, static_cast<size_t>(2));
251 values[values_index] |= true;
252 }
253
254 EXPECT_TRUE(values[0]);
255 EXPECT_TRUE(values[1]);
256 EXPECT_FALSE(values[2]);
257 }
258
TEST(XorShiftStarRng64,GetIntBoundedIsLowerThanPowersOfTwo)259 TEST(XorShiftStarRng64, GetIntBoundedIsLowerThanPowersOfTwo) {
260 XorShiftStarRng64 rng(seed1);
261 for (uint64_t pow_of_2 = 0; pow_of_2 < 64; ++pow_of_2) {
262 uint64_t upper_bound = static_cast<uint64_t>(1) << pow_of_2;
263 uint64_t value = 0;
264 for (int i = 0; i < 256; ++i) {
265 rng.GetInt(value, upper_bound);
266 EXPECT_LT(value, upper_bound);
267 }
268 }
269 }
270
TEST(XorShiftStarRng64,GetIntBoundedUint64IsLowerThanSomeNumbers)271 TEST(XorShiftStarRng64, GetIntBoundedUint64IsLowerThanSomeNumbers) {
272 XorShiftStarRng64 rng(seed1);
273 uint64_t bounds[] = {7, 13, 51, 233, 181, 1025, 50323, 546778};
274 size_t bounds_size = sizeof(bounds) / sizeof(bounds[0]);
275
276 for (size_t i = 0; i < bounds_size; ++i) {
277 for (int j = 0; j < 256; ++j) {
278 uint64_t value = 0;
279 rng.GetInt(value, bounds[i]);
280 EXPECT_LT(value, bounds[i]);
281 }
282 }
283 }
284
TEST(XorShiftStarRng64,GetIntBoundedHasHighBitSetSometimes)285 TEST(XorShiftStarRng64, GetIntBoundedHasHighBitSetSometimes) {
286 XorShiftStarRng64 rng(seed1);
287 bool high_bit = false;
288
289 for (int i = 0; i < 256; ++i) {
290 uint64_t value = 0;
291 rng.GetInt(value, std::numeric_limits<uint64_t>::max());
292 high_bit |= value & (1ULL << 63);
293 }
294
295 EXPECT_TRUE(high_bit);
296 }
297
298 } // namespace
299 } // namespace pw::random
300