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 : 0 : BOOST_FIXTURE_TEST_SUITE(random_tests, BasicTestingSetup)
17 : :
18 : 0 : BOOST_AUTO_TEST_CASE(osrandom_tests)
19 : : {
20 : 0 : BOOST_CHECK(Random_SanityCheck());
21 : 0 : }
22 : :
23 : 0 : BOOST_AUTO_TEST_CASE(fastrandom_tests)
24 : : {
25 : : // Check that deterministic FastRandomContexts are deterministic
26 : 0 : g_mock_deterministic_tests = true;
27 : 0 : FastRandomContext ctx1(true);
28 : 0 : FastRandomContext ctx2(true);
29 : :
30 : 0 : for (int i = 10; i > 0; --i) {
31 : 0 : BOOST_CHECK_EQUAL(GetRand<uint64_t>(), uint64_t{10393729187455219830U});
32 : 0 : BOOST_CHECK_EQUAL(GetRand<int>(), int{769702006});
33 : 0 : BOOST_CHECK_EQUAL(GetRandMicros(std::chrono::hours{1}).count(), 2917185654);
34 : 0 : BOOST_CHECK_EQUAL(GetRandMillis(std::chrono::hours{1}).count(), 2144374);
35 : 0 : }
36 : : {
37 : 0 : constexpr SteadySeconds time_point{1s};
38 : 0 : FastRandomContext ctx{true};
39 : 0 : BOOST_CHECK_EQUAL(7, ctx.rand_uniform_delay(time_point, 9s).time_since_epoch().count());
40 : 0 : BOOST_CHECK_EQUAL(-6, ctx.rand_uniform_delay(time_point, -9s).time_since_epoch().count());
41 : 0 : BOOST_CHECK_EQUAL(1, ctx.rand_uniform_delay(time_point, 0s).time_since_epoch().count());
42 : 0 : BOOST_CHECK_EQUAL(1467825113502396065, ctx.rand_uniform_delay(time_point, 9223372036854775807s).time_since_epoch().count());
43 : 0 : BOOST_CHECK_EQUAL(-970181367944767837, ctx.rand_uniform_delay(time_point, -9223372036854775807s).time_since_epoch().count());
44 : 0 : BOOST_CHECK_EQUAL(24761, ctx.rand_uniform_delay(time_point, 9h).time_since_epoch().count());
45 : 0 : }
46 : 0 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
47 : 0 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
48 : 0 : BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64());
49 : 0 : BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
50 : 0 : BOOST_CHECK(ctx1.randbytes(17) == ctx2.randbytes(17));
51 : 0 : BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
52 : 0 : BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7));
53 : 0 : BOOST_CHECK(ctx1.randbytes(128) == ctx2.randbytes(128));
54 : 0 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
55 : 0 : BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
56 : 0 : BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
57 : 0 : BOOST_CHECK(ctx1.randbytes(50) == ctx2.randbytes(50));
58 : : {
59 : : struct MicroClock {
60 : : using duration = std::chrono::microseconds;
61 : : };
62 : 0 : FastRandomContext ctx{true};
63 : : // Check with clock type
64 : 0 : BOOST_CHECK_EQUAL(47222, ctx.rand_uniform_duration<MicroClock>(1s).count());
65 : : // Check with time-point type
66 : 0 : BOOST_CHECK_EQUAL(2782, ctx.rand_uniform_duration<SteadySeconds>(9h).count());
67 : 0 : }
68 : :
69 : : // Check that a nondeterministic ones are not
70 : 0 : g_mock_deterministic_tests = false;
71 : 0 : for (int i = 10; i > 0; --i) {
72 : 0 : BOOST_CHECK(GetRand<uint64_t>() != uint64_t{10393729187455219830U});
73 : 0 : BOOST_CHECK(GetRand<int>() != int{769702006});
74 : 0 : BOOST_CHECK(GetRandMicros(std::chrono::hours{1}) != std::chrono::microseconds{2917185654});
75 : 0 : BOOST_CHECK(GetRandMillis(std::chrono::hours{1}) != std::chrono::milliseconds{2144374});
76 : 0 : }
77 : : {
78 : 0 : FastRandomContext ctx3, ctx4;
79 : 0 : BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
80 : 0 : }
81 : : {
82 : 0 : FastRandomContext ctx3, ctx4;
83 : 0 : BOOST_CHECK(ctx3.rand256() != ctx4.rand256());
84 : 0 : }
85 : : {
86 : 0 : FastRandomContext ctx3, ctx4;
87 : 0 : BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));
88 : 0 : }
89 : 0 : }
90 : :
91 : 0 : BOOST_AUTO_TEST_CASE(fastrandom_randbits)
92 : : {
93 : 0 : FastRandomContext ctx1;
94 : 0 : FastRandomContext ctx2;
95 : 0 : for (int bits = 0; bits < 63; ++bits) {
96 : 0 : for (int j = 0; j < 1000; ++j) {
97 : 0 : uint64_t rangebits = ctx1.randbits(bits);
98 : 0 : BOOST_CHECK_EQUAL(rangebits >> bits, 0U);
99 : 0 : uint64_t range = (uint64_t{1}) << bits | rangebits;
100 : 0 : uint64_t rand = ctx2.randrange(range);
101 : 0 : BOOST_CHECK(rand < range);
102 : 0 : }
103 : 0 : }
104 : 0 : }
105 : :
106 : : /** Does-it-compile test for compatibility with standard library RNG interface. */
107 : 0 : BOOST_AUTO_TEST_CASE(stdrandom_test)
108 : : {
109 : 0 : FastRandomContext ctx;
110 : 0 : std::uniform_int_distribution<int> distribution(3, 9);
111 : 0 : for (int i = 0; i < 100; ++i) {
112 : 0 : int x = distribution(ctx);
113 : 0 : BOOST_CHECK(x >= 3);
114 : 0 : BOOST_CHECK(x <= 9);
115 : :
116 : 0 : std::vector<int> test{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
117 : 0 : std::shuffle(test.begin(), test.end(), ctx);
118 : 0 : for (int j = 1; j <= 10; ++j) {
119 : 0 : BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
120 : 0 : }
121 : 0 : Shuffle(test.begin(), test.end(), ctx);
122 : 0 : for (int j = 1; j <= 10; ++j) {
123 : 0 : BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
124 : 0 : }
125 : 0 : }
126 : 0 : }
127 : :
128 : : /** Test that Shuffle reaches every permutation with equal probability. */
129 : 0 : BOOST_AUTO_TEST_CASE(shuffle_stat_test)
130 : : {
131 : 0 : FastRandomContext ctx(true);
132 : 0 : uint32_t counts[5 * 5 * 5 * 5 * 5] = {0};
133 : 0 : for (int i = 0; i < 12000; ++i) {
134 : 0 : int data[5] = {0, 1, 2, 3, 4};
135 : 0 : Shuffle(std::begin(data), std::end(data), ctx);
136 : 0 : int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625;
137 : 0 : ++counts[pos];
138 : 0 : }
139 : 0 : unsigned int sum = 0;
140 : 0 : double chi_score = 0.0;
141 : 0 : for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) {
142 : 0 : int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625;
143 : 0 : uint32_t count = counts[i];
144 : 0 : if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) {
145 : 0 : BOOST_CHECK(count == 0);
146 : 0 : } else {
147 : 0 : chi_score += ((count - 100.0) * (count - 100.0)) / 100.0;
148 : 0 : BOOST_CHECK(count > 50);
149 : 0 : BOOST_CHECK(count < 150);
150 : 0 : sum += count;
151 : : }
152 : 0 : }
153 : 0 : BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval
154 : 0 : BOOST_CHECK(chi_score < 210.275);
155 : 0 : BOOST_CHECK_EQUAL(sum, 12000U);
156 : 0 : }
157 : :
158 : 0 : BOOST_AUTO_TEST_SUITE_END()
|
