in lib/src/int64.dart [920:1050]
static Int64 _divideHelper(
// up to 64 bits unsigned in a2/a1/a0 and b2/b1/b0
int a0,
int a1,
int a2,
bool aNeg, // input A.
int b0,
int b1,
int b2,
bool bNeg, // input B.
int what) {
int q0 = 0, q1 = 0, q2 = 0; // result Q.
int r0 = 0, r1 = 0, r2 = 0; // result R.
if (b2 == 0 && b1 == 0 && b0 < (1 << (30 - _BITS))) {
// Small divisor can be handled by single-digit division within Smi range.
//
// Handling small divisors here helps the estimate version below by
// handling cases where the estimate is off by more than a small amount.
q2 = a2 ~/ b0;
int carry = a2 - q2 * b0;
int d1 = a1 + (carry << _BITS);
q1 = d1 ~/ b0;
carry = d1 - q1 * b0;
int d0 = a0 + (carry << _BITS);
q0 = d0 ~/ b0;
r0 = d0 - q0 * b0;
} else {
// Approximate Q = A ~/ B and R = A - Q * B using doubles.
// The floating point approximation is very close to the correct value
// when floor(A/B) fits in fewer that 53 bits.
// We use double arithmetic for intermediate values. Double arithmetic on
// non-negative values is exact under the following conditions:
//
// - The values are integer values that fit in 53 bits.
// - Dividing by powers of two (adjusts exponent only).
// - Floor (zeroes bits with fractional weight).
const double K2 = 17592186044416.0; // 2^44
const double K1 = 4194304.0; // 2^22
// Approximate double values for [a] and [b].
double ad = a0 + K1 * a1 + K2 * a2;
double bd = b0 + K1 * b1 + K2 * b2;
// Approximate quotient.
double qd = (ad / bd).floorToDouble();
// Extract components of [qd] using double arithmetic.
double q2d = (qd / K2).floorToDouble();
qd = qd - K2 * q2d;
double q1d = (qd / K1).floorToDouble();
double q0d = qd - K1 * q1d;
q2 = q2d.toInt();
q1 = q1d.toInt();
q0 = q0d.toInt();
assert(q0 + K1 * q1 + K2 * q2 == (ad / bd).floorToDouble());
assert(q2 == 0 || b2 == 0); // Q and B can't both be big since Q*B <= A.
// P = Q * B, using doubles to hold intermediates.
// We don't need all partial sums since Q*B <= A.
double p0d = q0d * b0;
double p0carry = (p0d / K1).floorToDouble();
p0d = p0d - p0carry * K1;
double p1d = q1d * b0 + q0d * b1 + p0carry;
double p1carry = (p1d / K1).floorToDouble();
p1d = p1d - p1carry * K1;
double p2d = q2d * b0 + q1d * b1 + q0d * b2 + p1carry;
assert(p2d <= _MASK2); // No partial sum overflow.
// R = A - P
int diff0 = a0 - p0d.toInt();
int diff1 = a1 - p1d.toInt() - ((diff0 >> _BITS) & 1);
int diff2 = a2 - p2d.toInt() - ((diff1 >> _BITS) & 1);
r0 = _MASK & diff0;
r1 = _MASK & diff1;
r2 = _MASK2 & diff2;
// while (R < 0 || R >= B)
// adjust R towards [0, B)
while (r2 >= _SIGN_BIT_MASK ||
r2 > b2 ||
(r2 == b2 && (r1 > b1 || (r1 == b1 && r0 >= b0)))) {
// Direction multiplier for adjustment.
int m = (r2 & _SIGN_BIT_MASK) == 0 ? 1 : -1;
// R = R - B or R = R + B
int d0 = r0 - m * b0;
int d1 = r1 - m * (b1 + ((d0 >> _BITS) & 1));
int d2 = r2 - m * (b2 + ((d1 >> _BITS) & 1));
r0 = _MASK & d0;
r1 = _MASK & d1;
r2 = _MASK2 & d2;
// Q = Q + 1 or Q = Q - 1
d0 = q0 + m;
d1 = q1 + m * ((d0 >> _BITS) & 1);
d2 = q2 + m * ((d1 >> _BITS) & 1);
q0 = _MASK & d0;
q1 = _MASK & d1;
q2 = _MASK2 & d2;
}
}
// 0 <= R < B
assert(Int64.ZERO <= Int64._bits(r0, r1, r2));
assert(r2 < b2 || // Handles case where B = -(MIN_VALUE)
Int64._bits(r0, r1, r2) < Int64._bits(b0, b1, b2));
assert(what == _RETURN_DIV || what == _RETURN_MOD || what == _RETURN_REM);
if (what == _RETURN_DIV) {
if (aNeg != bNeg) return _negate(q0, q1, q2);
return Int64._masked(q0, q1, q2); // Masking for type inferrer.
}
if (!aNeg) {
return Int64._masked(r0, r1, r2); // Masking for type inferrer.
}
if (what == _RETURN_MOD) {
if (r0 == 0 && r1 == 0 && r2 == 0) {
return ZERO;
} else {
return _sub(b0, b1, b2, r0, r1, r2);
}
} else {
return _negate(r0, r1, r2);
}
}