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 : }
|