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 
55   FakeUrbg() = default;
FakeUrbgabsl::random_internal::__anon05bd534e0111::FakeUrbg56   explicit FakeUrbg(bool r) : reject(r) {}
57 
result_typeabsl::random_internal::__anon05bd534e0111::FakeUrbg58   static constexpr result_type(max)() { return Hi; }
result_typeabsl::random_internal::__anon05bd534e0111::FakeUrbg59   static constexpr result_type(min)() { return Lo; }
operator ()absl::random_internal::__anon05bd534e0111::FakeUrbg60   result_type operator()() {
61     // when reject is set, return Hi half the time.
62     return ((++calls % 2) == 1 && reject) ? Hi : Val;
63   }
64 
65   bool reject = false;
66   size_t calls = 0;
67 };
68 
TEST(FastUniformBitsTest,IsPowerOfTwoOrZero)69 TEST(FastUniformBitsTest, IsPowerOfTwoOrZero) {
70   EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{0}));
71   EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{1}));
72   EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{2}));
73   EXPECT_FALSE(IsPowerOfTwoOrZero(uint8_t{3}));
74   EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{4}));
75   EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{16}));
76   EXPECT_FALSE(IsPowerOfTwoOrZero(uint8_t{17}));
77   EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint8_t>::max)()));
78 
79   EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{0}));
80   EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{1}));
81   EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{2}));
82   EXPECT_FALSE(IsPowerOfTwoOrZero(uint16_t{3}));
83   EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{4}));
84   EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{16}));
85   EXPECT_FALSE(IsPowerOfTwoOrZero(uint16_t{17}));
86   EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint16_t>::max)()));
87 
88   EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{0}));
89   EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{1}));
90   EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{2}));
91   EXPECT_FALSE(IsPowerOfTwoOrZero(uint32_t{3}));
92   EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{32}));
93   EXPECT_FALSE(IsPowerOfTwoOrZero(uint32_t{17}));
94   EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint32_t>::max)()));
95 
96   EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{0}));
97   EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{1}));
98   EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{2}));
99   EXPECT_FALSE(IsPowerOfTwoOrZero(uint64_t{3}));
100   EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{4}));
101   EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{64}));
102   EXPECT_FALSE(IsPowerOfTwoOrZero(uint64_t{17}));
103   EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint64_t>::max)()));
104 }
105 
TEST(FastUniformBitsTest,IntegerLog2)106 TEST(FastUniformBitsTest, IntegerLog2) {
107   EXPECT_EQ(0, IntegerLog2(uint16_t{0}));
108   EXPECT_EQ(0, IntegerLog2(uint16_t{1}));
109   EXPECT_EQ(1, IntegerLog2(uint16_t{2}));
110   EXPECT_EQ(1, IntegerLog2(uint16_t{3}));
111   EXPECT_EQ(2, IntegerLog2(uint16_t{4}));
112   EXPECT_EQ(2, IntegerLog2(uint16_t{5}));
113   EXPECT_EQ(2, IntegerLog2(uint16_t{7}));
114   EXPECT_EQ(3, IntegerLog2(uint16_t{8}));
115   EXPECT_EQ(63, IntegerLog2((std::numeric_limits<uint64_t>::max)()));
116 }
117 
TEST(FastUniformBitsTest,RangeSize)118 TEST(FastUniformBitsTest, RangeSize) {
119   EXPECT_EQ(2, (RangeSize<FakeUrbg<uint8_t, 0, 1>>()));
120   EXPECT_EQ(3, (RangeSize<FakeUrbg<uint8_t, 0, 2>>()));
121   EXPECT_EQ(4, (RangeSize<FakeUrbg<uint8_t, 0, 3>>()));
122   //  EXPECT_EQ(0, (RangeSize<FakeUrbg<uint8_t, 2, 2>>()));
123   EXPECT_EQ(4, (RangeSize<FakeUrbg<uint8_t, 2, 5>>()));
124   EXPECT_EQ(5, (RangeSize<FakeUrbg<uint8_t, 2, 6>>()));
125   EXPECT_EQ(9, (RangeSize<FakeUrbg<uint8_t, 2, 10>>()));
126   EXPECT_EQ(
127       0, (RangeSize<
128              FakeUrbg<uint8_t, 0, (std::numeric_limits<uint8_t>::max)()>>()));
129 
130   EXPECT_EQ(4, (RangeSize<FakeUrbg<uint16_t, 0, 3>>()));
131   EXPECT_EQ(4, (RangeSize<FakeUrbg<uint16_t, 2, 5>>()));
132   EXPECT_EQ(5, (RangeSize<FakeUrbg<uint16_t, 2, 6>>()));
133   EXPECT_EQ(18, (RangeSize<FakeUrbg<uint16_t, 1000, 1017>>()));
134   EXPECT_EQ(
135       0, (RangeSize<
136              FakeUrbg<uint16_t, 0, (std::numeric_limits<uint16_t>::max)()>>()));
137 
138   EXPECT_EQ(4, (RangeSize<FakeUrbg<uint32_t, 0, 3>>()));
139   EXPECT_EQ(4, (RangeSize<FakeUrbg<uint32_t, 2, 5>>()));
140   EXPECT_EQ(5, (RangeSize<FakeUrbg<uint32_t, 2, 6>>()));
141   EXPECT_EQ(18, (RangeSize<FakeUrbg<uint32_t, 1000, 1017>>()));
142   EXPECT_EQ(0, (RangeSize<FakeUrbg<uint32_t, 0, 0xffffffff>>()));
143   EXPECT_EQ(0xffffffff, (RangeSize<FakeUrbg<uint32_t, 1, 0xffffffff>>()));
144   EXPECT_EQ(0xfffffffe, (RangeSize<FakeUrbg<uint32_t, 1, 0xfffffffe>>()));
145   EXPECT_EQ(0xfffffffd, (RangeSize<FakeUrbg<uint32_t, 2, 0xfffffffe>>()));
146   EXPECT_EQ(
147       0, (RangeSize<
148              FakeUrbg<uint32_t, 0, (std::numeric_limits<uint32_t>::max)()>>()));
149 
150   EXPECT_EQ(4, (RangeSize<FakeUrbg<uint64_t, 0, 3>>()));
151   EXPECT_EQ(4, (RangeSize<FakeUrbg<uint64_t, 2, 5>>()));
152   EXPECT_EQ(5, (RangeSize<FakeUrbg<uint64_t, 2, 6>>()));
153   EXPECT_EQ(18, (RangeSize<FakeUrbg<uint64_t, 1000, 1017>>()));
154   EXPECT_EQ(0x100000000, (RangeSize<FakeUrbg<uint64_t, 0, 0xffffffff>>()));
155   EXPECT_EQ(0xffffffff, (RangeSize<FakeUrbg<uint64_t, 1, 0xffffffff>>()));
156   EXPECT_EQ(0xfffffffe, (RangeSize<FakeUrbg<uint64_t, 1, 0xfffffffe>>()));
157   EXPECT_EQ(0xfffffffd, (RangeSize<FakeUrbg<uint64_t, 2, 0xfffffffe>>()));
158   EXPECT_EQ(0, (RangeSize<FakeUrbg<uint64_t, 0, 0xffffffffffffffff>>()));
159   EXPECT_EQ(0xffffffffffffffff,
160             (RangeSize<FakeUrbg<uint64_t, 1, 0xffffffffffffffff>>()));
161   EXPECT_EQ(0xfffffffffffffffe,
162             (RangeSize<FakeUrbg<uint64_t, 1, 0xfffffffffffffffe>>()));
163   EXPECT_EQ(0xfffffffffffffffd,
164             (RangeSize<FakeUrbg<uint64_t, 2, 0xfffffffffffffffe>>()));
165   EXPECT_EQ(
166       0, (RangeSize<
167              FakeUrbg<uint64_t, 0, (std::numeric_limits<uint64_t>::max)()>>()));
168 }
169 
170 // The constants need to be choosen so that an infinite rejection loop doesn't
171 // happen...
172 using Urng1_5bit = FakeUrbg<uint8_t, 0, 2, 0>;  // ~1.5 bits (range 3)
173 using Urng4bits = FakeUrbg<uint8_t, 1, 0x10, 2>;
174 using Urng22bits = FakeUrbg<uint32_t, 0, 0x3fffff, 0x301020>;
175 using Urng31bits = FakeUrbg<uint32_t, 1, 0xfffffffe, 0x60070f03>;  // ~31.9 bits
176 using Urng32bits = FakeUrbg<uint32_t, 0, 0xffffffff, 0x74010f01>;
177 using Urng33bits =
178     FakeUrbg<uint64_t, 1, 0x1ffffffff, 0x013301033>;  // ~32.9 bits
179 using Urng63bits = FakeUrbg<uint64_t, 1, 0xfffffffffffffffe,
180                             0xfedcba9012345678>;  // ~63.9 bits
181 using Urng64bits =
182     FakeUrbg<uint64_t, 0, 0xffffffffffffffff, 0x123456780fedcba9>;
183 
TEST(FastUniformBitsTest,OutputsUpTo32Bits)184 TEST(FastUniformBitsTest, OutputsUpTo32Bits) {
185   // Tests that how values are composed; the single-bit deltas should be spread
186   // across each invocation.
187   Urng1_5bit urng1_5;
188   Urng4bits urng4;
189   Urng22bits urng22;
190   Urng31bits urng31;
191   Urng32bits urng32;
192   Urng33bits urng33;
193   Urng63bits urng63;
194   Urng64bits urng64;
195 
196   // 8-bit types
197   {
198     FastUniformBits<uint8_t> fast8;
199     EXPECT_EQ(0x0, fast8(urng1_5));
200     EXPECT_EQ(0x11, fast8(urng4));
201     EXPECT_EQ(0x20, fast8(urng22));
202     EXPECT_EQ(0x2, fast8(urng31));
203     EXPECT_EQ(0x1, fast8(urng32));
204     EXPECT_EQ(0x32, fast8(urng33));
205     EXPECT_EQ(0x77, fast8(urng63));
206     EXPECT_EQ(0xa9, fast8(urng64));
207   }
208 
209   // 16-bit types
210   {
211     FastUniformBits<uint16_t> fast16;
212     EXPECT_EQ(0x0, fast16(urng1_5));
213     EXPECT_EQ(0x1111, fast16(urng4));
214     EXPECT_EQ(0x1020, fast16(urng22));
215     EXPECT_EQ(0x0f02, fast16(urng31));
216     EXPECT_EQ(0x0f01, fast16(urng32));
217     EXPECT_EQ(0x1032, fast16(urng33));
218     EXPECT_EQ(0x5677, fast16(urng63));
219     EXPECT_EQ(0xcba9, fast16(urng64));
220   }
221 
222   // 32-bit types
223   {
224     FastUniformBits<uint32_t> fast32;
225     EXPECT_EQ(0x0, fast32(urng1_5));
226     EXPECT_EQ(0x11111111, fast32(urng4));
227     EXPECT_EQ(0x08301020, fast32(urng22));
228     EXPECT_EQ(0x0f020f02, fast32(urng31));
229     EXPECT_EQ(0x74010f01, fast32(urng32));
230     EXPECT_EQ(0x13301032, fast32(urng33));
231     EXPECT_EQ(0x12345677, fast32(urng63));
232     EXPECT_EQ(0x0fedcba9, fast32(urng64));
233   }
234 }
235 
TEST(FastUniformBitsTest,Outputs64Bits)236 TEST(FastUniformBitsTest, Outputs64Bits) {
237   // Tests that how values are composed; the single-bit deltas should be spread
238   // across each invocation.
239   FastUniformBits<uint64_t> fast64;
240 
241   {
242     FakeUrbg<uint8_t, 0, 1, 0> urng0;
243     FakeUrbg<uint8_t, 0, 1, 1> urng1;
244     Urng4bits urng4;
245     Urng22bits urng22;
246     Urng31bits urng31;
247     Urng32bits urng32;
248     Urng33bits urng33;
249     Urng63bits urng63;
250     Urng64bits urng64;
251 
252     // somewhat degenerate cases only create a single bit.
253     EXPECT_EQ(0x0, fast64(urng0));
254     EXPECT_EQ(64, urng0.calls);
255     EXPECT_EQ(0xffffffffffffffff, fast64(urng1));
256     EXPECT_EQ(64, urng1.calls);
257 
258     // less degenerate cases.
259     EXPECT_EQ(0x1111111111111111, fast64(urng4));
260     EXPECT_EQ(16, urng4.calls);
261     EXPECT_EQ(0x01020c0408301020, fast64(urng22));
262     EXPECT_EQ(3, urng22.calls);
263     EXPECT_EQ(0x387811c3c0870f02, fast64(urng31));
264     EXPECT_EQ(3, urng31.calls);
265     EXPECT_EQ(0x74010f0174010f01, fast64(urng32));
266     EXPECT_EQ(2, urng32.calls);
267     EXPECT_EQ(0x808194040cb01032, fast64(urng33));
268     EXPECT_EQ(3, urng33.calls);
269     EXPECT_EQ(0x1234567712345677, fast64(urng63));
270     EXPECT_EQ(2, urng63.calls);
271     EXPECT_EQ(0x123456780fedcba9, fast64(urng64));
272     EXPECT_EQ(1, urng64.calls);
273   }
274 
275   // The 1.5 bit case is somewhat interesting in that the algorithm refinement
276   // causes one extra small sample. Comments here reference the names used in
277   // [rand.adapt.ibits] that correspond to this case.
278   {
279     Urng1_5bit urng1_5;
280 
281     // w = 64
282     // R = 3
283     // m = 1
284     // n' = 64
285     // w0' = 1
286     // y0' = 2
287     // n = (1 <= 0) > 64 : 65 = 65
288     // n0 = 65 - (64%65) = 1
289     // n1 = 64
290     // w0 = 0
291     // y0 = 3
292     // w1 = 1
293     // y1 = 2
294     EXPECT_EQ(0x0, fast64(urng1_5));
295     EXPECT_EQ(65, urng1_5.calls);
296   }
297 
298   // Validate rejections for non-power-of-2 cases.
299   {
300     Urng1_5bit urng1_5(true);
301     Urng31bits urng31(true);
302     Urng33bits urng33(true);
303     Urng63bits urng63(true);
304 
305     // For 1.5 bits, there would be 1+2*64, except the first
306     // value was accepted and shifted off the end.
307     EXPECT_EQ(0, fast64(urng1_5));
308     EXPECT_EQ(128, urng1_5.calls);
309     EXPECT_EQ(0x387811c3c0870f02, fast64(urng31));
310     EXPECT_EQ(6, urng31.calls);
311     EXPECT_EQ(0x808194040cb01032, fast64(urng33));
312     EXPECT_EQ(6, urng33.calls);
313     EXPECT_EQ(0x1234567712345677, fast64(urng63));
314     EXPECT_EQ(4, urng63.calls);
315   }
316 }
317 
TEST(FastUniformBitsTest,URBG32bitRegression)318 TEST(FastUniformBitsTest, URBG32bitRegression) {
319   // Validate with deterministic 32-bit std::minstd_rand
320   // to ensure that operator() performs as expected.
321 
322   EXPECT_EQ(2147483646, RangeSize<std::minstd_rand>());
323   EXPECT_EQ(30, IntegerLog2(RangeSize<std::minstd_rand>()));
324 
325   std::minstd_rand gen(1);
326   FastUniformBits<uint64_t> fast64;
327 
328   EXPECT_EQ(0x05e47095f8791f45, fast64(gen));
329   EXPECT_EQ(0x028be17e3c07c122, fast64(gen));
330   EXPECT_EQ(0x55d2847c1626e8c2, fast64(gen));
331 }
332 
333 }  // namespace
334 }  // namespace random_internal
335 ABSL_NAMESPACE_END
336 }  // namespace absl
337