// Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

/*
 * Copyright (c) 2003-2005  Tom Wu
 * Copyright (c) 2012 Adam Singer (adam@solvr.io)
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
 * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
 *
 * IN NO EVENT SHALL TOM WU BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
 * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER
 * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF
 * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT
 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 * In addition, the following condition applies:
 *
 * All redistributions must retain an intact copy of this copyright notice
 * and disclaimer.
 */

class _Bigint extends _IntegerImplementation implements int {
  // Bits per digit.
  static const int DIGIT_BITS = 32;
  static const int DIGIT_BASE = 1 << DIGIT_BITS;
  static const int DIGIT_MASK = (1 << DIGIT_BITS) - 1;

  // Bits per half digit.
  static const int DIGIT2_BITS = DIGIT_BITS >> 1;
  static const int DIGIT2_BASE = 1 << DIGIT2_BITS;
  static const int DIGIT2_MASK = (1 << DIGIT2_BITS) - 1;

  // Allocate extra digits so the bigint can be reused.
  static const int EXTRA_DIGITS = 4;

  // Floating-point unit integer precision.
  static const int FP_BITS = 52;
  static const int FP_BASE = 1 << FP_BITS;
  static const int FP_D1 = FP_BITS - DIGIT_BITS;
  static const int FP_D2 = 2 * DIGIT_BITS - FP_BITS;

  // Min and max of non bigint values.
  static const int MIN_INT64 = (-1) << 63;
  static const int MAX_INT64 = 0x7fffffffffffffff;

  // Bigint constant values.
  // Note: Not declared as final in order to satisfy optimizer, which expects
  // constants to be in canonical form (Smi).
  static _Bigint ZERO = new _Bigint();
  static _Bigint ONE = new _Bigint()._setInt(1);

  // Digit conversion table for parsing.
  static final Map<int, int> DIGIT_TABLE = _createDigitTable();

  // Internal data structure.
  bool get _neg native "Bigint_getNeg";
  void set _neg(bool neg) native "Bigint_setNeg";
  int get _used native "Bigint_getUsed";
  void set _used(int used) native "Bigint_setUsed";
  Uint32List get _digits native "Bigint_getDigits";
  void set _digits(Uint32List digits) native "Bigint_setDigits";

  // Factory returning an instance initialized to value 0.
  factory _Bigint() native "Bigint_allocate";

  // Factory returning an instance initialized to an integer value.
  factory _Bigint._fromInt(int i) {
    return new _Bigint()._setInt(i);
  }

  // Factory returning an instance initialized to a hex string.
  factory _Bigint._fromHex(String s) {
    return new _Bigint()._setHex(s);
  }

  // Factory returning an instance initialized to a double value given by its
  // components.
  factory _Bigint._fromDouble(int sign, int significand, int exponent) {
    return new _Bigint()._setDouble(sign, significand, exponent);
  }

  // Initialize instance to the given value no larger than a Mint.
  _Bigint _setInt(int i) {
    assert(i is! _Bigint);
    _ensureLength(2);
    _used = 2;
    var l, h;
    if (i < 0) {
      _neg = true;
      if (i == MIN_INT64) {
        l = 0;
        h = 0x80000000;
      } else {
        l = (-i) & DIGIT_MASK;
        h = (-i) >> DIGIT_BITS;
      }
    } else {
      _neg = false;
      l = i & DIGIT_MASK;
      h = i >> DIGIT_BITS;
    }
    _digits[0] = l;
    _digits[1] = h;
    _clamp();
    return this;
  }

  // Initialize instance to the given hex string.
  // TODO(regis): Copy Bigint::NewFromHexCString, fewer digit accesses.
  // TODO(regis): Unused.
  _Bigint _setHex(String s) {
    const int HEX_BITS = 4;
    const int HEX_DIGITS_PER_DIGIT = 8;
    var hexDigitIndex = s.length;
    _ensureLength((hexDigitIndex + HEX_DIGITS_PER_DIGIT - 1) ~/ HEX_DIGITS_PER_DIGIT);
    var bitIndex = 0;
    while (--hexDigitIndex >= 0) {
      var digit = DIGIT_TABLE[s.codeUnitAt(hexDigitIndex)];
      if (digit = null) {
        if (s[hexDigitIndex] == "-") _neg = true;
        continue;  // Ignore invalid digits.
      }
      _neg = false;  // Ignore "-" if not at index 0.
      if (bitIndex == 0) {
        _digits[_used++] = digit;
        // TODO(regis): What if too many bad digits were ignored and
        // _used becomes larger than _digits.length? error or reallocate?
      } else {
        _digits[_used - 1] |= digit << bitIndex;
      }
      bitIndex = (bitIndex + HEX_BITS) % DIGIT_BITS;
    }
    _clamp();
    return this;
  }

  // Initialize instance to the given double value.
  _Bigint _setDouble(int sign, int significand, int exponent) {
    assert(significand >= 0);
    assert(exponent >= 0);
    _setInt(significand);
    _neg = sign < 0;
    if (exponent > 0) {
      _lShiftTo(exponent, this);
    }
    return this;
  }

  // Create digit conversion table for parsing.
  static Map<int, int> _createDigitTable() {
    Map table = new HashMap();
    int digit, value;
    digit = "0".codeUnitAt(0);
    for(value = 0; value <= 9; ++value) table[digit++] = value;
    digit = "a".codeUnitAt(0);
    for(value = 10; value < 36; ++value) table[digit++] = value;
    digit = "A".codeUnitAt(0);
    for(value = 10; value < 36; ++value) table[digit++] = value;
    return table;
  }

  // Return most compact integer (i.e. possibly Smi or Mint).
  // TODO(regis): Intrinsify.
  int _toValidInt() {
    assert(DIGIT_BITS == 32);  // Otherwise this code needs to be revised.
    if (_used == 0) return 0;
    if (_used == 1) return _neg ? -_digits[0] : _digits[0];
    if (_used > 2) return this;
    if (_neg) {
      if (_digits[1] > 0x80000000) return this;
      if (_digits[1] == 0x80000000) {
        if (_digits[0] > 0) return this;
        return MIN_INT64;
      }
      return -((_digits[1] << DIGIT_BITS) | _digits[0]);
    }
    if (_digits[1] >= 0x80000000) return this;
    return (_digits[1] << DIGIT_BITS) | _digits[0];
  }

  // Conversion from int to bigint.
  _Bigint _toBigint() => this;

  // Make sure at least 'length' _digits are allocated.
  // Copy existing _digits if reallocation is necessary.
  // TODO(regis): Check that we are not preserving _digits unnecessarily.
  void _ensureLength(int length) {
    if (length > 0 && (_digits == null || length > _digits.length)) {
      var new_digits = new Uint32List(length + EXTRA_DIGITS);
      if (_digits != null) {
        for (var i = _used; --i >= 0; ) {
          new_digits[i] = _digits[i];
        }
      }
      _digits = new_digits;
    }
  }

  // Clamp off excess high _digits.
  void _clamp() {
    while (_used > 0 && _digits[_used - 1] == 0) {
      --_used;
    }
    assert(_used > 0 || !_neg);
  }

  // Copy this to r.
  void _copyTo(_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, 0 <= x < DIGIT_BASE (i.e. 32-bit multiplier).
  // w[j..j+n-1]: bigint accumulator.
  // Returns carry out.
  // w[j..j+n-1] += this[i..i+n-1] * x.
  // Returns carry out.
  int _am(int i, int x, _Bigint w, int j, int n) {
    if (x == 0) {
      // No-op if x is 0.
      return 0;
    }
    int c = 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;
  }

  // Accumulate multiply with carry.
  // this[i..i+n-1]: bigint multiplicand.
  // x: digit multiplier, 0 <= x < 2*DIGIT_BASE  (i.e. 33-bit 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.
  int _amc(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) {
      r._digits[i + _used] = _am(0, a._digits[i], r, i, _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, 1);
      var d = r._digits[i + _used];
      d += _amc(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, 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._amc(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();
  }

  // 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 -() {
    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;
  }

  // Return -1/this % DIGIT_BASE, useful for Montgomery reduction.
  //
  //         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.
  int _invDigit() {
    if (_used == 0) return 0;
    var x = _digits[0];
    if ((x & 1) == 0) return 0;
    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 % DIGIT_BASE)) % DIGIT_BASE;    // y == 1/x mod DIGIT_BASE
    // We really want the negative inverse, and - DIGIT_BASE < y < DIGIT_BASE.
    return (y > 0) ? DIGIT_BASE - y : -y;
  }

  // TODO(regis): Make this method private once the plumbing to invoke it from
  // dart:math is in place.
  // Return pow(this, e) % m.
  int modPow(int e, int m) {
    // TODO(regis): Where/how do we handle values of e smaller than 256?
    // TODO(regis): Where/how do we handle even values of m?
    assert(e >= 256 && !m.isEven());
    if (e is! _Bigint) {
      _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();
    }
    var i = e.bitLength;
    var k;
    var r = new _Bigint()._setInt(1);
    if (i <= 0) return r;
    // TODO(regis): Are these values of k really optimal for our implementation?
    else if (i < 18) k = 1;
    else if (i < 48) k = 3;
    else if (i < 144) k = 4;
    else if (i < 768) k = 5;
    else k = 6;
    _Reduction z = new _Montgomery(m);
    var n = 3;
    var k1 = k - 1;
    var km = (1 << k) - 1;
    List g = new List(km + 1);
    g[1] = z._convert(this);
    if (k > 1) {
      var g2 = new _Bigint();
      z._sqrTo(g[1], g2);
      while (n <= km) {
        g[n] = new _Bigint();
        z._mulTo(g2, g[n - 2], g[n]);
        n += 2;
      }
    }
    var j = e._used - 1;
    var w;
    var is1 = true;
    var r2 = new _Bigint();
    var t;
    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.
        g[w]._copyTo(r);
        is1 = false;
      }
      else {
        while (n > 1) {
          z._sqrTo(r, r2);
          z._sqrTo(r2, r);
          n -= 2;
        }
        if (n > 0) {
          z._sqrTo(r, r2);
        } else {
          t = r;
          r = r2;
          r2 = t;
        }
        z._mulTo(r2,g[w], r);
      }

      while (j >= 0 && (e._digits[j] & (1 << i)) == 0) {
        z._sqrTo(r, r2);
        t = r;
        r = r2;
        r2 = t;
        if (--i < 0) {
          i = DIGIT_BITS - 1;
          --j;
        }
      }
    }
    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, _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);
  }
}