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 <span.h>
9 : : #include <util/check.h>
10 : : #include <util/overflow.h>
11 : :
12 : : #include <compare>
13 : : #include <cstdint>
14 : : #include <vector>
15 : :
16 : : /** Data structure storing a fee and size, ordered by increasing fee/size.
17 : : *
18 : : * The size of a FeeFrac cannot be zero unless the fee is also zero.
19 : : *
20 : : * FeeFracs have a total ordering, first by increasing feerate (ratio of fee over size), and then
21 : : * by decreasing size. The empty FeeFrac (fee and size both 0) sorts last. So for example, the
22 : : * following FeeFracs are in sorted order:
23 : : *
24 : : * - fee=0 size=1 (feerate 0)
25 : : * - fee=1 size=2 (feerate 0.5)
26 : : * - fee=2 size=3 (feerate 0.667...)
27 : : * - fee=2 size=2 (feerate 1)
28 : : * - fee=1 size=1 (feerate 1)
29 : : * - fee=3 size=2 (feerate 1.5)
30 : : * - fee=2 size=1 (feerate 2)
31 : : * - fee=0 size=0 (undefined feerate)
32 : : *
33 : : * A FeeFrac is considered "better" if it sorts after another, by this ordering. All standard
34 : : * comparison operators (<=>, ==, !=, >, <, >=, <=) respect this ordering.
35 : : *
36 : : * The FeeRateCompare, and >> and << operators only compare feerate and treat equal feerate but
37 : : * different size as equivalent. The empty FeeFrac is neither lower or higher in feerate than any
38 : : * other.
39 : : */
40 : : struct FeeFrac
41 : : {
42 : : /** Helper function for 32*64 signed multiplication, returning an unspecified but totally
43 : : * ordered type. This is a fallback version, separate so it can be tested on platforms where
44 : : * it isn't actually needed. */
45 : : static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
46 : : {
47 : : int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
48 : : int64_t high = (a >> 32) * b;
49 : : return {high + (low >> 32), static_cast<uint32_t>(low)};
50 : : }
51 : :
52 : : /** Helper function for 96/32 signed division, rounding towards negative infinity (if
53 : : * round_down) or positive infinity (if !round_down). This is a fallback version, separate so
54 : : * that it can be tested on platforms where it isn't actually needed.
55 : : *
56 : : * The exact behavior with negative n does not really matter, but this implementation chooses
57 : : * to be consistent for testability reasons.
58 : : *
59 : : * The result must fit in an int64_t, and d must be strictly positive. */
60 : : static inline int64_t DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down) noexcept
61 : : {
62 : : Assume(d > 0);
63 : : // Compute quot_high = n.first / d, so the result becomes
64 : : // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
65 : : // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
66 : : int64_t quot_high = n.first / d;
67 : : // Evaluate the parenthesized expression above, so the result becomes
68 : : // n_low / d + (quot_high * 2**32)
69 : : int64_t n_low = ((n.first % d) << 32) + n.second;
70 : : // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible
71 : : // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
72 : : // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
73 : : // correction.
74 : : int64_t quot_low = n_low / d;
75 : : int32_t mod_low = n_low % d;
76 : : quot_low += (mod_low > 0) - (mod_low && round_down);
77 : : // Combine and return the result
78 : : return (quot_high << 32) + quot_low;
79 : : }
80 : :
81 : : #ifdef __SIZEOF_INT128__
82 : : /** Helper function for 32*64 signed multiplication, returning an unspecified but totally
83 : : * ordered type. This is a version relying on __int128. */
84 : 76399447 : static inline __int128 Mul(int64_t a, int32_t b) noexcept
85 : : {
86 : 76399507 : return __int128{a} * b;
87 : : }
88 : :
89 : : /** Helper function for 96/32 signed division, rounding towards negative infinity (if
90 : : * round_down), or towards positive infinity (if !round_down). This is a
91 : : * version relying on __int128.
92 : : *
93 : : * The result must fit in an int64_t, and d must be strictly positive. */
94 : 52 : static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
95 : : {
96 : 52 : Assume(d > 0);
97 : : // Compute the division.
98 : 52 : int64_t quot = n / d;
99 : 52 : int32_t mod = n % d;
100 : : // Correct result if the / operator above rounded in the wrong direction.
101 : 52 : return quot + ((mod > 0) - (mod && round_down));
102 : : }
103 : : #else
104 : : static constexpr auto Mul = MulFallback;
105 : : static constexpr auto Div = DivFallback;
106 : : #endif
107 : :
108 : : int64_t fee;
109 : : int32_t size;
110 : :
111 : : /** Construct an IsEmpty() FeeFrac. */
112 : 5186198 : constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
113 : :
114 : : /** Construct a FeeFrac with specified fee and size. */
115 [ - + ][ - + : 603153 : constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
- + - + -
+ - + ][ +
- + - + -
+ - + - +
- + - + -
+ - + - ]
[ + - + - ]
116 : :
117 : : constexpr inline FeeFrac(const FeeFrac&) noexcept = default;
118 : : constexpr inline FeeFrac& operator=(const FeeFrac&) noexcept = default;
119 : :
120 : : /** Check if this is empty (size and fee are 0). */
121 : 1186211 : bool inline IsEmpty() const noexcept {
122 [ + + ][ + + : 1186211 : return size == 0;
+ + + + +
+ + + ]
123 : : }
124 : :
125 : : /** Add fee and size of another FeeFrac to this one. */
126 : 35279322 : void inline operator+=(const FeeFrac& other) noexcept
127 : : {
128 : 35279322 : fee += other.fee;
129 [ + - ]: 35256284 : size += other.size;
130 : 23038 : }
131 : :
132 : : /** Subtract fee and size of another FeeFrac from this one. */
133 : 15688419 : void inline operator-=(const FeeFrac& other) noexcept
134 : : {
135 : 15688419 : fee -= other.fee;
136 : 15688419 : size -= other.size;
137 : : }
138 : :
139 : : /** Sum fee and size. */
140 : 238 : friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
141 : : {
142 : 238 : return {a.fee + b.fee, a.size + b.size};
143 : : }
144 : :
145 : : /** Subtract both fee and size. */
146 : 136 : friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
147 : : {
148 [ + + + + ]: 82 : return {a.fee - b.fee, a.size - b.size};
149 : : }
150 : :
151 : : /** Check if two FeeFrac objects are equal (both same fee and same size). */
152 : 253558 : friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
153 : : {
154 [ + - - + : 253558 : return a.fee == b.fee && a.size == b.size;
+ - - + ]
[ + + + +
# # # # ]
[ + - - +
+ - - + +
- - + - +
- - - + -
- + - - +
+ - - + -
+ - - ][ +
- + - + -
+ - + - +
- + - + -
+ - + - +
+ + + ][ +
- - + + -
- + + - -
+ # # # #
# # # # #
# # # # #
# # # # #
# ]
155 : : }
156 : :
157 : : /** Compare two FeeFracs just by feerate. */
158 : 69128974 : friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept
159 : : {
160 : 69128974 : auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
161 [ + + + + ]: 69128974 : return cross_a <=> cross_b;
162 : : }
163 : :
164 : : /** Check if a FeeFrac object has strictly lower feerate than another. */
165 : 6092743 : friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept
166 : : {
167 [ + - ]: 6092740 : auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
168 [ - - - - : 6092743 : return cross_a < cross_b;
+ + ][ + + ]
[ + - + -
+ - + - #
# ][ + + +
+ + + + +
+ + ]
169 : : }
170 : :
171 : : /** Check if a FeeFrac object has strictly higher feerate than another. */
172 : 90738 : friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept
173 : : {
174 [ + - ]: 117 : auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
175 [ + + + + : 90738 : return cross_a > cross_b;
+ + ][ + + ]
176 : : }
177 : :
178 : : /** Compare two FeeFracs. <, >, <=, and >= are auto-generated from this. */
179 : 1086940 : friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept
180 : : {
181 : 1086940 : auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
182 [ + + + + : 1086940 : if (cross_a == cross_b) return b.size <=> a.size;
+ + ]
183 [ + + ]: 1085553 : return cross_a <=> cross_b;
184 : : }
185 : :
186 : : /** Swap two FeeFracs. */
187 : 0 : friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
188 : : {
189 : 0 : std::swap(a.fee, b.fee);
190 : 0 : std::swap(a.size, b.size);
191 : : }
192 : :
193 : : /** Compute the fee for a given size `at_size` using this object's feerate.
194 : : *
195 : : * This effectively corresponds to evaluating (this->fee * at_size) / this->size, with the
196 : : * result rounded towards negative infinity (if RoundDown) or towards positive infinity
197 : : * (if !RoundDown).
198 : : *
199 : : * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This
200 : : * is guaranteed to be the case when 0 <= at_size <= this->size.
201 : : */
202 : : template<bool RoundDown>
203 : 1064628 : int64_t EvaluateFee(int32_t at_size) const noexcept
204 : : {
205 [ + + ]: 1064628 : Assume(size > 0);
206 : 1064628 : Assume(at_size >= 0);
207 [ + + ]: 1064628 : if (fee >= 0 && fee < 0x200000000) [[likely]] {
208 : : // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
209 : : if constexpr (RoundDown) {
210 : 148020 : return (uint64_t(fee) * at_size) / uint32_t(size);
211 : : } else {
212 : 916556 : return CeilDiv(uint64_t(fee) * at_size, uint32_t(size));
213 : : }
214 : : } else {
215 : : // Otherwise, use Mul and Div.
216 : 52 : return Div(Mul(fee, at_size), size, RoundDown);
217 : : }
218 : : }
219 : :
220 : : public:
221 : : /** Compute the fee for a given size `at_size` using this object's feerate, rounding down. */
222 [ + + + + ]: 98908 : int64_t EvaluateFeeDown(int32_t at_size) const noexcept { return EvaluateFee<true>(at_size); }
[ + + # # ]
[ + + - ][ -
+ + - + -
+ - ][ + -
- - - - -
- - - + -
- - + - ]
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ][ +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ][ +
- + - + -
+ - + - +
- + - + -
- - - - +
- ]
223 : : /** Compute the fee for a given size `at_size` using this object's feerate, rounding up. */
224 : 916586 : int64_t EvaluateFeeUp(int32_t at_size) const noexcept { return EvaluateFee<false>(at_size); }
225 : : };
226 : :
227 : : /** Compare the feerate diagrams implied by the provided sorted chunks data.
228 : : *
229 : : * The implied diagram for each starts at (0, 0), then contains for each chunk the cumulative fee
230 : : * and size up to that chunk, and then extends infinitely to the right with a horizontal line.
231 : : *
232 : : * The caller must guarantee that the sum of the FeeFracs in either of the chunks' data set do not
233 : : * overflow (so sum fees < 2^63, and sum sizes < 2^31).
234 : : */
235 : : std::partial_ordering CompareChunks(std::span<const FeeFrac> chunks0, std::span<const FeeFrac> chunks1);
236 : :
237 : : /** Tagged wrapper around FeeFrac to avoid unit confusion. */
238 : : template<typename Tag>
239 [ + + ]: 204770 : struct FeePerUnit : public FeeFrac
240 : : {
241 : : // Inherit FeeFrac constructors.
242 [ + - + - ]: 522904 : using FeeFrac::FeeFrac;
[ + + # #
# # ][ + -
+ - + + ]
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + + + -
+ - - - ]
[ + - + -
+ - + - +
- + - -
- ][ + - +
- + - + -
+ - + - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ + - +
- + - + -
# # # # #
# ][ + - +
- + - + -
+ - # # ]
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
243 : :
244 : : /** Convert a FeeFrac to a FeePerUnit. */
245 : 28298 : static FeePerUnit FromFeeFrac(const FeeFrac& feefrac) noexcept
246 : : {
247 [ - - + + ]: 28289 : return {feefrac.fee, feefrac.size};
248 : : }
249 : : };
250 : :
251 : : // FeePerUnit instance for satoshi / vbyte.
252 : : struct VSizeTag {};
253 : : using FeePerVSize = FeePerUnit<VSizeTag>;
254 : :
255 : : // FeePerUnit instance for satoshi / WU.
256 : : struct WeightTag {};
257 : : using FeePerWeight = FeePerUnit<WeightTag>;
258 : :
259 : : #endif // BITCOIN_UTIL_FEEFRAC_H
|
