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      static inline __int128 Mul(int64_t a, int32_t b) noexcept
 85      {
 86          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      static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
 95      {
 96          Assume(d > 0);
 97          // Compute the division.
 98          int64_t quot = n / d;
 99          int32_t mod = n % d;
100          // Correct result if the / operator above rounded in the wrong direction.
101          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      constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
113  
114      /** Construct a FeeFrac with specified fee and size. */
115      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      bool inline IsEmpty() const noexcept {
122          return size == 0;
123      }
124  
125      /** Add fee and size of another FeeFrac to this one. */
126      void inline operator+=(const FeeFrac& other) noexcept
127      {
128          fee += other.fee;
129          size += other.size;
130      }
131  
132      /** Subtract fee and size of another FeeFrac from this one. */
133      void inline operator-=(const FeeFrac& other) noexcept
134      {
135          fee -= other.fee;
136          size -= other.size;
137      }
138  
139      /** Sum fee and size. */
140      friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
141      {
142          return {a.fee + b.fee, a.size + b.size};
143      }
144  
145      /** Subtract both fee and size. */
146      friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
147      {
148          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      friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
153      {
154          return a.fee == b.fee && a.size == b.size;
155      }
156  
157      /** Compare two FeeFracs just by feerate. */
158      friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept
159      {
160          auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
161          return cross_a <=> cross_b;
162      }
163  
164      /** Check if a FeeFrac object has strictly lower feerate than another. */
165      friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept
166      {
167          auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
168          return cross_a < cross_b;
169      }
170  
171      /** Check if a FeeFrac object has strictly higher feerate than another. */
172      friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept
173      {
174          auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
175          return cross_a > cross_b;
176      }
177  
178      /** Compare two FeeFracs. <, >, <=, and >= are auto-generated from this. */
179      friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept
180      {
181          auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
182          if (cross_a == cross_b) return b.size <=> a.size;
183          return cross_a <=> cross_b;
184      }
185  
186      /** Swap two FeeFracs. */
187      friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
188      {
189          std::swap(a.fee, b.fee);
190          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      int64_t EvaluateFee(int32_t at_size) const noexcept
204      {
205          Assume(size > 0);
206          Assume(at_size >= 0);
207          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                  return (uint64_t(fee) * at_size) / uint32_t(size);
211              } else {
212                  return CeilDiv(uint64_t(fee) * at_size, uint32_t(size));
213              }
214          } else {
215              // Otherwise, use Mul and Div.
216              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      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      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  struct FeePerUnit : public FeeFrac
240  {
241      // Inherit FeeFrac constructors.
242      using FeeFrac::FeeFrac;
243  
244      /** Convert a FeeFrac to a FeePerUnit. */
245      static FeePerUnit FromFeeFrac(const FeeFrac& feefrac) noexcept
246      {
247          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