in runtime/runtime.cpp [4091:4247]
bool Runtime::intDivideModulo(Thread* thread, const Int& dividend,
const Int& divisor, Object* quotient,
Object* modulo) {
// Some notes for understanding this code:
// - This is built around an unsigned division algorithm in
// `unsignedDivideRemainder()`.
// - Remember that this implements floor div and modulo which is different
// from C++ giving you truncated div and remainder when operands are
// negative.
// - To build a signed floor division from an unsigned division primitive we
// use the following formula when the sign of dividend and divisor differs:
// floor_div = -1 - (abs(dividend) - 1) / abs(divisor)
// modulo = divisor_sign *
// (abs(divisor) - 1 - (abs(dividend) - 1) % abs(divisor))
// TODO(matthiasb): Optimization idea: Fuse the independent operations/loops
// on arrays of `halfuword`s to reduce the number of passes over the data.
word divisor_digits = divisor.numDigits();
word dividend_digits = dividend.numDigits();
bool same_sign = dividend.isNegative() == divisor.isNegative();
if (divisor_digits == 1) {
word divisor_word = divisor.asWord();
if (divisor_word == 0) {
return false;
}
// Handle -1 as a special case because for dividend being the smallest
// negative number possible for the amount of digits and `divisor == -1`
// produces a result that is bigger than the input.
if (divisor_word == -1) {
if (quotient != nullptr) *quotient = intNegate(thread, dividend);
if (modulo != nullptr) *modulo = SmallInt::fromWord(0);
return true;
}
if (dividend_digits == 1) {
word dividend_word = dividend.asWord();
word quotient_word = dividend_word / divisor_word;
word modulo_word = dividend_word % divisor_word;
if (!same_sign && modulo_word) {
DCHECK(quotient_word > kMinWord, "underflow");
quotient_word--;
modulo_word += divisor_word;
}
if (quotient != nullptr) *quotient = newInt(quotient_word);
if (modulo != nullptr) *modulo = newInt(modulo_word);
return true;
}
// Handle the case where `abs(divisor)` fits in single half word.
// This helps performance and simplifies `unsignedDivideRemainder()` because
// it can assume to have at least 2 divisor half words.
word max_half_uword = (word{1} << kBitsPerHalfWord) - 1;
if (-max_half_uword <= divisor_word && divisor_word <= max_half_uword) {
divideModuloSingleHalfDivisor(thread, dividend, divisor_word, quotient,
modulo);
return true;
}
}
if (divisor_digits > dividend_digits) {
divideWithBiggerDivisor(thread, dividend, divisor, quotient, modulo);
return true;
}
// Convert divisor to `halfuword`s. Normalize by left shifting until the
// highest bit (of the highest half) is set as required by
// `unsignedDivideRemainder()`. We count the non-zero halves in the
// `significant_xxx_halves` variables.
word divisor_halves = divisor_digits * 2;
std::unique_ptr<halfuword[]> divisor_n(new halfuword[divisor_halves]);
halvesFromIntMagnitude(divisor_n.get(), divisor);
word significant_divisor_halves =
halvesNormalize(divisor_n.get(), divisor_halves);
static_assert(sizeof(divisor_n[0]) == sizeof(unsigned),
"choose right builtin");
int shift = __builtin_clz(divisor_n[significant_divisor_halves - 1]);
halvesShiftLeft(divisor_n.get(), significant_divisor_halves, shift);
// Convert dividend to `halfuword`s and shift by the same amount we used for
// the divisor. We reserve 1 extra half so we can save a bounds check in
// `unsignedDivideRemainder()` because `dividend_halves` will still be valid
// to access at index `significant_divisor_halves`.
word dividend_halves = (dividend_digits + 1) * 2;
std::unique_ptr<halfuword[]> dividend_n(new halfuword[dividend_halves]);
halvesFromIntMagnitude(dividend_n.get(), dividend);
dividend_n[dividend_halves - 1] = 0;
dividend_n[dividend_halves - 2] = 0;
if (!same_sign) {
halvesDecrement(dividend_n.get(), dividend_halves);
}
halvesShiftLeft(dividend_n.get(), dividend_halves, shift);
word significant_dividend_halves =
halvesNormalize(dividend_n.get(), dividend_halves);
// Handle special case of divisor being bigger than the dividend.
if (significant_divisor_halves > significant_dividend_halves ||
(significant_divisor_halves == significant_dividend_halves &&
divisor_n[significant_divisor_halves - 1] >
dividend_n[significant_divisor_halves - 1])) {
divideWithBiggerDivisor(thread, dividend, divisor, quotient, modulo);
return true;
}
// Allocate storage for result. Make sure we have an even number of halves.
word result_halves = (dividend_halves - divisor_halves + 2) & ~1;
DCHECK(result_halves % 2 == 0, "even number of halves");
std::unique_ptr<halfuword[]> result(new halfuword[result_halves]);
word significant_result_halves =
significant_dividend_halves - significant_divisor_halves + 1;
DCHECK(significant_result_halves <= result_halves, "no overflow");
unsignedDivideRemainder(result.get(), significant_result_halves,
dividend_n.get(), divisor_n.get(),
significant_divisor_halves);
// TODO(matthiasb): We copy the data in result[] to a new LargeInt,
// normalizeLargeInt will probably just copy it again. Should we normalize on
// result[]? Can we do it without duplicating the normalization code?
if (quotient != nullptr) {
for (word i = significant_result_halves; i < result_halves; i++) {
result[i] = 0;
}
if (!same_sign) {
// Compute `-1 - quotient == -1 + (~quotient + 1) == ~quotient`.
halvesInvert(result.get(), result_halves);
}
*quotient = largeIntFromHalves(thread, result.get(), result_halves);
}
if (modulo != nullptr) {
// `dividend` contains the remainder now. First revert normalization shift.
halvesShiftRight(dividend_n.get(), significant_dividend_halves, shift);
if (!same_sign) {
// Revert divisor shift.
halvesShiftRight(divisor_n.get(), significant_divisor_halves, shift);
// Compute `-remainder + divisor - 1`.
halvesNegate(dividend_n.get(), dividend_halves);
halfuword carry = halvesAdd(dividend_n.get(), divisor_n.get(),
significant_divisor_halves);
DCHECK(carry <= 1, "carry <= 1");
if (carry) {
halvesIncrement(dividend_n.get() + significant_divisor_halves,
dividend_halves - significant_divisor_halves, true);
}
halvesDecrement(dividend_n.get(), dividend_halves);
}
if (divisor.isNegative()) {
halvesNegate(dividend_n.get(), dividend_halves);
}
*modulo = largeIntFromHalves(thread, dividend_n.get(), dividend_halves);
}
return true;
}