Inside Bitcoin

1// Copyright (c) The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#ifndef BITCOIN_UTIL_FEEFRAC_H
6#define BITCOIN_UTIL_FEEFRAC_H
7
8#include <util/check.h>
9#include <util/overflow.h>
10
11#include <concepts>
12#include <cstdint>
13#include <span>
14#include <utility>
15
16/** Data structure storing a fee and size.
17 *
18 * The size of a FeeFrac cannot be zero unless the fee is also zero.
19 */
20struct FeeFrac
21{
22    /** Helper function for 32*64 signed multiplication, returning an unspecified but totally
23     *  ordered type. This is a fallback version, separate so it can be tested on platforms where
24     *  it isn't actually needed. */
25    static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
26    {
27        int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
28        int64_t high = (a >> 32) * b;
29        return {high + (low >> 32), static_cast<uint32_t>(low)};
30    }
31
32    /** Helper function for 96/32 signed division, rounding towards negative infinity (if
33     *  round_down) or positive infinity (if !round_down). This is a fallback version, separate so
34     *  that it can be tested on platforms where it isn't actually needed.
35     *
36     * The exact behavior with negative n does not really matter, but this implementation chooses
37     * to be consistent for testability reasons.
38     *
39     * The result must fit in an int64_t, and d must be strictly positive. */
40    static inline int64_t DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down) noexcept
41    {
42        Assume(d > 0);
43        // Compute quot_high = n.first / d, so the result becomes
44        // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
45        // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
46        int64_t quot_high = n.first / d;
47        // Evaluate the parenthesized expression above, so the result becomes
48        // n_low / d + (quot_high * 2**32)
49        int64_t n_low = ((n.first % d) << 32) + n.second;
50        // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible
51        // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
52        // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
53        // correction.
54        int64_t quot_low = n_low / d;
55        int32_t mod_low = n_low % d;
56        quot_low += (mod_low > 0) - (mod_low && round_down);
57        // Combine and return the result
58        return (quot_high << 32) + quot_low;
59    }
60
61#ifdef __SIZEOF_INT128__
62    /** Helper function for 32*64 signed multiplication, returning an unspecified but totally
63     *  ordered type. This is a version relying on __int128. */
64    static inline __int128 Mul(int64_t a, int32_t b) noexcept
65    {
66        return __int128{a} * b;
67    }
68
69    /** Helper function for 96/32 signed division, rounding towards negative infinity (if
70     *  round_down), or towards positive infinity (if !round_down). This is a
71     *  version relying on __int128.
72     *
73     * The result must fit in an int64_t, and d must be strictly positive. */
74    static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
75    {
76        Assume(d > 0);
77        // Compute the division.
78        int64_t quot = n / d;
79        int32_t mod = n % d;
80        // Correct result if the / operator above rounded in the wrong direction.
81        return quot + ((mod > 0) - (mod && round_down));
82    }
83#else
84    static constexpr auto Mul = MulFallback;
85    static constexpr auto Div = DivFallback;
86#endif
87
88    int64_t fee;
89    int32_t size;
90
91    /** Construct an IsEmpty() FeeFrac. */
92    constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
93
94    /** Construct a FeeFrac with specified fee and size. */
95    constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
96
97    constexpr inline FeeFrac(const FeeFrac&) noexcept = default;
98    constexpr inline FeeFrac& operator=(const FeeFrac&) noexcept = default;
99
100    /** Check if this is empty (size and fee are 0). */
101    bool inline IsEmpty() const noexcept {
102        return size == 0;
103    }
104
105    /** Add fee and size of another FeeFrac to this one. */
106    void inline operator+=(const FeeFrac& other) noexcept
107    {
108        fee += other.fee;
109        size += other.size;
110    }
111
112    /** Subtract fee and size of another FeeFrac from this one. */
113    void inline operator-=(const FeeFrac& other) noexcept
114    {
115        fee -= other.fee;
116        size -= other.size;
117    }
118
119    /** Sum fee and size. */
120    friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
121    {
122        return {a.fee + b.fee, a.size + b.size};
123    }
124
125    /** Subtract both fee and size. */
126    friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
127    {
128        return {a.fee - b.fee, a.size - b.size};
129    }
130
131    /** Check if two FeeFrac objects are equal (both same fee and same size). */
132    friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
133    {
134        return a.fee == b.fee && a.size == b.size;
135    }
136
137    /** Swap two FeeFracs. */
138    friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
139    {
140        std::swap(a.fee, b.fee);
141        std::swap(a.size, b.size);
142    }
143
144    /** Compute the fee for a given size `at_size` using this object's feerate.
145     *
146     * This effectively corresponds to evaluating (this->fee * at_size) / this->size, with the
147     * result rounded towards negative infinity (if RoundDown) or towards positive infinity
148     * (if !RoundDown).
149     *
150     * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This
151     * is guaranteed to be the case when 0 <= at_size <= this->size.
152     */
153    template<bool RoundDown>
154    int64_t EvaluateFee(int32_t at_size) const noexcept
155    {
156        Assume(size > 0);
157        Assume(at_size >= 0);
158        if (fee >= 0 && fee < 0x200000000) [[likely]] {
159            // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
160            if constexpr (RoundDown) {
161                return (uint64_t(fee) * at_size) / uint32_t(size);
162            } else {
163                return CeilDiv(uint64_t(fee) * at_size, uint32_t(size));
164            }
165        } else {
166            // Otherwise, use Mul and Div.
167            return Div(Mul(fee, at_size), size, RoundDown);
168        }
169    }
170
171public:
172    /** Compute the fee for a given size `at_size` using this object's feerate, rounding down. */
173    int64_t EvaluateFeeDown(int32_t at_size) const noexcept { return EvaluateFee<true>(at_size); }
174    /** Compute the fee for a given size `at_size` using this object's feerate, rounding up. */
175    int64_t EvaluateFeeUp(int32_t at_size) const noexcept { return EvaluateFee<false>(at_size); }
176};
177
178/** Compare the feerate diagrams implied by the provided sorted chunks data.
179 *
180 * The implied diagram for each starts at (0, 0), then contains for each chunk the cumulative fee
181 * and size up to that chunk, and then extends infinitely to the right with a horizontal line.
182 *
183 * The caller must guarantee that the sum of the FeeFracs in either of the chunks' data set do not
184 * overflow (so sum fees < 2^63, and sum sizes < 2^31).
185 */
186std::partial_ordering CompareChunks(std::span<const FeeFrac> chunks0, std::span<const FeeFrac> chunks1);
187
188/** Tagged wrapper around FeeFrac to avoid unit confusion. */
189template<typename Tag>
190struct FeePerUnit : public FeeFrac
191{
192    // Inherit FeeFrac constructors.
193    using FeeFrac::FeeFrac;
194
195    /** Convert a FeeFrac to a FeePerUnit. */
196    static FeePerUnit FromFeeFrac(const FeeFrac& feefrac) noexcept
197    {
198        return {feefrac.fee, feefrac.size};
199    }
200};
201
202// FeePerUnit instance for satoshi / vbyte.
203struct VSizeTag {};
204using FeePerVSize = FeePerUnit<VSizeTag>;
205
206// FeePerUnit instance for satoshi / WU.
207struct WeightTag {};
208using FeePerWeight = FeePerUnit<WeightTag>;
209
210/** Wrapper around FeeFrac & derived types, which adds a feerate-based ordering which treats
211 *  equal-feerate but distinct-size FeeFracs as equals.
212 *
213 *  This is not included inside FeeFrac itself, because it is not a total ordering (as would be
214 *  expected for built-in comparison operators).
215 */
216template<std::derived_from<FeeFrac> T>
217class ByRatio
218{
219    const T& m_feefrac;
220
221public:
222    constexpr ByRatio(const T& feefrac) noexcept : m_feefrac{feefrac} {}
223
224    friend bool operator==(const ByRatio& a, const ByRatio& b) noexcept
225    {
226        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
227        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
228        return cross_a == cross_b;
229    }
230
231    // Note that we can use std::strong_ordering here, because even though FeeFrac{1,2} and
232    // FeeFrac{2,4} are distinct as FeeFracs, they are indistinguishable from ByRatio's perspective
233    // (operator== also treats them as equal).
234    friend std::strong_ordering operator<=>(const ByRatio& a, const ByRatio& b) noexcept
235    {
236        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
237        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
238        return cross_a <=> cross_b;
239    }
240
241    // Specialized versions for efficiency. GCC 15+ and Clang 11+ produce operator<=>-derived
242    // versions that are equally efficient as this at -O2, but earlier versions do not.
243    friend bool operator<(const ByRatio& a, const ByRatio& b) noexcept
244    {
245        auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
246        auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
247        return cross_a < cross_b;
248    }
249    friend bool operator>(const ByRatio& a, const ByRatio& b) noexcept
250    {