Add tests for gcd, modInverse and modPow that also run on dart2js.

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 249 matching lines @@
     assert(r_digits.length >= r_used + (r_used & 1));
     for (var i = n; i < x_used; i++) {
       r_digits[i - n] = x_digits[i];
     }
     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.
+  // r_digits[ds..x_used+ds] = x_digits[0..x_used-1] << (n % _DIGIT_BITS)
+  // where ds = ceil(n / _DIGIT_BITS)
+  // Doesn't clear digits below ds.
   static void _lsh(Uint32List x_digits, int x_used, int n,
                    Uint32List r_digits) {
     final ds = n ~/ _DIGIT_BITS;
     final bs = n % _DIGIT_BITS;
     final cbs = _DIGIT_BITS - bs;
     final bm = (1 << cbs) - 1;
     var c = 0;
     var i = x_used;
     while (--i >= 0) {
       final d = x_digits[i];
@@ skipping 1116 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_used2p4 = 2*m_used + 4;
+    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_used2p4);
       var r2_digits = new Uint32List(m_used2p4);
@@ skipping 137 matching lines @@
     if (inv) {
       if ((y_used == 1) && (y_digits[0] == 1)) return 1;
       if ((y_used == 0) || (y_digits[0].isEven && x_digits[0].isEven)) {
         throw new RangeError("Not coprime");
       }
     } else {
       if ((x_used == 0) || (y_used == 0)) throw new RangeError(0);
       if (((x_used == 1) && (x_digits[0] == 1)) ||
           ((y_used == 1) && (y_digits[0] == 1))) return 1;
       bool xy_cloned = false;
-      while (x.isEven && y.isEven) {
+      while (((x_digits[0] & 1) == 0) && ((y_digits[0] & 1) == 0)) {
         _rsh(x_digits, x_used, 1, x_digits);
         _rsh(y_digits, y_used, 1, y_digits);
         s++;
       }
       if (s >= _DIGIT_BITS) {
         var sd = s >> _LOG2_DIGIT_BITS;
         x_used -= sd;
         y_used -= sd;
         m_used -= sd;
       }
@@ skipping 163 matching lines @@
         } else {
           _absAdd(d_digits, abcd_used, b_digits, abcd_used, d_digits);
         }
       }
       // Exit loop if u == 0.
       var i = m_used;
       while ((i > 0) && (u_digits[i - 1] == 0)) --i;
       if (i == 0) break;
     }
     if (!inv) {
-      if (s > 0) {
-        _lsh(v_digits, m_used, s, v_digits);
-      }
-      return new _Bigint(false, m_used, v_digits)._toValidInt();
+      // TODO(regis): Make this work correctly:
+      // if (s > 0) {
+      //   m_used = _dlShiftDigits(v_digits, m_used, s, v_digits);
+      // }
+      return new _Bigint(false, m_used, v_digits)._toValidInt() << s;
     }
     // No inverse if v != 1.
     var i = m_used - 1;
     while ((i > 0) && (v_digits[i] == 0)) --i;
     if ((i != 0) || (v_digits[0] != 1)) throw new RangeError("Not coprime");
 
     if (d_neg) {
       if ((d_digits[m_used] != 0) ||
           (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
         _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
@@ skipping 307 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);
   }
 }