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";

[Vyacheslav Egorov (Google), 2014/09/10 11:44:12]

Any reason why is this not a real field?

This is completely nontransparent for the optimizer. 

Even if you recognize and inline this as LoadField with an offset it will still
be worse because optimizer can't used Field based aliasing for fields that we
refer by offsets.

[regis, 2014/09/10 17:34:17]

Class _Bigint being part of the integer class hierarchy, we need handles for it.
It is also used early in bootstrapping the system (e.g. bigint literals in
source), so we need to be able to allocate and initialize a bigint instance from
C++ without calling into Dart.

So either we declare the fields in Dart and make access from C++ somewhat
complicated, or we declare them in C++ (RawBigint) and provide native accessors.

Ivan and Srdjan recommended the second approach and suggested to handle the 3
required fields like the length field of Array.

I am opened to either way, as long as it is efficient.

I do not expect field accesses to be the bottleneck anyway. The fields neg and
used are typically accessed once in each method and I plan to introduce local
variables to cache the digits field.

[Vyacheslav Egorov (Google), 2014/09/10 17:40:44]

But we can force fields declared in the dart code into offsets "expected
offsets" known to C++ code, e.g. we deal with offsetInBytes in TypedData in this
manner.

I think is totally preferable to having a getter like this that does nothing but
marshall a field from C++ side and then having intrinsic for it.

+  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(_Bigint 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(int n, _Bigint 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(int n, _Bigint 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(int n, _Bigint 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(int n, _Bigint 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(_Bigint 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(_Bigint 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(_Bigint a, _Bigint 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(_Bigint a, _Bigint 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(_Bigint a, _Bigint 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(_Bigint a, _Bigint 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(_Bigint a, _Bigint 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(_Bigint a, _Bigint 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.
+  _Bigint _andTo(_Bigint a, _Bigint 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.
+  _Bigint _andNotTo(_Bigint a, _Bigint 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.
+  _Bigint _orTo(_Bigint a, _Bigint 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.
+  _Bigint _xorTo(_Bigint a, _Bigint 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.
+  _Bigint _notTo(_Bigint 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.
+  _Bigint _addTo(_Bigint a, _Bigint 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.
+  _Bigint _subTo(_Bigint a, _Bigint 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(_Bigint a, _Bigint 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(_Bigint 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(_Bigint a, _Bigint q, _Bigint 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(int count, int 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);
+  }
+}
+