1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_RANDOM_INTERNAL_WIDE_MULTIPLY_H_
16 #define ABSL_RANDOM_INTERNAL_WIDE_MULTIPLY_H_
17
18 #include <cstdint>
19 #include <limits>
20 #include <type_traits>
21
22 #if (defined(_WIN32) || defined(_WIN64)) && defined(_M_IA64)
23 #include <intrin.h> // NOLINT(build/include_order)
24 #pragma intrinsic(_umul128)
25 #define ABSL_INTERNAL_USE_UMUL128 1
26 #endif
27
28 #include "absl/base/config.h"
29 #include "absl/base/internal/bits.h"
30 #include "absl/numeric/int128.h"
31 #include "absl/random/internal/traits.h"
32
33 namespace absl {
34 ABSL_NAMESPACE_BEGIN
35 namespace random_internal {
36
37 // Helper object to multiply two 64-bit values to a 128-bit value.
38 // MultiplyU64ToU128 multiplies two 64-bit values to a 128-bit value.
39 // If an intrinsic is available, it is used, otherwise use native 32-bit
40 // multiplies to construct the result.
MultiplyU64ToU128(uint64_t a,uint64_t b)41 inline absl::uint128 MultiplyU64ToU128(uint64_t a, uint64_t b) {
42 #if defined(ABSL_HAVE_INTRINSIC_INT128)
43 return absl::uint128(static_cast<__uint128_t>(a) * b);
44 #elif defined(ABSL_INTERNAL_USE_UMUL128)
45 // uint64_t * uint64_t => uint128 multiply using imul intrinsic on MSVC.
46 uint64_t high = 0;
47 const uint64_t low = _umul128(a, b, &high);
48 return absl::MakeUint128(high, low);
49 #else
50 // uint128(a) * uint128(b) in emulated mode computes a full 128-bit x 128-bit
51 // multiply. However there are many cases where that is not necessary, and it
52 // is only necessary to support a 64-bit x 64-bit = 128-bit multiply. This is
53 // for those cases.
54 const uint64_t a00 = static_cast<uint32_t>(a);
55 const uint64_t a32 = a >> 32;
56 const uint64_t b00 = static_cast<uint32_t>(b);
57 const uint64_t b32 = b >> 32;
58
59 const uint64_t c00 = a00 * b00;
60 const uint64_t c32a = a00 * b32;
61 const uint64_t c32b = a32 * b00;
62 const uint64_t c64 = a32 * b32;
63
64 const uint32_t carry =
65 static_cast<uint32_t>(((c00 >> 32) + static_cast<uint32_t>(c32a) +
66 static_cast<uint32_t>(c32b)) >>
67 32);
68
69 return absl::MakeUint128(c64 + (c32a >> 32) + (c32b >> 32) + carry,
70 c00 + (c32a << 32) + (c32b << 32));
71 #endif
72 }
73
74 // wide_multiply<T> multiplies two N-bit values to a 2N-bit result.
75 template <typename UIntType>
76 struct wide_multiply {
77 static constexpr size_t kN = std::numeric_limits<UIntType>::digits;
78 using input_type = UIntType;
79 using result_type = typename random_internal::unsigned_bits<kN * 2>::type;
80
multiplywide_multiply81 static result_type multiply(input_type a, input_type b) {
82 return static_cast<result_type>(a) * b;
83 }
84
hiwide_multiply85 static input_type hi(result_type r) { return r >> kN; }
lowide_multiply86 static input_type lo(result_type r) { return r; }
87
88 static_assert(std::is_unsigned<UIntType>::value,
89 "Class-template wide_multiply<> argument must be unsigned.");
90 };
91
92 #ifndef ABSL_HAVE_INTRINSIC_INT128
93 template <>
94 struct wide_multiply<uint64_t> {
95 using input_type = uint64_t;
96 using result_type = absl::uint128;
97
98 static result_type multiply(uint64_t a, uint64_t b) {
99 return MultiplyU64ToU128(a, b);
100 }
101
102 static uint64_t hi(result_type r) { return absl::Uint128High64(r); }
103 static uint64_t lo(result_type r) { return absl::Uint128Low64(r); }
104 };
105 #endif
106
107 } // namespace random_internal
108 ABSL_NAMESPACE_END
109 } // namespace absl
110
111 #endif // ABSL_RANDOM_INTERNAL_WIDE_MULTIPLY_H_
112