Implement bigint shift intrinsics 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 267 matching lines @@
   }
 
   // Return this << n.
   _Bigint _lShift(int n) {
     final ds = n ~/ _DIGIT_BITS;
     final bs = n % _DIGIT_BITS;
     if (bs == 0) {
       return _dlShift(ds);
     }
     var r_used = _used + ds + 1;
-    var r_digits = new Uint32List(r_used + (r_used & 1));
+    var r_digits = new Uint32List(r_used + 2 + (r_used & 1));  // +2 for 64-bit.
     _lsh(_digits, _used, n, r_digits);
     return new _Bigint(_neg, r_used, r_digits);
   }
 
   // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n.
   // Return r_used.
   static int _lShiftDigits(Uint32List x_digits, int x_used, int n,
                            Uint32List r_digits) {
     final ds = n ~/ _DIGIT_BITS;
     final bs = n % _DIGIT_BITS;
     if (bs == 0) {
       return _dlShiftDigits(x_digits, x_used, ds, r_digits);
     }
     var r_used = x_used + ds + 1;
-    assert(r_digits.length >= r_used + (r_used & 1));
+    assert(r_digits.length >= r_used + 2 + (r_used & 1));  // +2 for 64-bit.
     _lsh(x_digits, x_used, n, r_digits);
     if (r_digits[r_used - 1] == 0) {
       r_used--;  // Clamp result.
     } else if (r_used.isOdd) {
       r_digits[r_used] = 0;
     }
     return r_used;
   }
 
   // r_digits[0..r_used-1] = x_digits[0..x_used-1] >> n.
@@ skipping 650 matching lines @@
     if (a._used.isOdd) {
       nsh += _DIGIT_BITS;
     }
     // Concatenated positive quotient and normalized positive remainder.
     var r_digits;
     var r_used;
     // Normalized positive divisor.
     var y_digits;
     var y_used;
     if (nsh > 0) {
-      y_digits = new Uint32List(a._used + 3);  // +3 for normalization.
+      y_digits = new Uint32List(a._used + 5);  // +5 for norm. and 64-bit.
       y_used = _lShiftDigits(a._digits, a._used, nsh, y_digits);
-      r_digits = new Uint32List(_used + 3);  // +3 for normalization.
+      r_digits = new Uint32List(_used + 5);  // +5 for normalization and 64-bit.
       r_used = _lShiftDigits(_digits, _used, nsh, r_digits);
     } else {
       y_digits = a._digits;
       y_used = a._used;
       r_digits = _cloneDigits(_digits, 0, _used, _used + 2);
       r_used = _used;
     }
     Uint32List yt_qd = new Uint32List(4);
     yt_qd[_YT_LO] = y_digits[y_used - 2];
     yt_qd[_YT] = y_digits[y_used - 1];
@@ skipping 365 matching lines @@
 
   // Returns pow(this, e) % m, with e >= 0, m > 0.
   int modPow(int e, int m) {
     if (e is! int) throw new ArgumentError(e);
     if (m is! int) throw new ArgumentError(m);
     if (e < 0) throw new RangeError(e);
     if (m <= 0) throw new RangeError(m);
     if (e == 0) return 1;
     m = m._toBigint();
     final m_used = m._used;
-    final m_used2p2 = 2*m_used + 2;
+    final m_used2p4 = 2*m_used + 4;
     final e_bitlen = e.bitLength;
     if (e_bitlen <= 0) return 1;
     final bool cannotUseMontgomery = m.isEven || _abs() >= m;
     if (cannotUseMontgomery || e_bitlen < 64) {
       _Reduction z = (cannotUseMontgomery || e_bitlen < 8) ?
           new _Classic(m) : new _Montgomery(m);
       // TODO(regis): Should we use Barrett reduction for an even modulus and a
       // large exponent?
-      var r_digits = new Uint32List(m_used2p2);
-      var r2_digits = new Uint32List(m_used2p2);
+      var r_digits = new Uint32List(m_used2p4);
+      var r2_digits = new Uint32List(m_used2p4);
       var g_digits = new Uint32List(m_used + (m_used & 1));
       var g_used = z._convert(this, g_digits);
       // Initialize r with g.
       var j = g_used + (g_used & 1);  // Copy leading zero if any.
       while (--j >= 0) {
         r_digits[j] = g_digits[j];
       }
       var r_used = g_used;
       var r2_used;
       var i = e_bitlen - 1;
@@ skipping 21 matching lines @@
     else k = 6;
     _Reduction z = new _Montgomery(m);
     var n = 3;
     final k1 = k - 1;
     final km = (1 << k) - 1;
     List g_digits = new List(km + 1);
     List g_used = new List(km + 1);
     g_digits[1] = new Uint32List(m_used + (m_used & 1));
     g_used[1] = z._convert(this, g_digits[1]);
     if (k > 1) {
-      var g2_digits = new Uint32List(m_used2p2);
+      var g2_digits = new Uint32List(m_used2p4);
       var g2_used = z._sqr(g_digits[1], g_used[1], g2_digits);
       while (n <= km) {
-        g_digits[n] = new Uint32List(m_used2p2);
+        g_digits[n] = new Uint32List(m_used2p4);
         g_used[n] = z._mul(g2_digits, g2_used,
                            g_digits[n - 2], g_used[n - 2],
                            g_digits[n]);
         n += 2;
       }
     }
     var w;
     var is1 = true;
     var r_digits = _ONE._digits;
     var r_used = _ONE._used;
-    var r2_digits = new Uint32List(m_used2p2);
+    var r2_digits = new Uint32List(m_used2p4);
     var r2_used;
     var e_digits = e._digits;
     var j = e._used - 1;
     var i = _nbits(e_digits[j]) - 1;
     while (j >= 0) {
       if (i >= k1) {
         w = (e_digits[j] >> (i - k1)) & km;
       } else {
         w = (e_digits[j] & ((1 << (i + 1)) - 1)) << (k1 - i);
         if (j > 0) {
           w |= e_digits[j - 1] >> (_DIGIT_BITS + i - k1);
         }
       }
       n = k;
       while ((w & 1) == 0) {
         w >>= 1;
         --n;
       }
       if ((i -= n) < 0) {
         i += _DIGIT_BITS;
         --j;
       }
       if (is1) {  // r == 1, don't bother squaring or multiplying it.
-        r_digits = new Uint32List(m_used2p2);
+        r_digits = new Uint32List(m_used2p4);
         r_used = g_used[w];
         var gw_digits = g_digits[w];
         var ri = r_used + (r_used & 1);  // Copy leading zero if any.
         while (--ri >= 0) {
           r_digits[ri] = gw_digits[ri];
         }
         is1 = false;
       }
       else {
         while (n > 1) {
@@ skipping 299 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);
   }
 }