absl/random/internal/fast_uniform_bits_test.cc

// Copyright 2017 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "absl/random/internal/fast_uniform_bits.h"

#include <random>

#include "gtest/gtest.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace random_internal {
namespace {

template <typename IntType>
class FastUniformBitsTypedTest : public ::testing::Test {};

using IntTypes = ::testing::Types<uint8_t, uint16_t, uint32_t, uint64_t>;

TYPED_TEST_SUITE(FastUniformBitsTypedTest, IntTypes);

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)());

  constexpr int kIters = 10000;
  std::random_device rd;
  std::mt19937 gen(rd());
  FastBits fast;
  for (int i = 0; i < kIters; i++) {
    const auto v = fast(gen);
    EXPECT_LE(v, (FastBits::max)());
    EXPECT_GE(v, (FastBits::min)());
  }
}

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()() {
    // when reject is set, return Hi half the time.
    return ((++calls % 2) == 1 && reject) ? Hi : Val;
  }

  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)()));

  EXPECT_TRUE(IsPowerOfTwoOrZero(uint16_t{0}));
  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)()));

  EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{0}));
  EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{1}));
  EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{2}));
  EXPECT_FALSE(IsPowerOfTwoOrZero(uint32_t{3}));
  EXPECT_TRUE(IsPowerOfTwoOrZero(uint32_t{32}));
  EXPECT_FALSE(IsPowerOfTwoOrZero(uint32_t{17}));
  EXPECT_FALSE(IsPowerOfTwoOrZero((std::numeric_limits<uint32_t>::max)()));

  EXPECT_TRUE(IsPowerOfTwoOrZero(uint64_t{0}));
  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(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(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(
      0, (RangeSize<
             FakeUrbg<uint8_t, 0, (std::numeric_limits<uint8_t>::max)()>>()));

  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(
      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(
      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(
      0, (RangeSize<
             FakeUrbg<uint64_t, 0, (std::numeric_limits<uint64_t>::max)()>>()));
}

// 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(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;

  {
    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(0x05e47095f8791f45, fast64(gen));
  EXPECT_EQ(0x028be17e3c07c122, fast64(gen));
  EXPECT_EQ(0x55d2847c1626e8c2, fast64(gen));
}

}  // namespace
}  // namespace random_internal
ABSL_NAMESPACE_END
}  // namespace absl