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