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/fast_uniform_bits.h"
16
17 #include <random>
18
19 #include "gtest/gtest.h"
20
21 namespace absl {
22 ABSL_NAMESPACE_BEGIN
23 namespace random_internal {
24 namespace {
25
26 template <typename IntType>
27 class FastUniformBitsTypedTest : public ::testing::Test {};
28
29 using IntTypes = ::testing::Types<uint8_t, uint16_t, uint32_t, uint64_t>;
30
31 TYPED_TEST_SUITE(FastUniformBitsTypedTest, IntTypes);
32
TYPED_TEST(FastUniformBitsTypedTest,BasicTest)33 TYPED_TEST(FastUniformBitsTypedTest, BasicTest) {
34 using Limits = std::numeric_limits<TypeParam>;
35 using FastBits = FastUniformBits<TypeParam>;
36
37 EXPECT_EQ(0, FastBits::min());
38 EXPECT_EQ(Limits::max(), FastBits::max());
39
40 constexpr int kIters = 10000;
41 std::random_device rd;
42 std::mt19937 gen(rd());
43 FastBits fast;
44 for (int i = 0; i < kIters; i++) {
45 const auto v = fast(gen);
46 EXPECT_LE(v, FastBits::max());
47 EXPECT_GE(v, FastBits::min());
48 }
49 }
50
51 template <typename UIntType, UIntType Lo, UIntType Hi, UIntType Val = Lo>
52 struct FakeUrbg {
53 using result_type = UIntType;
54
result_typeabsl::random_internal::__anond5f66ca60111::FakeUrbg55 static constexpr result_type(max)() { return Hi; }
result_typeabsl::random_internal::__anond5f66ca60111::FakeUrbg56 static constexpr result_type(min)() { return Lo; }
operator ()absl::random_internal::__anond5f66ca60111::FakeUrbg57 result_type operator()() { return Val; }
58 };
59
60 using UrngOddbits = FakeUrbg<uint8_t, 1, 0xfe, 0x73>;
61 using Urng4bits = FakeUrbg<uint8_t, 1, 0x10, 2>;
62 using Urng31bits = FakeUrbg<uint32_t, 1, 0xfffffffe, 0x60070f03>;
63 using Urng32bits = FakeUrbg<uint32_t, 0, 0xffffffff, 0x74010f01>;
64
TEST(FastUniformBitsTest,IsPowerOfTwoOrZero)65 TEST(FastUniformBitsTest, IsPowerOfTwoOrZero) {
66 EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{0}));
67 EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{1}));
68 EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{2}));
69 EXPECT_FALSE(IsPowerOfTwoOrZero(uint8_t{3}));
70 EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{16}));
71 EXPECT_FALSE(IsPowerOfTwoOrZero(uint8_t{17}));
72 EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint8_t>::max)()));
73
74 EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{0}));
75 EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{1}));
76 EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{2}));
77 EXPECT_FALSE(IsPowerOfTwoOrZero(uint16_t{3}));
78 EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{16}));
79 EXPECT_FALSE(IsPowerOfTwoOrZero(uint16_t{17}));
80 EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint16_t>::max)()));
81
82 EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{0}));
83 EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{1}));
84 EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{2}));
85 EXPECT_FALSE(IsPowerOfTwoOrZero(uint32_t{3}));
86 EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{32}));
87 EXPECT_FALSE(IsPowerOfTwoOrZero(uint32_t{17}));
88 EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint32_t>::max)()));
89
90 EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{0}));
91 EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{1}));
92 EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{2}));
93 EXPECT_FALSE(IsPowerOfTwoOrZero(uint64_t{3}));
94 EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{64}));
95 EXPECT_FALSE(IsPowerOfTwoOrZero(uint64_t{17}));
96 EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint64_t>::max)()));
97 }
98
TEST(FastUniformBitsTest,IntegerLog2)99 TEST(FastUniformBitsTest, IntegerLog2) {
100 EXPECT_EQ(IntegerLog2(uint16_t{0}), 0);
101 EXPECT_EQ(IntegerLog2(uint16_t{1}), 0);
102 EXPECT_EQ(IntegerLog2(uint16_t{2}), 1);
103 EXPECT_EQ(IntegerLog2(uint16_t{3}), 1);
104 EXPECT_EQ(IntegerLog2(uint16_t{4}), 2);
105 EXPECT_EQ(IntegerLog2(uint16_t{5}), 2);
106 EXPECT_EQ(IntegerLog2(std::numeric_limits<uint64_t>::max()), 63);
107 }
108
TEST(FastUniformBitsTest,RangeSize)109 TEST(FastUniformBitsTest, RangeSize) {
110 EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 0, 3>>()), 4);
111 EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 2, 2>>()), 1);
112 EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 2, 5>>()), 4);
113 EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 2, 6>>()), 5);
114 EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 2, 10>>()), 9);
115 EXPECT_EQ(
116 (RangeSize<FakeUrbg<uint8_t, 0, std::numeric_limits<uint8_t>::max()>>()),
117 0);
118
119 EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 0, 3>>()), 4);
120 EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 2, 2>>()), 1);
121 EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 2, 5>>()), 4);
122 EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 2, 6>>()), 5);
123 EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 1000, 1017>>()), 18);
124 EXPECT_EQ((RangeSize<
125 FakeUrbg<uint16_t, 0, std::numeric_limits<uint16_t>::max()>>()),
126 0);
127
128 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 0, 3>>()), 4);
129 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 2, 2>>()), 1);
130 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 2, 5>>()), 4);
131 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 2, 6>>()), 5);
132 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 1000, 1017>>()), 18);
133 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 0, 0xffffffff>>()), 0);
134 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 1, 0xffffffff>>()), 0xffffffff);
135 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 1, 0xfffffffe>>()), 0xfffffffe);
136 EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 2, 0xfffffffe>>()), 0xfffffffd);
137 EXPECT_EQ((RangeSize<
138 FakeUrbg<uint32_t, 0, std::numeric_limits<uint32_t>::max()>>()),
139 0);
140
141 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 0, 3>>()), 4);
142 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 2>>()), 1);
143 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 5>>()), 4);
144 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 6>>()), 5);
145 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1000, 1017>>()), 18);
146 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 0, 0xffffffff>>()), 0x100000000ull);
147 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1, 0xffffffff>>()), 0xffffffffull);
148 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1, 0xfffffffe>>()), 0xfffffffeull);
149 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 0xfffffffe>>()), 0xfffffffdull);
150 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 0, 0xffffffffffffffffull>>()), 0ull);
151 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1, 0xffffffffffffffffull>>()),
152 0xffffffffffffffffull);
153 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1, 0xfffffffffffffffeull>>()),
154 0xfffffffffffffffeull);
155 EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 0xfffffffffffffffeull>>()),
156 0xfffffffffffffffdull);
157 EXPECT_EQ((RangeSize<
158 FakeUrbg<uint64_t, 0, std::numeric_limits<uint64_t>::max()>>()),
159 0);
160 }
161
TEST(FastUniformBitsTest,PowerOfTwoSubRangeSize)162 TEST(FastUniformBitsTest, PowerOfTwoSubRangeSize) {
163 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 0, 3>>()), 4);
164 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 2, 2>>()), 1);
165 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 2, 5>>()), 4);
166 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 2, 6>>()), 4);
167 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 2, 10>>()), 8);
168 EXPECT_EQ((PowerOfTwoSubRangeSize<
169 FakeUrbg<uint8_t, 0, std::numeric_limits<uint8_t>::max()>>()),
170 0);
171
172 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 0, 3>>()), 4);
173 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 2, 2>>()), 1);
174 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 2, 5>>()), 4);
175 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 2, 6>>()), 4);
176 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 1000, 1017>>()), 16);
177 EXPECT_EQ((PowerOfTwoSubRangeSize<
178 FakeUrbg<uint16_t, 0, std::numeric_limits<uint16_t>::max()>>()),
179 0);
180
181 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 0, 3>>()), 4);
182 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 2, 2>>()), 1);
183 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 2, 5>>()), 4);
184 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 2, 6>>()), 4);
185 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 1000, 1017>>()), 16);
186 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 0, 0xffffffff>>()), 0);
187 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 1, 0xffffffff>>()),
188 0x80000000);
189 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 1, 0xfffffffe>>()),
190 0x80000000);
191 EXPECT_EQ((PowerOfTwoSubRangeSize<
192 FakeUrbg<uint32_t, 0, std::numeric_limits<uint32_t>::max()>>()),
193 0);
194
195 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 0, 3>>()), 4);
196 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 2, 2>>()), 1);
197 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 2, 5>>()), 4);
198 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 2, 6>>()), 4);
199 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1000, 1017>>()), 16);
200 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 0, 0xffffffff>>()),
201 0x100000000ull);
202 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1, 0xffffffff>>()),
203 0x80000000ull);
204 EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1, 0xfffffffe>>()),
205 0x80000000ull);
206 EXPECT_EQ(
207 (PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 0, 0xffffffffffffffffull>>()),
208 0);
209 EXPECT_EQ(
210 (PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1, 0xffffffffffffffffull>>()),
211 0x8000000000000000ull);
212 EXPECT_EQ(
213 (PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1, 0xfffffffffffffffeull>>()),
214 0x8000000000000000ull);
215 EXPECT_EQ((PowerOfTwoSubRangeSize<
216 FakeUrbg<uint64_t, 0, std::numeric_limits<uint64_t>::max()>>()),
217 0);
218 }
219
TEST(FastUniformBitsTest,Urng4_VariousOutputs)220 TEST(FastUniformBitsTest, Urng4_VariousOutputs) {
221 // Tests that how values are composed; the single-bit deltas should be spread
222 // across each invocation.
223 Urng4bits urng4;
224 Urng31bits urng31;
225 Urng32bits urng32;
226
227 // 8-bit types
228 {
229 FastUniformBits<uint8_t> fast8;
230 EXPECT_EQ(0x11, fast8(urng4));
231 EXPECT_EQ(0x2, fast8(urng31));
232 EXPECT_EQ(0x1, fast8(urng32));
233 }
234
235 // 16-bit types
236 {
237 FastUniformBits<uint16_t> fast16;
238 EXPECT_EQ(0x1111, fast16(urng4));
239 EXPECT_EQ(0xf02, fast16(urng31));
240 EXPECT_EQ(0xf01, fast16(urng32));
241 }
242
243 // 32-bit types
244 {
245 FastUniformBits<uint32_t> fast32;
246 EXPECT_EQ(0x11111111, fast32(urng4));
247 EXPECT_EQ(0x0f020f02, fast32(urng31));
248 EXPECT_EQ(0x74010f01, fast32(urng32));
249 }
250
251 // 64-bit types
252 {
253 FastUniformBits<uint64_t> fast64;
254 EXPECT_EQ(0x1111111111111111, fast64(urng4));
255 EXPECT_EQ(0x387811c3c0870f02, fast64(urng31));
256 EXPECT_EQ(0x74010f0174010f01, fast64(urng32));
257 }
258 }
259
TEST(FastUniformBitsTest,URBG32bitRegression)260 TEST(FastUniformBitsTest, URBG32bitRegression) {
261 // Validate with deterministic 32-bit std::minstd_rand
262 // to ensure that operator() performs as expected.
263 std::minstd_rand gen(1);
264 FastUniformBits<uint64_t> fast64;
265
266 EXPECT_EQ(0x05e47095f847c122ull, fast64(gen));
267 EXPECT_EQ(0x8f82c1ba30b64d22ull, fast64(gen));
268 EXPECT_EQ(0x3b971a3558155039ull, fast64(gen));
269 }
270
271 } // namespace
272 } // namespace random_internal
273 ABSL_NAMESPACE_END
274 } // namespace absl
275