1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of 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,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/random/internal/pool_urbg.h"
16
17 #include <algorithm>
18 #include <bitset>
19 #include <cmath>
20 #include <cstdint>
21 #include <iterator>
22
23 #include "gtest/gtest.h"
24 #include "absl/meta/type_traits.h"
25 #include "absl/types/span.h"
26
27 using absl::random_internal::PoolURBG;
28 using absl::random_internal::RandenPool;
29
30 namespace {
31
32 // is_randen_pool trait is true when parameterized by an RandenPool
33 template <typename T>
34 using is_randen_pool = typename absl::disjunction< //
35 std::is_same<T, RandenPool<uint8_t>>, //
36 std::is_same<T, RandenPool<uint16_t>>, //
37 std::is_same<T, RandenPool<uint32_t>>, //
38 std::is_same<T, RandenPool<uint64_t>>>; //
39
40 // MyFill either calls RandenPool::Fill() or std::generate(..., rng)
41 template <typename T, typename V>
42 typename absl::enable_if_t<absl::negation<is_randen_pool<T>>::value, void> //
MyFill(T & rng,absl::Span<V> data)43 MyFill(T& rng, absl::Span<V> data) { // NOLINT(runtime/references)
44 std::generate(std::begin(data), std::end(data), rng);
45 }
46
47 template <typename T, typename V>
48 typename absl::enable_if_t<is_randen_pool<T>::value, void> //
MyFill(T & rng,absl::Span<V> data)49 MyFill(T& rng, absl::Span<V> data) { // NOLINT(runtime/references)
50 rng.Fill(data);
51 }
52
53 template <typename EngineType>
54 class PoolURBGTypedTest : public ::testing::Test {};
55
56 using EngineTypes = ::testing::Types< //
57 RandenPool<uint8_t>, //
58 RandenPool<uint16_t>, //
59 RandenPool<uint32_t>, //
60 RandenPool<uint64_t>, //
61 PoolURBG<uint8_t, 2>, //
62 PoolURBG<uint16_t, 2>, //
63 PoolURBG<uint32_t, 2>, //
64 PoolURBG<uint64_t, 2>, //
65 PoolURBG<unsigned int, 8>, // NOLINT(runtime/int)
66 PoolURBG<unsigned long, 8>, // NOLINT(runtime/int)
67 PoolURBG<unsigned long int, 4>, // NOLINT(runtime/int)
68 PoolURBG<unsigned long long, 4>>; // NOLINT(runtime/int)
69
70 TYPED_TEST_SUITE(PoolURBGTypedTest, EngineTypes);
71
72 // This test is checks that the engines meet the URBG interface requirements
73 // defined in [rand.req.urbg].
TYPED_TEST(PoolURBGTypedTest,URBGInterface)74 TYPED_TEST(PoolURBGTypedTest, URBGInterface) {
75 using E = TypeParam;
76 using T = typename E::result_type;
77
78 static_assert(std::is_copy_constructible<E>::value,
79 "engine must be copy constructible");
80
81 static_assert(absl::is_copy_assignable<E>::value,
82 "engine must be copy assignable");
83
84 E e;
85 const E x;
86
87 e();
88
89 static_assert(std::is_same<decltype(e()), T>::value,
90 "return type of operator() must be result_type");
91
92 E u0(x);
93 u0();
94
95 E u1 = e;
96 u1();
97 }
98
99 // This validates that sequences are independent.
TYPED_TEST(PoolURBGTypedTest,VerifySequences)100 TYPED_TEST(PoolURBGTypedTest, VerifySequences) {
101 using E = TypeParam;
102 using result_type = typename E::result_type;
103
104 E rng;
105 (void)rng(); // Discard one value.
106
107 constexpr int kNumOutputs = 64;
108 result_type a[kNumOutputs];
109 result_type b[kNumOutputs];
110 std::fill(std::begin(b), std::end(b), 0);
111
112 // Fill a using Fill or generate, depending on the engine type.
113 {
114 E x = rng;
115 MyFill(x, absl::MakeSpan(a));
116 }
117
118 // Fill b using std::generate().
119 {
120 E x = rng;
121 std::generate(std::begin(b), std::end(b), x);
122 }
123
124 // Test that generated sequence changed as sequence of bits, i.e. if about
125 // half of the bites were flipped between two non-correlated values.
126 size_t changed_bits = 0;
127 size_t unchanged_bits = 0;
128 size_t total_set = 0;
129 size_t total_bits = 0;
130 size_t equal_count = 0;
131 for (size_t i = 0; i < kNumOutputs; ++i) {
132 equal_count += (a[i] == b[i]) ? 1 : 0;
133 std::bitset<sizeof(result_type) * 8> bitset(a[i] ^ b[i]);
134 changed_bits += bitset.count();
135 unchanged_bits += bitset.size() - bitset.count();
136
137 std::bitset<sizeof(result_type) * 8> a_set(a[i]);
138 std::bitset<sizeof(result_type) * 8> b_set(b[i]);
139 total_set += a_set.count() + b_set.count();
140 total_bits += 2 * 8 * sizeof(result_type);
141 }
142 // On average, half the bits are changed between two calls.
143 EXPECT_LE(changed_bits, 0.60 * (changed_bits + unchanged_bits));
144 EXPECT_GE(changed_bits, 0.40 * (changed_bits + unchanged_bits));
145
146 // verify using a quick normal-approximation to the binomial.
147 EXPECT_NEAR(total_set, total_bits * 0.5, 4 * std::sqrt(total_bits))
148 << "@" << total_set / static_cast<double>(total_bits);
149
150 // Also, A[i] == B[i] with probability (1/range) * N.
151 // Give this a pretty wide latitude, though.
152 const double kExpected = kNumOutputs / (1.0 * sizeof(result_type) * 8);
153 EXPECT_LE(equal_count, 1.0 + kExpected);
154 }
155
156 } // namespace
157
158 /*
159 $ nanobenchmarks 1 RandenPool construct
160 $ nanobenchmarks 1 PoolURBG construct
161
162 RandenPool<uint32_t> | 1 | 1000 | 48482.00 ticks | 48.48 ticks | 13.9 ns
163 RandenPool<uint32_t> | 10 | 2000 | 1028795.00 ticks | 51.44 ticks | 14.7 ns
164 RandenPool<uint32_t> | 100 | 1000 | 5119968.00 ticks | 51.20 ticks | 14.6 ns
165 RandenPool<uint32_t> | 1000 | 500 | 25867936.00 ticks | 51.74 ticks | 14.8 ns
166
167 RandenPool<uint64_t> | 1 | 1000 | 49921.00 ticks | 49.92 ticks | 14.3 ns
168 RandenPool<uint64_t> | 10 | 2000 | 1208269.00 ticks | 60.41 ticks | 17.3 ns
169 RandenPool<uint64_t> | 100 | 1000 | 5844955.00 ticks | 58.45 ticks | 16.7 ns
170 RandenPool<uint64_t> | 1000 | 500 | 28767404.00 ticks | 57.53 ticks | 16.4 ns
171
172 PoolURBG<uint32_t,8> | 1 | 1000 | 86431.00 ticks | 86.43 ticks | 24.7 ns
173 PoolURBG<uint32_t,8> | 10 | 1000 | 206191.00 ticks | 20.62 ticks | 5.9 ns
174 PoolURBG<uint32_t,8> | 100 | 1000 | 1516049.00 ticks | 15.16 ticks | 4.3 ns
175 PoolURBG<uint32_t,8> | 1000 | 500 | 7613936.00 ticks | 15.23 ticks | 4.4 ns
176
177 PoolURBG<uint64_t,4> | 1 | 1000 | 96668.00 ticks | 96.67 ticks | 27.6 ns
178 PoolURBG<uint64_t,4> | 10 | 1000 | 282423.00 ticks | 28.24 ticks | 8.1 ns
179 PoolURBG<uint64_t,4> | 100 | 1000 | 2609587.00 ticks | 26.10 ticks | 7.5 ns
180 PoolURBG<uint64_t,4> | 1000 | 500 | 12408757.00 ticks | 24.82 ticks | 7.1 ns
181
182 */
183