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 <stdint.h>
  9  #include <compare>
 10  #include <vector>
 11  #include <span.h>
 12  #include <util/check.h>
 13  
 14  /** Data structure storing a fee and size, ordered by increasing fee/size.
 15   *
 16   * The size of a FeeFrac cannot be zero unless the fee is also zero.
 17   *
 18   * FeeFracs have a total ordering, first by increasing feerate (ratio of fee over size), and then
 19   * by decreasing size. The empty FeeFrac (fee and size both 0) sorts last. So for example, the
 20   * following FeeFracs are in sorted order:
 21   *
 22   * - fee=0 size=1 (feerate 0)
 23   * - fee=1 size=2 (feerate 0.5)
 24   * - fee=2 size=3 (feerate 0.667...)
 25   * - fee=2 size=2 (feerate 1)
 26   * - fee=1 size=1 (feerate 1)
 27   * - fee=3 size=2 (feerate 1.5)
 28   * - fee=2 size=1 (feerate 2)
 29   * - fee=0 size=0 (undefined feerate)
 30   *
 31   * A FeeFrac is considered "better" if it sorts after another, by this ordering. All standard
 32   * comparison operators (<=>, ==, !=, >, <, >=, <=) respect this ordering.
 33   *
 34   * The CompareFeeFrac, and >> and << operators only compare feerate and treat equal feerate but
 35   * different size as equivalent. The empty FeeFrac is neither lower or higher in feerate than any
 36   * other.
 37   */
 38  struct FeeFrac
 39  {
 40      /** Fallback version for Mul (see below).
 41       *
 42       * Separate to permit testing on platforms where it isn't actually needed.
 43       */
 44      static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
 45      {
 46          // Otherwise, emulate 96-bit multiplication using two 64-bit multiplies.
 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      // Compute a * b, returning an unspecified but totally ordered type.
 53  #ifdef __SIZEOF_INT128__
 54      static inline __int128 Mul(int64_t a, int32_t b) noexcept
 55      {
 56          // If __int128 is available, use 128-bit wide multiply.
 57          return __int128{a} * b;
 58      }
 59  #else
 60      static constexpr auto Mul = MulFallback;
 61  #endif
 62  
 63      int64_t fee;
 64      int32_t size;
 65  
 66      /** Construct an IsEmpty() FeeFrac. */
 67      inline FeeFrac() noexcept : fee{0}, size{0} {}
 68  
 69      /** Construct a FeeFrac with specified fee and size. */
 70      inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
 71  
 72      inline FeeFrac(const FeeFrac&) noexcept = default;
 73      inline FeeFrac& operator=(const FeeFrac&) noexcept = default;
 74  
 75      /** Check if this is empty (size and fee are 0). */
 76      bool inline IsEmpty() const noexcept {
 77          return size == 0;
 78      }
 79  
 80      /** Add fee and size of another FeeFrac to this one. */
 81      void inline operator+=(const FeeFrac& other) noexcept
 82      {
 83          fee += other.fee;
 84          size += other.size;
 85      }
 86  
 87      /** Subtract fee and size of another FeeFrac from this one. */
 88      void inline operator-=(const FeeFrac& other) noexcept
 89      {
 90          fee -= other.fee;
 91          size -= other.size;
 92      }
 93  
 94      /** Sum fee and size. */
 95      friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
 96      {
 97          return {a.fee + b.fee, a.size + b.size};
 98      }
 99  
100      /** Subtract both fee and size. */
101      friend inline FeeFrac operator-(const FeeFrac& a, const FeeFrac& b) noexcept
102      {
103          return {a.fee - b.fee, a.size - b.size};
104      }
105  
106      /** Check if two FeeFrac objects are equal (both same fee and same size). */
107      friend inline bool operator==(const FeeFrac& a, const FeeFrac& b) noexcept
108      {
109          return a.fee == b.fee && a.size == b.size;
110      }
111  
112      /** Compare two FeeFracs just by feerate. */
113      friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept
114      {
115          auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
116          return cross_a <=> cross_b;
117      }
118  
119      /** Check if a FeeFrac object has strictly lower feerate than another. */
120      friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept
121      {
122          auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
123          return cross_a < cross_b;
124      }
125  
126      /** Check if a FeeFrac object has strictly higher feerate than another. */
127      friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept
128      {
129          auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
130          return cross_a > cross_b;
131      }
132  
133      /** Compare two FeeFracs. <, >, <=, and >= are auto-generated from this. */
134      friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept
135      {
136          auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
137          if (cross_a == cross_b) return b.size <=> a.size;
138          return cross_a <=> cross_b;
139      }
140  
141      /** Swap two FeeFracs. */
142      friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
143      {
144          std::swap(a.fee, b.fee);
145          std::swap(a.size, b.size);
146      }
147  };
148  
149  /** Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at FeeFrac of (0, 0) */
150  std::vector<FeeFrac> BuildDiagramFromChunks(Span<const FeeFrac> chunks);
151  
152  /** Compares two feerate diagrams. The shorter one is implicitly
153   * extended with a horizontal straight line.
154   *
155   * A feerate diagram consists of a list of (fee, size) points with the property that size
156   * is strictly increasing and that the first entry is (0, 0).
157   */
158  std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1);
159  
160  #endif // BITCOIN_UTIL_FEEFRAC_H