Google Git
Sign in
dart / sdk.git / refs/tags/1.9.0-dev.8.0 / . / runtime / lib / bigint.dart
blob: 7519ac1162044d14ddb14a40c2ec95e935b7eb28 [file] [log] [blame]
// 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) {
assert(y_used > 0 && x_used >= y_used);
// 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;
e = e._toBigint();
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;
if ((e is! _Bigint) || m.isEven) {
_Reduction z = (e_bitlen < 8 || m.isEven) ?
new _Classic(m) : new _Montgomery(m);
// TODO(regis): Should we use Barrett reduction for an even modulus?
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();
}
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) {
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);
}
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);
}
}