Number.h

#pragma once
 
#include <xrpl/beast/utility/instrumentation.h>
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <optional>
#include <ostream>
#include <set>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
 
namespace xrpl {
 
class Number;
 
std::string
to_string(Number const& amount);
 
template <typename T>
constexpr std::optional<int>
logTen(T value)
{
    int log = 0;
    while (value >= 10 && value % 10 == 0)
    {
        value /= 10;
        ++log;
    }
    if (value == 1)
        return log;
    return std::nullopt;
}
 
template <typename T>
constexpr bool
isPowerOfTen(T value)
{
    return logTen(value).has_value();
}
 
namespace detail {

constexpr std::size_t kUint64Digits = 20;
[[maybe_unused]] constexpr std::size_t kUint128Digits = 39;
 
template <typename T, std::size_t Digits>
consteval std::array<T, Digits>
buildPowersOfTen()
{
    std::array<T, Digits> result{};
 
    T power = 1;
    std::size_t exponent = 0;
    // end the loop early so it doesn't overflow;
    for (; exponent < result.size() - 1; ++exponent, power *= 10)
    {
        result[exponent] = power;
        if (power > std::numeric_limits<T>::max() / 10)
            throw std::logic_error("Power of 10 table is too big");
    }
    result[exponent] = power;
    if (power < std::numeric_limits<T>::max() / 10)
        throw std::logic_error("Power of 10 table is not big enough for the given type");
 
    return result;
}
 
}  // namespace detail
 
template <typename T = std::uint64_t, std::size_t Digits = detail::kUint64Digits>
constexpr std::array<T, Digits> kPowerOfTenImpl = detail::buildPowersOfTen<T, Digits>();
 
constexpr auto kPowerOfTen = kPowerOfTenImpl<std::uint64_t, detail::kUint64Digits>;
 
static_assert(kPowerOfTen[0] == 1);
static_assert(kPowerOfTen[1] == 10);
static_assert(kPowerOfTen[10] == 10'000'000'000);
static_assert(
    isPowerOfTen(kPowerOfTen.back()) && *logTen(kPowerOfTen.back()) == detail::kUint64Digits - 1);

struct MantissaRange final
{
    using rep = std::uint64_t;
 
    // NOLINTBEGIN(readability-enum-initial-value)
    // The values don't matter, except for Large
    enum class MantissaScale {
        // Small can be removed when any of featureSingleAssetVault, featureLendingProtocol, or
        // featureMPTokensV2 are retired
        Small,
        // LargeLegacy can be removed when fixCleanup3_2_0 is retired
        LargeLegacy,
        // Large320 can be removed when fixCleanup3_3_0 is retired
        Large320,
        // If Large330 is ever the only remaining "Large*" entry, it can be renamed to just "Large".
        Large330,
        // Large is a de-facto alias for "the latest", and is only here for backward compatibility
        // in the extremely unlikely case that a downstream project made use of it. Note that
        // because the behavior changed, this may still be a breaking change.
        Large = Large330,
    };
    // NOLINTEND(readability-enum-initial-value)
 
    // This entire enum can be removed when the last relevant amendment is retired
    enum class CuspRoundingFix : std::uint8_t {
        // Disabled can be removed when fixCleanup3_2_0 is retired
        Disabled = 0,
        // Enabled320 can be removed when fixCleanup3_3_0 is retired
        Enabled320 = 1,
        // If we ever get to the point that there's only one entry, remove the entire enum
        Enabled330 = 2,
        // Enabled is a de-facto alias for "the latest", and is only here for backward compatibility
        // in the extremely unlikely case that a downstream project made use of it. Note that
        // because the behavior changed, this may still be a breaking change.
        Enabled = Enabled330,
    };
 
    explicit constexpr MantissaRange(MantissaScale sc) : scale(sc)
    {
    }
 
    MantissaScale const scale;
    int const log{getExponent(scale)};
    rep const min{getMin(scale, log)};
    rep const max{(min * 10) - 1};
    CuspRoundingFix const cuspRoundingFix{isCuspFixEnabled(scale)};
 
    static std::set<MantissaScale> const&
    getAllScales()
    {
        static std::set<MantissaRange::MantissaScale> const kScales = {
            MantissaRange::MantissaScale::Small,
            MantissaRange::MantissaScale::LargeLegacy,
            MantissaRange::MantissaScale::Large320,
            MantissaRange::MantissaScale::Large330,
        };
        return kScales;
    }
 
    class Access
    {
        static constexpr MantissaRange const&
        mantissaRange(MantissaScale scale);
 
        friend Number;
    };
 
private:
    static constexpr int
    getExponent(MantissaScale scale)
    {
        switch (scale)
        {
            case MantissaScale::Small:
                return 15;
            case MantissaScale::LargeLegacy:
            case MantissaScale::Large320:
            case MantissaScale::Large330:
                return 18;
            // LCOV_EXCL_START
            default:
                // If called in a constexpr context, this throw assures that the build fails if an
                // invalid scale is used.
                throw std::runtime_error("Unknown mantissa scale");
                // LCOV_EXCL_STOP
        }
    }
 
    // Keep this function for future use with different ways to compute
    // the ranges.
    static constexpr rep
    getMin(MantissaScale scale, int exponent)
    {
        if (exponent < 0 || exponent >= kPowerOfTen.size())
            throw std::runtime_error("Invalid exponent");  // LCOV_EXCL_LINE
        return kPowerOfTen[exponent];
    }
 
    static constexpr CuspRoundingFix
    isCuspFixEnabled(MantissaScale scale)
    {
        switch (scale)
        {
            case MantissaScale::Small:
            case MantissaScale::LargeLegacy:
                return CuspRoundingFix::Disabled;
            case MantissaScale::Large320:
                return CuspRoundingFix::Enabled320;
            case MantissaScale::Large330:
                return CuspRoundingFix::Enabled330;
            default:
                // If called in a constexpr context, this throw assures that the build fails if an
                // invalid scale is used.
                throw std::runtime_error("Unknown mantissa scale");  // LCOV_EXCL_LINE
        }
    }
};
 
// Like std::integral, but only 64-bit integral types.
template <class T>
concept Integral64 = std::is_same_v<T, std::int64_t> || std::is_same_v<T, std::uint64_t>;

class Number final
{
    using rep = std::int64_t;
    using InternalRep = MantissaRange::rep;
 
    bool negative_{false};
    InternalRep mantissa_{0};
    int exponent_{std::numeric_limits<int>::lowest()};
 
public:
    // The range for the exponent when normalized
    static constexpr int kMinExponent = -32768;
    static constexpr int kMaxExponent = 32768;
 
    static constexpr InternalRep kMaxRep = std::numeric_limits<rep>::max();
    static_assert(kMaxRep == 9'223'372'036'854'775'807);
    static_assert(-kMaxRep == std::numeric_limits<rep>::min() + 1);
    static constexpr InternalRep kMaxRepUp = ((kMaxRep / 10) + 1) * 10;
    static_assert(kMaxRepUp == 9'223'372'036'854'775'810ULL);
 
    // May need to make unchecked private
    struct Unchecked
    {
        explicit Unchecked() = default;
    };
 
    // Like unchecked, normalized is used with the ctors that take an
    // internalrep mantissa. Unlike unchecked, those ctors will normalize the
    // value.
    // Only unit tests are expected to use this class
    struct Normalized
    {
        explicit Normalized() = default;
    };
 
    explicit constexpr Number() = default;
 
    Number(rep mantissa);
    explicit Number(rep mantissa, int exponent);
    explicit constexpr Number(
        bool negative,
        InternalRep mantissa,
        int exponent,
        Unchecked) noexcept;
    // Assume unsigned values are... unsigned. i.e. positive
    explicit constexpr Number(InternalRep mantissa, int exponent, Unchecked) noexcept;
    // Only unit tests are expected to use this ctor
    explicit Number(bool negative, InternalRep mantissa, int exponent, Normalized);
    // Assume unsigned values are... unsigned. i.e. positive
    explicit Number(InternalRep mantissa, int exponent, Normalized);
 
    [[nodiscard]] constexpr rep
    mantissa() const noexcept;
    [[nodiscard]] constexpr int
    exponent() const noexcept;
 
    constexpr Number
    operator+() const noexcept;
    constexpr Number
    operator-() const noexcept;
    Number&
    operator++();
    Number
    operator++(int);
    Number&
    operator--();
    Number
    operator--(int);
 
    Number&
    operator+=(Number const& x);
    Number&
    operator-=(Number const& x);
 
    Number&
    operator*=(Number const& x);
    Number&
    operator/=(Number const& x);
 
    static Number
    min() noexcept;
    static Number
    max() noexcept;
    static Number
    lowest() noexcept;

    explicit
    operator rep() const;  // round to nearest, even on tie
 
    friend constexpr bool
    operator==(Number const& x, Number const& y) noexcept
    {
        return x.negative_ == y.negative_ && x.mantissa_ == y.mantissa_ &&
            x.exponent_ == y.exponent_;
    }
 
    friend constexpr bool
    operator<(Number const& l, Number const& r) noexcept
    {
        bool const lneg = l.negative_;
        bool const rneg = r.negative_;
 
        // If the two amounts have different signs (zero is treated as positive)
        // then the comparison is true iff the left is negative.
        if (lneg != rneg)
            return lneg;
 
        // Both have same sign and the left is zero: both must be non-negative.
        // If the right is greater than 0, then it is larger, so the comparison is true.
        if (l.mantissa_ == 0)
            return r.mantissa_ > 0;
 
        // Both have same sign, the right is zero and the left is non-zero, so the left must be
        // positive, and thus is larger, so the comparison is false.
        if (r.mantissa_ == 0)
            return false;
 
        // Both have the same sign, compare by exponents:
        if (l.exponent_ > r.exponent_)
            return lneg;
        if (l.exponent_ < r.exponent_)
            return !lneg;
 
        // If equal signs and exponents, compare mantissas.
        if (lneg)
        {
            // If negative, the operator is reversed.
            return l.mantissa_ > r.mantissa_;
        }
 
        return l.mantissa_ < r.mantissa_;
    }

    [[nodiscard]] constexpr int
    signum() const noexcept
    {
        if (negative_)
            return -1;
        return (mantissa_ != 0u) ? 1 : 0;
    }
 
    [[nodiscard]] Number
    truncate() const noexcept;
 
    friend constexpr bool
    operator>(Number const& x, Number const& y) noexcept
    {
        return y < x;
    }
 
    friend constexpr bool
    operator<=(Number const& x, Number const& y) noexcept
    {
        return !(y < x);
    }
 
    friend constexpr bool
    operator>=(Number const& x, Number const& y) noexcept
    {
        return !(x < y);
    }
 
    friend std::ostream&
    operator<<(std::ostream& os, Number const& x)
    {
        return os << to_string(x);
    }
 
    friend std::string
    to_string(Number const& amount);
 
    friend Number
    root(Number f, unsigned d);
 
    friend Number
    root2(Number f);
 
    // Thread local rounding control.  Default is to_nearest
    enum class RoundingMode { ToNearest, TowardsZero, Downward, Upward };
 
    static RoundingMode
    getround();
 
    static RoundingMode
    setround(RoundingMode inMode);

    static MantissaRange::MantissaScale
    getMantissaScale();

    static void
    setMantissaScale(MantissaRange::MantissaScale scale);
 
    static InternalRep
    minMantissa()
    {
        return kRange.get().min;
    }
 
    static InternalRep
    maxMantissa()
    {
        return kRange.get().max;
    }
 
    static int
    mantissaLog()
    {
        return kRange.get().log;
    }
 
    static Number
    one();
 
    template <
        auto MinMantissa,
        auto MaxMantissa,
        Integral64 T = std::decay_t<decltype(MinMantissa)>>
    [[nodiscard]]
    std::pair<T, int>
    normalizeToRange() const;
 
    // Safely convert rep (int64) mantissa to internalrep (uint64). If the rep
    // is negative, returns the positive value. This takes a little extra work
    // because converting std::numeric_limits<std::int64_t>::min() flirts with
    // UB, and can vary across compilers.
    static InternalRep
    externalToInternal(rep mantissa);
 
private:
    static thread_local RoundingMode mode;
    // The available ranges for mantissa
 
    // The range for the mantissa when normalized.
    // Use reference_wrapper to avoid making copies, and prevent accidentally
    // changing the values inside the range.
    static thread_local std::reference_wrapper<MantissaRange const> kRange;
 
    class Guard;
 
    void
    normalize(MantissaRange const& range);
 
    // Guard has the fields that we need, as well as MantissaRange, so if we have a guard, use that
    void
    normalize(Guard const& guard);

    template <class T>
    static void
    normalize(
        bool& negative,
        T& mantissa,
        int& exponent,
        InternalRep const& minMantissa,
        InternalRep const& maxMantissa,
        MantissaRange::CuspRoundingFix cuspRoundingFix);
 
    template <class T>
    friend void
    doNormalize(
        bool& negative,
        T& mantissa,
        int& exponent,
        MantissaRange::rep const& minMantissa,
        MantissaRange::rep const& maxMantissa,
        MantissaRange::CuspRoundingFix cuspRoundingFix,
        bool dropped);
 
    [[nodiscard]] bool
    isnormal() const noexcept;
 
    // Copy the number, but modify the exponent by "exponentDelta". Because the
    // mantissa doesn't change, the result will be "mostly" normalized, but the
    // exponent could go out of range, so it will be checked.
    [[nodiscard]] Number
    shiftExponent(int exponentDelta) const;
};
 
constexpr Number::Number(bool negative, InternalRep mantissa, int exponent, Unchecked) noexcept
    : negative_(negative), mantissa_{mantissa}, exponent_{exponent}
{
}
 
constexpr Number::Number(InternalRep mantissa, int exponent, Unchecked) noexcept
    : Number(false, mantissa, exponent, Unchecked{})
{
}
 
static constexpr Number kNumZero{};
 
inline Number::Number(bool negative, InternalRep mantissa, int exponent, Normalized)
    : Number(negative, mantissa, exponent, Unchecked{})
{
    normalize(kRange);
}
 
inline Number::Number(InternalRep mantissa, int exponent, Normalized)
    : Number(false, mantissa, exponent, Normalized{})
{
}
 
inline Number::Number(rep mantissa, int exponent)
    : Number(mantissa < 0, externalToInternal(mantissa), exponent, Normalized{})
{
}
 
inline Number::Number(rep mantissa) : Number{mantissa, 0}
{
}

constexpr Number::rep
Number::mantissa() const noexcept
{
    auto m = mantissa_;
    if (m > kMaxRep)
    {
        XRPL_ASSERT_PARTS(
            !isnormal() || (m % 10 == 0 && m / 10 <= kMaxRep),
            "xrpl::Number::mantissa",
            "large normalized mantissa has no remainder");
        m /= 10;
    }
    auto const sign = negative_ ? -1 : 1;
    return sign * static_cast<Number::rep>(m);
}

constexpr int
Number::exponent() const noexcept
{
    auto e = exponent_;
    if (mantissa_ > kMaxRep)
    {
        XRPL_ASSERT_PARTS(
            !isnormal() || (mantissa_ % 10 == 0 && mantissa_ / 10 <= kMaxRep),
            "xrpl::Number::exponent",
            "large normalized mantissa has no remainder");
        ++e;
    }
    return e;
}
 
constexpr Number
Number::operator+() const noexcept
{
    return *this;
}
 
constexpr Number
Number::operator-() const noexcept
{
    if (mantissa_ == 0)
        return Number{};
    auto x = *this;
    x.negative_ = !x.negative_;
    return x;
}
 
inline Number&
Number::operator++()
{
    *this += one();
    return *this;
}
 
inline Number
Number::operator++(int)
{
    auto x = *this;
    ++(*this);
    return x;
}
 
inline Number&
Number::operator--()
{
    *this -= one();
    return *this;
}
 
inline Number
Number::operator--(int)
{
    auto x = *this;
    --(*this);
    return x;
}
 
inline Number&
Number::operator-=(Number const& x)
{
    return *this += -x;
}
 
inline Number
operator+(Number const& x, Number const& y)
{
    auto z = x;
    z += y;
    return z;
}
 
inline Number
operator-(Number const& x, Number const& y)
{
    auto z = x;
    z -= y;
    return z;
}
 
inline Number
operator*(Number const& x, Number const& y)
{
    auto z = x;
    z *= y;
    return z;
}
 
inline Number
operator/(Number const& x, Number const& y)
{
    auto z = x;
    z /= y;
    return z;
}
 
inline Number
Number::min() noexcept
{
    return Number{false, kRange.get().min, kMinExponent, Unchecked{}};
}
 
inline Number
Number::max() noexcept
{
    return Number{false, std::min(kRange.get().max, kMaxRep), kMaxExponent, Unchecked{}};
}
 
inline Number
Number::lowest() noexcept
{
    return Number{true, std::min(kRange.get().max, kMaxRep), kMaxExponent, Unchecked{}};
}
 
inline bool
Number::isnormal() const noexcept
{
    MantissaRange const& range = kRange;
    auto const absM = mantissa_;
    return *this == Number{} ||
        (range.min <= absM && absM <= range.max && (absM <= kMaxRep || absM % 10 == 0) &&
         kMinExponent <= exponent_ && exponent_ <= kMaxExponent);
}
 
template <auto MinMantissa, auto MaxMantissa, Integral64 T>
std::pair<T, int>
Number::normalizeToRange() const
{
    static_assert(std::is_same_v<T, std::uint64_t> || std::is_same_v<T, std::int64_t>);
    static_assert(std::is_same_v<T, std::decay_t<decltype(MinMantissa)>>);
    static_assert(std::is_same_v<T, std::decay_t<decltype(MaxMantissa)>>);
    auto constexpr kMIN = static_cast<T>(MinMantissa);
    auto constexpr kMAX = static_cast<T>(MaxMantissa);
    static_assert(kMIN > 0);
    static_assert(kMIN % 10 == 0);
    static_assert(isPowerOfTen(kMIN));
    static_assert(kMAX % 10 == 9);
    static_assert((kMAX + 1) / 10 == kMIN);
 
    bool negative = negative_;
    InternalRep mantissa = mantissa_;
    int exponent = exponent_;
 
    if constexpr (std::is_unsigned_v<T>)
    {
        XRPL_ASSERT_PARTS(
            !negative,
            "xrpl::Number::normalizeToRange",
            "Number is non-negative for unsigned range.");
    }
    // Don't need to worry about the cuspRounding fix because rounding up will never take the
    // mantissa over maxMantissa with a ones digit value other than 0. 0 can safely be truncated.
    Number::normalize(
        negative, mantissa, exponent, kMIN, kMAX, MantissaRange::CuspRoundingFix::Disabled);
 
    auto const sign = negative ? -1 : 1;
    return std::make_pair(static_cast<T>(sign * mantissa), exponent);
}
 
constexpr Number
abs(Number x) noexcept
{
    if (x < Number{})
        x = -x;
    return x;
}
 
// Returns f^n
// Uses a log_2(n) number of multiplications
 
Number
power(Number const& f, unsigned n);
 
// Returns f^(1/d)
// Uses Newton–Raphson iterations until the result stops changing
// to find the root of the polynomial g(x) = x^d - f
 
Number
root(Number f, unsigned d);
 
Number
root2(Number f);
 
// Returns f^(n/d)
 
Number
power(Number const& f, unsigned n, unsigned d);
 
// Return 0 if abs(x) < limit, else returns x
 
constexpr Number
squelch(Number const& x, Number const& limit) noexcept
{
    if (abs(x) < limit)
        return Number{};
    return x;
}
 
std::string
to_string(MantissaRange::MantissaScale const& scale);
 
std::string
to_string(Number::RoundingMode const& round);
 
class SaveNumberRoundMode
{
    Number::RoundingMode mode_;
 
public:
    ~SaveNumberRoundMode()
    {
        Number::setround(mode_);
    }
    explicit SaveNumberRoundMode(Number::RoundingMode mode) noexcept : mode_{mode}
    {
    }
    SaveNumberRoundMode(SaveNumberRoundMode const&) = delete;
    SaveNumberRoundMode&
    operator=(SaveNumberRoundMode const&) = delete;
};
 
// saveNumberRoundMode doesn't do quite enough for us.  What we want is a
// Number::RoundModeGuard that sets the new mode and restores the old mode
// when it leaves scope.  Since Number doesn't have that facility, we'll
// build it here.
class NumberRoundModeGuard
{
    SaveNumberRoundMode saved_;
 
public:
    explicit NumberRoundModeGuard(Number::RoundingMode mode) noexcept
        : saved_{Number::setround(mode)}
    {
    }
 
    NumberRoundModeGuard(NumberRoundModeGuard const&) = delete;
 
    NumberRoundModeGuard&
    operator=(NumberRoundModeGuard const&) = delete;
};

class NumberMantissaScaleGuard
{
    MantissaRange::MantissaScale const saved_;
 
public:
    explicit NumberMantissaScaleGuard(MantissaRange::MantissaScale scale) noexcept
        : saved_{Number::getMantissaScale()}
    {
        Number::setMantissaScale(scale);
    }
 
    ~NumberMantissaScaleGuard()
    {
        Number::setMantissaScale(saved_);
    }
 
    NumberMantissaScaleGuard(NumberMantissaScaleGuard const&) = delete;
 
    NumberMantissaScaleGuard&
    operator=(NumberMantissaScaleGuard const&) = delete;
};
 
}  // namespace xrpl