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