1  // Copyright (c) 2023 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  #include <stdint.h>
  6  
  7  #include <vector>
  8  
  9  #include <util/feefrac.h>
 10  #include <policy/rbf.h>
 11  
 12  #include <test/fuzz/fuzz.h>
 13  #include <test/fuzz/util.h>
 14  
 15  #include <assert.h>
 16  
 17  namespace {
 18  
 19  /** Evaluate a diagram at a specific size, returning the fee as a fraction.
 20   *
 21   * Fees in diagram cannot exceed 2^32, as the returned evaluation could overflow
 22   * the FeeFrac::fee field in the result. */
 23  FeeFrac EvaluateDiagram(int32_t size, Span<const FeeFrac> diagram)
 24  {
 25      assert(diagram.size() > 0);
 26      unsigned not_above = 0;
 27      unsigned not_below = diagram.size() - 1;
 28      // If outside the range of diagram, extend begin/end.
 29      if (size < diagram[not_above].size) return {diagram[not_above].fee, 1};
 30      if (size > diagram[not_below].size) return {diagram[not_below].fee, 1};
 31      // Perform bisection search to locate the diagram segment that size is in.
 32      while (not_below > not_above + 1) {
 33          unsigned mid = (not_below + not_above) / 2;
 34          if (diagram[mid].size <= size) not_above = mid;
 35          if (diagram[mid].size >= size) not_below = mid;
 36      }
 37      // If the size matches a transition point between segments, return its fee.
 38      if (not_below == not_above) return {diagram[not_below].fee, 1};
 39      // Otherwise, interpolate.
 40      auto dir_coef = diagram[not_below] - diagram[not_above];
 41      assert(dir_coef.size > 0);
 42      // Let A = diagram[not_above] and B = diagram[not_below]
 43      const auto& point_a = diagram[not_above];
 44      // We want to return:
 45      //     A.fee + (B.fee - A.fee) / (B.size - A.size) * (size - A.size)
 46      //   = A.fee + dir_coef.fee / dir_coef.size * (size - A.size)
 47      //   = (A.fee * dir_coef.size + dir_coef.fee * (size - A.size)) / dir_coef.size
 48      assert(size >= point_a.size);
 49      return {point_a.fee * dir_coef.size + dir_coef.fee * (size - point_a.size), dir_coef.size};
 50  }
 51  
 52  std::weak_ordering CompareFeeFracWithDiagram(const FeeFrac& ff, Span<const FeeFrac> diagram)
 53  {
 54      return FeeRateCompare(FeeFrac{ff.fee, 1}, EvaluateDiagram(ff.size, diagram));
 55  }
 56  
 57  std::partial_ordering CompareDiagrams(Span<const FeeFrac> dia1, Span<const FeeFrac> dia2)
 58  {
 59      bool all_ge = true;
 60      bool all_le = true;
 61      for (const auto p1 : dia1) {
 62          auto cmp = CompareFeeFracWithDiagram(p1, dia2);
 63          if (std::is_lt(cmp)) all_ge = false;
 64          if (std::is_gt(cmp)) all_le = false;
 65      }
 66      for (const auto p2 : dia2) {
 67          auto cmp = CompareFeeFracWithDiagram(p2, dia1);
 68          if (std::is_lt(cmp)) all_le = false;
 69          if (std::is_gt(cmp)) all_ge = false;
 70      }
 71      if (all_ge && all_le) return std::partial_ordering::equivalent;
 72      if (all_ge && !all_le) return std::partial_ordering::greater;
 73      if (!all_ge && all_le) return std::partial_ordering::less;
 74      return std::partial_ordering::unordered;
 75  }
 76  
 77  void PopulateChunks(FuzzedDataProvider& fuzzed_data_provider, std::vector<FeeFrac>& chunks)
 78  {
 79      chunks.clear();
 80  
 81      LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 50)
 82      {
 83          chunks.emplace_back(fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(INT32_MIN>>1, INT32_MAX>>1), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(1, 1000000));
 84      }
 85      return;
 86  }
 87  
 88  } // namespace
 89  
 90  FUZZ_TARGET(build_and_compare_feerate_diagram)
 91  {
 92      // Generate a random set of chunks
 93      FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
 94      std::vector<FeeFrac> chunks1, chunks2;
 95      FeeFrac empty{0, 0};
 96  
 97      PopulateChunks(fuzzed_data_provider, chunks1);
 98      PopulateChunks(fuzzed_data_provider, chunks2);
 99  
100      std::vector<FeeFrac> diagram1{BuildDiagramFromChunks(chunks1)};
101      std::vector<FeeFrac> diagram2{BuildDiagramFromChunks(chunks2)};
102  
103      assert(diagram1.front() == empty);
104      assert(diagram2.front() == empty);
105  
106      auto real = CompareFeerateDiagram(diagram1, diagram2);
107      auto sim = CompareDiagrams(diagram1, diagram2);
108      assert(real == sim);
109  
110      // Do explicit evaluation at up to 1000 points, and verify consistency with the result.
111      LIMITED_WHILE(fuzzed_data_provider.remaining_bytes(), 1000) {
112          int32_t size = fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(0, diagram2.back().size);
113          auto eval1 = EvaluateDiagram(size, diagram1);
114          auto eval2 = EvaluateDiagram(size, diagram2);
115          auto cmp = FeeRateCompare(eval1, eval2);
116          if (std::is_lt(cmp)) assert(!std::is_gt(real));
117          if (std::is_gt(cmp)) assert(!std::is_lt(real));
118      }
119  }