| 855 | /// \brief Do a decimal division with remainder. |
| 856 | template <class DecimalClass> |
| 857 | static inline DecimalStatus DecimalDivide(const DecimalClass& dividend, |
| 858 | const DecimalClass& divisor, |
| 859 | DecimalClass* result, DecimalClass* remainder) { |
| 860 | constexpr int64_t kDecimalArrayLength = DecimalClass::kBitWidth / sizeof(uint32_t); |
| 861 | // Split the dividend and divisor into integer pieces so that we can |
| 862 | // work on them. |
| 863 | uint32_t dividend_array[kDecimalArrayLength + 1]; |
| 864 | uint32_t divisor_array[kDecimalArrayLength]; |
| 865 | bool dividend_was_negative; |
| 866 | bool divisor_was_negative; |
| 867 | // leave an extra zero before the dividend |
| 868 | dividend_array[0] = 0; |
| 869 | int64_t dividend_length = |
| 870 | FillInArray(dividend, dividend_array + 1, dividend_was_negative) + 1; |
| 871 | int64_t divisor_length = FillInArray(divisor, divisor_array, divisor_was_negative); |
| 872 | |
| 873 | // Handle some of the easy cases. |
| 874 | if (dividend_length <= divisor_length) { |
| 875 | *remainder = dividend; |
| 876 | *result = 0; |
| 877 | return DecimalStatus::kSuccess; |
| 878 | } |
| 879 | |
| 880 | if (divisor_length == 0) { |
| 881 | return DecimalStatus::kDivideByZero; |
| 882 | } |
| 883 | |
| 884 | if (divisor_length == 1) { |
| 885 | return SingleDivide(dividend_array, dividend_length, divisor_array[0], remainder, |
| 886 | dividend_was_negative, divisor_was_negative, result); |
| 887 | } |
| 888 | |
| 889 | int64_t result_length = dividend_length - divisor_length; |
| 890 | uint32_t result_array[kDecimalArrayLength]; |
| 891 | DCHECK_LE(result_length, kDecimalArrayLength); |
| 892 | |
| 893 | // Normalize by shifting both by a multiple of 2 so that |
| 894 | // the digit guessing is better. The requirement is that |
| 895 | // divisor_array[0] is greater than 2**31. |
| 896 | int64_t normalize_bits = std::countl_zero(divisor_array[0]); |
| 897 | ShiftArrayLeft(divisor_array, divisor_length, normalize_bits); |
| 898 | ShiftArrayLeft(dividend_array, dividend_length, normalize_bits); |
| 899 | |
| 900 | // compute each digit in the result |
| 901 | for (int64_t j = 0; j < result_length; ++j) { |
| 902 | // Guess the next digit. At worst it is two too large |
| 903 | uint32_t guess = std::numeric_limits<uint32_t>::max(); |
| 904 | const auto high_dividend = |
| 905 | static_cast<uint64_t>(dividend_array[j]) << 32 | dividend_array[j + 1]; |
| 906 | if (dividend_array[j] != divisor_array[0]) { |
| 907 | guess = static_cast<uint32_t>(high_dividend / divisor_array[0]); |
| 908 | } |
| 909 | |
| 910 | // catch all of the cases where guess is two too large and most of the |
| 911 | // cases where it is one too large |
| 912 | auto rhat = static_cast<uint32_t>(high_dividend - |
| 913 | guess * static_cast<uint64_t>(divisor_array[0])); |
| 914 | while (static_cast<uint64_t>(divisor_array[1]) * guess > |
no test coverage detected