summaryrefslogtreecommitdiff
path: root/absl/random/internal/fast_uniform_bits_test.cc
diff options
context:
space:
mode:
Diffstat (limited to 'absl/random/internal/fast_uniform_bits_test.cc')
-rw-r--r--absl/random/internal/fast_uniform_bits_test.cc318
1 files changed, 190 insertions, 128 deletions
diff --git a/absl/random/internal/fast_uniform_bits_test.cc b/absl/random/internal/fast_uniform_bits_test.cc
index f5b837e5..cee702df 100644
--- a/absl/random/internal/fast_uniform_bits_test.cc
+++ b/absl/random/internal/fast_uniform_bits_test.cc
@@ -34,8 +34,8 @@ TYPED_TEST(FastUniformBitsTypedTest, BasicTest) {
using Limits = std::numeric_limits<TypeParam>;
using FastBits = FastUniformBits<TypeParam>;
- EXPECT_EQ(0, FastBits::min());
- EXPECT_EQ(Limits::max(), FastBits::max());
+ EXPECT_EQ(0, (FastBits::min)());
+ EXPECT_EQ((Limits::max)(), (FastBits::max)());
constexpr int kIters = 10000;
std::random_device rd;
@@ -43,8 +43,8 @@ TYPED_TEST(FastUniformBitsTypedTest, BasicTest) {
FastBits fast;
for (int i = 0; i < kIters; i++) {
const auto v = fast(gen);
- EXPECT_LE(v, FastBits::max());
- EXPECT_GE(v, FastBits::min());
+ EXPECT_LE(v, (FastBits::max)());
+ EXPECT_GE(v, (FastBits::min)());
}
}
@@ -52,21 +52,26 @@ template <typename UIntType, UIntType Lo, UIntType Hi, UIntType Val = Lo>
struct FakeUrbg {
using result_type = UIntType;
+ FakeUrbg() = default;
+ explicit FakeUrbg(bool r) : reject(r) {}
+
static constexpr result_type(max)() { return Hi; }
static constexpr result_type(min)() { return Lo; }
- result_type operator()() { return Val; }
-};
+ result_type operator()() {
+ // when reject is set, return Hi half the time.
+ return ((++calls % 2) == 1 && reject) ? Hi : Val;
+ }
-using UrngOddbits = FakeUrbg<uint8_t, 1, 0xfe, 0x73>;
-using Urng4bits = FakeUrbg<uint8_t, 1, 0x10, 2>;
-using Urng31bits = FakeUrbg<uint32_t, 1, 0xfffffffe, 0x60070f03>;
-using Urng32bits = FakeUrbg<uint32_t, 0, 0xffffffff, 0x74010f01>;
+ bool reject = false;
+ size_t calls = 0;
+};
TEST(FastUniformBitsTest, IsPowerOfTwoOrZero) {
EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{0}));
EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{1}));
EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{2}));
EXPECT_FALSE(IsPowerOfTwoOrZero(uint8_t{3}));
+ EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{4}));
EXPECT_TRUE(IsPowerOfTwoOrZero(uint8_t{16}));
EXPECT_FALSE(IsPowerOfTwoOrZero(uint8_t{17}));
EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint8_t>::max)()));
@@ -75,6 +80,7 @@ TEST(FastUniformBitsTest, IsPowerOfTwoOrZero) {
EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{1}));
EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{2}));
EXPECT_FALSE(IsPowerOfTwoOrZero(uint16_t{3}));
+ EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{4}));
EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{16}));
EXPECT_FALSE(IsPowerOfTwoOrZero(uint16_t{17}));
EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint16_t>::max)()));
@@ -91,181 +97,237 @@ TEST(FastUniformBitsTest, IsPowerOfTwoOrZero) {
EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{1}));
EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{2}));
EXPECT_FALSE(IsPowerOfTwoOrZero(uint64_t{3}));
+ EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{4}));
EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{64}));
EXPECT_FALSE(IsPowerOfTwoOrZero(uint64_t{17}));
EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint64_t>::max)()));
}
TEST(FastUniformBitsTest, IntegerLog2) {
- EXPECT_EQ(IntegerLog2(uint16_t{0}), 0);
- EXPECT_EQ(IntegerLog2(uint16_t{1}), 0);
- EXPECT_EQ(IntegerLog2(uint16_t{2}), 1);
- EXPECT_EQ(IntegerLog2(uint16_t{3}), 1);
- EXPECT_EQ(IntegerLog2(uint16_t{4}), 2);
- EXPECT_EQ(IntegerLog2(uint16_t{5}), 2);
- EXPECT_EQ(IntegerLog2(std::numeric_limits<uint64_t>::max()), 63);
+ EXPECT_EQ(0, IntegerLog2(uint16_t{0}));
+ EXPECT_EQ(0, IntegerLog2(uint16_t{1}));
+ EXPECT_EQ(1, IntegerLog2(uint16_t{2}));
+ EXPECT_EQ(1, IntegerLog2(uint16_t{3}));
+ EXPECT_EQ(2, IntegerLog2(uint16_t{4}));
+ EXPECT_EQ(2, IntegerLog2(uint16_t{5}));
+ EXPECT_EQ(2, IntegerLog2(uint16_t{7}));
+ EXPECT_EQ(3, IntegerLog2(uint16_t{8}));
+ EXPECT_EQ(63, IntegerLog2((std::numeric_limits<uint64_t>::max)()));
}
TEST(FastUniformBitsTest, RangeSize) {
- EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 0, 3>>()), 4);
- EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 2, 2>>()), 1);
- EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 2, 5>>()), 4);
- EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 2, 6>>()), 5);
- EXPECT_EQ((RangeSize<FakeUrbg<uint8_t, 2, 10>>()), 9);
+ EXPECT_EQ(2, (RangeSize<FakeUrbg<uint8_t, 0, 1>>()));
+ EXPECT_EQ(3, (RangeSize<FakeUrbg<uint8_t, 0, 2>>()));
+ EXPECT_EQ(4, (RangeSize<FakeUrbg<uint8_t, 0, 3>>()));
+ // EXPECT_EQ(0, (RangeSize<FakeUrbg<uint8_t, 2, 2>>()));
+ EXPECT_EQ(4, (RangeSize<FakeUrbg<uint8_t, 2, 5>>()));
+ EXPECT_EQ(5, (RangeSize<FakeUrbg<uint8_t, 2, 6>>()));
+ EXPECT_EQ(9, (RangeSize<FakeUrbg<uint8_t, 2, 10>>()));
EXPECT_EQ(
- (RangeSize<FakeUrbg<uint8_t, 0, std::numeric_limits<uint8_t>::max()>>()),
- 0);
-
- EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 0, 3>>()), 4);
- EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 2, 2>>()), 1);
- EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 2, 5>>()), 4);
- EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 2, 6>>()), 5);
- EXPECT_EQ((RangeSize<FakeUrbg<uint16_t, 1000, 1017>>()), 18);
- EXPECT_EQ((RangeSize<
- FakeUrbg<uint16_t, 0, std::numeric_limits<uint16_t>::max()>>()),
- 0);
-
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 0, 3>>()), 4);
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 2, 2>>()), 1);
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 2, 5>>()), 4);
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 2, 6>>()), 5);
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 1000, 1017>>()), 18);
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 0, 0xffffffff>>()), 0);
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 1, 0xffffffff>>()), 0xffffffff);
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 1, 0xfffffffe>>()), 0xfffffffe);
- EXPECT_EQ((RangeSize<FakeUrbg<uint32_t, 2, 0xfffffffe>>()), 0xfffffffd);
- EXPECT_EQ((RangeSize<
- FakeUrbg<uint32_t, 0, std::numeric_limits<uint32_t>::max()>>()),
- 0);
-
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 0, 3>>()), 4);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 2>>()), 1);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 5>>()), 4);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 6>>()), 5);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1000, 1017>>()), 18);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 0, 0xffffffff>>()), 0x100000000ull);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1, 0xffffffff>>()), 0xffffffffull);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1, 0xfffffffe>>()), 0xfffffffeull);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 0xfffffffe>>()), 0xfffffffdull);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 0, 0xffffffffffffffffull>>()), 0ull);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1, 0xffffffffffffffffull>>()),
- 0xffffffffffffffffull);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 1, 0xfffffffffffffffeull>>()),
- 0xfffffffffffffffeull);
- EXPECT_EQ((RangeSize<FakeUrbg<uint64_t, 2, 0xfffffffffffffffeull>>()),
- 0xfffffffffffffffdull);
- EXPECT_EQ((RangeSize<
- FakeUrbg<uint64_t, 0, std::numeric_limits<uint64_t>::max()>>()),
- 0);
-}
+ 0, (RangeSize<
+ FakeUrbg<uint8_t, 0, (std::numeric_limits<uint8_t>::max)()>>()));
-TEST(FastUniformBitsTest, PowerOfTwoSubRangeSize) {
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 0, 3>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 2, 2>>()), 1);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 2, 5>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 2, 6>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint8_t, 2, 10>>()), 8);
- EXPECT_EQ((PowerOfTwoSubRangeSize<
- FakeUrbg<uint8_t, 0, std::numeric_limits<uint8_t>::max()>>()),
- 0);
-
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 0, 3>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 2, 2>>()), 1);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 2, 5>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 2, 6>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint16_t, 1000, 1017>>()), 16);
- EXPECT_EQ((PowerOfTwoSubRangeSize<
- FakeUrbg<uint16_t, 0, std::numeric_limits<uint16_t>::max()>>()),
- 0);
-
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 0, 3>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 2, 2>>()), 1);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 2, 5>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 2, 6>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 1000, 1017>>()), 16);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 0, 0xffffffff>>()), 0);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 1, 0xffffffff>>()),
- 0x80000000);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint32_t, 1, 0xfffffffe>>()),
- 0x80000000);
- EXPECT_EQ((PowerOfTwoSubRangeSize<
- FakeUrbg<uint32_t, 0, std::numeric_limits<uint32_t>::max()>>()),
- 0);
-
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 0, 3>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 2, 2>>()), 1);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 2, 5>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 2, 6>>()), 4);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1000, 1017>>()), 16);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 0, 0xffffffff>>()),
- 0x100000000ull);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1, 0xffffffff>>()),
- 0x80000000ull);
- EXPECT_EQ((PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1, 0xfffffffe>>()),
- 0x80000000ull);
+ EXPECT_EQ(4, (RangeSize<FakeUrbg<uint16_t, 0, 3>>()));
+ EXPECT_EQ(4, (RangeSize<FakeUrbg<uint16_t, 2, 5>>()));
+ EXPECT_EQ(5, (RangeSize<FakeUrbg<uint16_t, 2, 6>>()));
+ EXPECT_EQ(18, (RangeSize<FakeUrbg<uint16_t, 1000, 1017>>()));
EXPECT_EQ(
- (PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 0, 0xffffffffffffffffull>>()),
- 0);
+ 0, (RangeSize<
+ FakeUrbg<uint16_t, 0, (std::numeric_limits<uint16_t>::max)()>>()));
+
+ EXPECT_EQ(4, (RangeSize<FakeUrbg<uint32_t, 0, 3>>()));
+ EXPECT_EQ(4, (RangeSize<FakeUrbg<uint32_t, 2, 5>>()));
+ EXPECT_EQ(5, (RangeSize<FakeUrbg<uint32_t, 2, 6>>()));
+ EXPECT_EQ(18, (RangeSize<FakeUrbg<uint32_t, 1000, 1017>>()));
+ EXPECT_EQ(0, (RangeSize<FakeUrbg<uint32_t, 0, 0xffffffff>>()));
+ EXPECT_EQ(0xffffffff, (RangeSize<FakeUrbg<uint32_t, 1, 0xffffffff>>()));
+ EXPECT_EQ(0xfffffffe, (RangeSize<FakeUrbg<uint32_t, 1, 0xfffffffe>>()));
+ EXPECT_EQ(0xfffffffd, (RangeSize<FakeUrbg<uint32_t, 2, 0xfffffffe>>()));
EXPECT_EQ(
- (PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1, 0xffffffffffffffffull>>()),
- 0x8000000000000000ull);
+ 0, (RangeSize<
+ FakeUrbg<uint32_t, 0, (std::numeric_limits<uint32_t>::max)()>>()));
+
+ EXPECT_EQ(4, (RangeSize<FakeUrbg<uint64_t, 0, 3>>()));
+ EXPECT_EQ(4, (RangeSize<FakeUrbg<uint64_t, 2, 5>>()));
+ EXPECT_EQ(5, (RangeSize<FakeUrbg<uint64_t, 2, 6>>()));
+ EXPECT_EQ(18, (RangeSize<FakeUrbg<uint64_t, 1000, 1017>>()));
+ EXPECT_EQ(0x100000000, (RangeSize<FakeUrbg<uint64_t, 0, 0xffffffff>>()));
+ EXPECT_EQ(0xffffffff, (RangeSize<FakeUrbg<uint64_t, 1, 0xffffffff>>()));
+ EXPECT_EQ(0xfffffffe, (RangeSize<FakeUrbg<uint64_t, 1, 0xfffffffe>>()));
+ EXPECT_EQ(0xfffffffd, (RangeSize<FakeUrbg<uint64_t, 2, 0xfffffffe>>()));
+ EXPECT_EQ(0, (RangeSize<FakeUrbg<uint64_t, 0, 0xffffffffffffffff>>()));
+ EXPECT_EQ(0xffffffffffffffff,
+ (RangeSize<FakeUrbg<uint64_t, 1, 0xffffffffffffffff>>()));
+ EXPECT_EQ(0xfffffffffffffffe,
+ (RangeSize<FakeUrbg<uint64_t, 1, 0xfffffffffffffffe>>()));
+ EXPECT_EQ(0xfffffffffffffffd,
+ (RangeSize<FakeUrbg<uint64_t, 2, 0xfffffffffffffffe>>()));
EXPECT_EQ(
- (PowerOfTwoSubRangeSize<FakeUrbg<uint64_t, 1, 0xfffffffffffffffeull>>()),
- 0x8000000000000000ull);
- EXPECT_EQ((PowerOfTwoSubRangeSize<
- FakeUrbg<uint64_t, 0, std::numeric_limits<uint64_t>::max()>>()),
- 0);
+ 0, (RangeSize<
+ FakeUrbg<uint64_t, 0, (std::numeric_limits<uint64_t>::max)()>>()));
}
-TEST(FastUniformBitsTest, Urng4_VariousOutputs) {
+// The constants need to be choosen so that an infinite rejection loop doesn't
+// happen...
+using Urng1_5bit = FakeUrbg<uint8_t, 0, 2, 0>; // ~1.5 bits (range 3)
+using Urng4bits = FakeUrbg<uint8_t, 1, 0x10, 2>;
+using Urng22bits = FakeUrbg<uint32_t, 0, 0x3fffff, 0x301020>;
+using Urng31bits = FakeUrbg<uint32_t, 1, 0xfffffffe, 0x60070f03>; // ~31.9 bits
+using Urng32bits = FakeUrbg<uint32_t, 0, 0xffffffff, 0x74010f01>;
+using Urng33bits =
+ FakeUrbg<uint64_t, 1, 0x1ffffffff, 0x013301033>; // ~32.9 bits
+using Urng63bits = FakeUrbg<uint64_t, 1, 0xfffffffffffffffe,
+ 0xfedcba9012345678>; // ~63.9 bits
+using Urng64bits =
+ FakeUrbg<uint64_t, 0, 0xffffffffffffffff, 0x123456780fedcba9>;
+
+TEST(FastUniformBitsTest, OutputsUpTo32Bits) {
// Tests that how values are composed; the single-bit deltas should be spread
// across each invocation.
+ Urng1_5bit urng1_5;
Urng4bits urng4;
+ Urng22bits urng22;
Urng31bits urng31;
Urng32bits urng32;
+ Urng33bits urng33;
+ Urng63bits urng63;
+ Urng64bits urng64;
// 8-bit types
{
FastUniformBits<uint8_t> fast8;
+ EXPECT_EQ(0x0, fast8(urng1_5));
EXPECT_EQ(0x11, fast8(urng4));
+ EXPECT_EQ(0x20, fast8(urng22));
EXPECT_EQ(0x2, fast8(urng31));
EXPECT_EQ(0x1, fast8(urng32));
+ EXPECT_EQ(0x32, fast8(urng33));
+ EXPECT_EQ(0x77, fast8(urng63));
+ EXPECT_EQ(0xa9, fast8(urng64));
}
// 16-bit types
{
FastUniformBits<uint16_t> fast16;
+ EXPECT_EQ(0x0, fast16(urng1_5));
EXPECT_EQ(0x1111, fast16(urng4));
- EXPECT_EQ(0xf02, fast16(urng31));
- EXPECT_EQ(0xf01, fast16(urng32));
+ EXPECT_EQ(0x1020, fast16(urng22));
+ EXPECT_EQ(0x0f02, fast16(urng31));
+ EXPECT_EQ(0x0f01, fast16(urng32));
+ EXPECT_EQ(0x1032, fast16(urng33));
+ EXPECT_EQ(0x5677, fast16(urng63));
+ EXPECT_EQ(0xcba9, fast16(urng64));
}
// 32-bit types
{
FastUniformBits<uint32_t> fast32;
+ EXPECT_EQ(0x0, fast32(urng1_5));
EXPECT_EQ(0x11111111, fast32(urng4));
+ EXPECT_EQ(0x08301020, fast32(urng22));
EXPECT_EQ(0x0f020f02, fast32(urng31));
EXPECT_EQ(0x74010f01, fast32(urng32));
+ EXPECT_EQ(0x13301032, fast32(urng33));
+ EXPECT_EQ(0x12345677, fast32(urng63));
+ EXPECT_EQ(0x0fedcba9, fast32(urng64));
}
+}
+
+TEST(FastUniformBitsTest, Outputs64Bits) {
+ // Tests that how values are composed; the single-bit deltas should be spread
+ // across each invocation.
+ FastUniformBits<uint64_t> fast64;
- // 64-bit types
{
- FastUniformBits<uint64_t> fast64;
+ FakeUrbg<uint8_t, 0, 1, 0> urng0;
+ FakeUrbg<uint8_t, 0, 1, 1> urng1;
+ Urng4bits urng4;
+ Urng22bits urng22;
+ Urng31bits urng31;
+ Urng32bits urng32;
+ Urng33bits urng33;
+ Urng63bits urng63;
+ Urng64bits urng64;
+
+ // somewhat degenerate cases only create a single bit.
+ EXPECT_EQ(0x0, fast64(urng0));
+ EXPECT_EQ(64, urng0.calls);
+ EXPECT_EQ(0xffffffffffffffff, fast64(urng1));
+ EXPECT_EQ(64, urng1.calls);
+
+ // less degenerate cases.
EXPECT_EQ(0x1111111111111111, fast64(urng4));
+ EXPECT_EQ(16, urng4.calls);
+ EXPECT_EQ(0x01020c0408301020, fast64(urng22));
+ EXPECT_EQ(3, urng22.calls);
EXPECT_EQ(0x387811c3c0870f02, fast64(urng31));
+ EXPECT_EQ(3, urng31.calls);
EXPECT_EQ(0x74010f0174010f01, fast64(urng32));
+ EXPECT_EQ(2, urng32.calls);
+ EXPECT_EQ(0x808194040cb01032, fast64(urng33));
+ EXPECT_EQ(3, urng33.calls);
+ EXPECT_EQ(0x1234567712345677, fast64(urng63));
+ EXPECT_EQ(2, urng63.calls);
+ EXPECT_EQ(0x123456780fedcba9, fast64(urng64));
+ EXPECT_EQ(1, urng64.calls);
+ }
+
+ // The 1.5 bit case is somewhat interesting in that the algorithm refinement
+ // causes one extra small sample. Comments here reference the names used in
+ // [rand.adapt.ibits] that correspond to this case.
+ {
+ Urng1_5bit urng1_5;
+
+ // w = 64
+ // R = 3
+ // m = 1
+ // n' = 64
+ // w0' = 1
+ // y0' = 2
+ // n = (1 <= 0) > 64 : 65 = 65
+ // n0 = 65 - (64%65) = 1
+ // n1 = 64
+ // w0 = 0
+ // y0 = 3
+ // w1 = 1
+ // y1 = 2
+ EXPECT_EQ(0x0, fast64(urng1_5));
+ EXPECT_EQ(65, urng1_5.calls);
+ }
+
+ // Validate rejections for non-power-of-2 cases.
+ {
+ Urng1_5bit urng1_5(true);
+ Urng31bits urng31(true);
+ Urng33bits urng33(true);
+ Urng63bits urng63(true);
+
+ // For 1.5 bits, there would be 1+2*64, except the first
+ // value was accepted and shifted off the end.
+ EXPECT_EQ(0, fast64(urng1_5));
+ EXPECT_EQ(128, urng1_5.calls);
+ EXPECT_EQ(0x387811c3c0870f02, fast64(urng31));
+ EXPECT_EQ(6, urng31.calls);
+ EXPECT_EQ(0x808194040cb01032, fast64(urng33));
+ EXPECT_EQ(6, urng33.calls);
+ EXPECT_EQ(0x1234567712345677, fast64(urng63));
+ EXPECT_EQ(4, urng63.calls);
}
}
TEST(FastUniformBitsTest, URBG32bitRegression) {
// Validate with deterministic 32-bit std::minstd_rand
// to ensure that operator() performs as expected.
+
+ EXPECT_EQ(2147483646, RangeSize<std::minstd_rand>());
+ EXPECT_EQ(30, IntegerLog2(RangeSize<std::minstd_rand>()));
+
std::minstd_rand gen(1);
FastUniformBits<uint64_t> fast64;
- EXPECT_EQ(0x05e47095f847c122ull, fast64(gen));
- EXPECT_EQ(0x8f82c1ba30b64d22ull, fast64(gen));
- EXPECT_EQ(0x3b971a3558155039ull, fast64(gen));
+ EXPECT_EQ(0x05e47095f8791f45, fast64(gen));
+ EXPECT_EQ(0x028be17e3c07c122, fast64(gen));
+ EXPECT_EQ(0x55d2847c1626e8c2, fast64(gen));
}
} // namespace
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-04 06:43:55 +0000