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