Repository: bitcoin/bitcoin
File: src/util/feefrac.h (C/C++)

Code before:
    }

    // 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;
    }
#else
    static constexpr auto Mul = MulFallback;
#endif

    int64_t fee;
    int32_t size;

    /** Construct an IsEmpty() FeeFrac. */
    constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}

    /** Construct a FeeFrac with specified fee and size. */
    constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}

    constexpr inline FeeFrac(const FeeFrac&) noexcept = default;
    constexpr inline FeeFrac& operator=(const FeeFrac&) noexcept = default;

    /** Check if this is empty (size and fee are 0). */
    bool inline IsEmpty() const noexcept {
        return size == 0;
    }

    /** Add fee and size of another FeeFrac to this one. */
    void inline operator+=(const FeeFrac& other) noexcept
    {
        fee += other.fee;
        size += other.size;
    }

    /** Subtract fee and size of another FeeFrac from this one. */
    void inline operator-=(const FeeFrac& other) noexcept
    {
        fee -= other.fee;
        size -= other.size;
    }

    /** Sum fee and size. */
    friend inline FeeFrac operator+(const FeeFrac& a, const FeeFrac& b) noexcept
    {
        return {a.fee + b.fee, a.size + b.size};
    }

    /** Subtract both fee and size. */

Review comment (bug):
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:
```patch
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.

Code after:
    /** Helper function for 96/32 signed division, rounding towards negative infinity (if
     *  round_down) or positive infinity (if !round_down). This is a fallback version, separate so
     *  that it can be tested on platforms where it isn't actually needed.
     *
     * The exact behavior with negative n does not really matter, but this implementation chooses
     * 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
    {
        Assume(d > 0);
        // 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;
        // 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;
        // 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
        // correction.
        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
        return (quot_high << 32) + quot_low;
    }

#ifdef __SIZEOF_INT128__
    /** Helper function for 32*64 signed multiplication, returning an unspecified but totally
     *  ordered type. This is a version relying on __int128. */
    static inline __int128 Mul(int64_t a, int32_t b) noexcept
    {
        return __int128{a} * b;
    }

    /** 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. */
    static inline int64_t Div(__int128 n, int32_t d, bool round_down) 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.
        return quot + (mod > 0) - (mod && round_down);
    }