Bitcoin Core 29.99.0
P2P Digital Currency
feefrac.cpp
Go to the documentation of this file.
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>
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
17namespace {
18
20const auto MAX_ABS_INT64 = arith_uint256{1} << 63;
21
23arith_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
38arith_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
49std::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
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
110FUZZ_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
158FUZZ_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, (uint32_t)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}
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
CAmount GetFee(uint32_t num_bytes) const
Return the fee in satoshis for the given vsize in vbytes.
Definition: feerate.cpp:23
T ConsumeIntegralInRange(T min, T max)
256-bit unsigned big integer.
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:39
int64_t EvaluateFeeDown(int32_t at_size) const noexcept
Compute the fee for a given size at_size using this object's feerate, rounding down.
Definition: feefrac.h:220
static int64_t DivFallback(std::pair< int64_t, uint32_t > n, int32_t d, bool round_down) noexcept
Helper function for 96/32 signed division, rounding towards negative infinity (if round_down) or posi...
Definition: feefrac.h:58
int64_t EvaluateFeeUp(int32_t at_size) const noexcept
Compute the fee for a given size at_size using this object's feerate, rounding up.
Definition: feefrac.h:222
static constexpr auto Div
Definition: feefrac.h:103
static constexpr auto Mul
Definition: feefrac.h:102
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
Definition: feefrac.h:119
static std::pair< int64_t, uint32_t > MulFallback(int64_t a, int32_t b) noexcept
Helper function for 32*64 signed multiplication, returning an unspecified but totally ordered type.
Definition: feefrac.h:43
FUZZ_TARGET(feefrac)
Definition: feefrac.cpp:69
#define expect(bit)
assert(!tx.IsCoinBase())