| // Copyright (c) 2017, 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. |
| |
| // part of dart.core; |
| |
| // 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. |
| */ |
| |
| @patch |
| class BigInt implements Comparable<BigInt> { |
| @patch |
| static BigInt get zero => _BigIntImpl.zero; |
| @patch |
| static BigInt get one => _BigIntImpl.one; |
| @patch |
| static BigInt get two => _BigIntImpl.two; |
| |
| @patch |
| static BigInt parse(String source, {int radix}) => |
| _BigIntImpl.parse(source, radix: radix); |
| |
| @patch |
| factory BigInt.from(num value) => new _BigIntImpl.from(value); |
| } |
| |
| int _max(int a, int b) => a > b ? a : b; |
| int _min(int a, int b) => a < b ? a : b; |
| |
| /** |
| * An implementation for the arbitrarily large integer. |
| * |
| * The integer number is represented by a sign, an array of 16-bit unsigned |
| * integers in little endian format, and a number of used digits in that array. |
| */ |
| class _BigIntImpl implements BigInt { |
| // Bits per digit. |
| static const int _digitBits = 16; |
| static const int _digitBase = 1 << _digitBits; |
| static const int _digitMask = (1 << _digitBits) - 1; |
| |
| static final _BigIntImpl zero = new _BigIntImpl._fromInt(0); |
| static final _BigIntImpl one = new _BigIntImpl._fromInt(1); |
| static final _BigIntImpl two = new _BigIntImpl._fromInt(2); |
| |
| static final _BigIntImpl _minusOne = -one; |
| static final _BigIntImpl _bigInt10000 = new _BigIntImpl._fromInt(10000); |
| |
| // Result cache for last _divRem call. |
| // Result cache for last _divRem call. |
| static Uint16List _lastDividendDigits; |
| static int _lastDividendUsed; |
| static Uint16List _lastDivisorDigits; |
| static int _lastDivisorUsed; |
| static Uint16List _lastQuoRemDigits; |
| static int _lastQuoRemUsed; |
| static int _lastRemUsed; |
| static int _lastRem_nsh; |
| |
| /// Whether this bigint is negative. |
| final bool _isNegative; |
| |
| /// The unsigned digits of this bigint. |
| /// |
| /// The least significant digit is in slot 0. |
| /// The list may have more digits than needed. That is, `_digits.length` may |
| /// be strictly greater than `_used`. |
| final Uint16List _digits; |
| |
| /// The number of used entries in [_digits]. |
| /// |
| /// To avoid reallocating [Uint16List]s, lists that are too big are not |
| /// replaced. |
| final int _used; |
| |
| /** |
| * Parses [source] as a, possibly signed, integer literal and returns its |
| * value. |
| * |
| * The [source] must be a non-empty sequence of base-[radix] digits, |
| * optionally prefixed with a minus or plus sign ('-' or '+'). |
| * |
| * The [radix] must be in the range 2..36. The digits used are |
| * first the decimal digits 0..9, and then the letters 'a'..'z' with |
| * values 10 through 35. Also accepts upper-case letters with the same |
| * values as the lower-case ones. |
| * |
| * If no [radix] is given then it defaults to 10. In this case, the [source] |
| * digits may also start with `0x`, in which case the number is interpreted |
| * as a hexadecimal literal, which effectively means that the `0x` is ignored |
| * and the radix is instead set to 16. |
| * |
| * For any int `n` and radix `r`, it is guaranteed that |
| * `n == int.parse(n.toRadixString(r), radix: r)`. |
| * |
| * Throws a [FormatException] if the [source] is not a valid integer literal, |
| * optionally prefixed by a sign. |
| */ |
| static _BigIntImpl parse(String source, {int radix}) { |
| var result = _tryParse(source, radix: radix); |
| if (result == null) { |
| throw new FormatException("Could not parse BigInt", source); |
| } |
| return result; |
| } |
| |
| /// Parses a decimal bigint literal. |
| /// |
| /// The [source] must not contain leading or trailing whitespace. |
| static _BigIntImpl _parseDecimal(String source, bool isNegative) { |
| const _0 = 48; |
| |
| int part = 0; |
| _BigIntImpl result = zero; |
| // Read in the source 4 digits at a time. |
| // The first part may have a few leading virtual '0's to make the remaining |
| // parts all have exactly 4 digits. |
| int digitInPartCount = 4 - source.length.remainder(4); |
| if (digitInPartCount == 4) digitInPartCount = 0; |
| for (int i = 0; i < source.length; i++) { |
| part = part * 10 + source.codeUnitAt(i) - _0; |
| if (++digitInPartCount == 4) { |
| result = result * _bigInt10000 + new _BigIntImpl._fromInt(part); |
| part = 0; |
| digitInPartCount = 0; |
| } |
| } |
| if (isNegative) return -result; |
| return result; |
| } |
| |
| /// Returns the value of a given source digit. |
| /// |
| /// Source digits between "0" and "9" (inclusive) return their decimal value. |
| /// |
| /// Source digits between "a" and "z", or "A" and "Z" (inclusive) return |
| /// 10 + their position in the ASCII alphabet. |
| /// |
| /// The incoming [codeUnit] must be an ASCII code-unit. |
| static int _codeUnitToRadixValue(int codeUnit) { |
| // We know that the characters must be ASCII as otherwise the |
| // regexp wouldn't have matched. Lowercasing by doing `| 0x20` is thus |
| // guaranteed to be a safe operation, since it preserves digits |
| // and lower-cases ASCII letters. |
| const int _0 = 48; |
| const int _9 = 57; |
| const int _a = 97; |
| if (_0 <= codeUnit && codeUnit <= _9) return codeUnit - _0; |
| codeUnit |= 0x20; |
| var result = codeUnit - _a + 10; |
| return result; |
| } |
| |
| /// Parses the given [source] string, starting at [startPos], as a hex |
| /// literal. |
| /// |
| /// If [isNegative] is true, negates the result before returning it. |
| /// |
| /// The [source] (substring) must be a valid hex literal. |
| static _BigIntImpl _parseHex(String source, int startPos, bool isNegative) { |
| int hexDigitsPerChunk = _digitBits ~/ 4; |
| int sourceLength = source.length - startPos; |
| int chunkCount = (sourceLength / hexDigitsPerChunk).ceil(); |
| var digits = new Uint16List(chunkCount); |
| |
| int lastDigitLength = sourceLength - (chunkCount - 1) * hexDigitsPerChunk; |
| int digitIndex = digits.length - 1; |
| int i = startPos; |
| int chunk = 0; |
| for (int j = 0; j < lastDigitLength; j++) { |
| var digitValue = _codeUnitToRadixValue(source.codeUnitAt(i++)); |
| if (digitValue >= 16) return null; |
| chunk = chunk * 16 + digitValue; |
| } |
| digits[digitIndex--] = chunk; |
| |
| while (i < source.length) { |
| chunk = 0; |
| for (int j = 0; j < 4; j++) { |
| var digitValue = _codeUnitToRadixValue(source.codeUnitAt(i++)); |
| if (digitValue >= 16) return null; |
| chunk = chunk * 16 + digitValue; |
| } |
| digits[digitIndex--] = chunk; |
| } |
| if (digits.length == 1 && digits[0] == 0) return zero; |
| return new _BigIntImpl._(isNegative, digits.length, digits); |
| } |
| |
| /// Parses the given [source] as a [radix] literal. |
| /// |
| /// The [source] will be checked for invalid characters. If it is invalid, |
| /// this function returns `null`. |
| static _BigIntImpl _parseRadix(String source, int radix, bool isNegative) { |
| var result = zero; |
| var base = new _BigIntImpl._fromInt(radix); |
| for (int i = 0; i < source.length; i++) { |
| var digitValue = _codeUnitToRadixValue(source.codeUnitAt(i)); |
| if (digitValue >= radix) return null; |
| result = result * base + new _BigIntImpl._fromInt(digitValue); |
| } |
| if (isNegative) return -result; |
| return result; |
| } |
| |
| /// Tries to parse the given [source] as a [radix] literal. |
| /// |
| /// Returns the parsed big integer, or `null` if it failed. |
| /// |
| /// If the [radix] is `null` accepts decimal literals or `0x` hex literals. |
| static _BigIntImpl _tryParse(String source, {int radix}) { |
| if (source == "") return null; |
| |
| var re = new RegExp(r'^\s*([+-]?)((0x[a-f0-9]+)|(\d+)|([a-z0-9]+))\s*$', |
| caseSensitive: false); |
| var match = re.firstMatch(source); |
| int signIndex = 1; |
| int hexIndex = 3; |
| int decimalIndex = 4; |
| int nonDecimalHexIndex = 5; |
| if (match == null) return null; |
| |
| bool isNegative = match[signIndex] == "-"; |
| |
| String decimalMatch = match[decimalIndex]; |
| String hexMatch = match[hexIndex]; |
| String nonDecimalMatch = match[nonDecimalHexIndex]; |
| |
| if (radix == null) { |
| if (decimalMatch != null) { |
| // Cannot fail because we know that the digits are all decimal. |
| return _parseDecimal(decimalMatch, isNegative); |
| } |
| if (hexMatch != null) { |
| // Cannot fail because we know that the digits are all hex. |
| return _parseHex(hexMatch, 2, isNegative); |
| } |
| return null; |
| } |
| |
| if (radix is! int) { |
| throw new ArgumentError.value(radix, 'radix', 'is not an integer'); |
| } |
| if (radix < 2 || radix > 36) { |
| throw new RangeError.range(radix, 2, 36, 'radix'); |
| } |
| if (radix == 10 && decimalMatch != null) { |
| return _parseDecimal(decimalMatch, isNegative); |
| } |
| if (radix == 16 && (decimalMatch != null || nonDecimalMatch != null)) { |
| return _parseHex(decimalMatch ?? nonDecimalMatch, 0, isNegative); |
| } |
| |
| return _parseRadix( |
| decimalMatch ?? nonDecimalMatch ?? hexMatch, radix, isNegative); |
| } |
| |
| /// Finds the amount significant digits in the provided [digits] array. |
| static int _normalize(int used, Uint16List digits) { |
| while (used > 0 && digits[used - 1] == 0) used--; |
| return used; |
| } |
| |
| /// Factory returning an instance initialized with the given field values. |
| /// If the [digits] array contains leading 0s, the [used] value is adjusted |
| /// accordingly. The [digits] array is not modified. |
| _BigIntImpl._(bool isNegative, int used, Uint16List digits) |
| : this._normalized(isNegative, _normalize(used, digits), digits); |
| |
| _BigIntImpl._normalized(bool isNegative, this._used, this._digits) |
| : _isNegative = _used == 0 ? false : isNegative; |
| |
| /// Whether this big integer is zero. |
| bool get _isZero => _used == 0; |
| |
| /// Allocates an array of the given [length] and copies the [digits] in the |
| /// range [from] to [to-1], starting at index 0, followed by leading zero |
| /// digits. |
| static Uint16List _cloneDigits( |
| Uint16List digits, int from, int to, int length) { |
| var resultDigits = new Uint16List(length); |
| var n = to - from; |
| for (var i = 0; i < n; i++) { |
| resultDigits[i] = digits[from + i]; |
| } |
| return resultDigits; |
| } |
| |
| /// Allocates a big integer from the provided [value] number. |
| factory _BigIntImpl.from(num value) { |
| if (value == 0) return zero; |
| if (value == 1) return one; |
| if (value == 2) return two; |
| |
| // Given this order dart2js will use the `_fromInt` for smaller value and |
| // then use the bit-manipulating `_fromDouble` for all other values. |
| if (value.abs() < 0x100000000) |
| return new _BigIntImpl._fromInt(value.toInt()); |
| if (value is double) return new _BigIntImpl._fromDouble(value); |
| return new _BigIntImpl._fromInt(value); |
| } |
| |
| factory _BigIntImpl._fromInt(int value) { |
| bool isNegative = value < 0; |
| if (isNegative) { |
| // Handle the min 64-bit value differently, since its negation is not |
| // positive. |
| // TODO(floitsch): we should use min.minValue or 0x8000000000000000 here. |
| const int minInt64 = -9223372036854775807 - 1; |
| if (value == minInt64) { |
| var digits = new Uint16List(4); |
| digits[3] = 0x8000; |
| return new _BigIntImpl._(true, digits.length, digits); |
| } |
| value = -value; |
| } |
| assert(_digitBits == 16); |
| if (value < _digitBase) { |
| var digits = new Uint16List(1); |
| digits[0] = value; |
| return new _BigIntImpl._(isNegative, digits.length, digits); |
| } |
| if (value <= 0xFFFFFFFF) { |
| var digits = new Uint16List(2); |
| digits[0] = value & _digitMask; |
| digits[1] = value >> _digitBits; |
| return new _BigIntImpl._(isNegative, digits.length, digits); |
| } |
| |
| var bits = value.bitLength; |
| var digits = new Uint16List((bits - 1) ~/ _digitBits + 1); |
| var i = 0; |
| while (value != 0) { |
| digits[i++] = value & _digitMask; |
| value = value ~/ _digitBase; |
| } |
| return new _BigIntImpl._(isNegative, digits.length, digits); |
| } |
| |
| /// An 8-byte Uint8List we can reuse for [_fromDouble] to avoid generating |
| /// garbage. |
| static final Uint8List _bitsForFromDouble = new Uint8List(8); |
| |
| factory _BigIntImpl._fromDouble(double value) { |
| const int exponentBias = 1075; |
| |
| if (value.isNaN || value.isInfinite) { |
| throw new ArgumentError("Value must be finite: $value"); |
| } |
| bool isNegative = value < 0; |
| if (isNegative) value = -value; |
| |
| value = value.floorToDouble(); |
| if (value == 0) return zero; |
| |
| var bits = _bitsForFromDouble; |
| for (int i = 0; i < 8; i++) { |
| bits[i] = 0; |
| } |
| bits.buffer.asByteData().setFloat64(0, value, Endian.little); |
| // The exponent is in bits 53..63. |
| var biasedExponent = (bits[7] << 4) + (bits[6] >> 4); |
| var exponent = biasedExponent - exponentBias; |
| |
| assert(_digitBits == 16); |
| // The significant bits are in 0 .. 52. |
| var unshiftedDigits = new Uint16List(4); |
| unshiftedDigits[0] = (bits[1] << 8) + bits[0]; |
| unshiftedDigits[1] = (bits[3] << 8) + bits[2]; |
| unshiftedDigits[2] = (bits[5] << 8) + bits[4]; |
| // Don't forget to add the hidden bit. |
| unshiftedDigits[3] = 0x10 | (bits[6] & 0xF); |
| |
| var unshiftedBig = new _BigIntImpl._normalized(false, 4, unshiftedDigits); |
| _BigIntImpl absResult; |
| if (exponent < 0) { |
| absResult = unshiftedBig >> -exponent; |
| } else if (exponent > 0) { |
| absResult = unshiftedBig << exponent; |
| } |
| if (isNegative) return -absResult; |
| return absResult; |
| } |
| |
| /** |
| * Return the negative value of this integer. |
| * |
| * The result of negating an integer always has the opposite sign, except |
| * for zero, which is its own negation. |
| */ |
| _BigIntImpl operator -() { |
| if (_used == 0) return this; |
| return new _BigIntImpl._(!_isNegative, _used, _digits); |
| } |
| |
| /** |
| * Returns the absolute value of this integer. |
| * |
| * For any integer `x`, the result is the same as `x < 0 ? -x : x`. |
| */ |
| _BigIntImpl abs() => _isNegative ? -this : this; |
| |
| /// Returns this << n *_DIGIT_BITS. |
| _BigIntImpl _dlShift(int n) { |
| final used = _used; |
| if (used == 0) { |
| return zero; |
| } |
| final resultUsed = used + n; |
| final digits = _digits; |
| final resultDigits = new Uint16List(resultUsed); |
| for (int i = used - 1; i >= 0; i--) { |
| resultDigits[i + n] = digits[i]; |
| } |
| return new _BigIntImpl._(_isNegative, resultUsed, resultDigits); |
| } |
| |
| /// Same as [_dlShift] but works on the decomposed big integers. |
| /// |
| /// Returns `resultUsed`. |
| /// |
| /// `resultDigits[0..resultUsed-1] = xDigits[0..xUsed-1] << n*_DIGIT_BITS`. |
| static int _dlShiftDigits( |
| Uint16List xDigits, int xUsed, int n, Uint16List resultDigits) { |
| if (xUsed == 0) { |
| return 0; |
| } |
| if (n == 0 && identical(resultDigits, xDigits)) { |
| return xUsed; |
| } |
| final resultUsed = xUsed + n; |
| for (int i = xUsed - 1; i >= 0; i--) { |
| resultDigits[i + n] = xDigits[i]; |
| } |
| for (int i = n - 1; i >= 0; i--) { |
| resultDigits[i] = 0; |
| } |
| return resultUsed; |
| } |
| |
| /// Returns `this >> n*_DIGIT_BITS`. |
| _BigIntImpl _drShift(int n) { |
| final used = _used; |
| if (used == 0) { |
| return zero; |
| } |
| final resultUsed = used - n; |
| if (resultUsed <= 0) { |
| return _isNegative ? _minusOne : zero; |
| } |
| final digits = _digits; |
| final resultDigits = new Uint16List(resultUsed); |
| for (var i = n; i < used; i++) { |
| resultDigits[i - n] = digits[i]; |
| } |
| final result = new _BigIntImpl._(_isNegative, resultUsed, resultDigits); |
| if (_isNegative) { |
| // Round down if any bit was shifted out. |
| for (var i = 0; i < n; i++) { |
| if (digits[i] != 0) { |
| return result - one; |
| } |
| } |
| } |
| return result; |
| } |
| |
| /// Shifts the digits of [xDigits] into the right place in [resultDigits]. |
| /// |
| /// `resultDigits[ds..xUsed+ds] = xDigits[0..xUsed-1] << (n % _DIGIT_BITS)` |
| /// where `ds = ceil(n / _DIGIT_BITS)` |
| /// |
| /// Does *not* clear digits below ds. |
| static void _lsh( |
| Uint16List xDigits, int xUsed, int n, Uint16List resultDigits) { |
| final digitShift = n ~/ _digitBits; |
| final bitShift = n % _digitBits; |
| final carryBitShift = _digitBits - bitShift; |
| final bitMask = (1 << carryBitShift) - 1; |
| var carry = 0; |
| for (int i = xUsed - 1; i >= 0; i--) { |
| final digit = xDigits[i]; |
| resultDigits[i + digitShift + 1] = (digit >> carryBitShift) | carry; |
| carry = (digit & bitMask) << bitShift; |
| } |
| resultDigits[digitShift] = carry; |
| } |
| |
| /** |
| * Shift the bits of this integer to the left by [shiftAmount]. |
| * |
| * Shifting to the left makes the number larger, effectively multiplying |
| * the number by `pow(2, shiftIndex)`. |
| * |
| * There is no limit on the size of the result. It may be relevant to |
| * limit intermediate values by using the "and" operator with a suitable |
| * mask. |
| * |
| * It is an error if [shiftAmount] is negative. |
| */ |
| _BigIntImpl operator <<(int shiftAmount) { |
| if (shiftAmount < 0) { |
| throw new ArgumentError("shift-amount must be posititve $shiftAmount"); |
| } |
| final digitShift = shiftAmount ~/ _digitBits; |
| final bitShift = shiftAmount % _digitBits; |
| if (bitShift == 0) { |
| return _dlShift(digitShift); |
| } |
| var resultUsed = _used + digitShift + 1; |
| var resultDigits = new Uint16List(resultUsed); |
| _lsh(_digits, _used, shiftAmount, resultDigits); |
| return new _BigIntImpl._(_isNegative, resultUsed, resultDigits); |
| } |
| |
| // resultDigits[0..resultUsed-1] = xDigits[0..xUsed-1] << n. |
| // Returns resultUsed. |
| static int _lShiftDigits( |
| Uint16List xDigits, int xUsed, int n, Uint16List resultDigits) { |
| final digitsShift = n ~/ _digitBits; |
| final bitShift = n % _digitBits; |
| if (bitShift == 0) { |
| return _dlShiftDigits(xDigits, xUsed, digitsShift, resultDigits); |
| } |
| var resultUsed = xUsed + digitsShift + 1; |
| _lsh(xDigits, xUsed, n, resultDigits); |
| var i = digitsShift; |
| while (--i >= 0) { |
| resultDigits[i] = 0; |
| } |
| if (resultDigits[resultUsed - 1] == 0) { |
| resultUsed--; // Clamp result. |
| } |
| return resultUsed; |
| } |
| |
| // resultDigits[0..resultUsed-1] = xDigits[0..xUsed-1] >> n. |
| static void _rsh( |
| Uint16List xDigits, int xUsed, int n, Uint16List resultDigits) { |
| final digitsShift = n ~/ _digitBits; |
| final bitShift = n % _digitBits; |
| final carryBitShift = _digitBits - bitShift; |
| final bitMask = (1 << bitShift) - 1; |
| var carry = xDigits[digitsShift] >> bitShift; |
| final last = xUsed - digitsShift - 1; |
| for (var i = 0; i < last; i++) { |
| final digit = xDigits[i + digitsShift + 1]; |
| resultDigits[i] = ((digit & bitMask) << carryBitShift) | carry; |
| carry = digit >> bitShift; |
| } |
| resultDigits[last] = carry; |
| } |
| |
| /** |
| * Shift the bits of this integer to the right by [shiftAmount]. |
| * |
| * Shifting to the right makes the number smaller and drops the least |
| * significant bits, effectively doing an integer division by |
| *`pow(2, shiftIndex)`. |
| * |
| * It is an error if [shiftAmount] is negative. |
| */ |
| _BigIntImpl operator >>(int shiftAmount) { |
| if (shiftAmount < 0) { |
| throw new ArgumentError("shift-amount must be posititve $shiftAmount"); |
| } |
| final digitShift = shiftAmount ~/ _digitBits; |
| final bitShift = shiftAmount % _digitBits; |
| if (bitShift == 0) { |
| return _drShift(digitShift); |
| } |
| final used = _used; |
| final resultUsed = used - digitShift; |
| if (resultUsed <= 0) { |
| return _isNegative ? _minusOne : zero; |
| } |
| final digits = _digits; |
| final resultDigits = new Uint16List(resultUsed); |
| _rsh(digits, used, shiftAmount, resultDigits); |
| final result = new _BigIntImpl._(_isNegative, resultUsed, resultDigits); |
| if (_isNegative) { |
| // Round down if any bit was shifted out. |
| if ((digits[digitShift] & ((1 << bitShift) - 1)) != 0) { |
| return result - one; |
| } |
| for (var i = 0; i < digitShift; i++) { |
| if (digits[i] != 0) { |
| return result - one; |
| } |
| } |
| } |
| return result; |
| } |
| |
| /// Compares this to [other] taking the absolute value of both operands. |
| /// |
| /// Returns 0 if abs(this) == abs(other); a positive number if |
| /// abs(this) > abs(other); and a negative number if abs(this) < abs(other). |
| int _absCompare(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| return _compareDigits(_digits, _used, other._digits, other._used); |
| } |
| |
| /** |
| * Compares this to `other`. |
| * |
| * Returns a negative number if `this` is less than `other`, zero if they are |
| * equal, and a positive number if `this` is greater than `other`. |
| */ |
| int compareTo(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| if (_isNegative == other._isNegative) { |
| var result = _absCompare(other); |
| // Use 0 - result to avoid negative zero in JavaScript. |
| return _isNegative ? 0 - result : result; |
| } |
| return _isNegative ? -1 : 1; |
| } |
| |
| /// Compares `digits[0..used-1]` with `otherDigits[0..otherUsed-1]`. |
| /// |
| /// Returns 0 if equal; a positive number if larger; |
| /// and a negative number if smaller. |
| static int _compareDigits( |
| Uint16List digits, int used, Uint16List otherDigits, int otherUsed) { |
| var result = used - otherUsed; |
| if (result == 0) { |
| for (int i = used - 1; i >= 0; i--) { |
| result = digits[i] - otherDigits[i]; |
| if (result != 0) return result; |
| } |
| } |
| return result; |
| } |
| |
| // resultDigits[0..used] = digits[0..used-1] + otherDigits[0..otherUsed-1]. |
| // used >= otherUsed > 0. |
| static void _absAdd(Uint16List digits, int used, Uint16List otherDigits, |
| int otherUsed, Uint16List resultDigits) { |
| assert(used >= otherUsed && otherUsed > 0); |
| var carry = 0; |
| for (var i = 0; i < otherUsed; i++) { |
| carry += digits[i] + otherDigits[i]; |
| resultDigits[i] = carry & _digitMask; |
| carry >>= _digitBits; |
| } |
| for (var i = otherUsed; i < used; i++) { |
| carry += digits[i]; |
| resultDigits[i] = carry & _digitMask; |
| carry >>= _digitBits; |
| } |
| resultDigits[used] = carry; |
| } |
| |
| // resultDigits[0..used-1] = digits[0..used-1] - otherDigits[0..otherUsed-1]. |
| // used >= otherUsed > 0. |
| static void _absSub(Uint16List digits, int used, Uint16List otherDigits, |
| int otherUsed, Uint16List resultDigits) { |
| assert(used >= otherUsed && otherUsed > 0); |
| |
| var carry = 0; |
| for (var i = 0; i < otherUsed; i++) { |
| carry += digits[i] - otherDigits[i]; |
| resultDigits[i] = carry & _digitMask; |
| // Dart2js only supports unsigned shifts. |
| // Since the carry can only be -1 or 0 use this hack. |
| carry = 0 - ((carry >> _digitBits) & 1); |
| } |
| for (var i = otherUsed; i < used; i++) { |
| carry += digits[i]; |
| resultDigits[i] = carry & _digitMask; |
| // Dart2js only supports unsigned shifts. |
| // Since the carry can only be -1 or 0 use this hack. |
| carry = 0 - ((carry >> _digitBits) & 1); |
| } |
| } |
| |
| /// Returns `abs(this) + abs(other)` with sign set according to [isNegative]. |
| _BigIntImpl _absAddSetSign(_BigIntImpl other, bool isNegative) { |
| var used = _used; |
| var otherUsed = other._used; |
| if (used < otherUsed) { |
| return other._absAddSetSign(this, isNegative); |
| } |
| if (used == 0) { |
| assert(!isNegative); |
| return zero; |
| } |
| if (otherUsed == 0) { |
| return _isNegative == isNegative ? this : -this; |
| } |
| var resultUsed = used + 1; |
| var resultDigits = new Uint16List(resultUsed); |
| _absAdd(_digits, used, other._digits, otherUsed, resultDigits); |
| return new _BigIntImpl._(isNegative, resultUsed, resultDigits); |
| } |
| |
| /// Returns `abs(this) - abs(other)` with sign set according to [isNegative]. |
| /// |
| /// Requirement: `abs(this) >= abs(other)`. |
| _BigIntImpl _absSubSetSign(_BigIntImpl other, bool isNegative) { |
| assert(_absCompare(other) >= 0); |
| var used = _used; |
| if (used == 0) { |
| assert(!isNegative); |
| return zero; |
| } |
| var otherUsed = other._used; |
| if (otherUsed == 0) { |
| return _isNegative == isNegative ? this : -this; |
| } |
| var resultDigits = new Uint16List(used); |
| _absSub(_digits, used, other._digits, otherUsed, resultDigits); |
| return new _BigIntImpl._(isNegative, used, resultDigits); |
| } |
| |
| /// Returns `abs(this) & abs(other)` with sign set according to [isNegative]. |
| _BigIntImpl _absAndSetSign(_BigIntImpl other, bool isNegative) { |
| var resultUsed = _min(_used, other._used); |
| var digits = _digits; |
| var otherDigits = other._digits; |
| var resultDigits = new Uint16List(resultUsed); |
| for (var i = 0; i < resultUsed; i++) { |
| resultDigits[i] = digits[i] & otherDigits[i]; |
| } |
| return new _BigIntImpl._(isNegative, resultUsed, resultDigits); |
| } |
| |
| /// Returns `abs(this) &~ abs(other)` with sign set according to [isNegative]. |
| _BigIntImpl _absAndNotSetSign(_BigIntImpl other, bool isNegative) { |
| var resultUsed = _used; |
| var digits = _digits; |
| var otherDigits = other._digits; |
| var resultDigits = new Uint16List(resultUsed); |
| var m = _min(resultUsed, other._used); |
| for (var i = 0; i < m; i++) { |
| resultDigits[i] = digits[i] & ~otherDigits[i]; |
| } |
| for (var i = m; i < resultUsed; i++) { |
| resultDigits[i] = digits[i]; |
| } |
| return new _BigIntImpl._(isNegative, resultUsed, resultDigits); |
| } |
| |
| /// Returns `abs(this) | abs(other)` with sign set according to [isNegative]. |
| _BigIntImpl _absOrSetSign(_BigIntImpl other, bool isNegative) { |
| var used = _used; |
| var otherUsed = other._used; |
| var resultUsed = _max(used, otherUsed); |
| var digits = _digits; |
| var otherDigits = other._digits; |
| var resultDigits = new Uint16List(resultUsed); |
| var l, m; |
| if (used < otherUsed) { |
| l = other; |
| m = used; |
| } else { |
| l = this; |
| m = otherUsed; |
| } |
| for (var i = 0; i < m; i++) { |
| resultDigits[i] = digits[i] | otherDigits[i]; |
| } |
| var lDigits = l._digits; |
| for (var i = m; i < resultUsed; i++) { |
| resultDigits[i] = lDigits[i]; |
| } |
| return new _BigIntImpl._(isNegative, resultUsed, resultDigits); |
| } |
| |
| /// Returns `abs(this) ^ abs(other)` with sign set according to [isNegative]. |
| _BigIntImpl _absXorSetSign(_BigIntImpl other, bool isNegative) { |
| var used = _used; |
| var otherUsed = other._used; |
| var resultUsed = _max(used, otherUsed); |
| var digits = _digits; |
| var otherDigits = other._digits; |
| var resultDigits = new Uint16List(resultUsed); |
| var l, m; |
| if (used < otherUsed) { |
| l = other; |
| m = used; |
| } else { |
| l = this; |
| m = otherUsed; |
| } |
| for (var i = 0; i < m; i++) { |
| resultDigits[i] = digits[i] ^ otherDigits[i]; |
| } |
| var lDigits = l._digits; |
| for (var i = m; i < resultUsed; i++) { |
| resultDigits[i] = lDigits[i]; |
| } |
| return new _BigIntImpl._(isNegative, resultUsed, resultDigits); |
| } |
| |
| /** |
| * Bit-wise and operator. |
| * |
| * Treating both `this` and [other] as sufficiently large two's component |
| * integers, the result is a number with only the bits set that are set in |
| * both `this` and [other] |
| * |
| * Of both operands are negative, the result is negative, otherwise |
| * the result is non-negative. |
| */ |
| _BigIntImpl operator &(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| if (_isNegative == other._isNegative) { |
| if (_isNegative) { |
| // (-this) & (-other) == ~(this-1) & ~(other-1) |
| // == ~((this-1) | (other-1)) |
| // == -(((this-1) | (other-1)) + 1) |
| _BigIntImpl this1 = _absSubSetSign(one, true); |
| _BigIntImpl other1 = other._absSubSetSign(one, true); |
| // Result cannot be zero if this and other are negative. |
| return this1._absOrSetSign(other1, true)._absAddSetSign(one, true); |
| } |
| return _absAndSetSign(other, false); |
| } |
| // _isNegative != other._isNegative |
| var p, n; |
| if (_isNegative) { |
| p = other; |
| n = this; |
| } else { |
| // & is symmetric. |
| p = this; |
| n = other; |
| } |
| // p & (-n) == p & ~(n-1) == p &~ (n-1) |
| var n1 = n._absSubSetSign(one, false); |
| return p._absAndNotSetSign(n1, false); |
| } |
| |
| /** |
| * Bit-wise or operator. |
| * |
| * Treating both `this` and [other] as sufficiently large two's component |
| * integers, the result is a number with the bits set that are set in either |
| * of `this` and [other] |
| * |
| * If both operands are non-negative, the result is non-negative, |
| * otherwise the result us negative. |
| */ |
| _BigIntImpl operator |(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| if (_isNegative == other._isNegative) { |
| if (_isNegative) { |
| // (-this) | (-other) == ~(this-1) | ~(other-1) |
| // == ~((this-1) & (other-1)) |
| // == -(((this-1) & (other-1)) + 1) |
| var this1 = _absSubSetSign(one, true); |
| var other1 = other._absSubSetSign(one, true); |
| // Result cannot be zero if this and a are negative. |
| return this1._absAndSetSign(other1, true)._absAddSetSign(one, true); |
| } |
| return _absOrSetSign(other, false); |
| } |
| // _neg != a._neg |
| var p, n; |
| if (_isNegative) { |
| p = other; |
| n = this; |
| } else { |
| // | is symmetric. |
| p = this; |
| n = other; |
| } |
| // p | (-n) == p | ~(n-1) == ~((n-1) &~ p) == -(~((n-1) &~ p) + 1) |
| var 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); |
| } |
| |
| /** |
| * Bit-wise exclusive-or operator. |
| * |
| * Treating both `this` and [other] as sufficiently large two's component |
| * integers, the result is a number with the bits set that are set in one, |
| * but not both, of `this` and [other] |
| * |
| * If the operands have the same sign, the result is non-negative, |
| * otherwise the result is negative. |
| */ |
| _BigIntImpl operator ^(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| if (_isNegative == other._isNegative) { |
| if (_isNegative) { |
| // (-this) ^ (-other) == ~(this-1) ^ ~(other-1) == (this-1) ^ (other-1) |
| var this1 = _absSubSetSign(one, true); |
| var other1 = other._absSubSetSign(one, true); |
| return this1._absXorSetSign(other1, false); |
| } |
| return _absXorSetSign(other, false); |
| } |
| // _isNegative != a._isNegative |
| var p, n; |
| if (_isNegative) { |
| p = other; |
| n = this; |
| } else { |
| // ^ is symmetric. |
| p = this; |
| n = other; |
| } |
| // p ^ (-n) == p ^ ~(n-1) == ~(p ^ (n-1)) == -((p ^ (n-1)) + 1) |
| var 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); |
| } |
| |
| /** |
| * The bit-wise negate operator. |
| * |
| * Treating `this` as a sufficiently large two's component integer, |
| * the result is a number with the opposite bits set. |
| * |
| * This maps any integer `x` to `-x - 1`. |
| */ |
| _BigIntImpl operator ~() { |
| if (_isNegative) { |
| // ~(-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); |
| } |
| |
| /// Addition operator. |
| _BigIntImpl operator +(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| var isNegative = _isNegative; |
| if (isNegative == other._isNegative) { |
| // this + other == this + other |
| // (-this) + (-other) == -(this + other) |
| return _absAddSetSign(other, isNegative); |
| } |
| // this + (-other) == this - other == -(this - other) |
| // (-this) + other == other - this == -(this - other) |
| if (_absCompare(other) >= 0) { |
| return _absSubSetSign(other, isNegative); |
| } |
| return other._absSubSetSign(this, !isNegative); |
| } |
| |
| /// Subtraction operator. |
| _BigIntImpl operator -(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| var isNegative = _isNegative; |
| if (isNegative != other._isNegative) { |
| // this - (-other) == this + other |
| // (-this) - other == -(this + other) |
| return _absAddSetSign(other, isNegative); |
| } |
| // this - other == this - a == -(this - other) |
| // (-this) - (-other) == other - this == -(this - other) |
| if (_absCompare(other) >= 0) { |
| return _absSubSetSign(other, isNegative); |
| } |
| return other._absSubSetSign(this, !isNegative); |
| } |
| |
| /// Multiplies [x] with [multiplicandDigits] and adds the result to |
| /// [accumulatorDigits]. |
| /// |
| /// The [multiplicandDigits] in the range [i] to [i]+[n]-1 are the |
| /// multiplicand digits. |
| /// |
| /// The [acculumatorDigits] in the range [j] to [j]+[n]-1 are the accumulator |
| /// digits. |
| /// |
| /// Adds the result of the multiplicand-digits * [x] to the accumulator. |
| /// |
| /// Concretely: `accumulatorDigits[j..j+n] += x * m_digits[i..i+n-1]`. |
| static void _mulAdd(int x, Uint16List multiplicandDigits, int i, |
| Uint16List accumulatorDigits, int j, int n) { |
| if (x == 0) { |
| // No-op if x is 0. |
| return; |
| } |
| int c = 0; |
| while (--n >= 0) { |
| int product = x * multiplicandDigits[i++]; |
| int combined = product + accumulatorDigits[j] + c; |
| accumulatorDigits[j++] = combined & _digitMask; |
| // Note that this works with 53 bits, as the division will not lose |
| // bits. |
| c = combined ~/ _digitBase; |
| } |
| while (c != 0) { |
| int l = accumulatorDigits[j] + c; |
| accumulatorDigits[j++] = l & _digitMask; |
| c = l ~/ _digitBase; |
| } |
| } |
| |
| /// Multiplication operator. |
| _BigIntImpl operator *(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| var used = _used; |
| var otherUsed = other._used; |
| if (used == 0 || otherUsed == 0) { |
| return zero; |
| } |
| var resultUsed = used + otherUsed; |
| var digits = _digits; |
| var otherDigits = other._digits; |
| var resultDigits = new Uint16List(resultUsed); |
| var i = 0; |
| while (i < otherUsed) { |
| _mulAdd(otherDigits[i], digits, 0, resultDigits, i, used); |
| i++; |
| } |
| return new _BigIntImpl._( |
| _isNegative != other._isNegative, resultUsed, resultDigits); |
| } |
| |
| // r_digits[0..rUsed-1] = xDigits[0..xUsed-1]*otherDigits[0..otherUsed-1]. |
| // Return resultUsed = xUsed + otherUsed. |
| static int _mulDigits(Uint16List xDigits, int xUsed, Uint16List otherDigits, |
| int otherUsed, Uint16List resultDigits) { |
| var resultUsed = xUsed + otherUsed; |
| var i = resultUsed; |
| assert(resultDigits.length >= i); |
| while (--i >= 0) { |
| resultDigits[i] = 0; |
| } |
| i = 0; |
| while (i < otherUsed) { |
| _mulAdd(otherDigits[i], xDigits, 0, resultDigits, i, xUsed); |
| i++; |
| } |
| return resultUsed; |
| } |
| |
| /// Returns an estimate of `digits[i-1..i] ~/ topDigitDivisor`. |
| static int _estimateQuotientDigit( |
| int topDigitDivisor, Uint16List digits, int i) { |
| if (digits[i] == topDigitDivisor) return _digitMask; |
| var quotientDigit = |
| (digits[i] << _digitBits | digits[i - 1]) ~/ topDigitDivisor; |
| if (quotientDigit > _digitMask) return _digitMask; |
| return quotientDigit; |
| } |
| |
| /// Returns `trunc(this / other)`, with `other != 0`. |
| _BigIntImpl _div(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| assert(other._used > 0); |
| if (_used < other._used) { |
| return zero; |
| } |
| _divRem(other); |
| // Return quotient, i.e. |
| // _lastQuoRem_digits[_lastRem_used.._lastQuoRem_used-1] with proper sign. |
| var lastQuo_used = _lastQuoRemUsed - _lastRemUsed; |
| var quo_digits = _cloneDigits( |
| _lastQuoRemDigits, _lastRemUsed, _lastQuoRemUsed, lastQuo_used); |
| var quo = new _BigIntImpl._(false, lastQuo_used, quo_digits); |
| if ((_isNegative != other._isNegative) && (quo._used > 0)) { |
| quo = -quo; |
| } |
| return quo; |
| } |
| |
| /// Returns `this - other * trunc(this / other)`, with `other != 0`. |
| _BigIntImpl _rem(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| assert(other._used > 0); |
| if (_used < other._used) { |
| return this; |
| } |
| _divRem(other); |
| // Return remainder, i.e. |
| // denormalized _lastQuoRem_digits[0.._lastRem_used-1] with proper sign. |
| var remDigits = |
| _cloneDigits(_lastQuoRemDigits, 0, _lastRemUsed, _lastRemUsed); |
| var rem = new _BigIntImpl._(false, _lastRemUsed, remDigits); |
| if (_lastRem_nsh > 0) { |
| rem = rem >> _lastRem_nsh; // Denormalize remainder. |
| } |
| if (_isNegative && (rem._used > 0)) { |
| rem = -rem; |
| } |
| return rem; |
| } |
| |
| /// Computes this ~/ other and this.remainder(other). |
| /// |
| /// Stores the result in [_lastQuoRemDigits], [_lastQuoRemUsed] and |
| /// [_lastRemUsed]. The [_lastQuoRemDigits] contains the digits of *both*, the |
| /// quotient and the remainder. |
| /// |
| /// Caches the input to avoid doing the work again when users write |
| /// `a ~/ b` followed by a `a % b`. |
| void _divRem(_BigIntImpl other) { |
| // Check if result is already cached. |
| if ((this._used == _lastDividendUsed) && |
| (other._used == _lastDivisorUsed) && |
| identical(this._digits, _lastDividendDigits) && |
| identical(other._digits, _lastDivisorDigits)) { |
| return; |
| } |
| assert(_used >= other._used); |
| |
| var nsh = _digitBits - other._digits[other._used - 1].bitLength; |
| // Concatenated positive quotient and normalized positive remainder. |
| // The resultDigits can have at most one more digit than the dividend. |
| Uint16List resultDigits; |
| int resultUsed; |
| // Normalized positive divisor. |
| // The normalized divisor has the most-significant bit of it's most |
| // significant digit set. |
| // This makes estimating the quotient easier. |
| Uint16List yDigits; |
| int yUsed; |
| if (nsh > 0) { |
| yDigits = new Uint16List(other._used + 5); |
| yUsed = _lShiftDigits(other._digits, other._used, nsh, yDigits); |
| resultDigits = new Uint16List(_used + 5); |
| resultUsed = _lShiftDigits(_digits, _used, nsh, resultDigits); |
| } else { |
| yDigits = other._digits; |
| yUsed = other._used; |
| resultDigits = _cloneDigits(_digits, 0, _used, _used + 2); |
| resultUsed = _used; |
| } |
| var topDigitDivisor = yDigits[yUsed - 1]; |
| var i = resultUsed; |
| var j = i - yUsed; |
| // tmpDigits is a temporary array of i (resultUsed) digits. |
| var tmpDigits = new Uint16List(i); |
| var tmpUsed = _dlShiftDigits(yDigits, yUsed, j, tmpDigits); |
| // Explicit first division step in case normalized dividend is larger or |
| // equal to shifted normalized divisor. |
| if (_compareDigits(resultDigits, resultUsed, tmpDigits, tmpUsed) >= 0) { |
| assert(i == resultUsed); |
| resultDigits[resultUsed++] = 1; // Quotient = 1. |
| // Subtract divisor from remainder. |
| _absSub(resultDigits, resultUsed, tmpDigits, tmpUsed, resultDigits); |
| } else { |
| // Account for possible carry in _mulAdd step. |
| resultDigits[resultUsed++] = 0; |
| } |
| |
| // Negate y so we can later use _mulAdd instead of non-existent _mulSub. |
| var nyDigits = new Uint16List(yUsed + 2); |
| nyDigits[yUsed] = 1; |
| _absSub(nyDigits, yUsed + 1, yDigits, yUsed, nyDigits); |
| // nyDigits is read-only and has yUsed digits (possibly including several |
| // leading zeros). |
| // resultDigits is modified during iteration. |
| // resultDigits[0..yUsed-1] is the current remainder. |
| // resultDigits[yUsed..resultUsed-1] is the current quotient. |
| --i; |
| |
| while (j > 0) { |
| var estimatedQuotientDigit = |
| _estimateQuotientDigit(topDigitDivisor, resultDigits, i); |
| j--; |
| _mulAdd(estimatedQuotientDigit, nyDigits, 0, resultDigits, j, yUsed); |
| if (resultDigits[i] < estimatedQuotientDigit) { |
| // Reusing the already existing tmpDigits array. |
| var tmpUsed = _dlShiftDigits(nyDigits, yUsed, j, tmpDigits); |
| _absSub(resultDigits, resultUsed, tmpDigits, tmpUsed, resultDigits); |
| while (resultDigits[i] < --estimatedQuotientDigit) { |
| _absSub(resultDigits, resultUsed, tmpDigits, tmpUsed, resultDigits); |
| } |
| } |
| i--; |
| } |
| // Cache result. |
| _lastDividendDigits = _digits; |
| _lastDividendUsed = _used; |
| _lastDivisorDigits = other._digits; |
| _lastDivisorUsed = other._used; |
| _lastQuoRemDigits = resultDigits; |
| _lastQuoRemUsed = resultUsed; |
| _lastRemUsed = yUsed; |
| _lastRem_nsh = nsh; |
| } |
| |
| int get hashCode { |
| // This is the [Jenkins hash function][1] but using masking to keep |
| // values in SMI range. |
| // |
| // [1]: http://en.wikipedia.org/wiki/Jenkins_hash_function |
| |
| int combine(int hash, int value) { |
| hash = 0x1fffffff & (hash + value); |
| hash = 0x1fffffff & (hash + ((0x0007ffff & hash) << 10)); |
| return hash ^ (hash >> 6); |
| } |
| |
| int finish(int hash) { |
| hash = 0x1fffffff & (hash + ((0x03ffffff & hash) << 3)); |
| hash = hash ^ (hash >> 11); |
| return 0x1fffffff & (hash + ((0x00003fff & hash) << 15)); |
| } |
| |
| if (_isZero) return 6707; // Just a random number. |
| var hash = _isNegative ? 83585 : 429689; // Also random. |
| for (int i = 0; i < _used; i++) { |
| hash = combine(hash, _digits[i]); |
| } |
| return finish(hash); |
| } |
| |
| /** |
| * Test whether this value is numerically equal to `other`. |
| * |
| * If [other] is a [_BigIntImpl] returns whether the two operands have the same |
| * value. |
| * |
| * Returns false if `other` is not a [_BigIntImpl]. |
| */ |
| bool operator ==(Object other) => |
| other is _BigIntImpl && compareTo(other) == 0; |
| |
| /** |
| * Returns the minimum number of bits required to store this big integer. |
| * |
| * The number of bits excludes the sign bit, which gives the natural length |
| * for non-negative (unsigned) values. Negative values are complemented to |
| * return the bit position of the first bit that differs from the sign bit. |
| * |
| * To find the number of bits needed to store the value as a signed value, |
| * add one, i.e. use `x.bitLength + 1`. |
| * |
| * ``` |
| * x.bitLength == (-x-1).bitLength |
| * |
| * new BigInt.from(3).bitLength == 2; // 00000011 |
| * new BigInt.from(2).bitLength == 2; // 00000010 |
| * new BigInt.from(1).bitLength == 1; // 00000001 |
| * new BigInt.from(0).bitLength == 0; // 00000000 |
| * new BigInt.from(-1).bitLength == 0; // 11111111 |
| * new BigInt.from(-2).bitLength == 1; // 11111110 |
| * new BigInt.from(-3).bitLength == 2; // 11111101 |
| * new BigInt.from(-4).bitLength == 2; // 11111100 |
| * ``` |
| */ |
| int get bitLength { |
| if (_used == 0) return 0; |
| if (_isNegative) return (~this).bitLength; |
| return _digitBits * (_used - 1) + _digits[_used - 1].bitLength; |
| } |
| |
| /** |
| * Truncating division operator. |
| * |
| * Performs a truncating integer division, where the remainder is discarded. |
| * |
| * The remainder can be computed using the [remainder] method. |
| * |
| * Examples: |
| * ``` |
| * var seven = new BigInt.from(7); |
| * var three = new BigInt.from(3); |
| * seven ~/ three; // => 2 |
| * (-seven) ~/ three; // => -2 |
| * seven ~/ -three; // => -2 |
| * seven.remainder(three); // => 1 |
| * (-seven).remainder(three); // => -1 |
| * seven.remainder(-three); // => 1 |
| * ``` |
| */ |
| _BigIntImpl operator ~/(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| if (other._used == 0) { |
| throw const IntegerDivisionByZeroException(); |
| } |
| return _div(other); |
| } |
| |
| /** |
| * Returns the remainder of the truncating division of `this` by [other]. |
| * |
| * The result `r` of this operation satisfies: |
| * `this == (this ~/ other) * other + r`. |
| * As a consequence the remainder `r` has the same sign as the divider `this`. |
| */ |
| _BigIntImpl remainder(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| if (other._used == 0) { |
| throw const IntegerDivisionByZeroException(); |
| } |
| return _rem(other); |
| } |
| |
| /// Division operator. |
| double operator /(BigInt other) => this.toDouble() / other.toDouble(); |
| |
| /** Relational less than operator. */ |
| bool operator <(BigInt other) => compareTo(other) < 0; |
| |
| /** Relational less than or equal operator. */ |
| bool operator <=(BigInt other) => compareTo(other) <= 0; |
| |
| /** Relational greater than operator. */ |
| bool operator >(BigInt other) => compareTo(other) > 0; |
| |
| /** Relational greater than or equal operator. */ |
| bool operator >=(BigInt other) => compareTo(other) >= 0; |
| |
| /** |
| * Euclidean modulo operator. |
| * |
| * Returns the remainder of the Euclidean division. The Euclidean division of |
| * two integers `a` and `b` yields two integers `q` and `r` such that |
| * `a == b * q + r` and `0 <= r < b.abs()`. |
| * |
| * The sign of the returned value `r` is always positive. |
| * |
| * See [remainder] for the remainder of the truncating division. |
| */ |
| _BigIntImpl operator %(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| if (other._used == 0) { |
| throw const IntegerDivisionByZeroException(); |
| } |
| var result = _rem(other); |
| if (result._isNegative) { |
| if (other._isNegative) { |
| result = result - other; |
| } else { |
| result = result + other; |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Returns the sign of this big integer. |
| * |
| * Returns 0 for zero, -1 for values less than zero and |
| * +1 for values greater than zero. |
| */ |
| int get sign { |
| if (_used == 0) return 0; |
| return _isNegative ? -1 : 1; |
| } |
| |
| /// Whether this big integer is even. |
| bool get isEven => _used == 0 || (_digits[0] & 1) == 0; |
| |
| /// Whether this big integer is odd. |
| bool get isOdd => !isEven; |
| |
| /// Whether this number is negative. |
| bool get isNegative => _isNegative; |
| |
| _BigIntImpl pow(int exponent) { |
| if (exponent < 0) { |
| throw new ArgumentError("Exponent must not be negative: $exponent"); |
| } |
| if (exponent == 0) return one; |
| |
| // Exponentiation by squaring. |
| var result = one; |
| var base = this; |
| while (exponent != 0) { |
| if ((exponent & 1) == 1) { |
| result *= base; |
| } |
| exponent >>= 1; |
| // Skip unnecessary operation. |
| if (exponent != 0) { |
| base *= base; |
| } |
| } |
| return result; |
| } |
| |
| /** |
| * Returns this integer to the power of [exponent] modulo [modulus]. |
| * |
| * The [exponent] must be non-negative and [modulus] must be |
| * positive. |
| */ |
| _BigIntImpl modPow(BigInt bigExponent, BigInt bigModulus) { |
| _BigIntImpl exponent = bigExponent; |
| _BigIntImpl modulus = bigModulus; |
| if (exponent._isNegative) { |
| throw new ArgumentError("exponent must be positive: $exponent"); |
| } |
| if (modulus <= zero) { |
| throw new ArgumentError("modulus must be strictly positive: $modulus"); |
| } |
| if (exponent._isZero) return one; |
| |
| final modulusUsed = modulus._used; |
| final modulusUsed2p4 = 2 * modulusUsed + 4; |
| final exponentBitlen = exponent.bitLength; |
| if (exponentBitlen <= 0) return one; |
| _BigIntReduction z = new _BigIntClassic(modulus); |
| var resultDigits = new Uint16List(modulusUsed2p4); |
| var result2Digits = new Uint16List(modulusUsed2p4); |
| var gDigits = new Uint16List(modulusUsed); |
| var gUsed = z.convert(this, gDigits); |
| // Initialize result with g. |
| // Copy leading zero if any. |
| for (int j = gUsed - 1; j >= 0; j--) { |
| resultDigits[j] = gDigits[j]; |
| } |
| var resultUsed = gUsed; |
| var result2Used; |
| for (int i = exponentBitlen - 2; i >= 0; i--) { |
| result2Used = z.sqr(resultDigits, resultUsed, result2Digits); |
| if (!(exponent & (one << i))._isZero) { |
| resultUsed = |
| z.mul(result2Digits, result2Used, gDigits, gUsed, resultDigits); |
| } else { |
| // Swap result and result2. |
| var tmpDigits = resultDigits; |
| var tmpUsed = resultUsed; |
| resultDigits = result2Digits; |
| resultUsed = result2Used; |
| result2Digits = tmpDigits; |
| result2Used = tmpUsed; |
| } |
| } |
| return z.revert(resultDigits, resultUsed); |
| } |
| |
| // If inv is false, returns gcd(x, y). |
| // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1. |
| // If inv is true and gcd(x, y) != 1, throws Exception("Not coprime"). |
| static _BigIntImpl _binaryGcd(_BigIntImpl x, _BigIntImpl y, bool inv) { |
| var xDigits = x._digits; |
| var yDigits = y._digits; |
| var xUsed = x._used; |
| var yUsed = y._used; |
| var maxUsed = xUsed > yUsed ? xUsed : yUsed; |
| var unshiftedMaxUsed = maxUsed; // Keep |
| xDigits = _cloneDigits(xDigits, 0, xUsed, maxUsed); |
| yDigits = _cloneDigits(yDigits, 0, yUsed, maxUsed); |
| int shiftAmount = 0; |
| if (inv) { |
| if ((yUsed == 1) && (yDigits[0] == 1)) return one; |
| if ((yUsed == 0) || (yDigits[0].isEven && xDigits[0].isEven)) { |
| throw new Exception("Not coprime"); |
| } |
| } else { |
| if (x._isZero) { |
| throw new ArgumentError.value(0, "this", "must not be zero"); |
| } |
| if (y._isZero) { |
| throw new ArgumentError.value(0, "other", "must not be zero"); |
| } |
| if (((xUsed == 1) && (xDigits[0] == 1)) || |
| ((yUsed == 1) && (yDigits[0] == 1))) return one; |
| while (((xDigits[0] & 1) == 0) && ((yDigits[0] & 1) == 0)) { |
| _rsh(xDigits, xUsed, 1, xDigits); |
| _rsh(yDigits, yUsed, 1, yDigits); |
| shiftAmount++; |
| } |
| if (shiftAmount >= _digitBits) { |
| var digitShiftAmount = shiftAmount ~/ _digitBits; |
| xUsed -= digitShiftAmount; |
| yUsed -= digitShiftAmount; |
| maxUsed -= digitShiftAmount; |
| } |
| if ((yDigits[0] & 1) == 1) { |
| // Swap x and y. |
| var tmpDigits = xDigits; |
| var tmpUsed = xUsed; |
| xDigits = yDigits; |
| xUsed = yUsed; |
| yDigits = tmpDigits; |
| yUsed = tmpUsed; |
| } |
| } |
| var uDigits = _cloneDigits(xDigits, 0, xUsed, unshiftedMaxUsed); |
| var vDigits = |
| _cloneDigits(yDigits, 0, yUsed, unshiftedMaxUsed + 2); // +2 for lsh. |
| final bool ac = (xDigits[0] & 1) == 0; |
| |
| // Variables a, b, c, and d require one more digit. |
| final abcdUsed = maxUsed + 1; |
| final abcdLen = abcdUsed + 2; // +2 to satisfy _absAdd. |
| var aDigits, bDigits, cDigits, dDigits; |
| bool aIsNegative, bIsNegative, cIsNegative, dIsNegative; |
| if (ac) { |
| aDigits = new Uint16List(abcdLen); |
| aIsNegative = false; |
| aDigits[0] = 1; |
| cDigits = new Uint16List(abcdLen); |
| cIsNegative = false; |
| } |
| bDigits = new Uint16List(abcdLen); |
| bIsNegative = false; |
| dDigits = new Uint16List(abcdLen); |
| dIsNegative = false; |
| dDigits[0] = 1; |
| |
| while (true) { |
| while ((uDigits[0] & 1) == 0) { |
| _rsh(uDigits, maxUsed, 1, uDigits); |
| if (ac) { |
| if (((aDigits[0] & 1) == 1) || ((bDigits[0] & 1) == 1)) { |
| if (aIsNegative) { |
| if ((aDigits[maxUsed] != 0) || |
| (_compareDigits(aDigits, maxUsed, yDigits, maxUsed)) > 0) { |
| _absSub(aDigits, abcdUsed, yDigits, maxUsed, aDigits); |
| } else { |
| _absSub(yDigits, maxUsed, aDigits, maxUsed, aDigits); |
| aIsNegative = false; |
| } |
| } else { |
| _absAdd(aDigits, abcdUsed, yDigits, maxUsed, aDigits); |
| } |
| if (bIsNegative) { |
| _absAdd(bDigits, abcdUsed, xDigits, maxUsed, bDigits); |
| } else if ((bDigits[maxUsed] != 0) || |
| (_compareDigits(bDigits, maxUsed, xDigits, maxUsed) > 0)) { |
| _absSub(bDigits, abcdUsed, xDigits, maxUsed, bDigits); |
| } else { |
| _absSub(xDigits, maxUsed, bDigits, maxUsed, bDigits); |
| bIsNegative = true; |
| } |
| } |
| _rsh(aDigits, abcdUsed, 1, aDigits); |
| } else if ((bDigits[0] & 1) == 1) { |
| if (bIsNegative) { |
| _absAdd(bDigits, abcdUsed, xDigits, maxUsed, bDigits); |
| } else if ((bDigits[maxUsed] != 0) || |
| (_compareDigits(bDigits, maxUsed, xDigits, maxUsed) > 0)) { |
| _absSub(bDigits, abcdUsed, xDigits, maxUsed, bDigits); |
| } else { |
| _absSub(xDigits, maxUsed, bDigits, maxUsed, bDigits); |
| bIsNegative = true; |
| } |
| } |
| _rsh(bDigits, abcdUsed, 1, bDigits); |
| } |
| while ((vDigits[0] & 1) == 0) { |
| _rsh(vDigits, maxUsed, 1, vDigits); |
| if (ac) { |
| if (((cDigits[0] & 1) == 1) || ((dDigits[0] & 1) == 1)) { |
| if (cIsNegative) { |
| if ((cDigits[maxUsed] != 0) || |
| (_compareDigits(cDigits, maxUsed, yDigits, maxUsed) > 0)) { |
| _absSub(cDigits, abcdUsed, yDigits, maxUsed, cDigits); |
| } else { |
| _absSub(yDigits, maxUsed, cDigits, maxUsed, cDigits); |
| cIsNegative = false; |
| } |
| } else { |
| _absAdd(cDigits, abcdUsed, yDigits, maxUsed, cDigits); |
| } |
| if (dIsNegative) { |
| _absAdd(dDigits, abcdUsed, xDigits, maxUsed, dDigits); |
| } else if ((dDigits[maxUsed] != 0) || |
| (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) { |
| _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits); |
| } else { |
| _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits); |
| dIsNegative = true; |
| } |
| } |
| _rsh(cDigits, abcdUsed, 1, cDigits); |
| } else if ((dDigits[0] & 1) == 1) { |
| if (dIsNegative) { |
| _absAdd(dDigits, abcdUsed, xDigits, maxUsed, dDigits); |
| } else if ((dDigits[maxUsed] != 0) || |
| (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) { |
| _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits); |
| } else { |
| _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits); |
| dIsNegative = true; |
| } |
| } |
| _rsh(dDigits, abcdUsed, 1, dDigits); |
| } |
| if (_compareDigits(uDigits, maxUsed, vDigits, maxUsed) >= 0) { |
| _absSub(uDigits, maxUsed, vDigits, maxUsed, uDigits); |
| if (ac) { |
| if (aIsNegative == cIsNegative) { |
| var a_cmp_c = _compareDigits(aDigits, abcdUsed, cDigits, abcdUsed); |
| if (a_cmp_c > 0) { |
| _absSub(aDigits, abcdUsed, cDigits, abcdUsed, aDigits); |
| } else { |
| _absSub(cDigits, abcdUsed, aDigits, abcdUsed, aDigits); |
| aIsNegative = !aIsNegative && (a_cmp_c != 0); |
| } |
| } else { |
| _absAdd(aDigits, abcdUsed, cDigits, abcdUsed, aDigits); |
| } |
| } |
| if (bIsNegative == dIsNegative) { |
| var b_cmp_d = _compareDigits(bDigits, abcdUsed, dDigits, abcdUsed); |
| if (b_cmp_d > 0) { |
| _absSub(bDigits, abcdUsed, dDigits, abcdUsed, bDigits); |
| } else { |
| _absSub(dDigits, abcdUsed, bDigits, abcdUsed, bDigits); |
| bIsNegative = !bIsNegative && (b_cmp_d != 0); |
| } |
| } else { |
| _absAdd(bDigits, abcdUsed, dDigits, abcdUsed, bDigits); |
| } |
| } else { |
| _absSub(vDigits, maxUsed, uDigits, maxUsed, vDigits); |
| if (ac) { |
| if (cIsNegative == aIsNegative) { |
| var c_cmp_a = _compareDigits(cDigits, abcdUsed, aDigits, abcdUsed); |
| if (c_cmp_a > 0) { |
| _absSub(cDigits, abcdUsed, aDigits, abcdUsed, cDigits); |
| } else { |
| _absSub(aDigits, abcdUsed, cDigits, abcdUsed, cDigits); |
| cIsNegative = !cIsNegative && (c_cmp_a != 0); |
| } |
| } else { |
| _absAdd(cDigits, abcdUsed, aDigits, abcdUsed, cDigits); |
| } |
| } |
| if (dIsNegative == bIsNegative) { |
| var d_cmp_b = _compareDigits(dDigits, abcdUsed, bDigits, abcdUsed); |
| if (d_cmp_b > 0) { |
| _absSub(dDigits, abcdUsed, bDigits, abcdUsed, dDigits); |
| } else { |
| _absSub(bDigits, abcdUsed, dDigits, abcdUsed, dDigits); |
| dIsNegative = !dIsNegative && (d_cmp_b != 0); |
| } |
| } else { |
| _absAdd(dDigits, abcdUsed, bDigits, abcdUsed, dDigits); |
| } |
| } |
| // Exit loop if u == 0. |
| var i = maxUsed; |
| while ((i > 0) && (uDigits[i - 1] == 0)) --i; |
| if (i == 0) break; |
| } |
| if (!inv) { |
| if (shiftAmount > 0) { |
| maxUsed = _lShiftDigits(vDigits, maxUsed, shiftAmount, vDigits); |
| } |
| return new _BigIntImpl._(false, maxUsed, vDigits); |
| } |
| // No inverse if v != 1. |
| var i = maxUsed - 1; |
| while ((i > 0) && (vDigits[i] == 0)) --i; |
| if ((i != 0) || (vDigits[0] != 1)) { |
| throw new Exception("Not coprime"); |
| } |
| |
| if (dIsNegative) { |
| if ((dDigits[maxUsed] != 0) || |
| (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) { |
| _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits); |
| if ((dDigits[maxUsed] != 0) || |
| (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) { |
| _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits); |
| } else { |
| _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits); |
| dIsNegative = false; |
| } |
| } else { |
| _absSub(xDigits, maxUsed, dDigits, maxUsed, dDigits); |
| dIsNegative = false; |
| } |
| } else if ((dDigits[maxUsed] != 0) || |
| (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) { |
| _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits); |
| if ((dDigits[maxUsed] != 0) || |
| (_compareDigits(dDigits, maxUsed, xDigits, maxUsed) > 0)) { |
| _absSub(dDigits, abcdUsed, xDigits, maxUsed, dDigits); |
| } |
| } |
| return new _BigIntImpl._(false, maxUsed, dDigits); |
| } |
| |
| /** |
| * Returns the modular multiplicative inverse of this big integer |
| * modulo [modulus]. |
| * |
| * The [modulus] must be positive. |
| * |
| * It is an error if no modular inverse exists. |
| */ |
| // Returns 1/this % modulus, with modulus > 0. |
| _BigIntImpl modInverse(BigInt bigInt) { |
| _BigIntImpl modulus = bigInt; |
| if (modulus <= zero) { |
| throw new ArgumentError("Modulus must be strictly positive: $modulus"); |
| } |
| if (modulus == one) return zero; |
| var tmp = this; |
| if (tmp._isNegative || (tmp._absCompare(modulus) >= 0)) { |
| tmp %= modulus; |
| } |
| return _binaryGcd(modulus, tmp, true); |
| } |
| |
| /** |
| * Returns the greatest common divisor of this big integer and [other]. |
| * |
| * If either number is non-zero, the result is the numerically greatest |
| * integer dividing both `this` and `other`. |
| * |
| * The greatest common divisor is independent of the order, |
| * so `x.gcd(y)` is always the same as `y.gcd(x)`. |
| * |
| * For any integer `x`, `x.gcd(x)` is `x.abs()`. |
| * |
| * If both `this` and `other` is zero, the result is also zero. |
| */ |
| _BigIntImpl gcd(BigInt bigInt) { |
| _BigIntImpl other = bigInt; |
| if (_isZero) return other.abs(); |
| if (other._isZero) return this.abs(); |
| return _binaryGcd(this, other, false); |
| } |
| |
| /** |
| * Returns the least significant [width] bits of this big integer as a |
| * non-negative number (i.e. unsigned representation). The returned value has |
| * zeros in all bit positions higher than [width]. |
| * |
| * ``` |
| * new BigInt.from(-1).toUnsigned(5) == 31 // 11111111 -> 00011111 |
| * ``` |
| * |
| * This operation can be used to simulate arithmetic from low level languages. |
| * For example, to increment an 8 bit quantity: |
| * |
| * ``` |
| * q = (q + 1).toUnsigned(8); |
| * ``` |
| * |
| * `q` will count from `0` up to `255` and then wrap around to `0`. |
| * |
| * If the input fits in [width] bits without truncation, the result is the |
| * same as the input. The minimum width needed to avoid truncation of `x` is |
| * given by `x.bitLength`, i.e. |
| * |
| * ``` |
| * x == x.toUnsigned(x.bitLength); |
| * ``` |
| */ |
| _BigIntImpl toUnsigned(int width) { |
| return this & ((one << width) - one); |
| } |
| |
| /** |
| * Returns the least significant [width] bits of this integer, extending the |
| * highest retained bit to the sign. This is the same as truncating the value |
| * to fit in [width] bits using an signed 2-s complement representation. The |
| * returned value has the same bit value in all positions higher than [width]. |
| * |
| * ``` |
| * var big15 = new BigInt.from(15); |
| * var big16 = new BigInt.from(16); |
| * var big239 = new BigInt.from(239); |
| * V--sign bit-V |
| * big16.toSigned(5) == -big16 // 00010000 -> 11110000 |
| * big239.toSigned(5) == big15 // 11101111 -> 00001111 |
| * ^ ^ |
| * ``` |
| * |
| * This operation can be used to simulate arithmetic from low level languages. |
| * For example, to increment an 8 bit signed quantity: |
| * |
| * ``` |
| * q = (q + 1).toSigned(8); |
| * ``` |
| * |
| * `q` will count from `0` up to `127`, wrap to `-128` and count back up to |
| * `127`. |
| * |
| * If the input value fits in [width] bits without truncation, the result is |
| * the same as the input. The minimum width needed to avoid truncation of `x` |
| * is `x.bitLength + 1`, i.e. |
| * |
| * ``` |
| * x == x.toSigned(x.bitLength + 1); |
| * ``` |
| */ |
| _BigIntImpl toSigned(int width) { |
| // The value of binary number weights each bit by a power of two. The |
| // twos-complement value weights the sign bit negatively. We compute the |
| // value of the negative weighting by isolating the sign bit with the |
| // correct power of two weighting and subtracting it from the value of the |
| // lower bits. |
| var signMask = one << (width - 1); |
| return (this & (signMask - one)) - (this & signMask); |
| } |
| |
| // TODO(floitsch): implement `isValidInt`. |
| // Remove the comment in [BigInt.isValidInt] when done. |
| bool get isValidInt => true; |
| |
| // TODO(floitsch): implement the clamping. It behaves differently on dart2js |
| // and the VM. |
| // Remove the comment in [BigInt.isValidInt] when done. |
| int toInt() { |
| var result = 0; |
| for (int i = _used - 1; i >= 0; i--) { |
| result = result * _digitBase + _digits[i]; |
| } |
| return _isNegative ? -result : result; |
| } |
| |
| /** |
| * Returns this [_BigIntImpl] as a [double]. |
| * |
| * If the number is not representable as a [double], an |
| * approximation is returned. For numerically large integers, the |
| * approximation may be infinite. |
| */ |
| double toDouble() { |
| const int exponentBias = 1075; |
| // There are 11 bits for the exponent. |
| // 2047 (all bits set to 1) is reserved for infinity and NaN. |
| // When storing the exponent in the 11 bits, it is biased by exponentBias |
| // to support negative exponents. |
| const int maxDoubleExponent = 2046 - exponentBias; |
| if (_isZero) return 0.0; |
| |
| // We fill the 53 bits little-endian. |
| var resultBits = new Uint8List(8); |
| |
| var length = _digitBits * (_used - 1) + _digits[_used - 1].bitLength; |
| if (length - 53 > maxDoubleExponent) return double.INFINITY; |
| |
| // The most significant bit is for the sign. |
| if (_isNegative) resultBits[7] = 0x80; |
| |
| // Write the exponent into bits 1..12: |
| var biasedExponent = length - 53 + exponentBias; |
| resultBits[6] = (biasedExponent & 0xF) << 4; |
| resultBits[7] |= biasedExponent >> 4; |
| |
| int cachedBits = 0; |
| int cachedBitsLength = 0; |
| int digitIndex = _used - 1; |
| int readBits(int n) { |
| // Ensure that we have enough bits in [cachedBits]. |
| while (cachedBitsLength < n) { |
| int nextDigit; |
| int nextDigitLength = _digitBits; // May get updated. |
| if (digitIndex < 0) { |
| nextDigit = 0; |
| digitIndex--; |
| } else { |
| nextDigit = _digits[digitIndex]; |
| if (digitIndex == _used - 1) nextDigitLength = nextDigit.bitLength; |
| digitIndex--; |
| } |
| cachedBits = (cachedBits << nextDigitLength) + nextDigit; |
| cachedBitsLength += nextDigitLength; |
| } |
| // Read the top [n] bits. |
| var result = cachedBits >> (cachedBitsLength - n); |
| // Remove the bits from the cache. |
| cachedBits -= result << (cachedBitsLength - n); |
| cachedBitsLength -= n; |
| return result; |
| } |
| |
| // The first leading 1 bit is implicit in the double-representation and can |
| // be discarded. |
| var leadingBits = readBits(5) & 0xF; |
| resultBits[6] |= leadingBits; |
| |
| for (int i = 5; i >= 0; i--) { |
| // Get the remaining 48 bits. |
| resultBits[i] = readBits(8); |
| } |
| |
| void roundUp() { |
| // Simply consists of adding 1 to the whole 64 bit "number". |
| // It will update the exponent, if necessary. |
| // It might even round up to infinity (which is what we want). |
| var carry = 1; |
| for (int i = 0; i < 8; i++) { |
| if (carry == 0) break; |
| var sum = resultBits[i] + carry; |
| resultBits[i] = sum & 0xFF; |
| carry = sum >> 8; |
| } |
| } |
| |
| if (readBits(1) == 1) { |
| if (resultBits[0].isOdd) { |
| // Rounds to even all the time. |
| roundUp(); |
| } else { |
| // Round up, if there is at least one other digit that is not 0. |
| if (cachedBits != 0) { |
| // There is already one in the cachedBits. |
| roundUp(); |
| } else { |
| for (int i = digitIndex; digitIndex >= 0; i--) { |
| if (_digits[i] != 0) { |
| roundUp(); |
| break; |
| } |
| } |
| } |
| } |
| } |
| return resultBits.buffer.asByteData().getFloat64(0, Endian.little); |
| } |
| |
| /** |
| * Returns a String-representation of this integer. |
| * |
| * The returned string is parsable by [parse]. |
| * For any `_BigIntImpl` `i`, it is guaranteed that |
| * `i == _BigIntImpl.parse(i.toString())`. |
| */ |
| String toString() { |
| if (_used == 0) return "0"; |
| if (_used == 1) { |
| if (_isNegative) return (-_digits[0]).toString(); |
| return _digits[0].toString(); |
| } |
| |
| // Generate in chunks of 4 digits. |
| // The chunks are in reversed order. |
| var decimalDigitChunks = <String>[]; |
| var rest = isNegative ? -this : this; |
| while (rest._used > 1) { |
| var digits4 = rest.remainder(_bigInt10000).toString(); |
| decimalDigitChunks.add(digits4); |
| if (digits4.length == 1) decimalDigitChunks.add("000"); |
| if (digits4.length == 2) decimalDigitChunks.add("00"); |
| if (digits4.length == 3) decimalDigitChunks.add("0"); |
| rest = rest ~/ _bigInt10000; |
| } |
| decimalDigitChunks.add(rest._digits[0].toString()); |
| if (_isNegative) decimalDigitChunks.add("-"); |
| return decimalDigitChunks.reversed.join(); |
| } |
| |
| int _toRadixCodeUnit(int digit) { |
| const int _0 = 48; |
| const int _a = 97; |
| if (digit < 10) return _0 + digit; |
| return _a + digit - 10; |
| } |
| |
| /** |
| * Converts [this] to a string representation in the given [radix]. |
| * |
| * In the string representation, lower-case letters are used for digits above |
| * '9', with 'a' being 10 an 'z' being 35. |
| * |
| * The [radix] argument must be an integer in the range 2 to 36. |
| */ |
| String toRadixString(int radix) { |
| if (radix > 36) throw new RangeError.range(radix, 2, 36); |
| |
| if (_used == 0) return "0"; |
| |
| if (_used == 1) { |
| var digitString = _digits[0].toRadixString(radix); |
| if (_isNegative) return "-" + digitString; |
| return digitString; |
| } |
| |
| if (radix == 16) return _toHexString(); |
| |
| var base = new _BigIntImpl._fromInt(radix); |
| var reversedDigitCodeUnits = <int>[]; |
| var rest = this.abs(); |
| while (!rest._isZero) { |
| var digit = rest.remainder(base).toInt(); |
| rest = rest ~/ base; |
| reversedDigitCodeUnits.add(_toRadixCodeUnit(digit)); |
| } |
| var digitString = new String.fromCharCodes(reversedDigitCodeUnits.reversed); |
| if (_isNegative) return "-" + digitString; |
| return digitString; |
| } |
| |
| String _toHexString() { |
| var chars = <int>[]; |
| for (int i = 0; i < _used - 1; i++) { |
| int chunk = _digits[i]; |
| for (int j = 0; j < (_digitBits ~/ 4); j++) { |
| chars.add(_toRadixCodeUnit(chunk & 0xF)); |
| chunk >>= 4; |
| } |
| } |
| var msbChunk = _digits[_used - 1]; |
| while (msbChunk != 0) { |
| chars.add(_toRadixCodeUnit(msbChunk & 0xF)); |
| msbChunk >>= 4; |
| } |
| if (_isNegative) { |
| const _dash = 45; |
| chars.add(_dash); |
| } |
| return new String.fromCharCodes(chars.reversed); |
| } |
| } |
| |
| // Interface for modular reduction. |
| abstract class _BigIntReduction { |
| // Return the number of digits used by r_digits. |
| int convert(_BigIntImpl x, Uint16List r_digits); |
| int mul(Uint16List xDigits, int xUsed, Uint16List yDigits, int yUsed, |
| Uint16List resultDigits); |
| int sqr(Uint16List xDigits, int xUsed, Uint16List resultDigits); |
| |
| // Return x reverted to _BigIntImpl. |
| _BigIntImpl revert(Uint16List xDigits, int xUsed); |
| } |
| |
| // Modular reduction using "classic" algorithm. |
| class _BigIntClassic implements _BigIntReduction { |
| final _BigIntImpl _modulus; // Modulus. |
| final _BigIntImpl _normalizedModulus; // Normalized _modulus. |
| |
| _BigIntClassic(this._modulus) |
| : _normalizedModulus = _modulus << |
| (_BigIntImpl._digitBits - |
| _modulus._digits[_modulus._used - 1].bitLength); |
| |
| int convert(_BigIntImpl x, Uint16List resultDigits) { |
| var digits; |
| var used; |
| if (x._isNegative || x.compareTo(_modulus) >= 0) { |
| var remainder = x._rem(_modulus); |
| if (x._isNegative && !remainder._isNegative && remainder._used > 0) { |
| remainder = _modulus - remainder; |
| } |
| assert(!remainder._isNegative); |
| used = remainder._used; |
| digits = remainder._digits; |
| } else { |
| used = x._used; |
| digits = x._digits; |
| } |
| var i = used; // Copy leading zero if any. |
| while (--i >= 0) { |
| resultDigits[i] = digits[i]; |
| } |
| return used; |
| } |
| |
| _BigIntImpl revert(Uint16List xDigits, int xUsed) { |
| return new _BigIntImpl._(false, xUsed, xDigits); |
| } |
| |
| int _reduce(Uint16List xDigits, int xUsed) { |
| if (xUsed < _modulus._used) { |
| return xUsed; |
| } |
| var reverted = revert(xDigits, xUsed); |
| var rem = reverted._rem(_normalizedModulus); |
| return convert(rem, xDigits); |
| } |
| |
| int sqr(Uint16List xDigits, int xUsed, Uint16List resultDigits) { |
| var b = new _BigIntImpl._(false, xUsed, xDigits); |
| var b2 = b * b; |
| for (int i = 0; i < b2._used; i++) { |
| resultDigits[i] = b2._digits[i]; |
| } |
| for (int i = b2._used; i < 2 * xUsed; i++) { |
| resultDigits[i] = 0; |
| } |
| return _reduce(resultDigits, 2 * xUsed); |
| } |
| |
| int mul(Uint16List xDigits, int xUsed, Uint16List yDigits, int yUsed, |
| Uint16List resultDigits) { |
| var resultUsed = |
| _BigIntImpl._mulDigits(xDigits, xUsed, yDigits, yUsed, resultDigits); |
| return _reduce(resultDigits, resultUsed); |
| } |
| } |