Branch data Line data Source code
1 : : // Copyright (c) 2017-2022 The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #include <random.h>
6 : :
7 : : #include <test/util/random.h>
8 : : #include <test/util/setup_common.h>
9 : : #include <util/time.h>
10 : :
11 : : #include <boost/test/unit_test.hpp>
12 : :
13 : : #include <algorithm>
14 : : #include <random>
15 : :
16 : : BOOST_FIXTURE_TEST_SUITE(random_tests, BasicTestingSetup)
17 : :
18 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(osrandom_tests)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
19 : : {
20 [ + - + - ]: 2 : BOOST_CHECK(Random_SanityCheck());
21 : 1 : }
22 : :
23 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(fastrandom_tests_deterministic)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
24 : : {
25 : : // Check that deterministic FastRandomContexts are deterministic
26 : 1 : SeedRandomForTest(SeedRand::ZEROS);
27 : 1 : FastRandomContext ctx1{true};
28 : 1 : FastRandomContext ctx2{true};
29 : :
30 : 1 : {
31 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().rand<uint64_t>(), uint64_t{9330418229102544152u});
32 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().rand<int>(), int{618925161});
33 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::microseconds>(1h).count(), 1271170921);
34 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count(), 2803534);
35 : :
36 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().rand<uint64_t>(), uint64_t{10170981140880778086u});
37 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().rand<int>(), int{1689082725});
38 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::microseconds>(1h).count(), 2464643716);
39 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count(), 2312205);
40 : :
41 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().rand<uint64_t>(), uint64_t{5689404004456455543u});
42 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().rand<int>(), int{785839937});
43 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::microseconds>(1h).count(), 93558804);
44 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count(), 507022);
45 : : }
46 : :
47 : 1 : {
48 : 1 : constexpr SteadySeconds time_point{1s};
49 : 1 : FastRandomContext ctx{true};
50 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(7, ctx.rand_uniform_delay(time_point, 9s).time_since_epoch().count());
51 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(-6, ctx.rand_uniform_delay(time_point, -9s).time_since_epoch().count());
52 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(1, ctx.rand_uniform_delay(time_point, 0s).time_since_epoch().count());
53 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(4652286523065884857, ctx.rand_uniform_delay(time_point, 9223372036854775807s).time_since_epoch().count());
54 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(-8813961240025683129, ctx.rand_uniform_delay(time_point, -9223372036854775807s).time_since_epoch().count());
55 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(26443, ctx.rand_uniform_delay(time_point, 9h).time_since_epoch().count());
56 : 0 : }
57 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
58 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
59 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64());
60 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
61 [ + - + - : 2 : BOOST_CHECK(ctx1.randbytes(17) == ctx2.randbytes(17));
+ - ]
62 [ + - + - : 2 : BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
+ - ]
63 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7));
64 [ + - + - : 2 : BOOST_CHECK(ctx1.randbytes(128) == ctx2.randbytes(128));
+ - ]
65 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
66 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
67 [ + - + - : 2 : BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
+ - ]
68 [ + - + - ]: 2 : BOOST_CHECK(ctx1.randbytes(50) == ctx2.randbytes(50));
69 : 1 : {
70 : 1 : struct MicroClock {
71 : : using duration = std::chrono::microseconds;
72 : : };
73 : 1 : FastRandomContext ctx{true};
74 : : // Check with clock type
75 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(47222, ctx.rand_uniform_duration<MicroClock>(1s).count());
76 : : // Check with time-point type
77 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(2782, ctx.rand_uniform_duration<SteadySeconds>(9h).count());
78 : 1 : }
79 : 1 : }
80 : :
81 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(fastrandom_tests_nondeterministic)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
82 : : {
83 : : // Check that a nondeterministic ones are not
84 : 1 : {
85 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().rand<uint64_t>() != uint64_t{9330418229102544152u});
86 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().rand<int>() != int{618925161});
87 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().randrange<std::chrono::microseconds>(1h).count() != 1271170921);
88 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count() != 2803534);
89 : :
90 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().rand<uint64_t>() != uint64_t{10170981140880778086u});
91 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().rand<int>() != int{1689082725});
92 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().randrange<std::chrono::microseconds>(1h).count() != 2464643716);
93 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count() != 2312205);
94 : :
95 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().rand<uint64_t>() != uint64_t{5689404004456455543u});
96 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().rand<int>() != int{785839937});
97 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().randrange<std::chrono::microseconds>(1h).count() != 93558804);
98 [ + - ]: 2 : BOOST_CHECK(FastRandomContext().randrange<std::chrono::milliseconds>(1h).count() != 507022);
99 : : }
100 : :
101 : 1 : {
102 : 1 : FastRandomContext ctx3, ctx4;
103 [ + - + - ]: 2 : BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
104 : 1 : }
105 : 1 : {
106 : 1 : FastRandomContext ctx3, ctx4;
107 [ + - + - ]: 2 : BOOST_CHECK(ctx3.rand256() != ctx4.rand256());
108 : 1 : }
109 : 1 : {
110 : 1 : FastRandomContext ctx3, ctx4;
111 [ + - + - ]: 2 : BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));
112 : 1 : }
113 : 1 : }
114 : :
115 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(fastrandom_randbits)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
116 : : {
117 : 1 : FastRandomContext ctx1;
118 : 1 : FastRandomContext ctx2;
119 [ + + ]: 64 : for (int bits = 0; bits < 63; ++bits) {
120 [ + + ]: 63063 : for (int j = 0; j < 1000; ++j) {
121 : 63000 : uint64_t rangebits = ctx1.randbits(bits);
122 [ + - + - ]: 63000 : BOOST_CHECK_EQUAL(rangebits >> bits, 0U);
123 : 63000 : uint64_t range = (uint64_t{1}) << bits | rangebits;
124 : 63000 : uint64_t rand = ctx2.randrange(range);
125 [ + - + - ]: 126000 : BOOST_CHECK(rand < range);
126 : : }
127 : : }
128 : 1 : }
129 : :
130 : : /** Verify that RandomMixin::randbits returns 0 and 1 for every requested bit. */
131 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(randbits_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
132 : : {
133 : 1 : FastRandomContext ctx_lens; //!< RNG for producing the lengths requested from ctx_test.
134 : 1 : FastRandomContext ctx_test1(true), ctx_test2(true); //!< The RNGs being tested.
135 : 1 : int ctx_test_bitsleft{0}; //!< (Assumed value of) ctx_test::bitbuf_len
136 : :
137 : : // Run the entire test 5 times.
138 [ + + ]: 6 : for (int i = 0; i < 5; ++i) {
139 : : // count (first) how often it has occurred, and (second) how often it was true:
140 : : // - for every bit position, in every requested bits count (0 + 1 + 2 + ... + 64 = 2080)
141 : : // - for every value of ctx_test_bitsleft (0..63 = 64)
142 [ + - ]: 5 : std::vector<std::pair<uint64_t, uint64_t>> seen(2080 * 64);
143 : 6289 : while (true) {
144 : : // Loop 1000 times, just to not continuously check std::all_of.
145 [ + + ]: 6295289 : for (int j = 0; j < 1000; ++j) {
146 : : // Decide on a number of bits to request (0 through 64, inclusive; don't use randbits/randrange).
147 : 6289000 : int bits = ctx_lens.rand64() % 65;
148 : : // Generate that many bits.
149 : 6289000 : uint64_t gen = ctx_test1.randbits(bits);
150 : : // For certain bits counts, also test randbits<Bits> and compare.
151 : 6289000 : uint64_t gen2;
152 [ + + + + : 6289000 : if (bits == 0) {
+ + + ]
153 : 96621 : gen2 = ctx_test2.randbits<0>();
154 : : } else if (bits == 1) {
155 : 96442 : gen2 = ctx_test2.randbits<1>();
156 : : } else if (bits == 7) {
157 : 96492 : gen2 = ctx_test2.randbits<7>();
158 : : } else if (bits == 32) {
159 : 96694 : gen2 = ctx_test2.randbits<32>();
160 : : } else if (bits == 51) {
161 : 96775 : gen2 = ctx_test2.randbits<51>();
162 : : } else if (bits == 64) {
163 : 96477 : gen2 = ctx_test2.randbits<64>();
164 : : } else {
165 : 5709499 : gen2 = ctx_test2.randbits(bits);
166 : : }
167 [ + - + - ]: 6289000 : BOOST_CHECK_EQUAL(gen, gen2);
168 : : // Make sure the result is in range.
169 [ + + + - : 6289000 : if (bits < 64) BOOST_CHECK_EQUAL(gen >> bits, 0);
+ - ]
170 : : // Mark all the seen bits in the output.
171 [ + + ]: 207536768 : for (int bit = 0; bit < bits; ++bit) {
172 : 201247768 : int idx = bit + (bits * (bits - 1)) / 2 + 2080 * ctx_test_bitsleft;
173 : 201247768 : seen[idx].first += 1;
174 : 201247768 : seen[idx].second += (gen >> bit) & 1;
175 : : }
176 : : // Update ctx_test_bitself.
177 [ + + ]: 6289000 : if (bits > ctx_test_bitsleft) {
178 : 3144497 : ctx_test_bitsleft = ctx_test_bitsleft + 64 - bits;
179 : : } else {
180 : 3144503 : ctx_test_bitsleft -= bits;
181 : : }
182 : : }
183 : : // Loop until every bit position/combination is seen 242 times.
184 [ + + + + : 4371342 : if (std::all_of(seen.begin(), seen.end(), [](const auto& x) { return x.first >= 242; })) break;
+ + + + -
- - - -
- ]
185 : : }
186 : : // Check that each bit appears within 7.78 standard deviations of 50%
187 : : // (each will fail with P < 1/(2080 * 64 * 10^9)).
188 [ + + ]: 665605 : for (const auto& val : seen) {
189 [ - + ]: 665600 : assert(fabs(val.first * 0.5 - val.second) < sqrt(val.first * 0.25) * 7.78);
190 : : }
191 : 5 : }
192 : 1 : }
193 : :
194 : : /** Does-it-compile test for compatibility with standard library RNG interface. */
195 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(stdrandom_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
196 : : {
197 : 1 : FastRandomContext ctx;
198 : 1 : std::uniform_int_distribution<int> distribution(3, 9);
199 [ + + ]: 101 : for (int i = 0; i < 100; ++i) {
200 : 100 : int x = distribution(ctx);
201 [ + - + - : 200 : BOOST_CHECK(x >= 3);
+ - ]
202 [ + - + - : 200 : BOOST_CHECK(x <= 9);
+ - ]
203 : :
204 [ + - ]: 100 : std::vector<int> test{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
205 : 100 : std::shuffle(test.begin(), test.end(), ctx);
206 [ + + ]: 1100 : for (int j = 1; j <= 10; ++j) {
207 [ + - + - ]: 2000 : BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
208 : : }
209 : 100 : }
210 : 1 : }
211 : :
212 : : /** Test that Shuffle reaches every permutation with equal probability. */
213 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(shuffle_stat_test)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
214 : : {
215 : 1 : FastRandomContext ctx(true);
216 : 1 : uint32_t counts[5 * 5 * 5 * 5 * 5] = {0};
217 [ + + ]: 12001 : for (int i = 0; i < 12000; ++i) {
218 : 12000 : int data[5] = {0, 1, 2, 3, 4};
219 : 12000 : std::shuffle(std::begin(data), std::end(data), ctx);
220 : 12000 : int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625;
221 : 12000 : ++counts[pos];
222 : : }
223 : 1 : unsigned int sum = 0;
224 : 1 : double chi_score = 0.0;
225 [ + + ]: 3126 : for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) {
226 : 3125 : int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625;
227 : 3125 : uint32_t count = counts[i];
228 [ + + + + : 3125 : if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) {
+ + + + +
+ ]
229 [ + - + - ]: 6010 : BOOST_CHECK(count == 0);
230 : : } else {
231 : 120 : chi_score += ((count - 100.0) * (count - 100.0)) / 100.0;
232 [ + - + - : 240 : BOOST_CHECK(count > 50);
+ - ]
233 [ + - + - ]: 240 : BOOST_CHECK(count < 150);
234 : 120 : sum += count;
235 : : }
236 : : }
237 [ + - + - : 2 : BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval
+ - ]
238 [ + - + - : 2 : BOOST_CHECK(chi_score < 210.275);
+ - ]
239 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(sum, 12000U);
240 : 1 : }
241 : :
242 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(xoroshiro128plusplus_reference_values)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
243 : : {
244 : : // numbers generated from reference implementation
245 : 1 : InsecureRandomContext rng(0);
246 [ + - + - ]: 2 : BOOST_TEST(0x6f68e1e7e2646ee1 == rng());
247 [ + - + - ]: 2 : BOOST_TEST(0xbf971b7f454094ad == rng());
248 [ + - + - ]: 2 : BOOST_TEST(0x48f2de556f30de38 == rng());
249 [ + - + - ]: 2 : BOOST_TEST(0x6ea7c59f89bbfc75 == rng());
250 : :
251 : : // seed with a random number
252 : 1 : rng.Reseed(0x1a26f3fa8546b47a);
253 [ + - + - ]: 2 : BOOST_TEST(0xc8dc5e08d844ac7d == rng());
254 [ + - + - ]: 2 : BOOST_TEST(0x5b5f1f6d499dad1b == rng());
255 [ + - + - ]: 2 : BOOST_TEST(0xbeb0031f93313d6f == rng());
256 [ + - + - ]: 2 : BOOST_TEST(0xbfbcf4f43a264497 == rng());
257 : 1 : }
258 : :
259 : : BOOST_AUTO_TEST_SUITE_END()
|
