Process two 32-bit digits as one 64-bit digit in bigint absAdd intrinsic on x64.

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 185 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) {
     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;
+      if (_used > 0) {
+        for (var i = _used + 1; --i >= 0; ) {  // Copy leading zero.

[zra, 2014/11/18 19:04:45]

So, every number has a leading zero? Even those with an even number of digits?

[regis, 2014/11/18 23:19:54]

Yes, I figured that the _mulAdd intrinsic (among others) will get called on a
partial number at an odd digit index.

My plan is to change this intrinsic to return the number of processed digits (1
or 2), so it may be possible to keep processing aligned on digit pairs. But for
now, I prefer to always add a leading zero, until this works.  

+          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) {
+      r._used = 0;  // No digits to preserve.
+      r._ensureLength(used);
+      var digits = _digits;
+      var r_digits = r._digits;
+      // Copy leading zero for 64-bit processing.
+      for (var i = used + 1; --i >= 0; ) {

[zra, 2014/11/18 19:04:45]

Would a while loop improve readability here?

[regis, 2014/11/18 23:19:54]

Done.

+        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;
     r._ensureLength(r_used);
     var digits = _digits;
     var r_digits = r._digits;
-    for (var i = _used - 1; i >= 0; --i) {
+    for (var i = _used; --i >= 0; ) {

[zra, 2014/11/18 19:04:45]

Same comment

[regis, 2014/11/18 23:19:54]

Done.

       r_digits[i + n] = digits[i];
     }
     for (var i = n - 1; i >= 0; --i) {
       r_digits[i] = 0;
     }
     r._used = r_used;
     r._neg = _neg;
+    // Set leading zero for 64-bit processing.
+    if (r_used > 0) {
+      r_digits[r_used] = 0;
+    }
   }
 
   // r = this >> n*DIGIT_BITS.
   void _drShiftTo(int n, _Bigint r) {
     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) {
       r_digits[i - n] = digits[i];
     }
     r._used = r_used;
     r._neg = _neg;
+    // Set leading zero for 64-bit processing.
+    if (r_used > 0) {
+      r_digits[r_used] = 0;
+    }
     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 32 matching lines @@
     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);
@@ skipping 503 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);
@@ skipping 422 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) {
       _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 44 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);
   }
 }