Warning: This file is not a C or C++ file. It does not have highlighting.
1 | //===-- include/flang/Common/uint128.h --------------------------*- C++ -*-===// |
---|---|
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | // Portable 128-bit integer arithmetic for use in impoverished C++ |
10 | // implementations lacking __uint128_t & __int128_t. |
11 | |
12 | #ifndef FORTRAN_COMMON_UINT128_H_ |
13 | #define FORTRAN_COMMON_UINT128_H_ |
14 | |
15 | // Define AVOID_NATIVE_UINT128_T to force the use of UnsignedInt128 below |
16 | // instead of the C++ compiler's native 128-bit unsigned integer type, if |
17 | // it has one. |
18 | #ifndef AVOID_NATIVE_UINT128_T |
19 | #define AVOID_NATIVE_UINT128_T 0 |
20 | #endif |
21 | |
22 | #include "leading-zero-bit-count.h" |
23 | #include "flang/Common/api-attrs.h" |
24 | #include <cstdint> |
25 | #include <type_traits> |
26 | |
27 | namespace Fortran::common { |
28 | |
29 | template <bool IS_SIGNED = false> class Int128 { |
30 | public: |
31 | constexpr Int128() {} |
32 | // This means of definition provides some portability for |
33 | // "size_t" operands. |
34 | constexpr Int128(unsigned n) : low_{n} {} |
35 | constexpr Int128(unsigned long n) : low_{n} {} |
36 | constexpr Int128(unsigned long long n) : low_{n} {} |
37 | constexpr Int128(int n) { |
38 | low_ = static_cast<std::uint64_t>(n); |
39 | high_ = -static_cast<std::uint64_t>(n < 0); |
40 | } |
41 | constexpr Int128(long n) { |
42 | low_ = static_cast<std::uint64_t>(n); |
43 | high_ = -static_cast<std::uint64_t>(n < 0); |
44 | } |
45 | constexpr Int128(long long n) { |
46 | low_ = static_cast<std::uint64_t>(n); |
47 | high_ = -static_cast<std::uint64_t>(n < 0); |
48 | } |
49 | constexpr Int128(const Int128 &) = default; |
50 | constexpr Int128(Int128 &&) = default; |
51 | constexpr Int128 &operator=(const Int128 &) = default; |
52 | constexpr Int128 &operator=(Int128 &&) = default; |
53 | |
54 | explicit constexpr Int128(const Int128<!IS_SIGNED> &n) |
55 | : low_{n.low()}, high_{n.high()} {} |
56 | explicit constexpr Int128(Int128<!IS_SIGNED> &&n) |
57 | : low_{n.low()}, high_{n.high()} {} |
58 | |
59 | constexpr Int128 operator+() const { return *this; } |
60 | constexpr Int128 operator~() const { return {~high_, ~low_}; } |
61 | constexpr Int128 operator-() const { return ~*this + 1; } |
62 | constexpr bool operator!() const { return !low_ && !high_; } |
63 | constexpr explicit operator bool() const { return low_ || high_; } |
64 | constexpr explicit operator std::uint64_t() const { return low_; } |
65 | constexpr explicit operator std::int64_t() const { return low_; } |
66 | constexpr explicit operator int() const { return static_cast<int>(low_); } |
67 | |
68 | constexpr std::uint64_t high() const { return high_; } |
69 | constexpr std::uint64_t low() const { return low_; } |
70 | |
71 | constexpr Int128 operator++(/*prefix*/) { |
72 | *this += 1; |
73 | return *this; |
74 | } |
75 | constexpr Int128 operator++(int /*postfix*/) { |
76 | Int128 result{*this}; |
77 | *this += 1; |
78 | return result; |
79 | } |
80 | constexpr Int128 operator--(/*prefix*/) { |
81 | *this -= 1; |
82 | return *this; |
83 | } |
84 | constexpr Int128 operator--(int /*postfix*/) { |
85 | Int128 result{*this}; |
86 | *this -= 1; |
87 | return result; |
88 | } |
89 | |
90 | constexpr Int128 operator&(Int128 that) const { |
91 | return {high_ & that.high_, low_ & that.low_}; |
92 | } |
93 | constexpr Int128 operator|(Int128 that) const { |
94 | return {high_ | that.high_, low_ | that.low_}; |
95 | } |
96 | constexpr Int128 operator^(Int128 that) const { |
97 | return {high_ ^ that.high_, low_ ^ that.low_}; |
98 | } |
99 | |
100 | constexpr Int128 operator<<(Int128 that) const { |
101 | if (that >= 128) { |
102 | return {}; |
103 | } else if (that == 0) { |
104 | return *this; |
105 | } else { |
106 | std::uint64_t n{that.low_}; |
107 | if (n >= 64) { |
108 | return {low_ << (n - 64), 0}; |
109 | } else { |
110 | return {(high_ << n) | (low_ >> (64 - n)), low_ << n}; |
111 | } |
112 | } |
113 | } |
114 | constexpr Int128 operator>>(Int128 that) const { |
115 | if (that >= 128) { |
116 | return {}; |
117 | } else if (that == 0) { |
118 | return *this; |
119 | } else { |
120 | std::uint64_t n{that.low_}; |
121 | if (n >= 64) { |
122 | return {0, high_ >> (n - 64)}; |
123 | } else { |
124 | return {high_ >> n, (high_ << (64 - n)) | (low_ >> n)}; |
125 | } |
126 | } |
127 | } |
128 | |
129 | constexpr Int128 operator+(Int128 that) const { |
130 | std::uint64_t lower{(low_ & ~topBit) + (that.low_ & ~topBit)}; |
131 | bool carry{((lower >> 63) + (low_ >> 63) + (that.low_ >> 63)) > 1}; |
132 | return {high_ + that.high_ + carry, low_ + that.low_}; |
133 | } |
134 | constexpr Int128 operator-(Int128 that) const { return *this + -that; } |
135 | |
136 | constexpr Int128 operator*(Int128 that) const { |
137 | std::uint64_t mask32{0xffffffff}; |
138 | if (high_ == 0 && that.high_ == 0) { |
139 | std::uint64_t x0{low_ & mask32}, x1{low_ >> 32}; |
140 | std::uint64_t y0{that.low_ & mask32}, y1{that.low_ >> 32}; |
141 | Int128 x0y0{x0 * y0}, x0y1{x0 * y1}; |
142 | Int128 x1y0{x1 * y0}, x1y1{x1 * y1}; |
143 | return x0y0 + ((x0y1 + x1y0) << 32) + (x1y1 << 64); |
144 | } else { |
145 | std::uint64_t x0{low_ & mask32}, x1{low_ >> 32}, x2{high_ & mask32}, |
146 | x3{high_ >> 32}; |
147 | std::uint64_t y0{that.low_ & mask32}, y1{that.low_ >> 32}, |
148 | y2{that.high_ & mask32}, y3{that.high_ >> 32}; |
149 | Int128 x0y0{x0 * y0}, x0y1{x0 * y1}, x0y2{x0 * y2}, x0y3{x0 * y3}; |
150 | Int128 x1y0{x1 * y0}, x1y1{x1 * y1}, x1y2{x1 * y2}; |
151 | Int128 x2y0{x2 * y0}, x2y1{x2 * y1}; |
152 | Int128 x3y0{x3 * y0}; |
153 | return x0y0 + ((x0y1 + x1y0) << 32) + ((x0y2 + x1y1 + x2y0) << 64) + |
154 | ((x0y3 + x1y2 + x2y1 + x3y0) << 96); |
155 | } |
156 | } |
157 | |
158 | constexpr Int128 operator/(Int128 that) const { |
159 | int j{LeadingZeroes()}; |
160 | Int128 bits{*this}; |
161 | bits <<= j; |
162 | Int128 numerator{}; |
163 | Int128 quotient{}; |
164 | for (; j < 128; ++j) { |
165 | numerator <<= 1; |
166 | if (bits.high_ & topBit) { |
167 | numerator.low_ |= 1; |
168 | } |
169 | bits <<= 1; |
170 | quotient <<= 1; |
171 | if (numerator >= that) { |
172 | ++quotient; |
173 | numerator -= that; |
174 | } |
175 | } |
176 | return quotient; |
177 | } |
178 | |
179 | constexpr Int128 operator%(Int128 that) const { |
180 | int j{LeadingZeroes()}; |
181 | Int128 bits{*this}; |
182 | bits <<= j; |
183 | Int128 remainder{}; |
184 | for (; j < 128; ++j) { |
185 | remainder <<= 1; |
186 | if (bits.high_ & topBit) { |
187 | remainder.low_ |= 1; |
188 | } |
189 | bits <<= 1; |
190 | if (remainder >= that) { |
191 | remainder -= that; |
192 | } |
193 | } |
194 | return remainder; |
195 | } |
196 | |
197 | constexpr bool operator<(Int128 that) const { |
198 | if (IS_SIGNED && (high_ ^ that.high_) & topBit) { |
199 | return (high_ & topBit) != 0; |
200 | } |
201 | return high_ < that.high_ || (high_ == that.high_ && low_ < that.low_); |
202 | } |
203 | constexpr bool operator<=(Int128 that) const { return !(*this > that); } |
204 | constexpr bool operator==(Int128 that) const { |
205 | return low_ == that.low_ && high_ == that.high_; |
206 | } |
207 | constexpr bool operator!=(Int128 that) const { return !(*this == that); } |
208 | constexpr bool operator>=(Int128 that) const { return that <= *this; } |
209 | constexpr bool operator>(Int128 that) const { return that < *this; } |
210 | |
211 | constexpr Int128 &operator&=(const Int128 &that) { |
212 | *this = *this & that; |
213 | return *this; |
214 | } |
215 | constexpr Int128 &operator|=(const Int128 &that) { |
216 | *this = *this | that; |
217 | return *this; |
218 | } |
219 | constexpr Int128 &operator^=(const Int128 &that) { |
220 | *this = *this ^ that; |
221 | return *this; |
222 | } |
223 | constexpr Int128 &operator<<=(const Int128 &that) { |
224 | *this = *this << that; |
225 | return *this; |
226 | } |
227 | constexpr Int128 &operator>>=(const Int128 &that) { |
228 | *this = *this >> that; |
229 | return *this; |
230 | } |
231 | constexpr Int128 &operator+=(const Int128 &that) { |
232 | *this = *this + that; |
233 | return *this; |
234 | } |
235 | constexpr Int128 &operator-=(const Int128 &that) { |
236 | *this = *this - that; |
237 | return *this; |
238 | } |
239 | constexpr Int128 &operator*=(const Int128 &that) { |
240 | *this = *this * that; |
241 | return *this; |
242 | } |
243 | constexpr Int128 &operator/=(const Int128 &that) { |
244 | *this = *this / that; |
245 | return *this; |
246 | } |
247 | constexpr Int128 &operator%=(const Int128 &that) { |
248 | *this = *this % that; |
249 | return *this; |
250 | } |
251 | |
252 | private: |
253 | constexpr Int128(std::uint64_t hi, std::uint64_t lo) { |
254 | low_ = lo; |
255 | high_ = hi; |
256 | } |
257 | constexpr int LeadingZeroes() const { |
258 | if (high_ == 0) { |
259 | return 64 + LeadingZeroBitCount(low_); |
260 | } else { |
261 | return LeadingZeroBitCount(high_); |
262 | } |
263 | } |
264 | RT_VAR_GROUP_BEGIN |
265 | static constexpr std::uint64_t topBit{std::uint64_t{1} << 63}; |
266 | RT_VAR_GROUP_END |
267 | #if FLANG_LITTLE_ENDIAN |
268 | std::uint64_t low_{0}, high_{0}; |
269 | #elif FLANG_BIG_ENDIAN |
270 | std::uint64_t high_{0}, low_{0}; |
271 | #else |
272 | #error host endianness is not known |
273 | #endif |
274 | }; |
275 | |
276 | using UnsignedInt128 = Int128<false>; |
277 | using SignedInt128 = Int128<true>; |
278 | |
279 | #if !AVOID_NATIVE_UINT128_T && (defined __GNUC__ || defined __clang__) && \ |
280 | defined __SIZEOF_INT128__ |
281 | using uint128_t = __uint128_t; |
282 | using int128_t = __int128_t; |
283 | #else |
284 | using uint128_t = UnsignedInt128; |
285 | using int128_t = SignedInt128; |
286 | #endif |
287 | |
288 | template <int BITS> struct HostUnsignedIntTypeHelper { |
289 | using type = std::conditional_t<(BITS <= 8), std::uint8_t, |
290 | std::conditional_t<(BITS <= 16), std::uint16_t, |
291 | std::conditional_t<(BITS <= 32), std::uint32_t, |
292 | std::conditional_t<(BITS <= 64), std::uint64_t, uint128_t>>>>; |
293 | }; |
294 | template <int BITS> struct HostSignedIntTypeHelper { |
295 | using type = std::conditional_t<(BITS <= 8), std::int8_t, |
296 | std::conditional_t<(BITS <= 16), std::int16_t, |
297 | std::conditional_t<(BITS <= 32), std::int32_t, |
298 | std::conditional_t<(BITS <= 64), std::int64_t, int128_t>>>>; |
299 | }; |
300 | template <int BITS> |
301 | using HostUnsignedIntType = typename HostUnsignedIntTypeHelper<BITS>::type; |
302 | template <int BITS> |
303 | using HostSignedIntType = typename HostSignedIntTypeHelper<BITS>::type; |
304 | |
305 | } // namespace Fortran::common |
306 | #endif |
307 |
Warning: This file is not a C or C++ file. It does not have highlighting.