catch2/internal/catch_random_integer_helpers.hpp

0001
0002 //              Copyright Catch2 Authors
0003 // Distributed under the Boost Software License, Version 1.0.
0004 //   (See accompanying file LICENSE.txt or copy at
0005 //        https://www.boost.org/LICENSE_1_0.txt)
0006
0007 // SPDX-License-Identifier: BSL-1.0
0008
0009 #ifndef CATCH_RANDOM_INTEGER_HELPERS_HPP_INCLUDED
0010 #define CATCH_RANDOM_INTEGER_HELPERS_HPP_INCLUDED
0011
0012 #include <climits>
0013 #include <cstddef>
0014 #include <cstdint>
0015 #include <type_traits>
0016
0017 // Note: We use the usual enable-disable-autodetect dance here even though
0018 //       we do not support these in CMake configuration options (yet?).
0019 //       It is highly unlikely that we will need to make these actually
0020 //       user-configurable, but this will make it simpler if weend up needing
0021 //       it, and it provides an escape hatch to the users who need it.
0022 #if defined( __SIZEOF_INT128__ )
0023 #    define CATCH_CONFIG_INTERNAL_UINT128
0024 // Unlike GCC, MSVC does not polyfill umul as mulh + mul pair on ARM machines.
0025 // Currently we do not bother doing this ourselves, but we could if it became
0026 // important for perf.
0027 #elif defined( _MSC_VER ) && defined( _M_X64 )
0028 #    define CATCH_CONFIG_INTERNAL_MSVC_UMUL128
0029 #endif
0030
0031 #if defined( CATCH_CONFIG_INTERNAL_UINT128 ) && \
0032     !defined( CATCH_CONFIG_NO_UINT128 ) &&      \
0033     !defined( CATCH_CONFIG_UINT128 )
0034 #define CATCH_CONFIG_UINT128
0035 #endif
0036
0037 #if defined( CATCH_CONFIG_INTERNAL_MSVC_UMUL128 ) && \
0038     !defined( CATCH_CONFIG_NO_MSVC_UMUL128 ) &&      \
0039     !defined( CATCH_CONFIG_MSVC_UMUL128 )
0040 #    define CATCH_CONFIG_MSVC_UMUL128
0041 #    include <intrin.h>
0042 #endif
0043
0044
0045 namespace Catch {
0046     namespace Detail {
0047
0048         template <std::size_t>
0049         struct SizedUnsignedType;
0050 #define SizedUnsignedTypeHelper( TYPE )        \
0051     template <>                                \
0052     struct SizedUnsignedType<sizeof( TYPE )> { \
0053         using type = TYPE;                     \
0054     }
0055
0056         SizedUnsignedTypeHelper( std::uint8_t );
0057         SizedUnsignedTypeHelper( std::uint16_t );
0058         SizedUnsignedTypeHelper( std::uint32_t );
0059         SizedUnsignedTypeHelper( std::uint64_t );
0060 #undef SizedUnsignedTypeHelper
0061
0062         template <std::size_t sz>
0063         using SizedUnsignedType_t = typename SizedUnsignedType<sz>::type;
0064
0065         template <typename T>
0066         using DoubleWidthUnsignedType_t = SizedUnsignedType_t<2 * sizeof( T )>;
0067
0068         template <typename T>
0069         struct ExtendedMultResult {
0070             T upper;
0071             T lower;
0072             constexpr bool operator==( ExtendedMultResult const& rhs ) const {
0073                 return upper == rhs.upper && lower == rhs.lower;
0074             }
0075         };
0076
0077         /**
0078          * Returns 128 bit result of lhs * rhs using portable C++ code
0079          *
0080          * This implementation is almost twice as fast as naive long multiplication,
0081          * and unlike intrinsic-based approach, it supports constexpr evaluation.
0082          */
0083         constexpr ExtendedMultResult<std::uint64_t>
0084         extendedMultPortable(std::uint64_t lhs, std::uint64_t rhs) {
0085 #define CarryBits( x ) ( x >> 32 )
0086 #define Digits( x ) ( x & 0xFF'FF'FF'FF )
0087             std::uint64_t lhs_low = Digits( lhs );
0088             std::uint64_t rhs_low = Digits( rhs );
0089             std::uint64_t low_low = ( lhs_low * rhs_low );
0090             std::uint64_t high_high = CarryBits( lhs ) * CarryBits( rhs );
0091
0092             // We add in carry bits from low-low already
0093             std::uint64_t high_low =
0094                 ( CarryBits( lhs ) * rhs_low ) + CarryBits( low_low );
0095             // Note that we can add only low bits from high_low, to avoid
0096             // overflow with large inputs
0097             std::uint64_t low_high =
0098                 ( lhs_low * CarryBits( rhs ) ) + Digits( high_low );
0099
0100             return { high_high + CarryBits( high_low ) + CarryBits( low_high ),
0101                      ( low_high << 32 ) | Digits( low_low ) };
0102 #undef CarryBits
0103 #undef Digits
0104         }
0105
0106         //! Returns 128 bit result of lhs * rhs
0107         inline ExtendedMultResult<std::uint64_t>
0108         extendedMult( std::uint64_t lhs, std::uint64_t rhs ) {
0109 #if defined( CATCH_CONFIG_UINT128 )
0110             auto result = __uint128_t( lhs ) * __uint128_t( rhs );
0111             return { static_cast<std::uint64_t>( result >> 64 ),
0112                      static_cast<std::uint64_t>( result ) };
0113 #elif defined( CATCH_CONFIG_MSVC_UMUL128 )
0114             std::uint64_t high;
0115             std::uint64_t low = _umul128( lhs, rhs, &high );
0116             return { high, low };
0117 #else
0118             return extendedMultPortable( lhs, rhs );
0119 #endif
0120         }
0121
0122
0123         template <typename UInt>
0124         constexpr ExtendedMultResult<UInt> extendedMult( UInt lhs, UInt rhs ) {
0125             static_assert( std::is_unsigned<UInt>::value,
0126                            "extendedMult can only handle unsigned integers" );
0127             static_assert( sizeof( UInt ) < sizeof( std::uint64_t ),
0128                            "Generic extendedMult can only handle types smaller "
0129                            "than uint64_t" );
0130             using WideType = DoubleWidthUnsignedType_t<UInt>;
0131
0132             auto result = WideType( lhs ) * WideType( rhs );
0133             return {
0134                 static_cast<UInt>( result >> ( CHAR_BIT * sizeof( UInt ) ) ),
0135                 static_cast<UInt>( result & UInt( -1 ) ) };
0136         }
0137
0138
0139         template <typename TargetType,
0140                   typename Generator>
0141             std::enable_if_t<sizeof(typename Generator::result_type) >= sizeof(TargetType),
0142             TargetType> fillBitsFrom(Generator& gen) {
0143             using gresult_type = typename Generator::result_type;
0144             static_assert( std::is_unsigned<TargetType>::value, "Only unsigned integers are supported" );
0145             static_assert( Generator::min() == 0 &&
0146                            Generator::max() == static_cast<gresult_type>( -1 ),
0147                            "Generator must be able to output all numbers in its result type (effectively it must be a random bit generator)" );
0148
0149             // We want to return the top bits from a generator, as they are
0150             // usually considered higher quality.
0151             constexpr auto generated_bits = sizeof( gresult_type ) * CHAR_BIT;
0152             constexpr auto return_bits = sizeof( TargetType ) * CHAR_BIT;
0153
0154             return static_cast<TargetType>( gen() >>
0155                                             ( generated_bits - return_bits) );
0156         }
0157
0158         template <typename TargetType,
0159                   typename Generator>
0160             std::enable_if_t<sizeof(typename Generator::result_type) < sizeof(TargetType),
0161             TargetType> fillBitsFrom(Generator& gen) {
0162             using gresult_type = typename Generator::result_type;
0163             static_assert( std::is_unsigned<TargetType>::value,
0164                            "Only unsigned integers are supported" );
0165             static_assert( Generator::min() == 0 &&
0166                            Generator::max() == static_cast<gresult_type>( -1 ),
0167                            "Generator must be able to output all numbers in its result type (effectively it must be a random bit generator)" );
0168
0169             constexpr auto generated_bits = sizeof( gresult_type ) * CHAR_BIT;
0170             constexpr auto return_bits = sizeof( TargetType ) * CHAR_BIT;
0171             std::size_t filled_bits = 0;
0172             TargetType ret = 0;
0173             do {
0174                 ret <<= generated_bits;
0175                 ret |= gen();
0176                 filled_bits += generated_bits;
0177             } while ( filled_bits < return_bits );
0178
0179             return ret;
0180         }
0181
0182         /*
0183          * Transposes numbers into unsigned type while keeping their ordering
0184          *
0185          * This means that signed types are changed so that the ordering is
0186          * [INT_MIN, ..., -1, 0, ..., INT_MAX], rather than order we would
0187          * get by simple casting ([0, ..., INT_MAX, INT_MIN, ..., -1])
0188          */
0189         template <typename OriginalType, typename UnsignedType>
0190         constexpr
0191         std::enable_if_t<std::is_signed<OriginalType>::value, UnsignedType>
0192         transposeToNaturalOrder( UnsignedType in ) {
0193             static_assert(
0194                 sizeof( OriginalType ) == sizeof( UnsignedType ),
0195                 "reordering requires the same sized types on both sides" );
0196             static_assert( std::is_unsigned<UnsignedType>::value,
0197                            "Input type must be unsigned" );
0198             // Assuming 2s complement (standardized in current C++), the
0199             // positive and negative numbers are already internally ordered,
0200             // and their difference is in the top bit. Swapping it orders
0201             // them the desired way.
0202             constexpr auto highest_bit =
0203                 UnsignedType( 1 ) << ( sizeof( UnsignedType ) * CHAR_BIT - 1 );
0204             return static_cast<UnsignedType>( in ^ highest_bit );
0205         }
0206
0207
0208
0209         template <typename OriginalType,
0210                   typename UnsignedType>
0211         constexpr
0212         std::enable_if_t<std::is_unsigned<OriginalType>::value, UnsignedType>
0213             transposeToNaturalOrder(UnsignedType in) {
0214             static_assert(
0215                 sizeof( OriginalType ) == sizeof( UnsignedType ),
0216                 "reordering requires the same sized types on both sides" );
0217             static_assert( std::is_unsigned<UnsignedType>::value, "Input type must be unsigned" );
0218             // No reordering is needed for unsigned -> unsigned
0219             return in;
0220         }
0221     } // namespace Detail
0222 } // namespace Catch
0223
0224 #endif // CATCH_RANDOM_INTEGER_HELPERS_HPP_INCLUDED