Long division/modulo for uint128 implemented using the shift-subtract division algorithm adapted from: https://stackoverflow.com/questions/5386377/division-without-using
| 54 | // division algorithm adapted from: |
| 55 | // https://stackoverflow.com/questions/5386377/division-without-using |
| 56 | inline void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret, |
| 57 | uint128* remainder_ret) { |
| 58 | assert(divisor != 0); |
| 59 | |
| 60 | if (divisor > dividend) { |
| 61 | *quotient_ret = 0; |
| 62 | *remainder_ret = dividend; |
| 63 | return; |
| 64 | } |
| 65 | |
| 66 | if (divisor == dividend) { |
| 67 | *quotient_ret = 1; |
| 68 | *remainder_ret = 0; |
| 69 | return; |
| 70 | } |
| 71 | |
| 72 | uint128 denominator = divisor; |
| 73 | uint128 quotient = 0; |
| 74 | |
| 75 | // Left aligns the MSB of the denominator and the dividend. |
| 76 | const int shift = Fls128(dividend) - Fls128(denominator); |
| 77 | denominator <<= shift; |
| 78 | |
| 79 | // Uses shift-subtract algorithm to divide dividend by denominator. The |
| 80 | // remainder will be left in dividend. |
| 81 | for (int i = 0; i <= shift; ++i) { |
| 82 | quotient <<= 1; |
| 83 | if (dividend >= denominator) { |
| 84 | dividend -= denominator; |
| 85 | quotient |= 1; |
| 86 | } |
| 87 | denominator >>= 1; |
| 88 | } |
| 89 | |
| 90 | *quotient_ret = quotient; |
| 91 | *remainder_ret = dividend; |
| 92 | } |
| 93 | |
| 94 | template <typename T> |
| 95 | uint128 MakeUint128FromFloat(T v) { |
no test coverage detected