LCOV - code coverage report
Current view: top level - src/test/fuzz - feeratediagram.cpp (source / functions) Coverage Total Hit
Test: fuzz_coverage.info Lines: 98.5 % 67 66
Test Date: 2026-11-21 05:38:30 Functions: 100.0 % 7 7
Branches: 71.2 % 104 74

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

Generated by: LCOV version 2.5.0-full