LCOV - code coverage report
Current view: top level - src/test/fuzz - feefrac.cpp (source / functions) Coverage Total Hit
Test: fuzz_coverage.info Lines: 100.0 % 111 111
Test Date: 2026-11-17 05:46:53 Functions: 100.0 % 9 9
Branches: 76.9 % 156 120

             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                 :             : }
        

Generated by: LCOV version 2.5.0-full