| // A relatively minimal unsigned 128-bit integer class type, used by the |
| // floating-point std::to_chars implementation on targets that lack __int128. |
| |
| // Copyright (C) 2021 Free Software Foundation, Inc. |
| // |
| // This file is part of the GNU ISO C++ Library. This library is free |
| // software; you can redistribute it and/or modify it under the |
| // terms of the GNU General Public License as published by the |
| // Free Software Foundation; either version 3, or (at your option) |
| // any later version. |
| |
| // This library is distributed in the hope that it will be useful, |
| // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| // GNU General Public License for more details. |
| |
| // Under Section 7 of GPL version 3, you are granted additional |
| // permissions described in the GCC Runtime Library Exception, version |
| // 3.1, as published by the Free Software Foundation. |
| |
| // You should have received a copy of the GNU General Public License and |
| // a copy of the GCC Runtime Library Exception along with this program; |
| // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
| // <http://www.gnu.org/licenses/>. |
| |
| struct uint128_t |
| { |
| #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ |
| uint64_t lo, hi; |
| #else |
| uint64_t hi, lo; |
| #endif |
| |
| uint128_t() = default; |
| |
| constexpr |
| uint128_t(uint64_t lo, uint64_t hi = 0) |
| #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ |
| : lo(lo), hi(hi) |
| #else |
| : hi(hi), lo(lo) |
| #endif |
| { } |
| |
| constexpr explicit |
| operator bool() const |
| { return *this != 0; } |
| |
| template<typename T, typename = std::enable_if_t<std::is_integral_v<T>>> |
| constexpr explicit |
| operator T() const |
| { |
| static_assert(sizeof(T) <= sizeof(uint64_t)); |
| return static_cast<T>(lo); |
| } |
| |
| friend constexpr uint128_t |
| operator&(uint128_t x, const uint128_t y) |
| { |
| x.lo &= y.lo; |
| x.hi &= y.hi; |
| return x; |
| } |
| |
| friend constexpr uint128_t |
| operator|(uint128_t x, const uint128_t y) |
| { |
| x.lo |= y.lo; |
| x.hi |= y.hi; |
| return x; |
| } |
| |
| friend constexpr uint128_t |
| operator<<(uint128_t x, const uint128_t y) |
| { |
| __glibcxx_assert(y < 128); |
| // TODO: Convince GCC to use shldq on x86 here. |
| if (y.lo >= 64) |
| { |
| x.hi = x.lo << (y.lo - 64); |
| x.lo = 0; |
| } |
| else if (y.lo != 0) |
| { |
| x.hi <<= y.lo; |
| x.hi |= x.lo >> (64 - y.lo); |
| x.lo <<= y.lo; |
| } |
| return x; |
| } |
| |
| friend constexpr uint128_t |
| operator>>(uint128_t x, const uint128_t y) |
| { |
| __glibcxx_assert(y < 128); |
| // TODO: Convince GCC to use shrdq on x86 here. |
| if (y.lo >= 64) |
| { |
| x.lo = x.hi >> (y.lo - 64); |
| x.hi = 0; |
| } |
| else if (y.lo != 0) |
| { |
| x.lo >>= y.lo; |
| x.lo |= x.hi << (64 - y.lo); |
| x.hi >>= y.lo; |
| } |
| return x; |
| } |
| |
| constexpr uint128_t |
| operator~() const |
| { return {~lo, ~hi}; } |
| |
| constexpr uint128_t |
| operator-() const |
| { return operator~() + 1; } |
| |
| friend constexpr uint128_t |
| operator+(uint128_t x, const uint128_t y) |
| { |
| x.hi += __builtin_add_overflow(x.lo, y.lo, &x.lo); |
| x.hi += y.hi; |
| return x; |
| } |
| |
| friend constexpr uint128_t |
| operator-(uint128_t x, const uint128_t y) |
| { |
| x.hi -= __builtin_sub_overflow(x.lo, y.lo, &x.lo); |
| x.hi -= y.hi; |
| return x; |
| } |
| |
| static constexpr uint128_t |
| umul64_64_128(const uint64_t x, const uint64_t y) |
| { |
| const uint64_t xl = x & 0xffffffff; |
| const uint64_t xh = x >> 32; |
| const uint64_t yl = y & 0xffffffff; |
| const uint64_t yh = y >> 32; |
| const uint64_t ll = xl * yl; |
| const uint64_t lh = xl * yh; |
| const uint64_t hl = xh * yl; |
| const uint64_t hh = xh * yh; |
| const uint64_t m = (ll >> 32) + lh + (hl & 0xffffffff); |
| const uint64_t l = (ll & 0xffffffff ) | (m << 32); |
| const uint64_t h = (m >> 32) + (hl >> 32) + hh; |
| return {l, h}; |
| } |
| |
| friend constexpr uint128_t |
| operator*(const uint128_t x, const uint128_t y) |
| { |
| uint128_t z = umul64_64_128(x.lo, y.lo); |
| z.hi += x.lo * y.hi + x.hi * y.lo; |
| return z; |
| } |
| |
| friend constexpr uint128_t |
| operator/(const uint128_t x, const uint128_t y) |
| { |
| // Ryu performs 128-bit division only by 5 and 10, so that's what we |
| // implement. The strategy here is to relate division of x with that of |
| // x.hi and x.lo separately. |
| __glibcxx_assert(y == 5 || y == 10); |
| // The following implements division by 5 and 10. In either case, we |
| // first compute division by 5: |
| // x/5 = (x.hi*2^64 + x.lo)/5 |
| // = (x.hi*(2^64-1) + x.hi + x.lo)/5 |
| // = x.hi*((2^64-1)/5) + (x.hi + x.lo)/5 since CST=(2^64-1)/5 is exact |
| // = x.hi*CST + x.hi/5 + x.lo/5 + ((x.lo%5) + (x.hi%5) >= 5) |
| // We go a step further and replace the last adjustment term with a |
| // lookup table, which we encode as a binary literal. This seems to |
| // yield smaller code on x86 at least. |
| constexpr auto cst = ~uint64_t(0) / 5; |
| uint128_t q = uint128_t{x.hi}*cst + uint128_t{x.hi/5 + x.lo/5}; |
| constexpr auto lookup = 0b111100000u; |
| q += (lookup >> ((x.hi % 5) + (x.lo % 5))) & 1; |
| if (y == 10) |
| q >>= 1; |
| return q; |
| } |
| |
| friend constexpr uint128_t |
| operator%(const uint128_t x, const uint128_t y) |
| { |
| // Ryu performs 128-bit modulus only by 2, 5 and 10, so that's what we |
| // implement. The strategy here is to relate modulus of x with that of |
| // x.hi and x.lo separately. |
| if (y == 2) |
| return x & 1; |
| __glibcxx_assert(y == 5 || y == 10); |
| // The following implements modulus by 5 and 10. In either case, |
| // we first compute modulus by 5: |
| // x (mod 5) = x.hi*2^64 + x.lo (mod 5) |
| // = x.hi + x.lo (mod 5) since 2^64 ≡ 1 (mod 5) |
| // So the straightforward implementation would be |
| // ((x.hi % 5) + (x.lo % 5)) % 5 |
| // But we go a step further and replace the outermost % with a |
| // lookup table: |
| // = {0,1,2,3,4,0,1,2,3}[(x.hi % 5) + (x.lo % 5)] (mod 5) |
| // which we encode as an octal literal. |
| constexpr auto lookup = 0321043210u; |
| auto r = (lookup >> 3*((x.hi % 5) + (x.lo % 5))) & 7; |
| if (y == 10) |
| // x % 10 = (x % 5) if x / 5 is even |
| // (x % 5) + 5 if x / 5 is odd |
| // The compiler should be able to CSE the below computation of x/5 and |
| // the above modulus operations with a nearby inlined computation of x/10. |
| r += 5 * ((x/5).lo & 1); |
| return r; |
| } |
| |
| friend constexpr bool |
| operator==(const uint128_t x, const uint128_t y) |
| { return x.hi == y.hi && x.lo == y.lo; } |
| |
| friend constexpr bool |
| operator<(const uint128_t x, const uint128_t y) |
| { return x.hi < y.hi || (x.hi == y.hi && x.lo < y.lo); } |
| |
| friend constexpr auto |
| __bit_width(const uint128_t x) |
| { |
| if (auto w = std::__bit_width(x.hi)) |
| return w + 64; |
| else |
| return std::__bit_width(x.lo); |
| } |
| |
| friend constexpr auto |
| __countr_zero(const uint128_t x) |
| { |
| auto c = std::__countr_zero(x.lo); |
| if (c == 64) |
| return 64 + std::__countr_zero(x.hi); |
| else |
| return c; |
| } |
| |
| constexpr uint128_t& |
| operator--() |
| { return *this -= 1; } |
| |
| constexpr uint128_t& |
| operator++() |
| { return *this += 1; } |
| |
| constexpr uint128_t& |
| operator+=(const uint128_t y) |
| { return *this = *this + y; } |
| |
| constexpr uint128_t& |
| operator-=(const uint128_t y) |
| { return *this = *this - y; } |
| |
| constexpr uint128_t& |
| operator*=(const uint128_t y) |
| { return *this = *this * y; } |
| |
| constexpr uint128_t& |
| operator<<=(const uint128_t y) |
| { return *this = *this << y; } |
| |
| constexpr uint128_t& |
| operator>>=(const uint128_t y) |
| { return *this = *this >> y; } |
| |
| constexpr uint128_t& |
| operator|=(const uint128_t y) |
| { return *this = *this | y; } |
| |
| constexpr uint128_t& |
| operator&=(const uint128_t y) |
| { return *this = *this & y; } |
| |
| constexpr uint128_t& |
| operator%=(const uint128_t y) |
| { return *this = *this % y; } |
| |
| constexpr uint128_t& |
| operator/=(const uint128_t y) |
| { return *this = *this / y; } |
| |
| friend constexpr bool |
| operator!=(const uint128_t x, const uint128_t y) |
| { return !(x == y); } |
| |
| friend constexpr bool |
| operator>(const uint128_t x, const uint128_t y) |
| { return y < x; } |
| |
| friend constexpr bool |
| operator>=(const uint128_t x, const uint128_t y) |
| { return !(x < y); } |
| }; |