New bigint implementation in the vm.

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
+ * Copyright (c) 2012 Adam Singer (adam@solvr.io)
+ * All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
+ * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * IN NO EVENT SHALL TOM WU BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
+ * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER
+ * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF
+ * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT
+ * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * In addition, the following condition applies:
+ *
+ * All redistributions must retain an intact copy of this copyright notice
+ * and disclaimer.
+ */
+
+class _Bigint extends _IntegerImplementation implements int {
+  // Bits per digit.
+  static const int DIGIT_BITS = 32;
+  static const int DIGIT_BASE = 1 << DIGIT_BITS;
+  static const int DIGIT_MASK = (1 << DIGIT_BITS) - 1;
+
+  // Bits per half digit.
+  static const int DIGIT2_BITS = DIGIT_BITS >> 1;
+  static const int DIGIT2_BASE = 1 << DIGIT2_BITS;
+  static const int DIGIT2_MASK = (1 << DIGIT2_BITS) - 1;
+
+  // Allocate extra digits so the bigint can be reused.
+  static const int EXTRA_DIGITS = 4;
+
+  // Floating-point unit integer precision.
+  static const int FP_BITS = 52;
+  static const int FP_BASE = 1 << FP_BITS;
+  static const int FP_D1 = FP_BITS - DIGIT_BITS;
+  static const int FP_D2 = 2 * DIGIT_BITS - FP_BITS;
+
+  // 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);
+
+  // 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 neg) native "Bigint_setNeg";
+  int get _used native "Bigint_getUsed";
+  void set _used(int used) native "Bigint_setUsed";
+  Uint32List get _digits native "Bigint_getDigits";
+  void set _digits(Uint32List digits) native "Bigint_setDigits";
+
+  // Factory returning an instance initialized to value 0.
+  factory _Bigint() native "Bigint_allocate";
+
+  // Factory returning an instance initialized to an integer value.
+  factory _Bigint._fromInt(int i) {
+    return new _Bigint()._setInt(i);
+  }
+
+  // Factory returning an instance initialized to a hex string.
+  factory _Bigint._fromHex(String s) {
+    return new _Bigint()._setHex(s);
+  }
+
+  // Factory returning an instance initialized to a double value given by its
+  // components.
+  factory _Bigint._fromDouble(int sign, int significand, int exponent) {
+    return new _Bigint()._setDouble(sign, significand, exponent);
+  }
+
+  // Initialize instance to the given value no larger than a Mint.
+  _Bigint _setInt(int i) {
+    assert(i is! _Bigint);
+    _ensureLength(2);
+    _used = 2;
+    var l, h;
+    if (i < 0) {
+      _neg = true;
+      if (i == MIN_INT64) {
+        l = 0;
+        h = 0x80000000;
+      } else {
+        l = (-i) & DIGIT_MASK;
+        h = (-i) >> DIGIT_BITS;
+      }
+    } else {
+      _neg = false;
+      l = i & DIGIT_MASK;
+      h = i >> DIGIT_BITS;
+    }
+    _digits[0] = l;
+    _digits[1] = h;
+    _clamp();
+    return this;
+  }
+
+  // Initialize instance to the given hex string.
+  // TODO(regis): Copy Bigint::NewFromHexCString, fewer digit accesses.
+  // TODO(regis): Unused.
+  _Bigint _setHex(String s) {
+    const int HEX_BITS = 4;
+    const int HEX_DIGITS_PER_DIGIT = 8;
+    var hexDigitIndex = s.length;
+    _ensureLength((hexDigitIndex + HEX_DIGITS_PER_DIGIT - 1) ~/ HEX_DIGITS_PER_DIGIT);
+    var bitIndex = 0;
+    while (--hexDigitIndex >= 0) {
+      var digit = DIGIT_TABLE[s.codeUnitAt(hexDigitIndex)];
+      if (digit = null) {
+        if (s[hexDigitIndex] == "-") _neg = true;
+        continue;  // Ignore invalid digits.
+      }
+      _neg = false;  // Ignore "-" if not at index 0.
+      if (bitIndex == 0) {
+        _digits[_used++] = digit;
+        // TODO(regis): What if too many bad digits were ignored and
+        // _used becomes larger than _digits.length? error or reallocate?
+      } else {
+        _digits[_used - 1] |= digit << bitIndex;
+      }
+      bitIndex = (bitIndex + HEX_BITS) % DIGIT_BITS;
+    }
+    _clamp();
+    return this;
+  }
+
+  // Initialize instance to the given double value.
+  _Bigint _setDouble(int sign, int significand, int exponent) {
+    assert(significand >= 0);
+    assert(exponent >= 0);
+    _setInt(significand);
+    _neg = sign < 0;
+    if (exponent > 0) {
+      _lShiftTo(exponent, this);
+    }
+    return this;
+  }
+
+  // Create digit conversion table for parsing.
+  static Map<int, int> _createDigitTable() {
+    Map table = new HashMap();
+    int digit, value;
+    digit = "0".codeUnitAt(0);
+    for(value = 0; value <= 9; ++value) table[digit++] = value;
+    digit = "a".codeUnitAt(0);
+    for(value = 10; value < 36; ++value) table[digit++] = value;
+    digit = "A".codeUnitAt(0);
+    for(value = 10; value < 36; ++value) table[digit++] = value;
+    return table;
+  }
+
+  // Return most compact integer (i.e. possibly Smi or Mint).
+  // TODO(regis): Intrinsify.
+  int _toValidInt() {
+    assert(DIGIT_BITS == 32);  // Otherwise this code needs to be revised.
+    if (_used == 0) return 0;
+    if (_used == 1) return _neg ? -_digits[0] : _digits[0];
+    if (_used > 2) return this;
+    if (_neg) {
+      if (_digits[1] > 0x80000000) return this;
+      if (_digits[1] == 0x80000000) {
+        if (_digits[0] > 0) return this;
+        return MIN_INT64;
+      }
+      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.
+  void _ensureLength(int length) {
+    if (length > 0 && (_digits == null || length > _digits.length)) {
+      var new_digits = new Uint32List(length + EXTRA_DIGITS);
+      if (_digits != null) {
+        for (var i = _used; --i >= 0; ) {
+          new_digits[i] = _digits[i];
+        }
+      }
+      _digits = new_digits;
+    }
+  }
+
+  // Clamp off excess high _digits.
+  void _clamp() {
+    while (_used > 0 && _digits[_used - 1] == 0) {
+      --_used;
+    }
+    assert(_used > 0 || !_neg);
+  }
+
+  // Copy this to r.
+  void _copyTo(r) {
+    r._ensureLength(_used);
+    for (var i = _used - 1; i >= 0; --i) {
+      r._digits[i] = _digits[i];
+    }
+    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(n, r) {
+    var r_used = _used + n;
+    r._ensureLength(r_used);
+    for (var i = _used - 1; i >= 0; --i) {
+      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;
+  }
+
+  // r = this >> n*DIGIT_BITS.
+  void _drShiftTo(n, r) {
+    var r_used = _used - n;
+    if (r_used < 0) {
+      if (_neg) {
+        // Set r to -1.
+        r._neg = true;
+        r._ensureLength(1);
+        r._used = 1;
+        r._digits[0] = 1;
+      } else {
+        // Set r to 0.
+        r._neg = false;
+        r._used = 0;
+      }
+      return;
+    }
+    r._ensureLength(r_used);
+    for (var i = n; i < _used; ++i) {
+      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;
+        }
+      }
+    }
+  }
+
+  // r = this << n.
+  void _lShiftTo(n, r) {
+    var ds = n ~/ DIGIT_BITS;
+    var bs = n % DIGIT_BITS;
+    if (bs == 0) {
+      _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 c = 0;
+    for (var i = _used - 1; i >= 0; --i) {
+      r._digits[i + ds + 1] = (_digits[i] >> cbs) | c;
+      c = (_digits[i] & bm) << bs;
+    }
+    for (var i = ds - 1; i >= 0; --i) {
+      r._digits[i] = 0;
+    }
+    r._digits[ds] = c;
+    r._used = r_used;
+    r._neg = _neg;
+    r._clamp();
+  }
+
+  // r = this >> n.
+  void _rShiftTo(n, 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._ensureLength(1);
+        r._used = 1;
+        r._digits[0] = 1;
+      } 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);
+    r._digits[0] = _digits[ds] >> bs;
+    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);
+        return;
+      }
+      for (var i = 0; i < ds; i++) {
+        if (_digits[i] != 0) {
+          r._subTo(ONE, r);
+          return;
+        }
+      }
+    }
+  }
+
+  // Return 0 if abs(this) == abs(a).
+  // Return a positive number if abs(this) > abs(a).
+  // Return a negative number if abs(this) < abs(a).
+  int _absCompareTo(a) {
+    var r = _used - a._used;
+    if (r == 0) {
+      var i = _used;
+      while (--i >= 0 && (r = _digits[i] - a._digits[i]) == 0);
+    }
+    return r;
+  }
+
+  // Return 0 if this == a.
+  // Return a positive number if this > a.
+  // Return a negative number if this < a.
+  int _compareTo(a) {
+    var r;
+    if (_neg == a._neg) {
+      r = _absCompareTo(a);
+      if (_neg) {
+        r = -r;
+      }
+    } else if (_neg) {
+      r = -1;
+    } else {
+      r = 1;
+    }
+    return r;
+  }
+
+  // r = abs(this) + abs(a).
+  void _absAddTo(a, r) {
+    if (_used < a._used) {
+      a._absAddTo(this, r);
+      return;
+    }
+    if (_used == 0) {
+      // Set r to 0.
+      r._neg = false;
+      r._used = 0;
+      return;
+    }
+    if (a._used == 0) {
+      _copyTo(r);
+      return;
+    }
+    r._ensureLength(_used + 1);
+    var c = 0;
+    for (var i = 0; i < a._used; i++) {
+      c += _digits[i] + a._digits[i];
+      r._digits[i] = c & DIGIT_MASK;
+      c >>= DIGIT_BITS;
+    }
+    for (var i = a._used; i < _used; i++) {
+      c += _digits[i];
+      r._digits[i] = c & DIGIT_MASK;
+      c >>= DIGIT_BITS;
+    }
+    r._digits[_used] = c;
+    r._used = _used + 1;
+    r._clamp();
+  }
+
+  // r = abs(this) - abs(a), with abs(this) >= abs(a).
+  void _absSubTo(a, r) {
+    assert(_absCompareTo(a) >= 0);
+    if (_used == 0) {
+      // Set r to 0.
+      r._neg = false;
+      r._used = 0;
+      return;
+    }
+    if (a._used == 0) {
+      _copyTo(r);
+      return;
+    }
+    r._ensureLength(_used);
+    var c = 0;
+    for (var i = 0; i < a._used; i++) {
+      c += _digits[i] - a._digits[i];
+      r._digits[i] = c & DIGIT_MASK;
+      c >>= DIGIT_BITS;
+    }
+    for (var i = a._used; i < _used; i++) {
+      c += _digits[i];
+      r._digits[i] = c & DIGIT_MASK;
+      c >>= DIGIT_BITS;
+    }
+    r._used = _used;
+    r._clamp();
+  }
+
+  // r = abs(this) & abs(a).
+  void _absAndTo(a, r) {
+    var r_used = (_used < a._used) ? _used : a._used;
+    r._ensureLength(r_used);
+    for (var i = 0; i < r_used; i++) {
+      r._digits[i] = _digits[i] & a._digits[i];
+    }
+    r._used = r_used;
+    r._clamp();
+  }
+
+  // r = abs(this) &~ abs(a).
+  void _absAndNotTo(a, r) {
+    var r_used = _used;
+    r._ensureLength(r_used);
+    var m = (r_used < a._used) ? r_used : a._used;
+    for (var i = 0; i < m; i++) {
+      r._digits[i] = _digits[i] &~ a._digits[i];
+    }
+    for (var i = m; i < r_used; i++) {
+      r._digits[i] = _digits[i];
+    }
+    r._used = r_used;
+    r._clamp();
+  }
+
+  // r = abs(this) | abs(a).
+  void _absOrTo(a, r) {
+    var r_used = (_used > a._used) ? _used : a._used;
+    r._ensureLength(r_used);
+    var l, m;
+    if (_used < a._used) {
+      l = a;
+      m = _used;
+    } else {
+      l = this;
+      m = a._used;
+    }
+    for (var i = 0; i < m; i++) {
+      r._digits[i] = _digits[i] | a._digits[i];
+    }
+    for (var i = m; i < r_used; i++) {
+      r._digits[i] = l._digits[i];
+    }
+    r._used = r_used;
+    r._clamp();
+  }
+
+  // r = abs(this) ^ abs(a).
+  void _absXorTo(a, r) {
+    var r_used = (_used > a._used) ? _used : a._used;
+    r._ensureLength(r_used);
+    var l, m;
+    if (_used < a._used) {
+      l = a;
+      m = _used;
+    } else {
+      l = this;
+      m = a._used;
+    }
+    for (var i = 0; i < m; i++) {
+      r._digits[i] = _digits[i] ^ a._digits[i];
+    }
+    for (var i = m; i < r_used; i++) {
+      r._digits[i] = l._digits[i];
+    }
+    r._used = r_used;
+    r._clamp();
+  }
+
+  // Return r = this & a.
+  _andTo(a, r) {
+    if (_neg == a._neg) {
+      if (_neg) {
+        // (-this) & (-a) == ~(this-1) & ~(a-1)
+        //                == ~((this-1) | (a-1))
+        //                == -(((this-1) | (a-1)) + 1)
+        _Bigint t1 = new _Bigint();
+        _absSubTo(ONE, t1);
+        _Bigint a1 = new _Bigint();
+        a._absSubTo(ONE, a1);
+        t1._absOrTo(a1, r);
+        r._absAddTo(ONE, r);
+        r._neg = true;  // r cannot be zero if this and a are negative.
+        return r;
+      }
+      _absAndTo(a, r);
+      r._neg = false;
+      return r;
+    }
+    // _neg != a._neg
+    var p, n;
+    if (_neg) {
+      p = a;
+      n = this;
+    } else {  // & is symmetric.
+      p = this;
+      n = a;
+    }
+    // p & (-n) == p & ~(n-1) == p &~ (n-1)
+    _Bigint n1 = new _Bigint();
+    n._absSubTo(ONE, n1);
+    p._absAndNotTo(n1, r);
+    r._neg = false;
+    return r;
+  }
+
+  // Return r = this &~ a.
+  _andNotTo(a, r) {
+    if (_neg == a._neg) {
+      if (_neg) {
+        // (-this) &~ (-a) == ~(this-1) &~ ~(a-1)
+        //                 == ~(this-1) & (a-1)
+        //                 == (a-1) &~ (this-1)
+        _Bigint t1 = new _Bigint();
+        _absSubTo(ONE, t1);
+        _Bigint a1 = new _Bigint();
+        a._absSubTo(ONE, a1);
+        a1._absAndNotTo(t1, r);
+        r._neg = false;
+        return r;
+      }
+      _absAndNotTo(a, r);
+      r._neg = false;
+      return r;
+    }
+    if (_neg) {
+      // (-this) &~ a == ~(this-1) &~ a
+      //              == ~(this-1) & ~a
+      //              == ~((this-1) | a)
+      //              == -(((this-1) | a) + 1)
+      _Bigint t1 = new _Bigint();
+      _absSubTo(ONE, t1);
+      t1._absOrTo(a, r);
+      r._absAddTo(ONE, r);
+      r._neg = true;  // r cannot be zero if this is negative and a is positive.
+      return r;
+    }
+    // this &~ (-a) == this &~ ~(a-1) == this & (a-1)
+    _Bigint a1 = new _Bigint();
+    a._absSubTo(ONE, a1);
+    _absAndTo(a1, r);
+    r._neg = false;
+    return r;
+  }
+
+  // Return r = this | a.
+  _orTo(a, r) {
+    if (_neg == a._neg) {
+      if (_neg) {
+        // (-this) | (-a) == ~(this-1) | ~(a-1)
+        //                == ~((this-1) & (a-1))
+        //                == -(((this-1) & (a-1)) + 1)
+        _Bigint t1 = new _Bigint();
+        _absSubTo(ONE, t1);
+        _Bigint a1 = new _Bigint();
+        a._absSubTo(ONE, a1);
+        t1._absAndTo(a1, r);
+        r._absAddTo(ONE, r);
+        r._neg = true;  // r cannot be zero if this and a are negative.
+        return r;
+      }
+      _absOrTo(a, r);
+      r._neg = false;
+      return r;
+    }
+    // _neg != a._neg
+    var p, n;
+    if (_neg) {
+      p = a;
+      n = this;
+    } else {  // | is symmetric.
+      p = this;
+      n = a;
+    }
+    // p | (-n) == p | ~(n-1) == ~((n-1) &~ p) == -(~((n-1) &~ p) + 1)
+    _Bigint n1 = new _Bigint();
+    n._absSubTo(ONE, n1);
+    n1._absAndNotTo(p, r);
+    r._absAddTo(ONE, r);
+    r._neg = true;  // r cannot be zero if only one of this or a is negative.
+    return r;
+  }
+
+  // Return r = this ^ a.
+  _xorTo(a, r) {
+    if (_neg == a._neg) {
+      if (_neg) {
+        // (-this) ^ (-a) == ~(this-1) ^ ~(a-1) == (this-1) ^ (a-1)
+        _Bigint t1 = new _Bigint();
+        _absSubTo(ONE, t1);
+        _Bigint a1 = new _Bigint();
+        a._absSubTo(ONE, a1);
+        t1._absXorTo(a1, r);
+        r._neg = false;
+        return r;
+      }
+      _absXorTo(a, r);
+      r._neg = false;
+      return r;
+    }
+    // _neg != a._neg
+    var p, n;
+    if (_neg) {
+      p = a;
+      n = this;
+    } else {  // ^ is symmetric.
+      p = this;
+      n = a;
+    }
+    // p ^ (-n) == p ^ ~(n-1) == ~(p ^ (n-1)) == -((p ^ (n-1)) + 1)
+    _Bigint n1 = new _Bigint();
+    n._absSubTo(ONE, n1);
+    p._absXorTo(n1, r);
+    r._absAddTo(ONE, r);
+    r._neg = true;  // r cannot be zero if only one of this or a is negative.
+    return r;
+  }
+
+  // Return r = ~this.
+  _notTo(r) {
+    if (_neg) {
+      // ~(-this) == ~(~(this-1)) == this-1
+      _absSubTo(ONE, r);
+      r._neg = false;
+      return r;
+    }
+    // ~this == -this-1 == -(this+1)
+    _absAddTo(ONE, r);
+    r._neg = true;  // r cannot be zero if this is positive.
+    return r;
+  }
+
+  // Return r = this + a.
+  _addTo(a, r) {
+    var r_neg = _neg;
+    if (_neg == a._neg) {
+      // this + a == this + a
+      // (-this) + (-a) == -(this + a)
+      _absAddTo(a, r);
+    } else {
+      // this + (-a) == this - a == -(this - a)
+      // (-this) + a == a - this == -(this - a)
+      if (_absCompareTo(a) >= 0) {
+        _absSubTo(a, r);
+      } else {
+        r_neg = !r_neg;
+        a._absSubTo(this, r);
+      }
+    }
+        r._neg = r_neg;
+    return r;
+  }
+
+  // Return r = this - a.
+  _subTo(a, r) {
+        var r_neg = _neg;
+    if (_neg != a._neg) {
+                // this - (-a) == this + a
+                // (-this) - a == -(this + a)
+      _absAddTo(a, r);
+        } else {
+                // this - a == this - a == -(this - a)
+                // (-this) - (-a) == a - this == -(this - a)
+      if (_absCompareTo(a) >= 0) {
+        _absSubTo(a, r);
+                } else {
+        r_neg = !r_neg;
+        a._absSubTo(this, r);
+      }
+    }
+        r._neg = r_neg;
+    return r;
+  }
+
+  // Accumulate multiply.
+  // this[i..i+n-1]: bigint multiplicand.
+  // x: digit multiplier.
+  // w[j..j+n-1]: bigint accumulator.
+  // c: int carry in.
+  // Returns carry out.
+  // w[j..j+n-1] += this[i..i+n-1] * x + c.
+  // Returns carry out.
+  // TODO(regis): _sqrTo is the only caller passing an x possibly larger than
+  // a digit (2*digit) and passing a non-zero carry in. Refactor?
+  int _am(int i, int x, _Bigint w, int j, int c, int n) {
+    if (x == 0 && c == 0) {
+      // No-op if both x and c are 0.
+      return 0;
+    }
+    int xl = x & DIGIT2_MASK;
+    int xh = x >> DIGIT2_BITS;
+    while (--n >= 0) {
+      int l = _digits[i] & DIGIT2_MASK;
+      int h = _digits[i++] >> DIGIT2_BITS;
+      int m = xh*l + h*xl;
+      l = xl*l + ((m & DIGIT2_MASK) << DIGIT2_BITS) + w._digits[j] + c;
+      c = (l >> DIGIT_BITS) + (m >> DIGIT2_BITS) + xh*h;
+      w._digits[j++] = l & DIGIT_MASK;
+    }
+    return c;
+  }
+
+  // r = this * a.
+  void _mulTo(a, r) {
+    // TODO(regis): Use karatsuba multiplication when appropriate.
+    var i = _used;
+    r._ensureLength(i + a._used);
+    r._used = i + a._used;
+    while (--i >= 0) {
+      r._digits[i] = 0;
+    }
+    for (i = 0; i < a._used; ++i) {
+      // TODO(regis): Replace _am with addMulVVW.
+      r._digits[i + _used] = _am(0, a._digits[i], r, i, 0, _used);
+    }
+    r._clamp();
+    r._neg = r._used > 0 && _neg != a._neg;  // Zero cannot be negative.
+  }
+
+  // r = this^2, r != this.
+  void _sqrTo(r) {
+    var i = 2 * _used;
+    r._ensureLength(i);
+    r._used = i;
+    while (--i >= 0) {
+      r._digits[i] = 0;
+    }
+    for (i = 0; i < _used - 1; ++i) {
+      var c = _am(i, _digits[i], r, 2*i, 0, 1);
+      var d = r._digits[i + _used];
+      d += _am(i + 1, _digits[i] << 1, r, 2*i + 1, c, _used - i - 1);
+      if (d >= DIGIT_BASE) {
+        r._digits[i + _used] = d - DIGIT_BASE;
+        r._digits[i + _used + 1] = 1;
+      } else {
+        r._digits[i + _used] = d;
+      }
+    }
+    if (r._used > 0) {
+      r._digits[r._used - 1] += _am(i, _digits[i], r, 2*i, 0, 1);
+    }
+    r._neg = false;
+    r._clamp();
+  }
+
+  // Truncating division and remainder.
+  // If q != null, q = trunc(this / a).
+  // If r != null, r = this - a * trunc(this / a).
+  void _divRemTo(a, q, r) {
+    if (a._used == 0) return;
+    if (_used < a._used) {
+      if (q != null) {
+        // Set q to 0.
+        q._neg = false;
+        q._used = 0;
+      }
+      if (r != null) {
+        _copyTo(r);
+      }
+      return;
+    }
+    if (r == null) {
+      r = new _Bigint();
+    }
+    var y = new _Bigint();
+    var nsh = DIGIT_BITS - _nbits(a._digits[a._used - 1]);  // normalize modulus
+    if (nsh > 0) {
+      a._lShiftTo(nsh, y);
+      _lShiftTo(nsh, r);
+    }
+    else {
+      a._copyTo(y);
+      _copyTo(r);
+    }
+    // We consider this and a positive. Ignore the copied sign.
+    y._neg = false;
+    r._neg = false;
+    var y_used = y._used;
+    var y0 = y._digits[y_used - 1];
+    if (y0 == 0) return;
+    var yt = y0*(1 << FP_D1) + ((y_used > 1) ? y._digits[y_used - 2] >> FP_D2 : 0);
+    var d1 = FP_BASE/yt;
+    var d2 = (1 << FP_D1)/yt;
+    var e = 1 << FP_D2;
+    var i = r._used;
+    var j = i - y_used;
+    _Bigint t = (q == null) ? new _Bigint() : q;
+
+    y._dlShiftTo(j, t);
+
+    if (r._compareTo(t) >= 0) {
+      r._digits[r._used++] = 1;
+      r._subTo(t, r);
+    }
+    ONE._dlShiftTo(y_used, t);
+    t._subTo(y, y);  // "negative" y so we can replace sub with _am later
+    while (y._used < y_used) {
+      y._digits[y._used++] = 0;
+    }
+    while (--j >= 0) {
+      // Estimate quotient digit
+      var qd = (r._digits[--i] == y0)
+          ? DIGIT_MASK
+          : (r._digits[i]*d1 + (r._digits[i - 1] + e)*d2).floor();
+      if ((r._digits[i] += y._am(0, qd, r, j, 0, y_used)) < qd) {  // Try it out
+        y._dlShiftTo(j, t);
+        r._subTo(t, r);
+        while (r._digits[i] < --qd) {
+          r._subTo(t, r);
+        }
+      }
+    }
+    if (q != null) {
+      r._drShiftTo(y_used, q);
+      if (_neg != a._neg) {
+        ZERO._subTo(q, q);
+      }
+    }
+    r._used = y_used;
+    r._clamp();
+    if (nsh > 0) {
+      r._rShiftTo(nsh, r);  // Denormalize remainder
+    }
+    if (_neg) {
+      ZERO._subTo(r, r);
+    }
+  }
+
+  int get _identityHashCode {
+    return this;
+  }
+  int operator ~() {
+    _Bigint result = new _Bigint();
+    _notTo(result);
+    return result._toValidInt();
+  }
+
+  int get bitLength {
+    if (_used == 0) return 0;
+    if (_neg) return (~this).bitLength;
+    return DIGIT_BITS*(_used - 1) + _nbits(_digits[_used - 1]);
+  }
+
+  // This method must support smi._toBigint()._shrFromInt(int).
+  int _shrFromInt(int other) {
+    if (_used == 0) return other;  // Shift amount is zero.
+    if (_neg) throw "negative shift amount";  // TODO(regis): What exception?
+    assert(DIGIT_BITS == 32);  // Otherwise this code needs to be revised.
+    var shift;
+    if (_used > 2 || (_used == 2 && _digits[1] > 0x10000000)) {
+      if (other < 0) {
+        return -1;
+      } else {
+        return 0;
+      }
+    } else {
+      shift = ((_used == 2) ? (_digits[1] << DIGIT_BITS) : 0) + _digits[0];
+    }
+    _Bigint result = new _Bigint();
+    other._toBigint()._rShiftTo(shift, result);
+    return result._toValidInt();
+  }
+
+  // This method must support smi._toBigint()._shlFromInt(int).
+  // An out of memory exception is thrown if the result cannot be allocated.
+  int _shlFromInt(int other) {
+    if (_used == 0) return other;  // Shift amount is zero.
+    if (_neg) throw "negative shift amount";  // TODO(regis): What exception?
+    assert(DIGIT_BITS == 32);  // Otherwise this code needs to be revised.
+    var shift;
+    if (_used > 2 || (_used == 2 && _digits[1] > 0x10000000)) {
+      throw new OutOfMemoryError();
+    } else {
+      shift = ((_used == 2) ? (_digits[1] << DIGIT_BITS) : 0) + _digits[0];
+    }
+    _Bigint result = new _Bigint();
+    other._toBigint()._lShiftTo(shift, result);
+    return result._toValidInt();
+  }
+
+  int pow(int exponent) {
+    throw "Bigint.pow not implemented";
+  }
+
+  // Overriden operators and methods.
+
+  // The following operators override operators of _IntegerImplementation for
+  // efficiency, but are not necessary for correctness. They shortcut native
+  // calls that would return null because the receiver is _Bigint.
+  num operator +(num other) {
+    return other._toBigint()._addFromInteger(this);
+  }
+  num operator -(num other) {
+    return other._toBigint()._subFromInteger(this);
+  }
+  num operator *(num other) {
+    return other._toBigint()._mulFromInteger(this);
+  }
+  num operator ~/(num other) {
+    if ((other is int) && (other == 0)) {
+      throw const IntegerDivisionByZeroException();
+    }
+    return other._toBigint()._truncDivFromInteger(this);
+  }
+  num operator /(num other) {
+    return this.toDouble() / other.toDouble();
+  }
+  // TODO(regis): Investigate strange behavior with % double.INFINITY.
+  /*
+  num operator %(num other) {
+    if ((other is int) && (other == 0)) {
+      throw const IntegerDivisionByZeroException();
+    }
+    return other._toBigint()._moduloFromInteger(this);
+  }
+  */
+  int operator &(int other) {
+    return other._toBigint()._bitAndFromInteger(this);
+  }
+  int operator |(int other) {
+    return other._toBigint()._bitOrFromInteger(this);
+  }
+  int operator ^(int other) {
+    return other._toBigint()._bitXorFromInteger(this);
+  }
+  int operator >>(int other) {
+    return other._toBigint()._shrFromInt(this);
+  }
+  int operator <<(int other) {
+    return other._toBigint()._shlFromInt(this);
+  }
+  // End of operator shortcuts.
+
+  int operator -() {
+    if (_used == 0) {
+      return this;
+    }
+    var r = new _Bigint();
+    _copyTo(r);
+    r._neg = !_neg;
+    return r._toValidInt();
+  }
+
+  int get sign {
+    return (_used == 0) ? 0 : _neg ? -1 : 1;
+  }
+
+  bool get isEven => _used == 0 || (_digits[0] & 1) == 0;
+  bool get isNegative => _neg;
+
+  _leftShiftWithMask32(count, mask) {
+    if (_used == 0) return 0;
+    if (count is! _Smi) {
+      _shlFromInt(count);  // Throws out of memory exception.
+    }
+    assert(DIGIT_BITS == 32);  // Otherwise this code needs to be revised.
+    if (count > 31) return 0;
+    return (_digits[0] << count) & mask;
+  }
+
+  int _bitAndFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    other._toBigint()._andTo(this, result);
+    return result._toValidInt();
+  }
+  int _bitOrFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    other._toBigint()._orTo(this, result);
+    return result._toValidInt();
+  }
+  int _bitXorFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    other._toBigint()._xorTo(this, result);
+    return result._toValidInt();
+  }
+  int _addFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    other._toBigint()._addTo(this, result);
+    return result._toValidInt();
+  }
+  int _subFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    other._toBigint()._subTo(this, result);
+    return result._toValidInt();
+  }
+  int _mulFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    other._toBigint()._mulTo(this, result);
+    return result._toValidInt();
+  }
+  int _truncDivFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    other._toBigint()._divRemTo(this, result, null);
+    return result._toValidInt();
+  }
+  int _moduloFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    var ob = other._toBigint();
+    other._toBigint()._divRemTo(this, null, result);
+    if (result._neg) {
+      if (_neg) {
+        result._subTo(this, result);
+      } else {
+        result._addTo(this, result);
+      }
+    }
+    return result._toValidInt();
+  }
+  int _remainderFromInteger(int other) {
+    _Bigint result = new _Bigint();
+    other._toBigint()._divRemTo(this, null, result);
+    return result._toValidInt();
+  }
+  bool _greaterThanFromInteger(int other) {
+    return other._toBigint()._compareTo(this) > 0;
+  }
+  bool _equalToInteger(int other) {
+    return other._toBigint()._compareTo(this) == 0;
+  }
+
+  // New method to support crypto.
+
+  // Return this.pow(e) mod m, with 256 <= e < 1<<32.
+  int modPow(int e, int m) {
+    assert(e >= 256 && !m.isEven());
+    if (e >= (1 << 32)) {
+      throw "Bigint.modPow with exponent larger than 32-bit not implemented";
+    }
+    _Reduction z = new _Montgomery(m);
+    var r = new _Bigint();
+    var r2 = new _Bigint();
+    var g = z.convert(this);
+    int i = _nbits(e) - 1;
+    g._copyTo(r);
+    while (--i >= 0) {
+      z.sqrTo(r, r2);
+      if ((e & (1 << i)) > 0) {
+        z.mulTo(r2, g, r);
+      } else {
+        var t = r;
+        r = r2;
+        r2 = t;
+      }
+    }
+    return z.revert(r)._toValidInt();
+  }
+}
+
+// New classes to support crypto (modPow method).
+
+class _Reduction {
+  const _Reduction();
+  _Bigint _convert(_Bigint x) => x;
+  _Bigint _revert(_Bigint x) => x;
+
+  void _mulTo(_Bigint x, _Bigint y, _Bigint r) {
+    x._mulTo(y, r);
+  }
+
+  void _sqrTo(_Bigint x, _Bigint r) {
+    x._sqrTo(r);
+  }
+}
+
+// Montgomery reduction on _Bigint.
+class _Montgomery implements _Reduction {
+  final _Bigint _m;
+  var _mp;
+  var _mpl;
+  var _mph;
+  var _um;
+  var _mused2;
+
+  _Montgomery(this._m) {
+    _mp = _m._invDigit();
+    _mpl = _mp & _Bigint.DIGIT2_MASK;
+    _mph = _mp >> _Bigint.DIGIT2_BITS;
+    _um = (1 << (_Bigint.DIGIT_BITS - _Bigint.DIGIT2_BITS)) - 1;
+    _mused2 = 2*_m._used;
+  }
+
+  // Return x*R mod _m
+  _Bigint _convert(_Bigint x) {
+    var r = new _Bigint();
+    x.abs()._dlShiftTo(_m._used, r);
+    r._divRemTo(_m, null, r);
+    if (x._neg && !r._neg && r._used > 0) {
+      _m._subTo(r, r);
+    }
+    return r;
+  }
+
+  // Return x/R mod _m
+  _Bigint _revert(_Bigint x) {
+    var r = new _Bigint();
+    x._copyTo(r);
+    _reduce(r);
+    return r;
+  }
+
+  // x = x/R mod _m
+  void _reduce(_Bigint x) {
+    x._ensureLength(_mused2 + 1);
+    while (x._used <= _mused2) {  // Pad x so _am has enough room later.
+      x._digits[x._used++] = 0;
+    }
+    for (var i = 0; i < _m._used; ++i) {
+      // Faster way of calculating u0 = x[i]*mp mod DIGIT_BASE.
+      var j = x._digits[i] & _Bigint.DIGIT2_MASK;
+      var u0 = (j*_mpl + (((j*_mph + (x._digits[i] >> _Bigint.DIGIT2_BITS)
+          *_mpl) & _um) << _Bigint.DIGIT2_BITS)) & _Bigint.DIGIT_MASK;
+      // Use _am to combine the multiply-shift-add into one call.
+      j = i + _m._used;
+      var digit = x._digits[j];
+      digit += _m ._am(0, u0, x, i, 0, _m ._used);
+      // propagate carry
+      while (digit >= _Bigint.DIGIT_BASE) {
+        digit -= _Bigint.DIGIT_BASE;
+        x._digits[j++] = digit;
+        digit = x._digits[j];
+        digit++;
+      }
+      x._digits[j] = digit;
+    }
+    x._clamp();
+    x._drShiftTo(_m ._used, x);
+    if (x._compareTo(_m ) >= 0) {
+      x._subTo(_m , x);
+    }
+  }
+
+  // r = x^2/R mod _m ; x != r
+  void _sqrTo(_Bigint x, _Bigint r) {
+    x._sqrTo(r);
+    _reduce(r);
+  }
+
+  // r = x*y/R mod _m ; x, y != r
+  void _mulTo(_Bigint x, _Bigint y, _Bigint r) {
+    x._mulTo(y, r);
+    _reduce(r);
+  }
+}
+