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