feefrac: add support for evaluating at given size #30535

sipa commented at 7:34 PM on July 26, 2024: member

The FeeFrac type represents a fraction, intended to be used for sats/vbyte or sats/WU. This PR adds functionality to evaluate that feerate for a given size, in order to obtain the fee it corresponds with (rounding down, or rounding up).

The motivation here is being able to do accurate feerate evaluations in cluster mempool block building heuristics (where rounding down is needed), but in principle this makes it possible to use FeeFrac as a more accurate replacement for CFeeRate (where for feerate estimation rounding up is desirable). Because of this, both rounding modes are implemented.

Unit tests are included for known-correct values, plus a fuzz test that verifies the result using arith_uint256.

DrahtBot commented at 7:34 PM on July 26, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/30535.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	l0rinc, ismaelsadeeq, glozow
Concept ACK	tdb3, ceffikhan, brunoerg, Christewart, murchandamus, instagibbs, ryanofsky
Stale ACK	laanwj

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

sipa force-pushed on Jul 26, 2024

ismaelsadeeq commented at 9:03 PM on July 26, 2024: member

Concept ACK

I think we should also have GetFeePerK or GetFeePerS method in FeeFrac similar to CFeeRate

sipa commented at 9:52 PM on July 27, 2024: member

@ismaelsadeeq It's a possibility, if we'd want to replace CFeeRate entirely. Another possibility is keeping CFeeRate and its interface, but make it be an encapsulated FeeFrac object (that e.g. on serialization converts to sats/kvb, but that otherwise keeps exact fractions).

sipa force-pushed on Jul 28, 2024

tdb3 commented at 6:32 PM on July 28, 2024: contributor

Concept ACK Seems like a helpful improvement. Would like to circle back to take a deeper look. Out of curiosity, why the adjustment from 0x200000004 to 0x200000000? (nothing immediately popped out to me)

sipa commented at 6:41 PM on July 28, 2024: member

@tdb3 0x200000004 is the more accurate number (it equals floor((2^64-1)/(2^31-1))) but 0x200000000 obviously also works, and:

It compiles to slightly simpler asm code (it computes fee >> 33, rather than comparing fee with a literal).
The difference is so small that it shouldn't matter.
I would think it's more obviously correct to a reviewer.

in src/util/feefrac.h:197 in 5a4c01c4b2 outdated

 148 | +    /** Compute, at this object's feerate, how much fee does at_size correspond to.
 149 | +     *
 150 | +     * This effectively corresponds to evaluating (this->fee * at_size) / this->size, with the
 151 | +     * result rounded down (even for negative feerates).
 152 | +     *
 153 | +     * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This

l0rinc commented at 7:14 PM on July 28, 2024:

nit: if you think the preconditions already stated in the Assumes is worth repeating in the comments, consider swapping their order to match the order in the code.

sipa commented at 8:21 PM on July 29, 2024:

Done.

in src/util/feefrac.h:181 in 5a4c01c4b2 outdated

 176 | +            // this division to round down however, while the / operator rounds towards zero. In
 177 | +            // case low64 is negative and not a multiple of size, we thus need a correction.
 178 | +            int64_t low64_div = low64 / size;
 179 | +            low64_div -= (low64 % size) < 0;
 180 | +            // Evaluate and return the result
 181 | +            return (high64_div << 32) + low64_div;

l0rinc commented at 5:43 AM on July 29, 2024:

would it make sense to extract this into a DivFallback - and test it independently, like we do with MulFallback? This would make it independently testable and we could extend it to 128 bit division seamlessly, e.g.:

diff --git a/src/util/feefrac.h b/src/util/feefrac.h
--- a/src/util/feefrac.h	(revision 5a4c01c4b29b7a2542e43222fa64cdb4ca6ee3dc)
+++ b/src/util/feefrac.h	(date 1722234628938)
@@ -41,23 +41,56 @@
      *
      * Separate to permit testing on platforms where it isn't actually needed.
      */
-    static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
+    static inline std::pair<int64_t, uint32_t> MulFallback(int64_t high, int32_t low) noexcept
     {
-        // Otherwise, emulate 96-bit multiplication using two 64-bit multiplies.
-        int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
-        int64_t high = (a >> 32) * b;
-        return {high + (low >> 32), static_cast<uint32_t>(low)};
+        // Emulate 96-bit multiplication using two 64-bit multiplies.
+        int64_t low_mul = int64_t{static_cast<uint32_t>(high)} * low;
+        int64_t high_mul = (high >> 32) * low;
+        return {high_mul + (low_mul >> 32), static_cast<uint32_t>(low_mul)};
+    }
+
+    /** Fallback version for Div (see below).
+     *
+     * Separate to permit testing on platforms where it isn't actually needed.
+     */
+    static inline int64_t DivFallback(int64_t high, uint32_t low, int32_t divisor) noexcept
+    {
+        Assume(divisor != 0);
+        // Compute high / divisor, so the result becomes
+        // (low + (high - high_div * divisor) * 2**32) / divisor + (high_div * 2**32).
+        int64_t high_div = high / divisor;
+        // Evaluate the parenthesized expression above, so the result becomes
+        // low64 / divisor + (high_div * 2**32)
+        int64_t low64 = ((high - high_div * divisor) << 32) | low;
+        // Evaluate the division so the result becomes low64_div + high_div * 2**32.
+        int64_t low64_div = low64 / divisor;
+        // Round towards negative infinity
+        low64_div -= (low64 % divisor) < 0;
+        return (high_div << 32) + low64_div;
     }
 
     // Compute a * b, returning an unspecified but totally ordered type.
 #ifdef __SIZEOF_INT128__
     static inline __int128 Mul(int64_t a, int32_t b) noexcept
     {
-        // If __int128 is available, use 128-bit wide multiply.
         return __int128{a} * b;
     }
+
+    // Compute product / divisor, rounding towards negative infinity.
+    static inline int64_t Div(__int128 product, int32_t divisor) noexcept
+    {
+        auto quotient = product / divisor;
+        // Round towards negative infinity
+        quotient -= (product % divisor) < 0;
+        return quotient;
+    }
 #else
     static constexpr auto Mul = MulFallback;
+    // Compute (high << 64 | low) / divisor, rounding towards negative infinity.
+    static inline int64_t Div(std::pair<int64_t, uint32_t> product, int32_t divisor) noexcept
+    {
+        return DivFallback(product.first, product.second, divisor);
+    }
 #endif
 
     int64_t fee;
@@ -162,23 +195,7 @@
             return (uint64_t(fee) * at_size) / uint32_t(size);
         } else {
             // If not, use a custom 96-bit division.
-
-            // Write (this->fee * at_size) as (low32 + high64 * 2**32), so the result can be stated
-            // as (low32 + high64 * 2**32) / this->size.
-            auto [high64, low32] = MulFallback(fee, at_size);
-            // Compute high64 / this->size, so the result becomes
-            // (low32 + (high64 - high64_div * size) * 2**32) / this->size + (high64_div * 2**32).
-            int64_t high64_div = high64 / size;
-            // Evaluate the parenthesized expression above, so the result becomes
-            // low64 / this->size + (high64_div * 2**32)
-            int64_t low64 = ((high64 - high64_div * size) << 32) + low32;
-            // Evaluate the division so the result becomes low64_div + high64_div * 2**32. We need
-            // this division to round down however, while the / operator rounds towards zero. In
-            // case low64 is negative and not a multiple of size, we thus need a correction.
-            int64_t low64_div = low64 / size;
-            low64_div -= (low64 % size) < 0;
-            // Evaluate and return the result
-            return (high64_div << 32) + low64_div;
+            return Div(Mul(fee, at_size), size);
         }
     }
 };

sipa commented at 8:22 PM on July 29, 2024:

I didn't do something like this initially, as the Evaluate / Div operations are far less performance critical than Mul, but I've now adopted code like this (plus adding an __int128-based Div as well) for consistency and testability.

in src/util/feefrac.h:174 in 5a4c01c4b2 outdated

 169 | +            // Compute high64 / this->size, so the result becomes
 170 | +            // (low32 + (high64 - high64_div * size) * 2**32) / this->size + (high64_div * 2**32).
 171 | +            int64_t high64_div = high64 / size;
 172 | +            // Evaluate the parenthesized expression above, so the result becomes
 173 | +            // low64 / this->size + (high64_div * 2**32)
 174 | +            int64_t low64 = ((high64 - high64_div * size) << 32) + low32;

l0rinc commented at 6:41 AM on July 29, 2024:

nit: while the return value needs a +, I think this would work with a | low32 as well (which would provide better documentation about them not overlapping)

sipa commented at 8:23 PM on July 29, 2024:

I'd rather not. I find the use of bitwise operations with signed integers a bit unintuitive.

in src/test/feefrac_tests.cpp:32 in 5a4c01c4b2 outdated

  27 | +    BOOST_CHECK_EQUAL(p1.Evaluate(100000000), 1000000000);
  28 | +    BOOST_CHECK_EQUAL(p1.Evaluate(0x7fffffff), int64_t(0x7fffffff) * 10);
  29 | +
  30 | +    FeeFrac neg{-1001, 100};
  31 | +    BOOST_CHECK_EQUAL(neg.Evaluate(0), 0);
  32 | +    BOOST_CHECK_EQUAL(neg.Evaluate(1), -11);

l0rinc commented at 6:53 AM on July 29, 2024:

how often would we get negative fee in reality? If rounding towards negative infinity just a theoretical exercise or is it an important usecase?

sipa commented at 8:27 PM on July 29, 2024:

I only added the logic for rounding towards negative infinity because of consistency, not because of a hard requirement. I've added a comment too.

But just to clarify, without the correction step, the behavior is essentially arbitrary for negative fees. low64 (now renamed to n_low) can be both positive or negative with negative n (positive when n.second is positive, and n.first is a multiple of d; negative when n.first is non-multiple of d). That's just too hard to specify and test.

l0rinc changes_requested

l0rinc commented at 6:57 AM on July 29, 2024: contributor

I think we could make the code more testable by extracting the 96 bit division like we did for the multiplication

ceffikhan commented at 8:47 AM on July 29, 2024: none

Concept ACK

instagibbs commented at 1:41 PM on July 29, 2024: member

The motivation here is being able to do accurate feerate evaluations in cluster mempool block building heuristics

for end-of-block packing reasons I assume?

glozow commented at 3:51 PM on July 29, 2024: member

Concept ACK

Also concept ack to changing CFeeRate to use a FeeFrac internally. Did it locally to see what the quirks are - CFeeRate rounds up, is that maybe worth matching?

sipa force-pushed on Jul 29, 2024

sipa commented at 9:43 PM on July 29, 2024: member

I've made a number of changes, mostly in response to @paplorinc's suggestion, which involves:

Rewriting all of feefrac's fuzz tests to test against arith_uint256 (rather than using its own ad-hoc 128-bit bigint logic), which also involved adding an arith_uint256::operator<=>.
Separating out a FeeFrac::Div (with FeeFrac::DivFallback, like Mul) for 96-bit division, which is tested directly.
Writing FeeFrac::Evaluate in terms of FeeFrac::Div and FeeFrac::Mul.

In addition, a bunch of comment change and code simplifications.

@instagibbs

The motivation here is being able to do accurate feerate evaluations in cluster mempool block building heuristics

for end-of-block packing reasons I assume?

The thing I have in mind, is the following algorithm for finding out an upper bound on the maximum fee a block template can gather (assuming optimally-linearized clusters):

weight_left = 4000000
fee_collected = 0
for chunk in sorted(mempool.all_chunks, by_decreasing_feerate):
    if chunk.weight <= weight_left:
        weight_left -= chunk.weight
        fee_collected += chunk.fee
    else:
        fee_collected += chunk.Evaluate(weight)
        break

Assuming optimally-linearized clusters, this gives a correct upper bound on total collectable fee, which may be useful in heuristics to determine whether it's worth spending time on searching more for example, or in statistics. It's really a super simple operation, but the multiplication being able to exceed 64-bit integers makes it a whole lot more complicated.

@glozow

Concept ACK

Also concept ack to changing CFeeRate to use a FeeFrac internally. Did it locally to see what the quirks are - CFeeRate rounds up, is that maybe worth matching?

Ha, nice catch. See above why I do actually want rounding-down behavior here. Perhaps we'll need to add a boolean argument for controlling up/down rounding behavior?

DrahtBot added the label CI failed on Jul 30, 2024

DrahtBot removed the label CI failed on Jul 30, 2024

sipa force-pushed on Jul 30, 2024

sipa commented at 4:01 PM on July 30, 2024: member

I have added a commit that splits FeeFrac::Evaluate into an EvaluateDown and an EvaluateUp, corresponding to the rounding modes they implement (plus tests for both behaviors).

in src/util/feefrac.h:75 in 1cc0d5475a outdated

  76 | +        // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
  77 | +        // correction.
  78 | +        int64_t quot_low = n_low / d;
  79 | +        int64_t mod_low = n_low % d;
  80 | +        if (mod_low) [[likely]] {
  81 | +            quot_low += (mod_low > 0) - round_down;

l0rinc commented at 5:27 PM on July 31, 2024:

Looks like this isn't covered by dedicated tests - only by fuzz and on platforms where !__SIZEOF_INT128__, right?

Since the rounding should be the same for both implementations, we could consider pulling the rounding into Evaluate to make sure these lines are always tested:

diff --git a/src/util/feefrac.h b/src/util/feefrac.h
--- a/src/util/feefrac.h	(revision 1cc0d5475a578a8299c24c008c0080a6006cae28)
+++ b/src/util/feefrac.h	(date 1722450548560)
@@ -55,7 +55,7 @@
      * to be consistent for testability reasons.
      *
      * The result must fit in an int64_t, and d must be strictly positive. */
-    static inline int64_t DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down) noexcept
+    static inline std::pair<int64_t, int64_t> DivFallback(std::pair<int64_t, uint32_t> n, int32_t d) noexcept
     {
         Assume(d > 0);
         // Compute quot_high = n.first / d, so the result becomes
@@ -69,13 +69,7 @@
         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
         // correction.
-        int64_t quot_low = n_low / d;
-        int64_t mod_low = n_low % d;
-        if (mod_low) [[likely]] {
-            quot_low += (mod_low > 0) - round_down;
-        }
-        // Combine and return the result
-        return (quot_high << 32) + quot_low;
+        return {(quot_high << 32) + n_low / d, n_low % d};
     }
 
 #ifdef __SIZEOF_INT128__
@@ -90,17 +84,10 @@
      *  version relying on __int128.
      *
      * The result must fit in an int64_t, and d must be strictly positive. */
-    static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
+    static inline std::pair<int64_t, int32_t> Div(__int128 n, int32_t d) noexcept
     {
         Assume(d > 0);
-        // Compute the division.
-        int64_t quot = n / d;
-        int32_t mod = n % d;
-        // Correct result if the / operator above rounded in the wrong direction.
-        if (mod) [[likely]] {
-            quot += (mod > 0) - round_down;
-        }
-        return quot;
+        return {n / d, n % d};
     }
 #else
     static constexpr auto Mul = MulFallback;
@@ -216,7 +203,9 @@
             }
         } else {
             // Otherwise, use Mul and Div.
-            return Div(Mul(fee, at_size), size, RoundDown);
+            auto [quot, mod] = Div(Mul(fee, at_size), size);
+            auto round = (mod > 0) - (mod && RoundDown);
+            return quot + round;
         }
     }

It seems to me both are already using combined division/modulo anyway (i.e. __divmodti4 on gcc), so the performance should be similar https://godbolt.org/z/Es5o8b3qo.

sipa commented at 8:51 PM on July 31, 2024:

Looks like this isn't covered by dedicated tests - only by fuzz and on platforms where !SIZEOF_INT128, right?

The feefrac_mul_div fuzz test tests this code on every platform (only for n inputs which are themselves the product of a 32-bit integer times a 64-bit integer, but given that those are the only ones that matter for production that seems sufficient to me).

Also note that we build fuzz corpora only on platforms that support libfuzzer, but the constructed fuzz inputs then do get tested (in CI even) on other test environments too.

sipa commented at 9:25 PM on July 31, 2024:

Since the rounding should be the same for both implementations, we could consider pulling the rounding into Evaluate to make sure these lines are always tested:

I like that idea, but it's a bigger change than I'm willing to make to this code now.

in src/util/feefrac.h:103 in 1cc0d5475a outdated

 105 | +        int32_t mod = n % d;
 106 | +        // Correct result if the / operator above rounded in the wrong direction.
 107 | +        if (mod) [[likely]] {
 108 | +            quot += (mod > 0) - round_down;
 109 | +        }
 110 | +        return quot;

l0rinc commented at 6:36 PM on July 31, 2024:

If we want to avoid branching here, I think we can avoid the jump i.e.

        test    eax, eax
        je      .L4
        setg    al
        movzx   eax, al
        sub     eax, ebx
        cdqe
        add     rbp, rax

by doing something like

        auto round = (mod > 0) - (mod && round_down);
        return quot + round;

which looks like

        test    eax, eax
        setne   al
        setg    bl
        movzx   eax, al
        and     eax, ecx
        sub     ebx, eax
        movsx   rbx, ebx
        add     rbx, rdx

(see: https://godbolt.org/z/Es5o8b3qo)

sipa commented at 9:23 PM on July 31, 2024:

Neat! Will incorporate.

sipa commented at 10:13 PM on July 31, 2024:

Done.

in src/util/feefrac.h:214 in 1cc0d5475a outdated

 214 | +            } else {
 215 | +                return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
 216 | +            }
 217 | +        } else {
 218 | +            // Otherwise, use Mul and Div.
 219 | +            return Div(Mul(fee, at_size), size, RoundDown);

l0rinc commented at 7:46 PM on July 31, 2024:

+1, feefrac_tests pass if I delete the first part of the if and use this for the small values as well! (would be nice if we could automate this)

sipa commented at 8:52 PM on July 31, 2024:

That is what the feefrac_mul_div test does effectively.

l0rinc commented at 8:58 PM on July 31, 2024:

Does it test return Div(Mul(fee, at_size), size, RoundDown) when fee < 0x200000000? I don't think that can happen in reality, I just tested it to make sure it's correct for small values as well.

sipa commented at 9:00 PM on July 31, 2024:

Yes, it invokes Div(Mul(mul64, mul32), div), which is effectively that.

It's not running this exact line inside Evaluate, but instead contains a copy of the code we want to behave correctly. But please, it's one line.

l0rinc commented at 9:14 PM on July 31, 2024:

But please, it's one line.

+1 meant that I like this, maybe I should use a 👍 next time :)

sipa commented at 9:16 PM on July 31, 2024:

My line of commenting here was in response to your "(would be nice if we could automate this)". My point is that to a large extent, the feefrac_mul_div test does this (even for small values), with the minor limitation that it does it by effectively copying the line rather than invoking it directly (so over time it's possible in theory that the two diverge, and this doesn't remain tested; but right now you need but look at the test and see it does the same thing to get confidence Div/Mul also work for this purpose for small values).

l0rinc commented at 9:27 PM on July 31, 2024:

Thanks!

in src/test/fuzz/feefrac.cpp:181 in 1cc0d5475a outdated

 160 | +    // rounding down or positive and we rounding up, the absolute value of the quotient is the
 161 | +    // rounded-up quotient of the absolute values.
 162 | +    auto prod_abs = Abs256(mul32) * Abs256(mul64);
 163 | +    auto div_abs = Abs256(div);
 164 | +    auto quot_abs = (is_negative == round_down) ?
 165 | +        (prod_abs + div_abs - 1) / div_abs :

l0rinc commented at 7:48 PM on July 31, 2024:

nit: this is very useful way to test the big divisions - but it repeats the production code logic for the small ones.

sipa commented at 8:47 PM on July 31, 2024:

I don't understand what you mean by big and small divisions.

l0rinc commented at 8:54 PM on July 31, 2024:

I meant that in https://github.com/bitcoin/bitcoin/pull/30535/files#diff-09e6cf871236bf03d32cca9405837d9b7927690b2296a2de17c9be6ea0e75959R215 we're using the same A + (B - 1) / B equation for rounding, i.e. the test and production code may be too similar. I think it's fine since the big fee rounding is the more complicated one.

sipa commented at 8:56 PM on July 31, 2024:

Ah, I see, yes. I mean it's really the only way of implementing a rounding-up division that I know. And while conceptually the algorithm is the same, it is being done on arith_uint256 rather than the types used in production.

l0rinc commented at 9:29 PM on July 31, 2024:

Indeed, thanks for checking

in src/test/fuzz/feefrac.cpp:63 in 1cc0d5475a outdated

  71 | +        return mul_abs_a <=> mul_abs_b;
  72 |      }
  73 |  }
  74 |  
  75 | +/** The maximum absolute value of an int64_t, as an arith_uint256 (2^63). */
  76 | +const auto MAX_ABS_INT64 = arith_uint256{1} << 63;

l0rinc commented at 7:50 PM on July 31, 2024:

can we move this to the top to make it available for Abs256?

sipa commented at 10:13 PM on July 31, 2024:

Done.

in src/test/fuzz/feefrac.cpp:28 in 1cc0d5475a outdated

  51 | +    } else if (x > std::numeric_limits<int64_t>::min()) {
  52 | +        // For negative numbers, negate first.
  53 | +        return arith_uint256{static_cast<uint64_t>(-x)};
  54 | +    } else {
  55 | +        // Special case for x == -2^63 (for which -x results in integer overflow).
  56 | +        return arith_uint256{1} << 63;

l0rinc commented at 7:51 PM on July 31, 2024:

        return MAX_ABS_INT64;

sipa commented at 10:13 PM on July 31, 2024:

Done.

in src/util/feefrac.h:196 in 1cc0d5475a outdated

 190 | @@ -144,6 +191,38 @@ struct FeeFrac
 191 |          std::swap(a.fee, b.fee);
 192 |          std::swap(a.size, b.size);
 193 |      }
 194 | +
 195 | +private:
 196 | +    /** Compute, at this object's feerate, how much fee does at_size correspond to.

l0rinc commented at 7:55 PM on July 31, 2024:

nit (sounds a bit weird to me):

    /** Compute the fee for a given `at_size` using this object's feerate.

sipa commented at 10:13 PM on July 31, 2024:

Done.

in src/test/fuzz/feefrac.cpp:162 in 1cc0d5475a outdated

 141 | +
 142 | +FUZZ_TARGET(feefrac_mul_div)
 143 | +{
 144 | +    // Verify the behavior of:
 145 | +    // - The combination of FeeFrac::Mul + FeeFrac::Div.
 146 | +    // - The combination of FeeFrac::MulFallback + FeeFrac::DivFallback.

l0rinc commented at 7:58 PM on July 31, 2024:

how are we testing both? Not on the same platform, right? And we're also testing the small value calculations here, right?

sipa commented at 8:54 PM on July 31, 2024:

The test directly invokes both Div(Mul(mul64, mul32), div) and DivFallback(MulFallback(mul64, mul32), div).

l0rinc commented at 8:58 PM on July 31, 2024:

My mistake, thanks for clarifying

in src/arith_uint256.h:216 in 1cc0d5475a outdated

 210 | @@ -210,13 +211,8 @@ class base_uint
 211 |      friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
 212 |      friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
 213 |      friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
 214 | -    friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; }
 215 | -    friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; }
 216 | -    friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
 217 | -    friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
 218 | -    friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
 219 | +    friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }

l0rinc commented at 7:59 PM on July 31, 2024:

nice!

in src/test/fuzz/feefrac.cpp:56 in bcf879056d outdated

  55 | -    // intentional here.
  56 | -    if (a1 < 0) abs_a1 = ~abs_a1 + 1;
  57 | -    if (a2 < 0) abs_a2 = ~abs_a2 + 1;
  58 | -    if (b1 < 0) abs_b1 = ~abs_b1 + 1;
  59 | -    if (b2 < 0) abs_b2 = ~abs_b2 + 1;
  60 | +    // Compute absolute values of products.

l0rinc commented at 8:16 PM on July 31, 2024:

Is it important to distinguish the 0 values from the positive ones when comparing the signs? If not, maybe we can simplify a bit:

    // Compute and compare signs.
    int sign_a = (a1 < 0) ^ (a2 < 0) ? -1 : 1;
    int sign_b = (b1 < 0) ^ (b2 < 0) ? -1 : 1;
    if (sign_a != sign_b) return sign_a <=> sign_b;

    auto result = Abs256(a1) * Abs256(a2) <=> Abs256(b1) * Abs256(b2);
    return (sign_a >= 0) ? result : 0 <=> result;

sipa commented at 9:38 PM on July 31, 2024:

I believe that's correct, but it's less obviously correct than the existing code IMO, which I think is the more relevant criterion for tests.

l0rinc commented at 9:46 PM on July 31, 2024:

In that case consider only the second part of the suggestion:

    auto result = Abs256(a1) * Abs256(a2) <=> Abs256(b1) * Abs256(b2);
    return (sign_a >= 0) ? result : 0 <=> result;

(obviously non-blocker)

l0rinc commented at 10:10 PM on July 31, 2024:

Or a local lambda, for the first part to make it cleaner:

    auto sign = [](int64_t x) { return x == 0 ? 0 : x < 0 ? -1 : 1; };
    int sign_a = sign(a1) * sign(a2);
    int sign_b = sign(b1) * sign(b2);
    if (sign_a != sign_b) return sign_a <=> sign_b;

sipa commented at 10:14 PM on July 31, 2024:

I prefer not changing this code except to the extent needed for the switch to arith_uint256. The existing code already works.

in src/util/feefrac.h:205 in 80711ef01b outdated

 193 | +     */
 194 | +    int64_t Evaluate(int32_t at_size) const noexcept
 195 | +    {
 196 | +        Assume(size > 0);
 197 | +        Assume(at_size >= 0);
 198 | +        if (fee >= 0 && fee < 0x200000000) [[likely]] {

l0rinc commented at 8:32 PM on July 31, 2024:

would it make sense to add non-fuzz 0x1ffffffff, 0x200000000 and 0x200000001 test cases for this boundary?

sipa commented at 10:14 PM on July 31, 2024:

Done.

l0rinc approved

l0rinc commented at 8:36 PM on July 31, 2024: contributor

ACK 1cc0d5475a578a8299c24c008c0080a6006cae28

I left a few recommendations and questions, was really fun reviewing this change - though it took me a lot of time.

If you think our contributions have affected the change, please consider adding us as co-authors.

DrahtBot requested review from tdb3 on Jul 31, 2024

DrahtBot requested review from glozow on Jul 31, 2024

DrahtBot requested review from ismaelsadeeq on Jul 31, 2024

sipa force-pushed on Jul 31, 2024

l0rinc commented at 7:50 AM on August 1, 2024: contributor

ACK 9590cdd1afc78ff73fdccd2d016075bf40b6b0e2

glozow added the label Utils/log/libs on Aug 2, 2024

brunoerg commented at 1:16 PM on August 6, 2024: contributor

Concept ACK

brunoerg commented at 2:22 PM on August 7, 2024: contributor

I didn't review it in depth but I used this PR to test my "mutation testing tool", which creates mutations based on diff, and the tests are REALLY great! The only two mutants that were not killed seems to be "equivalent mutants", so we can ignore them. See:

Bitcoin Core (#30535 - feefrac: add support for evaluating at given size)

make && ./src/test/test_bitcoin --run_test=feefrac_tests
Mutation score: 94.4% (Excelent)

MUTANTS NOT KILLED

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.22.h
index dbb03bbccc..0930d12846 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.22.h
@@ -201,7 +201,7 @@ struct FeeFrac
     {
         Assume(size > 0);
         Assume(at_size >= 0);
-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
+        if (fee >= 0 && fee <= 0x200000000) [[likely]] {
             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.13.h
index dbb03bbccc..71cb90757e 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.13.h
@@ -201,7 +201,7 @@ struct FeeFrac
     {
         Assume(size > 0);
         Assume(at_size >= 0);
-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
+        if (fee > 0 && fee < 0x200000000) [[likely]] {
             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);

<details> <summary>Killed mutants</summary> <br>

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.27.h
index dbb03bbccc..1f9ca50a5e 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.27.h
@@ -69,7 +69,7 @@ struct FeeFrac
         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
         // correction.
-        int64_t quot_low = n_low / d;
+                int64_t quot_low = (n_low / d) + 1;
         int32_t mod_low = n_low % d;
         quot_low += (mod_low > 0) - (mod_low && round_down);
         // Combine and return the result

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.29.h
index dbb03bbccc..96f39cdd74 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.29.h
@@ -92,7 +92,7 @@ struct FeeFrac
     {
         Assume(d > 0);
         // Compute the division.
-        int64_t quot = n / d;
+                int64_t quot = (n / d) + 1;
         int32_t mod = n % d;
         // Correct result if the / operator above rounded in the wrong direction.
         return quot + (mod > 0) - (mod && round_down);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.23.h
index dbb03bbccc..eb87c9c3b6 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.23.h
@@ -201,7 +201,7 @@ struct FeeFrac
     {
         Assume(size > 0);
         Assume(at_size >= 0);
-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
+                if (fee >= 0 && fee > 0x200000000) [[likely]] {
             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.0.h
index dbb03bbccc..41599bcccd 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.0.h
@@ -216,7 +216,7 @@ struct FeeFrac
 
 public:
     /** Compute the fee for a given size `at_size` using this object's feerate, rounding down. */
-    int64_t EvaluateDown(int32_t at_size) const noexcept { return Evaluate<true>(at_size); }
+        int64_t EvaluateDown(int32_t at_size) const noexcept { return Evaluate<false>(at_size); }
     /** Compute the fee for a given size `at_size` using this object's feerate, rounding up. */
     int64_t EvaluateUp(int32_t at_size) const noexcept { return Evaluate<false>(at_size); }
 };

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.33.h
index dbb03bbccc..7776bb61da 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.33.h
@@ -69,7 +69,7 @@ struct FeeFrac
         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
         // correction.
-        int64_t quot_low = n_low / d;
+                int64_t quot_low = (n_low / d) - 1;
         int32_t mod_low = n_low % d;
         quot_low += (mod_low > 0) - (mod_low && round_down);
         // Combine and return the result

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.16.h
index dbb03bbccc..ec3adc87bf 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.16.h
@@ -71,7 +71,7 @@ struct FeeFrac
         // correction.
         int64_t quot_low = n_low / d;
         int32_t mod_low = n_low % d;
-        quot_low += (mod_low > 0) - (mod_low && round_down);
+                quot_low += (mod_low > 0) - (mod_low || round_down);
         // Combine and return the result
         return (quot_high << 32) + quot_low;
     }

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.12.h
index dbb03bbccc..92848b64d3 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.12.h
@@ -201,7 +201,7 @@ struct FeeFrac
     {
         Assume(size > 0);
         Assume(at_size >= 0);
-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
+                if (fee <= 0 && fee < 0x200000000) [[likely]] {
             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.18.h
index dbb03bbccc..08f5b1fd81 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.18.h
@@ -201,7 +201,7 @@ struct FeeFrac
     {
         Assume(size > 0);
         Assume(at_size >= 0);
-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
+                if (fee >= 0 || fee < 0x200000000) [[likely]] {
             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.4.h
index dbb03bbccc..2177b00401 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.4.h
@@ -92,7 +92,7 @@ struct FeeFrac
     {
         Assume(d > 0);
         // Compute the division.
-        int64_t quot = n / d;
+                int64_t quot = n * d;
         int32_t mod = n % d;
         // Correct result if the / operator above rounded in the wrong direction.
         return quot + (mod > 0) - (mod && round_down);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.24.h
index dbb03bbccc..ac4672aa71 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.24.h
@@ -201,7 +201,7 @@ struct FeeFrac
     {
         Assume(size > 0);
         Assume(at_size >= 0);
-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
+                if (fee >= 0 && fee >= 0x200000000) [[likely]] {
             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.20.h
index dbb03bbccc..abc34f1f78 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.20.h
@@ -95,7 +95,7 @@ struct FeeFrac
         int64_t quot = n / d;
         int32_t mod = n % d;
         // Correct result if the / operator above rounded in the wrong direction.
-        return quot + (mod > 0) - (mod && round_down);
+                return quot + (mod > 0) + (mod && round_down);
     }
 #else
     static constexpr auto Mul = MulFallback;

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.15.h
index dbb03bbccc..ce3a513935 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.15.h
@@ -95,7 +95,7 @@ struct FeeFrac
         int64_t quot = n / d;
         int32_t mod = n % d;
         // Correct result if the / operator above rounded in the wrong direction.
-        return quot + (mod > 0) - (mod && round_down);
+                return quot + (mod <= 0) - (mod && round_down);
     }
 #else
     static constexpr auto Mul = MulFallback;

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.9.h
index dbb03bbccc..b3563eb3a6 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.9.h
@@ -71,7 +71,7 @@ struct FeeFrac
         // correction.
         int64_t quot_low = n_low / d;
         int32_t mod_low = n_low % d;
-        quot_low += (mod_low > 0) - (mod_low && round_down);
+                quot_low += (mod_low >= 0) - (mod_low && round_down);
         // Combine and return the result
         return (quot_high << 32) + quot_low;
     }

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.3.h
index dbb03bbccc..001523cad9 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.3.h
@@ -69,7 +69,7 @@ struct FeeFrac
         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
         // correction.
-        int64_t quot_low = n_low / d;
+                int64_t quot_low = n_low * d;
         int32_t mod_low = n_low % d;
         quot_low += (mod_low > 0) - (mod_low && round_down);
         // Combine and return the result

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.30.h
index dbb03bbccc..814f0fc845 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.30.h
@@ -93,7 +93,7 @@ struct FeeFrac
         Assume(d > 0);
         // Compute the division.
         int64_t quot = n / d;
-        int32_t mod = n % d;
+                int32_t mod = (n % d) + 1;
         // Correct result if the / operator above rounded in the wrong direction.
         return quot + (mod > 0) - (mod && round_down);
     }

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.7.h
index dbb03bbccc..13bbadc2e3 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.7.h
@@ -71,7 +71,7 @@ struct FeeFrac
         // correction.
         int64_t quot_low = n_low / d;
         int32_t mod_low = n_low % d;
-        quot_low += (mod_low > 0) - (mod_low && round_down);
+                quot_low += (mod_low < 0) - (mod_low && round_down);
         // Combine and return the result
         return (quot_high << 32) + quot_low;
     }

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.34.h
index dbb03bbccc..00f6e048f6 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.34.h
@@ -70,7 +70,7 @@ struct FeeFrac
         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
         // correction.
         int64_t quot_low = n_low / d;
-        int32_t mod_low = n_low % d;
+                int32_t mod_low = (n_low % d) - 1;
         quot_low += (mod_low > 0) - (mod_low && round_down);
         // Combine and return the result
         return (quot_high << 32) + quot_low;

11.h

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.11.h
index dbb03bbccc..eb87c9c3b6 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.11.h
@@ -201,7 +201,7 @@ struct FeeFrac
     {
         Assume(size > 0);
         Assume(at_size >= 0);
-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
+                if (fee >= 0 && fee > 0x200000000) [[likely]] {
             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.25.h
index dbb03bbccc..0c3ddaee86 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.25.h
@@ -61,7 +61,7 @@ struct FeeFrac
         // Compute quot_high = n.first / d, so the result becomes
         // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
         // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
-        int64_t quot_high = n.first / d;
+                int64_t quot_high = (n.first / d) + 1;
         // Evaluate the parenthesized expression above, so the result becomes
         // n_low / d + (quot_high * 2**32)
         int64_t n_low = ((n.first % d) << 32) + n.second;

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.21.h
index dbb03bbccc..657f9144d4 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.21.h
@@ -206,7 +206,7 @@ struct FeeFrac
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);
             } else {
-                return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
+                                return (uint64_t(fee) * at_size + size + 1U) / uint32_t(size);
             }
         } else {
             // Otherwise, use Mul and Div.

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.14.h
index dbb03bbccc..e5cdb1f96f 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.14.h
@@ -71,7 +71,7 @@ struct FeeFrac
         // correction.
         int64_t quot_low = n_low / d;
         int32_t mod_low = n_low % d;
-        quot_low += (mod_low > 0) - (mod_low && round_down);
+                quot_low += (mod_low <= 0) - (mod_low && round_down);
         // Combine and return the result
         return (quot_high << 32) + quot_low;
     }

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.31.h
index dbb03bbccc..fcddd25bb4 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.31.h
@@ -61,7 +61,7 @@ struct FeeFrac
         // Compute quot_high = n.first / d, so the result becomes
         // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
         // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
-        int64_t quot_high = n.first / d;
+                int64_t quot_high = (n.first / d) - 1;
         // Evaluate the parenthesized expression above, so the result becomes
         // n_low / d + (quot_high * 2**32)
         int64_t n_low = ((n.first % d) << 32) + n.second;

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.2.h
index dbb03bbccc..071fc90a19 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.2.h
@@ -61,7 +61,7 @@ struct FeeFrac
         // Compute quot_high = n.first / d, so the result becomes
         // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
         // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
-        int64_t quot_high = n.first / d;
+                int64_t quot_high = n.first * d;
         // Evaluate the parenthesized expression above, so the result becomes
         // n_low / d + (quot_high * 2**32)
         int64_t n_low = ((n.first % d) << 32) + n.second;

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.8.h
index dbb03bbccc..084326c37d 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.8.h
@@ -95,7 +95,7 @@ struct FeeFrac
         int64_t quot = n / d;
         int32_t mod = n % d;
         // Correct result if the / operator above rounded in the wrong direction.
-        return quot + (mod > 0) - (mod && round_down);
+                return quot + (mod < 0) - (mod && round_down);
     }
 #else
     static constexpr auto Mul = MulFallback;

35.h

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.35.h
index dbb03bbccc..ae18b13a15 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.35.h
@@ -92,7 +92,7 @@ struct FeeFrac
     {
         Assume(d > 0);
         // Compute the division.
-        int64_t quot = n / d;
+                int64_t quot = (n / d) - 1;
         int32_t mod = n % d;
         // Correct result if the / operator above rounded in the wrong direction.
         return quot + (mod > 0) - (mod && round_down);

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.6.h
index dbb03bbccc..6c98522329 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.6.h
@@ -206,7 +206,7 @@ struct FeeFrac
             if constexpr (RoundDown) {
                 return (uint64_t(fee) * at_size) / uint32_t(size);
             } else {
-                return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
+                                return (uint64_t(fee) * at_size + size - 1U) * uint32_t(size);
             }
         } else {
             // Otherwise, use Mul and Div.

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.10.h
index dbb03bbccc..92b2c76d10 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.10.h
@@ -95,7 +95,7 @@ struct FeeFrac
         int64_t quot = n / d;
         int32_t mod = n % d;
         // Correct result if the / operator above rounded in the wrong direction.
-        return quot + (mod > 0) - (mod && round_down);
+                return quot + (mod >= 0) - (mod && round_down);
     }
 #else
     static constexpr auto Mul = MulFallback;

26.h

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.26.h
index dbb03bbccc..6b8d17594c 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.26.h
@@ -64,7 +64,7 @@ struct FeeFrac
         int64_t quot_high = n.first / d;
         // Evaluate the parenthesized expression above, so the result becomes
         // n_low / d + (quot_high * 2**32)
-        int64_t n_low = ((n.first % d) << 32) + n.second;
+                int64_t n_low = (((n.first % d) << 32) + n.second) + 1;
         // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible
         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.28.h
index dbb03bbccc..e1b7b34e80 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.28.h
@@ -70,7 +70,7 @@ struct FeeFrac
         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
         // correction.
         int64_t quot_low = n_low / d;
-        int32_t mod_low = n_low % d;
+                int32_t mod_low = (n_low % d) + 1;
         quot_low += (mod_low > 0) - (mod_low && round_down);
         // Combine and return the result
         return (quot_high << 32) + quot_low;

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.32.h
index dbb03bbccc..384b3f294d 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.32.h
@@ -64,7 +64,7 @@ struct FeeFrac
         int64_t quot_high = n.first / d;
         // Evaluate the parenthesized expression above, so the result becomes
         // n_low / d + (quot_high * 2**32)
-        int64_t n_low = ((n.first % d) << 32) + n.second;
+                int64_t n_low = (((n.first % d) << 32) + n.second) - 1;
         // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible
         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.1.h
index dbb03bbccc..f2991cb61f 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.1.h
@@ -218,7 +218,7 @@ public:
     /** Compute the fee for a given size `at_size` using this object's feerate, rounding down. */
     int64_t EvaluateDown(int32_t at_size) const noexcept { return Evaluate<true>(at_size); }
     /** Compute the fee for a given size `at_size` using this object's feerate, rounding up. */
-    int64_t EvaluateUp(int32_t at_size) const noexcept { return Evaluate<false>(at_size); }
+        int64_t EvaluateUp(int32_t at_size) const noexcept { return Evaluate<true>(at_size); }
 };
 
 /** Compare the feerate diagrams implied by the provided sorted chunks data.

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.17.h
index dbb03bbccc..b4f0590650 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.17.h
@@ -95,7 +95,7 @@ struct FeeFrac
         int64_t quot = n / d;
         int32_t mod = n % d;
         // Correct result if the / operator above rounded in the wrong direction.
-        return quot + (mod > 0) - (mod && round_down);
+                return quot + (mod > 0) - (mod || round_down);
     }
 #else
     static constexpr auto Mul = MulFallback;

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.19.h
index dbb03bbccc..c421f87da4 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.19.h
@@ -71,7 +71,7 @@ struct FeeFrac
         // correction.
         int64_t quot_low = n_low / d;
         int32_t mod_low = n_low % d;
-        quot_low += (mod_low > 0) - (mod_low && round_down);
+                quot_low += (mod_low > 0) + (mod_low && round_down);
         // Combine and return the result
         return (quot_high << 32) + quot_low;
     }

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.36.h
index dbb03bbccc..3a52d4728e 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.36.h
@@ -93,7 +93,7 @@ struct FeeFrac
         Assume(d > 0);
         // Compute the division.
         int64_t quot = n / d;
-        int32_t mod = n % d;
+                int32_t mod = (n % d) - 1;
         // Correct result if the / operator above rounded in the wrong direction.
         return quot + (mod > 0) - (mod && round_down);
     }

diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.5.h
index dbb03bbccc..587cfedecd 100644
--- a/src/util/feefrac.h
+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.5.h
@@ -204,7 +204,7 @@ struct FeeFrac
         if (fee >= 0 && fee < 0x200000000) [[likely]] {
             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
             if constexpr (RoundDown) {
-                return (uint64_t(fee) * at_size) / uint32_t(size);
+                                return (uint64_t(fee) * at_size) * uint32_t(size);
             } else {
                 return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
             }

</details>

sipa commented at 2:39 PM on August 7, 2024: member

@brunoerg Cool!

in src/util/feefrac.h:194 in 97f319e68a outdated

 189 | +     * result rounded down (even for negative feerates).
 190 | +     *
 191 | +     * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This
 192 | +     * is guaranteed to be the case when 0 <= at_size <= this->size.
 193 | +     */
 194 | +    int64_t Evaluate(int32_t at_size) const noexcept

ismaelsadeeq commented at 8:47 AM on August 8, 2024:

nit: It might be worth renaming this to EvaluateFee. The helper function and fuzzing comments refer to Evaluate to explain the calculations. While it's clear they aren't the same, differentiating explicitly by stating whats being evaluated might be better.

sipa commented at 8:55 PM on August 16, 2024:

Done!

ismaelsadeeq approved

ismaelsadeeq commented at 12:33 PM on August 8, 2024: member

Code review ACK 9590cdd1afc78ff73fdccd2d016075bf40b6b0e2

@ismaelsadeeq It's a possibility, if we'd want to replace CFeeRate entirely. Another possibility is keeping CFeeRate and its interface, but make it be an encapsulated FeeFrac object (that e.g. on serialization converts to sats/kvb, but that otherwise keeps exact fractions).

I prefer the idea of encapsulating FeeFrac within CFeeRate given how widely CFeeRate is relied upon. I’ve attempt to implement this approach on top of this PR. If this aligns with your idea, I can create a PR for it although the test currently assumes CFeeRate represents a fee rate per kb rather than a fraction, so I had to touch the test a bit.

Note: A few mempool tests are failing with this diff, which I haven’t yet investigated.

diff --git a/src/policy/feerate.cpp b/src/policy/feerate.cpp
index eb0cba5c67a..05b4905b5e3 100644
--- a/src/policy/feerate.cpp
+++ b/src/policy/feerate.cpp
@@ -9,37 +9,24 @@
 
 #include <cmath>
 
-CFeeRate::CFeeRate(const CAmount& nFeePaid, uint32_t num_bytes)
+CAmount CFeeRate::GetFee(uint32_t num_bytes) const
 {
-    const int64_t nSize{num_bytes};
-
-    if (nSize > 0) {
-        nSatoshisPerK = nFeePaid * 1000 / nSize;
-    } else {
-        nSatoshisPerK = 0;
-    }
+    return feerate.EvaluateUp(num_bytes);
 }
 
-CAmount CFeeRate::GetFee(uint32_t num_bytes) const
+CAmount CFeeRate::GetFeePerK() const
 {
-    const int64_t nSize{num_bytes};
-
-    // Be explicit that we're converting from a double to int64_t (CAmount) here.
-    // We've previously had issues with the silent double->int64_t conversion.
-    CAmount nFee{static_cast<CAmount>(std::ceil(nSatoshisPerK * nSize / 1000.0))};
-
-    if (nFee == 0 && nSize != 0) {
-        if (nSatoshisPerK > 0) nFee = CAmount(1);
-        if (nSatoshisPerK < 0) nFee = CAmount(-1);
+    if (feerate.size > 0) {
+        return feerate.fee * kvb / feerate.size;
     }
-
-    return nFee;
+    return 0;
 }
 
 std::string CFeeRate::ToString(const FeeEstimateMode& fee_estimate_mode) const
 {
+    CAmount nSatoshisPerK = GetFeePerK();
     switch (fee_estimate_mode) {
-    case FeeEstimateMode::SAT_VB: return strprintf("%d.%03d %s/vB", nSatoshisPerK / 1000, nSatoshisPerK % 1000, CURRENCY_ATOM);
+    case FeeEstimateMode::SAT_VB: return strprintf("%d.%03d %s/vB", nSatoshisPerK / kvb, nSatoshisPerK % kvb, CURRENCY_ATOM);
     default:                      return strprintf("%d.%08d %s/kvB", nSatoshisPerK / COIN, nSatoshisPerK % COIN, CURRENCY_UNIT);
     }
 }
diff --git a/src/policy/feerate.h b/src/policy/feerate.h
index 2e501729148..16c76fa71e5 100644
--- a/src/policy/feerate.h
+++ b/src/policy/feerate.h
@@ -8,6 +8,7 @@
 
 #include <consensus/amount.h>
 #include <serialize.h>
+#include <util/feefrac.h>
 
 
 #include <cstdint>
@@ -26,20 +27,21 @@ enum class FeeEstimateMode {
     SAT_VB,       //!< Use sat/vB fee rate unit
 };
 
+const int32_t kvb{1000};
 /**
  * Fee rate in satoshis per kilovirtualbyte: CAmount / kvB
  */
 class CFeeRate
 {
 private:
-    /** Fee rate in sat/kvB (satoshis per 1000 virtualbytes) */
-    CAmount nSatoshisPerK;
+    FeeFrac feerate;
 
 public:
     /** Fee rate of 0 satoshis per kvB */
-    CFeeRate() : nSatoshisPerK(0) { }
+    CFeeRate() : feerate(0, kvb) { }
+    /** Fee rate of _nSatoshisPerK satoshis per kvB */
     template<typename I>
-    explicit CFeeRate(const I _nSatoshisPerK): nSatoshisPerK(_nSatoshisPerK) {
+    explicit CFeeRate(const I _nSatoshisPerK): feerate(_nSatoshisPerK, kvb) {
         // We've previously had bugs creep in from silent double->int conversion...
         static_assert(std::is_integral<I>::value, "CFeeRate should be used without floats");
     }
@@ -50,7 +52,7 @@ public:
      * param@[in]   nFeePaid    The fee paid by a transaction, in satoshis
      * param@[in]   num_bytes   The vsize of a transaction, in vbytes
      */
-    CFeeRate(const CAmount& nFeePaid, uint32_t num_bytes);
+    CFeeRate(const CAmount& nFeePaid, uint32_t num_bytes) : feerate(nFeePaid, num_bytes) {};
 
     /**
      * Return the fee in satoshis for the given vsize in vbytes.
@@ -62,19 +64,19 @@ public:
     /**
      * Return the fee in satoshis for a vsize of 1000 vbytes
      */
-    CAmount GetFeePerK() const { return nSatoshisPerK; }
-    friend bool operator<(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK < b.nSatoshisPerK; }
-    friend bool operator>(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK > b.nSatoshisPerK; }
-    friend bool operator==(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK == b.nSatoshisPerK; }
-    friend bool operator<=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK <= b.nSatoshisPerK; }
-    friend bool operator>=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK >= b.nSatoshisPerK; }
-    friend bool operator!=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK != b.nSatoshisPerK; }
-    CFeeRate& operator+=(const CFeeRate& a) { nSatoshisPerK += a.nSatoshisPerK; return *this; }
+    CAmount GetFeePerK() const;
+    friend bool operator<(const CFeeRate& a, const CFeeRate& b) { return a.feerate < b.feerate; }
+    friend bool operator>(const CFeeRate& a, const CFeeRate& b) { return a.feerate > b.feerate; }
+    friend bool operator==(const CFeeRate& a, const CFeeRate& b) { return a.feerate == b.feerate; }
+    friend bool operator<=(const CFeeRate& a, const CFeeRate& b) { return a.feerate <= b.feerate; }
+    friend bool operator>=(const CFeeRate& a, const CFeeRate& b) { return a.feerate >= b.feerate; }
+    friend bool operator!=(const CFeeRate& a, const CFeeRate& b) { return a.feerate != b.feerate; }
+    CFeeRate& operator+=(const CFeeRate& a) { feerate += a.feerate; return *this; }
     std::string ToString(const FeeEstimateMode& fee_estimate_mode = FeeEstimateMode::BTC_KVB) const;
-    friend CFeeRate operator*(const CFeeRate& f, int a) { return CFeeRate(a * f.nSatoshisPerK); }
-    friend CFeeRate operator*(int a, const CFeeRate& f) { return CFeeRate(a * f.nSatoshisPerK); }
+    friend CFeeRate operator*(const CFeeRate& f, int a) { return CFeeRate(a * f.GetFeePerK()); }
+    friend CFeeRate operator*(int a, const CFeeRate& f) { return CFeeRate(a * f.GetFeePerK()); }
 
-    SERIALIZE_METHODS(CFeeRate, obj) { READWRITE(obj.nSatoshisPerK); }
+    SERIALIZE_METHODS(CFeeRate, obj) { READWRITE(obj.GetFeePerK()); }
 };
 
 #endif // BITCOIN_POLICY_FEERATE_H
diff --git a/src/test/amount_tests.cpp b/src/test/amount_tests.cpp
index e5ab1cfb902..ce8aa7f7515 100644
--- a/src/test/amount_tests.cpp
+++ b/src/test/amount_tests.cpp
@@ -50,7 +50,7 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
     feeRate = CFeeRate(123);
     // Rounds up the result, if not integer
     BOOST_CHECK_EQUAL(feeRate.GetFee(0), CAmount(0));
-    BOOST_CHECK_EQUAL(feeRate.GetFee(8), CAmount(1)); // Special case: returns 1 instead of 0
+    BOOST_CHECK_EQUAL(feeRate.GetFee(8), CAmount(1)); // returns 1 instead of 0; because we are rounding up
     BOOST_CHECK_EQUAL(feeRate.GetFee(9), CAmount(2));
     BOOST_CHECK_EQUAL(feeRate.GetFee(121), CAmount(15));
     BOOST_CHECK_EQUAL(feeRate.GetFee(122), CAmount(16));
@@ -61,7 +61,7 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
     feeRate = CFeeRate(-123);
     // Truncates the result, if not integer
     BOOST_CHECK_EQUAL(feeRate.GetFee(0), CAmount(0));
-    BOOST_CHECK_EQUAL(feeRate.GetFee(8), CAmount(-1)); // Special case: returns -1 instead of 0
+    BOOST_CHECK_EQUAL(feeRate.GetFee(8), CAmount(0));
     BOOST_CHECK_EQUAL(feeRate.GetFee(9), CAmount(-1));
 
     // check alternate constructor
@@ -70,21 +70,21 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
     BOOST_CHECK_EQUAL(feeRate.GetFee(100), altFeeRate.GetFee(100));
 
     // Check full constructor
-    BOOST_CHECK(CFeeRate(CAmount(-1), 0) == CFeeRate(0));
-    BOOST_CHECK(CFeeRate(CAmount(0), 0) == CFeeRate(0));
-    BOOST_CHECK(CFeeRate(CAmount(1), 0) == CFeeRate(0));
+    BOOST_CHECK(CFeeRate(CAmount(-1)).GetFeePerK() == -1);
+    BOOST_CHECK(CFeeRate(CAmount(0)).GetFeePerK() == 0);
+    BOOST_CHECK(CFeeRate(CAmount(1), kvb).GetFeePerK() == 1);
     // default value
     BOOST_CHECK(CFeeRate(CAmount(-1), 1000) == CFeeRate(-1));
     BOOST_CHECK(CFeeRate(CAmount(0), 1000) == CFeeRate(0));
     BOOST_CHECK(CFeeRate(CAmount(1), 1000) == CFeeRate(1));
     // lost precision (can only resolve satoshis per kB)
-    BOOST_CHECK(CFeeRate(CAmount(1), 1001) == CFeeRate(0));
-    BOOST_CHECK(CFeeRate(CAmount(2), 1001) == CFeeRate(1));
+    BOOST_CHECK(CFeeRate(CAmount(1), 1001).GetFeePerK() == 0);
+    BOOST_CHECK(CFeeRate(CAmount(2), 1001).GetFeePerK() == 1);
     // some more integer checks
-    BOOST_CHECK(CFeeRate(CAmount(26), 789) == CFeeRate(32));
-    BOOST_CHECK(CFeeRate(CAmount(27), 789) == CFeeRate(34));
+    BOOST_CHECK(CFeeRate(CAmount(26), 789).GetFeePerK() == CFeeRate(32).GetFeePerK());
+    BOOST_CHECK(CFeeRate(CAmount(27), 789).GetFeePerK() == CFeeRate(34).GetFeePerK());
     // Maximum size in bytes, should not crash
-    CFeeRate(MAX_MONEY, std::numeric_limits<uint32_t>::max()).GetFeePerK();
+    CFeeRate(MAX_MONEY, std::numeric_limits<int32_t>::max()).GetFeePerK();
 
     // check multiplication operator
     // check multiplying by zero
@@ -105,8 +105,8 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
     // check boundary values
     int maxInt = std::numeric_limits<int>::max();
     feeRate = CFeeRate(maxInt);
-    BOOST_CHECK(feeRate * 2 == CFeeRate(static_cast<int64_t>(maxInt) * 2));
-    BOOST_CHECK(2 * feeRate == CFeeRate(static_cast<int64_t>(maxInt) * 2));
+    BOOST_CHECK((feeRate * 2).GetFeePerK() == CFeeRate(static_cast<int64_t>(maxInt) * 2).GetFeePerK());
+    BOOST_CHECK((2 * feeRate).GetFeePerK() == CFeeRate(static_cast<int64_t>(maxInt) * 2).GetFeePerK());
     // check with zero fee rate
     feeRate = CFeeRate(0);
     BOOST_CHECK(feeRate * 5 == CFeeRate(0));
@@ -125,9 +125,9 @@ BOOST_AUTO_TEST_CASE(BinaryOperatorTest)
     BOOST_CHECK(a <= a);
     BOOST_CHECK(b >= a);
     BOOST_CHECK(b >= b);
-    // a should be 0.00000002 BTC/kvB now
+    // a is still 0.00000001 BTC/kvB because the size is added also
     a += a;
-    BOOST_CHECK(a == b);
+    BOOST_CHECK_EQUAL(a.GetFeePerK(), a.GetFeePerK());
 }
 
 BOOST_AUTO_TEST_CASE(ToStringTest)

</details>

DrahtBot requested review from brunoerg on Aug 8, 2024

in src/arith_uint256.h:221 in c8b7cc2300 outdated

 216 | -    friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
 217 | -    friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
 218 | -    friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
 219 | +    friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
 220 |      friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
 221 | -    friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }

maflcko commented at 1:23 PM on August 8, 2024:

Can you explain why you remove this line of code? IIUC, this means that != with uint64_t will now go through the implicit constructor call, and then through the new operator<=>.

If it is intentional, then removing operator == with uint64_t should be done as well for the same reason? If not, it may be better to keep them?

Mostly a consistency style-question, feel free to ignore.

sipa commented at 2:07 PM on August 8, 2024:

I don't think so: https://godbolt.org/z/vYr4Tsbde

The implicitly-defined operator!= falls back to using operator==. Only the implicitly defined operator<, operator>, operator<=, operator>= fall back to using operator<=>.

l0rinc commented at 6:32 PM on August 8, 2024:

Checked the same with a simple logging to make sure the reproducer is representative:

diff --git a/src/arith_uint256.h b/src/arith_uint256.h
index d91689c3b3..0198edbbbe 100644
--- a/src/arith_uint256.h
+++ b/src/arith_uint256.h
@@ -12,6 +12,7 @@
 #include <limits>
 #include <stdexcept>
 #include <string>
+#include <iostream>
 
 class uint256;
 
@@ -212,7 +213,10 @@ public:
     friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
     friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
     friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
-    friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
+    friend inline bool operator==(const base_uint& a, uint64_t b) {
+        std::cout << "base_uint::operator==(const base_uint& a, uint64_t b)" << std::endl;
+        return a.EqualTo(b);
+    }
 
     std::string GetHex() const;
     std::string ToString() const;
diff --git a/src/test/feefrac_tests.cpp b/src/test/feefrac_tests.cpp
index 3bbc7450ea..255e96af01 100644
--- a/src/test/feefrac_tests.cpp
+++ b/src/test/feefrac_tests.cpp
@@ -6,9 +6,19 @@
 #include <random.h>
 
 #include <boost/test/unit_test.hpp>
+#include "arith_uint256.h"
+#include <iostream>
 
 BOOST_AUTO_TEST_SUITE(feefrac_tests)
 
+BOOST_AUTO_TEST_CASE(feefrac_operators_ne)
+{
+    auto x = arith_uint256{};
+    std::cout << x.ToString() << std::endl;
+    std::cout << (x == uint64_t(123)) << std::endl;
+    std::cout << (x != uint64_t(123)) << std::endl;
+}
+
 BOOST_AUTO_TEST_CASE(feefrac_operators)
 {
     FeeFrac p1{1000, 100}, p2{500, 300};

% make -j10 && src/test/test_bitcoin --run_test=feefrac_tests/feefrac_operators_ne

which prints:

0000000000000000000000000000000000000000000000000000000000000000 base_uint::operator==(const base_uint& a, uint64_t b) 0 base_uint::operator==(const base_uint& a, uint64_t b) 1

in src/util/feefrac.h:200 in 9590cdd1af outdated

 195 | +     * (if !RoundDown).
 196 |       *
 197 |       * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This
 198 |       * is guaranteed to be the case when 0 <= at_size <= this->size.
 199 |       */
 200 | +    template<bool RoundDown>

glozow commented at 1:45 PM on August 8, 2024:

Question: why did you make this a templated function instead of adding a bool parameter? Is it a compile-time optimization?

sipa commented at 1:53 PM on August 8, 2024:

Yeah, exactly. I think we want this function to be fast (and the rounding mode is always known at compile time anyway), while the Div functions are only needed in exceptional cases (negative fees, or >20 BTC fees) anyway.

glozow commented at 1:55 PM on August 8, 2024:

Makes sense!

DrahtBot requested review from glozow on Aug 8, 2024

in src/util/feefrac.h:205 in 9590cdd1af outdated

 199 | +    template<bool RoundDown>
 200 | +    int64_t Evaluate(int32_t at_size) const noexcept
 201 | +    {
 202 | +        Assume(size > 0);
 203 | +        Assume(at_size >= 0);
 204 | +        if (fee >= 0 && fee < 0x200000000) [[likely]] {

fanquake commented at 3:55 PM on August 8, 2024:

Was curious how much difference using [[likely]] may/may-not have, as I've seen mixed discussions around it's usage. For a single call to EvaluateDown (from the profile_estimate pass):

combined

l0rinc commented at 5:53 PM on August 8, 2024:

I was also wondering, checked the actual execution for both paths (with & without [[likely]]), and if the benchmarks are accurate, AppleClang 15 doesn't seem to make any change in this case (yet?).

<details><summary>FeeFracEvaluate bench</summary>

cmake --build build && ./build/src/bench/bench_bitcoin -filter='FeeFracEvaluate.*' --min-time=10000

// tried a few different ways of testing it, none of them showed any difference

#include <bench/bench.h>
#include <util/feefrac.h>
#include <random.h>
#include <vector>

static void FeeFracEvaluate_likely(benchmark::Bench& bench)
{
    FastRandomContext rng(true);

    constexpr size_t NUM_SAMPLES = 1'000'000;
    std::vector<int64_t> fees(NUM_SAMPLES);
    std::vector<int32_t> sizes(NUM_SAMPLES);
    std::vector<int32_t> at_sizes(NUM_SAMPLES);

    for (size_t i = 0; i < NUM_SAMPLES; ++i) {
        fees[i] = rng.randrange(0x200000000);
        sizes[i] = 1 + rng.randrange(INT32_MAX - 1);
        at_sizes[i] = rng.randrange(INT32_MAX);
    }

    bench.run([&] {
        for (size_t i = 0; i < NUM_SAMPLES; ++i) {
            FeeFrac ff{fees[i], sizes[i]};
            auto fee = i % 2 ? ff.EvaluateDown(at_sizes[i]) : ff.EvaluateUp(at_sizes[i]);
            ankerl::nanobench::doNotOptimizeAway(fee);
        }
    });
}

static void FeeFracEvaluate_unlikely(benchmark::Bench& bench)
{
    FastRandomContext rng(true);

    constexpr size_t NUM_SAMPLES = 1'000'000;
    std::vector<int64_t> fees(NUM_SAMPLES);
    std::vector<int32_t> sizes(NUM_SAMPLES);
    std::vector<int32_t> at_sizes(NUM_SAMPLES);

    for (size_t i = 0; i < NUM_SAMPLES; ++i) {
        fees[i] = 0x200000000 + rng.randrange(0x200000000);
        sizes[i] = 1 + rng.randrange(INT32_MAX - 1);
        at_sizes[i] = rng.randrange(INT32_MAX);
    }

    bench.run([&] {
        for (size_t i = 0; i < NUM_SAMPLES; ++i) {
            FeeFrac ff{fees[i], sizes[i]};
            auto fee = i % 2 ? ff.EvaluateDown(at_sizes[i]) : ff.EvaluateUp(at_sizes[i]);
            ankerl::nanobench::doNotOptimizeAway(fee);
        }
    });
}

BENCHMARK(FeeFracEvaluate_likely, benchmark::PriorityLevel::HIGH);
BENCHMARK(FeeFracEvaluate_unlikely, benchmark::PriorityLevel::HIGH);

</details>

with [[likely]] (2x):

	ns/op	op/s	err%	total	benchmark
	1,133,642.20	882.11	0.1%	11.01	`FeeFracEvaluate_likely`
	6,809,775.64	146.85	0.1%	10.62	`FeeFracEvaluate_unlikely`

	ns/op	op/s	err%	total	benchmark
	1,132,721.68	882.83	0.0%	11.00	`FeeFracEvaluate_likely`
	6,811,900.44	146.80	0.1%	10.62	`FeeFracEvaluate_unlikely`

without any attributes (2x):

	ns/op	op/s	err%	total	benchmark
	1,133,687.15	882.08	0.1%	11.00	`FeeFracEvaluate_likely`
	6,807,422.74	146.90	0.0%	10.62	`FeeFracEvaluate_unlikely`

	ns/op	op/s	err%	total	benchmark
	1,133,233.44	882.43	0.1%	11.04	`FeeFracEvaluate_likely`
	6,809,800.59	146.85	0.1%	10.63	`FeeFracEvaluate_unlikely`

sipa commented at 7:46 PM on August 16, 2024:

Looking at the actual code generated by GCC 14.2 (https://godbolt.org/z/8oTfPKE4q), I get the following diff from adding [[likely]]:

@@ -1,6 +1,13 @@
         mov     rax, rdi
         shr     rax, 33
-        je      .L8
+        jne     .L2
+        movsx   rax, edx
+        mov     esi, esi
+        xor     edx, edx
+        imul    rax, rdi
+        div     rsi
+        ret
+.L2:
         movsx   r10, edx
         sub     rsp, 24
         mov     rax, r10
@@ -24,10 +31,3 @@
         adc     rax, -1
         add     rsp, 24
         ret
-.L8:
-        movsx   rax, edx
-        mov     esi, esi
-        xor     edx, edx
-        imul    rax, rdi
-        div     rsi
-        ret

which is exactly what I'd expect. The default branch prediction (before observations are available) is to assume that a conditional jump backwards will happen, while a conditional jump forward will not happen, so we want the likely branch to be emitted first; adding the [[likely]] does indeed result in that.

It may be hard to observe this effect in a micro-benchmark as we expect that after a few iterations the CPU branch predictor will guess 100% correctly anyway.

I think that's sufficient reason to keep the [[likely]] here because (1) it is semantically correct (it is the only branch relevant in production code) (2) it documents this fact to human readers (3) it does not measurably worsen the code and (4) it appears to make at least some compilers produce marginally better code, but if people feel it should only be used when backed by observably better benchmarks, I'm okay with dropping it.

l0rinc commented at 7:59 PM on August 16, 2024:

I personally view it as documentation and would definitely keep it here

sipa force-pushed on Aug 16, 2024

l0rinc commented at 9:24 AM on August 17, 2024: contributor

ACK eff5bf7d673c797d63c5ad15ac18b8316dea5ffe (diff only contains Evaluate* -> EvaluateFee* changes)

DrahtBot requested review from ismaelsadeeq on Aug 17, 2024

ismaelsadeeq commented at 8:49 AM on August 19, 2024: member

re-ACK eff5bf7d673c797d63c5ad15ac18b8316dea5ffe

DrahtBot added the label CI failed on Sep 10, 2024

DrahtBot removed the label CI failed on Sep 13, 2024

Christewart commented at 6:51 PM on October 4, 2024: contributor

concept ACK

glozow added this to the milestone 29.0 on Feb 5, 2025

sipa force-pushed on Feb 5, 2025

sipa commented at 5:19 PM on February 5, 2025: member

Rebased because of datedness.

in src/test/fuzz/feefrac.cpp:38 in b4a1cee76e outdated

  63 | -/* comparison helper for std::array */
  64 | -std::strong_ordering compare_arrays(const std::array<uint32_t, 4>& a, const std::array<uint32_t, 4>& b) {
  65 | -    for (size_t i = 0; i < a.size(); ++i) {
  66 | -        if (a[i] != b[i]) return a[i] <=> b[i];
  67 | +/** Construct an arith_uint256 whose value equals abs(x), for 96-bit x. */
  68 | +arith_uint256 Abs256(std::pair<int64_t, uint32_t> x)

l0rinc commented at 6:19 PM on February 5, 2025:

Now that Fuzz is always compiled, this should likely be move to feefrac: add helper functions for 96-bit division (see https://github.com/bitcoin/bitcoin/actions/runs/13162889382/job/36735875466?pr=30535#step:6:2772)

sipa commented at 6:30 PM on February 5, 2025:

Done.

l0rinc approved

l0rinc commented at 6:20 PM on February 5, 2025: contributor

Rebase didn't result in any code change, but CI compiles fuzzing for every commit now

sipa force-pushed on Feb 5, 2025

DrahtBot added the label CI failed on Feb 5, 2025

l0rinc commented at 6:39 PM on February 5, 2025: contributor

ACK 5600091e8384a69cfc7e95a7aea816e7a9076917

Build failure will likely be resolved by retriggering it later

DrahtBot requested review from ismaelsadeeq on Feb 5, 2025

sipa force-pushed on Feb 5, 2025

sipa commented at 6:44 PM on February 5, 2025: member

Added a few commit messages to explain the rationale for the changes more.

l0rinc commented at 7:04 PM on February 5, 2025: contributor

ACK f6aa28cf8fad6a3240498b500524bb380855b18e

Added build failure to #31797 (comment) - should be retriggered later

murchandamus commented at 7:26 PM on February 5, 2025: contributor

Concept ACK, I also really like the idea of improving CFeeRate.

ACK up to 5147b5d602d1f55d7c9f497cf0cfc23263f5caf5, still mulling over the last three commits.

DrahtBot removed the label CI failed on Feb 5, 2025

ismaelsadeeq commented at 8:02 PM on February 5, 2025: member

@murchandamus

Concept ACK, I also really like the idea of improving CFeeRate.

You will also like https://github.com/bitcoin/bitcoin/pull/31363/commits/46ffaf98503c7f6c8a8d9b9a188f541d77e08b1a

If this aligns with your idea, I can create a PR for it although the test currently assumes CFeeRate represents a fee rate per kb rather than a fraction, so I had to touch the test a bit.

I think after this and #31363 making CFeeRate a wrapper around FeePerVSize will be a good follow-up.

instagibbs commented at 2:14 PM on February 6, 2025: member

I did some very light fuzzing against CFeeRate results to make sure the "gap" between the two values is never huge, would there be some value in adding coverage to confirm that results aren't wildly off from what we have today if we use it more widely?

sipa commented at 2:25 PM on February 6, 2025: member

would there be some value in adding coverage to confirm that results aren't wildly off from what we have today if we use it more widely?

Sure, happy to add a commit for tests with that.

instagibbs commented at 2:51 PM on February 6, 2025: member

https://github.com/instagibbs/bitcoin/commit/ac2e55980bb4841a55b9396070af62cf3925e721

Bounding difference to "100 sats", seems to work ok to a 500BTC fee, feel free to take or leave it since these numbers are kind of made up.

concept ACK anyways

laanwj approved

laanwj commented at 3:13 PM on February 6, 2025: member

Code review ACK f6aa28cf8fad6a3240498b500524bb380855b18e, mul/division code looks correct, testing and fuzzing coverage seems very good

DrahtBot requested review from instagibbs on Feb 6, 2025

DrahtBot requested review from murchandamus on Feb 6, 2025

in src/test/fuzz/feefrac.cpp:130 in f6aa28cf8f outdated

 123 | +    // rounding down, or positive and we are rounding up, the absolute value of the quotient is
 124 | +    // the rounded-up quotient of the absolute values.
 125 | +    auto num_abs = Abs256(num);
 126 | +    auto den_abs = Abs256(den);
 127 | +    auto quot_abs = (is_negative == round_down) ?
 128 | +        (num_abs + den_abs - 1) / den_abs :

yancyribbens commented at 3:32 PM on February 7, 2025:

At first glance this is confusing. It looks like quot_abs is being computed differently depending on if num_high is negative or not, although it's not apparent why right away. Maybe I will take these fuzz tests for a spin and look at some example values. As a side note, it's interesting that fuzz tests are used to test for program correctness where I thought the main objective for fuzz tests was to find crashes and panics.

l0rinc commented at 7:09 PM on February 7, 2025:

Modern C++ integer division always truncates toward zero. For positive numbers, that’s equivalent to rounding down, but for negatives it rounds up. Since we need controlled rounding (toward negative infinity when round_down is true, or toward positive infinity otherwise), we need to take the sign of the numerator into account to adjust the result when necessary

For example, in feefrac_tests.cpp, tests like the following verify the rounding behavior:

For a positive fee (p1 initialized as {1000, 100}):

BOOST_CHECK_EQUAL(p1.EvaluateFeeDown(1), 10);
BOOST_CHECK_EQUAL(p1.EvaluateFeeUp(1), 10);

For a negative fee (neg initialized as {-1001, 100}):

BOOST_CHECK_EQUAL(neg.EvaluateFeeDown(1), -11);
BOOST_CHECK_EQUAL(neg.EvaluateFeeUp(1), -10);

Which would result for the same absolute values in:

BOOST_AUTO_TEST_CASE(feefrac_operators)
{
    FeeFrac p1{1001, 100};

    BOOST_CHECK_EQUAL(p1.EvaluateFeeDown(1), 10);
    BOOST_CHECK_EQUAL(p1.EvaluateFeeUp(1), 11);

    FeeFrac neg{-1001, 100};
    BOOST_CHECK_EQUAL(neg.EvaluateFeeDown(1), -11);
    BOOST_CHECK_EQUAL(neg.EvaluateFeeUp(1), -10);
}

sipa commented at 8:53 PM on February 7, 2025:

Right. The variables this code operates on are arith_uint256, which represent integers in range $[0, 2^{256}-1]$, and whose division operator rounds down (whether that means towards $-\infty$ or towards 0 does not matter, since only non-negative numbers can be represented anyway).

However, these values reason about the absolute value of what Div is expected to do. If we want to round down (towards $-\infty$), but the value being divided is negative, that means the absolute value of the result is rounded up (e.g. -5/3 = -1.6, if we want to round down would be -2, whose absolute value is 2, which is the rounded-up value of 5/3).

sipa commented at 8:58 PM on February 7, 2025:

As a side note, it's interesting that fuzz tests are used to test for program correctness where I thought the main objective for fuzz tests was to find crashes and panics.

They're an amazing tool for this purpose. Any time you write a well-contained, well-specified piece of code, you can essentially write a less efficient simulator for its behavior, and compare the two in a fuzz test. We have many such examples in the codebase.

yancyribbens commented at 1:09 AM on February 8, 2025:

They're an amazing tool for this purpose. Any time you write a well-contained, well-specified piece of code, you can essentially write a less efficient simulator for its behavior, and compare the two in a fuzz test. We have many such examples in the codebase.

However property tests, which like fuzz tests generate random input, although the inputs are truly random, which may be desirable for testing program correctness. From what I understand about fuzz tests, the random inputs are generated in such a way that new code paths are discovered with the goal of producing an overflow or crash.

sipa commented at 7:05 PM on February 10, 2025:

Fuzzing is still random, it's just biased towards increasing coverage. It's not specifically intended to trigger bugs, it just aims to maximize coverage (code coverage, branch coverage, and "values being compared" coverage). And typically, this is exactly what you want in correctness tests too, as it may result in far more edge/special cases being exercised than uniformly random inputs may trigger.

Also note that coverage include the test harness itself, so if you add branches/cases to the test code, those too will be biased towards. In a way, this removes (or at least reduces, in typical cases) the need for the test designer to reason about what probability distributions of inputs are likely to trigger bugs.

in src/test/feefrac_tests.cpp:18 in f6aa28cf8f outdated

  16 | @@ -17,6 +17,44 @@ BOOST_AUTO_TEST_CASE(feefrac_operators)
  17 |      FeeFrac empty{0, 0};
  18 |      [[maybe_unused]] FeeFrac zero_fee{0, 1}; // zero-fee allowed

l0rinc commented at 7:12 PM on February 7, 2025:

nit: This is always used now, right?

sipa commented at 6:58 PM on February 10, 2025:

Gone.

sipa force-pushed on Feb 10, 2025

in src/test/fuzz/feefrac.cpp:145 in e9f22e28e9 outdated

 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::floorl(num_high * 4294967296.0L + num_low) / den
 145 | +                                    : std::ceill(num_high * 4294967296.0L + num_low) / den;

l0rinc commented at 7:21 PM on February 10, 2025:

It seems to me that std::floor and std::ceil already have overloads for long double, which we could use instead to appease the CI gods:

feefrac.cpp:144:44: error: ‘floorl’ is not a member of ‘std’; did you mean ‘floor’?

sipa commented at 8:06 PM on February 10, 2025:

Fixed.

sipa force-pushed on Feb 10, 2025

DrahtBot added the label CI failed on Feb 10, 2025

DrahtBot commented at 7:22 PM on February 10, 2025: contributor

🚧 At least one of the CI tasks failed. <sub>Debug: https://github.com/bitcoin/bitcoin/runs/36980187687</sub>

<details><summary>Hints</summary>

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

</details>

in src/test/fuzz/feefrac.cpp:146 in cf00540f54 outdated

 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.

l0rinc commented at 7:43 PM on February 10, 2025:

I was wondering if we could measure ULP tolerance here instead to better control the step sizes - or if that would be too much effort in this context.

sipa commented at 7:54 PM on February 10, 2025:

Honestly, I think the code I included here already is more complicated than what I think was worth writing. But it's just test code, and it's already written, and it works.

Its added value is adding confidence for anyone looking at the test who has difficulty following, the exact arith_uint256-based test code, or otherwise doubts its correctness. The exact precision used here won't make much difference I think - it should just be enough so someone can a single glance say "ok, if this test doesn't fail, at least the result won't be wildly off from what i expect it to do".

instagibbs commented at 8:12 PM on February 10, 2025:

I think there's also some value in knowing we're not diverging wildly from what already exists if we're planning on swapping functionality later. Agreed on the rest.

sipa commented at 8:14 PM on February 10, 2025:

@instagibbs Note that this is about a separate addition I made, which compares the behaviour with a pure floating-point simulation. The comparison with CFeeRate is elsewhere.

instagibbs commented at 8:15 PM on February 10, 2025:

oh right, I conflated the two threads here

l0rinc approved

l0rinc commented at 7:47 PM on February 10, 2025: contributor

ACK cf00540f54302e37f8af08f15fce16cbcab0f8c9

Added approximately floating point comparisons to fuzz tests and removed the lingering [[maybe_unused]] in feefrac_tests.cpp

DrahtBot requested review from laanwj on Feb 10, 2025

sipa commented at 8:07 PM on February 10, 2025: member

@instagibbs I incorporated a variant of your commit into the existing feefrac_mul_div fuzz test, with the tightest bounds I could make work.

DrahtBot removed the label CI failed on Feb 10, 2025

glozow removed this from the milestone 29.0 on Feb 13, 2025

ryanofsky commented at 2:34 PM on April 1, 2025: contributor

PR may be ready for merge if @ismaelsadeeq and @laanwj want to re-ack or others want to ACK

ismaelsadeeq commented at 11:47 AM on April 2, 2025: member

I will review soon.

in src/test/fuzz/feefrac.cpp:36 in c71afe6a04 outdated

  32 | @@ -32,6 +33,18 @@ arith_uint256 Abs256(int64_t x)
  33 |      }
  34 |  }
  35 |

ismaelsadeeq commented at 1:51 PM on April 7, 2025:

In "feefrac: add helper functions for 96-bit division" c71afe6a041e557b403159d0a974965a06b6fc43

typo in commit message

(given a FeeFrac{fee, size}, its fee at at_size is (fee * at_size / at_size).

should be

(given a FeeFrac{fee, size}, its fee at at_size is (fee * at_size / size).

sipa commented at 2:51 PM on April 7, 2025:

Done.

in src/test/fuzz/feefrac.cpp:213 in c71afe6a04 outdated

 196 | +        assert(res >= expect * 0.999999999999999L - 1.0L);
 197 | +        assert(res <= expect * 1.000000000000001L + 1.0L);
 198 | +    } else {
 199 | +        assert(res >= expect * 1.000000000000001L - 1.0L);
 200 | +        assert(res <= expect * 0.999999999999999L + 1.0L);
 201 | +    }

ismaelsadeeq commented at 1:53 PM on April 7, 2025:

in "feefrac: add helper functions for 96-bit division" c71afe6a041e557b403159d0a974965a06b6fc43 can be a util function since exact same thing is repeated twice.

sipa commented at 2:52 PM on April 7, 2025:

That seems a bit excessive for just two lines.

in src/util/feefrac.h:92 in 486e816bd7 outdated

  87 | @@ -85,13 +88,14 @@ struct FeeFrac
  88 |       *  version relying on __int128.
  89 |       *
  90 |       * The result must fit in an int64_t, and d must be strictly positive. */
  91 | -    static inline int64_t Div(__int128 n, int32_t d) noexcept
  92 | +    static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept

ismaelsadeeq commented at 1:59 PM on April 7, 2025:

In "feefrac: support both rounding up and down for Evaluate" 486e816bd7d68f4411b35330907ce42812c5c71b

Div method description needs to be updated we round toward positive infinity when round down is false.

sipa commented at 2:52 PM on April 7, 2025:

Done.

in src/test/fuzz/feefrac.cpp:228 in cf00540f54 outdated

 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);

ismaelsadeeq commented at 2:35 PM on April 7, 2025:

In "fuzz: assert min diff between FeeFrac and CFeeRate" cf00540f54302e37f8af08f15fce16cbcab0f8c9

I could not comprehend the computation. how did you come up with this gap.

sipa commented at 2:53 PM on April 7, 2025:

I just tried things until the tests pass. As pointed out elsewhere, I don't think the exact accuracy promises are all that relevant - the point is convincing a reviewer (who isn't convinced by the other tests) that the result is never going to be hugely off.

ismaelsadeeq commented at 2:39 PM on April 7, 2025: member

Code review ACK cf00540f54302e37f8af08f15fce16cbcab0f8c9

I have reviewed each commit it looks good, my comments below are not serious just a question on last commit and some suggestions that improve doc, making fuzz test dry and improving commit message.

DrahtBot requested review from ryanofsky on Apr 7, 2025

arith_uint256: modernize comparison operators

Since C++20, operator!= is implicitly defaulted using operator==, and
operator<, operator<=, operator>, and operator>= are defaulted using
operator<=>, so it suffices to just provide these two.

46ff4220bf

feefrac fuzz: use arith_uint256 instead of ad-hoc multiply

Rather than use an ad-hoc reimplementation of wide multiplication inside the
fuzz test, reuse arith_uint256, which already has this. It's larger than what we
need here, but performance isn't a concern in this test, and it does what we need.

fcfe008db2

feefrac: rework comments around Mul/MulFallback 800c0dea9a

feefrac: add helper functions for 96-bit division

These functions are needed to implement FeeFrac evaluation later: given a
FeeFrac{fee, size}, its fee at at_size is (fee * at_size / size).

7963aecead

feefrac: add support for evaluating at given size ecf956ec9d

feefrac: support both rounding up and down for Evaluate

Co-Authored-By: l0rinc <pap.lorinc@gmail.com>

0c6bcfd8f7

fuzz: assert min diff between FeeFrac and CFeeRate

Co-Authored-By: Greg Sanders <gsanders87@gmail.com>

58914ab459

sipa force-pushed on Apr 7, 2025

in src/test/fuzz/feefrac.cpp:135 in c71afe6a04 outdated

 125 | +    auto den_abs = Abs256(den);
 126 | +    auto quot_abs = is_negative ? (num_abs + den_abs - 1) / den_abs : num_abs / den_abs;
 127 | +
 128 | +    // If the result is not representable by an int64_t, bail out.
 129 | +    if ((is_negative && quot_abs > MAX_ABS_INT64) || (!is_negative && quot_abs >= MAX_ABS_INT64)) {
 130 | +        return;

sipa commented at 2:52 PM on April 7, 2025:

Can you suggest code?

l0rinc commented at 3:18 PM on April 7, 2025: contributor

ACK 58914ab459c46c518c47c5082aec25ac0d03ab11

Rebased, changing mostly Span to std::span - and a minor comment update.

<details> <summary>patch</summary>

diff --git a/src/util/feefrac.h b/src/util/feefrac.h
--- a/src/util/feefrac.h(revision a9f419ef8aa2d518de1ad87603b82248bf88f864)
+++ b/src/util/feefrac.h(date 1744038722170)
@@ -84,7 +84,8 @@
         return __int128{a} * b;
     }
 
-    /** Helper function for 96/32 signed division, rounding towards negative infinity. This is a
+    /** Helper function for 96/32 signed division, rounding towards negative infinity (if
+     *  round_down), or towards positive infinity (if !round_down). This is a
      *  version relying on __int128.
      *
      * The result must fit in an int64_t, and d must be strictly positive. */

</details>

DrahtBot requested review from ismaelsadeeq on Apr 7, 2025

ismaelsadeeq commented at 3:39 PM on April 7, 2025: member

reACK 58914ab459c46c518c47c5082aec25ac0d03ab11

in src/util/feefrac.h:193 in 58914ab459

 186 | @@ -144,6 +187,39 @@ struct FeeFrac
 187 |          std::swap(a.fee, b.fee);
 188 |          std::swap(a.size, b.size);
 189 |      }
 190 | +
 191 | +    /** Compute the fee for a given size `at_size` using this object's feerate.
 192 | +     *
 193 | +     * This effectively corresponds to evaluating (this->fee * at_size) / this->size, with the

yancyribbens commented at 7:39 PM on April 7, 2025:

Wouldn't it save some confusion if there was a type for WU and a type for vbytes? If for example a FeeFrac is created as {sats /vbytes} then one wouldn't want to accidentally pass an argument calculated using a wu metric for at_size param (possibly). In that case one would want to div by 4 first to get corresponding vbytes metric, however if there where strong types, then it could be converted automagically.

sipa commented at 7:43 PM on April 7, 2025:

See the FeePerVSize and FeePerWeight types below, which are FeeFrac wrappers that provide some basic type-safety.

I don't think going as far as having separate types for weights/vsize itself is realistic, given how much they're used in the codebase already (and in any case, this is unrelated to this PR).

yancyribbens commented at 8:09 PM on April 7, 2025:

See the FeePerVSize and FeePerWeight types below, which are FeeFrac wrappers that provide some basic type-safety.

Thanks, I didn't notice the wrappers. Maybe they would enhance some of the tests if they where incorporated.

I don't think going as far as having separate types for weights/vsize itself is realistic, given how much they're used in the codebase already (and in any case, this is unrelated to this PR).

Personally I've wished for these types when working in the wallet coin-selection test suit for example. Although, this discussion can be saved for elsewhere though since it's not strictly on topic.

glozow commented at 9:28 PM on April 7, 2025: member

light code review ACK 58914ab459c46c518c47c5082aec25ac0d03ab11

glozow merged this on Apr 7, 2025

glozow closed this on Apr 7, 2025

glozow referenced this in commit 874da961d0 on Apr 9, 2025

TheCharlatan referenced this in commit a9c46ce3c3 on Apr 24, 2025

stickies-v referenced this in commit 772a33e052 on May 23, 2025

yuvicc referenced this in commit 069643f094 on Jul 6, 2025

achow101 referenced this in commit daca51bf80 on Aug 9, 2025