Fix bigint division (issue 23238).

runtime/lib/bigint.dart

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 /*
  * Copyright (c) 2003-2005  Tom Wu
@@ skipping 1024 matching lines @@
     var i = r_used + (r_used & 1);
     var j = i - y_used;
     // t_digits is a temporary array of i digits.
     var t_digits = new Uint32List(i);
     var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits);
     // Explicit first division step in case normalized dividend is larger or
     // equal to shifted normalized divisor.
     if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) {
       assert(i == r_used);
       r_digits[r_used++] = 1;  // Quotient = 1.
-      r_digits[r_used] = 0;  // Leading zero.
       // Subtract divisor from remainder.
       _absSub(r_digits, r_used, t_digits, t_used, r_digits);
+    } else {
+      // Account for possible carry in _mulAdd step.
+      r_digits[r_used++] = 0;
     }
+    r_digits[r_used] = 0;  // Leading zero for 64-bit processing.
     // Negate y so we can later use _mulAdd instead of non-existent _mulSub.
     var ny_digits = new Uint32List(y_used + 2);
     ny_digits[y_used] = 1;
     _absSub(ny_digits, y_used + 1, y_digits, y_used, ny_digits);
     // ny_digits is read-only and has y_used digits (possibly including several
     // leading zeros) plus a leading zero for 64-bit processing.
     // r_digits is modified during iteration.
     // r_digits[0..y_used-1] is the current remainder.
     // r_digits[y_used..r_used-1] is the current quotient.
     --i;
@@ skipping 71 matching lines @@
     // For 64-bit processing, make sure y_used, i, and j are even.
     assert(y_used.isEven);
     var i = r_used + (r_used & 1);
     var j = i - y_used;
     var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits);
     // Explicit first division step in case normalized dividend is larger or
     // equal to shifted normalized divisor.
     if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) {
       assert(i == r_used);
       r_digits[r_used++] = 1;  // Quotient = 1.
-      r_digits[r_used] = 0;  // Leading zero.
       // Subtract divisor from remainder.
       _absSub(r_digits, r_used, t_digits, t_used, r_digits);
+    } else {
+      // Account for possible carry in _mulAdd step.
+      r_digits[r_used++] = 0;
     }
+    r_digits[r_used] = 0;  // Leading zero for 64-bit processing.
     // Negated y_digits passed in ny_digits allow the use of _mulAdd instead of
     // unimplemented _mulSub.
     // ny_digits is read-only and has y_used digits (possibly including several
     // leading zeros) plus a leading zero for 64-bit processing.
     // r_digits is modified during iteration.
     // r_digits[0..y_used-1] is the current remainder.
     // r_digits[y_used..r_used-1] is the current quotient.
     --i;
     while (j > 0) {
       var d0 = _estQuotientDigit(yt_qd, r_digits, i);
@@ skipping 643 matching lines @@
 
   int _mul(Uint32List x_digits, int x_used,
            Uint32List y_digits, int y_used,
            Uint32List r_digits) {
     var r_used = _Bigint._mulDigits(x_digits, x_used,
                                     y_digits, y_used,
                                     r_digits);
     return _reduce(r_digits, r_used);
   }
 }