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);

[zra, 2014/11/20 22:56:16]

final?

[regis, 2014/11/20 23:17:40]

No. See comment above.

 
   // 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";
   Uint32List get _digits native "Bigint_getDigits";
@@ skipping 123 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.
     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) {

[zra, 2014/11/20 22:56:16]

x.bitLength ?

Not sure how that's implemented, but it might be worth looking into.

[regis, 2014/11/20 23:17:40]

It's a call to Utils::HighestBit, which I remember improving. So it is identical
to this call, except that we avoid the call to runtime plumbing and also save
processing for one bit (32 instead of 64).

An intrinsic could help, especially since we could make use of an instruction,
but not a runtime call.

I'll keep this in mind in case it shows up on the profile.

     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);
   }
 }