feefrac.cpp raw
1 // Copyright (c) 2024-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 <arith_uint256.h>
6 #include <policy/feerate.h>
7 #include <util/feefrac.h>
8 #include <test/fuzz/FuzzedDataProvider.h>
9 #include <test/fuzz/fuzz.h>
10 #include <test/fuzz/util.h>
11
12 #include <compare>
13 #include <cmath>
14 #include <cstdint>
15 #include <iostream>
16
17 namespace {
18
19 /** The maximum absolute value of an int64_t, as an arith_uint256 (2^63). */
20 const auto MAX_ABS_INT64 = arith_uint256{1} << 63;
21
22 /** Construct an arith_uint256 whose value equals abs(x). */
23 arith_uint256 Abs256(int64_t x)
24 {
25 if (x >= 0) {
26 // For positive numbers, pass through the value.
27 return arith_uint256{static_cast<uint64_t>(x)};
28 } else if (x > std::numeric_limits<int64_t>::min()) {
29 // For negative numbers, negate first.
30 return arith_uint256{static_cast<uint64_t>(-x)};
31 } else {
32 // Special case for x == -2^63 (for which -x results in integer overflow).
33 return MAX_ABS_INT64;
34 }
35 }
36
37 /** Construct an arith_uint256 whose value equals abs(x), for 96-bit x. */
38 arith_uint256 Abs256(std::pair<int64_t, uint32_t> x)
39 {
40 if (x.first >= 0) {
41 // x.first and x.second are both non-negative; sum their absolute values.
42 return (Abs256(x.first) << 32) + Abs256(x.second);
43 } else {
44 // x.first is negative and x.second is non-negative; subtract the absolute values.
45 return (Abs256(x.first) << 32) - Abs256(x.second);
46 }
47 }
48
49 std::strong_ordering MulCompare(int64_t a1, int64_t a2, int64_t b1, int64_t b2)
50 {
51 // Compute and compare signs.
52 int sign_a = (a1 == 0 ? 0 : a1 < 0 ? -1 : 1) * (a2 == 0 ? 0 : a2 < 0 ? -1 : 1);
53 int sign_b = (b1 == 0 ? 0 : b1 < 0 ? -1 : 1) * (b2 == 0 ? 0 : b2 < 0 ? -1 : 1);
54 if (sign_a != sign_b) return sign_a <=> sign_b;
55
56 // Compute absolute values of products.
57 auto mul_abs_a = Abs256(a1) * Abs256(a2), mul_abs_b = Abs256(b1) * Abs256(b2);
58
59 // Compute products of absolute values.
60 if (sign_a < 0) {
61 return mul_abs_b <=> mul_abs_a;
62 } else {
63 return mul_abs_a <=> mul_abs_b;
64 }
65 }
66
67 } // namespace
68
69 FUZZ_TARGET(feefrac)
70 {
71 FuzzedDataProvider provider(buffer.data(), buffer.size());
72
73 int64_t f1 = provider.ConsumeIntegral<int64_t>();
74 int32_t s1 = provider.ConsumeIntegral<int32_t>();
75 if (s1 == 0) f1 = 0;
76 FeeFrac fr1(f1, s1);
77 assert(fr1.IsEmpty() == (s1 == 0));
78
79 int64_t f2 = provider.ConsumeIntegral<int64_t>();
80 int32_t s2 = provider.ConsumeIntegral<int32_t>();
81 if (s2 == 0) f2 = 0;
82 FeeFrac fr2(f2, s2);
83 assert(fr2.IsEmpty() == (s2 == 0));
84
85 // Feerate comparisons
86 auto cmp_feerate = MulCompare(f1, s2, f2, s1);
87 assert((ByRatio{fr1} <=> ByRatio{fr2}) == cmp_feerate);
88 assert((ByRatio{fr1} < ByRatio{fr2}) == std::is_lt(cmp_feerate));
89 assert((ByRatio{fr1} > ByRatio{fr2}) == std::is_gt(cmp_feerate));
90
91 // Compare with manual invocation of FeeFrac::Mul.
92 auto cmp_mul = FeeFrac::Mul(f1, s2) <=> FeeFrac::Mul(f2, s1);
93 assert(cmp_mul == cmp_feerate);
94
95 // Same, but using FeeFrac::MulFallback.
96 auto cmp_fallback = FeeFrac::MulFallback(f1, s2) <=> FeeFrac::MulFallback(f2, s1);
97 assert(cmp_fallback == cmp_feerate);
98
99 // Total order comparisons
100 auto cmp_total = std::is_eq(cmp_feerate) ? (s2 <=> s1) : cmp_feerate;
101 assert((ByRatioNegSize{fr1} <=> ByRatioNegSize{fr2}) == cmp_total);
102 assert((ByRatioNegSize{fr1} < ByRatioNegSize{fr2}) == std::is_lt(cmp_total));
103 assert((ByRatioNegSize{fr1} > ByRatioNegSize{fr2}) == std::is_gt(cmp_total));
104 assert((ByRatioNegSize{fr1} <= ByRatioNegSize{fr2}) == std::is_lteq(cmp_total));
105 assert((ByRatioNegSize{fr1} >= ByRatioNegSize{fr2}) == std::is_gteq(cmp_total));
106 assert((ByRatioNegSize{fr1} == ByRatioNegSize{fr2}) == std::is_eq(cmp_total));
107 assert((ByRatioNegSize{fr1} != ByRatioNegSize{fr2}) == std::is_neq(cmp_total));
108 }
109
110 FUZZ_TARGET(feefrac_div_fallback)
111 {
112 // Verify the behavior of FeeFrac::DivFallback over all possible inputs.
113
114 // Construct a 96-bit signed value num, a positive 31-bit value den, and rounding mode.
115 FuzzedDataProvider provider(buffer.data(), buffer.size());
116 auto num_high = provider.ConsumeIntegral<int64_t>();
117 auto num_low = provider.ConsumeIntegral<uint32_t>();
118 std::pair<int64_t, uint32_t> num{num_high, num_low};
119 auto den = provider.ConsumeIntegralInRange<int32_t>(1, std::numeric_limits<int32_t>::max());
120 auto round_down = provider.ConsumeBool();
121
122 // Predict the sign of the actual result.
123 bool is_negative = num_high < 0;
124 // Evaluate absolute value using arith_uint256. If the actual result is negative and we are
125 // rounding down, or positive and we are rounding up, the absolute value of the quotient is
126 // the rounded-up quotient of the absolute values.
127 auto num_abs = Abs256(num);
128 auto den_abs = Abs256(den);
129 auto quot_abs = (is_negative == round_down) ?
130 (num_abs + den_abs - 1) / den_abs :
131 num_abs / den_abs;
132
133 // If the result is not representable by an int64_t, bail out.
134 if ((is_negative && quot_abs > MAX_ABS_INT64) || (!is_negative && quot_abs >= MAX_ABS_INT64)) {
135 return;
136 }
137
138 // Verify the behavior of FeeFrac::DivFallback.
139 auto res = FeeFrac::DivFallback(num, den, round_down);
140 assert(res == 0 || (res < 0) == is_negative);
141 assert(Abs256(res) == quot_abs);
142
143 // Compare approximately with floating-point.
144 long double expect = round_down ? std::floor(num_high * 4294967296.0L + num_low) / den
145 : std::ceil(num_high * 4294967296.0L + num_low) / den;
146 // Expect to be accurate within 50 bits of precision, +- 1 sat.
147 if (expect == 0.0L) {
148 assert(res >= -1 && res <= 1);
149 } else if (expect > 0.0L) {
150 assert(res >= expect * 0.999999999999999L - 1.0L);
151 assert(res <= expect * 1.000000000000001L + 1.0L);
152 } else {
153 assert(res >= expect * 1.000000000000001L - 1.0L);
154 assert(res <= expect * 0.999999999999999L + 1.0L);
155 }
156 }
157
158 FUZZ_TARGET(feefrac_mul_div)
159 {
160 // Verify the behavior of:
161 // - The combination of FeeFrac::Mul + FeeFrac::Div.
162 // - The combination of FeeFrac::MulFallback + FeeFrac::DivFallback.
163 // - FeeFrac::Evaluate.
164
165 // Construct a 32-bit signed multiplicand, a 64-bit signed multiplicand, a positive 31-bit
166 // divisor, and a rounding mode.
167 FuzzedDataProvider provider(buffer.data(), buffer.size());
168 auto mul32 = provider.ConsumeIntegral<int32_t>();
169 auto mul64 = provider.ConsumeIntegral<int64_t>();
170 auto div = provider.ConsumeIntegralInRange<int32_t>(1, std::numeric_limits<int32_t>::max());
171 auto round_down = provider.ConsumeBool();
172
173 // Predict the sign of the overall result.
174 bool is_negative = ((mul32 < 0) && (mul64 > 0)) || ((mul32 > 0) && (mul64 < 0));
175 // Evaluate absolute value using arith_uint256. If the actual result is negative and we are
176 // rounding down or positive and we rounding up, the absolute value of the quotient is the
177 // rounded-up quotient of the absolute values.
178 auto prod_abs = Abs256(mul32) * Abs256(mul64);
179 auto div_abs = Abs256(div);
180 auto quot_abs = (is_negative == round_down) ?
181 (prod_abs + div_abs - 1) / div_abs :
182 prod_abs / div_abs;
183
184 // If the result is not representable by an int64_t, bail out.
185 if ((is_negative && quot_abs > MAX_ABS_INT64) || (!is_negative && quot_abs >= MAX_ABS_INT64)) {
186 // If 0 <= mul32 <= div, then the result is guaranteed to be representable. In the context
187 // of the Evaluate{Down,Up} calls below, this corresponds to 0 <= at_size <= feefrac.size.
188 assert(mul32 < 0 || mul32 > div);
189 return;
190 }
191
192 // Verify the behavior of FeeFrac::Mul + FeeFrac::Div.
193 auto res = FeeFrac::Div(FeeFrac::Mul(mul64, mul32), div, round_down);
194 assert(res == 0 || (res < 0) == is_negative);
195 assert(Abs256(res) == quot_abs);
196
197 // Verify the behavior of FeeFrac::MulFallback + FeeFrac::DivFallback.
198 auto res_fallback = FeeFrac::DivFallback(FeeFrac::MulFallback(mul64, mul32), div, round_down);
199 assert(res == res_fallback);
200
201 // Compare approximately with floating-point.
202 long double expect = round_down ? std::floor(static_cast<long double>(mul32) * mul64 / div)
203 : std::ceil(static_cast<long double>(mul32) * mul64 / div);
204 // Expect to be accurate within 50 bits of precision, +- 1 sat.
205 if (expect == 0.0L) {
206 assert(res >= -1 && res <= 1);
207 } else if (expect > 0.0L) {
208 assert(res >= expect * 0.999999999999999L - 1.0L);
209 assert(res <= expect * 1.000000000000001L + 1.0L);
210 } else {
211 assert(res >= expect * 1.000000000000001L - 1.0L);
212 assert(res <= expect * 0.999999999999999L + 1.0L);
213 }
214
215 // Verify the behavior of FeeFrac::Evaluate{Down,Up}.
216 if (mul32 >= 0) {
217 auto res_fee = round_down ?
218 FeeFrac{mul64, div}.EvaluateFeeDown(mul32) :
219 FeeFrac{mul64, div}.EvaluateFeeUp(mul32);
220 assert(res == res_fee);
221
222 // Compare approximately with CFeeRate.
223 if (mul64 < std::numeric_limits<int64_t>::max() / 1000 &&
224 mul64 > std::numeric_limits<int64_t>::min() / 1000 &&
225 quot_abs < arith_uint256{std::numeric_limits<int64_t>::max() / 1000}) {
226 CFeeRate feerate(mul64, div);
227 CAmount feerate_fee{feerate.GetFee(mul32)};
228 auto allowed_gap = static_cast<int64_t>(mul32 / 1000 + 3 + round_down);
229 assert(feerate_fee - res_fee >= -allowed_gap);
230 assert(feerate_fee - res_fee <= allowed_gap);
231 }
232 }
233 }
234