fast_uniform_bits_test.cc (11792B)
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 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; 56 explicit FakeUrbg(bool r) : reject(r) {} 57 58 static constexpr result_type(max)() { return Hi; } 59 static constexpr result_type(min)() { return Lo; } 60 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 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 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 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 chosen 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 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 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 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