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

Code before:
 */
std::partial_ordering CompareChunks(std::span<const FeeFrac> chunks0, std::span<const FeeFrac> chunks1);

/** Tagged wrapper around FeeFrac to avoid unit confusion. */
template<typename Tag>
struct FeePerUnit : public FeeFrac
{
    // Inherit FeeFrac constructors.
    using FeeFrac::FeeFrac;

    /** Convert a FeeFrac to a FeePerUnit. */
    static FeePerUnit FromFeeFrac(const FeeFrac& feefrac) noexcept
    {
        return {feefrac.fee, feefrac.size};
    }
};

// FeePerUnit instance for satoshi / vbyte.
struct VSizeTag {};
using FeePerVSize = FeePerUnit<VSizeTag>;

// FeePerUnit instance for satoshi / WU.
struct WeightTag {};
using FeePerWeight = FeePerUnit<WeightTag>;

#endif // BITCOIN_UTIL_FEEFRAC_H


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

Code after:
    friend inline std::weak_ordering FeeRateCompare(const FeeFrac& a, const FeeFrac& b) noexcept
    {
        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
        return cross_a <=> cross_b;
    }

    /** Check if a FeeFrac object has strictly lower feerate than another. */
    friend inline bool operator<<(const FeeFrac& a, const FeeFrac& b) noexcept
    {
        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
        return cross_a < cross_b;
    }

    /** Check if a FeeFrac object has strictly higher feerate than another. */
    friend inline bool operator>>(const FeeFrac& a, const FeeFrac& b) noexcept
    {
        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
        return cross_a > cross_b;
    }

    /** Compare two FeeFracs. <, >, <=, and >= are auto-generated from this. */
    friend inline std::strong_ordering operator<=>(const FeeFrac& a, const FeeFrac& b) noexcept
    {
        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
        if (cross_a == cross_b) return b.size <=> a.size;
        return cross_a <=> cross_b;
    }

    /** Swap two FeeFracs. */
    friend inline void swap(FeeFrac& a, FeeFrac& b) noexcept
    {
        std::swap(a.fee, b.fee);
        std::swap(a.size, b.size);
    }

    /** Compute the fee for a given size `at_size` using this object's feerate.
     *
     * This effectively corresponds to evaluating (this->fee * at_size) / this->size, with the
     * result rounded towards negative infinity (if RoundDown) or towards positive infinity
     * (if !RoundDown).
     *
     * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This
     * is guaranteed to be the case when 0 <= at_size <= this->size.
     */
    template<bool RoundDown>
    int64_t EvaluateFee(int32_t at_size) const noexcept
    {
        Assume(size > 0);
        Assume(at_size >= 0);
        if (fee >= 0 && fee < 0x200000000) [[likely]] {
            // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.