// 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.
 */

// A big integer number is represented by a sign, an array of 32-bit unsigned
// integers in little endian format, and a number of used digits in that array.
// The code makes sure that an even number of digits is always accessible and
// meaningful, so that pairs of digits can be processed as 64-bit unsigned
// numbers on a 64-bit platform. This requires the initialization of a leading
// zero if the number of used digits is odd.
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_MASK = (1 << _DIGIT2_BITS) - 1;

  // 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 _MINUS_ONE = new _Bigint._fromInt(-1);
  static _Bigint _ZERO = new _Bigint._fromInt(0);
  static _Bigint _ONE = new _Bigint._fromInt(1);

  // Internal data structure.
  bool get _neg native "Bigint_getNeg";
  int get _used native "Bigint_getUsed";
  Uint32List get _digits native "Bigint_getDigits";

  // Factory returning an instance initialized with the given field values.
  // The 'digits' array is first clamped and 'used' is reduced accordingly.
  // A leading zero digit may be initialized to guarantee that digit pairs can
  // be processed as 64-bit values on 64-bit platforms.
  factory _Bigint(bool neg, int used, Uint32List digits)
      native "Bigint_allocate";

  // Factory returning an instance initialized to an integer value no larger
  // than a Mint.
  factory _Bigint._fromInt(int i) {
    assert(i is! _Bigint);
    var neg;
    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;
    }
    var digits = new Uint32List(2);
    digits[0] = l;
    digits[1] = h;
    return new _Bigint(neg, 2, digits);
  }

  // Allocate an array of the given length (+1 for at least one leading zero
  // digit if odd) and copy digits[from..to-1] starting at index 0, followed by
  // leading zero digits.
  static Uint32List _cloneDigits(Uint32List digits, int from, int to,
                                 int length) {
    length += length & 1;  // Even number of digits.
    var r_digits = new Uint32List(length);
    var n = to - from;
    for (var i = 0; i < n; i++) {
      r_digits[i] = digits[from + i];
    }
    return r_digits;
  }

  // Return most compact integer (i.e. possibly Smi or Mint).
  int _toValidInt() {
    assert(_DIGIT_BITS == 32);  // Otherwise this code needs to be revised.
    var used = _used;
    if (used == 0) return 0;
    var digits = _digits;
    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;

  // Return -this.
  _Bigint _negate() {
    var used = _used;
    if (used == 0) {
      return this;
    }
    return new _Bigint(!_neg, used, _digits);
  }

  // Return abs(this).
  _Bigint _abs() {
    var neg = _neg;
    if (!neg) {
      return this;
    }
    return new _Bigint(!neg, _used, _digits);
  }

  // Return the bit length of digit x.
  static 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;
  }

  // Return this << n*_DIGIT_BITS.
  _Bigint _dlShift(int n) {
    var used = _used;
    if (used == 0) {
      return _ZERO;
    }
    var r_used = used + n;
    var digits = _digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    var i = used;
    while (--i >= 0) {
      r_digits[i + n] = digits[i];
    }
    return new _Bigint(_neg, r_used, r_digits);
  }

  // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n*_DIGIT_BITS.
  // Return r_used.
  static int _dlShiftDigits(Uint32List x_digits, int x_used, int n,
                            Uint32List r_digits) {
    if (x_used == 0) {
      return 0;
    }
    if (n == 0 && r_digits == x_digits) {
      return x_used;
    }
    var r_used = x_used + n;
    assert(r_digits.length >= r_used + (r_used & 1));
    var i = x_used;
    while (--i >= 0) {
      r_digits[i + n] = x_digits[i];
    }
    i = n;
    while (--i >= 0) {
      r_digits[i] = 0;
    }
    if (r_used.isOdd) {
      r_digits[r_used] = 0;
    }
    return r_used;
  }

  // Return this >> n*_DIGIT_BITS.
  _Bigint _drShift(int n) {
    var used = _used;
    if (used == 0) {
      return _ZERO;
    }
    var r_used = used - n;
    if (r_used <= 0) {
      return _neg ? _MINUS_ONE : _ZERO;
    }
    var digits = _digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    for (var i = n; i < used; i++) {
      r_digits[i - n] = digits[i];
    }
    var r = new _Bigint(_neg, r_used, r_digits);
    if (_neg) {
      // Round down if any bit was shifted out.
      for (var i = 0; i < n; i++) {
        if (digits[i] != 0) {
          return r._sub(_ONE);
        }
      }
    }
    return r;
  }

  // r_digits[0..r_used-1] = x_digits[0..x_used-1] >> n*_DIGIT_BITS.
  // Return r_used.
  static int _drShiftDigits(Uint32List x_digits, int x_used, int n,
                            Uint32List r_digits) {
    var r_used = x_used - n;
    if (r_used <= 0) {
      return 0;
    }
    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;
  }

  // Return this << n.
  _Bigint _lShift(int n) {
    var ds = n ~/ _DIGIT_BITS;
    var bs = n % _DIGIT_BITS;
    if (bs == 0) {
      return _dlShift(ds);
    }
    var cbs = _DIGIT_BITS - bs;
    var bm = (1 << cbs) - 1;
    var r_used = _used + ds + 1;
    var digits = _digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    var c = 0;
    var i = _used;
    while (--i >= 0) {
      r_digits[i + ds + 1] = (digits[i] >> cbs) | c;
      c = (digits[i] & bm) << bs;
    }
    r_digits[ds] = c;
    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) {
    var ds = n ~/ _DIGIT_BITS;
    var bs = n % _DIGIT_BITS;
    if (bs == 0) {
      return _dlShiftDigits(x_digits, x_used, ds, r_digits);
    }
    var cbs = _DIGIT_BITS - bs;
    var bm = (1 << cbs) - 1;
    var r_used = x_used + ds + 1;
    assert(r_digits.length >= r_used + (r_used & 1));
    var c = 0;
    var i = x_used;
    while (--i >= 0) {
      r_digits[i + ds + 1] = (x_digits[i] >> cbs) | c;
      c = (x_digits[i] & bm) << bs;
    }
    r_digits[ds] = c;
    i = ds;
    while (--i >= 0) {
      r_digits[i] = 0;
    }
    if (r_used.isOdd) {
      r_digits[r_used] = 0;
    }
    return r_used;
  }

  // Return this >> n.
  _Bigint _rShift(int n) {
    var ds = n ~/ _DIGIT_BITS;
    var bs = n % _DIGIT_BITS;
    if (bs == 0) {
      return _drShift(ds);
    }
    var r_used = _used - ds;
    if (r_used <= 0) {
      return _neg ? _MINUS_ONE : _ZERO;
    }
    var cbs = _DIGIT_BITS - bs;
    var bm = (1 << bs) - 1;
    var digits = _digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    r_digits[0] = digits[ds] >> bs;
    var used = _used;
    for (var i = ds + 1; i < used; i++) {
      r_digits[i - ds - 1] |= (digits[i] & bm) << cbs;
      r_digits[i - ds] = digits[i] >> bs;
    }
    var r = new _Bigint(_neg, r_used, r_digits);
    if (_neg) {
      // Round down if any bit was shifted out.
      if ((digits[ds] & bm) != 0) {
        return r._sub(_ONE);
      }
      for (var i = 0; i < ds; i++) {
        if (digits[i] != 0) {
          return r._sub(_ONE);
        }
      }
    }
    return r;
  }

  // r_digits[0..r_used-1] = x_digits[0..x_used-1] >> n.
  // Return r_used.
  static int _rShiftDigits(Uint32List x_digits, int x_used, int n,
                           Uint32List r_digits) {
    var ds = n ~/ _DIGIT_BITS;
    var bs = n % _DIGIT_BITS;
    if (bs == 0) {
      return _drShiftDigits(x_digits, x_used, ds, r_digits);
    }
    var r_used = x_used - ds;
    if (r_used <= 0) {
      return 0;
    }
    var cbs = _DIGIT_BITS - bs;
    var bm = (1 << bs) - 1;
    assert(r_digits.length >= r_used + (r_used & 1));
    r_digits[0] = x_digits[ds] >> bs;
    for (var i = ds + 1; i < x_used; i++) {
      r_digits[i - ds - 1] |= (x_digits[i] & bm) << cbs;
      r_digits[i - ds] = x_digits[i] >> bs;
    }
    if (r_used.isOdd) {
      r_digits[r_used] = 0;
    }
    return r_used;
  }

  // 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 _absCompare(_Bigint a) {
    var r = _used - a._used;
    if (r == 0) {
      var i = _used;
      var digits = _digits;
      var a_digits = a._digits;
      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 _compare(_Bigint a) {
    if (_neg == a._neg) {
      var r = _absCompare(a);
      return _neg ? -r : r;
    }
    return _neg ? -1 : 1;
  }

  // Compare digits[0..used-1] with a_digits[0..a_used-1].
  // Return 0 if equal.
  // Return a positive number if larger.
  // Return a negative number if smaller.
  static int _compareDigits(Uint32List digits, int used,
                            Uint32List a_digits, int a_used) {
    var r = used - a_used;
    if (r == 0) {
      var i = a_used;
      while (--i >= 0 && (r = digits[i] - a_digits[i]) == 0);
    }
    return r;
  }

  // r_digits[0..used] = digits[0..used-1] + a_digits[0..a_used-1].
  // used >= a_used > 0.
  // Note: Intrinsics on 64-bit platforms process digit pairs at even indices.
  static void _absAdd(Uint32List digits, int used,
                      Uint32List a_digits, int a_used,
                      Uint32List r_digits) {
    assert(used >= a_used && a_used > 0);
    // Verify that digit pairs are accessible for 64-bit processing.
    assert(digits.length > ((used - 1) | 1));
    assert(a_digits.length > ((a_used - 1) | 1));
    assert(r_digits.length > (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_digits[0..used-1] = digits[0..used-1] - a_digits[0..a_used-1].
  // used >= a_used > 0.
  // Note: Intrinsics on 64-bit platforms process digit pairs at even indices.
  static void _absSub(Uint32List digits, int used,
                      Uint32List a_digits, int a_used,
                      Uint32List r_digits) {
    assert(used >= a_used && a_used > 0);
    // Verify that digit pairs are accessible for 64-bit processing.
    assert(digits.length > ((used - 1) | 1));
    assert(a_digits.length > ((a_used - 1) | 1));
    assert(r_digits.length > ((used - 1) | 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;
    }
  }

  // Return abs(this) + abs(a) with sign set according to neg.
  _Bigint _absAddSetSign(_Bigint a, bool neg) {
    var used = _used;
    var a_used = a._used;
    if (used < a_used) {
      return a._absAddSetSign(this, neg);
    }
    if (used == 0) {
      assert(!neg);
      return _ZERO;
    }
    if (a_used == 0) {
      return _neg == neg ? this : this._negate();
    }
    var r_used = used + 1;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    _absAdd(_digits, used, a._digits, a_used, r_digits);
    return new _Bigint(neg, r_used, r_digits);
  }

  // Return abs(this) - abs(a) with sign set according to neg.
  // Requirement: abs(this) >= abs(a).
  _Bigint _absSubSetSign(_Bigint a, bool neg) {
    assert(_absCompare(a) >= 0);
    var used = _used;
    if (used == 0) {
      assert(!neg);
      return _ZERO;
    }
    var a_used = a._used;
    if (a_used == 0) {
      return _neg == neg ? this : this._negate();
    }
    var r_digits = new Uint32List(used + (used & 1));
    _absSub(_digits, used, a._digits, a_used, r_digits);
    return new _Bigint(neg, used, r_digits);
  }

  // Return abs(this) & abs(a) with sign set according to neg.
  _Bigint _absAndSetSign(_Bigint a, bool neg) {
    var r_used = (_used < a._used) ? _used : a._used;
    var digits = _digits;
    var a_digits = a._digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    for (var i = 0; i < r_used; i++) {
      r_digits[i] = digits[i] & a_digits[i];
    }
    return new _Bigint(neg, r_used, r_digits);
  }

  // Return abs(this) &~ abs(a) with sign set according to neg.
  _Bigint _absAndNotSetSign(_Bigint a, bool neg) {
    var r_used = _used;
    var digits = _digits;
    var a_digits = a._digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    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];
    }
    return new _Bigint(neg, r_used, r_digits);
  }

  // Return abs(this) | abs(a) with sign set according to neg.
  _Bigint _absOrSetSign(_Bigint a, bool neg) {
    var used = _used;
    var a_used = a._used;
    var r_used = (used > a_used) ? used : a_used;
    var digits = _digits;
    var a_digits = a._digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    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];
    }
    var l_digits = l._digits;
    for (var i = m; i < r_used; i++) {
      r_digits[i] = l_digits[i];
    }
    return new _Bigint(neg, r_used, r_digits);
  }

  // Return abs(this) ^ abs(a) with sign set according to neg.
  _Bigint _absXorSetSign(_Bigint a, bool neg) {
    var used = _used;
    var a_used = a._used;
    var r_used = (used > a_used) ? used : a_used;
    var digits = _digits;
    var a_digits = a._digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    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];
    }
    var l_digits = l._digits;
    for (var i = m; i < r_used; i++) {
      r_digits[i] = l_digits[i];
    }
    return new _Bigint(neg, r_used, r_digits);
  }

  // Return this & a.
  _Bigint _and(_Bigint a) {
    if (_neg == a._neg) {
      if (_neg) {
        // (-this) & (-a) == ~(this-1) & ~(a-1)
        //                == ~((this-1) | (a-1))
        //                == -(((this-1) | (a-1)) + 1)
        _Bigint t1 = _absSubSetSign(_ONE, true);
        _Bigint a1 = a._absSubSetSign(_ONE, true);
        // Result cannot be zero if this and a are negative.
        return t1._absOrSetSign(a1, true)._absAddSetSign(_ONE, true);
      }
      return _absAndSetSign(a, false);
    }
    // _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 = n._absSubSetSign(_ONE, false);
    return p._absAndNotSetSign(n1, false);
  }

  // Return this &~ a.
  _Bigint _andNot(_Bigint a) {
    if (_neg == a._neg) {
      if (_neg) {
        // (-this) &~ (-a) == ~(this-1) &~ ~(a-1)
        //                 == ~(this-1) & (a-1)
        //                 == (a-1) &~ (this-1)
        _Bigint t1 = _absSubSetSign(_ONE, true);
        _Bigint a1 = a._absSubSetSign(_ONE, true);
        return a1._absAndNotSetSign(t1, false);
      }
      return _absAndNotSetSign(a, false);
    }
    if (_neg) {
      // (-this) &~ a == ~(this-1) &~ a
      //              == ~(this-1) & ~a
      //              == ~((this-1) | a)
      //              == -(((this-1) | a) + 1)
      _Bigint t1 = _absSubSetSign(_ONE, true);
      // Result cannot be zero if this is negative and a is positive.
      return t1._absOrSetSign(a, true)._absAddSetSign(_ONE, true);
    }
    // this &~ (-a) == this &~ ~(a-1) == this & (a-1)
    _Bigint a1 = a._absSubSetSign(_ONE, true);
    return _absAndSetSign(a1, false);
  }

  // Return this | a.
  _Bigint _or(_Bigint a) {
    if (_neg == a._neg) {
      if (_neg) {
        // (-this) | (-a) == ~(this-1) | ~(a-1)
        //                == ~((this-1) & (a-1))
        //                == -(((this-1) & (a-1)) + 1)
        _Bigint t1 = _absSubSetSign(_ONE, true);
        _Bigint a1 = a._absSubSetSign(_ONE, true);
        // Result cannot be zero if this and a are negative.
        return t1._absAndSetSign(a1, true)._absAddSetSign(_ONE, true);
      }
      return _absOrSetSign(a, false);
    }
    // _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 = n._absSubSetSign(_ONE, true);
    // Result cannot be zero if only one of this or a is negative.
    return n1._absAndNotSetSign(p, true)._absAddSetSign(_ONE, true);
  }

  // Return this ^ a.
  _Bigint _xor(_Bigint a) {
    if (_neg == a._neg) {
      if (_neg) {
        // (-this) ^ (-a) == ~(this-1) ^ ~(a-1) == (this-1) ^ (a-1)
        _Bigint t1 = _absSubSetSign(_ONE, true);
        _Bigint a1 = a._absSubSetSign(_ONE, true);
        return t1._absXorSetSign(a1, false);
      }
      return _absXorSetSign(a, false);
    }
    // _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 = n._absSubSetSign(_ONE, true);
    // Result cannot be zero if only one of this or a is negative.
    return p._absXorSetSign(n1, true)._absAddSetSign(_ONE, true);
  }

  // Return ~this.
  _Bigint _not() {
    if (_neg) {
      // ~(-this) == ~(~(this-1)) == this-1
      return _absSubSetSign(_ONE, false);
    }
    // ~this == -this-1 == -(this+1)
    // Result cannot be zero if this is positive.
    return _absAddSetSign(_ONE, true);
  }

  // Return this + a.
  _Bigint _add(_Bigint a) {
    var neg = _neg;
    if (neg == a._neg) {
      // this + a == this + a
      // (-this) + (-a) == -(this + a)
      return _absAddSetSign(a, neg);
    }
    // this + (-a) == this - a == -(this - a)
    // (-this) + a == a - this == -(this - a)
    if (_absCompare(a) >= 0) {
      return _absSubSetSign(a, neg);
    }
    return a._absSubSetSign(this, !neg);
  }

  // Return this - a.
  _Bigint _sub(_Bigint a) {
    var neg = _neg;
    if (neg != a._neg) {
      // this - (-a) == this + a
      // (-this) - a == -(this + a)
      return _absAddSetSign(a, neg);
    }
    // this - a == this - a == -(this - a)
    // (-this) - (-a) == a - this == -(this - a)
    if (_absCompare(a) >= 0) {
      return _absSubSetSign(a, neg);
    }
    return a._absSubSetSign(this, !neg);
  }

  // Multiply and accumulate.
  // Input:
  //   x_digits[xi]: multiplier digit x.
  //   m_digits[i..i+n-1]: multiplicand digits.
  //   a_digits[j..j+n-1]: accumulator digits.
  // Operation:
  //   a_digits[j..j+n] += x_digits[xi]*m_digits[i..i+n-1].
  //   return 1.
  // Note: Intrinsics on 64-bit platforms process digit pairs at even indices
  //   and return 2.
  static int _mulAdd(Uint32List x_digits, int xi,
                     Uint32List m_digits, int i,
                     Uint32List a_digits, int j, int n) {
    // Verify that digit pairs are accessible for 64-bit processing.
    assert(x_digits.length > (xi | 1));
    assert(m_digits.length > ((i + n - 1) | 1));
    assert(a_digits.length > ((j + n) | 1));
    int x = x_digits[xi];
    if (x == 0) {
      // No-op if x is 0.
      return 1;
    }
    int c = 0;
    int xl = x & _DIGIT2_MASK;
    int xh = x >> _DIGIT2_BITS;
    while (--n >= 0) {
      int l = m_digits[i] & _DIGIT2_MASK;
      int h = m_digits[i++] >> _DIGIT2_BITS;
      int m = xh*l + h*xl;
      l = xl*l + ((m & _DIGIT2_MASK) << _DIGIT2_BITS) + a_digits[j] + c;
      c = (l >> _DIGIT_BITS) + (m >> _DIGIT2_BITS) + xh*h;
      a_digits[j++] = l & _DIGIT_MASK;
    }
    while (c != 0) {
      int l = a_digits[j] + c;
      c = l >> _DIGIT_BITS;
      a_digits[j++] = l & _DIGIT_MASK;
    }
    return 1;
  }

  // Square and accumulate.
  // Input:
  //   x_digits[i..used-1]: digits of operand being squared.
  //   a_digits[2*i..i+used-1]: accumulator digits.
  // Operation:
  //   a_digits[2*i..i+used-1] += x_digits[i]*x_digits[i] +
  //                              2*x_digits[i]*x_digits[i+1..used-1].
  //   return 1.
  // Note: Intrinsics on 64-bit platforms process digit pairs at even indices
  //   and return 2.
  static int _sqrAdd(Uint32List x_digits, int i,
                     Uint32List a_digits, int used) {
    // Verify that digit pairs are accessible for 64-bit processing.
    assert(x_digits.length > ((used - 1) | 1));
    assert(a_digits.length > ((i + used - 1) | 1));
    int x = x_digits[i];
    if (x == 0) return 1;
    int j = 2*i;
    int c = 0;
    int xl = x & _DIGIT2_MASK;
    int xh = x >> _DIGIT2_BITS;
    int m = 2*xh*xl;
    int l = xl*xl + ((m & _DIGIT2_MASK) << _DIGIT2_BITS) + a_digits[j];
    c = (l >> _DIGIT_BITS) + (m >> _DIGIT2_BITS) + xh*xh;
    a_digits[j] = l & _DIGIT_MASK;
    x <<= 1;
    xl = x & _DIGIT2_MASK;
    xh = x >> _DIGIT2_BITS;
    int n = used - i - 1;
    int k = i + 1;
    j++;
    while (--n >= 0) {
      int l = x_digits[k] & _DIGIT2_MASK;
      int h = x_digits[k++] >> _DIGIT2_BITS;
      int m = xh*l + h*xl;
      l = xl*l + ((m & _DIGIT2_MASK) << _DIGIT2_BITS) + a_digits[j] + c;
      c = (l >> _DIGIT_BITS) + (m >> _DIGIT2_BITS) + xh*h;
      a_digits[j++] = l & _DIGIT_MASK;
    }
    c += a_digits[i + used];
    if (c >= _DIGIT_BASE) {
      a_digits[i + used] = c - _DIGIT_BASE;
      a_digits[i + used + 1] = 1;
    } else {
      a_digits[i + used] = c;
    }
    return 1;
  }

  // Return this * a.
  _Bigint _mul(_Bigint a) {
    // TODO(regis): Use karatsuba multiplication when appropriate.
    var used = _used;
    var a_used = a._used;
    if (used == 0 || a_used == 0) {
      return _ZERO;
    }
    var r_used = used + a_used;
    var digits = _digits;
    var a_digits = a._digits;
    var r_digits = new Uint32List(r_used + (r_used & 1));
    var i = 0;
    while (i < a_used) {
      i += _mulAdd(a_digits, i, digits, 0, r_digits, i, used);
    }
    return new _Bigint(_neg != a._neg, r_used, r_digits);
  }

  // r_digits[0..r_used-1] = x_digits[0..x_used-1]*a_digits[0..a_used-1].
  // Return r_used = x_used + a_used.
  static int _mulDigits(Uint32List x_digits, int x_used,
                        Uint32List a_digits, int a_used,
                        Uint32List r_digits) {
    var r_used = x_used + a_used;
    var i = r_used + (r_used & 1);
    assert(r_digits.length >= i);
    while (--i >= 0) {
      r_digits[i] = 0;
    }
    i = 0;
    while (i < a_used) {
      i += _mulAdd(a_digits, i, x_digits, 0, r_digits, i, x_used);
    }
    return r_used;
  }

  // Return this^2.
  _Bigint _sqr() {
    var used = _used;
    if (used == 0) {
      return _ZERO;
    }
    var r_used = 2 * used;
    var digits = _digits;
    var r_digits = new Uint32List(r_used);
    // Since r_used is even, no need for a leading zero for 64-bit processing.
    var i = 0;
    while (i < used - 1) {
      i += _sqrAdd(digits, i, r_digits, used);
    }
    // The last step is already done if digit pairs were processed above.
    if (i < used) {
      _mulAdd(digits, i, digits, i, r_digits, 2*i, 1);
    }
    return new _Bigint(false, r_used, r_digits);
  }

  // r_digits[0..r_used-1] = x_digits[0..x_used-1]*x_digits[0..x_used-1].
  // Return r_used = 2*x_used.
  static int _sqrDigits(Uint32List x_digits, int x_used, Uint32List r_digits) {
    var r_used = 2 * x_used;
    assert(r_digits.length >= r_used);
    // Since r_used is even, no need for a leading zero for 64-bit processing.
    var i = r_used;
    while (--i >= 0) {
      r_digits[i] = 0;
    }
    i = 0;
    while (i < x_used - 1) {
      i += _sqrAdd(x_digits, i, r_digits, x_used);
    }
    // The last step is already done if digit pairs were processed above.
    if (i < x_used) {
      _mulAdd(x_digits, i, x_digits, i, r_digits, 2*i, 1);
    }
    return r_used;
  }

  // Indices of the arguments of _estQuotientDigit.
  // For 64-bit processing by intrinsics on 64-bit platforms, the top digit pair
  // of divisor y is provided in the args array, and a 64-bit estimated quotient
  // is returned. However, on 32-bit platforms, the low 32-bit digit is ignored
  // and only one 32-bit digit is returned as the estimated quotient.
  static const int _YT_LO = 0;  // Low digit of top digit pair of y, for 64-bit.
  static const int _YT = 1;  // Top digit of divisor y.
  static const int _QD = 2;  // Estimated quotient.
  static const int _QD_HI = 3;  // High digit of estimated quotient, for 64-bit.

  // Operation:
  //   Estimate args[_QD] = digits[i-1..i] ~/ args[_YT]
  //   return 1
  // Note: Intrinsics on 64-bit platforms process a digit pair (i always odd):
  //   Estimate args[_QD.._QD_HI] = digits[i-3..i] ~/ args[_YT_LO.._YT]
  //   return 2
  static int _estQuotientDigit(Uint32List args, Uint32List digits, int i) {
    // Verify that digit pairs are accessible for 64-bit processing.
    assert(digits.length >= 4);
    if (digits[i] == args[_YT]) {
      args[_QD] = _DIGIT_MASK;
    } else {
      // Chop off one bit, since a Mint cannot hold 2 DIGITs.
      var qd = ((digits[i] << (_DIGIT_BITS - 1)) | (digits[i - 1] >> 1))
          ~/ (args[_YT] >> 1);
      if (qd > _DIGIT_MASK) {
        args[_QD] = _DIGIT_MASK;
      } else {
        args[_QD] = qd;
      }
    }
    return 1;
  }

  // Return trunc(this / a), a != 0.
  _Bigint _div(_Bigint a) {
    return _divRem(a, true);
  }

  // Return this - a * trunc(this / a), a != 0.
  _Bigint _rem(_Bigint a) {
    return _divRem(a, false);
  }

  // Return trunc(this / a), a != 0, if div == true.
  // Return this - a * trunc(this / a), a != 0, if div == false.
  _Bigint _divRem(_Bigint a, bool div) {
    assert(a._used > 0);
    if (_used < a._used) {
      return div ? _ZERO : this;
    }
    var nsh = _DIGIT_BITS - _nbits(a._digits[a._used - 1]);
    // For 64-bit processing, make sure y has an even number of digits.
    if (a._used.isOdd) {
      nsh += _DIGIT_BITS;
    }
    var y;  // Normalized positive divisor.
    var r;  // Concatenated positive quotient and normalized positive remainder.
    if (nsh > 0) {
      y = a._lShift(nsh)._abs();
      r = _lShift(nsh)._abs();
    }
    else {
      y = a._abs();
      r = _abs();
    }
    var y_used = y._used;
    var y_digits = y._digits;
    Uint32List args = new Uint32List(4);
    args[_YT_LO] = y_digits[y_used - 2];
    args[_YT] = y_digits[y_used - 1];
    var r_used = r._used;
    // For 64-bit processing, make sure y_used, i, and j are even.
    assert(y_used.isEven);
    var i = r_used + (r_used & 1);
    var j = i - y_used;
    var t = y._dlShift(j);
    if (r._compare(t) >= 0) {
      assert(i == r_used);
      r = r._or(_ONE._dlShift(r_used++))._sub(t);
      assert(r._used == r_used && (i + 1) == r_used);
    }
    // Negate y so we can later use _mulAdd instead of non-existent _mulSub.
    y = _ONE._dlShift(y_used)._sub(y);
    if (y._used < y_used) {
      y_digits = _cloneDigits(y._digits, 0, y._used, y_used);
    } else {
      y_digits = y._digits;
    }
    // y_digits is read-only and has y_used digits (possibly including several
    // leading zeros) plus a leading zero for 64-bit processing.
    var r_digits = _cloneDigits(r._digits, 0, r._used, i + 1);
    // r_digits is modified during iteration.
    // r_digits[0..y_used-1] is the current remainder.
    // r_digits[y_used..r_used-1] is the current quotient.
    --i;
    while (j > 0) {
      var d0 = _estQuotientDigit(args, r_digits, i);
      j -= d0;
      var d1 = _mulAdd(args, _QD, y_digits, 0, r_digits, j, y_used);
      // _estQuotientDigit and _mulAdd must agree on the number of digits to
      // process.
      assert(d0 == d1);
      if (d0 == 1) {
        if (r_digits[i] < args[_QD]) {
          var t = y._dlShift(j);
          var t_digits = t._digits;
          var t_used = t._used;
          _absSub(r_digits, r_used, t_digits, t_used, r_digits);
          while (r_digits[i] < --args[_QD]) {
            _absSub(r_digits, r_used, t_digits, t_used, r_digits);
          }
        }
      } else {
        assert(d0 == 2);
        assert(r_digits[i] <= args[_QD_HI]);
        if ((r_digits[i] < args[_QD_HI]) || (r_digits[i-1] < args[_QD])) {
          var t = y._dlShift(j);
          var t_digits = t._digits;
          var t_used = t._used;
          _absSub(r_digits, r_used, t_digits, t_used, r_digits);
          if (args[_QD] == 0) {
            --args[_QD_HI];
          }
          --args[_QD];
          assert(r_digits[i] <= args[_QD_HI]);
          while ((r_digits[i] < args[_QD_HI]) || (r_digits[i-1] < args[_QD])) {
            _absSub(r_digits, r_used, t_digits, t_used, r_digits);
            if (args[_QD] == 0) {
              --args[_QD_HI];
            }
            --args[_QD];
            assert(r_digits[i] <= args[_QD_HI]);
          }
        }
      }
      i -= d0;
    }
    if (div) {
      // Return quotient, i.e. r_digits[y_used..r_used-1] with proper sign.
      r_digits = _cloneDigits(r_digits, y_used, r_used, r_used - y_used);
      r = new _Bigint(false, r_used - y_used, r_digits);
      if (_neg != a._neg && r._used > 0) {
        r = r._negate();
      }
      return r;
    }
    // Return remainder, i.e. denormalized r_digits[0..y_used-1] with
    // proper sign.
    r_digits = _cloneDigits(r_digits, 0, y_used, y_used);
    r = new _Bigint(false, y_used, r_digits);
    if (nsh > 0) {
      r = r._rShift(nsh);  // Denormalize remainder.
    }
    if (_neg && r._used > 0) {
      r = r._negate();
    }
    return r;
  }

  // Customized version of _rem() minimizing allocations for use in reduction.
  // Input:
  //   x_digits[0..x_used-1]: positive dividend.
  //   y_digits[0..y_used-1]: normalized positive divisor.
  //   ny_digits[0..y_used-1]: negated y_digits.
  //   nsh: normalization shift amount.
  //   yt_qd: top y digit(s) and place holder for estimated quotient digit(s).
  //   t_digits: temp array of 2*y_used digits.
  //   r_digits: result digits array large enough to temporarily hold
  //             concatenated quotient and normalized remainder.
  // Output:
  //   r_digits[0..r_used-1]: positive remainder.
  // Returns r_used.
  static int _remDigits(Uint32List x_digits, int x_used,
                        Uint32List y_digits, int y_used, Uint32List ny_digits,
                        int nsh,
                        Uint32List yt_qd,
                        Uint32List t_digits,
                        Uint32List r_digits) {
    // Initialize r_digits to normalized positive dividend.
    var r_used = _lShiftDigits(x_digits, x_used, nsh, r_digits);
    // For 64-bit processing, make sure y_used, i, and j are even.
    assert(y_used.isEven);
    var i = r_used + (r_used & 1);
    var j = i - y_used;
    var t_used = _dlShiftDigits(y_digits, y_used, j, t_digits);
    // Explicit first division step in case normalized dividend is larger or
    // equal to shifted normalized divisor.
    if (_compareDigits(r_digits, r_used, t_digits, t_used) >= 0) {
      assert(i == r_used);
      r_digits[r_used++] = 1;  // Quotient = 1.
      r_digits[r_used] = 0;  // Leading zero.
      // Subtract divisor from remainder.
      _absSub(r_digits, r_used, t_digits, t_used, r_digits);
    }
    // Negated y_digits passed in ny_digits allow the use of _mulAdd instead of
    // unimplemented _mulSub.
    // ny_digits is read-only and has y_used digits (possibly including several
    // leading zeros) plus a leading zero for 64-bit processing.
    // r_digits is modified during iteration.
    // r_digits[0..y_used-1] is the current remainder.
    // r_digits[y_used..r_used-1] is the current quotient.
    --i;
    while (j > 0) {
      var d0 = _estQuotientDigit(yt_qd, r_digits, i);
      j -= d0;
      var d1 = _mulAdd(yt_qd, _QD, ny_digits, 0, r_digits, j, y_used);
      // _estQuotientDigit and _mulAdd must agree on the number of digits to
      // process.
      assert(d0 == d1);
      if (d0 == 1) {
        if (r_digits[i] < yt_qd[_QD]) {
          var t_used = _dlShiftDigits(ny_digits, y_used, j, t_digits);
          _absSub(r_digits, r_used, t_digits, t_used, r_digits);
          while (r_digits[i] < --yt_qd[_QD]) {
            _absSub(r_digits, r_used, t_digits, t_used, r_digits);
          }
        }
      } else {
        assert(d0 == 2);
        assert(r_digits[i] <= yt_qd[_QD_HI]);
        if ((r_digits[i] < yt_qd[_QD_HI]) || (r_digits[i-1] < yt_qd[_QD])) {
          var t_used = _dlShiftDigits(ny_digits, y_used, j, t_digits);
          _absSub(r_digits, r_used, t_digits, t_used, r_digits);
          if (yt_qd[_QD] == 0) {
            --yt_qd[_QD_HI];
          }
          --yt_qd[_QD];
          assert(r_digits[i] <= yt_qd[_QD_HI]);
          while ((r_digits[i] < yt_qd[_QD_HI]) ||
                 (r_digits[i-1] < yt_qd[_QD])) {
            _absSub(r_digits, r_used, t_digits, t_used, r_digits);
            if (yt_qd[_QD] == 0) {
              --yt_qd[_QD_HI];
            }
            --yt_qd[_QD];
            assert(r_digits[i] <= yt_qd[_QD_HI]);
          }
        }
      }
      i -= d0;
    }
    // Return remainder, i.e. denormalized r_digits[0..y_used-1].
    r_used = y_used;
    if (nsh > 0) {
      // Denormalize remainder.
      r_used = _rShiftDigits(r_digits, r_used, nsh, r_digits);
    }
    return r_used;
  }

  int get _identityHashCode {
    return this;
  }
  int operator ~() {
    return _not()._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 new RangeError(this);
    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];
    }
    return other._toBigint()._rShift(shift)._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 new RangeError(this);
    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];
    }
    return other._toBigint()._lShift(shift)._toValidInt();
  }

  // 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._toBigintOrDouble()._addFromInteger(this);
  }
  num operator -(num other) {
    return other._toBigintOrDouble()._subFromInteger(this);
  }
  num operator *(num other) {
    return other._toBigintOrDouble()._mulFromInteger(this);
  }
  num operator ~/(num other) {
    if ((other is int) && (other == 0)) {
      throw const IntegerDivisionByZeroException();
    }
    return other._toBigintOrDouble()._truncDivFromInteger(this);
  }
  num operator %(num other) {
    if ((other is int) && (other == 0)) {
      throw const IntegerDivisionByZeroException();
    }
    return other._toBigintOrDouble()._moduloFromInteger(this);
  }
  int operator &(int other) {
    return other._toBigintOrDouble()._bitAndFromInteger(this);
  }
  int operator |(int other) {
    return other._toBigintOrDouble()._bitOrFromInteger(this);
  }
  int operator ^(int other) {
    return other._toBigintOrDouble()._bitXorFromInteger(this);
  }
  int operator >>(int other) {
    return other._toBigintOrDouble()._shrFromInt(this);
  }
  int operator <<(int other) {
    return other._toBigintOrDouble()._shlFromInt(this);
  }
  // End of operator shortcuts.

  int operator -() {
    return _negate()._toValidInt();
  }

  int get sign {
    return (_used == 0) ? 0 : _neg ? -1 : 1;
  }

  bool get isEven => _used == 0 || (_digits[0] & 1) == 0;
  bool get isNegative => _neg;

  String _toPow2String(int radix) {
    if (_used == 0) return "0";
    assert(radix & (radix - 1) == 0);
    final bitsPerChar = radix.bitLength - 1;
    final firstcx = _neg ? 1 : 0;  // Index of first char in str after the sign.
    final lastdx = _used - 1;  // Index of last digit in bigint.
    final bitLength = lastdx*_DIGIT_BITS + _nbits(_digits[lastdx]);
    // Index of char in str. Initialize with str length.
    var cx = firstcx + (bitLength + bitsPerChar - 1) ~/ bitsPerChar;
    _OneByteString str = _OneByteString._allocate(cx);
    str._setAt(0, 0x2d);  // '-'. Is overwritten if not negative.
    final mask = radix - 1;
    var dx = 0;  // Digit index in bigint.
    var bx = 0;  // Bit index in bigint digit.
    do {
      var ch;
      if (bx > (_DIGIT_BITS - bitsPerChar)) {
        ch = _digits[dx++] >> bx;
        bx += bitsPerChar - _DIGIT_BITS;
        if (dx <= lastdx) {
          ch |= (_digits[dx] & ((1 << bx) - 1)) << (bitsPerChar - bx);
        }
      } else {
        ch = (_digits[dx] >> bx) & mask;
        bx += bitsPerChar;
        if (bx >= _DIGIT_BITS) {
          bx -= _DIGIT_BITS;
          dx++;
        }
      }
      str._setAt(--cx, _IntegerImplementation._digits.codeUnitAt(ch));
    } while (cx > firstcx);
    return str;
  }

  _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) {
    return other._toBigint()._and(this)._toValidInt();
  }
  int _bitOrFromInteger(int other) {
    return other._toBigint()._or(this)._toValidInt();
  }
  int _bitXorFromInteger(int other) {
    return other._toBigint()._xor(this)._toValidInt();
  }
  int _addFromInteger(int other) {
    return other._toBigint()._add(this)._toValidInt();
  }
  int _subFromInteger(int other) {
    return other._toBigint()._sub(this)._toValidInt();
  }
  int _mulFromInteger(int other) {
    return other._toBigint()._mul(this)._toValidInt();
  }
  int _truncDivFromInteger(int other) {
    return other._toBigint()._div(this)._toValidInt();
  }
  int _moduloFromInteger(int other) {
    _Bigint result = other._toBigint()._rem(this);
    if (result._neg) {
      if (_neg) {
        result = result._sub(this);
      } else {
        result = result._add(this);
      }
    }
    return result._toValidInt();
  }
  int _remainderFromInteger(int other) {
    return other._toBigint()._rem(this)._toValidInt();
  }
  bool _greaterThanFromInteger(int other) {
    return other._toBigint()._compare(this) > 0;
  }
  bool _equalToInteger(int other) {
    return other._toBigint()._compare(this) == 0;
  }

  // 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 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 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;
      while (--i >= 0) {
        r2_used = z._sqr(r_digits, r_used, r2_digits);
        if ((e & (1 << i)) != 0) {
          r_used = z._mul(r2_digits, r2_used, g_digits, g_used, r_digits);
        } else {
          var t_digits = r_digits;
          var t_used = r_used;
          r_digits = r2_digits;
          r_used = r2_used;
          r2_digits = t_digits;
          r2_used = t_used;
        }
      }
      return z._revert(r_digits, r_used)._toValidInt();
    }
    e = e._toBigint();
    var k;
    if (e_bitlen < 18) k = 1;
    else if (e_bitlen < 48) k = 3;
    else if (e_bitlen < 144) k = 4;
    else if (e_bitlen < 768) k = 5;
    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_used = z._sqr(g_digits[1], g_used[1], g2_digits);
      while (n <= km) {
        g_digits[n] = new Uint32List(m_used2p2);
        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_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_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) {
          r2_used = z._sqr(r_digits, r_used, r2_digits);
          r_used = z._sqr(r2_digits, r2_used, r_digits);
          n -= 2;
        }
        if (n > 0) {
          r2_used = z._sqr(r_digits, r_used, r2_digits);
        } else {
          var t_digits = r_digits;
          var t_used = r_used;
          r_digits = r2_digits;
          r_used = r2_used;
          r2_digits = t_digits;
          r2_used = t_used;
        }
        r_used = z._mul(r2_digits, r2_used, g_digits[w], g_used[w], r_digits);
      }
      while (j >= 0 && (e_digits[j] & (1 << i)) == 0) {
        r2_used = z._sqr(r_digits, r_used, r2_digits);
        var t_digits = r_digits;
        var t_used = r_used;
        r_digits = r2_digits;
        r_used = r2_used;
        r2_digits = t_digits;
        r2_used = t_used;
        if (--i < 0) {
          i = _DIGIT_BITS - 1;
          --j;
        }
      }
    }
    assert(!is1);
    return z._revert(r_digits, r_used)._toValidInt();
  }
}

// Interface for modular reduction.
class _Reduction {
  // Return the number of digits used by r_digits.
  int _convert(_Bigint x, Uint32List r_digits);
  int _mul(Uint32List x_digits, int x_used,
           Uint32List y_digits, int y_used, Uint32List r_digits);
  int _sqr(Uint32List x_digits, int x_used, Uint32List r_digits);

  // Return x reverted to _Bigint.
  _Bigint _revert(Uint32List x_digits, int x_used);
}

// Montgomery reduction on _Bigint.
class _Montgomery implements _Reduction {
  _Bigint _m;  // Modulus.
  int _mused2p2;
  Uint32List _args;
  int _digits_per_step;  // Number of digits processed in one step. 1 or 2.
  static const int _X = 0;  // Index of x.
  static const int _X_HI = 1;  // Index of high 32-bits of x (64-bit only).
  static const int _RHO = 2;  // Index of rho.
  static const int _RHO_HI = 3;  // Index of high 32-bits of rho (64-bit only).
  static const int _MU = 4;  // Index of mu.
  static const int _MU_HI = 5;  // Index of high 32-bits of mu (64-bit only).

  _Montgomery(m) {
    _m = m._toBigint();
    _mused2p2 = 2*_m._used + 2;
    _args = new Uint32List(6);
    // Determine if we can process digit pairs by calling an intrinsic.
    _digits_per_step = _mulMod(_args, _args, 0);
    _args[_X] = _m._digits[0];
    if (_digits_per_step == 1) {
      _invDigit(_args);
    } else {
      assert(_digits_per_step == 2);
      _args[_X_HI] = _m._digits[1];
      _invDigitPair(_args);
    }
  }

  // Calculates -1/x % _DIGIT_BASE, x is 32-bit digit.
  //         xy == 1 (mod m)
  //         xy =  1+km
  //   xy(2-xy) = (1+km)(1-km)
  // x(y(2-xy)) = 1-k^2 m^2
  // x(y(2-xy)) == 1 (mod m^2)
  // if y is 1/x mod m, then y(2-xy) is 1/x mod m^2
  // Should reduce x and y(2-xy) by m^2 at each step to keep size bounded.
  //
  // Operation:
  //   args[_RHO] = 1/args[_X] mod _DIGIT_BASE.
  static void _invDigit(Uint32List args) {
    var x = args[_X];
    var y = x & 3;    // y == 1/x mod 2^2
    y = (y*(2 - (x & 0xf)*y)) & 0xf;  // y == 1/x mod 2^4
    y = (y*(2 - (x & 0xff)*y)) & 0xff;  // y == 1/x mod 2^8
    y = (y*(2 - (((x & 0xffff)*y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16
    // Last step - calculate inverse mod _DIGIT_BASE directly;
    // Assumes 16 < _DIGIT_BITS <= 32 and assumes ability to handle 48-bit ints.
    y = (y*(2 - x*y % _Bigint._DIGIT_BASE)) % _Bigint._DIGIT_BASE;
    // y == 1/x mod _DIGIT_BASE
    y = -y;  // We really want the negative inverse.
    args[_RHO] = y & _Bigint._DIGIT_MASK;
  }

  // Calculates -1/x % _DIGIT_BASE^2, x is a pair of 32-bit digits.
  // Operation:
  //   args[_RHO.._RHO_HI] = 1/args[_X.._X_HI] mod _DIGIT_BASE^2.
  static void _invDigitPair(Uint32List args) {
    var xl = args[_X];  // Lower 32-bit digit of x.
    var y = xl & 3;    // y == 1/x mod 2^2
    y = (y*(2 - (xl & 0xf)*y)) & 0xf;  // y == 1/x mod 2^4
    y = (y*(2 - (xl & 0xff)*y)) & 0xff;  // y == 1/x mod 2^8
    y = (y*(2 - (((xl & 0xffff)*y) & 0xffff))) & 0xffff;  // y == 1/x mod 2^16
    y = (y*(2 - ((xl*y) & 0xffffffff))) & 0xffffffff;  // y == 1/x mod 2^32
    var x = (args[_X_HI] << _Bigint._DIGIT_BITS) | xl;
    y = (y*(2 - ((x*y) & 0xffffffffffffffff))) & 0xffffffffffffffff;
    // y == 1/x mod _DIGIT_BASE^2
    y = -y;  // We really want the negative inverse.
    args[_RHO] = y & _Bigint._DIGIT_MASK;
    args[_RHO_HI] = (y >> _Bigint._DIGIT_BITS) & _Bigint._DIGIT_MASK;
  }

  // Operation:
  //   args[_MU] = args[_RHO]*digits[i] mod _DIGIT_BASE.
  //   return 1.
  // Note: Intrinsics on 64-bit platforms process digit pairs at even indices:
  //   args[_MU.._MU_HI] = args[_RHO.._RHO_HI]*digits[i..i+1] mod _DIGIT_BASE^2.
  //   return 2.
  static int _mulMod(Uint32List args, Uint32List digits, int i) {
    // Verify that digit pairs are accessible for 64-bit processing.
    assert(digits.length > (i | 1));
    const int MU_MASK = (1 << (_Bigint._DIGIT_BITS - _Bigint._DIGIT2_BITS)) - 1;
    var rhol = args[_RHO] & _Bigint._DIGIT2_MASK;
    var rhoh = args[_RHO] >> _Bigint._DIGIT2_BITS;
    var dh = digits[i] >> _Bigint._DIGIT2_BITS;
    var dl = digits[i] & _Bigint._DIGIT2_MASK;
    args[_MU] =
        (dl*rhol + (((dl*rhoh + dh*rhol) & MU_MASK) << _Bigint._DIGIT2_BITS))
        & _Bigint._DIGIT_MASK;
    return 1;
  }

  // r = x*R mod _m.
  // Return r_used.
  int _convert(_Bigint x, Uint32List r_digits) {
    // Montgomery reduction only works if abs(x) < _m.
    assert(x._abs() < _m);
    var r = x._abs()._dlShift(_m._used)._rem(_m);
    if (x._neg && !r._neg && r._used > 0) {
      r = _m._sub(r);
    }
    var used = r._used;
    var digits = r._digits;
    var i = used + (used & 1);
    while (--i >= 0) {
      r_digits[i] = digits[i];
    }
    return used;
  }

  _Bigint _revert(Uint32List x_digits, int x_used) {
    var r_digits = new Uint32List(_mused2p2);
    var i = x_used + (x_used & 1);
    while (--i >= 0) {
      r_digits[i] = x_digits[i];
    }
    var r_used = _reduce(r_digits, x_used);
    return new _Bigint(false, r_used, r_digits);
  }

  // x = x/R mod _m.
  // Return x_used.
  int _reduce(Uint32List x_digits, int x_used) {
    while (x_used < _mused2p2) {  // Pad x so _mulAdd has enough room later.
      x_digits[x_used++] = 0;
    }
    var m_used = _m._used;
    var m_digits = _m._digits;
    var i = 0;
    while (i < m_used) {
      var d = _mulMod(_args, x_digits, i);
      assert(d == _digits_per_step);
      d = _Bigint._mulAdd(_args, _MU, m_digits, 0, x_digits, i, m_used);
      assert(d == _digits_per_step);
      i += d;
    }
    // Clamp x.
    while (x_used > 0 && x_digits[x_used - 1] == 0) {
      --x_used;
    }
    // Shift right by m_used digits or, if processing pairs, by i (even) digits.
    x_used = _Bigint._drShiftDigits(x_digits, x_used, i, x_digits);
    if (_Bigint._compareDigits(x_digits, x_used, m_digits, m_used) >= 0) {
      _Bigint._absSub(x_digits, x_used, m_digits, m_used, x_digits);
    }
    // Clamp x.
    while (x_used > 0 && x_digits[x_used - 1] == 0) {
      --x_used;
    }
    return x_used;
  }

  int _sqr(Uint32List x_digits, int x_used, Uint32List r_digits) {
    var r_used = _Bigint._sqrDigits(x_digits, x_used, r_digits);
    return _reduce(r_digits, r_used);
  }

  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);
  }
}

// Modular reduction using "classic" algorithm.
class _Classic implements _Reduction {
  _Bigint _m;  // Modulus.
  _Bigint _norm_m;  // Normalized _m.
  Uint32List _neg_norm_m_digits;  // Negated _norm_m digits.
  int _m_nsh;  // Normalization shift amount.
  Uint32List _mt_qd;  // Top _norm_m digit(s) and place holder for
                      // estimated quotient digit(s).
  Uint32List _t_digits;  // Temporary digits used during reduction.

  _Classic(int m) {
    _m = m._toBigint();
    // Preprocess arguments to _remDigits.
    var nsh = _Bigint._DIGIT_BITS - _Bigint._nbits(_m._digits[_m._used - 1]);
    // For 64-bit processing, make sure _norm_m_digits has an even number of
    // digits.
    if (_m._used.isOdd) {
      nsh += _Bigint._DIGIT_BITS;
    }
    _m_nsh = nsh;
    _norm_m = _m._lShift(nsh);
    var nm_used = _norm_m._used;
    assert(nm_used.isEven);
    _mt_qd = new Uint32List(4);
    _mt_qd[_Bigint._YT_LO] = _norm_m._digits[nm_used - 2];
    _mt_qd[_Bigint._YT] = _norm_m._digits[nm_used - 1];
    // Negate _norm_m so we can use _mulAdd instead of unimplemented _mulSub.
    var neg_norm_m = _Bigint._ONE._dlShift(nm_used)._sub(_norm_m);
    if (neg_norm_m._used < nm_used) {
      _neg_norm_m_digits =
          _Bigint._cloneDigits(neg_norm_m._digits, 0, nm_used, nm_used);
    } else {
      _neg_norm_m_digits = neg_norm_m._digits;
    }
    // _neg_norm_m_digits is read-only and has nm_used digits (possibly
    // including several leading zeros) plus a leading zero for 64-bit
    // processing.
    _t_digits = new Uint32List(2*nm_used + 2);
  }

  int _convert(_Bigint x, Uint32List r_digits) {
    var digits;
    var used;
    if (x._neg || x._compare(_m) >= 0) {
      var r = x._rem(_m);
      if (x._neg && !r._neg && r._used > 0) {
        r = _m._sub(r);
      }
      assert(!r._neg);
      used = r._used;
      digits = r._digits;
    } else {
      used = x._used;
      digits = x._digits;
    }
    var i = used + (used & 1);  // Copy leading zero if any.
    while (--i >= 0) {
      r_digits[i] = digits[i];
    }
    return used;
  }

  _Bigint _revert(Uint32List x_digits, int x_used) {
    return new _Bigint(false, x_used, x_digits);
  }

  int _reduce(Uint32List x_digits, int x_used) {
    // The function _remDigits(...) is optimized for reduction and equivalent to
    // calling _convert(_revert(x_digits, x_used)._rem(_m), x_digits);
    return _Bigint._remDigits(x_digits, x_used,
                              _norm_m._digits, _norm_m._used,
                              _neg_norm_m_digits,
                              _m_nsh,
                              _mt_qd,
                              _t_digits,
                              x_digits);
  }

  int _sqr(Uint32List x_digits, int x_used, Uint32List r_digits) {
    var r_used = _Bigint._sqrDigits(x_digits, x_used, r_digits);
    return _reduce(r_digits, r_used);
  }

  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);
  }
}