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