Source/WTF/wtf/Int128.h

// Taken from LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See Source/WTF/LICENSE-LLVM.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

// Portable 128-bit unsigned integer arithmetic for use in impoverished
// C++ implementations lacking __uint128_t.

// Based on:
// https://github.com/llvm/llvm-project/blob/d480f968/flang/include/flang/Common/uint128.h

#pragma once

// Define AVOID_NATIVE_INT128_T to force the use of Int128Impl below instead of
// the C++ compiler's native 128-bit unsigned integer type, if it has one.
#ifndef AVOID_NATIVE_INT128_T
#define AVOID_NATIVE_INT128_T 0
#endif

#include <cstdint>
#include <type_traits>
#include <wtf/LeadingZeroBitCount.h>

namespace WTF {

template <bool IS_SIGNED = false> class Int128Impl {
public:
    constexpr Int128Impl() { }
    // This means of definition provides some portability for
    // "size_t" operands.
    constexpr Int128Impl(unsigned n) : low_ {n} { }
    constexpr Int128Impl(unsigned long n) : low_ {n} { }
    constexpr Int128Impl(unsigned long long n) : low_ {n} { }
    constexpr Int128Impl(int n)
        : low_ {static_cast<std::uint64_t>(n)}
        , high_ {-static_cast<std::uint64_t>(n < 0)}
    { }
    constexpr Int128Impl(long n)
        : low_ {static_cast<std::uint64_t>(n)}
        , high_ {-static_cast<std::uint64_t>(n < 0)}
    { }
    constexpr Int128Impl(long long n)
        : low_ {static_cast<std::uint64_t>(n)}
        , high_ {-static_cast<std::uint64_t>(n < 0)}
    { }
    constexpr Int128Impl(const Int128Impl &) = default;
    constexpr Int128Impl(Int128Impl &&) = default;
    constexpr Int128Impl &operator=(const Int128Impl &) = default;
    constexpr Int128Impl &operator=(Int128Impl &&) = default;

    constexpr Int128Impl operator+() const { return *this; }
    constexpr Int128Impl operator~() const { return {~high_, ~low_}; }
    constexpr Int128Impl operator-() const { return ~*this + 1; }
    constexpr bool operator!() const { return !low_ && !high_; }
    constexpr explicit operator bool() const { return low_ || high_; }
    constexpr explicit operator std::uint64_t() const { return low_; }
    constexpr explicit operator std::int64_t() const { return low_; }
    constexpr explicit operator int() const { return static_cast<int>(low_); }

    constexpr std::uint64_t high() const { return high_; }
    constexpr std::uint64_t low() const { return low_; }

    constexpr Int128Impl operator++(/*prefix*/)
    {
        *this += 1;
        return *this;
    }
    constexpr Int128Impl operator++(int /*postfix*/)
    {
        Int128Impl result {*this};
        *this += 1;
        return result;
    }
    constexpr Int128Impl operator--(/*prefix*/)
    {
        *this -= 1;
        return *this;
    }
    constexpr Int128Impl operator--(int /*postfix*/)
    {
        Int128Impl result {*this};
        *this -= 1;
        return result;
    }

    constexpr Int128Impl operator&(Int128Impl that) const
    {
        return {high_ & that.high_, low_ & that.low_};
    }
    constexpr Int128Impl operator | (Int128Impl that) const
    {
        return {high_ | that.high_, low_ | that.low_};
    }
    constexpr Int128Impl operator^(Int128Impl that) const
    {
        return {high_ ^ that.high_, low_ ^ that.low_};
    }

    constexpr Int128Impl operator<<(Int128Impl that) const
    {
        if (that >= 128)
            return { };
        if (!that)
            return *this;
        std::uint64_t n {that.low_};
        if (n >= 64)
            return {low_ << (n - 64), 0};
        return {(high_ << n) | (low_ >> (64 - n)), low_ << n};
    }
    constexpr Int128Impl operator>>(Int128Impl that) const
    {
        if (that >= 128)
            return { };
        if (!that)
            return *this;
        std::uint64_t n {that.low_};
        if (n >= 64)
            return {0, high_ >> (n - 64)};
        return {high_ >> n, (high_ << (64 - n)) | (low_ >> n)};
    }

    constexpr Int128Impl operator+(Int128Impl that) const
    {
        std::uint64_t lower {(low_ & ~topBit) + (that.low_ & ~topBit)};
        bool carry {((lower >> 63) + (low_ >> 63) + (that.low_ >> 63)) > 1};
        return {high_ + that.high_ + carry, low_ + that.low_};
    }
    constexpr Int128Impl operator-(Int128Impl that) const { return *this + -that; }

    constexpr Int128Impl operator*(Int128Impl that) const
    {
        std::uint64_t mask32 {0xffffffff};
        if (!high_ && !that.high_) {
            std::uint64_t x0 {low_ & mask32}, x1 {low_ >> 32};
            std::uint64_t y0 {that.low_ & mask32}, y1 {that.low_ >> 32};
            Int128Impl x0y0 {x0 * y0}, x0y1 {x0 * y1};
            Int128Impl x1y0 {x1 * y0}, x1y1 {x1 * y1};
            return x0y0 + ((x0y1 + x1y0) << 32) + (x1y1 << 64);
        }

        std::uint64_t x0 {low_ & mask32}, x1 {low_ >> 32}, x2 {high_ & mask32},
            x3 {high_ >> 32};
        std::uint64_t y0 {that.low_ & mask32}, y1 {that.low_ >> 32},
            y2 {that.high_ & mask32}, y3 {that.high_ >> 32};
        Int128Impl x0y0 {x0 * y0}, x0y1 {x0 * y1}, x0y2 {x0 * y2}, x0y3 {x0 * y3};
        Int128Impl x1y0 {x1 * y0}, x1y1 {x1 * y1}, x1y2 {x1 * y2};
        Int128Impl x2y0 {x2 * y0}, x2y1 {x2 * y1};
        Int128Impl x3y0 {x3 * y0};
        return x0y0 + ((x0y1 + x1y0) << 32) + ((x0y2 + x1y1 + x2y0) << 64) +
            ((x0y3 + x1y2 + x2y1 + x3y0) << 96);
    }

    constexpr Int128Impl operator/(Int128Impl that) const
    {
        int j {leadingZeroes()};
        Int128Impl bits {*this};
        bits <<= j;
        Int128Impl numerator { };
        Int128Impl quotient { };
        for (; j < 128; ++j) {
            numerator <<= 1;
            if (bits.high_ & topBit)
                numerator.low_ |= 1;
            bits <<= 1;
            quotient <<= 1;
            if (numerator >= that) {
                ++quotient;
                numerator -= that;
            }
        }
        return quotient;
    }

    constexpr Int128Impl operator%(Int128Impl that) const
    {
        int j {leadingZeroes()};
        Int128Impl bits {*this};
        bits <<= j;
        Int128Impl remainder { };
        for (; j < 128; ++j) {
            remainder <<= 1;
            if (bits.high_ & topBit)
                remainder.low_ |= 1;
            bits <<= 1;
            if (remainder >= that)
                remainder -= that;
        }
        return remainder;
    }

    constexpr bool operator<(Int128Impl that) const
    {
        if (IS_SIGNED && (high_ ^ that.high_) & topBit)
            return !!(high_ & topBit);

        return high_ < that.high_ || (high_ == that.high_ && low_ < that.low_);
    }
    constexpr bool operator<=(Int128Impl that) const { return !(*this > that); }
    constexpr bool operator==(Int128Impl that) const
    {
        return low_ == that.low_ && high_ == that.high_;
    }
    constexpr bool operator!=(Int128Impl that) const { return !(*this == that); }
    constexpr bool operator>=(Int128Impl that) const { return that <= *this; }
    constexpr bool operator>(Int128Impl that) const { return that < *this; }

    constexpr Int128Impl &operator&=(const Int128Impl &that)
    {
        *this = *this & that;
        return *this;
    }
    constexpr Int128Impl &operator|=(const Int128Impl &that)
    {
        *this = *this | that;
        return *this;
    }
    constexpr Int128Impl &operator^=(const Int128Impl &that)
    {
        *this = *this ^ that;
        return *this;
    }
    constexpr Int128Impl &operator<<=(const Int128Impl &that)
    {
        *this = *this << that;
        return *this;
    }
    constexpr Int128Impl &operator>>=(const Int128Impl &that)
    {
        *this = *this >> that;
        return *this;
    }
    constexpr Int128Impl &operator+=(const Int128Impl &that)
    {
        *this = *this + that;
        return *this;
    }
    constexpr Int128Impl &operator-=(const Int128Impl &that)
    {
        *this = *this - that;
        return *this;
    }
    constexpr Int128Impl &operator*=(const Int128Impl &that)
    {
        *this = *this * that;
        return *this;
    }
    constexpr Int128Impl &operator/=(const Int128Impl &that)
    {
        *this = *this / that;
        return *this;
    }
    constexpr Int128Impl &operator%=(const Int128Impl &that)
    {
        *this = *this % that;
        return *this;
    }

private:
    constexpr Int128Impl(std::uint64_t hi, std::uint64_t lo) : low_ {lo}, high_ {hi} { }
    constexpr int leadingZeroes() const
    {
        if (!high_)
            return 64 + leadingZeroBitCount(low_);
        return leadingZeroBitCount(high_);
    }
    static constexpr std::uint64_t topBit {std::uint64_t {1} << 63};
    std::uint64_t low_ {0}, high_ {0};
};

#if !AVOID_NATIVE_INT128_T && HAVE(INT128_T)
using UInt128 = __uint128_t;
using Int128 = __int128_t;
#else
using UInt128 = Int128Impl<false>;
using Int128 = Int128Impl<true>;
#endif

template <int BITS> struct HostUnsignedIntTypeHelper {
    using type = std::conditional_t<(BITS <= 8), std::uint8_t,
        std::conditional_t<(BITS <= 16), std::uint16_t,
        std::conditional_t<(BITS <= 32), std::uint32_t,
        std::conditional_t<(BITS <= 64), std::uint64_t, UInt128>>>>;
};
template <int BITS> struct HostSignedIntTypeHelper {
    using type = std::conditional_t<(BITS <= 8), std::int8_t,
        std::conditional_t<(BITS <= 16), std::int16_t,
        std::conditional_t<(BITS <= 32), std::int32_t,
        std::conditional_t<(BITS <= 64), std::int64_t, Int128>>>>;
};
template <int BITS>
using HostUnsignedIntType = typename HostUnsignedIntTypeHelper<BITS>::type;
template <int BITS>
using HostSignedIntType = typename HostSignedIntTypeHelper<BITS>::type;

} // namespace WTF

using WTF::Int128;
using WTF::UInt128;