catch_random_integer_helpers.hpp
1 2 // Copyright Catch2 Authors 3 // Distributed under the Boost Software License, Version 1.0. 4 // (See accompanying file LICENSE.txt or copy at 5 // https://www.boost.org/LICENSE_1_0.txt) 6 7 // SPDX-License-Identifier: BSL-1.0 8 9 #ifndef CATCH_RANDOM_INTEGER_HELPERS_HPP_INCLUDED 10 #define CATCH_RANDOM_INTEGER_HELPERS_HPP_INCLUDED 11 12 #include <climits> 13 #include <cstddef> 14 #include <cstdint> 15 #include <type_traits> 16 17 namespace Catch { 18 namespace Detail { 19 20 template <std::size_t> 21 struct SizedUnsignedType; 22 #define SizedUnsignedTypeHelper( TYPE ) \ 23 template <> \ 24 struct SizedUnsignedType<sizeof( TYPE )> { \ 25 using type = TYPE; \ 26 } 27 28 SizedUnsignedTypeHelper( std::uint8_t ); 29 SizedUnsignedTypeHelper( std::uint16_t ); 30 SizedUnsignedTypeHelper( std::uint32_t ); 31 SizedUnsignedTypeHelper( std::uint64_t ); 32 #undef SizedUnsignedTypeHelper 33 34 template <std::size_t sz> 35 using SizedUnsignedType_t = typename SizedUnsignedType<sz>::type; 36 37 template <typename T> 38 using DoubleWidthUnsignedType_t = SizedUnsignedType_t<2 * sizeof( T )>; 39 40 template <typename T> 41 struct ExtendedMultResult { 42 T upper; 43 T lower; 44 friend bool operator==( ExtendedMultResult const& lhs, 45 ExtendedMultResult const& rhs ) { 46 return lhs.upper == rhs.upper && lhs.lower == rhs.lower; 47 } 48 }; 49 50 // Returns 128 bit result of multiplying lhs and rhs 51 constexpr ExtendedMultResult<std::uint64_t> 52 extendedMult( std::uint64_t lhs, std::uint64_t rhs ) { 53 // We use the simple long multiplication approach for 54 // correctness, we can use platform specific builtins 55 // for performance later. 56 57 // Split the lhs and rhs into two 32bit "digits", so that we can 58 // do 64 bit arithmetic to handle carry bits. 59 // 32b 32b 32b 32b 60 // lhs L1 L2 61 // * rhs R1 R2 62 // ------------------------ 63 // | R2 * L2 | 64 // | R2 * L1 | 65 // | R1 * L2 | 66 // | R1 * L1 | 67 // ------------------------- 68 // | a | b | c | d | 69 70 #define CarryBits( x ) ( x >> 32 ) 71 #define Digits( x ) ( x & 0xFF'FF'FF'FF ) 72 73 auto r2l2 = Digits( rhs ) * Digits( lhs ); 74 auto r2l1 = Digits( rhs ) * CarryBits( lhs ); 75 auto r1l2 = CarryBits( rhs ) * Digits( lhs ); 76 auto r1l1 = CarryBits( rhs ) * CarryBits( lhs ); 77 78 // Sum to columns first 79 auto d = Digits( r2l2 ); 80 auto c = CarryBits( r2l2 ) + Digits( r2l1 ) + Digits( r1l2 ); 81 auto b = CarryBits( r2l1 ) + CarryBits( r1l2 ) + Digits( r1l1 ); 82 auto a = CarryBits( r1l1 ); 83 84 // Propagate carries between columns 85 c += CarryBits( d ); 86 b += CarryBits( c ); 87 a += CarryBits( b ); 88 89 // Remove the used carries 90 c = Digits( c ); 91 b = Digits( b ); 92 a = Digits( a ); 93 94 #undef CarryBits 95 #undef Digits 96 97 return { 98 a << 32 | b, // upper 64 bits 99 c << 32 | d // lower 64 bits 100 }; 101 } 102 103 template <typename UInt> 104 constexpr ExtendedMultResult<UInt> extendedMult( UInt lhs, UInt rhs ) { 105 static_assert( std::is_unsigned<UInt>::value, 106 "extendedMult can only handle unsigned integers" ); 107 static_assert( sizeof( UInt ) < sizeof( std::uint64_t ), 108 "Generic extendedMult can only handle types smaller " 109 "than uint64_t" ); 110 using WideType = DoubleWidthUnsignedType_t<UInt>; 111 112 auto result = WideType( lhs ) * WideType( rhs ); 113 return { 114 static_cast<UInt>( result >> ( CHAR_BIT * sizeof( UInt ) ) ), 115 static_cast<UInt>( result & UInt( -1 ) ) }; 116 } 117 118 119 template <typename TargetType, 120 typename Generator> 121 std::enable_if_t<sizeof(typename Generator::result_type) >= sizeof(TargetType), 122 TargetType> fillBitsFrom(Generator& gen) { 123 using gresult_type = typename Generator::result_type; 124 static_assert( std::is_unsigned<TargetType>::value, "Only unsigned integers are supported" ); 125 static_assert( Generator::min() == 0 && 126 Generator::max() == static_cast<gresult_type>( -1 ), 127 "Generator must be able to output all numbers in its result type (effectively it must be a random bit generator)" ); 128 129 // We want to return the top bits from a generator, as they are 130 // usually considered higher quality. 131 constexpr auto generated_bits = sizeof( gresult_type ) * CHAR_BIT; 132 constexpr auto return_bits = sizeof( TargetType ) * CHAR_BIT; 133 134 return static_cast<TargetType>( gen() >> 135 ( generated_bits - return_bits) ); 136 } 137 138 template <typename TargetType, 139 typename Generator> 140 std::enable_if_t<sizeof(typename Generator::result_type) < sizeof(TargetType), 141 TargetType> fillBitsFrom(Generator& gen) { 142 using gresult_type = typename Generator::result_type; 143 static_assert( std::is_unsigned<TargetType>::value, 144 "Only unsigned integers are supported" ); 145 static_assert( Generator::min() == 0 && 146 Generator::max() == static_cast<gresult_type>( -1 ), 147 "Generator must be able to output all numbers in its result type (effectively it must be a random bit generator)" ); 148 149 constexpr auto generated_bits = sizeof( gresult_type ) * CHAR_BIT; 150 constexpr auto return_bits = sizeof( TargetType ) * CHAR_BIT; 151 std::size_t filled_bits = 0; 152 TargetType ret = 0; 153 do { 154 ret <<= generated_bits; 155 ret |= gen(); 156 filled_bits += generated_bits; 157 } while ( filled_bits < return_bits ); 158 159 return ret; 160 } 161 162 /* 163 * Transposes numbers into unsigned type while keeping their ordering 164 * 165 * This means that signed types are changed so that the ordering is 166 * [INT_MIN, ..., -1, 0, ..., INT_MAX], rather than order we would 167 * get by simple casting ([0, ..., INT_MAX, INT_MIN, ..., -1]) 168 */ 169 template <typename OriginalType, typename UnsignedType> 170 std::enable_if_t<std::is_signed<OriginalType>::value, UnsignedType> 171 transposeToNaturalOrder( UnsignedType in ) { 172 static_assert( 173 sizeof( OriginalType ) == sizeof( UnsignedType ), 174 "reordering requires the same sized types on both sides" ); 175 static_assert( std::is_unsigned<UnsignedType>::value, 176 "Input type must be unsigned" ); 177 // Assuming 2s complement (standardized in current C++), the 178 // positive and negative numbers are already internally ordered, 179 // and their difference is in the top bit. Swapping it orders 180 // them the desired way. 181 constexpr auto highest_bit = 182 UnsignedType( 1 ) << ( sizeof( UnsignedType ) * CHAR_BIT - 1 ); 183 return static_cast<UnsignedType>( in ^ highest_bit ); 184 } 185 186 187 188 template <typename OriginalType, 189 typename UnsignedType> 190 std::enable_if_t<std::is_unsigned<OriginalType>::value, UnsignedType> 191 transposeToNaturalOrder(UnsignedType in) { 192 static_assert( 193 sizeof( OriginalType ) == sizeof( UnsignedType ), 194 "reordering requires the same sized types on both sides" ); 195 static_assert( std::is_unsigned<UnsignedType>::value, "Input type must be unsigned" ); 196 // No reordering is needed for unsigned -> unsigned 197 return in; 198 } 199 } // namespace Detail 200 } // namespace Catch 201 202 #endif // CATCH_RANDOM_INTEGER_HELPERS_HPP_INCLUDED