diff options
Diffstat (limited to 'src/google/protobuf/stubs/int128.cc')
-rw-r--r-- | src/google/protobuf/stubs/int128.cc | 60 |
1 files changed, 22 insertions, 38 deletions
diff --git a/src/google/protobuf/stubs/int128.cc b/src/google/protobuf/stubs/int128.cc index d80c64f2..7b993e8f 100644 --- a/src/google/protobuf/stubs/int128.cc +++ b/src/google/protobuf/stubs/int128.cc @@ -31,7 +31,7 @@ #include <google/protobuf/stubs/int128.h> #include <iomanip> -#include <iostream> // NOLINT(readability/streams) +#include <ostream> // NOLINT(readability/streams) #include <sstream> namespace google { @@ -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; @@ -145,15 +129,15 @@ std::ostream& operator<<(std::ostream& o, const uint128& b) { std::streamsize div_base_log; switch (flags & std::ios::basefield) { case std::ios::hex: - div = GOOGLE_ULONGLONG(0x1000000000000000); // 16^15 + div = static_cast<uint64>(GOOGLE_ULONGLONG(0x1000000000000000)); // 16^15 div_base_log = 15; break; case std::ios::oct: - div = GOOGLE_ULONGLONG(01000000000000000000000); // 8^21 + div = static_cast<uint64>(GOOGLE_ULONGLONG(01000000000000000000000)); // 8^21 div_base_log = 21; break; default: // std::ios::dec - div = GOOGLE_ULONGLONG(10000000000000000000); // 10^19 + div = static_cast<uint64>(GOOGLE_ULONGLONG(10000000000000000000)); // 10^19 div_base_log = 19; break; } |