diff options
Diffstat (limited to 'abseil-cpp/absl/random/internal/wide_multiply.h')
-rw-r--r-- | abseil-cpp/absl/random/internal/wide_multiply.h | 83 |
1 files changed, 34 insertions, 49 deletions
diff --git a/abseil-cpp/absl/random/internal/wide_multiply.h b/abseil-cpp/absl/random/internal/wide_multiply.h index 0afcbe0..891e363 100644 --- a/abseil-cpp/absl/random/internal/wide_multiply.h +++ b/abseil-cpp/absl/random/internal/wide_multiply.h @@ -26,7 +26,7 @@ #endif #include "absl/base/config.h" -#include "absl/base/internal/bits.h" +#include "absl/numeric/bits.h" #include "absl/numeric/int128.h" #include "absl/random/internal/traits.h" @@ -34,43 +34,6 @@ namespace absl { ABSL_NAMESPACE_BEGIN namespace random_internal { -// Helper object to multiply two 64-bit values to a 128-bit value. -// MultiplyU64ToU128 multiplies two 64-bit values to a 128-bit value. -// If an intrinsic is available, it is used, otherwise use native 32-bit -// multiplies to construct the result. -inline absl::uint128 MultiplyU64ToU128(uint64_t a, uint64_t b) { -#if defined(ABSL_HAVE_INTRINSIC_INT128) - return absl::uint128(static_cast<__uint128_t>(a) * b); -#elif defined(ABSL_INTERNAL_USE_UMUL128) - // uint64_t * uint64_t => uint128 multiply using imul intrinsic on MSVC. - uint64_t high = 0; - const uint64_t low = _umul128(a, b, &high); - return absl::MakeUint128(high, low); -#else - // uint128(a) * uint128(b) in emulated mode computes a full 128-bit x 128-bit - // multiply. However there are many cases where that is not necessary, and it - // is only necessary to support a 64-bit x 64-bit = 128-bit multiply. This is - // for those cases. - const uint64_t a00 = static_cast<uint32_t>(a); - const uint64_t a32 = a >> 32; - const uint64_t b00 = static_cast<uint32_t>(b); - const uint64_t b32 = b >> 32; - - const uint64_t c00 = a00 * b00; - const uint64_t c32a = a00 * b32; - const uint64_t c32b = a32 * b00; - const uint64_t c64 = a32 * b32; - - const uint32_t carry = - static_cast<uint32_t>(((c00 >> 32) + static_cast<uint32_t>(c32a) + - static_cast<uint32_t>(c32b)) >> - 32); - - return absl::MakeUint128(c64 + (c32a >> 32) + (c32b >> 32) + carry, - c00 + (c32a << 32) + (c32b << 32)); -#endif -} - // wide_multiply<T> multiplies two N-bit values to a 2N-bit result. template <typename UIntType> struct wide_multiply { @@ -82,27 +45,49 @@ struct wide_multiply { return static_cast<result_type>(a) * b; } - static input_type hi(result_type r) { return r >> kN; } - static input_type lo(result_type r) { return r; } + static input_type hi(result_type r) { + return static_cast<input_type>(r >> kN); + } + static input_type lo(result_type r) { return static_cast<input_type>(r); } static_assert(std::is_unsigned<UIntType>::value, "Class-template wide_multiply<> argument must be unsigned."); }; -#ifndef ABSL_HAVE_INTRINSIC_INT128 +// MultiplyU128ToU256 multiplies two 128-bit values to a 256-bit value. +inline U256 MultiplyU128ToU256(uint128 a, uint128 b) { + const uint128 a00 = static_cast<uint64_t>(a); + const uint128 a64 = a >> 64; + const uint128 b00 = static_cast<uint64_t>(b); + const uint128 b64 = b >> 64; + + const uint128 c00 = a00 * b00; + const uint128 c64a = a00 * b64; + const uint128 c64b = a64 * b00; + const uint128 c128 = a64 * b64; + + const uint64_t carry = + static_cast<uint64_t>(((c00 >> 64) + static_cast<uint64_t>(c64a) + + static_cast<uint64_t>(c64b)) >> + 64); + + return {c128 + (c64a >> 64) + (c64b >> 64) + carry, + c00 + (c64a << 64) + (c64b << 64)}; +} + + template <> -struct wide_multiply<uint64_t> { - using input_type = uint64_t; - using result_type = absl::uint128; +struct wide_multiply<uint128> { + using input_type = uint128; + using result_type = U256; - static result_type multiply(uint64_t a, uint64_t b) { - return MultiplyU64ToU128(a, b); + static result_type multiply(input_type a, input_type b) { + return MultiplyU128ToU256(a, b); } - static uint64_t hi(result_type r) { return absl::Uint128High64(r); } - static uint64_t lo(result_type r) { return absl::Uint128Low64(r); } + static input_type hi(result_type r) { return r.hi; } + static input_type lo(result_type r) { return r.lo; } }; -#endif } // namespace random_internal ABSL_NAMESPACE_END |