Bitcoin Core 29.99.0
P2P Digital Currency
feefrac.h
Go to the documentation of this file.
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
11#include <compare>
12#include <cstdint>
13#include <vector>
14
39struct FeeFrac
40{
44 static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
45 {
46 int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
47 int64_t high = (a >> 32) * b;
48 return {high + (low >> 32), static_cast<uint32_t>(low)};
49 }
50
59 static inline int64_t DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down) noexcept
60 {
61 Assume(d > 0);
62 // Compute quot_high = n.first / d, so the result becomes
63 // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
64 // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
65 int64_t quot_high = n.first / d;
66 // Evaluate the parenthesized expression above, so the result becomes
67 // n_low / d + (quot_high * 2**32)
68 int64_t n_low = ((n.first % d) << 32) + n.second;
69 // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible
70 // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
71 // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
72 // correction.
73 int64_t quot_low = n_low / d;
74 int32_t mod_low = n_low % d;
75 quot_low += (mod_low > 0) - (mod_low && round_down);
76 // Combine and return the result
77 return (quot_high << 32) + quot_low;
78 }
79
80#ifdef __SIZEOF_INT128__
83 static inline __int128 Mul(int64_t a, int32_t b) noexcept
84 {
85 return __int128{a} * b;
86 }
87
93 static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
94 {
95 Assume(d > 0);
96 // Compute the division.
97 int64_t quot = n / d;
98 int32_t mod = n % d;
99 // Correct result if the / operator above rounded in the wrong direction.
100 return quot + ((mod > 0) - (mod && round_down));
101 }
102#else
103 static constexpr auto Mul = MulFallback;
104 static constexpr auto Div = DivFallback;
105#endif
106
107 int64_t fee;
108 int32_t size;
109
111 constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
112
114 constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
115
116 constexpr inline FeeFrac(const FeeFrac&) noexcept = default;
117 constexpr inline FeeFrac& operator=(const FeeFrac&) noexcept = default;
118
120 bool inline IsEmpty() const noexcept {
121 return size == 0;
122 }
123
125 void inline operator+=(const FeeFrac& other) noexcept
126 {
127 fee += other.fee;
128 size += other.size;
129 }
130
132 void inline operator-=(const FeeFrac& other) noexcept
133 {
134 fee -= other.fee;
135 size -= other.size;
136 }
137
139 friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
140 {
141 return {a.fee + b.fee, a.size + b.size};
142 }
143
145 friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
146 {
147 return {a.fee - b.fee, a.size - b.size};
148 }
149
151 friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
152 {
153 return a.fee == b.fee && a.size == b.size;
154 }
155
157 friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept
158 {
159 auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
160 return cross_a <=> cross_b;
161 }
162
164 friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept
165 {
166 auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
167 return cross_a < cross_b;
168 }
169
171 friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept
172 {
173 auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
174 return cross_a > cross_b;
175 }
176
178 friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept
179 {
180 auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
181 if (cross_a == cross_b) return b.size <=> a.size;
182 return cross_a <=> cross_b;
183 }
184
186 friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
187 {
188 std::swap(a.fee, b.fee);
189 std::swap(a.size, b.size);
190 }
191
201 template<bool RoundDown>
202 int64_t EvaluateFee(int32_t at_size) const noexcept
203 {
204 Assume(size > 0);
205 Assume(at_size >= 0);
206 if (fee >= 0 && fee < 0x200000000) [[likely]] {
207 // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
208 if constexpr (RoundDown) {
209 return (uint64_t(fee) * at_size) / uint32_t(size);
210 } else {
211 return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
212 }
213 } else {
214 // Otherwise, use Mul and Div.
215 return Div(Mul(fee, at_size), size, RoundDown);
216 }
217 }
218
219public:
221 int64_t EvaluateFeeDown(int32_t at_size) const noexcept { return EvaluateFee<true>(at_size); }
223 int64_t EvaluateFeeUp(int32_t at_size) const noexcept { return EvaluateFee<false>(at_size); }
224};
225
234std::partial_ordering CompareChunks(std::span<const FeeFrac> chunks0, std::span<const FeeFrac> chunks1);
235
237template<typename Tag>
238struct FeePerUnit : public FeeFrac
239{
240 // Inherit FeeFrac constructors.
241 using FeeFrac::FeeFrac;
242
244 static FeePerUnit FromFeeFrac(const FeeFrac& feefrac) noexcept
245 {
246 return {feefrac.fee, feefrac.size};
247 }
248};
249
250// FeePerUnit instance for satoshi / vbyte.
251struct VSizeTag {};
253
254// FeePerUnit instance for satoshi / WU.
255struct WeightTag {};
257
258#endif // BITCOIN_UTIL_FEEFRAC_H
#define Assume(val)
Assume is the identity function.
Definition: check.h:118
std::partial_ordering CompareChunks(std::span< const FeeFrac > chunks0, std::span< const FeeFrac > chunks1)
Compare the feerate diagrams implied by the provided sorted chunks data.
Definition: feefrac.cpp:10
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:40
constexpr FeeFrac(int64_t f, int32_t s) noexcept
Construct a FeeFrac with specified fee and size.
Definition: feefrac.h:114
friend std::weak_ordering FeeRateCompare(const FeeFrac &a, const FeeFrac &b) noexcept
Compare two FeeFracs just by feerate.
Definition: feefrac.h:157
friend FeeFrac operator-(const FeeFrac &a, const FeeFrac &b) noexcept
Subtract both fee and size.
Definition: feefrac.h:145
friend bool operator>>(const FeeFrac &a, const FeeFrac &b) noexcept
Check if a FeeFrac object has strictly higher feerate than another.
Definition: feefrac.h:171
friend void swap(FeeFrac &a, FeeFrac &b) noexcept
Swap two FeeFracs.
Definition: feefrac.h:186
int64_t fee
Definition: feefrac.h:107
int64_t EvaluateFeeDown(int32_t at_size) const noexcept
Compute the fee for a given size at_size using this object's feerate, rounding down.
Definition: feefrac.h:221
int64_t EvaluateFee(int32_t at_size) const noexcept
Compute the fee for a given size at_size using this object's feerate.
Definition: feefrac.h:202
static int64_t DivFallback(std::pair< int64_t, uint32_t > n, int32_t d, bool round_down) noexcept
Helper function for 96/32 signed division, rounding towards negative infinity (if round_down) or posi...
Definition: feefrac.h:59
int64_t EvaluateFeeUp(int32_t at_size) const noexcept
Compute the fee for a given size at_size using this object's feerate, rounding up.
Definition: feefrac.h:223
friend std::strong_ordering operator<=>(const FeeFrac &a, const FeeFrac &b) noexcept
Compare two FeeFracs.
Definition: feefrac.h:178
constexpr FeeFrac(const FeeFrac &) noexcept=default
static constexpr auto Div
Definition: feefrac.h:104
constexpr FeeFrac & operator=(const FeeFrac &) noexcept=default
static constexpr auto Mul
Definition: feefrac.h:103
friend bool operator<<(const FeeFrac &a, const FeeFrac &b) noexcept
Check if a FeeFrac object has strictly lower feerate than another.
Definition: feefrac.h:164
void operator-=(const FeeFrac &other) noexcept
Subtract fee and size of another FeeFrac from this one.
Definition: feefrac.h:132
int32_t size
Definition: feefrac.h:108
void operator+=(const FeeFrac &other) noexcept
Add fee and size of another FeeFrac to this one.
Definition: feefrac.h:125
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
Definition: feefrac.h:120
constexpr FeeFrac() noexcept
Construct an IsEmpty() FeeFrac.
Definition: feefrac.h:111
static std::pair< int64_t, uint32_t > MulFallback(int64_t a, int32_t b) noexcept
Helper function for 32*64 signed multiplication, returning an unspecified but totally ordered type.
Definition: feefrac.h:44
friend FeeFrac operator+(const FeeFrac &a, const FeeFrac &b) noexcept
Sum fee and size.
Definition: feefrac.h:139
friend bool operator==(const FeeFrac &a, const FeeFrac &b) noexcept
Check if two FeeFrac objects are equal (both same fee and same size).
Definition: feefrac.h:151
Tagged wrapper around FeeFrac to avoid unit confusion.
Definition: feefrac.h:239
static FeePerUnit FromFeeFrac(const FeeFrac &feefrac) noexcept
Convert a FeeFrac to a FeePerUnit.
Definition: feefrac.h:244