Data structure storing a fee and size. * * The size of a FeeFrac cannot be zero unless the fee is also zero. */
| 19 | * The size of a FeeFrac cannot be zero unless the fee is also zero. |
| 20 | */ |
| 21 | struct FeeFrac |
| 22 | { |
| 23 | /** Helper function for 32*64 signed multiplication, returning an unspecified but totally |
| 24 | * ordered type. This is a fallback version, separate so it can be tested on platforms where |
| 25 | * it isn't actually needed. */ |
| 26 | static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept |
| 27 | { |
| 28 | int64_t low = int64_t{static_cast<uint32_t>(a)} * b; |
| 29 | int64_t high = (a >> 32) * b; |
| 30 | return {high + (low >> 32), static_cast<uint32_t>(low)}; |
| 31 | } |
| 32 | |
| 33 | /** Helper function for 96/32 signed division, rounding towards negative infinity (if |
| 34 | * round_down) or positive infinity (if !round_down). This is a fallback version, separate so |
| 35 | * that it can be tested on platforms where it isn't actually needed. |
| 36 | * |
| 37 | * The exact behavior with negative n does not really matter, but this implementation chooses |
| 38 | * to be consistent for testability reasons. |
| 39 | * |
| 40 | * The result must fit in an int64_t, and d must be strictly positive. */ |
| 41 | static inline int64_t DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down) noexcept |
| 42 | { |
| 43 | Assume(d > 0); |
| 44 | // Compute quot_high = n.first / d, so the result becomes |
| 45 | // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or |
| 46 | // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32). |
| 47 | int64_t quot_high = n.first / d; |
| 48 | // Evaluate the parenthesized expression above, so the result becomes |
| 49 | // n_low / d + (quot_high * 2**32) |
| 50 | int64_t n_low = ((n.first % d) << 32) + n.second; |
| 51 | // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible |
| 52 | // that the / operator here rounds in the wrong direction (if n_low is not a multiple of |
| 53 | // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a |
| 54 | // correction. |
| 55 | int64_t quot_low = n_low / d; |
| 56 | int32_t mod_low = n_low % d; |
| 57 | quot_low += (mod_low > 0) - (mod_low && round_down); |
| 58 | // Combine and return the result |
| 59 | return (quot_high << 32) + quot_low; |
| 60 | } |
| 61 | |
| 62 | #ifdef __SIZEOF_INT128__ |
| 63 | /** Helper function for 32*64 signed multiplication, returning an unspecified but totally |
| 64 | * ordered type. This is a version relying on __int128. */ |
| 65 | static inline __int128 Mul(int64_t a, int32_t b) noexcept |
| 66 | { |
| 67 | return __int128{a} * b; |
| 68 | } |
| 69 | |
| 70 | /** Helper function for 96/32 signed division, rounding towards negative infinity (if |
| 71 | * round_down), or towards positive infinity (if !round_down). This is a |
| 72 | * version relying on __int128. |
| 73 | * |
| 74 | * The result must fit in an int64_t, and d must be strictly positive. */ |
| 75 | static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept |
| 76 | { |
| 77 | Assume(d > 0); |
| 78 | // Compute the division. |
no outgoing calls