Compare commits

..

41 Commits

Author SHA1 Message Date
Ed Hennis
ae41a712b3 Merge branch 'develop' into ximinez/fix/validator-cache 2026-02-24 17:34:55 -04:00
Ed Hennis
7684f9dd58 Merge branch 'develop' into ximinez/fix/validator-cache 2026-02-20 18:49:57 -04:00
Ed Hennis
7c34be898d Merge branch 'develop' into ximinez/fix/validator-cache 2026-02-20 18:26:15 -04:00
Ed Hennis
5e282f49da Merge branch 'develop' into ximinez/fix/validator-cache 2026-02-20 17:31:58 -04:00
Ed Hennis
86722689ac Merge remote-tracking branch 'upstream/develop' into ximinez/fix/validator-cache
* upstream/develop:
  ci: [DEPENDABOT] bump tj-actions/changed-files from 46.0.5 to 47.0.4 (6394)
  ci: [DEPENDABOT] bump codecov/codecov-action from 5.4.3 to 5.5.2 (6398)
  ci: Build docs in PRs and in private repos (6400)
  ci: Add dependabot config (6379)
  Fix tautological assertion (6393)
  chore: Apply clang-format width 100 (6387)
2026-02-20 16:25:05 -05:00
Ed Hennis
3759144bba Update formatting 2026-02-20 16:23:53 -05:00
Ed Hennis
16c41c2143 Merge commit '25cca465538a56cce501477f9e5e2c1c7ea2d84c' into ximinez/fix/validator-cache
* commit '25cca465538a56cce501477f9e5e2c1c7ea2d84c':
  chore: Set clang-format width to 100 in config file (6387)
2026-02-20 16:22:13 -05:00
Ed Hennis
af28042946 Merge branch 'develop' into ximinez/fix/validator-cache 2026-02-19 16:24:50 -05:00
Ed Hennis
734426554d Merge branch 'develop' into ximinez/fix/validator-cache 2026-02-18 20:49:50 -04:00
Ed Hennis
7f17daa95f Merge branch 'develop' into ximinez/fix/validator-cache 2026-02-04 16:30:05 -04:00
Ed Hennis
f359cd8dad Merge branch 'develop' into ximinez/fix/validator-cache 2026-02-03 16:08:02 -04:00
Ed Hennis
bf0b10404d Fix formatting 2026-01-28 19:40:27 -05:00
Ed Hennis
d019ebaf36 Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-28 18:44:52 -04:00
Ed Hennis
b6e4620349 Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-15 13:03:28 -04:00
Ed Hennis
db0ef6a370 Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-15 12:05:56 -04:00
Ed Hennis
11a45a0ac2 Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-13 18:19:08 -04:00
Ed Hennis
aa035f4cfd Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-13 15:27:57 -04:00
Ed Hennis
8988f9117f Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-12 14:52:12 -04:00
Ed Hennis
ae4f379845 Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-11 00:50:40 -04:00
Ed Hennis
671aa11649 Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-08 17:06:06 -04:00
Ed Hennis
53d35fd8ea Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-08 13:04:16 -04:00
Ed Hennis
0c7ea2e333 Merge branch 'develop' into ximinez/fix/validator-cache 2026-01-06 14:02:10 -05:00
Ed Hennis
5f54be25e9 Merge branch 'develop' into ximinez/fix/validator-cache 2025-12-22 17:39:55 -05:00
Ed Hennis
d82756519c Merge branch 'develop' into ximinez/fix/validator-cache 2025-12-18 19:59:49 -05:00
Ed Hennis
1f23832659 Merge branch 'develop' into ximinez/fix/validator-cache 2025-12-12 20:34:55 -05:00
Ed Hennis
4c50969bde Merge branch 'develop' into ximinez/fix/validator-cache 2025-12-11 15:31:29 -05:00
Ed Hennis
aabdf372dd Merge branch 'develop' into ximinez/fix/validator-cache 2025-12-05 21:13:06 -05:00
Ed Hennis
c6d63a4b90 Merge branch 'develop' into ximinez/fix/validator-cache 2025-12-02 17:37:25 -05:00
Ed Hennis
1e6c3208db Merge branch 'develop' into ximinez/fix/validator-cache 2025-12-01 14:40:41 -05:00
Ed Hennis
a74f223efb Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-28 15:46:40 -05:00
Ed Hennis
1eb3a3ea5a Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-27 01:48:53 -05:00
Ed Hennis
630e428929 Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-26 00:25:12 -05:00
Ed Hennis
3f93edc5e0 Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-25 14:55:02 -05:00
Ed Hennis
baf62689ff Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-24 21:49:07 -05:00
Ed Hennis
ddf7d6cac4 Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-24 21:30:18 -05:00
Ed Hennis
fcd2ea2d6e Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-21 12:47:54 -05:00
Ed Hennis
a16aa5b12f Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-18 22:39:25 -05:00
Ed Hennis
ef2de81870 Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-15 03:08:38 -05:00
Ed Hennis
fce6757260 Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-13 12:19:10 -05:00
Ed Hennis
d759a0a2b0 Merge branch 'develop' into ximinez/fix/validator-cache 2025-11-12 14:12:51 -05:00
Ed Hennis
d2dda416e8 Use Validator List (VL) cache files in more scenarios
- If any [validator_list_keys] are not available after all
  [validator_list_sites] have had a chance to be queried, then fall
  back to loading cache files. Currently, cache files are only used if
  no sites are defined, or the request to one of them has an error. It
  does not include cases where not enough sites are defined, or if a
  site returns an invalid VL (or something else entirely).
- Resolves #5320
2025-11-10 19:53:02 -05:00
7 changed files with 421 additions and 1006 deletions

View File

@@ -7,13 +7,8 @@
#include <limits>
#include <optional>
#include <ostream>
#include <stdexcept>
#include <string>
#ifdef _MSC_VER
#include <boost/multiprecision/cpp_int.hpp>
#endif // !defined(_MSC_VER)
namespace xrpl {
class Number;
@@ -21,39 +16,18 @@ class Number;
std::string
to_string(Number const& amount);
/** Returns a rough estimate of log10(value).
*
* The return value is a pair (log, rem), where log is the estimated
* base-10 logarithm (roughly floor(log10(value))), and rem is value with
* all factors of 10 removed (i.e., divided by the largest power of 10 that
* divides value). If rem is 1, then value is an exact power of ten, and
* log is the exact log10(value).
*
* This function only works for positive values.
*/
template <typename T>
constexpr std::pair<int, T>
logTenEstimate(T value)
{
int log = 0;
T remainder = value;
while (value >= 10)
{
if (value % 10 == 0)
remainder = remainder / 10;
value /= 10;
++log;
}
return {log, remainder};
}
template <typename T>
constexpr std::optional<int>
logTen(T value)
{
auto const est = logTenEstimate(value);
if (est.second == 1)
return est.first;
int log = 0;
while (value >= 10 && value % 10 == 0)
{
value /= 10;
++log;
}
if (value == 1)
return log;
return std::nullopt;
}
@@ -67,10 +41,12 @@ isPowerOfTen(T value)
/** MantissaRange defines a range for the mantissa of a normalized Number.
*
* The mantissa is in the range [min, max], where
* * min is a power of 10, and
* * max = min * 10 - 1.
*
* The mantissa_scale enum indicates whether the range is "small" or
* "large". This intentionally prevents the creation of any
* MantissaRanges representing other values.
* The mantissa_scale enum indicates whether the range is "small" or "large".
* This intentionally restricts the number of MantissaRanges that can be
* instantiated to two: one for each scale.
*
* The "small" scale is based on the behavior of STAmount for IOUs. It has a min
* value of 10^15, and a max value of 10^16-1. This was sufficient for
@@ -84,8 +60,8 @@ isPowerOfTen(T value)
* "large" scale.
*
* The "large" scale is intended to represent all values that can be represented
* by an STAmount - IOUs, XRP, and MPTs. It has a min value of 2^63/10+1
* (truncated), and a max value of 2^63-1.
* by an STAmount - IOUs, XRP, and MPTs. It has a min value of 10^18, and a max
* value of 10^19-1.
*
* Note that if the mentioned amendments are eventually retired, this class
* should be left in place, but the "small" scale option should be removed. This
@@ -97,50 +73,25 @@ struct MantissaRange
enum mantissa_scale { small, large };
explicit constexpr MantissaRange(mantissa_scale scale_)
: max(getMax(scale_))
, min(computeMin(max))
, referenceMin(getReferenceMin(scale_, min))
, log(computeLog(min))
, scale(scale_)
: min(getMin(scale_)), max(min * 10 - 1), log(logTen(min).value_or(-1)), scale(scale_)
{
// Since this is constexpr, if any of these throw, it won't compile
if (min * 10 <= max)
throw std::out_of_range("min * 10 <= max");
if (max / 10 >= min)
throw std::out_of_range("max / 10 >= min");
if ((min - 1) * 10 > max)
throw std::out_of_range("(min - 1) * 10 > max");
// This is a little hacky
if ((max + 10) / 10 < min)
throw std::out_of_range("(max + 10) / 10 < min");
}
// Explicitly delete copy and move operations
MantissaRange(MantissaRange const&) = delete;
MantissaRange(MantissaRange&&) = delete;
MantissaRange&
operator=(MantissaRange const&) = delete;
MantissaRange&
operator=(MantissaRange&&) = delete;
rep max;
rep min;
// This is not a great name. Used to determine if mantissas are in range,
// but have fewer digits than max
rep referenceMin;
rep max;
int log;
mantissa_scale scale;
private:
static constexpr rep
getMax(mantissa_scale scale)
getMin(mantissa_scale scale_)
{
switch (scale)
switch (scale_)
{
case small:
return 9'999'999'999'999'999ULL;
return 1'000'000'000'000'000ULL;
case large:
return std::numeric_limits<std::int64_t>::max();
return 1'000'000'000'000'000'000ULL;
default:
// Since this can never be called outside a non-constexpr
// context, this throw assures that the build fails if an
@@ -148,59 +99,19 @@ private:
throw std::runtime_error("Unknown mantissa scale");
}
}
static constexpr rep
computeMin(rep max)
{
return max / 10 + 1;
}
static constexpr rep
getReferenceMin(mantissa_scale scale, rep min)
{
switch (scale)
{
case large:
return 1'000'000'000'000'000'000ULL;
default:
if (isPowerOfTen(min))
return min;
throw std::runtime_error("Unknown/bad mantissa scale");
}
}
static constexpr rep
computeLog(rep min)
{
auto const estimate = logTenEstimate(min);
return estimate.first + (estimate.second == 1 ? 0 : 1);
}
};
// 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>;
namespace detail {
#ifdef _MSC_VER
using uint128_t = boost::multiprecision::uint128_t;
using int128_t = boost::multiprecision::int128_t;
#else // !defined(_MSC_VER)
using uint128_t = __uint128_t;
using int128_t = __int128_t;
#endif // !defined(_MSC_VER)
template <class T>
concept UnsignedMantissa = std::is_unsigned_v<T> || std::is_same_v<T, uint128_t>;
} // namespace detail
/** Number is a floating point type that can represent a wide range of values.
*
* It can represent all values that can be represented by an STAmount -
* regardless of asset type - XRPAmount, MPTAmount, and IOUAmount, with at least
* as much precision as those types require.
*
* ---- Internal Operational Representation ----
* ---- Internal Representation ----
*
* Internally, Number is represented with three values:
* 1. a bool sign flag,
@@ -215,21 +126,15 @@ concept UnsignedMantissa = std::is_unsigned_v<T> || std::is_same_v<T, uint128_t>
*
* A non-zero mantissa is (almost) always normalized, meaning it and the
* exponent are grown or shrunk until the mantissa is in the range
* [MantissaRange.referenceMin, MantissaRange.referenceMin * 10 - 1].
*
* This internal representation is only used during some operations to ensure
* that the mantissa is a known, predictable size. The class itself stores the
* values using the external representation described below.
* [MantissaRange.min, MantissaRange.max].
*
* Note:
* 1. Normalization can be disabled by using the "unchecked" ctor tag. This
* should only be used at specific conversion points, some constexpr
* values, and in unit tests.
* 2. Unlike MantissaRange.min, referenceMin is always an exact power of 10,
* so a mantissa in the internal representation will always have a
* consistent number of digits.
* 3. The functions toInternal() and fromInternal() are used to convert
* between the two representations.
* 2. The max of the "large" range, 10^19-1, is the largest 10^X-1 value that
* fits in an unsigned 64-bit number. (10^19-1 < 2^64-1 and
* 10^20-1 > 2^64-1). This avoids under- and overflows.
*
* ---- External Interface ----
*
@@ -242,12 +147,13 @@ concept UnsignedMantissa = std::is_unsigned_v<T> || std::is_same_v<T, uint128_t>
* represent the full range of valid XRP and MPT integer values accurately.
*
* Note:
* 1. The "large" mantissa range is (2^63/10+1) to 2^63-1. 2^63-1 is between
* 10^18 and 10^19-1, and (2^63/10+1) is between 10^17 and 10^18-1. Thus,
* the mantissa may have 18 or 19 digits. This value will be modified to
* always have 19 digits before some operations to ensure consistency.
* 1. 2^63-1 is between 10^18 and 10^19-1, which are the limits of the "large"
* mantissa range.
* 2. The functions mantissa() and exponent() return the external view of the
* Number value, specifically using a signed 63-bit mantissa.
* Number value, specifically using a signed 63-bit mantissa. This may
* require altering the internal representation to fit into that range
* before the value is returned. The interface guarantees consistency of
* the two values.
* 3. Number cannot represent -2^63 (std::numeric_limits<std::int64_t>::min())
* as an exact integer, but it doesn't need to, because all asset values
* on-ledger are non-negative. This is due to implementation details of
@@ -302,7 +208,8 @@ class Number
using rep = std::int64_t;
using internalrep = MantissaRange::rep;
rep mantissa_{0};
bool negative_{false};
internalrep mantissa_{0};
int exponent_{std::numeric_limits<int>::lowest()};
public:
@@ -310,6 +217,10 @@ public:
constexpr static int minExponent = -32768;
constexpr static int maxExponent = 32768;
constexpr static internalrep maxRep = std::numeric_limits<rep>::max();
static_assert(maxRep == 9'223'372'036'854'775'807);
static_assert(-maxRep == std::numeric_limits<rep>::min() + 1);
// May need to make unchecked private
struct unchecked
{
@@ -387,7 +298,8 @@ public:
friend constexpr bool
operator==(Number const& x, Number const& y) noexcept
{
return x.mantissa_ == y.mantissa_ && x.exponent_ == y.exponent_;
return x.negative_ == y.negative_ && x.mantissa_ == y.mantissa_ &&
x.exponent_ == y.exponent_;
}
friend constexpr bool
@@ -401,8 +313,8 @@ public:
{
// If the two amounts have different signs (zero is treated as positive)
// then the comparison is true iff the left is negative.
bool const lneg = x.mantissa_ < 0;
bool const rneg = y.mantissa_ < 0;
bool const lneg = x.negative_;
bool const rneg = y.negative_;
if (lneg != rneg)
return lneg;
@@ -430,7 +342,7 @@ public:
constexpr int
signum() const noexcept
{
return mantissa_ < 0 ? -1 : (mantissa_ ? 1 : 0);
return negative_ ? -1 : (mantissa_ ? 1 : 0);
}
Number
@@ -469,9 +381,6 @@ public:
friend Number
root2(Number f);
friend Number
power(Number const& f, unsigned n, unsigned d);
// Thread local rounding control. Default is to_nearest
enum rounding_mode { to_nearest, towards_zero, downward, upward };
static rounding_mode
@@ -536,39 +445,22 @@ private:
static_assert(isPowerOfTen(smallRange.min));
static_assert(smallRange.min == 1'000'000'000'000'000LL);
static_assert(smallRange.max == 9'999'999'999'999'999LL);
static_assert(smallRange.referenceMin == smallRange.min);
static_assert(smallRange.log == 15);
static_assert(smallRange.min < maxRep);
static_assert(smallRange.max < maxRep);
constexpr static MantissaRange largeRange{MantissaRange::large};
static_assert(!isPowerOfTen(largeRange.min));
static_assert(largeRange.min == 922'337'203'685'477'581ULL);
static_assert(largeRange.max == internalrep(9'223'372'036'854'775'807ULL));
static_assert(largeRange.max == std::numeric_limits<rep>::max());
static_assert(largeRange.referenceMin == 1'000'000'000'000'000'000ULL);
static_assert(isPowerOfTen(largeRange.min));
static_assert(largeRange.min == 1'000'000'000'000'000'000ULL);
static_assert(largeRange.max == internalrep(9'999'999'999'999'999'999ULL));
static_assert(largeRange.log == 18);
// There are 2 values that will not fit in largeRange without some extra
// work
// * 9223372036854775808
// * 9223372036854775809
// They both end up < min, but with a leftover. If they round up, everything
// will be fine. If they don't, we'll need to bring them up into range.
// Guard::bringIntoRange handles this situation.
static_assert(largeRange.min < maxRep);
static_assert(largeRange.max > maxRep);
// 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> range_;
// And one is needed because it needs to choose between oneSmall and
// oneLarge based on the current range
static Number
one(MantissaRange const& range);
static Number
root(MantissaRange const& range, Number f, unsigned d);
void
normalize(MantissaRange const& range);
void
normalize();
@@ -591,14 +483,11 @@ private:
friend void
doNormalize(
bool& negative,
T& mantissa,
int& exponent,
T& mantissa_,
int& exponent_,
MantissaRange::rep const& minMantissa,
MantissaRange::rep const& maxMantissa);
bool
isnormal(MantissaRange const& range) const noexcept;
bool
isnormal() const noexcept;
@@ -608,60 +497,14 @@ private:
Number
shiftExponent(int exponentDelta) const;
// Safely return the absolute value of a rep (int64) mantissa as an internalrep (uint64).
// 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);
/** Breaks down the number into components, potentially de-normalizing it.
*
* Ensures that the mantissa always has range_.log + 1 digits.
*
*/
template <detail::UnsignedMantissa Rep = internalrep>
std::tuple<bool, Rep, int>
toInternal(MantissaRange const& range) const;
/** Breaks down the number into components, potentially de-normalizing it.
*
* Ensures that the mantissa always has range_.log + 1 digits.
*
*/
template <detail::UnsignedMantissa Rep = internalrep>
std::tuple<bool, Rep, int>
toInternal() const;
/** Rebuilds the number from components.
*
* If "expectNormal" is true, the values are expected to be normalized - all
* in their valid ranges.
*
* If "expectNormal" is false, the values are expected to be "near
* normalized", meaning that the mantissa has to be modified at most once to
* bring it back into range.
*
*/
template <bool expectNormal = true, detail::UnsignedMantissa Rep = internalrep>
void
fromInternal(bool negative, Rep mantissa, int exponent, MantissaRange const* pRange);
/** Rebuilds the number from components.
*
* If "expectNormal" is true, the values are expected to be normalized - all
* in their valid ranges.
*
* If "expectNormal" is false, the values are expected to be "near
* normalized", meaning that the mantissa has to be modified at most once to
* bring it back into range.
*
*/
template <bool expectNormal = true, detail::UnsignedMantissa Rep = internalrep>
void
fromInternal(bool negative, Rep mantissa, int exponent);
class Guard;
public:
constexpr static internalrep largestMantissa = largeRange.max;
};
inline constexpr Number::Number(
@@ -669,8 +512,7 @@ inline constexpr Number::Number(
internalrep mantissa,
int exponent,
unchecked) noexcept
: mantissa_{negative ? -static_cast<rep>(mantissa) : static_cast<rep>(mantissa)}
, exponent_{exponent}
: negative_(negative), mantissa_{mantissa}, exponent_{exponent}
{
}
@@ -681,6 +523,12 @@ inline constexpr Number::Number(internalrep mantissa, int exponent, unchecked) n
constexpr static Number numZero{};
inline Number::Number(bool negative, internalrep mantissa, int exponent, normalized)
: Number(negative, mantissa, exponent, unchecked{})
{
normalize();
}
inline Number::Number(internalrep mantissa, int exponent, normalized)
: Number(false, mantissa, exponent, normalized{})
{
@@ -703,7 +551,17 @@ inline Number::Number(rep mantissa) : Number{mantissa, 0}
inline constexpr Number::rep
Number::mantissa() const noexcept
{
return mantissa_;
auto m = mantissa_;
if (m > maxRep)
{
XRPL_ASSERT_PARTS(
!isnormal() || (m % 10 == 0 && m / 10 <= maxRep),
"xrpl::Number::mantissa",
"large normalized mantissa has no remainder");
m /= 10;
}
auto const sign = negative_ ? -1 : 1;
return sign * static_cast<Number::rep>(m);
}
/** Returns the exponent of the external view of the Number.
@@ -714,7 +572,16 @@ Number::mantissa() const noexcept
inline constexpr int
Number::exponent() const noexcept
{
return exponent_;
auto e = exponent_;
if (mantissa_ > maxRep)
{
XRPL_ASSERT_PARTS(
!isnormal() || (mantissa_ % 10 == 0 && mantissa_ / 10 <= maxRep),
"xrpl::Number::exponent",
"large normalized mantissa has no remainder");
++e;
}
return e;
}
inline constexpr Number
@@ -729,7 +596,7 @@ Number::operator-() const noexcept
if (mantissa_ == 0)
return Number{};
auto x = *this;
x.mantissa_ = -x.mantissa_;
x.negative_ = !x.negative_;
return x;
}
@@ -810,58 +677,42 @@ Number::min() noexcept
inline Number
Number::max() noexcept
{
return Number{false, range_.get().max, maxExponent, unchecked{}};
return Number{false, std::min(range_.get().max, maxRep), maxExponent, unchecked{}};
}
inline Number
Number::lowest() noexcept
{
return Number{true, range_.get().max, maxExponent, unchecked{}};
}
inline bool
Number::isnormal(MantissaRange const& range) const noexcept
{
auto const abs_m = externalToInternal(mantissa_);
return *this == Number{} ||
(range.min <= abs_m && abs_m <= range.max && //
minExponent <= exponent_ && exponent_ <= maxExponent);
return Number{true, std::min(range_.get().max, maxRep), maxExponent, unchecked{}};
}
inline bool
Number::isnormal() const noexcept
{
return isnormal(range_);
MantissaRange const& range = range_;
auto const abs_m = mantissa_;
return *this == Number{} ||
(range.min <= abs_m && abs_m <= range.max && (abs_m <= maxRep || abs_m % 10 == 0) &&
minExponent <= exponent_ && exponent_ <= maxExponent);
}
template <Integral64 T>
std::pair<T, int>
Number::normalizeToRange(T minMantissa, T maxMantissa) const
{
bool negative = mantissa_ < 0;
internalrep mantissa = externalToInternal(mantissa_);
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.");
// To avoid logical errors in release builds, throw if the Number is
// negative for an unsigned range.
if (negative)
throw std::runtime_error(
"Number::normalizeToRange: Number is negative for "
"unsigned range.");
}
Number::normalize(negative, mantissa, exponent, minMantissa, maxMantissa);
// Cast mantissa to signed type first (if T is a signed type) to avoid
// unsigned integer overflow when multiplying by negative sign
T signedMantissa = negative ? -static_cast<T>(mantissa) : static_cast<T>(mantissa);
return std::make_pair(signedMantissa, exponent);
auto const sign = negative ? -1 : 1;
return std::make_pair(static_cast<T>(sign * mantissa), exponent);
}
inline constexpr Number

View File

@@ -232,7 +232,7 @@ std::size_t constexpr maxMPTokenMetadataLength = 1024;
/** The maximum amount of MPTokenIssuance */
std::uint64_t constexpr maxMPTokenAmount = 0x7FFF'FFFF'FFFF'FFFFull;
static_assert(Number::largestMantissa >= maxMPTokenAmount);
static_assert(Number::maxRep >= maxMPTokenAmount);
/** The maximum length of Data payload */
std::size_t constexpr maxDataPayloadLength = 256;

View File

@@ -539,8 +539,6 @@ STAmount::fromNumber(A const& a, Number const& number)
return STAmount{asset, intValue, 0, negative};
}
XRPL_ASSERT_PARTS(
working.signum() >= 0, "xrpl::STAmount::fromNumber", "non-negative Number to normalize");
auto const [mantissa, exponent] = working.normalizeToRange(cMinValue, cMaxValue);
return STAmount{asset, mantissa, exponent, negative};

View File

@@ -23,7 +23,7 @@ systemName()
/** Number of drops in the genesis account. */
constexpr XRPAmount INITIAL_XRP{100'000'000'000 * DROPS_PER_XRP};
static_assert(INITIAL_XRP.drops() == 100'000'000'000'000'000);
static_assert(Number::largestMantissa >= INITIAL_XRP.drops());
static_assert(Number::maxRep >= INITIAL_XRP.drops());
/** Returns true if the amount does not exceed the initial XRP in existence. */
inline bool

View File

@@ -9,17 +9,20 @@
#include <iterator>
#include <limits>
#include <numeric>
#include <stdexcept>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
#ifdef _MSC_VER
#pragma message("Using boost::multiprecision::uint128_t and int128_t")
#endif
using uint128_t = xrpl::detail::uint128_t;
using int128_t = xrpl::detail::int128_t;
#include <boost/multiprecision/cpp_int.hpp>
using uint128_t = boost::multiprecision::uint128_t;
using int128_t = boost::multiprecision::int128_t;
#else // !defined(_MSC_VER)
using uint128_t = __uint128_t;
using int128_t = __int128_t;
#endif // !defined(_MSC_VER)
namespace xrpl {
@@ -58,6 +61,9 @@ Number::setMantissaScale(MantissaRange::mantissa_scale scale)
// precision to an operation. This enables the final result
// to be correctly rounded to the internal precision of Number.
template <class T>
concept UnsignedMantissa = std::is_unsigned_v<T> || std::is_same_v<T, uint128_t>;
class Number::Guard
{
std::uint64_t digits_; // 16 decimal guard digits
@@ -93,7 +99,7 @@ public:
round() noexcept;
// Modify the result to the correctly rounded value
template <detail::UnsignedMantissa T>
template <UnsignedMantissa T>
void
doRoundUp(
bool& negative,
@@ -101,22 +107,22 @@ public:
int& exponent,
internalrep const& minMantissa,
internalrep const& maxMantissa,
std::string_view location);
std::string location);
// Modify the result to the correctly rounded value
template <detail::UnsignedMantissa T>
template <UnsignedMantissa T>
void
doRoundDown(bool& negative, T& mantissa, int& exponent, internalrep const& minMantissa);
// Modify the result to the correctly rounded value
void
doRound(rep& drops, std::string_view location);
doRound(rep& drops, std::string location);
private:
void
doPush(unsigned d) noexcept;
template <detail::UnsignedMantissa T>
template <UnsignedMantissa T>
void
bringIntoRange(bool& negative, T& mantissa, int& exponent, internalrep const& minMantissa);
};
@@ -203,7 +209,7 @@ Number::Guard::round() noexcept
return 0;
}
template <detail::UnsignedMantissa T>
template <UnsignedMantissa T>
void
Number::Guard::bringIntoRange(
bool& negative,
@@ -222,13 +228,13 @@ Number::Guard::bringIntoRange(
{
constexpr Number zero = Number{};
negative = false;
negative = zero.negative_;
mantissa = zero.mantissa_;
exponent = zero.exponent_;
}
}
template <detail::UnsignedMantissa T>
template <UnsignedMantissa T>
void
Number::Guard::doRoundUp(
bool& negative,
@@ -236,7 +242,7 @@ Number::Guard::doRoundUp(
int& exponent,
internalrep const& minMantissa,
internalrep const& maxMantissa,
std::string_view location)
std::string location)
{
auto r = round();
if (r == 1 || (r == 0 && (mantissa & 1) == 1))
@@ -244,7 +250,7 @@ Number::Guard::doRoundUp(
++mantissa;
// Ensure mantissa after incrementing fits within both the
// min/maxMantissa range and is a valid "rep".
if (mantissa > maxMantissa)
if (mantissa > maxMantissa || mantissa > maxRep)
{
mantissa /= 10;
++exponent;
@@ -252,10 +258,10 @@ Number::Guard::doRoundUp(
}
bringIntoRange(negative, mantissa, exponent, minMantissa);
if (exponent > maxExponent)
throw std::overflow_error(std::string{location});
throw std::overflow_error(location);
}
template <detail::UnsignedMantissa T>
template <UnsignedMantissa T>
void
Number::Guard::doRoundDown(
bool& negative,
@@ -278,22 +284,21 @@ Number::Guard::doRoundDown(
// Modify the result to the correctly rounded value
void
Number::Guard::doRound(rep& drops, std::string_view location)
Number::Guard::doRound(rep& drops, std::string location)
{
auto r = round();
if (r == 1 || (r == 0 && (drops & 1) == 1))
{
auto const& range = range_.get();
if (drops >= range.max)
if (drops >= maxRep)
{
static_assert(sizeof(internalrep) == sizeof(rep));
// This should be impossible, because it's impossible to represent
// "largestMantissa + 0.6" in Number, regardless of the scale. There aren't
// enough digits available. You'd either get a mantissa of "largestMantissa"
// or "largestMantissa / 10 + 1", neither of which will round up when
// "maxRep + 0.6" in Number, regardless of the scale. There aren't
// enough digits available. You'd either get a mantissa of "maxRep"
// or "(maxRep + 1) / 10", neither of which will round up when
// converting to rep, though the latter might overflow _before_
// rounding.
throw std::overflow_error(std::string{location}); // LCOV_EXCL_LINE
throw std::overflow_error(location); // LCOV_EXCL_LINE
}
++drops;
}
@@ -313,133 +318,23 @@ Number::externalToInternal(rep mantissa)
// If the mantissa is already positive, just return it
if (mantissa >= 0)
return mantissa;
// If the mantissa is negative, but fits within the positive range of rep,
// return it negated
if (mantissa >= -std::numeric_limits<rep>::max())
return -mantissa;
// Cast to unsigned before negating to avoid undefined behavior
// when v == INT64_MIN (negating INT64_MIN in signed is UB)
return -static_cast<internalrep>(mantissa);
}
/** Breaks down the number into components, potentially de-normalizing it.
*
* Ensures that the mantissa always has range_.log + 1 digits.
*
*/
template <detail::UnsignedMantissa Rep>
std::tuple<bool, Rep, int>
Number::toInternal(MantissaRange const& range) const
{
auto exponent = exponent_;
bool const negative = mantissa_ < 0;
// It should be impossible for mantissa_ to be INT64_MIN, but use externalToInternal just in
// case.
Rep mantissa = static_cast<Rep>(externalToInternal(mantissa_));
auto const referenceMin = range.referenceMin;
auto const minMantissa = range.min;
if (mantissa != 0 && mantissa >= minMantissa && mantissa < referenceMin)
{
// Ensure the mantissa has the correct number of digits
mantissa *= 10;
--exponent;
XRPL_ASSERT_PARTS(
mantissa >= referenceMin && mantissa < referenceMin * 10,
"xrpl::Number::toInternal()",
"Number is within reference range and has 'log' digits");
}
return {negative, mantissa, exponent};
}
/** Breaks down the number into components, potentially de-normalizing it.
*
* Ensures that the mantissa always has exactly range_.log + 1 digits.
*
*/
template <detail::UnsignedMantissa Rep>
std::tuple<bool, Rep, int>
Number::toInternal() const
{
return toInternal(range_);
}
/** Rebuilds the number from components.
*
* If "expectNormal" is true, the values are expected to be normalized - all
* in their valid ranges.
*
* If "expectNormal" is false, the values are expected to be "near
* normalized", meaning that the mantissa has to be modified at most once to
* bring it back into range.
*
*/
template <bool expectNormal, detail::UnsignedMantissa Rep>
void
Number::fromInternal(bool negative, Rep mantissa, int exponent, MantissaRange const* pRange)
{
if constexpr (std::is_same_v<std::bool_constant<expectNormal>, std::false_type>)
{
if (!pRange)
throw std::runtime_error("Missing range to Number::fromInternal!");
auto const& range = *pRange;
auto const maxMantissa = range.max;
auto const minMantissa = range.min;
XRPL_ASSERT_PARTS(
mantissa >= minMantissa, "xrpl::Number::fromInternal", "mantissa large enough");
if (mantissa > maxMantissa || mantissa < minMantissa)
{
normalize(negative, mantissa, exponent, range.min, maxMantissa);
}
XRPL_ASSERT_PARTS(
mantissa >= minMantissa && mantissa <= maxMantissa,
"xrpl::Number::fromInternal",
"mantissa in range");
}
// mantissa is unsigned, but it might not be uint64
mantissa_ = static_cast<rep>(static_cast<internalrep>(mantissa));
if (negative)
mantissa_ = -mantissa_;
exponent_ = exponent;
XRPL_ASSERT_PARTS(
(pRange && isnormal(*pRange)) || isnormal(),
"xrpl::Number::fromInternal",
"Number is normalized");
}
/** Rebuilds the number from components.
*
* If "expectNormal" is true, the values are expected to be normalized - all in
* their valid ranges.
*
* If "expectNormal" is false, the values are expected to be "near normalized",
* meaning that the mantissa has to be modified at most once to bring it back
* into range.
*
*/
template <bool expectNormal, detail::UnsignedMantissa Rep>
void
Number::fromInternal(bool negative, Rep mantissa, int exponent)
{
MantissaRange const* pRange = nullptr;
if constexpr (std::is_same_v<std::bool_constant<expectNormal>, std::false_type>)
{
pRange = &Number::range_.get();
}
fromInternal(negative, mantissa, exponent, pRange);
// If the mantissa doesn't fit within the positive range, convert to
// int128_t, negate that, and cast it back down to the internalrep
// In practice, this is only going to cover the case of
// std::numeric_limits<rep>::min().
int128_t temp = mantissa;
return static_cast<internalrep>(-temp);
}
constexpr Number
Number::oneSmall()
{
return Number{
false, Number::smallRange.referenceMin, -Number::smallRange.log, Number::unchecked{}};
return Number{false, Number::smallRange.min, -Number::smallRange.log, Number::unchecked{}};
};
constexpr Number oneSml = Number::oneSmall();
@@ -447,89 +342,103 @@ constexpr Number oneSml = Number::oneSmall();
constexpr Number
Number::oneLarge()
{
return Number{
false, Number::largeRange.referenceMin, -Number::largeRange.log, Number::unchecked{}};
return Number{false, Number::largeRange.min, -Number::largeRange.log, Number::unchecked{}};
};
constexpr Number oneLrg = Number::oneLarge();
Number
Number::one(MantissaRange const& range)
Number::one()
{
if (&range == &smallRange)
if (&range_.get() == &smallRange)
return oneSml;
XRPL_ASSERT(&range == &largeRange, "Number::one() : valid range");
XRPL_ASSERT(&range_.get() == &largeRange, "Number::one() : valid range_");
return oneLrg;
}
Number
Number::one()
{
return one(range_);
}
// Use the member names in this static function for now so the diff is cleaner
// TODO: Rename the function parameters to get rid of the "_" suffix
template <class T>
void
doNormalize(
bool& negative,
T& mantissa,
int& exponent,
T& mantissa_,
int& exponent_,
MantissaRange::rep const& minMantissa,
MantissaRange::rep const& maxMantissa)
{
auto constexpr minExponent = Number::minExponent;
auto constexpr maxExponent = Number::maxExponent;
auto constexpr maxRep = Number::maxRep;
using Guard = Number::Guard;
constexpr Number zero = Number{};
if (mantissa == 0 || (mantissa < minMantissa && exponent <= minExponent))
if (mantissa_ == 0)
{
mantissa = zero.mantissa_;
exponent = zero.exponent_;
negative = false;
mantissa_ = zero.mantissa_;
exponent_ = zero.exponent_;
negative = zero.negative_;
return;
}
auto m = mantissa;
while ((m < minMantissa) && (exponent > minExponent))
auto m = mantissa_;
while ((m < minMantissa) && (exponent_ > minExponent))
{
m *= 10;
--exponent;
--exponent_;
}
Guard g;
if (negative)
g.set_negative();
while (m > maxMantissa)
{
if (exponent >= maxExponent)
if (exponent_ >= maxExponent)
throw std::overflow_error("Number::normalize 1");
g.push(m % 10);
m /= 10;
++exponent;
++exponent_;
}
if ((exponent < minExponent) || (m == 0))
if ((exponent_ < minExponent) || (m < minMantissa))
{
mantissa = zero.mantissa_;
exponent = zero.exponent_;
negative = false;
mantissa_ = zero.mantissa_;
exponent_ = zero.exponent_;
negative = zero.negative_;
return;
}
XRPL_ASSERT_PARTS(m <= maxMantissa, "xrpl::doNormalize", "intermediate mantissa fits in int64");
mantissa = m;
g.doRoundUp(negative, mantissa, exponent, minMantissa, maxMantissa, "Number::normalize 2");
// When using the largeRange, "m" needs fit within an int64, even if
// the final mantissa_ is going to end up larger to fit within the
// MantissaRange. Cut it down here so that the rounding will be done while
// it's smaller.
//
// Example: 9,900,000,000,000,123,456 > 9,223,372,036,854,775,807,
// so "m" will be modified to 990,000,000,000,012,345. Then that value
// will be rounded to 990,000,000,000,012,345 or
// 990,000,000,000,012,346, depending on the rounding mode. Finally,
// mantissa_ will be "m*10" so it fits within the range, and end up as
// 9,900,000,000,000,123,450 or 9,900,000,000,000,123,460.
// mantissa() will return mantissa_ / 10, and exponent() will return
// exponent_ + 1.
if (m > maxRep)
{
if (exponent_ >= maxExponent)
throw std::overflow_error("Number::normalize 1.5");
g.push(m % 10);
m /= 10;
++exponent_;
}
// Before modification, m should be within the min/max range. After
// modification, it must be less than maxRep. In other words, the original
// value should have been no more than maxRep * 10.
// (maxRep * 10 > maxMantissa)
XRPL_ASSERT_PARTS(m <= maxRep, "xrpl::doNormalize", "intermediate mantissa fits in int64");
mantissa_ = m;
g.doRoundUp(negative, mantissa_, exponent_, minMantissa, maxMantissa, "Number::normalize 2");
XRPL_ASSERT_PARTS(
mantissa >= minMantissa && mantissa <= maxMantissa,
mantissa_ >= minMantissa && mantissa_ <= maxMantissa,
"xrpl::doNormalize",
"final mantissa fits in range");
XRPL_ASSERT_PARTS(
exponent >= minExponent && exponent <= maxExponent,
"xrpl::doNormalize",
"final exponent fits in range");
}
template <>
@@ -568,20 +477,11 @@ Number::normalize<unsigned long>(
doNormalize(negative, mantissa, exponent, minMantissa, maxMantissa);
}
void
Number::normalize(MantissaRange const& range)
{
auto [negative, mantissa, exponent] = toInternal(range);
normalize(negative, mantissa, exponent, range.min, range.max);
fromInternal(negative, mantissa, exponent, &range);
}
void
Number::normalize()
{
normalize(range_);
auto const& range = range_.get();
normalize(negative_, mantissa_, exponent_, range.min, range.max);
}
// Copy the number, but set a new exponent. Because the mantissa doesn't change,
@@ -591,33 +491,21 @@ Number
Number::shiftExponent(int exponentDelta) const
{
XRPL_ASSERT_PARTS(isnormal(), "xrpl::Number::shiftExponent", "normalized");
Number result = *this;
result.exponent_ += exponentDelta;
if (result.exponent_ >= maxExponent)
auto const newExponent = exponent_ + exponentDelta;
if (newExponent >= maxExponent)
throw std::overflow_error("Number::shiftExponent");
if (result.exponent_ < minExponent)
if (newExponent < minExponent)
{
return Number{};
}
Number const result{negative_, mantissa_, newExponent, unchecked{}};
XRPL_ASSERT_PARTS(result.isnormal(), "xrpl::Number::shiftExponent", "result is normalized");
return result;
}
Number::Number(bool negative, internalrep mantissa, int exponent, normalized)
{
auto const& range = range_.get();
normalize(negative, mantissa, exponent, range.min, range.max);
fromInternal(negative, mantissa, exponent, &range);
}
Number&
Number::operator+=(Number const& y)
{
auto const& range = range_.get();
constexpr Number zero = Number{};
if (y == zero)
return *this;
@@ -632,8 +520,7 @@ Number::operator+=(Number const& y)
return *this;
}
XRPL_ASSERT(
isnormal(range) && y.isnormal(range), "xrpl::Number::operator+=(Number) : is normal");
XRPL_ASSERT(isnormal() && y.isnormal(), "xrpl::Number::operator+=(Number) : is normal");
// *n = negative
// *s = sign
// *m = mantissa
@@ -641,10 +528,13 @@ Number::operator+=(Number const& y)
// Need to use uint128_t, because large mantissas can overflow when added
// together.
auto [xn, xm, xe] = toInternal<uint128_t>(range);
auto [yn, ym, ye] = y.toInternal<uint128_t>(range);
bool xn = negative_;
uint128_t xm = mantissa_;
auto xe = exponent_;
bool yn = y.negative_;
uint128_t ym = y.mantissa_;
auto ye = y.exponent_;
Guard g;
if (xe < ye)
{
@@ -669,13 +559,14 @@ Number::operator+=(Number const& y)
} while (xe > ye);
}
auto const& range = range_.get();
auto const& minMantissa = range.min;
auto const& maxMantissa = range.max;
if (xn == yn)
{
xm += ym;
if (xm > maxMantissa)
if (xm > maxMantissa || xm > maxRep)
{
g.push(xm % 10);
xm /= 10;
@@ -695,7 +586,7 @@ Number::operator+=(Number const& y)
xe = ye;
xn = yn;
}
while (xm < minMantissa)
while (xm < minMantissa && xm * 10 <= maxRep)
{
xm *= 10;
xm -= g.pop();
@@ -704,8 +595,10 @@ Number::operator+=(Number const& y)
g.doRoundDown(xn, xm, xe, minMantissa);
}
normalize(xn, xm, xe, minMantissa, maxMantissa);
fromInternal(xn, xm, xe, &range);
negative_ = xn;
mantissa_ = static_cast<internalrep>(xm);
exponent_ = xe;
normalize();
return *this;
}
@@ -740,8 +633,6 @@ divu10(uint128_t& u)
Number&
Number::operator*=(Number const& y)
{
auto const& range = range_.get();
constexpr Number zero = Number{};
if (*this == zero)
return *this;
@@ -755,11 +646,15 @@ Number::operator*=(Number const& y)
// *m = mantissa
// *e = exponent
auto [xn, xm, xe] = toInternal(range);
bool xn = negative_;
int xs = xn ? -1 : 1;
internalrep xm = mantissa_;
auto xe = exponent_;
auto [yn, ym, ye] = y.toInternal(range);
bool yn = y.negative_;
int ys = yn ? -1 : 1;
internalrep ym = y.mantissa_;
auto ye = y.exponent_;
auto zm = uint128_t(xm) * uint128_t(ym);
auto ze = xe + ye;
@@ -769,10 +664,11 @@ Number::operator*=(Number const& y)
if (zn)
g.set_negative();
auto const& range = range_.get();
auto const& minMantissa = range.min;
auto const& maxMantissa = range.max;
while (zm > maxMantissa)
while (zm > maxMantissa || zm > maxRep)
{
// The following is optimization for:
// g.push(static_cast<unsigned>(zm % 10));
@@ -789,17 +685,17 @@ Number::operator*=(Number const& y)
minMantissa,
maxMantissa,
"Number::multiplication overflow : exponent is " + std::to_string(xe));
negative_ = zn;
mantissa_ = xm;
exponent_ = xe;
normalize(zn, xm, xe, minMantissa, maxMantissa);
fromInternal(zn, xm, xe, &range);
normalize();
return *this;
}
Number&
Number::operator/=(Number const& y)
{
auto const& range = range_.get();
constexpr Number zero = Number{};
if (y == zero)
throw std::overflow_error("Number: divide by 0");
@@ -812,12 +708,17 @@ Number::operator/=(Number const& y)
// *m = mantissa
// *e = exponent
auto [np, nm, ne] = toInternal(range);
bool np = negative_;
int ns = (np ? -1 : 1);
auto nm = mantissa_;
auto ne = exponent_;
auto [dp, dm, de] = y.toInternal(range);
bool dp = y.negative_;
int ds = (dp ? -1 : 1);
auto dm = y.mantissa_;
auto de = y.exponent_;
auto const& range = range_.get();
auto const& minMantissa = range.min;
auto const& maxMantissa = range.max;
@@ -829,7 +730,7 @@ Number::operator/=(Number const& y)
// f can be up to 10^(38-19) = 10^19 safely
static_assert(smallRange.log == 15);
static_assert(largeRange.log == 18);
bool small = range.scale == MantissaRange::small;
bool small = Number::getMantissaScale() == MantissaRange::small;
uint128_t const f = small ? 100'000'000'000'000'000 : 10'000'000'000'000'000'000ULL;
XRPL_ASSERT_PARTS(f >= minMantissa * 10, "Number::operator/=", "factor expected size");
@@ -879,8 +780,10 @@ Number::operator/=(Number const& y)
}
}
normalize(zn, zm, ze, minMantissa, maxMantissa);
fromInternal(zn, zm, ze, &range);
XRPL_ASSERT_PARTS(isnormal(range), "xrpl::Number::operator/=", "result is normalized");
negative_ = zn;
mantissa_ = static_cast<internalrep>(zm);
exponent_ = ze;
XRPL_ASSERT_PARTS(isnormal(), "xrpl::Number::operator/=", "result is normalized");
return *this;
}
@@ -893,10 +796,10 @@ operator rep() const
Guard g;
if (drops != 0)
{
if (drops < 0)
if (negative_)
{
g.set_negative();
drops = externalToInternal(drops);
drops = -drops;
}
for (; offset < 0; ++offset)
{
@@ -905,7 +808,7 @@ operator rep() const
}
for (; offset > 0; --offset)
{
if (drops >= largeRange.min)
if (drops > maxRep / 10)
throw std::overflow_error("Number::operator rep() overflow");
drops *= 10;
}
@@ -935,22 +838,19 @@ Number::truncate() const noexcept
std::string
to_string(Number const& amount)
{
auto const& range = Number::range_.get();
// keep full internal accuracy, but make more human friendly if possible
constexpr Number zero = Number{};
if (amount == zero)
return "0";
// The mantissa must have a set number of decimal places for this to work
auto [negative, mantissa, exponent] = amount.toInternal(range);
auto exponent = amount.exponent_;
auto mantissa = amount.mantissa_;
bool const negative = amount.negative_;
// Use scientific notation for exponents that are too small or too large
auto const rangeLog = range.log;
if (((exponent != 0 && amount.exponent() != 0) &&
((exponent < -(rangeLog + 10)) || (exponent > -(rangeLog - 10)))))
auto const rangeLog = Number::mantissaLog();
if (((exponent != 0) && ((exponent < -(rangeLog + 10)) || (exponent > -(rangeLog - 10)))))
{
// Remove trailing zeroes from the mantissa.
while (mantissa != 0 && mantissa % 10 == 0 && exponent < Number::maxExponent)
{
mantissa /= 10;
@@ -958,11 +858,8 @@ to_string(Number const& amount)
}
std::string ret = negative ? "-" : "";
ret.append(std::to_string(mantissa));
if (exponent != 0)
{
ret.append(1, 'e');
ret.append(std::to_string(exponent));
}
ret.append(1, 'e');
ret.append(std::to_string(exponent));
return ret;
}
@@ -1046,11 +943,20 @@ power(Number const& f, unsigned n)
return r;
}
// Returns f^(1/d)
// Uses NewtonRaphson iterations until the result stops changing
// to find the non-negative root of the polynomial g(x) = x^d - f
// This function, and power(Number f, unsigned n, unsigned d)
// treat corner cases such as 0 roots as advised by Annex F of
// the C standard, which itself is consistent with the IEEE
// floating point standards.
Number
Number::root(MantissaRange const& range, Number f, unsigned d)
root(Number f, unsigned d)
{
constexpr Number zero = Number{};
auto const one = Number::one(range);
auto const one = Number::one();
if (f == one || d == 1)
return f;
@@ -1067,28 +973,21 @@ Number::root(MantissaRange const& range, Number f, unsigned d)
if (f == zero)
return f;
auto const [e, di] = [&]() {
auto const [negative, mantissa, exponent] = f.toInternal(range);
// Scale f into the range (0, 1) such that the scale change (e) is a
// multiple of the root (d)
auto e = exponent + range.log + 1;
auto const di = static_cast<int>(d);
auto ex = [e = e, di = di]() // Euclidean remainder of e/d
{
int k = (e >= 0 ? e : e - (di - 1)) / di;
int k2 = e - k * di;
if (k2 == 0)
return 0;
return di - k2;
}();
e += ex;
f = f.shiftExponent(-e); // f /= 10^e;
return std::make_tuple(e, di);
// Scale f into the range (0, 1) such that f's exponent is a multiple of d
auto e = f.exponent_ + Number::mantissaLog() + 1;
auto const di = static_cast<int>(d);
auto ex = [e = e, di = di]() // Euclidean remainder of e/d
{
int k = (e >= 0 ? e : e - (di - 1)) / di;
int k2 = e - k * di;
if (k2 == 0)
return 0;
return di - k2;
}();
e += ex;
f = f.shiftExponent(-e); // f /= 10^e;
XRPL_ASSERT_PARTS(e % di == 0, "xrpl::root(Number, unsigned)", "e is divisible by d");
XRPL_ASSERT_PARTS(f.isnormal(range), "xrpl::root(Number, unsigned)", "f is normalized");
XRPL_ASSERT_PARTS(f.isnormal(), "xrpl::root(Number, unsigned)", "f is normalized");
bool neg = false;
if (f < zero)
{
@@ -1121,33 +1020,15 @@ Number::root(MantissaRange const& range, Number f, unsigned d)
// return r * 10^(e/d) to reverse scaling
auto const result = r.shiftExponent(e / di);
XRPL_ASSERT_PARTS(
result.isnormal(range), "xrpl::root(Number, unsigned)", "result is normalized");
XRPL_ASSERT_PARTS(result.isnormal(), "xrpl::root(Number, unsigned)", "result is normalized");
return result;
}
// Returns f^(1/d)
// Uses NewtonRaphson iterations until the result stops changing
// to find the non-negative root of the polynomial g(x) = x^d - f
// This function, and power(Number f, unsigned n, unsigned d)
// treat corner cases such as 0 roots as advised by Annex F of
// the C standard, which itself is consistent with the IEEE
// floating point standards.
Number
root(Number f, unsigned d)
{
auto const& range = Number::range_.get();
return Number::root(range, f, d);
}
Number
root2(Number f)
{
auto const& range = Number::range_.get();
constexpr Number zero = Number{};
auto const one = Number::one(range);
auto const one = Number::one();
if (f == one)
return f;
@@ -1156,18 +1037,12 @@ root2(Number f)
if (f == zero)
return f;
auto const e = [&]() {
auto const [negative, mantissa, exponent] = f.toInternal(range);
// Scale f into the range (0, 1) such that f's exponent is a
// multiple of d
auto e = exponent + range.log + 1;
if (e % 2 != 0)
++e;
f = f.shiftExponent(-e); // f /= 10^e;
return e;
}();
XRPL_ASSERT_PARTS(f.isnormal(range), "xrpl::root2(Number)", "f is normalized");
// Scale f into the range (0, 1) such that f's exponent is a multiple of d
auto e = f.exponent_ + Number::mantissaLog() + 1;
if (e % 2 != 0)
++e;
f = f.shiftExponent(-e); // f /= 10^e;
XRPL_ASSERT_PARTS(f.isnormal(), "xrpl::root2(Number)", "f is normalized");
// Quadratic least squares curve fit of f^(1/d) in the range [0, 1]
auto const D = 105;
@@ -1189,7 +1064,7 @@ root2(Number f)
// return r * 10^(e/2) to reverse scaling
auto const result = r.shiftExponent(e / 2);
XRPL_ASSERT_PARTS(result.isnormal(range), "xrpl::root2(Number)", "result is normalized");
XRPL_ASSERT_PARTS(result.isnormal(), "xrpl::root2(Number)", "result is normalized");
return result;
}
@@ -1199,10 +1074,8 @@ root2(Number f)
Number
power(Number const& f, unsigned n, unsigned d)
{
auto const& range = Number::range_.get();
constexpr Number zero = Number{};
auto const one = Number::one(range);
auto const one = Number::one();
if (f == one)
return f;
@@ -1224,7 +1097,7 @@ power(Number const& f, unsigned n, unsigned d)
d /= g;
if ((n % 2) == 1 && (d % 2) == 0 && f < zero)
throw std::overflow_error("Number::power nan");
return Number::root(range, power(f, n), d);
return root(power(f, n), d);
}
} // namespace xrpl

View File

@@ -32,10 +32,9 @@ public:
test_limits()
{
auto const scale = Number::getMantissaScale();
auto const minMantissa = Number::minMantissa();
testcase << "test_limits " << to_string(scale) << ", " << minMantissa;
testcase << "test_limits " << to_string(scale);
bool caught = false;
auto const minMantissa = Number::minMantissa();
try
{
Number x = Number{false, minMantissa * 10, 32768, Number::normalized{}};
@@ -59,9 +58,8 @@ public:
__LINE__);
test(Number{false, minMantissa, -32769, Number::normalized{}}, Number{}, __LINE__);
test(
// Use 1501 to force rounding up
Number{false, minMantissa, 32000, Number::normalized{}} * 1'000 +
Number{false, 1'501, 32000, Number::normalized{}},
Number{false, 1'500, 32000, Number::normalized{}},
Number{false, minMantissa + 2, 32003, Number::normalized{}},
__LINE__);
// 9,223,372,036,854,775,808
@@ -170,12 +168,8 @@ public:
{Number{true, 9'999'999'999'999'999'999ULL, -37, Number::normalized{}},
Number{1'000'000'000'000'000'000, -18},
Number{false, 9'999'999'999'999'999'990ULL, -19, Number::normalized{}}},
{Number{Number::largestMantissa},
Number{6, -1},
Number{Number::largestMantissa / 10, 1}},
{Number{Number::largestMantissa - 1},
Number{1, 0},
Number{Number::largestMantissa}},
{Number{Number::maxRep}, Number{6, -1}, Number{Number::maxRep / 10, 1}},
{Number{Number::maxRep - 1}, Number{1, 0}, Number{Number::maxRep}},
// Test extremes
{
// Each Number operand rounds up, so the actual mantissa is
@@ -185,18 +179,11 @@ public:
Number{2, 19},
},
{
// Does not round. Mantissas are going to be >
// largestMantissa, so if added together as uint64_t's, the
// result will overflow. With addition using uint128_t,
// there's no problem. After normalizing, the resulting
// mantissa ends up less than largestMantissa.
Number{false, Number::largestMantissa, 0, Number::normalized{}},
Number{false, Number::largestMantissa, 0, Number::normalized{}},
Number{false, Number::largestMantissa * 2, 0, Number::normalized{}},
},
{
// These mantissas round down, so adding them together won't
// have any consequences.
// Does not round. Mantissas are going to be > maxRep, so if
// added together as uint64_t's, the result will overflow.
// With addition using uint128_t, there's no problem. After
// normalizing, the resulting mantissa ends up less than
// maxRep.
Number{false, 9'999'999'999'999'999'990ULL, 0, Number::normalized{}},
Number{false, 9'999'999'999'999'999'990ULL, 0, Number::normalized{}},
Number{false, 1'999'999'999'999'999'998ULL, 1, Number::normalized{}},
@@ -285,16 +272,14 @@ public:
{Number{1'000'000'000'000'000'001, -18},
Number{1'000'000'000'000'000'000, -18},
Number{1'000'000'000'000'000'000, -36}},
{Number{Number::largestMantissa},
Number{6, -1},
Number{Number::largestMantissa - 1}},
{Number{false, Number::largestMantissa + 1, 0, Number::normalized{}},
{Number{Number::maxRep}, Number{6, -1}, Number{Number::maxRep - 1}},
{Number{false, Number::maxRep + 1, 0, Number::normalized{}},
Number{1, 0},
Number{Number::largestMantissa / 10 + 1, 1}},
{Number{false, Number::largestMantissa + 1, 0, Number::normalized{}},
Number{Number::maxRep / 10 + 1, 1}},
{Number{false, Number::maxRep + 1, 0, Number::normalized{}},
Number{3, 0},
Number{Number::largestMantissa}},
{power(2, 63), Number{3, 0}, Number{Number::largestMantissa}},
Number{Number::maxRep}},
{power(2, 63), Number{3, 0}, Number{Number::maxRep}},
});
auto test = [this](auto const& c) {
for (auto const& [x, y, z] : c)
@@ -317,15 +302,14 @@ public:
auto const scale = Number::getMantissaScale();
testcase << "test_mul " << to_string(scale);
// Case: Factor 1, Factor 2, Expected product, Line number
using Case = std::tuple<Number, Number, Number, int>;
using Case = std::tuple<Number, Number, Number>;
auto test = [this](auto const& c) {
for (auto const& [x, y, z, line] : c)
for (auto const& [x, y, z] : c)
{
auto const result = x * y;
std::stringstream ss;
ss << x << " * " << y << " = " << result << ". Expected: " << z;
BEAST_EXPECTS(result == z, ss.str() + " line: " + std::to_string(line));
BEAST_EXPECTS(result == z, ss.str());
}
};
auto tests = [&](auto const& cSmall, auto const& cLarge) {
@@ -335,100 +319,70 @@ public:
test(cLarge);
};
auto const maxMantissa = Number::maxMantissa();
auto const maxInternalMantissa = static_cast<std::uint64_t>(static_cast<std::int64_t>(
power(10, Number::mantissaLog()))) *
10 -
1;
saveNumberRoundMode save{Number::setround(Number::to_nearest)};
{
auto const cSmall = std::to_array<Case>({
{Number{7}, Number{8}, Number{56}, __LINE__},
{Number{7}, Number{8}, Number{56}},
{Number{1414213562373095, -15},
Number{1414213562373095, -15},
Number{2000000000000000, -15},
__LINE__},
Number{2000000000000000, -15}},
{Number{-1414213562373095, -15},
Number{1414213562373095, -15},
Number{-2000000000000000, -15},
__LINE__},
Number{-2000000000000000, -15}},
{Number{-1414213562373095, -15},
Number{-1414213562373095, -15},
Number{2000000000000000, -15},
__LINE__},
Number{2000000000000000, -15}},
{Number{3214285714285706, -15},
Number{3111111111111119, -15},
Number{1000000000000000, -14},
__LINE__},
{Number{1000000000000000, -32768},
Number{1000000000000000, -32768},
Number{0},
__LINE__},
Number{1000000000000000, -14}},
{Number{1000000000000000, -32768}, Number{1000000000000000, -32768}, Number{0}},
// Maximum mantissa range
{Number{9'999'999'999'999'999, 0},
Number{9'999'999'999'999'999, 0},
Number{9'999'999'999'999'998, 16},
__LINE__},
Number{9'999'999'999'999'998, 16}},
});
auto const cLarge = std::to_array<Case>({
// Note that items with extremely large mantissas need to be
// calculated, because otherwise they overflow uint64. Items
// from C with larger mantissa
{Number{7}, Number{8}, Number{56}, __LINE__},
{Number{7}, Number{8}, Number{56}},
{Number{1414213562373095, -15},
Number{1414213562373095, -15},
Number{1999999999999999862, -18},
__LINE__},
Number{1999999999999999862, -18}},
{Number{-1414213562373095, -15},
Number{1414213562373095, -15},
Number{-1999999999999999862, -18},
__LINE__},
Number{-1999999999999999862, -18}},
{Number{-1414213562373095, -15},
Number{-1414213562373095, -15},
Number{1999999999999999862, -18},
__LINE__},
Number{1999999999999999862, -18}},
{Number{3214285714285706, -15},
Number{3111111111111119, -15},
Number{false, 9'999'999'999'999'999'579ULL, -18, Number::normalized{}},
__LINE__},
Number{false, 9'999'999'999'999'999'579ULL, -18, Number::normalized{}}},
{Number{1000000000000000000, -32768},
Number{1000000000000000000, -32768},
Number{0},
__LINE__},
Number{0}},
// Items from cSmall expanded for the larger mantissa,
// except duplicates. Sadly, it looks like sqrt(2)^2 != 2
// with higher precision
{Number{1414213562373095049, -18},
Number{1414213562373095049, -18},
Number{2000000000000000001, -18},
__LINE__},
Number{2000000000000000001, -18}},
{Number{-1414213562373095048, -18},
Number{1414213562373095048, -18},
Number{-1999999999999999998, -18},
__LINE__},
Number{-1999999999999999998, -18}},
{Number{-1414213562373095048, -18},
Number{-1414213562373095049, -18},
Number{1999999999999999999, -18},
__LINE__},
{Number{3214285714285714278, -18},
Number{3111111111111111119, -18},
Number{10, 0},
__LINE__},
// Maximum internal mantissa range - rounds up to 1e19
{Number{false, maxInternalMantissa, 0, Number::normalized{}},
Number{false, maxInternalMantissa, 0, Number::normalized{}},
Number{1, 38},
__LINE__},
// Maximum actual mantissa range - same as int64 range
Number{1999999999999999999, -18}},
{Number{3214285714285714278, -18}, Number{3111111111111111119, -18}, Number{10, 0}},
// Maximum mantissa range - rounds up to 1e19
{Number{false, maxMantissa, 0, Number::normalized{}},
Number{false, maxMantissa, 0, Number::normalized{}},
Number{85'070'591'730'234'615'85, 19},
__LINE__},
Number{1, 38}},
// Maximum int64 range
{Number{Number::largestMantissa, 0},
Number{Number::largestMantissa, 0},
Number{85'070'591'730'234'615'85, 19},
__LINE__},
{Number{Number::maxRep, 0},
Number{Number::maxRep, 0},
Number{85'070'591'730'234'615'85, 19}},
});
tests(cSmall, cLarge);
}
@@ -436,90 +390,66 @@ public:
testcase << "test_mul " << to_string(Number::getMantissaScale()) << " towards_zero";
{
auto const cSmall = std::to_array<Case>(
{{Number{7}, Number{8}, Number{56}, __LINE__},
{{Number{7}, Number{8}, Number{56}},
{Number{1414213562373095, -15},
Number{1414213562373095, -15},
Number{1999999999999999, -15},
__LINE__},
Number{1999999999999999, -15}},
{Number{-1414213562373095, -15},
Number{1414213562373095, -15},
Number{-1999999999999999, -15},
__LINE__},
Number{-1999999999999999, -15}},
{Number{-1414213562373095, -15},
Number{-1414213562373095, -15},
Number{1999999999999999, -15},
__LINE__},
Number{1999999999999999, -15}},
{Number{3214285714285706, -15},
Number{3111111111111119, -15},
Number{9999999999999999, -15},
__LINE__},
{Number{1000000000000000, -32768},
Number{1000000000000000, -32768},
Number{0},
__LINE__}});
Number{9999999999999999, -15}},
{Number{1000000000000000, -32768}, Number{1000000000000000, -32768}, Number{0}}});
auto const cLarge = std::to_array<Case>(
// Note that items with extremely large mantissas need to be
// calculated, because otherwise they overflow uint64. Items
// from C with larger mantissa
{
{Number{7}, Number{8}, Number{56}, __LINE__},
{Number{7}, Number{8}, Number{56}},
{Number{1414213562373095, -15},
Number{1414213562373095, -15},
Number{1999999999999999861, -18},
__LINE__},
Number{1999999999999999861, -18}},
{Number{-1414213562373095, -15},
Number{1414213562373095, -15},
Number{-1999999999999999861, -18},
__LINE__},
Number{-1999999999999999861, -18}},
{Number{-1414213562373095, -15},
Number{-1414213562373095, -15},
Number{1999999999999999861, -18},
__LINE__},
Number{1999999999999999861, -18}},
{Number{3214285714285706, -15},
Number{3111111111111119, -15},
Number{false, 9999999999999999579ULL, -18, Number::normalized{}},
__LINE__},
Number{false, 9999999999999999579ULL, -18, Number::normalized{}}},
{Number{1000000000000000000, -32768},
Number{1000000000000000000, -32768},
Number{0},
__LINE__},
Number{0}},
// Items from cSmall expanded for the larger mantissa,
// except duplicates. Sadly, it looks like sqrt(2)^2 != 2
// with higher precision
{Number{1414213562373095049, -18},
Number{1414213562373095049, -18},
Number{2, 0},
__LINE__},
Number{2, 0}},
{Number{-1414213562373095048, -18},
Number{1414213562373095048, -18},
Number{-1999999999999999997, -18},
__LINE__},
Number{-1999999999999999997, -18}},
{Number{-1414213562373095048, -18},
Number{-1414213562373095049, -18},
Number{1999999999999999999, -18},
__LINE__},
Number{1999999999999999999, -18}},
{Number{3214285714285714278, -18},
Number{3111111111111111119, -18},
Number{10, 0},
__LINE__},
// Maximum internal mantissa range - rounds down to
// maxMantissa/10e1
Number{10, 0}},
// Maximum mantissa range - rounds down to maxMantissa/10e1
// 99'999'999'999'999'999'800'000'000'000'000'000'100
{Number{false, maxInternalMantissa, 0, Number::normalized{}},
Number{false, maxInternalMantissa, 0, Number::normalized{}},
Number{false, maxInternalMantissa / 10 - 1, 20, Number::normalized{}},
__LINE__},
// Maximum actual mantissa range - same as int64
{Number{false, maxMantissa, 0, Number::normalized{}},
Number{false, maxMantissa, 0, Number::normalized{}},
Number{85'070'591'730'234'615'84, 19},
__LINE__},
Number{false, maxMantissa / 10 - 1, 20, Number::normalized{}}},
// Maximum int64 range
// 85'070'591'730'234'615'847'396'907'784'232'501'249
{Number{Number::largestMantissa, 0},
Number{Number::largestMantissa, 0},
Number{85'070'591'730'234'615'84, 19},
__LINE__},
{Number{Number::maxRep, 0},
Number{Number::maxRep, 0},
Number{85'070'591'730'234'615'84, 19}},
});
tests(cSmall, cLarge);
}
@@ -527,90 +457,66 @@ public:
testcase << "test_mul " << to_string(Number::getMantissaScale()) << " downward";
{
auto const cSmall = std::to_array<Case>(
{{Number{7}, Number{8}, Number{56}, __LINE__},
{{Number{7}, Number{8}, Number{56}},
{Number{1414213562373095, -15},
Number{1414213562373095, -15},
Number{1999999999999999, -15},
__LINE__},
Number{1999999999999999, -15}},
{Number{-1414213562373095, -15},
Number{1414213562373095, -15},
Number{-2000000000000000, -15},
__LINE__},
Number{-2000000000000000, -15}},
{Number{-1414213562373095, -15},
Number{-1414213562373095, -15},
Number{1999999999999999, -15},
__LINE__},
Number{1999999999999999, -15}},
{Number{3214285714285706, -15},
Number{3111111111111119, -15},
Number{9999999999999999, -15},
__LINE__},
{Number{1000000000000000, -32768},
Number{1000000000000000, -32768},
Number{0},
__LINE__}});
Number{9999999999999999, -15}},
{Number{1000000000000000, -32768}, Number{1000000000000000, -32768}, Number{0}}});
auto const cLarge = std::to_array<Case>(
// Note that items with extremely large mantissas need to be
// calculated, because otherwise they overflow uint64. Items
// from C with larger mantissa
{
{Number{7}, Number{8}, Number{56}, __LINE__},
{Number{7}, Number{8}, Number{56}},
{Number{1414213562373095, -15},
Number{1414213562373095, -15},
Number{1999999999999999861, -18},
__LINE__},
Number{1999999999999999861, -18}},
{Number{-1414213562373095, -15},
Number{1414213562373095, -15},
Number{-1999999999999999862, -18},
__LINE__},
Number{-1999999999999999862, -18}},
{Number{-1414213562373095, -15},
Number{-1414213562373095, -15},
Number{1999999999999999861, -18},
__LINE__},
Number{1999999999999999861, -18}},
{Number{3214285714285706, -15},
Number{3111111111111119, -15},
Number{false, 9'999'999'999'999'999'579ULL, -18, Number::normalized{}},
__LINE__},
Number{false, 9'999'999'999'999'999'579ULL, -18, Number::normalized{}}},
{Number{1000000000000000000, -32768},
Number{1000000000000000000, -32768},
Number{0},
__LINE__},
Number{0}},
// Items from cSmall expanded for the larger mantissa,
// except duplicates. Sadly, it looks like sqrt(2)^2 != 2
// with higher precision
{Number{1414213562373095049, -18},
Number{1414213562373095049, -18},
Number{2, 0},
__LINE__},
Number{2, 0}},
{Number{-1414213562373095048, -18},
Number{1414213562373095048, -18},
Number{-1999999999999999998, -18},
__LINE__},
Number{-1999999999999999998, -18}},
{Number{-1414213562373095048, -18},
Number{-1414213562373095049, -18},
Number{1999999999999999999, -18},
__LINE__},
Number{1999999999999999999, -18}},
{Number{3214285714285714278, -18},
Number{3111111111111111119, -18},
Number{10, 0},
__LINE__},
// Maximum internal mantissa range - rounds down to
// maxMantissa/10-1
Number{10, 0}},
// Maximum mantissa range - rounds down to maxMantissa/10e1
// 99'999'999'999'999'999'800'000'000'000'000'000'100
{Number{false, maxInternalMantissa, 0, Number::normalized{}},
Number{false, maxInternalMantissa, 0, Number::normalized{}},
Number{false, maxInternalMantissa / 10 - 1, 20, Number::normalized{}},
__LINE__},
// Maximum mantissa range - same as int64
{Number{false, maxMantissa, 0, Number::normalized{}},
Number{false, maxMantissa, 0, Number::normalized{}},
Number{85'070'591'730'234'615'84, 19},
__LINE__},
Number{false, maxMantissa / 10 - 1, 20, Number::normalized{}}},
// Maximum int64 range
// 85'070'591'730'234'615'847'396'907'784'232'501'249
{Number{Number::largestMantissa, 0},
Number{Number::largestMantissa, 0},
Number{85'070'591'730'234'615'84, 19},
__LINE__},
{Number{Number::maxRep, 0},
Number{Number::maxRep, 0},
Number{85'070'591'730'234'615'84, 19}},
});
tests(cSmall, cLarge);
}
@@ -618,89 +524,66 @@ public:
testcase << "test_mul " << to_string(Number::getMantissaScale()) << " upward";
{
auto const cSmall = std::to_array<Case>(
{{Number{7}, Number{8}, Number{56}, __LINE__},
{{Number{7}, Number{8}, Number{56}},
{Number{1414213562373095, -15},
Number{1414213562373095, -15},
Number{2000000000000000, -15},
__LINE__},
Number{2000000000000000, -15}},
{Number{-1414213562373095, -15},
Number{1414213562373095, -15},
Number{-1999999999999999, -15},
__LINE__},
Number{-1999999999999999, -15}},
{Number{-1414213562373095, -15},
Number{-1414213562373095, -15},
Number{2000000000000000, -15},
__LINE__},
Number{2000000000000000, -15}},
{Number{3214285714285706, -15},
Number{3111111111111119, -15},
Number{1000000000000000, -14},
__LINE__},
{Number{1000000000000000, -32768},
Number{1000000000000000, -32768},
Number{0},
__LINE__}});
Number{1000000000000000, -14}},
{Number{1000000000000000, -32768}, Number{1000000000000000, -32768}, Number{0}}});
auto const cLarge = std::to_array<Case>(
// Note that items with extremely large mantissas need to be
// calculated, because otherwise they overflow uint64. Items
// from C with larger mantissa
{
{Number{7}, Number{8}, Number{56}, __LINE__},
{Number{7}, Number{8}, Number{56}},
{Number{1414213562373095, -15},
Number{1414213562373095, -15},
Number{1999999999999999862, -18},
__LINE__},
Number{1999999999999999862, -18}},
{Number{-1414213562373095, -15},
Number{1414213562373095, -15},
Number{-1999999999999999861, -18},
__LINE__},
Number{-1999999999999999861, -18}},
{Number{-1414213562373095, -15},
Number{-1414213562373095, -15},
Number{1999999999999999862, -18},
__LINE__},
Number{1999999999999999862, -18}},
{Number{3214285714285706, -15},
Number{3111111111111119, -15},
Number{999999999999999958, -17},
__LINE__},
Number{999999999999999958, -17}},
{Number{1000000000000000000, -32768},
Number{1000000000000000000, -32768},
Number{0},
__LINE__},
Number{0}},
// Items from cSmall expanded for the larger mantissa,
// except duplicates. Sadly, it looks like sqrt(2)^2 != 2
// with higher precision
{Number{1414213562373095049, -18},
Number{1414213562373095049, -18},
Number{2000000000000000001, -18},
__LINE__},
Number{2000000000000000001, -18}},
{Number{-1414213562373095048, -18},
Number{1414213562373095048, -18},
Number{-1999999999999999997, -18},
__LINE__},
Number{-1999999999999999997, -18}},
{Number{-1414213562373095048, -18},
Number{-1414213562373095049, -18},
Number{2, 0},
__LINE__},
Number{2, 0}},
{Number{3214285714285714278, -18},
Number{3111111111111111119, -18},
Number{1000000000000000001, -17},
__LINE__},
// Maximum internal mantissa range - rounds up to
// minMantissa*10 1e19*1e19=1e38
{Number{false, maxInternalMantissa, 0, Number::normalized{}},
Number{false, maxInternalMantissa, 0, Number::normalized{}},
Number{1, 38},
__LINE__},
// Maximum mantissa range - same as int64
Number{1000000000000000001, -17}},
// Maximum mantissa range - rounds up to minMantissa*10
// 1e19*1e19=1e38
{Number{false, maxMantissa, 0, Number::normalized{}},
Number{false, maxMantissa, 0, Number::normalized{}},
Number{85'070'591'730'234'615'85, 19},
__LINE__},
Number{1, 38}},
// Maximum int64 range
// 85'070'591'730'234'615'847'396'907'784'232'501'249
{Number{Number::largestMantissa, 0},
Number{Number::largestMantissa, 0},
Number{85'070'591'730'234'615'85, 19},
__LINE__},
{Number{Number::maxRep, 0},
Number{Number::maxRep, 0},
Number{85'070'591'730'234'615'85, 19}},
});
tests(cSmall, cLarge);
}
@@ -931,11 +814,6 @@ public:
};
*/
auto const maxInternalMantissa = static_cast<std::uint64_t>(static_cast<std::int64_t>(
power(10, Number::mantissaLog()))) *
10 -
1;
auto const cSmall = std::to_array<Case>(
{{Number{2}, 2, Number{1414213562373095049, -18}},
{Number{2'000'000}, 2, Number{1414213562373095049, -15}},
@@ -947,16 +825,16 @@ public:
{Number{0}, 5, Number{0}},
{Number{5625, -4}, 2, Number{75, -2}}});
auto const cLarge = std::to_array<Case>({
{Number{false, maxInternalMantissa - 9, -1, Number::normalized{}},
{Number{false, Number::maxMantissa() - 9, -1, Number::normalized{}},
2,
Number{false, 999'999'999'999'999'999, -9, Number::normalized{}}},
{Number{false, maxInternalMantissa - 9, 0, Number::normalized{}},
{Number{false, Number::maxMantissa() - 9, 0, Number::normalized{}},
2,
Number{false, 3'162'277'660'168'379'330, -9, Number::normalized{}}},
{Number{Number::largestMantissa},
{Number{Number::maxRep},
2,
Number{false, 3'037'000'499'976049692, -9, Number::normalized{}}},
{Number{Number::largestMantissa},
{Number{Number::maxRep},
4,
Number{false, 55'108'98747006743627, -14, Number::normalized{}}},
});
@@ -1005,8 +883,6 @@ public:
}
};
auto const maxInternalMantissa = power(10, Number::mantissaLog()) * 10 - 1;
auto const cSmall = std::to_array<Number>({
Number{2},
Number{2'000'000},
@@ -1016,10 +892,7 @@ public:
Number{5, -1},
Number{0},
Number{5625, -4},
Number{Number::largestMantissa},
maxInternalMantissa,
Number{Number::minMantissa(), 0, Number::unchecked{}},
Number{Number::maxMantissa(), 0, Number::unchecked{}},
Number{Number::maxRep},
});
test(cSmall);
bool caught = false;
@@ -1370,18 +1243,18 @@ public:
case MantissaRange::large:
// Test the edges
// ((exponent < -(28)) || (exponent > -(8)))))
test(Number::min(), "922337203685477581e-32768");
test(Number::min(), "1e-32750");
test(Number::max(), "9223372036854775807e32768");
test(Number::lowest(), "-9223372036854775807e32768");
{
NumberRoundModeGuard mg(Number::towards_zero);
auto const maxMantissa = Number::maxMantissa();
BEAST_EXPECT(maxMantissa == 9'223'372'036'854'775'807ULL);
BEAST_EXPECT(maxMantissa == 9'999'999'999'999'999'999ULL);
test(
Number{false, maxMantissa, 0, Number::normalized{}}, "9223372036854775807");
Number{false, maxMantissa, 0, Number::normalized{}}, "9999999999999999990");
test(
Number{true, maxMantissa, 0, Number::normalized{}}, "-9223372036854775807");
Number{true, maxMantissa, 0, Number::normalized{}}, "-9999999999999999990");
test(
Number{std::numeric_limits<std::int64_t>::max(), 0}, "9223372036854775807");
@@ -1617,7 +1490,7 @@ public:
Number const initalXrp{INITIAL_XRP};
BEAST_EXPECT(initalXrp.exponent() > 0);
Number const maxInt64{Number::largestMantissa};
Number const maxInt64{Number::maxRep};
BEAST_EXPECT(maxInt64.exponent() > 0);
// 85'070'591'730'234'615'865'843'651'857'942'052'864 - 38 digits
BEAST_EXPECT((power(maxInt64, 2) == Number{85'070'591'730'234'62, 22}));
@@ -1634,217 +1507,21 @@ public:
Number const initalXrp{INITIAL_XRP};
BEAST_EXPECT(initalXrp.exponent() <= 0);
Number const maxInt64{Number::largestMantissa};
Number const maxInt64{Number::maxRep};
BEAST_EXPECT(maxInt64.exponent() <= 0);
// 85'070'591'730'234'615'847'396'907'784'232'501'249 - 38 digits
BEAST_EXPECT((power(maxInt64, 2) == Number{85'070'591'730'234'615'85, 19}));
NumberRoundModeGuard mg(Number::towards_zero);
{
auto const maxInternalMantissa =
static_cast<std::uint64_t>(
static_cast<std::int64_t>(power(10, Number::mantissaLog()))) *
10 -
1;
// Rounds down to fit under 2^63
Number const max = Number{false, maxInternalMantissa, 0, Number::normalized{}};
// No alterations by the accessors
BEAST_EXPECT(max.mantissa() == maxInternalMantissa / 10);
BEAST_EXPECT(max.exponent() == 1);
// 99'999'999'999'999'999'800'000'000'000'000'000'100 - also 38
// digits
BEAST_EXPECT(
(power(max, 2) ==
Number{false, maxInternalMantissa / 10 - 1, 20, Number::normalized{}}));
}
{
auto const maxMantissa = Number::maxMantissa();
Number const max = Number{false, maxMantissa, 0, Number::normalized{}};
// No alterations by the accessors
BEAST_EXPECT(max.mantissa() == maxMantissa);
BEAST_EXPECT(max.exponent() == 0);
// 85'070'591'730'234'615'847'396'907'784'232'501'249 - also 38
// digits
BEAST_EXPECT(
(power(max, 2) ==
Number{false, 85'070'591'730'234'615'84, 19, Number::normalized{}}));
}
}
}
void
testNormalizeToRange()
{
// Test edge-cases of normalizeToRange
auto const scale = Number::getMantissaScale();
testcase << "normalizeToRange " << to_string(scale);
auto test = [this](
Number const& n,
auto const rangeMin,
auto const rangeMax,
auto const expectedMantissa,
auto const expectedExponent,
auto const line) {
auto const normalized = n.normalizeToRange(rangeMin, rangeMax);
BEAST_EXPECTS(
normalized.first == expectedMantissa,
"Number " + to_string(n) + " scaled to " + std::to_string(rangeMax) +
". Expected mantissa:" + std::to_string(expectedMantissa) +
", got: " + std::to_string(normalized.first) + " @ " + std::to_string(line));
BEAST_EXPECTS(
normalized.second == expectedExponent,
"Number " + to_string(n) + " scaled to " + std::to_string(rangeMax) +
". Expected exponent:" + std::to_string(expectedExponent) +
", got: " + std::to_string(normalized.second) + " @ " + std::to_string(line));
};
std::int64_t constexpr iRangeMin = 100;
std::int64_t constexpr iRangeMax = 999;
std::uint64_t constexpr uRangeMin = 100;
std::uint64_t constexpr uRangeMax = 999;
constexpr static MantissaRange largeRange{MantissaRange::large};
std::int64_t constexpr iBigMin = largeRange.min;
std::int64_t constexpr iBigMax = largeRange.max;
auto const testSuite = [&](Number const& n,
auto const expectedSmallMantissa,
auto const expectedSmallExponent,
auto const expectedLargeMantissa,
auto const expectedLargeExponent,
auto const line) {
test(n, iRangeMin, iRangeMax, expectedSmallMantissa, expectedSmallExponent, line);
test(n, iBigMin, iBigMax, expectedLargeMantissa, expectedLargeExponent, line);
// Only test non-negative. testing a negative number with an
// unsigned range will assert, and asserts can't be tested.
if (n.signum() >= 0)
{
test(n, uRangeMin, uRangeMax, expectedSmallMantissa, expectedSmallExponent, line);
test(
n,
largeRange.min,
largeRange.max,
expectedLargeMantissa,
expectedLargeExponent,
line);
}
};
{
// zero
Number const n{0};
testSuite(
n,
0,
std::numeric_limits<int>::lowest(),
0,
std::numeric_limits<int>::lowest(),
__LINE__);
}
{
// Small positive number
Number const n{2};
testSuite(n, 200, -2, 2'000'000'000'000'000'000, -18, __LINE__);
}
{
// Negative number
Number const n{-2};
testSuite(n, -200, -2, -2'000'000'000'000'000'000, -18, __LINE__);
}
{
// Biggest valid mantissa
Number const n{Number::largestMantissa, 0, Number::normalized{}};
if (scale == MantissaRange::small)
// With the small mantissa range, the value rounds up. Because
// it rounds up, when scaling up to the full int64 range, it
// can't go over the max, so it is one digit smaller than the
// full value.
testSuite(n, 922, 16, 922'337'203'685'477'600, 1, __LINE__);
else
testSuite(n, 922, 16, Number::largestMantissa, 0, __LINE__);
}
{
// Biggest valid mantissa + 1
Number const n{Number::largestMantissa + 1, 0, Number::normalized{}};
if (scale == MantissaRange::small)
// With the small mantissa range, the value rounds up. Because
// it rounds up, when scaling up to the full int64 range, it
// can't go over the max, so it is one digit smaller than the
// full value.
testSuite(n, 922, 16, 922'337'203'685'477'600, 1, __LINE__);
else
testSuite(n, 922, 16, 922'337'203'685'477'581, 1, __LINE__);
}
{
// Biggest valid mantissa + 2
Number const n{Number::largestMantissa + 2, 0, Number::normalized{}};
if (scale == MantissaRange::small)
// With the small mantissa range, the value rounds up. Because
// it rounds up, when scaling up to the full int64 range, it
// can't go over the max, so it is one digit smaller than the
// full value.
testSuite(n, 922, 16, 922'337'203'685'477'600, 1, __LINE__);
else
testSuite(n, 922, 16, 922'337'203'685'477'581, 1, __LINE__);
}
{
// Biggest valid mantissa + 3
Number const n{Number::largestMantissa + 3, 0, Number::normalized{}};
if (scale == MantissaRange::small)
// With the small mantissa range, the value rounds up. Because
// it rounds up, when scaling up to the full int64 range, it
// can't go over the max, so it is one digit smaller than the
// full value.
testSuite(n, 922, 16, 922'337'203'685'477'600, 1, __LINE__);
else
testSuite(n, 922, 16, 922'337'203'685'477'581, 1, __LINE__);
}
{
// int64 min
Number const n{std::numeric_limits<std::int64_t>::min(), 0};
if (scale == MantissaRange::small)
testSuite(n, -922, 16, -922'337'203'685'477'600, 1, __LINE__);
else
testSuite(n, -922, 16, -922'337'203'685'477'581, 1, __LINE__);
}
{
// int64 min + 1
Number const n{std::numeric_limits<std::int64_t>::min() + 1, 0};
if (scale == MantissaRange::small)
testSuite(n, -922, 16, -922'337'203'685'477'600, 1, __LINE__);
else
testSuite(n, -922, 16, -9'223'372'036'854'775'807, 0, __LINE__);
}
{
// int64 min - 1
// Need to cast to uint, even though we're dealing with a negative
// number to avoid overflow and UB
Number const n{
true,
-static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::min()) + 1,
0,
Number::normalized{}};
if (scale == MantissaRange::small)
testSuite(n, -922, 16, -922'337'203'685'477'600, 1, __LINE__);
else
testSuite(n, -922, 16, -922'337'203'685'477'581, 1, __LINE__);
auto const maxMantissa = Number::maxMantissa();
Number const max = Number{false, maxMantissa, 0, Number::normalized{}};
BEAST_EXPECT(max.mantissa() == maxMantissa / 10);
BEAST_EXPECT(max.exponent() == 1);
// 99'999'999'999'999'999'800'000'000'000'000'000'100 - also 38
// digits
BEAST_EXPECT(
(power(max, 2) == Number{false, maxMantissa / 10 - 1, 20, Number::normalized{}}));
}
}
@@ -1875,7 +1552,6 @@ public:
test_truncate();
testRounding();
testInt64();
testNormalizeToRange();
}
}
};

View File

@@ -129,7 +129,11 @@ ValidatorSite::load(
{
try
{
sites_.emplace_back(uri);
// This is not super efficient, but it doesn't happen often.
bool found = std::ranges::any_of(
sites_, [&uri](auto const& site) { return site.loadedResource->uri == uri; });
if (!found)
sites_.emplace_back(uri);
}
catch (std::exception const& e)
{
@@ -190,6 +194,16 @@ ValidatorSite::setTimer(
std::lock_guard<std::mutex> const& site_lock,
std::lock_guard<std::mutex> const& state_lock)
{
if (!sites_.empty() && //
std::ranges::all_of(
sites_, [](auto const& site) { return site.lastRefreshStatus.has_value(); }))
{
// If all of the sites have been handled at least once (including
// errors and timeouts), call missingSite, which will load the cache
// files for any lists that are still unavailable.
missingSite(site_lock);
}
auto next = std::min_element(sites_.begin(), sites_.end(), [](Site const& a, Site const& b) {
return a.nextRefresh < b.nextRefresh;
});
@@ -299,12 +313,15 @@ ValidatorSite::onRequestTimeout(std::size_t siteIdx, error_code const& ec)
// processes a network error. Usually, this function runs first,
// but on extremely rare occasions, the response handler can run
// first, which will leave activeResource empty.
auto const& site = sites_[siteIdx];
auto& site = sites_[siteIdx];
if (site.activeResource)
JLOG(j_.warn()) << "Request for " << site.activeResource->uri << " took too long";
else
JLOG(j_.error()) << "Request took too long, but a response has "
"already been processed";
if (!site.lastRefreshStatus)
site.lastRefreshStatus.emplace(
Site::Status{clock_type::now(), ListDisposition::invalid, "timeout"});
}
std::lock_guard lock_state{state_mutex_};