feefrac.h

Go to the documentation of this file.

// Copyright (c) The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
#ifndef BITCOIN_UTIL_FEEFRAC_H
#define BITCOIN_UTIL_FEEFRAC_H
 
#include <util/check.h>
#include <util/overflow.h>
 
#include <compare>
#include <concepts>
#include <cstdint>
#include <span>
#include <utility>
 
struct FeeFrac
{
    static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
    {
        int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
        int64_t high = (a >> 32) * b;
        return {high + (low >> 32), static_cast<uint32_t>(low)};
    }
 
    static inline int64_t DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down) noexcept
    {
        Assume(d > 0);
        // Compute quot_high = n.first / d, so the result becomes
        // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
        // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
        int64_t quot_high = n.first / d;
        // Evaluate the parenthesized expression above, so the result becomes
        // n_low / d + (quot_high * 2**32)
        int64_t n_low = ((n.first % d) << 32) + n.second;
        // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible
        // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
        // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
        // correction.
        int64_t quot_low = n_low / d;
        int32_t mod_low = n_low % d;
        quot_low += (mod_low > 0) - (mod_low && round_down);
        // Combine and return the result
        return (quot_high << 32) + quot_low;
    }
 
#ifdef __SIZEOF_INT128__
    static inline __int128 Mul(int64_t a, int32_t b) noexcept
    {
        return __int128{a} * b;
    }
 
    static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
    {
        Assume(d > 0);
        // Compute the division.
        int64_t quot = n / d;
        int32_t mod = n % d;
        // Correct result if the / operator above rounded in the wrong direction.
        return quot + ((mod > 0) - (mod && round_down));
    }
#else
    static constexpr auto Mul = MulFallback;
    static constexpr auto Div = DivFallback;
#endif
 
    int64_t fee;
    int32_t size;
 
    constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
 
    constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
 
    constexpr inline FeeFrac(const FeeFrac&) noexcept = default;
    constexpr inline FeeFrac& operator=(const FeeFrac&) noexcept = default;
 
    bool inline IsEmpty() const noexcept {
        return size == 0;
    }
 
    void inline operator+=(const FeeFrac& other) noexcept
    {
        fee += other.fee;
        size += other.size;
    }
 
    void inline operator-=(const FeeFrac& other) noexcept
    {
        fee -= other.fee;
        size -= other.size;
    }
 
    friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
    {
        return {a.fee + b.fee, a.size + b.size};
    }
 
    friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
    {
        return {a.fee - b.fee, a.size - b.size};
    }
 
    friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
    {
        return a.fee == b.fee && a.size == b.size;
    }
 
    friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
    {
        std::swap(a.fee, b.fee);
        std::swap(a.size, b.size);
    }
 
    template<bool RoundDown>
    int64_t EvaluateFee(int32_t at_size) const noexcept
    {
        Assume(size > 0);
        Assume(at_size >= 0);
        if (fee >= 0 && fee < 0x200000000) [[likely]] {
            // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
            if constexpr (RoundDown) {
                return (uint64_t(fee) * at_size) / uint32_t(size);
            } else {
                return CeilDiv(uint64_t(fee) * at_size, uint32_t(size));
            }
        } else {
            // Otherwise, use Mul and Div.
            return Div(Mul(fee, at_size), size, RoundDown);
        }
    }
 
public:
    int64_t EvaluateFeeDown(int32_t at_size) const noexcept { return EvaluateFee<true>(at_size); }
    int64_t EvaluateFeeUp(int32_t at_size) const noexcept { return EvaluateFee<false>(at_size); }
};
 
std::partial_ordering CompareChunks(std::span<const FeeFrac> chunks0, std::span<const FeeFrac> chunks1);
 
template<typename Tag>
struct FeePerUnit : public FeeFrac
{
    // Inherit FeeFrac constructors.
    using FeeFrac::FeeFrac;
 
    static FeePerUnit FromFeeFrac(const FeeFrac& feefrac) noexcept
    {
        return {feefrac.fee, feefrac.size};
    }
};
 
// FeePerUnit instance for satoshi / vbyte.
struct VSizeTag {};
using FeePerVSize = FeePerUnit<VSizeTag>;
 
// FeePerUnit instance for satoshi / WU.
struct WeightTag {};
using FeePerWeight = FeePerUnit<WeightTag>;
 
template<std::derived_from<FeeFrac> T>
class ByRatio
{
    const T& m_feefrac;
 
public:
    constexpr ByRatio(const T& feefrac) noexcept : m_feefrac{feefrac} {}
 
    friend bool operator==(const ByRatio& a, const ByRatio& b) noexcept
    {
        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
        return cross_a == cross_b;
    }
 
    // Note that we can use std::strong_ordering here, because even though FeeFrac{1,2} and
    // FeeFrac{2,4} are distinct as FeeFracs, they are indistinguishable from ByRatio's perspective
    // (operator== also treats them as equal).
    friend std::strong_ordering operator<=>(const ByRatio& a, const ByRatio& b) noexcept
    {
        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
        return cross_a <=> cross_b;
    }
 
    // Specialized versions for efficiency. GCC 15+ and Clang 11+ produce operator<=>-derived
    // versions that are equally efficient as this at -O2, but earlier versions do not.
    friend bool operator<(const ByRatio& a, const ByRatio& b) noexcept
    {
        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
        return cross_a < cross_b;
    }
    friend bool operator>(const ByRatio& a, const ByRatio& b) noexcept
    {
        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
        return cross_a > cross_b;
    }
    friend bool operator<=(const ByRatio& a, const ByRatio& b) noexcept
    {
        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
        return cross_a <= cross_b;
    }
    friend bool operator>=(const ByRatio& a, const ByRatio& b) noexcept
    {
        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
        return cross_a >= cross_b;
    }
};
 
template<std::derived_from<FeeFrac> T>
class ByRatioNegSize
{
    const T& m_feefrac;
 
public:
    constexpr ByRatioNegSize(const T& feefrac) noexcept : m_feefrac{feefrac} {}
 
    friend bool operator==(const ByRatioNegSize& a, const ByRatioNegSize& b) noexcept
    {
        return a.m_feefrac == b.m_feefrac;
    }
 
    friend std::strong_ordering operator<=>(const ByRatioNegSize& a, const ByRatioNegSize& b) noexcept
    {
        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
        auto cmp = cross_a <=> cross_b;
        if (cmp != 0) return cmp;
        return b.m_feefrac.size <=> a.m_feefrac.size;
    }
 
    // Support conversion back to underlying FeeFrac, which allows using std::max().
    operator const T&() const noexcept { return m_feefrac; }
};
 
#endif // BITCOIN_UTIL_FEEFRAC_H