Bitcoin Core  27.99.0
P2P Digital Currency
random_tests.cpp
Go to the documentation of this file.
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>
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 BOOST_AUTO_TEST_CASE(osrandom_tests)
19 {
21 }
22 
23 BOOST_AUTO_TEST_CASE(fastrandom_tests)
24 {
25  // Check that deterministic FastRandomContexts are deterministic
27  FastRandomContext ctx1(true);
28  FastRandomContext ctx2(true);
29 
30  for (int i = 10; i > 0; --i) {
31  BOOST_CHECK_EQUAL(GetRand<uint64_t>(), uint64_t{10393729187455219830U});
32  BOOST_CHECK_EQUAL(GetRand<int>(), int{769702006});
33  BOOST_CHECK_EQUAL(GetRandMicros(std::chrono::hours{1}).count(), 2917185654);
34  BOOST_CHECK_EQUAL(GetRandMillis(std::chrono::hours{1}).count(), 2144374);
35  }
36  {
37  constexpr SteadySeconds time_point{1s};
38  FastRandomContext ctx{true};
39  BOOST_CHECK_EQUAL(7, ctx.rand_uniform_delay(time_point, 9s).time_since_epoch().count());
40  BOOST_CHECK_EQUAL(-6, ctx.rand_uniform_delay(time_point, -9s).time_since_epoch().count());
41  BOOST_CHECK_EQUAL(1, ctx.rand_uniform_delay(time_point, 0s).time_since_epoch().count());
42  BOOST_CHECK_EQUAL(1467825113502396065, ctx.rand_uniform_delay(time_point, 9223372036854775807s).time_since_epoch().count());
43  BOOST_CHECK_EQUAL(-970181367944767837, ctx.rand_uniform_delay(time_point, -9223372036854775807s).time_since_epoch().count());
44  BOOST_CHECK_EQUAL(24761, ctx.rand_uniform_delay(time_point, 9h).time_since_epoch().count());
45  }
46  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
47  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
48  BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64());
49  BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
50  BOOST_CHECK(ctx1.randbytes(17) == ctx2.randbytes(17));
51  BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
52  BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7));
53  BOOST_CHECK(ctx1.randbytes(128) == ctx2.randbytes(128));
54  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
55  BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
56  BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
57  BOOST_CHECK(ctx1.randbytes(50) == ctx2.randbytes(50));
58  {
59  struct MicroClock {
60  using duration = std::chrono::microseconds;
61  };
62  FastRandomContext ctx{true};
63  // Check with clock type
64  BOOST_CHECK_EQUAL(47222, ctx.rand_uniform_duration<MicroClock>(1s).count());
65  // Check with time-point type
66  BOOST_CHECK_EQUAL(2782, ctx.rand_uniform_duration<SteadySeconds>(9h).count());
67  }
68 
69  // Check that a nondeterministic ones are not
71  for (int i = 10; i > 0; --i) {
72  BOOST_CHECK(GetRand<uint64_t>() != uint64_t{10393729187455219830U});
73  BOOST_CHECK(GetRand<int>() != int{769702006});
74  BOOST_CHECK(GetRandMicros(std::chrono::hours{1}) != std::chrono::microseconds{2917185654});
75  BOOST_CHECK(GetRandMillis(std::chrono::hours{1}) != std::chrono::milliseconds{2144374});
76  }
77  {
78  FastRandomContext ctx3, ctx4;
79  BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
80  }
81  {
82  FastRandomContext ctx3, ctx4;
83  BOOST_CHECK(ctx3.rand256() != ctx4.rand256());
84  }
85  {
86  FastRandomContext ctx3, ctx4;
87  BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));
88  }
89 }
90 
91 BOOST_AUTO_TEST_CASE(fastrandom_randbits)
92 {
93  FastRandomContext ctx1;
94  FastRandomContext ctx2;
95  for (int bits = 0; bits < 63; ++bits) {
96  for (int j = 0; j < 1000; ++j) {
97  uint64_t rangebits = ctx1.randbits(bits);
98  BOOST_CHECK_EQUAL(rangebits >> bits, 0U);
99  uint64_t range = (uint64_t{1}) << bits | rangebits;
100  uint64_t rand = ctx2.randrange(range);
101  BOOST_CHECK(rand < range);
102  }
103  }
104 }
105 
107 BOOST_AUTO_TEST_CASE(stdrandom_test)
108 {
109  FastRandomContext ctx;
110  std::uniform_int_distribution<int> distribution(3, 9);
111  for (int i = 0; i < 100; ++i) {
112  int x = distribution(ctx);
113  BOOST_CHECK(x >= 3);
114  BOOST_CHECK(x <= 9);
115 
116  std::vector<int> test{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
117  std::shuffle(test.begin(), test.end(), ctx);
118  for (int j = 1; j <= 10; ++j) {
119  BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
120  }
121  Shuffle(test.begin(), test.end(), ctx);
122  for (int j = 1; j <= 10; ++j) {
123  BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
124  }
125  }
126 }
127 
129 BOOST_AUTO_TEST_CASE(shuffle_stat_test)
130 {
131  FastRandomContext ctx(true);
132  uint32_t counts[5 * 5 * 5 * 5 * 5] = {0};
133  for (int i = 0; i < 12000; ++i) {
134  int data[5] = {0, 1, 2, 3, 4};
135  Shuffle(std::begin(data), std::end(data), ctx);
136  int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625;
137  ++counts[pos];
138  }
139  unsigned int sum = 0;
140  double chi_score = 0.0;
141  for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) {
142  int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625;
143  uint32_t count = counts[i];
144  if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) {
145  BOOST_CHECK(count == 0);
146  } else {
147  chi_score += ((count - 100.0) * (count - 100.0)) / 100.0;
148  BOOST_CHECK(count > 50);
149  BOOST_CHECK(count < 150);
150  sum += count;
151  }
152  }
153  BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval
154  BOOST_CHECK(chi_score < 210.275);
155  BOOST_CHECK_EQUAL(sum, 12000U);
156 }
157 
Fast randomness source.
Definition: random.h:145
uint32_t rand32() noexcept
Generate a random 32-bit integer.
Definition: random.h:222
uint64_t rand64() noexcept
Generate a random 64-bit integer.
Definition: random.h:176
uint256 rand256() noexcept
generate a random uint256.
Definition: random.cpp:664
uint64_t randbits(int bits) noexcept
Generate a random (bits)-bit integer.
Definition: random.h:185
std::vector< B > randbytes(size_t len)
Generate random bytes.
Definition: random.cpp:673
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Definition: random.h:203
BOOST_AUTO_TEST_SUITE_END()
volatile double sum
Definition: examples.cpp:10
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:18
#define BOOST_CHECK(expr)
Definition: object.cpp:17
bool g_mock_deterministic_tests
Flag to make GetRand in random.h return the same number.
Definition: random.cpp:643
bool Random_SanityCheck()
Check that OS randomness is available and returning the requested number of bytes.
Definition: random.cpp:690
constexpr auto GetRandMicros
Definition: random.h:97
constexpr auto GetRandMillis
Definition: random.h:98
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
Definition: random.h:265
BOOST_AUTO_TEST_CASE(osrandom_tests)
Basic testing setup.
Definition: setup_common.h:52
static int count
std::chrono::time_point< std::chrono::steady_clock, std::chrono::seconds > SteadySeconds
Definition: time.h:26