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 unsigned integer arithmetic for use in impoverished
10 // C++ implementations lacking __uint128_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 <cstdint>
24 #include <type_traits>
25 
26 namespace Fortran::common {
27 
28 class UnsignedInt128 {
29 public:
UnsignedInt128()30   constexpr UnsignedInt128() {}
31   // This means of definition provides some portability for
32   // "size_t" operands.
UnsignedInt128(unsigned n)33   constexpr UnsignedInt128(unsigned n) : low_{n} {}
UnsignedInt128(unsigned long n)34   constexpr UnsignedInt128(unsigned long n) : low_{n} {}
UnsignedInt128(unsigned long long n)35   constexpr UnsignedInt128(unsigned long long n) : low_{n} {}
UnsignedInt128(int n)36   constexpr UnsignedInt128(int n)
37       : low_{static_cast<std::uint64_t>(n)}, high_{-static_cast<std::uint64_t>(
38                                                  n < 0)} {}
UnsignedInt128(long n)39   constexpr UnsignedInt128(long n)
40       : low_{static_cast<std::uint64_t>(n)}, high_{-static_cast<std::uint64_t>(
41                                                  n < 0)} {}
UnsignedInt128(long long n)42   constexpr UnsignedInt128(long long n)
43       : low_{static_cast<std::uint64_t>(n)}, high_{-static_cast<std::uint64_t>(
44                                                  n < 0)} {}
45   constexpr UnsignedInt128(const UnsignedInt128 &) = default;
46   constexpr UnsignedInt128(UnsignedInt128 &&) = default;
47   constexpr UnsignedInt128 &operator=(const UnsignedInt128 &) = default;
48   constexpr UnsignedInt128 &operator=(UnsignedInt128 &&) = default;
49 
50   constexpr UnsignedInt128 operator+() const { return *this; }
51   constexpr UnsignedInt128 operator~() const { return {~high_, ~low_}; }
52   constexpr UnsignedInt128 operator-() const { return ~*this + 1; }
53   constexpr bool operator!() const { return !low_ && !high_; }
54   constexpr explicit operator bool() const { return low_ || high_; }
uint64_t()55   constexpr explicit operator std::uint64_t() const { return low_; }
int64_t()56   constexpr explicit operator std::int64_t() const { return low_; }
57   constexpr explicit operator int() const { return static_cast<int>(low_); }
58 
high()59   constexpr std::uint64_t high() const { return high_; }
low()60   constexpr std::uint64_t low() const { return low_; }
61 
62   constexpr UnsignedInt128 operator++(/*prefix*/) {
63     *this += 1;
64     return *this;
65   }
66   constexpr UnsignedInt128 operator++(int /*postfix*/) {
67     UnsignedInt128 result{*this};
68     *this += 1;
69     return result;
70   }
71   constexpr UnsignedInt128 operator--(/*prefix*/) {
72     *this -= 1;
73     return *this;
74   }
75   constexpr UnsignedInt128 operator--(int /*postfix*/) {
76     UnsignedInt128 result{*this};
77     *this -= 1;
78     return result;
79   }
80 
81   constexpr UnsignedInt128 operator&(UnsignedInt128 that) const {
82     return {high_ & that.high_, low_ & that.low_};
83   }
84   constexpr UnsignedInt128 operator|(UnsignedInt128 that) const {
85     return {high_ | that.high_, low_ | that.low_};
86   }
87   constexpr UnsignedInt128 operator^(UnsignedInt128 that) const {
88     return {high_ ^ that.high_, low_ ^ that.low_};
89   }
90 
91   constexpr UnsignedInt128 operator<<(UnsignedInt128 that) const {
92     if (that >= 128) {
93       return {};
94     } else if (that == 0) {
95       return *this;
96     } else {
97       std::uint64_t n{that.low_};
98       if (n >= 64) {
99         return {low_ << (n - 64), 0};
100       } else {
101         return {(high_ << n) | (low_ >> (64 - n)), low_ << n};
102       }
103     }
104   }
105   constexpr UnsignedInt128 operator>>(UnsignedInt128 that) const {
106     if (that >= 128) {
107       return {};
108     } else if (that == 0) {
109       return *this;
110     } else {
111       std::uint64_t n{that.low_};
112       if (n >= 64) {
113         return {0, high_ >> (n - 64)};
114       } else {
115         return {high_ >> n, (high_ << (64 - n)) | (low_ >> n)};
116       }
117     }
118   }
119 
120   constexpr UnsignedInt128 operator+(UnsignedInt128 that) const {
121     std::uint64_t lower{(low_ & ~topBit) + (that.low_ & ~topBit)};
122     bool carry{((lower >> 63) + (low_ >> 63) + (that.low_ >> 63)) > 1};
123     return {high_ + that.high_ + carry, low_ + that.low_};
124   }
125   constexpr UnsignedInt128 operator-(UnsignedInt128 that) const {
126     return *this + -that;
127   }
128 
129   constexpr UnsignedInt128 operator*(UnsignedInt128 that) const {
130     std::uint64_t mask32{0xffffffff};
131     if (high_ == 0 && that.high_ == 0) {
132       std::uint64_t x0{low_ & mask32}, x1{low_ >> 32};
133       std::uint64_t y0{that.low_ & mask32}, y1{that.low_ >> 32};
134       UnsignedInt128 x0y0{x0 * y0}, x0y1{x0 * y1};
135       UnsignedInt128 x1y0{x1 * y0}, x1y1{x1 * y1};
136       return x0y0 + ((x0y1 + x1y0) << 32) + (x1y1 << 64);
137     } else {
138       std::uint64_t x0{low_ & mask32}, x1{low_ >> 32}, x2{high_ & mask32},
139           x3{high_ >> 32};
140       std::uint64_t y0{that.low_ & mask32}, y1{that.low_ >> 32},
141           y2{that.high_ & mask32}, y3{that.high_ >> 32};
142       UnsignedInt128 x0y0{x0 * y0}, x0y1{x0 * y1}, x0y2{x0 * y2}, x0y3{x0 * y3};
143       UnsignedInt128 x1y0{x1 * y0}, x1y1{x1 * y1}, x1y2{x1 * y2};
144       UnsignedInt128 x2y0{x2 * y0}, x2y1{x2 * y1};
145       UnsignedInt128 x3y0{x3 * y0};
146       return x0y0 + ((x0y1 + x1y0) << 32) + ((x0y2 + x1y1 + x2y0) << 64) +
147           ((x0y3 + x1y2 + x2y1 + x3y0) << 96);
148     }
149   }
150 
151   constexpr UnsignedInt128 operator/(UnsignedInt128 that) const {
152     int j{LeadingZeroes()};
153     UnsignedInt128 bits{*this};
154     bits <<= j;
155     UnsignedInt128 numerator{};
156     UnsignedInt128 quotient{};
157     for (; j < 128; ++j) {
158       numerator <<= 1;
159       if (bits.high_ & topBit) {
160         numerator.low_ |= 1;
161       }
162       bits <<= 1;
163       quotient <<= 1;
164       if (numerator >= that) {
165         ++quotient;
166         numerator -= that;
167       }
168     }
169     return quotient;
170   }
171 
172   constexpr UnsignedInt128 operator%(UnsignedInt128 that) const {
173     int j{LeadingZeroes()};
174     UnsignedInt128 bits{*this};
175     bits <<= j;
176     UnsignedInt128 remainder{};
177     for (; j < 128; ++j) {
178       remainder <<= 1;
179       if (bits.high_ & topBit) {
180         remainder.low_ |= 1;
181       }
182       bits <<= 1;
183       if (remainder >= that) {
184         remainder -= that;
185       }
186     }
187     return remainder;
188   }
189 
190   constexpr bool operator<(UnsignedInt128 that) const {
191     return high_ < that.high_ || (high_ == that.high_ && low_ < that.low_);
192   }
193   constexpr bool operator<=(UnsignedInt128 that) const {
194     return !(*this > that);
195   }
196   constexpr bool operator==(UnsignedInt128 that) const {
197     return low_ == that.low_ && high_ == that.high_;
198   }
199   constexpr bool operator!=(UnsignedInt128 that) const {
200     return !(*this == that);
201   }
202   constexpr bool operator>=(UnsignedInt128 that) const { return that <= *this; }
203   constexpr bool operator>(UnsignedInt128 that) const { return that < *this; }
204 
205   constexpr UnsignedInt128 &operator&=(const UnsignedInt128 &that) {
206     *this = *this & that;
207     return *this;
208   }
209   constexpr UnsignedInt128 &operator|=(const UnsignedInt128 &that) {
210     *this = *this | that;
211     return *this;
212   }
213   constexpr UnsignedInt128 &operator^=(const UnsignedInt128 &that) {
214     *this = *this ^ that;
215     return *this;
216   }
217   constexpr UnsignedInt128 &operator<<=(const UnsignedInt128 &that) {
218     *this = *this << that;
219     return *this;
220   }
221   constexpr UnsignedInt128 &operator>>=(const UnsignedInt128 &that) {
222     *this = *this >> that;
223     return *this;
224   }
225   constexpr UnsignedInt128 &operator+=(const UnsignedInt128 &that) {
226     *this = *this + that;
227     return *this;
228   }
229   constexpr UnsignedInt128 &operator-=(const UnsignedInt128 &that) {
230     *this = *this - that;
231     return *this;
232   }
233   constexpr UnsignedInt128 &operator*=(const UnsignedInt128 &that) {
234     *this = *this * that;
235     return *this;
236   }
237   constexpr UnsignedInt128 &operator/=(const UnsignedInt128 &that) {
238     *this = *this / that;
239     return *this;
240   }
241   constexpr UnsignedInt128 &operator%=(const UnsignedInt128 &that) {
242     *this = *this % that;
243     return *this;
244   }
245 
246 private:
UnsignedInt128(std::uint64_t hi,std::uint64_t lo)247   constexpr UnsignedInt128(std::uint64_t hi, std::uint64_t lo)
248       : low_{lo}, high_{hi} {}
LeadingZeroes()249   constexpr int LeadingZeroes() const {
250     if (high_ == 0) {
251       return 64 + LeadingZeroBitCount(low_);
252     } else {
253       return LeadingZeroBitCount(high_);
254     }
255   }
256   static constexpr std::uint64_t topBit{std::uint64_t{1} << 63};
257   std::uint64_t low_{0}, high_{0};
258 };
259 
260 #if AVOID_NATIVE_UINT128_T
261 using uint128_t = UnsignedInt128;
262 #elif (defined __GNUC__ || defined __clang__) && defined __SIZEOF_INT128__
263 using uint128_t = __uint128_t;
264 #else
265 using uint128_t = UnsignedInt128;
266 #endif
267 
268 template <int BITS> struct HostUnsignedIntTypeHelper {
269   using type = std::conditional_t<(BITS <= 8), std::uint8_t,
270       std::conditional_t<(BITS <= 16), std::uint16_t,
271           std::conditional_t<(BITS <= 32), std::uint32_t,
272               std::conditional_t<(BITS <= 64), std::uint64_t, uint128_t>>>>;
273 };
274 template <int BITS>
275 using HostUnsignedIntType = typename HostUnsignedIntTypeHelper<BITS>::type;
276 
277 } // namespace Fortran::common
278 #endif
279