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 <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 : 92 : static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
27 : : {
28 : 92 : int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
29 : 92 : int64_t high = (a >> 32) * b;
30 [ - + ]: 92 : 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 : 73 : static inline int64_t DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down) noexcept
42 : : {
43 [ - + ]: 73 : 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 : 73 : 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 : 73 : 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 : 73 : int64_t quot_low = n_low / d;
56 : 73 : int32_t mod_low = n_low % d;
57 : 73 : quot_low += (mod_low > 0) - (mod_low && round_down);
58 : : // Combine and return the result
59 : 73 : 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 : 390335509 : static inline __int128 Mul(int64_t a, int32_t b) noexcept
66 : : {
67 [ + + ]: 390210273 : 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 : 127131 : static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
76 : : {
77 [ - + ]: 127131 : Assume(d > 0);
78 : : // Compute the division.
79 : 127131 : int64_t quot = n / d;
80 : 127131 : int32_t mod = n % d;
81 : : // Correct result if the / operator above rounded in the wrong direction.
82 : 127131 : 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 : 16583702 : constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
94 : :
95 : : /** Construct a FeeFrac with specified fee and size. */
96 [ - + ]: 68216496 : 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 : 75023719 : bool inline IsEmpty() const noexcept {
103 [ - + + + ]: 75023719 : return size == 0;
[ + + ][ + +
- + + + ]
[ - + - +
- + + + -
+ ]
104 : : }
105 : :
106 : : /** Add fee and size of another FeeFrac to this one. */
107 : 452338512 : void inline operator+=(const FeeFrac& other) noexcept
108 : : {
109 : 452338512 : fee += other.fee;
110 [ + - ]: 435347164 : size += other.size;
[ + + + + ]
111 : 2367317 : }
112 : :
113 : : /** Subtract fee and size of another FeeFrac from this one. */
114 : 2588964 : void inline operator-=(const FeeFrac& other) noexcept
115 : : {
116 : 2588964 : fee -= other.fee;
117 : 2588964 : size -= other.size;
118 : : }
119 : :
120 : : /** Sum fee and size. */
121 : 22849093 : friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
122 : : {
123 [ + - ]: 22849093 : return {a.fee + b.fee, a.size + b.size};
124 : : }
125 : :
126 : : /** Subtract both fee and size. */
127 : 10646289 : friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
128 : : {
129 [ - + - + ]: 10646289 : 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 : 13704656 : friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
134 : : {
135 [ + + + + ]: 13704456 : return a.fee == b.fee && a.size == b.size;
[ + - + +
+ - - + ]
[ + - + -
+ - - + +
- - + + +
+ + + + +
+ + - + +
+ - - + +
- + + + -
+ + + - -
+ + - +
+ ]
136 : : }
137 : :
138 : : /** Swap two FeeFracs. */
139 : 7580365 : friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
140 : : {
141 : 383591 : std::swap(a.fee, b.fee);
142 : 383591 : 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 : 73510823 : int64_t EvaluateFee(int32_t at_size) const noexcept
156 : : {
157 [ - + ]: 73510823 : Assume(size > 0);
158 [ - + ]: 73510823 : Assume(at_size >= 0);
159 [ + + ]: 73510823 : 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 : 1211606 : return (uint64_t(fee) * at_size) / uint32_t(size);
163 : : } else {
164 : 72172128 : return CeilDiv(uint64_t(fee) * at_size, uint32_t(size));
165 : : }
166 : : } else {
167 : : // Otherwise, use Mul and Div.
168 : 127089 : 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 : 1262029 : 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 : 72228555 : 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 [ + - ]: 5626022 : struct FeePerUnit : public FeeFrac
192 : : {
193 : : // Inherit FeeFrac constructors.
194 [ + + # # : 18176793 : using FeeFrac::FeeFrac;
# # ][ + +
+ + + + ]
[ + - + - ]
195 : :
196 : : /** Convert a FeeFrac to a FeePerUnit. */
197 : 7587657 : static FeePerUnit FromFeeFrac(const FeeFrac& feefrac) noexcept
198 : : {
199 [ + + ]: 7464360 : 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 [ + + ][ + + : 257507637 : constexpr ByRatio(const T& feefrac) noexcept : m_feefrac{feefrac} {}
+ + + + ]
[ + + + +
+ + + + +
+ + + +
+ ][ + + +
+ # # # #
# # # # #
# ][ + + +
+ + + + +
+ + + + ]
[ + + + +
+ + + + ]
224 : :
225 : 1942 : friend bool operator==(const ByRatio& a, const ByRatio& b) noexcept
226 : : {
227 : 43808 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
228 [ + + ]: 43808 : 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 : 254861301 : friend std::strong_ordering operator<=>(const ByRatio& a, const ByRatio& b) noexcept
236 : : {
237 : 254861301 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
238 : 254861301 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
239 [ + + + + ]: 254861301 : 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 : 8847326 : friend bool operator<(const ByRatio& a, const ByRatio& b) noexcept
245 : : {
246 : 8847326 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
247 [ + + ][ + + : 8847326 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
+ + + + ]
[ + + + + ]
248 [ - + ]: 50 : return cross_a < cross_b;
249 : : }
250 : 40769203 : friend bool operator>(const ByRatio& a, const ByRatio& b) noexcept
251 : : {
252 : 40769203 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
253 [ + + - + ]: 40769203 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
[ + + + +
+ + ][ + +
+ + + + +
+ ][ - + ]
254 [ - + ]: 50 : return cross_a > cross_b;
255 : : }
256 : 1332787 : friend bool operator<=(const ByRatio& a, const ByRatio& b) noexcept
257 : : {
258 : 1332787 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
259 [ - + ][ - + : 1332787 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
- + - + -
+ - + -
+ ]
260 : : return cross_a <= cross_b;
261 : : }
262 : 1277117 : friend bool operator>=(const ByRatio& a, const ByRatio& b) noexcept
263 : : {
264 : 1277117 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
265 [ - + ]: 1277117 : 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 [ + + ][ + + : 30547574 : constexpr ByRatioNegSize(const T& feefrac) noexcept : m_feefrac{feefrac} {}
+ + - + -
+ - + ]
295 : :
296 : 100 : friend bool operator==(const ByRatioNegSize& a, const ByRatioNegSize& b) noexcept
297 : : {
298 [ + + - + : 150 : return a.m_feefrac == b.m_feefrac;
+ + - + ]
299 : : }
300 : :
301 : 83120605 : friend std::strong_ordering operator<=>(const ByRatioNegSize& a, const ByRatioNegSize& b) noexcept
302 : : {
303 : 83120605 : auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size);
304 : 83120605 : auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size);
305 [ + + + + ]: 83120605 : auto cmp = cross_a <=> cross_b;
306 [ + + ]: 83120605 : if (cmp != 0) return cmp;
307 [ + + + + ]: 33302869 : return b.m_feefrac.size <=> a.m_feefrac.size;
308 : : }
309 : :
310 : : // Support conversion back to underlying FeeFrac, which allows using std::max().
311 : 18889002 : operator const T&() const noexcept { return m_feefrac; }
312 : : };
313 : :
314 : : #endif // BITCOIN_UTIL_FEEFRAC_H
|
