Branch data Line data Source code
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 : : */
20 : : struct 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 : 286221842 : static inline __int128 Mul(int64_t a, int32_t b) noexcept
65 : : {
66 : 286237724 : 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 : 78 : static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
75 : : {
76 : 78 : Assume(d > 0);
77 : : // Compute the division.
78 : 78 : int64_t quot = n / d;
79 : 78 : int32_t mod = n % d;
80 : : // Correct result if the / operator above rounded in the wrong direction.
81 : 78 : 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 : 5403133 : constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
93 : :
94 : : /** Construct a FeeFrac with specified fee and size. */
95 [ - + - + : 40568891 : 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 : 13796354 : bool inline IsEmpty() const noexcept {
102 [ + + + + : 13795912 : return size == 0;
+ + + + +
+ ][ + + +
+ + + ]
[ + + ]
103 : : }
104 : :
105 : : /** Add fee and size of another FeeFrac to this one. */
106 : 47543349 : void inline operator+=(const FeeFrac& other) noexcept
107 : : {
108 : 47543349 : fee += other.fee;
109 [ + - ]: 46994476 : size += other.size;
110 : 216454 : }
111 : :
112 : : /** Subtract fee and size of another FeeFrac from this one. */
113 : 15919429 : void inline operator-=(const FeeFrac& other) noexcept
114 : : {
115 : 15919429 : fee -= other.fee;
116 : 15919429 : size -= other.size;
117 : : }
118 : :
119 : : /** Sum fee and size. */
120 : 8563 : friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
121 : : {
122 : 8563 : return {a.fee + b.fee, a.size + b.size};
123 : : }
124 : :
125 : : /** Subtract both fee and size. */
126 : 4645 : friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
127 : : {
128 [ + + + + ]: 2685 : 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 : 43460176 : friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
133 : : {
134 [ + + + + : 43460175 : return a.fee == b.fee && a.size == b.size;
+ - - + +
- - + ][ +
- + + + -
+ + + - +
- + - + -
+ - + - +
+ + + ][ +
+ + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + - -
+ + - - +
+ - - + -
+ - - - +
- - + - -
+ + - - +
- - ][ + -
- + + - -
+ # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
- - + + -
- + + - -
+ + - - +
+ - - + +
- - + + -
- + + - -
+ + - - +
+ - - + +
- - + + -
- + + - -
+ ]
135 : : }
136 : :
137 : : /** Swap two FeeFracs. */
138 : 1863 : friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
139 : : {
140 : 89 : std::swap(a.fee, b.fee);
141 : 89 : 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 : 2642317 : int64_t EvaluateFee(int32_t at_size) const noexcept
155 : : {
156 [ + + ]: 2642317 : Assume(size > 0);
157 : 2642317 : Assume(at_size >= 0);
158 [ + + ]: 2642317 : 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 : 725579 : return (uint64_t(fee) * at_size) / uint32_t(size);
162 : : } else {
163 : 1916660 : return CeilDiv(uint64_t(fee) * at_size, uint32_t(size));
164 : : }
165 : : } else {
166 : : // Otherwise, use Mul and Div.
167 : 78 : return Div(Mul(fee, at_size), size, RoundDown);
168 : : }
169 : : }
170 : :
171 : : public:
172 : : /** Compute the fee for a given size `at_size` using this object's feerate, rounding down. */
173 [ + + + - : 635232 : 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 : 1916690 : 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 : : */
186 : : std::partial_ordering CompareChunks(std::span<const FeeFrac> chunks0, std::span<const FeeFrac> chunks1);
187 : :
188 : : /** Tagged wrapper around FeeFrac to avoid unit confusion. */
189 : : template<typename Tag>
190 [ + + ]: 345472 : struct FeePerUnit : public FeeFrac
191 : : {
192 : : // Inherit FeeFrac constructors.
193 [ + + + - : 1089047 : using FeeFrac::FeeFrac;
+ - + - +
- ][ + + +
+ # # # #
# # ][ + - ]
194 : :
195 : : /** Convert a FeeFrac to a FeePerUnit. */
196 : 90772 : static FeePerUnit FromFeeFrac(const FeeFrac& feefrac) noexcept
197 : : {
198 [ - - + + ]: 90763 : return {feefrac.fee, feefrac.size};
199 : : }
200 : : };
201 : :
202 : : // FeePerUnit instance for satoshi / vbyte.
203 : : struct VSizeTag {};
204 : : using FeePerVSize = FeePerUnit<VSizeTag>;
205 : :
206 : : // FeePerUnit instance for satoshi / WU.
207 : : struct WeightTag {};
208 : : using 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 : : */
216 : : template<std::derived_from<FeeFrac> T>
217 : : class ByRatio
218 : : {
219 : : const T& m_feefrac;
220 : :
221 : : public:
222 [ + + - + ]: 222192635 : constexpr ByRatio(const T& feefrac) noexcept : m_feefrac{feefrac} {}
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ ][ + + +
+ # # # #
# # # # #
# # # # #
# # # # ]
[ + + + +
+ + + - +
- + - + -
+ - + - +
- + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
- + + + +
+ + + + +
+ + + + +
+ + + + ]
[ + + + +
- - - - -
- - - +
+ ][ - - -
- - + ][ #
# # # # #
# # # # ]
223 : :
224 : 15801 : friend bool operator==(const ByRatio& a, const ByRatio& b) noexcept
225 : : {
226 : 169546 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
227 [ + + ][ + + : 167893 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
+ + + + ]
[ + - + -
+ - ]
228 [ + - + - : 35 : 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 : 221927923 : friend std::strong_ordering operator<=>(const ByRatio& a, const ByRatio& b) noexcept
235 : : {
236 : 221927923 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
237 : 221927923 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
238 [ + + + + ]: 221927923 : 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 : 6671171 : friend bool operator<(const ByRatio& a, const ByRatio& b) noexcept
244 : : {
245 : 6671172 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
246 [ + + + + : 6671170 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
+ + + + +
+ ][ + + +
+ + + ]
[ + + ]
247 [ + - + - ]: 2 : return cross_a < cross_b;
248 : : }
249 : 1114531 : friend bool operator>(const ByRatio& a, const ByRatio& b) noexcept
250 : : {
251 : 1114668 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
252 [ + + + + : 1109078 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
+ + ][ + +
+ + + + ]
[ - - - -
+ + + + +
+ + + + +
+ + + + -
+ - - - +
- + ]
253 [ + - # # ]: 3 : return cross_a > cross_b;
[ + - + - ]
254 : : }
255 : : friend bool operator<=(const ByRatio& a, const ByRatio& b) noexcept
256 : : {
257 : : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
258 : : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
259 : : return cross_a <= cross_b;
260 : : }
261 : 11759045 : friend bool operator>=(const ByRatio& a, const ByRatio& b) noexcept
262 : : {
263 : 11759045 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
264 [ - + ]: 11759045 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
265 : : return cross_a >= cross_b;
266 : : }
267 : : };
268 : :
269 : : /** Wrapper around FeeFrac & derived types, which adds a total ordering which first sorts by feerate
270 : : * and then by reversed size (i.e., larger sizes come first).
271 : : *
272 : : * This is not included inside FeeFrac itself, because it is not the most natural behavior, so it
273 : : * is better to make code using it invoke this explicitly.
274 : : *
275 : : * The empty FeeFrac (fee and size both 0) sorts last. So for example, the following FeeFracs are
276 : : * in sorted order:
277 : : *
278 : : * - fee=0 size=1 (feerate 0)
279 : : * - fee=1 size=2 (feerate 0.5)
280 : : * - fee=2 size=3 (feerate 0.667...)
281 : : * - fee=2 size=2 (feerate 1)
282 : : * - fee=1 size=1 (feerate 1)
283 : : * - fee=3 size=2 (feerate 1.5)
284 : : * - fee=2 size=1 (feerate 2)
285 : : * - fee=0 size=0 (undefined feerate)
286 : : */
287 : : template<std::derived_from<FeeFrac> T>
288 : : class ByRatioNegSize
289 : : {
290 : : const T& m_feefrac;
291 : :
292 : : public:
293 [ + - + - : 5359324 : constexpr ByRatioNegSize(const T& feefrac) noexcept : m_feefrac{feefrac} {}
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ][ + + ]
294 : :
295 : 1 : friend bool operator==(const ByRatioNegSize& a, const ByRatioNegSize& b) noexcept
296 : : {
297 [ - + + - ]: 2 : return a.m_feefrac == b.m_feefrac;
298 : : }
299 : :
300 : 44749036 : friend std::strong_ordering operator<=>(const ByRatioNegSize& a, const ByRatioNegSize& b) noexcept
301 : : {
302 : 44749036 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
303 : 44749036 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
304 [ + + + + ]: 44749036 : auto cmp = cross_a <=> cross_b;
305 [ + + ]: 44749036 : if (cmp != 0) return cmp;
306 [ + + + + ]: 43657899 : return b.m_feefrac.size <=> a.m_feefrac.size;
307 : : }
308 : :
309 : : // Support conversion back to underlying FeeFrac, which allows using std::max().
310 : 39389712 : operator const T&() const noexcept { return m_feefrac; }
311 : : };
312 : :
313 : : #endif // BITCOIN_UTIL_FEEFRAC_H
|
