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 <util/feefrac.h>
6 : : #include <test/fuzz/FuzzedDataProvider.h>
7 : : #include <test/fuzz/fuzz.h>
8 : : #include <test/fuzz/util.h>
9 : :
10 : : #include <compare>
11 : : #include <cstdint>
12 : : #include <iostream>
13 : :
14 : : namespace {
15 : :
16 : : /** Compute a * b, represented in 4x32 bits, highest limb first. */
17 : 80 : std::array<uint32_t, 4> Mul128(uint64_t a, uint64_t b)
18 : : {
19 : 80 : std::array<uint32_t, 4> ret{0, 0, 0, 0};
20 : :
21 : : /** Perform ret += v << (32 * pos), at 128-bit precision. */
22 : 400 : auto add_fn = [&](uint64_t v, int pos) {
23 : 320 : uint64_t accum{0};
24 [ + + ]: 1280 : for (int i = 0; i + pos < 4; ++i) {
25 : : // Add current value at limb pos in ret.
26 [ + + ]: 960 : accum += ret[3 - pos - i];
27 : : // Add low or high half of v.
28 [ + + ]: 960 : if (i == 0) accum += v & 0xffffffff;
29 [ + + ]: 960 : if (i == 1) accum += v >> 32;
30 : : // Store lower half of result in limb pos in ret.
31 : 960 : ret[3 - pos - i] = accum & 0xffffffff;
32 : : // Leave carry in accum.
33 : 960 : accum >>= 32;
34 : : }
35 : : // Make sure no overflow.
36 [ - + ]: 320 : assert(accum == 0);
37 : 400 : };
38 : :
39 : : // Multiply the 4 individual limbs (schoolbook multiply, with base 2^32).
40 : 80 : add_fn((a & 0xffffffff) * (b & 0xffffffff), 0);
41 : 80 : add_fn((a >> 32) * (b & 0xffffffff), 1);
42 : 80 : add_fn((a & 0xffffffff) * (b >> 32), 1);
43 : 80 : add_fn((a >> 32) * (b >> 32), 2);
44 : 80 : return ret;
45 : : }
46 : :
47 : : /* comparison helper for std::array */
48 : 40 : std::strong_ordering compare_arrays(const std::array<uint32_t, 4>& a, const std::array<uint32_t, 4>& b) {
49 [ + + ]: 109 : for (size_t i = 0; i < a.size(); ++i) {
50 [ + + + + ]: 103 : if (a[i] != b[i]) return a[i] <=> b[i];
51 : : }
52 : 6 : return std::strong_ordering::equal;
53 : : }
54 : :
55 : 43 : std::strong_ordering MulCompare(int64_t a1, int64_t a2, int64_t b1, int64_t b2)
56 : : {
57 : : // Compute and compare signs.
58 [ + + + + : 58 : int sign_a = (a1 == 0 ? 0 : a1 < 0 ? -1 : 1) * (a2 == 0 ? 0 : a2 < 0 ? -1 : 1);
+ + - + ]
59 [ + + + + : 48 : int sign_b = (b1 == 0 ? 0 : b1 < 0 ? -1 : 1) * (b2 == 0 ? 0 : b2 < 0 ? -1 : 1);
+ + + + ]
60 [ + + + + ]: 43 : if (sign_a != sign_b) return sign_a <=> sign_b;
61 : :
62 : : // Compute absolute values.
63 : 40 : uint64_t abs_a1 = static_cast<uint64_t>(a1), abs_a2 = static_cast<uint64_t>(a2);
64 : 40 : uint64_t abs_b1 = static_cast<uint64_t>(b1), abs_b2 = static_cast<uint64_t>(b2);
65 : : // Use (~x + 1) instead of the equivalent (-x) to silence the linter; mod 2^64 behavior is
66 : : // intentional here.
67 [ + + ]: 40 : if (a1 < 0) abs_a1 = ~abs_a1 + 1;
68 [ + + ]: 40 : if (a2 < 0) abs_a2 = ~abs_a2 + 1;
69 [ + + ]: 40 : if (b1 < 0) abs_b1 = ~abs_b1 + 1;
70 [ + + ]: 40 : if (b2 < 0) abs_b2 = ~abs_b2 + 1;
71 : :
72 : : // Compute products of absolute values.
73 : 40 : auto mul_abs_a = Mul128(abs_a1, abs_a2);
74 : 40 : auto mul_abs_b = Mul128(abs_b1, abs_b2);
75 [ + + ]: 40 : if (sign_a < 0) {
76 : 11 : return compare_arrays(mul_abs_b, mul_abs_a);
77 : : } else {
78 : 29 : return compare_arrays(mul_abs_a, mul_abs_b);
79 : : }
80 : : }
81 : :
82 : : } // namespace
83 : :
84 [ + - ]: 455 : FUZZ_TARGET(feefrac)
85 : : {
86 : 43 : FuzzedDataProvider provider(buffer.data(), buffer.size());
87 : :
88 : 43 : int64_t f1 = provider.ConsumeIntegral<int64_t>();
89 : 43 : int32_t s1 = provider.ConsumeIntegral<int32_t>();
90 [ + + ]: 43 : if (s1 == 0) f1 = 0;
91 : 43 : FeeFrac fr1(f1, s1);
92 : 43 : assert(fr1.IsEmpty() == (s1 == 0));
93 : :
94 : 43 : int64_t f2 = provider.ConsumeIntegral<int64_t>();
95 : 43 : int32_t s2 = provider.ConsumeIntegral<int32_t>();
96 [ + + ]: 43 : if (s2 == 0) f2 = 0;
97 : 43 : FeeFrac fr2(f2, s2);
98 : 43 : assert(fr2.IsEmpty() == (s2 == 0));
99 : :
100 : : // Feerate comparisons
101 : 43 : auto cmp_feerate = MulCompare(f1, s2, f2, s1);
102 [ + - ]: 43 : assert(FeeRateCompare(fr1, fr2) == cmp_feerate);
103 [ - + ]: 43 : assert((fr1 << fr2) == std::is_lt(cmp_feerate));
104 [ - + ]: 43 : assert((fr1 >> fr2) == std::is_gt(cmp_feerate));
105 : :
106 : : // Compare with manual invocation of FeeFrac::Mul.
107 [ + + + + ]: 43 : auto cmp_mul = FeeFrac::Mul(f1, s2) <=> FeeFrac::Mul(f2, s1);
108 [ - + ]: 43 : assert(cmp_mul == cmp_feerate);
109 : :
110 : : // Same, but using FeeFrac::MulFallback.
111 [ - + ]: 43 : auto cmp_fallback = FeeFrac::MulFallback(f1, s2) <=> FeeFrac::MulFallback(f2, s1);
112 [ - + ]: 43 : assert(cmp_fallback == cmp_feerate);
113 : :
114 : : // Total order comparisons
115 [ + + + - : 43 : auto cmp_total = std::is_eq(cmp_feerate) ? (s2 <=> s1) : cmp_feerate;
+ - ]
116 [ - + ]: 43 : assert((fr1 <=> fr2) == cmp_total);
117 [ - + ]: 43 : assert((fr1 < fr2) == std::is_lt(cmp_total));
118 [ - + ]: 43 : assert((fr1 > fr2) == std::is_gt(cmp_total));
119 [ - + ]: 43 : assert((fr1 <= fr2) == std::is_lteq(cmp_total));
120 [ - + ]: 43 : assert((fr1 >= fr2) == std::is_gteq(cmp_total));
121 [ + + - + ]: 86 : assert((fr1 == fr2) == std::is_eq(cmp_total));
122 [ + + - + ]: 86 : assert((fr1 != fr2) == std::is_neq(cmp_total));
123 : 43 : }
|
