Add helpers for implementing uniform integer distribution

* Utility for extended mult n x n bits -> 2n bits
* Utility to adapt output from URBG to target (unsigned) integral
  type
* Utility to reorder signed values into unsigned type while keeping
  the order.

4 files changed, 179 insertions, 0 deletions

diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index 4c3bad84..d3ab14a7 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -86,6 +86,7 @@ set(TEST_SOURCES
         ${SELF_TEST_DIR}/IntrospectiveTests/Details.tests.cpp
         ${SELF_TEST_DIR}/IntrospectiveTests/FloatingPoint.tests.cpp
         ${SELF_TEST_DIR}/IntrospectiveTests/GeneratorsImpl.tests.cpp
+        ${SELF_TEST_DIR}/IntrospectiveTests/Integer.tests.cpp
         ${SELF_TEST_DIR}/IntrospectiveTests/InternalBenchmark.tests.cpp
         ${SELF_TEST_DIR}/IntrospectiveTests/Json.tests.cpp
         ${SELF_TEST_DIR}/IntrospectiveTests/Parse.tests.cpp
diff --git a/tests/SelfTest/IntrospectiveTests/Integer.tests.cpp b/tests/SelfTest/IntrospectiveTests/Integer.tests.cpp
new file mode 100644
index 00000000..fd620ebb
--- /dev/null
+++ b/tests/SelfTest/IntrospectiveTests/Integer.tests.cpp
@@ -0,0 +1,150 @@
+
+//              Copyright Catch2 Authors
+// Distributed under the Boost Software License, Version 1.0.
+//   (See accompanying file LICENSE.txt or copy at
+//        https://www.boost.org/LICENSE_1_0.txt)
+
+// SPDX-License-Identifier: BSL-1.0
+
+#include <catch2/catch_test_macros.hpp>
+#include <catch2/internal/catch_random_integer_helpers.hpp>
+
+namespace {
+    template <typename Int>
+    static void
+    CommutativeMultCheck( Int a, Int b, Int upper_result, Int lower_result ) {
+        using Catch::Detail::extendedMult;
+        using Catch::Detail::ExtendedMultResult;
+        CHECK( extendedMult( a, b ) ==
+               ExtendedMultResult<Int>{ upper_result, lower_result } );
+        CHECK( extendedMult( b, a ) ==
+               ExtendedMultResult<Int>{ upper_result, lower_result } );
+    }
+} // namespace
+
+TEST_CASE( "extendedMult 64x64", "[Integer][approvals]" ) {
+    // a x 0 == 0
+    CommutativeMultCheck<uint64_t>( 0x1234'5678'9ABC'DEFF, 0, 0, 0 );
+
+    // bit carried from low half to upper half
+    CommutativeMultCheck<uint64_t>( uint64_t( 1 ) << 63, 2, 1, 0 );
+
+    // bits in upper half on one side, bits in lower half on other side
+    CommutativeMultCheck<uint64_t>( 0xcdcd'dcdc'0000'0000,
+                                    0x0000'0000'aeae'aeae,
+                                    0x0000'0000'8c6e'5a77,
+                                    0x7391'a588'0000'0000 );
+
+    // Some input numbers without interesting patterns
+    CommutativeMultCheck<uint64_t>( 0xaaaa'aaaa'aaaa'aaaa,
+                                    0xbbbb'bbbb'bbbb'bbbb,
+                                    0x7d27'd27d'27d2'7d26,
+                                    0xd82d'82d8'2d82'd82e );
+
+    CommutativeMultCheck<uint64_t>( 0x7d27'd27d'27d2'7d26,
+                                    0xd82d'82d8'2d82'd82e,
+                                    0x69af'd991'8256'b953,
+                                    0x8724'8909'fcb6'8cd4 );
+
+    CommutativeMultCheck<uint64_t>( 0xdead'beef'dead'beef,
+                                    0xfeed'feed'feed'feef,
+                                    0xddbf'680b'2b0c'b558,
+                                    0x7a36'b06f'2ce9'6321 );
+
+    CommutativeMultCheck<uint64_t>( 0xddbf'680b'2b0c'b558,
+                                    0x7a36'b06f'2ce9'6321,
+                                    0x69dc'96c9'294b'fc7f,
+                                    0xd038'39fa'a3dc'6858 );
+
+    CommutativeMultCheck<uint64_t>( 0x61c8'8646'80b5'83eb,
+                                    0x61c8'8646'80b5'83eb,
+                                    0x2559'92d3'8220'8bbe,
+                                    0xdf44'2d22'ce48'59b9 );
+}
+
+TEST_CASE( "SizedUnsignedType helpers", "[integer][approvals]" ) {
+    using Catch::Detail::SizedUnsignedType_t;
+    using Catch::Detail::DoubleWidthUnsignedType_t;
+
+    STATIC_REQUIRE( sizeof( SizedUnsignedType_t<1> ) == 1 );
+    STATIC_REQUIRE( sizeof( SizedUnsignedType_t<2> ) == 2 );
+    STATIC_REQUIRE( sizeof( SizedUnsignedType_t<4> ) == 4 );
+    STATIC_REQUIRE( sizeof( SizedUnsignedType_t<8> ) == 8 );
+
+    STATIC_REQUIRE( sizeof( DoubleWidthUnsignedType_t<std::uint8_t> ) == 2 );
+    STATIC_REQUIRE( std::is_unsigned<DoubleWidthUnsignedType_t<std::uint8_t>>::value );
+    STATIC_REQUIRE( sizeof( DoubleWidthUnsignedType_t<std::uint16_t> ) == 4 );
+    STATIC_REQUIRE( std::is_unsigned<DoubleWidthUnsignedType_t<std::uint16_t>>::value );
+    STATIC_REQUIRE( sizeof( DoubleWidthUnsignedType_t<std::uint32_t> ) == 8 );
+    STATIC_REQUIRE( std::is_unsigned<DoubleWidthUnsignedType_t<std::uint32_t>>::value );
+}
+
+TEST_CASE( "extendedMult 32x32", "[integer][approvals]" ) {
+    // a x 0 == 0
+    CommutativeMultCheck<uint32_t>( 0x1234'5678, 0, 0, 0 );
+
+    // bit carried from low half to upper half
+    CommutativeMultCheck<uint32_t>( uint32_t(1) << 31, 2, 1, 0 );
+
+    // bits in upper half on one side, bits in lower half on other side
+    CommutativeMultCheck<uint32_t>( 0xdcdc'0000, 0x0000'aabb, 0x0000'934b, 0x6cb4'0000 );
+
+    // Some input numbers without interesting patterns
+    CommutativeMultCheck<uint32_t>(
+        0xaaaa'aaaa, 0xbbbb'bbbb, 0x7d27'd27c, 0x2d82'd82e );
+
+    CommutativeMultCheck<uint32_t>(
+        0x7d27'd27c, 0x2d82'd82e, 0x163f'f7e8, 0xc5b8'7248 );
+
+    CommutativeMultCheck<uint32_t>(
+        0xdead'beef, 0xfeed'feed, 0xddbf'6809, 0x6f8d'e543 );
+
+    CommutativeMultCheck<uint32_t>(
+        0xddbf'6809, 0x6f8d'e543, 0x60a0'e71e, 0x751d'475b );
+}
+
+TEST_CASE( "extendedMult 8x8", "[integer][approvals]" ) {
+    // a x 0 == 0
+    CommutativeMultCheck<uint8_t>( 0xcd, 0, 0, 0 );
+
+    // bit carried from low half to upper half
+    CommutativeMultCheck<uint8_t>( uint8_t( 1 ) << 7, 2, 1, 0 );
+
+    // bits in upper half on one side, bits in lower half on other side
+    CommutativeMultCheck<uint8_t>( 0x80, 0x03, 0x01, 0x80 );
+
+    // Some input numbers without interesting patterns
+    CommutativeMultCheck<uint8_t>( 0xaa, 0xbb, 0x7c, 0x2e );
+    CommutativeMultCheck<uint8_t>( 0x7c, 0x2e, 0x16, 0x48 );
+    CommutativeMultCheck<uint8_t>( 0xdc, 0xcd, 0xb0, 0x2c );
+    CommutativeMultCheck<uint8_t>( 0xb0, 0x2c, 0x1e, 0x40 );
+}
+
+
+TEST_CASE( "negative and positive signed integers keep their order after transposeToNaturalOrder",
+                    "[integer][approvals]") {
+    using Catch::Detail::transposeToNaturalOrder;
+    int32_t negative( -1 );
+    int32_t positive( 1 );
+    uint32_t adjusted_negative =
+        transposeToNaturalOrder<int32_t>( static_cast<uint32_t>( negative ) );
+    uint32_t adjusted_positive =
+        transposeToNaturalOrder<int32_t>( static_cast<uint32_t>( positive ) );
+    REQUIRE( adjusted_negative < adjusted_positive );
+    REQUIRE( adjusted_positive - adjusted_negative == 2 );
+
+    // Conversion has to be reversible
+    REQUIRE( negative == static_cast<int32_t>( transposeToNaturalOrder<int32_t>(
+                             adjusted_negative ) ) );
+    REQUIRE( positive == static_cast<int32_t>( transposeToNaturalOrder<int32_t>(
+                             adjusted_positive ) ) );
+}
+
+TEST_CASE( "unsigned integers are unchanged by transposeToNaturalOrder",
+           "[integer][approvals]") {
+    using Catch::Detail::transposeToNaturalOrder;
+    uint32_t max = std::numeric_limits<uint32_t>::max();
+    uint32_t zero = 0;
+    REQUIRE( max == transposeToNaturalOrder<uint32_t>( max ) );
+    REQUIRE( zero == transposeToNaturalOrder<uint32_t>( zero ) );
+}
diff --git a/tests/SelfTest/IntrospectiveTests/RandomNumberGeneration.tests.cpp b/tests/SelfTest/IntrospectiveTests/RandomNumberGeneration.tests.cpp
index ad44668d..d432b445 100644
--- a/tests/SelfTest/IntrospectiveTests/RandomNumberGeneration.tests.cpp
+++ b/tests/SelfTest/IntrospectiveTests/RandomNumberGeneration.tests.cpp
@@ -8,6 +8,7 @@
 
 #include <catch2/catch_test_macros.hpp>
 #include <catch2/catch_template_test_macros.hpp>
+#include <catch2/internal/catch_random_integer_helpers.hpp>
 #include <catch2/internal/catch_random_number_generator.hpp>
 #include <catch2/internal/catch_random_seed_generation.hpp>
 #include <catch2/internal/catch_uniform_floating_point_distribution.hpp>
@@ -77,3 +78,29 @@ TEMPLATE_TEST_CASE("uniform_floating_point_distribution never returns infs from
         REQUIRE_FALSE( std::isnan( ret ) );
     }
 }
+
+TEST_CASE( "fillBitsFrom - shortening and stretching", "[rng][approvals]" ) {
+    using Catch::Detail::fillBitsFrom;
+
+    // The seed is not important, but the numbers below have to be repeatable.
+    // They should also exhibit the same general pattern of being prefixes
+    Catch::SimplePcg32 pcg( 0xaabb'ccdd );
+
+    SECTION( "Shorten to 8 bits" ) {
+        // We cast the result to avoid dealing with char-like type in uint8_t
+        auto shortened = static_cast<uint32_t>( fillBitsFrom<uint8_t>( pcg ) );
+        REQUIRE( shortened == 0xcc );
+    }
+    SECTION( "Shorten to 16 bits" ) {
+        auto shortened = fillBitsFrom<uint16_t>( pcg );
+        REQUIRE( shortened == 0xccbe );
+    }
+    SECTION( "Keep at 32 bits" ) {
+        auto n = fillBitsFrom<uint32_t>( pcg );
+        REQUIRE( n == 0xccbe'5f04 );
+    }
+    SECTION( "Stretch to 64 bits" ) {
+        auto stretched = fillBitsFrom<uint64_t>( pcg );
+        REQUIRE( stretched == 0xccbe'5f04'a424'a486 );
+    }
+}
diff --git a/tests/meson.build b/tests/meson.build
index f525f041..58302b7a 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -17,6 +17,7 @@ self_test_sources = files(
   'SelfTest/IntrospectiveTests/Details.tests.cpp',
   'SelfTest/IntrospectiveTests/FloatingPoint.tests.cpp',
   'SelfTest/IntrospectiveTests/GeneratorsImpl.tests.cpp',
+  'SelfTest/IntrospectiveTests/Integer.tests.cpp',
   'SelfTest/IntrospectiveTests/InternalBenchmark.tests.cpp',
   'SelfTest/IntrospectiveTests/Parse.tests.cpp',
   'SelfTest/IntrospectiveTests/PartTracker.tests.cpp',