Resubmit bigint changes of r41817 that were later reverted.

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 40 matching lines @@
   // Allocate extra digits so the bigint can be reused.
   static const int EXTRA_DIGITS = 4;
 
   // Min and max of non bigint values.
   static const int MIN_INT64 = (-1) << 63;
   static const int MAX_INT64 = 0x7fffffffffffffff;
 
   // Bigint constant values.
   // Note: Not declared as final in order to satisfy optimizer, which expects
   // constants to be in canonical form (Smi).
-  static _Bigint ZERO = new _Bigint();
   static _Bigint ONE = new _Bigint()._setInt(1);
 
   // Digit conversion table for parsing.
   static final Map<int, int> DIGIT_TABLE = _createDigitTable();
 
   // Internal data structure.
   bool get _neg native "Bigint_getNeg";
   void set _neg(bool value) native "Bigint_setNeg";
   int get _used native "Bigint_getUsed";
   void set _used(int value) native "Bigint_setUsed";
@@ skipping 124 matching lines @@
       return -((digits[1] << DIGIT_BITS) | digits[0]);
     }
     if (digits[1] >= 0x80000000) return this;
     return (digits[1] << DIGIT_BITS) | digits[0];
   }
 
   // Conversion from int to bigint.
   _Bigint _toBigint() => this;
 
   // Make sure at least 'length' _digits are allocated.
-  // Copy existing _digits if reallocation is necessary.
-  // TODO(regis): Check that we are not preserving _digits unnecessarily.
+  // Copy existing and used _digits if reallocation is necessary.
+  // Avoid preserving _digits unnecessarily by calling this function with a
+  // meaningful _used field.
   void _ensureLength(int length) {
+    length++;  // Account for leading zero for 64-bit processing.

[regis, 2014/11/20 22:37:23]

This increment was dropped by mistake in patch #4 of the reverted cl, here and
in the C++ version.

     var digits = _digits;
-    if (length > 0 && (length > digits.length)) {
+    if (length > digits.length) {
       var new_digits = new Uint32List(length + EXTRA_DIGITS);
-      for (var i = _used; --i >= 0; ) {
-        new_digits[i] = digits[i];
+      _digits = new_digits;
+      var used = _used;
+      if (used > 0) {
+        var i = used + 1;  // Copy leading zero for 64-bit processing.
+        while (--i >= 0) {
+          new_digits[i] = digits[i];
+        }
       }
-      _digits = new_digits;
     }
   }
 
   // Clamp off excess high _digits.
   void _clamp() {
-    var digits = _digits;
-    while (_used > 0 && digits[_used - 1] == 0) {
-      --_used;
+    var used = _used;
+    if (used > 0) {
+      var digits = _digits;
+      if (digits[used - 1] == 0) {
+        do {
+          --used;
+        } while (used > 0 && digits[used - 1] == 0);
+        _used = used;
+      }
+      digits[used] = 0;  // Set leading zero for 64-bit processing.
     }
   }
 
   // Copy this to r.
   void _copyTo(_Bigint r) {
-    r._ensureLength(_used);
-    var digits = _digits;
-    var r_digits = r._digits;
-    for (var i = _used - 1; i >= 0; --i) {
-      r_digits[i] = digits[i];
+    var used = _used;
+    if (used > 0) {
+      // We could set r._used to 0 in order to avoid preserving digits. However,
+      // it would be wrong to do so if this === r. Checking is too expensive.
+      // This case does not occur in the current implementation, but we want to
+      // remain safe.
+      r._ensureLength(used);
+      var digits = _digits;
+      var r_digits = r._digits;
+      var i = used + 1;  // Copy leading zero for 64-bit processing.
+      while (--i >= 0) {
+        r_digits[i] = digits[i];
+      }
     }
-    r._used = _used;
+    r._used = used;
     r._neg = _neg;
   }
 
   // Return the bit length of digit x.
   int _nbits(int x) {
     var r = 1, t;
     if ((t = x >> 16) != 0) { x = t; r += 16; }
     if ((t = x >> 8) != 0) { x = t; r += 8; }
     if ((t = x >> 4) != 0) { x = t; r += 4; }
     if ((t = x >> 2) != 0) { x = t; r += 2; }
     if ((x >> 1) != 0) { r += 1; }
     return r;
   }
 
   // r = this << n*DIGIT_BITS.
   void _dlShiftTo(int n, _Bigint r) {
-    var r_used = _used + n;
+    var used = _used;
+    if (used == 0) {
+      r._used = 0;
+      r._neg = false;
+      return;
+    }
+    var r_used = used + n;
     r._ensureLength(r_used);
     var digits = _digits;
     var r_digits = r._digits;
-    for (var i = _used - 1; i >= 0; --i) {
+    var i = used + 1;  // Copy leading zero for 64-bit processing.
+    while (--i >= 0) {
       r_digits[i + n] = digits[i];
     }
-    for (var i = n - 1; i >= 0; --i) {
+    i = n;
+    while (--i >= 0) {
       r_digits[i] = 0;
     }
     r._used = r_used;
     r._neg = _neg;
   }
 
   // r = this >> n*DIGIT_BITS.
   void _drShiftTo(int n, _Bigint r) {
-    var r_used = _used - n;
-    if (r_used < 0) {
+    var used = _used;
+    if (used == 0) {
+      r._used = 0;
+      r._neg = false;
+      return;
+    }
+    var r_used = used - n;
+    if (r_used <= 0) {
       if (_neg) {
         // Set r to -1.
+        r._used = 0;  // No digits to preserve.
+        r._ensureLength(1);
         r._neg = true;
-        r._ensureLength(1);
         r._used = 1;
         r._digits[0] = 1;
+        r._digits[1] = 0;  // Set leading zero for 64-bit processing.
       } else {
         // Set r to 0.
         r._neg = false;
         r._used = 0;
       }
       return;
     }
     r._ensureLength(r_used);
     var digits = _digits;
     var r_digits = r._digits;
-    var used = _used;
-    for (var i = n; i < used; ++i) {
+    for (var i = n; i < used + 1; i++) {  // Copy leading zero for 64-bit proc.
       r_digits[i - n] = digits[i];
     }
     r._used = r_used;
     r._neg = _neg;
     if (_neg) {
       // Round down if any bit was shifted out.
       for (var i = 0; i < n; i++) {
         if (digits[i] != 0) {
           r._subTo(ONE, r);
           break;
@@ skipping 10 matching lines @@
       _dlShiftTo(ds, r);
       return;
     }
     var cbs = DIGIT_BITS - bs;
     var bm = (1 << cbs) - 1;
     var r_used = _used + ds + 1;
     r._ensureLength(r_used);
     var digits = _digits;
     var r_digits = r._digits;
     var c = 0;
-    for (var i = _used - 1; i >= 0; --i) {
+    var i = _used;
+    while (--i >= 0) {
       r_digits[i + ds + 1] = (digits[i] >> cbs) | c;
       c = (digits[i] & bm) << bs;
     }
-    for (var i = ds - 1; i >= 0; --i) {
+    i = ds;
+    while (--i >= 0) {
       r_digits[i] = 0;
     }
     r_digits[ds] = c;
     r._used = r_used;
     r._neg = _neg;
     r._clamp();
   }
 
   // r = this >> n.
   void _rShiftTo(int n, _Bigint r) {
     var ds = n ~/ DIGIT_BITS;
     var bs = n % DIGIT_BITS;
     if (bs == 0) {
       _drShiftTo(ds, r);
       return;
     }
     var r_used = _used - ds;
     if (r_used <= 0) {
       if (_neg) {
         // Set r to -1.
         r._neg = true;
+        r._used = 0;  // No digits to preserve.
         r._ensureLength(1);
         r._used = 1;
         r._digits[0] = 1;
+        r._digits[1] = 0;  // Set leading zero for 64-bit processing.
       } else {
         // Set r to 0.
         r._neg = false;
         r._used = 0;
       }
       return;
     }
     var cbs = DIGIT_BITS - bs;
     var bm = (1 << bs) - 1;
     r._ensureLength(r_used);
     var digits = _digits;
     var r_digits = r._digits;
     r_digits[0] = digits[ds] >> bs;
     var used = _used;
-    for (var i = ds + 1; i < used; ++i) {
+    for (var i = ds + 1; i < used; i++) {
       r_digits[i - ds - 1] |= (digits[i] & bm) << cbs;
       r_digits[i - ds] = digits[i] >> bs;
     }
     r._neg = _neg;
     r._used = r_used;
     r._clamp();
     if (_neg) {
       // Round down if any bit was shifted out.
       if ((digits[ds] & bm) != 0) {
         r._subTo(ONE, r);
@@ skipping 488 matching lines @@
     } else {
       a_digits[i + used] = c;
     }
   }
 
   // r = this * a.
   void _mulTo(_Bigint a, _Bigint r) {
     // TODO(regis): Use karatsuba multiplication when appropriate.
     var used = _used;
     var a_used = a._used;
+    if (used == 0 || a_used == 0) {
+      r._used = 0;
+      r._neg = false;
+      return;
+    }
     var r_used = used + a_used;
     r._ensureLength(r_used);
     var digits = _digits;
     var a_digits = a._digits;
     var r_digits = r._digits;
     r._used = r_used;
-    var i = r_used;
+    var i = r_used + 1;  // Set leading zero for 64-bit processing.
     while (--i >= 0) {
       r_digits[i] = 0;
     }
     for (i = 0; i < a_used; ++i) {
       _mulAdd(a_digits, i, digits, 0, r_digits, i, used);
     }
     r._clamp();
     r._neg = r._used > 0 && _neg != a._neg;  // Zero cannot be negative.
   }
 
   // r = this^2, r != this.
   void _sqrTo(_Bigint r) {
     var used = _used;
+    if (used == 0) {
+      r._used = 0;
+      r._neg = false;
+      return;
+    }
     var r_used = 2 * used;
     r._ensureLength(r_used);
     var digits = _digits;
     var r_digits = r._digits;
-    var i = r_used;
+    var i = r_used + 1;  // Set leading zero for 64-bit processing.
     while (--i >= 0) {
       r_digits[i] = 0;
     }
     for (i = 0; i < used - 1; ++i) {
       _sqrAdd(digits, i, r_digits, used);
     }
     if (r_used > 0) {
       _mulAdd(digits, i, digits, i, r_digits, 2*i, 1);
     }
     r._used = r_used;
@@ skipping 58 matching lines @@
     var y_digits = y._digits;
     var yt = y_digits[y_used - 1];
     if (yt == 0) return;
     var i = r._used;
     var j = i - y_used;
     _Bigint t = (q == null) ? new _Bigint() : q;
     y._dlShiftTo(j, t);
     var r_digits = r._digits;
     if (r._compareTo(t) >= 0) {
       r_digits[r._used++] = 1;
+      r_digits[r._used] = 0;  // Set leading zero for 64-bit processing.
       r._subTo(t, r);
     }
     ONE._dlShiftTo(y_used, t);
     t._subTo(y, y);  // Negate y so we can replace sub with _mulAdd later.
     while (y._used < y_used) {
       y_digits[y._used++] = 0;
     }
+    y_digits[y._used] = 0;  // Set leading zero for 64-bit processing.
     Uint32List args = new Uint32List(2);
     args[_YT] = yt;
     while (--j >= 0) {
       _estQuotientDigit(args, r_digits, --i);
       _mulAdd(args, _QD, y_digits, 0, r_digits, j, y_used);
       if (r_digits[i] < args[_QD]) {
         y._dlShiftTo(j, t);
         r._subTo(t, r);
         while (r_digits[i] < --args[_QD]) {
           r._subTo(t, r);
         }
       }
     }
     if (q != null) {
       r._drShiftTo(y_used, q);
-      if (_neg != a._neg) {
-        ZERO._subTo(q, q);
+      if (_neg != a._neg && q._used > 0) {
+        q._neg = !q._neg;
       }
     }
     r._used = y_used;
     r._clamp();
     if (nsh > 0) {
       r._rShiftTo(nsh, r);  // Denormalize remainder.
     }
-    if (_neg) {
-      ZERO._subTo(r, r);
+    if (_neg && r._used > 0) {
+      r._neg = !r._neg;
     }
   }
 
   int get _identityHashCode {
     return this;
   }
   int operator ~() {
     _Bigint result = new _Bigint();
     _notTo(result);
     return result._toValidInt();
@@ skipping 396 matching lines @@
     return r;
   }
 
   // x = x/R mod _m
   void _reduce(_Bigint x) {
     x._ensureLength(_mused2 + 1);
     var x_digits = x._digits;
     while (x._used <= _mused2) {  // Pad x so _mulAdd has enough room later.
       x_digits[x._used++] = 0;
     }
+    x_digits[x._used] = 0;  // Set leading zero for 64-bit processing.
     var m_used = _m._used;
     var m_digits = _m._digits;
-    for (var i = 0; i < m_used; ++i) {
+    for (var i = 0; i < m_used; i++) {
       _mulMod(_rho_mu, x_digits, i);
       _Bigint._mulAdd(_rho_mu, _MU, m_digits, 0, x_digits, i, m_used);
     }
     x._clamp();
     x._drShiftTo(m_used, x);
     if (x._compareTo(_m) >= 0) {
       x._subTo(_m, x);
     }
   }
 
@@ skipping 41 matching lines @@
   void _sqrTo(_Bigint x, _Bigint r) {
     x._sqrTo(r);
     _reduce(r);
   }
 
   void _mulTo(_Bigint x, _Bigint y, _Bigint r) {
     x._mulTo(y, r);
     _reduce(r);
   }
 }