Bitcoin Core  22.99.0
P2P Digital Currency
random_tests.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017-2020 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 
8 
9 #include <boost/test/unit_test.hpp>
10 
11 #include <algorithm>
12 #include <random>
13 
15 
16 BOOST_AUTO_TEST_CASE(osrandom_tests)
17 {
19 }
20 
21 BOOST_AUTO_TEST_CASE(fastrandom_tests)
22 {
23  // Check that deterministic FastRandomContexts are deterministic
25  FastRandomContext ctx1(true);
26  FastRandomContext ctx2(true);
27 
28  for (int i = 10; i > 0; --i) {
29  BOOST_CHECK_EQUAL(GetRand(std::numeric_limits<uint64_t>::max()), uint64_t{10393729187455219830U});
30  BOOST_CHECK_EQUAL(GetRandInt(std::numeric_limits<int>::max()), int{769702006});
31  BOOST_CHECK_EQUAL(GetRandMicros(std::chrono::hours{1}).count(), 2917185654);
32  BOOST_CHECK_EQUAL(GetRandMillis(std::chrono::hours{1}).count(), 2144374);
33  }
34  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
35  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
36  BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64());
37  BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
38  BOOST_CHECK(ctx1.randbytes(17) == ctx2.randbytes(17));
39  BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
40  BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7));
41  BOOST_CHECK(ctx1.randbytes(128) == ctx2.randbytes(128));
42  BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
43  BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
44  BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
45  BOOST_CHECK(ctx1.randbytes(50) == ctx2.randbytes(50));
46 
47  // Check that a nondeterministic ones are not
49  for (int i = 10; i > 0; --i) {
50  BOOST_CHECK(GetRand(std::numeric_limits<uint64_t>::max()) != uint64_t{10393729187455219830U});
51  BOOST_CHECK(GetRandInt(std::numeric_limits<int>::max()) != int{769702006});
52  BOOST_CHECK(GetRandMicros(std::chrono::hours{1}) != std::chrono::microseconds{2917185654});
53  BOOST_CHECK(GetRandMillis(std::chrono::hours{1}) != std::chrono::milliseconds{2144374});
54  }
55  {
56  FastRandomContext ctx3, ctx4;
57  BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
58  }
59  {
60  FastRandomContext ctx3, ctx4;
61  BOOST_CHECK(ctx3.rand256() != ctx4.rand256());
62  }
63  {
64  FastRandomContext ctx3, ctx4;
65  BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));
66  }
67 }
68 
69 BOOST_AUTO_TEST_CASE(fastrandom_randbits)
70 {
71  FastRandomContext ctx1;
72  FastRandomContext ctx2;
73  for (int bits = 0; bits < 63; ++bits) {
74  for (int j = 0; j < 1000; ++j) {
75  uint64_t rangebits = ctx1.randbits(bits);
76  BOOST_CHECK_EQUAL(rangebits >> bits, 0U);
77  uint64_t range = ((uint64_t)1) << bits | rangebits;
78  uint64_t rand = ctx2.randrange(range);
79  BOOST_CHECK(rand < range);
80  }
81  }
82 }
83 
85 BOOST_AUTO_TEST_CASE(stdrandom_test)
86 {
88  std::uniform_int_distribution<int> distribution(3, 9);
89  for (int i = 0; i < 100; ++i) {
90  int x = distribution(ctx);
91  BOOST_CHECK(x >= 3);
92  BOOST_CHECK(x <= 9);
93 
94  std::vector<int> test{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
95  std::shuffle(test.begin(), test.end(), ctx);
96  for (int j = 1; j <= 10; ++j) {
97  BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
98  }
99  Shuffle(test.begin(), test.end(), ctx);
100  for (int j = 1; j <= 10; ++j) {
101  BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
102  }
103  }
104 }
105 
107 BOOST_AUTO_TEST_CASE(shuffle_stat_test)
108 {
109  FastRandomContext ctx(true);
110  uint32_t counts[5 * 5 * 5 * 5 * 5] = {0};
111  for (int i = 0; i < 12000; ++i) {
112  int data[5] = {0, 1, 2, 3, 4};
113  Shuffle(std::begin(data), std::end(data), ctx);
114  int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625;
115  ++counts[pos];
116  }
117  unsigned int sum = 0;
118  double chi_score = 0.0;
119  for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) {
120  int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625;
121  uint32_t count = counts[i];
122  if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) {
123  BOOST_CHECK(count == 0);
124  } else {
125  chi_score += ((count - 100.0) * (count - 100.0)) / 100.0;
126  BOOST_CHECK(count > 50);
127  BOOST_CHECK(count < 150);
128  sum += count;
129  }
130  }
131  BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval
132  BOOST_CHECK(chi_score < 210.275);
133  BOOST_CHECK_EQUAL(sum, 12000U);
134 }
135 
count
static int count
Definition: tests.c:41
FastRandomContext::rand256
uint256 rand256() noexcept
generate a random uint256.
Definition: random.cpp:615
setup_common.h
FastRandomContext::randbytes
std::vector< unsigned char > randbytes(size_t len)
Generate random bytes.
Definition: random.cpp:626
BOOST_FIXTURE_TEST_SUITE
#define BOOST_FIXTURE_TEST_SUITE(a, b)
Definition: object.cpp:14
BOOST_AUTO_TEST_SUITE_END
BOOST_AUTO_TEST_SUITE_END()
GetRand
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
Definition: random.cpp:591
FastRandomContext::randbits
uint64_t randbits(int bits) noexcept
Generate a random (bits)-bit integer.
Definition: random.h:172
random.h
GetRandInt
int GetRandInt(int nMax) noexcept
Definition: random.cpp:596
GetRandMicros
constexpr auto GetRandMicros
Definition: random.h:83
FastRandomContext::rand32
uint32_t rand32() noexcept
Generate a random 32-bit integer.
Definition: random.h:205
Shuffle
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
Definition: random.h:231
BasicTestingSetup
Basic testing setup.
Definition: setup_common.h:76
g_mock_deterministic_tests
bool g_mock_deterministic_tests
Flag to make GetRand in random.h return the same number.
Definition: random.cpp:589
sum
volatile double sum
Definition: examples.cpp:10
Random_SanityCheck
bool Random_SanityCheck()
Check that OS randomness is available and returning the requested number of bytes.
Definition: random.cpp:641
FastRandomContext::randrange
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Definition: random.h:190
FastRandomContext::rand64
uint64_t rand64() noexcept
Generate a random 64-bit integer.
Definition: random.h:163
BOOST_AUTO_TEST_CASE
BOOST_AUTO_TEST_CASE(osrandom_tests)
Definition: random_tests.cpp:16
GetRandMillis
constexpr auto GetRandMillis
Definition: random.h:84
FastRandomContext
Fast randomness source.
Definition: random.h:119
BOOST_CHECK
#define BOOST_CHECK(expr)
Definition: object.cpp:17
BOOST_CHECK_EQUAL
#define BOOST_CHECK_EQUAL(v1, v2)
Definition: object.cpp:18
ctx
static secp256k1_context * ctx
Definition: tests.c:42