feefrac.cpp
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(FeeRateCompare(fr1, fr2) == cmp_feerate); 88 assert((fr1 << fr2) == std::is_lt(cmp_feerate)); 89 assert((fr1 >> 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((fr1 <=> fr2) == cmp_total); 102 assert((fr1 < fr2) == std::is_lt(cmp_total)); 103 assert((fr1 > fr2) == std::is_gt(cmp_total)); 104 assert((fr1 <= fr2) == std::is_lteq(cmp_total)); 105 assert((fr1 >= fr2) == std::is_gteq(cmp_total)); 106 assert((fr1 == fr2) == std::is_eq(cmp_total)); 107 assert((fr1 != 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 }