diff options
Diffstat (limited to 'src/google/protobuf/stubs/int128.cc')
-rw-r--r-- | src/google/protobuf/stubs/int128.cc | 52 |
1 files changed, 18 insertions, 34 deletions
diff --git a/src/google/protobuf/stubs/int128.cc b/src/google/protobuf/stubs/int128.cc index a5090801..7b993e8f 100644 --- a/src/google/protobuf/stubs/int128.cc +++ b/src/google/protobuf/stubs/int128.cc @@ -76,52 +76,36 @@ static inline int Fls128(uint128 n) { return Fls64(Uint128Low64(n)); } -// Long division/modulo for uint128 implemented using the shift-subtract -// division algorithm adapted from: -// http://stackoverflow.com/questions/5386377/division-without-using void uint128::DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret, uint128* remainder_ret) { if (divisor == 0) { GOOGLE_LOG(FATAL) << "Division or mod by zero: dividend.hi=" << dividend.hi_ << ", lo=" << dividend.lo_; - } - - if (divisor > dividend) { + } else if (dividend < divisor) { *quotient_ret = 0; *remainder_ret = dividend; return; - } - - if (divisor == dividend) { - *quotient_ret = 1; - *remainder_ret = 0; - return; - } - - uint128 denominator = divisor; - uint128 position = 1; - uint128 quotient = 0; - - // Left aligns the MSB of the denominator and the dividend. - int shift = Fls128(dividend) - Fls128(denominator); - denominator <<= shift; - position <<= shift; - - // Uses shift-subtract algorithm to divide dividend by denominator. The - // remainder will be left in dividend. - while (position > 0) { - if (dividend >= denominator) { - dividend -= denominator; - quotient |= position; + } else { + int dividend_bit_length = Fls128(dividend); + int divisor_bit_length = Fls128(divisor); + int difference = dividend_bit_length - divisor_bit_length; + uint128 quotient = 0; + while (difference >= 0) { + quotient <<= 1; + uint128 shifted_divisor = divisor << difference; + if (shifted_divisor <= dividend) { + dividend -= shifted_divisor; + quotient += 1; + } + difference -= 1; } - position >>= 1; - denominator >>= 1; + //record the final quotient and remainder + *quotient_ret = quotient; + *remainder_ret = dividend; } - - *quotient_ret = quotient; - *remainder_ret = dividend; } + uint128& uint128::operator/=(const uint128& divisor) { uint128 quotient = 0; uint128 remainder = 0; |