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/numeric/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 // wide_multiply<T> multiplies two N-bit values to a 2N-bit result.
38 template <typename UIntType>
39 struct wide_multiply {
40 static constexpr size_t kN = std::numeric_limits<UIntType>::digits;
41 using input_type = UIntType;
42 using result_type = typename random_internal::unsigned_bits<kN * 2>::type;
43
multiplywide_multiply44 static result_type multiply(input_type a, input_type b) {
45 return static_cast<result_type>(a) * b;
46 }
47
hiwide_multiply48 static input_type hi(result_type r) {
49 return static_cast<input_type>(r >> kN);
50 }
lowide_multiply51 static input_type lo(result_type r) { return static_cast<input_type>(r); }
52
53 static_assert(std::is_unsigned<UIntType>::value,
54 "Class-template wide_multiply<> argument must be unsigned.");
55 };
56
57 // MultiplyU128ToU256 multiplies two 128-bit values to a 256-bit value.
MultiplyU128ToU256(uint128 a,uint128 b)58 inline U256 MultiplyU128ToU256(uint128 a, uint128 b) {
59 const uint128 a00 = static_cast<uint64_t>(a);
60 const uint128 a64 = a >> 64;
61 const uint128 b00 = static_cast<uint64_t>(b);
62 const uint128 b64 = b >> 64;
63
64 const uint128 c00 = a00 * b00;
65 const uint128 c64a = a00 * b64;
66 const uint128 c64b = a64 * b00;
67 const uint128 c128 = a64 * b64;
68
69 const uint64_t carry =
70 static_cast<uint64_t>(((c00 >> 64) + static_cast<uint64_t>(c64a) +
71 static_cast<uint64_t>(c64b)) >>
72 64);
73
74 return {c128 + (c64a >> 64) + (c64b >> 64) + carry,
75 c00 + (c64a << 64) + (c64b << 64)};
76 }
77
78
79 template <>
80 struct wide_multiply<uint128> {
81 using input_type = uint128;
82 using result_type = U256;
83
84 static result_type multiply(input_type a, input_type b) {
85 return MultiplyU128ToU256(a, b);
86 }
87
88 static input_type hi(result_type r) { return r.hi; }
89 static input_type lo(result_type r) { return r.lo; }
90 };
91
92 } // namespace random_internal
93 ABSL_NAMESPACE_END
94 } // namespace absl
95
96 #endif // ABSL_RANDOM_INTERNAL_WIDE_MULTIPLY_H_
97