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

runtime/lib/bigint.dart

Index: runtime/lib/bigint.dart
===================================================================
--- runtime/lib/bigint.dart	(revision 41808)
+++ runtime/lib/bigint.dart	(working copy)
@@ -203,36 +203,51 @@
   _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;
   }
 
@@ -253,7 +268,7 @@
     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) {
@@ -261,6 +276,10 @@
     }
     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.
@@ -269,10 +288,12 @@
     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;
@@ -289,6 +310,10 @@
     }
     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++) {
@@ -341,9 +366,11 @@
       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;
@@ -867,6 +894,11 @@
     // 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;
@@ -873,7 +905,7 @@
     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;
     }
@@ -887,11 +919,16 @@
   // 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;
     }
@@ -970,6 +1007,7 @@
     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);
@@ -977,6 +1015,7 @@
     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) {
@@ -1419,6 +1458,7 @@
     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) {