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