Branch data Line data Source code
1 : : // Copyright (c) 2024 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 : 615 : arith_uint256 Abs256(int64_t x)
24 : : {
25 [ + + ]: 615 : if (x >= 0) {
26 : : // For positive numbers, pass through the value.
27 : 362 : return arith_uint256{static_cast<uint64_t>(x)};
28 [ + + ]: 253 : } else if (x > std::numeric_limits<int64_t>::min()) {
29 : : // For negative numbers, negate first.
30 : 214 : 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 : 615 : return MAX_ABS_INT64;
34 : : }
35 : : }
36 : :
37 : : /** Construct an arith_uint256 whose value equals abs(x), for 96-bit x. */
38 : 73 : arith_uint256 Abs256(std::pair<int64_t, uint32_t> x)
39 : : {
40 [ + + ]: 73 : if (x.first >= 0) {
41 : : // x.first and x.second are both non-negative; sum their absolute values.
42 : 18 : 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 : 55 : return (Abs256(x.first) << 32) - Abs256(x.second);
46 : : }
47 : : }
48 : :
49 : 27 : std::strong_ordering MulCompare(int64_t a1, int64_t a2, int64_t b1, int64_t b2)
50 : : {
51 : : // Compute and compare signs.
52 [ + + + + : 34 : int sign_a = (a1 == 0 ? 0 : a1 < 0 ? -1 : 1) * (a2 == 0 ? 0 : a2 < 0 ? -1 : 1);
+ + - + ]
53 [ + + + + : 29 : int sign_b = (b1 == 0 ? 0 : b1 < 0 ? -1 : 1) * (b2 == 0 ? 0 : b2 < 0 ? -1 : 1);
+ + + + ]
54 [ + + + + ]: 27 : if (sign_a != sign_b) return sign_a <=> sign_b;
55 : :
56 : : // Compute absolute values of products.
57 : 24 : auto mul_abs_a = Abs256(a1) * Abs256(a2), mul_abs_b = Abs256(b1) * Abs256(b2);
58 : :
59 : : // Compute products of absolute values.
60 [ + + ]: 24 : if (sign_a < 0) {
61 : 6 : return mul_abs_b <=> mul_abs_a;
62 : : } else {
63 : 18 : return mul_abs_a <=> mul_abs_b;
64 : : }
65 : : }
66 : :
67 : : } // namespace
68 : :
69 [ + - ]: 471 : FUZZ_TARGET(feefrac)
70 : : {
71 : 27 : FuzzedDataProvider provider(buffer.data(), buffer.size());
72 : :
73 : 27 : int64_t f1 = provider.ConsumeIntegral<int64_t>();
74 : 27 : int32_t s1 = provider.ConsumeIntegral<int32_t>();
75 [ + + ]: 27 : if (s1 == 0) f1 = 0;
76 : 27 : FeeFrac fr1(f1, s1);
77 : 27 : assert(fr1.IsEmpty() == (s1 == 0));
78 : :
79 : 27 : int64_t f2 = provider.ConsumeIntegral<int64_t>();
80 : 27 : int32_t s2 = provider.ConsumeIntegral<int32_t>();
81 [ + + ]: 27 : if (s2 == 0) f2 = 0;
82 : 27 : FeeFrac fr2(f2, s2);
83 : 27 : assert(fr2.IsEmpty() == (s2 == 0));
84 : :
85 : : // Feerate comparisons
86 : 27 : auto cmp_feerate = MulCompare(f1, s2, f2, s1);
87 [ + - ]: 27 : assert(FeeRateCompare(fr1, fr2) == cmp_feerate);
88 [ - + ]: 27 : assert((fr1 << fr2) == std::is_lt(cmp_feerate));
89 [ - + ]: 27 : assert((fr1 >> fr2) == std::is_gt(cmp_feerate));
90 : :
91 : : // Compare with manual invocation of FeeFrac::Mul.
92 [ + + + + ]: 27 : auto cmp_mul = FeeFrac::Mul(f1, s2) <=> FeeFrac::Mul(f2, s1);
93 [ - + ]: 27 : assert(cmp_mul == cmp_feerate);
94 : :
95 : : // Same, but using FeeFrac::MulFallback.
96 [ - + ]: 27 : auto cmp_fallback = FeeFrac::MulFallback(f1, s2) <=> FeeFrac::MulFallback(f2, s1);
97 [ - + ]: 27 : assert(cmp_fallback == cmp_feerate);
98 : :
99 : : // Total order comparisons
100 [ + + + - : 27 : auto cmp_total = std::is_eq(cmp_feerate) ? (s2 <=> s1) : cmp_feerate;
+ - ]
101 [ - + ]: 27 : assert((fr1 <=> fr2) == cmp_total);
102 [ - + ]: 27 : assert((fr1 < fr2) == std::is_lt(cmp_total));
103 [ - + ]: 27 : assert((fr1 > fr2) == std::is_gt(cmp_total));
104 [ - + ]: 27 : assert((fr1 <= fr2) == std::is_lteq(cmp_total));
105 [ - + ]: 27 : assert((fr1 >= fr2) == std::is_gteq(cmp_total));
106 [ + + - + ]: 54 : assert((fr1 == fr2) == std::is_eq(cmp_total));
107 [ + + - + ]: 54 : assert((fr1 != fr2) == std::is_neq(cmp_total));
108 : 27 : }
109 : :
110 [ + - ]: 517 : 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 : 73 : FuzzedDataProvider provider(buffer.data(), buffer.size());
116 : 73 : auto num_high = provider.ConsumeIntegral<int64_t>();
117 : 73 : auto num_low = provider.ConsumeIntegral<uint32_t>();
118 : 73 : std::pair<int64_t, uint32_t> num{num_high, num_low};
119 : 73 : auto den = provider.ConsumeIntegralInRange<int32_t>(1, std::numeric_limits<int32_t>::max());
120 : 73 : auto round_down = provider.ConsumeBool();
121 : :
122 : : // Predict the sign of the actual result.
123 : 73 : 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 : 73 : auto num_abs = Abs256(num);
128 : 73 : auto den_abs = Abs256(den);
129 [ + + ]: 73 : auto quot_abs = (is_negative == round_down) ?
130 : 18 : (num_abs + den_abs - 1) / den_abs :
131 : 73 : num_abs / den_abs;
132 : :
133 : : // If the result is not representable by an int64_t, bail out.
134 [ + + + + : 73 : if ((is_negative && quot_abs > MAX_ABS_INT64) || (!is_negative && quot_abs >= MAX_ABS_INT64)) {
+ + ]
135 : 47 : return;
136 : : }
137 : :
138 : : // Verify the behavior of FeeFrac::DivFallback.
139 : 26 : auto res = FeeFrac::DivFallback(num, den, round_down);
140 [ + + - + ]: 26 : assert(res == 0 || (res < 0) == is_negative);
141 [ - + ]: 26 : assert(Abs256(res) == quot_abs);
142 : :
143 : : // Compare approximately with floating-point.
144 [ + + ]: 26 : long double expect = round_down ? std::floor(num_high * 4294967296.0L + num_low) / den
145 : 25 : : std::ceil(num_high * 4294967296.0L + num_low) / den;
146 : : // Expect to be accurate within 50 bits of precision, +- 1 sat.
147 [ + + ]: 26 : if (expect == 0.0L) {
148 [ - + ]: 1 : assert(res >= -1 && res <= 1);
149 [ + + ]: 25 : } else if (expect > 0.0L) {
150 [ - + ]: 8 : assert(res >= expect * 0.999999999999999L - 1.0L);
151 [ - + ]: 8 : assert(res <= expect * 1.000000000000001L + 1.0L);
152 : : } else {
153 [ - + ]: 17 : assert(res >= expect * 1.000000000000001L - 1.0L);
154 [ - + ]: 17 : assert(res <= expect * 0.999999999999999L + 1.0L);
155 : : }
156 : : }
157 : :
158 [ + - ]: 523 : 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 : 79 : FuzzedDataProvider provider(buffer.data(), buffer.size());
168 : 79 : auto mul32 = provider.ConsumeIntegral<int32_t>();
169 : 79 : auto mul64 = provider.ConsumeIntegral<int64_t>();
170 : 79 : auto div = provider.ConsumeIntegralInRange<int32_t>(1, std::numeric_limits<int32_t>::max());
171 : 79 : auto round_down = provider.ConsumeBool();
172 : :
173 : : // Predict the sign of the overall result.
174 [ + + + + ]: 79 : 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 : 79 : auto prod_abs = Abs256(mul32) * Abs256(mul64);
179 : 79 : auto div_abs = Abs256(div);
180 [ + + ]: 79 : auto quot_abs = (is_negative == round_down) ?
181 : 53 : (prod_abs + div_abs - 1) / div_abs :
182 : 79 : prod_abs / div_abs;
183 : :
184 : : // If the result is not representable by an int64_t, bail out.
185 [ + + + + : 79 : 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 [ - + ]: 42 : assert(mul32 < 0 || mul32 > div);
189 : : return;
190 : : }
191 : :
192 : : // Verify the behavior of FeeFrac::Mul + FeeFrac::Div.
193 : 37 : auto res = FeeFrac::Div(FeeFrac::Mul(mul64, mul32), div, round_down);
194 [ + + - + ]: 37 : assert(res == 0 || (res < 0) == is_negative);
195 [ - + ]: 37 : assert(Abs256(res) == quot_abs);
196 : :
197 : : // Verify the behavior of FeeFrac::MulFallback + FeeFrac::DivFallback.
198 : 37 : auto res_fallback = FeeFrac::DivFallback(FeeFrac::MulFallback(mul64, mul32), div, round_down);
199 [ - + ]: 37 : assert(res == res_fallback);
200 : :
201 : : // Compare approximately with floating-point.
202 [ + + ]: 37 : long double expect = round_down ? std::floor(static_cast<long double>(mul32) * mul64 / div)
203 : 33 : : std::ceil(static_cast<long double>(mul32) * mul64 / div);
204 : : // Expect to be accurate within 50 bits of precision, +- 1 sat.
205 [ + + ]: 37 : if (expect == 0.0L) {
206 [ - + ]: 7 : assert(res >= -1 && res <= 1);
207 [ + + ]: 30 : } else if (expect > 0.0L) {
208 [ - + ]: 21 : assert(res >= expect * 0.999999999999999L - 1.0L);
209 [ - + ]: 21 : assert(res <= expect * 1.000000000000001L + 1.0L);
210 : : } else {
211 [ - + ]: 9 : assert(res >= expect * 1.000000000000001L - 1.0L);
212 [ - + ]: 9 : assert(res <= expect * 0.999999999999999L + 1.0L);
213 : : }
214 : :
215 : : // Verify the behavior of FeeFrac::Evaluate{Down,Up}.
216 [ + + ]: 37 : if (mul32 >= 0) {
217 [ + + ]: 28 : auto res_fee = round_down ?
218 : 3 : FeeFrac{mul64, div}.EvaluateFeeDown(mul32) :
219 : 25 : FeeFrac{mul64, div}.EvaluateFeeUp(mul32);
220 [ - + ]: 28 : assert(res == res_fee);
221 : :
222 : : // Compare approximately with CFeeRate.
223 : 28 : if (mul64 < std::numeric_limits<int64_t>::max() / 1000 &&
224 [ + + + + ]: 47 : mul64 > std::numeric_limits<int64_t>::min() / 1000 &&
225 : 19 : quot_abs < arith_uint256{std::numeric_limits<int64_t>::max() / 1000}) {
226 : 17 : CFeeRate feerate(mul64, (uint32_t)div);
227 : 17 : CAmount feerate_fee{feerate.GetFee(mul32)};
228 : 17 : auto allowed_gap = static_cast<int64_t>(mul32 / 1000 + 3 + round_down);
229 [ - + ]: 17 : assert(feerate_fee - res_fee >= -allowed_gap);
230 [ - + ]: 17 : assert(feerate_fee - res_fee <= allowed_gap);
231 : : }
232 : : }
233 : : }
|
