.. _program_listing_file_src_rdf4cpp_BigDecimal.hpp: Program Listing for File BigDecimal.hpp ======================================= |exhale_lsh| :ref:`Return to documentation for file ` (``src/rdf4cpp/BigDecimal.hpp``) .. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS .. code-block:: cpp #ifndef RDF4CPP_BIGDECIMAL_H #define RDF4CPP_BIGDECIMAL_H #include #include #include #include #include #include #include #include #include namespace rdf4cpp { enum struct RoundingMode { Floor, Ceil, Round, Trunc, }; enum struct DecimalError { Overflow, NotDefined, // aka NotANumber }; template concept BigDecimalBaseType = std::numeric_limits::is_specialized && !std::floating_point; template requires(!std::signed_integral && !std::unsigned_integral) struct BigDecimal { // the entire class is loosely based on OpenJDKs BigDecimal: https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/math/BigDecimal.java private: UnscaledValue_t unscaled_value; Exponent_t exponent; static constexpr uint32_t base = 10; enum struct OverflowMode { Checked, UndefinedBehavior, }; template static constexpr bool add_checked(const T &a, const T &b, T &result) noexcept { if constexpr (std::is_integral_v && m == OverflowMode::Checked) { return __builtin_add_overflow(a, b, &result); } else { result = a + b; return false; } } template static constexpr bool sub_checked(const T &a, const T &b, T &result) noexcept { if constexpr (std::is_integral_v && m == OverflowMode::Checked) { return __builtin_sub_overflow(a, b, &result); } else { result = a - b; return false; } } template static constexpr bool mul_checked(const T &a, const T &b, T &result) noexcept { if constexpr (std::is_integral_v && m == OverflowMode::Checked) { return __builtin_mul_overflow(a, b, &result); } else { result = a * b; return false; } } template static constexpr bool pow_checked(const T &a, unsigned int b, T &result) noexcept { if constexpr (std::is_integral_v) { T r = 1; bool over = false; for (unsigned int i = 0; i < b; ++i) over |= mul_checked(r, a, r); result = r; return over; } else { result = boost::multiprecision::pow(a, b); return false; } } template static constexpr bool cast_checked(const From &f, To &result) noexcept { if constexpr (std::is_integral_v && std::is_integral_v && m == OverflowMode::Checked) { if (!std::in_range(f)) return true; } result = static_cast(f); return false; } static constexpr UnscaledValue_t abs(const UnscaledValue_t &value) noexcept { if constexpr (std::is_integral_v && !std::is_signed_v) { return value; } else { return value < 0 ? -value : value; } } public: constexpr BigDecimal() noexcept : BigDecimal{0, 0} { } constexpr BigDecimal(const UnscaledValue_t &unscaled_value, Exponent_t exponent) noexcept : unscaled_value(unscaled_value), exponent(exponent) {} constexpr explicit BigDecimal(std::string_view value) : unscaled_value(0), exponent(0) { bool begin = true; bool decimal = false; bool neg = false; for (const char c : value) { if (begin) { begin = false; if (c == '-') { neg = true; continue; } else if (c == '+') { continue; } } if (c == '.') { if (decimal) { throw InvalidNode{"http://www.w3.org/2001/XMLSchema#decimal parsing error: more than one . found"}; } decimal = true; continue; } if (c < '0' || c > '9') { throw InvalidNode{"http://www.w3.org/2001/XMLSchema#decimal parsing error: non-numeric char found"}; } auto n = c - '0'; if (mul_checked(unscaled_value, UnscaledValue_t{base}, unscaled_value)) { throw InvalidNode{"http://www.w3.org/2001/XMLSchema#decimal parsing error: unscaled_value overflow"}; } if (add_checked(unscaled_value, UnscaledValue_t{n}, unscaled_value)) { throw InvalidNode{"http://www.w3.org/2001/XMLSchema#decimal parsing error: unscaled_value overflow"}; } if (decimal) { if (add_checked(exponent, Exponent_t{1}, exponent)) { throw InvalidNode{"http://www.w3.org/2001/XMLSchema#decimal parsing error: exponent overflow"}; } } } if (unscaled_value == 0) { neg = false; } if (neg) { unscaled_value = -unscaled_value; } } constexpr explicit BigDecimal(uint32_t value) noexcept : BigDecimal(UnscaledValue_t{value}, 0) {} constexpr explicit BigDecimal(uint64_t value) noexcept : BigDecimal(UnscaledValue_t{value}, 0) {} constexpr explicit BigDecimal(int32_t value) noexcept : BigDecimal(static_cast(value), 0) {} constexpr explicit BigDecimal(int64_t value) noexcept : BigDecimal(static_cast(value), 0) {} constexpr explicit BigDecimal(const UnscaledValue_t &value) noexcept requires(!std::is_same_v && !std::is_same_v) : BigDecimal(value, 0) {} constexpr explicit BigDecimal(float value) : BigDecimal(static_cast(value)) {} explicit BigDecimal(double value) : unscaled_value(0), exponent(0) { // most of the algorithm is from OpenJDK: https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/19fb8f93c59dfd791f62d41f332db9e306bc1422/src/java.base/share/classes/java/math/BigDecimal.java#L915 if (std::isinf(value) || std::isnan(value)) throw std::invalid_argument{"value is NaN or infinity"}; // this might fail on anything that is not x86-32/64 static_assert(std::endian::native == std::endian::little, "BigDecimal{double} is only tested on x86-32/64 and might not work on other systems"); // double is an IEEE 754 64-bit floating point value // memory layout: // sign | exponent | fraction // 63 | 62 ... 52 | 51 ... 0 // see https://en.wikipedia.org/wiki/Double-precision_floating-point_format for more info (and a better graphic) auto v = std::bit_cast(value); bool neg = (v >> 63) != 0; auto ex = static_cast((v >> 52) & 0x7ffL); uint64_t significand = ex == 0 ? (v & ((1L << 52) - 1)) << 1 : (v & ((1L << 52) - 1)) | (1L << 52); ex -= 1075; if (significand == 0) { return; } while (significand & 1) { significand >>= 1; ++ex; } static constexpr const char *exc = "double to BigDecimal overflow"; if (ex == 0) { unscaled_value = UnscaledValue_t{significand}; } else if (ex < 0) { exponent = static_cast(-ex); UnscaledValue_t e{0}; if (pow_checked(UnscaledValue_t{5}, -ex, e)) throw std::overflow_error{exc}; if (mul_checked(UnscaledValue_t{significand}, e, unscaled_value)) throw std::overflow_error{exc}; } else { UnscaledValue_t e{0}; if (pow_checked(UnscaledValue_t{2}, ex, e)) throw std::overflow_error{exc}; if (mul_checked(UnscaledValue_t{significand}, e, unscaled_value)) throw std::overflow_error{exc}; } if (neg) unscaled_value = -unscaled_value; normalize(); } constexpr void normalize() noexcept { normalize(unscaled_value, exponent); } static constexpr void normalize(UnscaledValue_t &unscaled_value, Exponent_t &exponent) noexcept { while (exponent > 0 && unscaled_value % base == 0) { unscaled_value /= base; --exponent; } } [[nodiscard]] constexpr Exponent_t get_exponent() const noexcept { return exponent; } [[nodiscard]] constexpr UnscaledValue_t get_unscaled_value() const noexcept { return unscaled_value; } [[nodiscard]] constexpr bool positive() const noexcept { return unscaled_value >= 0; } private: // op_checked has to be add_checked or sub_checked with the same OverflowMode template constexpr bool add_or_sub(const BigDecimal &other, BigDecimal &result) const noexcept { UnscaledValue_t t = this->unscaled_value; UnscaledValue_t o = other.unscaled_value; Exponent_t new_exp = std::max(this->exponent, other.exponent); if (this->exponent < new_exp) { UnscaledValue_t ex{0}; if (pow_checked(UnscaledValue_t{base}, new_exp - this->exponent, ex)) return true; if (mul_checked(t, ex, t)) return true; } else if (other.exponent < new_exp) { UnscaledValue_t ex{0}; if (pow_checked(UnscaledValue_t{base}, new_exp - other.exponent, ex)) return true; if (mul_checked(o, ex, o)) return true; } UnscaledValue_t res = 0; if (op_checked(t, o, res)) return true; result = BigDecimal{res, new_exp}; return false; } template constexpr bool mul(const BigDecimal &other, BigDecimal &result) const noexcept { UnscaledValue_t v{0}; if (mul_checked(this->unscaled_value, other.unscaled_value, v)) return true; Exponent_t e{0}; if (add_checked(this->exponent, other.exponent, e)) return true; result = BigDecimal{v, e}; return false; } constexpr static BigDecimal handle_rounding(UnscaledValue_t v, Exponent_t e, UnscaledValue_t rem, RoundingMode m) noexcept { switch (m) { case RoundingMode::Trunc: return BigDecimal{v, e}; case RoundingMode::Floor: if (v >= 0 || rem == 0) return BigDecimal{v, e}; else return BigDecimal{v - 1, e}; case RoundingMode::Ceil: if (v < 0 || rem == 0) return BigDecimal{v, e}; else return BigDecimal{v + 1, e}; case RoundingMode::Round: if (rem < 0) rem = -rem; if (v < 0) { if (rem >= 5) return BigDecimal{v - 1, e}; else return BigDecimal{v, e}; } else { if (rem >= 5) return BigDecimal{v + 1, e}; else return BigDecimal{v, e}; } default: RDF4CPP_UNREACHABLE; } } template constexpr bool div(const BigDecimal &other, Exponent_t max_scale_increase, RoundingMode mode, BigDecimal &result) const noexcept { if (this->unscaled_value == 0) { result = BigDecimal{0, 0}; return false; } UnscaledValue_t t = this->unscaled_value; Exponent_t ex = this->exponent; UnscaledValue_t div = other.unscaled_value; if (ex >= other.exponent) { if (sub_checked(ex, other.exponent, ex)) return true; } else { Exponent_t tmp{0}; if (sub_checked(other.exponent, ex, tmp)) return true; if (pow_checked(Exponent_t{base}, tmp, tmp)) return true; UnscaledValue_t tmp2{0}; if (cast_checked(tmp, tmp2)) return true; if (mul_checked(t, tmp2, t)) return true; ex = 0; } UnscaledValue_t res = t / div; UnscaledValue_t rem = t % div; while (rem != 0) { if (max_scale_increase == 0) { if (mul_checked(rem, UnscaledValue_t{base}, rem)) return true; result = handle_rounding(res, ex, rem / div, mode); return false; } if constexpr (std::is_integral_v) { if (ex == std::numeric_limits::max()) { if (mul_checked(rem, UnscaledValue_t{base}, rem)) return true; result = handle_rounding(res, ex, rem / div, mode); return false; } } ++ex; if (mul_checked(res, UnscaledValue_t{base}, res)) return true; if (mul_checked(rem, UnscaledValue_t{base}, rem)) return true; res += rem / div; rem = rem % div; --max_scale_increase; } result = BigDecimal{res, ex}; return false; } template constexpr bool pow(unsigned int n, BigDecimal &result) const noexcept { BigDecimal r{1}; for (unsigned int i = 0; i < n; ++i) { if (r.mul(*this, r)) return true; } result = r; return false; } static double cast_unscaled_to_double_safe(UnscaledValue_t const &value) noexcept { // There is a bug in boost versions <1.86.0 // that can cause a crash in the cast `static_cast(cpp_int)` // https://github.com/boostorg/multiprecision/issues/553 #if BOOST_VERSION < 108600 // workaround from https://github.com/scylladb/scylladb/commit/51d09e6a2a407ea9b9ad380ba30e5558a25bb8be#diff-81e6758bbedbe566a51706c5af1ea68be225c36feb68983c3de0a69138f01264R73 static auto const min = UnscaledValue_t{std::numeric_limits::lowest()}; static auto const max = UnscaledValue_t{std::numeric_limits::max()}; if (value < min) { return -std::numeric_limits::infinity(); } else if (value > max) { return std::numeric_limits::infinity(); } #endif // BOOST_VERSION return static_cast(value); } public: [[nodiscard]] constexpr BigDecimal operator-() const noexcept { return BigDecimal(-this->unscaled_value, this->exponent); } [[nodiscard]] constexpr nonstd::expected unary_minus_checked() const noexcept { if constexpr (std::is_integral_v) { if (std::numeric_limits::min() == unscaled_value) return nonstd::make_unexpected(DecimalError::Overflow); } return BigDecimal(-this->unscaled_value, this->exponent); } [[nodiscard]] constexpr BigDecimal operator+() const noexcept { return *this; } [[nodiscard]] constexpr BigDecimal operator+(const BigDecimal &other) const noexcept { BigDecimal res{0}; add_or_sub>(other, res); return res; } [[nodiscard]] constexpr nonstd::expected add_checked(const BigDecimal &other) const noexcept { BigDecimal res{0}; if (add_or_sub>(other, res)) return nonstd::make_unexpected(DecimalError::Overflow); return res; } constexpr BigDecimal &operator+=(const BigDecimal &other) noexcept { *this = *this + other; return *this; } [[nodiscard]] constexpr BigDecimal operator-(const BigDecimal &other) const noexcept { BigDecimal res{0}; add_or_sub>(other, res); return res; } [[nodiscard]] constexpr nonstd::expected sub_checked(const BigDecimal &other) const noexcept { BigDecimal res{0}; if (add_or_sub>(other, res)) return nonstd::make_unexpected(DecimalError::Overflow); return res; } constexpr BigDecimal operator-=(const BigDecimal &other) noexcept { *this = *this - other; return *this; } [[nodiscard]] constexpr BigDecimal operator*(const BigDecimal &other) const noexcept { BigDecimal res{0}; mul(other, res); return res; } [[nodiscard]] constexpr nonstd::expected mul_checked(const BigDecimal &other) const noexcept { BigDecimal res{0}; if (mul(other, res)) return nonstd::make_unexpected(DecimalError::Overflow); return res; } constexpr BigDecimal &operator*=(const BigDecimal &other) noexcept { *this = *this * other; return *this; } [[nodiscard]] constexpr BigDecimal operator/(const BigDecimal &other) const noexcept { return div(other, 1000); } [[nodiscard]] constexpr BigDecimal div(const BigDecimal &other, Exponent_t max_scale_increase, RoundingMode mode = RoundingMode::Floor) const noexcept { if (other.unscaled_value == 0) return BigDecimal{0, 0}; // undefined behavior (cpp_int throws) BigDecimal res{0}; div(other, max_scale_increase, mode, res); return res; } [[nodiscard]] constexpr nonstd::expected div_checked(const BigDecimal &other, Exponent_t max_scale_increase, RoundingMode mode = RoundingMode::Floor) const noexcept { if (other.unscaled_value == 0) return nonstd::make_unexpected(DecimalError::NotDefined); BigDecimal res{0}; if (div(other, max_scale_increase, mode, res)) return nonstd::make_unexpected(DecimalError::Overflow); return res; } constexpr BigDecimal &operator/=(const BigDecimal &other) noexcept { *this = *this / other; return *this; } [[nodiscard]] constexpr BigDecimal pow(unsigned int n) const noexcept { BigDecimal r{0}; pow(n, r); return r; } [[nodiscard]] constexpr nonstd::expected pow_checked(unsigned int n) const noexcept { BigDecimal r{0}; if (pow(n, r)) return nonstd::make_unexpected(DecimalError::Overflow); return r; } [[nodiscard]] constexpr BigDecimal round(RoundingMode mode) const noexcept { if (exponent == 0) return *this; UnscaledValue_t v{base}; if (pow_checked(v, exponent, v)) return BigDecimal{0, 0}; // base pow exponent overflows and this did not, we have to be close to 0 UnscaledValue_t rem = unscaled_value % v; rem = rem * 10 / v; v = unscaled_value / v; return handle_rounding(v, 0, rem, mode); } [[nodiscard]] constexpr BigDecimal abs() const noexcept { if (positive()) return *this; else return -*this; } [[nodiscard]] constexpr nonstd::expected abs_checked() const noexcept { if (positive()) return *this; else return this->unary_minus_checked(); } constexpr std::strong_ordering operator<=>(const BigDecimal &other) const noexcept { if (this->positive() != other.positive()) return this->positive() ? std::strong_ordering::greater : std::strong_ordering::less; UnscaledValue_t t = this->unscaled_value; UnscaledValue_t o = other.unscaled_value; if (this->exponent > other.exponent) { UnscaledValue_t b{base}; if (pow_checked(b, this->exponent - other.exponent, b)) return std::strong_ordering::less; // t does fit into the same precision, while o does not if (mul_checked(o, b, o)) return std::strong_ordering::less; // t does fit into the same precision, while o does not } else if (this->exponent < other.exponent) { UnscaledValue_t b{base}; if (pow_checked(b, other.exponent - this->exponent, b)) return std::strong_ordering::greater; // o does fit into the same precision, while t does not if (mul_checked(t, b, t)) return std::strong_ordering::greater; // o does fit into the same precision, while t does not } if (t < o) return std::strong_ordering::less; else if (t > o) return std::strong_ordering::greater; else return std::strong_ordering::equivalent; }; constexpr bool operator==(const BigDecimal &other) const noexcept { return *this <=> other == std::strong_ordering::equivalent; } friend bool operator==(const BigDecimal &t, int other) noexcept { return t == BigDecimal{other, 0}; } friend bool operator==(int t, const BigDecimal &other) noexcept { return other == t; } [[nodiscard]] explicit operator double() const noexcept { double const v = cast_unscaled_to_double_safe(unscaled_value) * std::pow(static_cast(base), -static_cast(exponent)); if (!std::isnan(v) && !std::isinf(v)) return v; // even Javas BigDecimal has no better solution auto const s = static_cast(*this); return std::stod(s); } [[nodiscard]] explicit operator float() const noexcept { return static_cast(static_cast(*this)); } [[nodiscard]] constexpr explicit operator UnscaledValue_t() const noexcept { if (exponent == 0) return unscaled_value; return round(RoundingMode::Trunc).unscaled_value; } [[nodiscard]] explicit operator std::string() const noexcept { if (unscaled_value == 0) return "0.0"; std::stringstream s{}; UnscaledValue_t v = unscaled_value; Exponent_t ex = exponent; bool hasDot = false; while (v != 0) { if (!hasDot && ex == 0) { if (s.view().empty()) s << '0'; s << '.'; hasDot = true; } else { --ex; } using namespace std; auto c = static_cast(abs(v % base)); if (hasDot || c != 0 || !s.view().empty()) // skip trailing 0s s << c; v /= base; } if (!hasDot) { for (Exponent_t i = 0; i < ex; ++i) s << '0'; s << ".0"; } if (!positive()) s << '-'; std::string_view sv = s.view(); return std::string{sv.rbegin(), sv.rend()}; } friend std::ostream &operator<<(std::ostream &str, const BigDecimal &bn) { auto s = static_cast(bn); str << s; return str; } template [[nodiscard]] size_t hash() const { BigDecimal n = *this; n.normalize(); return dice::hash::dice_hash_templates::dice_hash(std::tie(n.unscaled_value, n.exponent)); } }; template std::string to_string(const BigDecimal &r) noexcept { return static_cast(r); } template BigDecimal pow(const BigDecimal &r, unsigned int n) noexcept { return r.pow(n); } template BigDecimal round(const BigDecimal &r) noexcept { return r.round(RoundingMode::Round); } template BigDecimal floor(const BigDecimal &r) noexcept { return r.round(RoundingMode::Floor); } template BigDecimal ceil(const BigDecimal &r) noexcept { return r.round(RoundingMode::Ceil); } template BigDecimal trunc(const BigDecimal &r) noexcept { return r.round(RoundingMode::Trunc); } template BigDecimal abs(const BigDecimal &r) noexcept { return r.abs(); } } // namespace rdf4cpp #ifndef DOXYGEN_PARSER template struct std::hash> { size_t operator()(const rdf4cpp::BigDecimal &r) const { return r.hash(); } }; template struct dice::hash::dice_hash_overload { static size_t dice_hash(::boost::multiprecision::cpp_int const &x) noexcept { return dice::hash::dice_hash_templates::dice_hash(std::hash<::boost::multiprecision::cpp_int>{}(x)); } }; template struct dice::hash::dice_hash_overload> { static size_t dice_hash(rdf4cpp::BigDecimal const &x) noexcept { return x.template hash(); } }; #endif template class std::numeric_limits> { public: using BigDecimal = rdf4cpp::BigDecimal; static constexpr bool is_specialized = true; static constexpr bool is_signed = true; static constexpr bool is_integer = false; static constexpr bool is_exact = true; static constexpr bool has_infinity = false; static constexpr bool has_quiet_NaN = false; static constexpr bool has_signaling_NaN = false; static constexpr std::float_denorm_style has_denorm = std::denorm_absent; static constexpr bool has_denorm_loss = false; static constexpr std::float_round_style round_style = std::round_toward_zero; static constexpr bool is_iec559 = false; static constexpr bool is_bounded = true; static constexpr bool is_modulo = false; static constexpr int digits = numeric_limits::digits; static constexpr int digits10 = numeric_limits::digits10; static constexpr int max_digits10 = numeric_limits::max_digits10; static constexpr int radix = 2; static constexpr int min_exponent = 0; static constexpr int min_exponent10 = 0; static constexpr int max_exponent = 0; static constexpr int max_exponent10 = 0; static constexpr bool traps = false; static constexpr bool tinyness_before = false; static constexpr BigDecimal max() noexcept { return BigDecimal{numeric_limits::max(), 0}; } static constexpr BigDecimal min() noexcept { return BigDecimal{numeric_limits::min(), 0}; } static constexpr BigDecimal lowest() noexcept { return min(); } static constexpr BigDecimal epsilon() noexcept { return BigDecimal{1, numeric_limits::max()}; } static constexpr BigDecimal round_error() noexcept { return BigDecimal{0}; } static constexpr BigDecimal infinity() noexcept { return 0; } static constexpr BigDecimal quiet_NaN() noexcept { return 0; } static constexpr BigDecimal signaling_NaN() noexcept { return 0; } static constexpr BigDecimal denorm_min() noexcept { return 0; } }; #endif //RDF4CPP_BIGDECIMAL_H