Google Git
Sign in
dart / sdk.git / dfff7719c2a23d7f1ff12b093e555d562e7f6d84 / . / pkg / fixnum / lib / src / int64.dart
blob: 036a06b837d12a6a143a80ad5e7659d0f02f3f8a [file] [log] [blame]
// Copyright (c) 2012, 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 fixnum;
/**
* An immutable 64-bit signed integer, in the range [-2^63, 2^63 - 1].
* Arithmetic operations may overflow in order to maintain this range.
*/
class Int64 implements IntX {
// A 64-bit integer is represented internally as three non-negative
// integers, storing the 22 low, 22 middle, and 20 high bits of the
// 64-bit value. _l (low) and _m (middle) are in the range
// [0, 2^22 - 1] and _h (high) is in the range [0, 2^20 - 1].
int _l, _m, _h;
// Note: instances of [Int64] are immutable outside of this library,
// therefore we may return a reference to an existing instance.
// We take care to perform mutation only on internally-generated
// instances before they are exposed to external code.
// Note: several functions require _BITS == 22 -- do not change this value.
static const int _BITS = 22;
static const int _BITS01 = 44; // 2 * _BITS
static const int _BITS2 = 20; // 64 - _BITS01
static const int _MASK = 4194303; // (1 << _BITS) - 1
static const int _MASK2 = 1048575; // (1 << _BITS2) - 1
static const int _SIGN_BIT = 19; // _BITS2 - 1
static const int _SIGN_BIT_MASK = 524288; // 1 << _SIGN_BIT
// Cached constants
static Int64 _MAX_VALUE;
static Int64 _MIN_VALUE;
static Int64 _ZERO;
static Int64 _ONE;
static Int64 _TWO;
// The remainder of the last divide operation.
static Int64 _remainder;
/**
* The maximum positive value attainable by an [Int64], namely
* 9,223,372,036,854,775,807.
*/
static Int64 get MAX_VALUE {
if (_MAX_VALUE == null) {
_MAX_VALUE = new Int64._bits(_MASK, _MASK, _MASK2 >> 1);
}
return _MAX_VALUE;
}
/**
* The minimum positive value attainable by an [Int64], namely
* -9,223,372,036,854,775,808.
*/
static Int64 get MIN_VALUE {
if (_MIN_VALUE == null) {
_MIN_VALUE = new Int64._bits(0, 0, _SIGN_BIT_MASK);
}
return _MIN_VALUE;
}
/**
* An [Int64] constant equal to 0.
*/
static Int64 get ZERO {
if (_ZERO == null) {
_ZERO = new Int64();
}
return _ZERO;
}
/**
* An [Int64] constant equal to 1.
*/
static Int64 get ONE {
if (_ONE == null) {
_ONE = new Int64._bits(1, 0, 0);
}
return _ONE;
}
/**
* An [Int64] constant equal to 2.
*/
static Int64 get TWO {
if (_TWO == null) {
_TWO = new Int64._bits(2, 0, 0);
}
return _TWO;
}
/**
* Parses a [String] in a given [radix] between 2 and 36 and returns an
* [Int64].
*/
static Int64 parseRadix(String s, int radix) {
if ((radix <= 1) || (radix > 36)) {
throw new ArgumentError("Bad radix: $radix");
}
return _parseRadix(s, radix);
}
static Int64 _parseRadix(String s, int radix) {
int i = 0;
bool negative = false;
if (s[0] == '-') {
negative = true;
i++;
}
int d0 = 0, d1 = 0, d2 = 0; // low, middle, high components.
for (; i < s.length; i++) {
int c = s.codeUnitAt(i);
int digit = Int32._decodeDigit(c);
if (digit < 0 || digit >= radix) {
throw new Exception("Non-radix char code: $c");
}
// [radix] and [digit] are at most 6 bits, component is 22, so we can
// multiply and add within 30 bit temporary values.
d0 = d0 * radix + digit;
int carry = d0 >> _BITS;
d0 &= _MASK;
d1 = d1 * radix + carry;
carry = d1 >> _BITS;
d1 &= _MASK;
d2 = d2 * radix + carry;
d2 &= _MASK2;
}
if (negative) {
d0 = 0 - d0;
int borrow = (d0 >> _BITS) & 1;
d0 &= _MASK;
d1 = 0 - d1 - borrow;
borrow = (d1 >> _BITS) & 1;
d1 &= _MASK;
d2 = 0 - d2 - borrow;
d2 &= _MASK2;
}
return new Int64._bits(d0, d1, d2);
}
/**
* Parses a decimal [String] and returns an [Int64].
*/
static Int64 parseInt(String s) => _parseRadix(s, 10);
/**
* Parses a hexadecimal [String] and returns an [Int64].
*/
static Int64 parseHex(String s) => _parseRadix(s, 16);
//
// Public constructors
//
/**
* Constructs an [Int64] equal to 0.
*/
Int64() : _l = 0, _m = 0, _h = 0;
/**
* Constructs an [Int64] with a given [int] value.
*/
Int64.fromInt(int value) {
bool negative = false;
if (value < 0) {
negative = true;
value = -value - 1;
}
if (_haveBigInts) {
_l = value & _MASK;
_m = (value >> _BITS) & _MASK;
_h = (value >> _BITS01) & _MASK2;
} else {
// Avoid using bitwise operations that coerce their input to 32 bits.
_h = value ~/ 17592186044416; // 2^44
value -= _h * 17592186044416;
_m = value ~/ 4194304; // 2^22
value -= _m * 4194304;
_l = value;
}
if (negative) {
_l = ~_l & _MASK;
_m = ~_m & _MASK;
_h = ~_h & _MASK2;
}
}
factory Int64.fromBytes(List<int> bytes) {
int top = bytes[7] & 0xff;
top <<= 8;
top |= bytes[6] & 0xff;
top <<= 8;
top |= bytes[5] & 0xff;
top <<= 8;
top |= bytes[4] & 0xff;
int bottom = bytes[3] & 0xff;
bottom <<= 8;
bottom |= bytes[2] & 0xff;
bottom <<= 8;
bottom |= bytes[1] & 0xff;
bottom <<= 8;
bottom |= bytes[0] & 0xff;
return new Int64.fromInts(top, bottom);
}
factory Int64.fromBytesBigEndian(List<int> bytes) {
int top = bytes[0] & 0xff;
top <<= 8;
top |= bytes[1] & 0xff;
top <<= 8;
top |= bytes[2] & 0xff;
top <<= 8;
top |= bytes[3] & 0xff;
int bottom = bytes[4] & 0xff;
bottom <<= 8;
bottom |= bytes[5] & 0xff;
bottom <<= 8;
bottom |= bytes[6] & 0xff;
bottom <<= 8;
bottom |= bytes[7] & 0xff;
return new Int64.fromInts(top, bottom);
}
/**
* Constructs an [Int64] from a pair of 32-bit integers having the value
* [:((top & 0xffffffff) << 32) | (bottom & 0xffffffff):].
*/
factory Int64.fromInts(int top, int bottom) {
top &= 0xffffffff;
bottom &= 0xffffffff;
int d0 = bottom & _MASK;
int d1 = ((top & 0xfff) << 10) | ((bottom >> _BITS) & 0x3ff);
int d2 = (top >> 12) & _MASK2;
return new Int64._bits(d0, d1, d2);
}
// Returns the [Int64] representation of the specified value. Throws
// [ArgumentError] for non-integer arguments.
Int64 _promote(val) {
if (val is Int64) {
return val;
} else if (val is int) {
return new Int64.fromInt(val);
} else if (val is Int32) {
return val.toInt64();
}
throw new ArgumentError(val);
}
Int64 operator +(other) {
Int64 o = _promote(other);
int sum0 = _l + o._l;
int sum1 = _m + o._m + _shiftRight(sum0, _BITS);
int sum2 = _h + o._h + _shiftRight(sum1, _BITS);
Int64 result = new Int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK2);
return result;
}
Int64 operator -(other) {
Int64 o = _promote(other);
int sum0 = _l - o._l;
int sum1 = _m - o._m + _shiftRight(sum0, _BITS);
int sum2 = _h - o._h + _shiftRight(sum1, _BITS);
Int64 result = new Int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK2);
return result;
}
Int64 operator -() {
// Like 0 - this.
int sum0 = -_l;
int sum1 = -_m + _shiftRight(sum0, _BITS);
int sum2 = -_h + _shiftRight(sum1, _BITS);
return new Int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK2);
}
Int64 operator *(other) {
Int64 o = _promote(other);
// Grab 13-bit chunks.
int a0 = _l & 0x1fff;
int a1 = (_l >> 13) | ((_m & 0xf) << 9);
int a2 = (_m >> 4) & 0x1fff;
int a3 = (_m >> 17) | ((_h & 0xff) << 5);
int a4 = (_h & 0xfff00) >> 8;
int b0 = o._l & 0x1fff;
int b1 = (o._l >> 13) | ((o._m & 0xf) << 9);
int b2 = (o._m >> 4) & 0x1fff;
int b3 = (o._m >> 17) | ((o._h & 0xff) << 5);
int b4 = (o._h & 0xfff00) >> 8;
// Compute partial products.
// Optimization: if b is small, avoid multiplying by parts that are 0.
int p0 = a0 * b0; // << 0
int p1 = a1 * b0; // << 13
int p2 = a2 * b0; // << 26
int p3 = a3 * b0; // << 39
int p4 = a4 * b0; // << 52
if (b1 != 0) {
p1 += a0 * b1;
p2 += a1 * b1;
p3 += a2 * b1;
p4 += a3 * b1;
}
if (b2 != 0) {
p2 += a0 * b2;
p3 += a1 * b2;
p4 += a2 * b2;
}
if (b3 != 0) {
p3 += a0 * b3;
p4 += a1 * b3;
}
if (b4 != 0) {
p4 += a0 * b4;
}
// Accumulate into 22-bit chunks:
// .........................................c10|...................c00|
// |....................|..................xxxx|xxxxxxxxxxxxxxxxxxxxxx| p0
// |....................|......................|......................|
// |....................|...................c11|......c01.............|
// |....................|....xxxxxxxxxxxxxxxxxx|xxxxxxxxx.............| p1
// |....................|......................|......................|
// |.................c22|...............c12....|......................|
// |..........xxxxxxxxxx|xxxxxxxxxxxxxxxxxx....|......................| p2
// |....................|......................|......................|
// |.................c23|..c13.................|......................|
// |xxxxxxxxxxxxxxxxxxxx|xxxxx.................|......................| p3
// |....................|......................|......................|
// |.........c24........|......................|......................|
// |xxxxxxxxxxxx........|......................|......................| p4
int c00 = p0 & 0x3fffff;
int c01 = (p1 & 0x1ff) << 13;
int c0 = c00 + c01;
int c10 = p0 >> 22;
int c11 = p1 >> 9;
int c12 = (p2 & 0x3ffff) << 4;
int c13 = (p3 & 0x1f) << 17;
int c1 = c10 + c11 + c12 + c13;
int c22 = p2 >> 18;
int c23 = p3 >> 5;
int c24 = (p4 & 0xfff) << 8;
int c2 = c22 + c23 + c24;
// Propagate high bits from c0 -> c1, c1 -> c2.
c1 += c0 >> _BITS;
c0 &= _MASK;
c2 += c1 >> _BITS;
c1 &= _MASK;
c2 &= _MASK2;
return new Int64._bits(c0, c1, c2);
}
Int64 operator %(other) {
if (other.isZero) {
throw new IntegerDivisionByZeroException();
}
if (this.isZero) {
return ZERO;
}
Int64 o = _promote(other).abs();
_divMod(this, o, true);
return _remainder < 0 ? (_remainder + o) : _remainder;
}
Int64 operator ~/(other) => _divMod(this, _promote(other), false);
// Int64 remainder(other) => this - (this ~/ other) * other;
Int64 remainder(other) {
if (other.isZero) {
throw new IntegerDivisionByZeroException();
}
Int64 o = _promote(other).abs();
_divMod(this, o, true);
return _remainder;
}
Int64 operator &(other) {
Int64 o = _promote(other);
int a0 = _l & o._l;
int a1 = _m & o._m;
int a2 = _h & o._h;
return new Int64._bits(a0, a1, a2);
}
Int64 operator |(other) {
Int64 o = _promote(other);
int a0 = _l | o._l;
int a1 = _m | o._m;
int a2 = _h | o._h;
return new Int64._bits(a0, a1, a2);
}
Int64 operator ^(other) {
Int64 o = _promote(other);
int a0 = _l ^ o._l;
int a1 = _m ^ o._m;
int a2 = _h ^ o._h;
return new Int64._bits(a0, a1, a2);
}
Int64 operator ~() {
var result = new Int64._bits((~_l) & _MASK, (~_m) & _MASK, (~_h) & _MASK2);
return result;
}
Int64 operator <<(int n) {
if (n < 0) {
throw new ArgumentError(n);
}
n &= 63;
int res0, res1, res2;
if (n < _BITS) {
res0 = _l << n;
res1 = (_m << n) | (_l >> (_BITS - n));
res2 = (_h << n) | (_m >> (_BITS - n));
} else if (n < _BITS01) {
res0 = 0;
res1 = _l << (n - _BITS);
res2 = (_m << (n - _BITS)) | (_l >> (_BITS01 - n));
} else {
res0 = 0;
res1 = 0;
res2 = _l << (n - _BITS01);
}
return new Int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK2);
}
Int64 operator >>(int n) {
if (n < 0) {
throw new ArgumentError(n);
}
n &= 63;
int res0, res1, res2;
// Sign extend h(a).
int a2 = _h;
bool negative = (a2 & _SIGN_BIT_MASK) != 0;
if (negative) {
a2 += 0x3 << _BITS2; // add extra one bits on the left
}
if (n < _BITS) {
res2 = _shiftRight(a2, n);
if (negative) {
res2 |= _MASK2 & ~(_MASK2 >> n);
}
res1 = _shiftRight(_m, n) | (a2 << (_BITS - n));
res0 = _shiftRight(_l, n) | (_m << (_BITS - n));
} else if (n < _BITS01) {
res2 = negative ? _MASK2 : 0;
res1 = _shiftRight(a2, n - _BITS);
if (negative) {
res1 |= _MASK & ~(_MASK >> (n - _BITS));
}
res0 = _shiftRight(_m, n - _BITS) | (a2 << (_BITS01 - n));
} else {
res2 = negative ? _MASK2 : 0;
res1 = negative ? _MASK : 0;
res0 = _shiftRight(a2, n - _BITS01);
if (negative) {
res0 |= _MASK & ~(_MASK >> (n - _BITS01));
}
}
return new Int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK2);
}
Int64 shiftRightUnsigned(int n) {
if (n < 0) {
throw new ArgumentError(n);
}
n &= 63;
int res0, res1, res2;
int a2 = _h & _MASK2; // Ensure a2 is positive.
if (n < _BITS) {
res2 = a2 >> n;
res1 = (_m >> n) | (a2 << (_BITS - n));
res0 = (_l >> n) | (_m << (_BITS - n));
} else if (n < _BITS01) {
res2 = 0;
res1 = a2 >> (n - _BITS);
res0 = (_m >> (n - _BITS)) | (_h << (_BITS01 - n));
} else {
res2 = 0;
res1 = 0;
res0 = a2 >> (n - _BITS01);
}
return new Int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK2);
}
/**
* Returns [true] if this [Int64] has the same numeric value as the
* given object. The argument may be an [int] or an [IntX].
*/
bool operator ==(other) {
Int64 o;
if (other is Int64) {
o = other;
} else if (other is int) {
o = new Int64.fromInt(other);
} else if (other is Int32) {
o = other.toInt64();
}
if (o != null) {
return _l == o._l && _m == o._m && _h == o._h;
}
return false;
}
int compareTo(Comparable other) {
Int64 o = _promote(other);
int signa = _h >> (_BITS2 - 1);
int signb = o._h >> (_BITS2 - 1);
if (signa != signb) {
return signa == 0 ? 1 : -1;
}
if (_h > o._h) {
return 1;
} else if (_h < o._h) {
return -1;
}
if (_m > o._m) {
return 1;
} else if (_m < o._m) {
return -1;
}
if (_l > o._l) {
return 1;
} else if (_l < o._l) {
return -1;
}
return 0;
}
bool operator <(other) {
return this.compareTo(other) < 0;
}
bool operator <=(other) {
return this.compareTo(other) <= 0;
}
bool operator >(other) {
return this.compareTo(other) > 0;
}
bool operator >=(other) {
return this.compareTo(other) >= 0;
}
bool get isEven => (_l & 0x1) == 0;
bool get isMaxValue => (_h == _MASK2 >> 1) && _m == _MASK && _l == _MASK;
bool get isMinValue => _h == _SIGN_BIT_MASK && _m == 0 && _l == 0;
bool get isNegative => (_h >> (_BITS2 - 1)) != 0;
bool get isOdd => (_l & 0x1) == 1;
bool get isZero => _h == 0 && _m == 0 && _l == 0;
/**
* Returns a hash code based on all the bits of this [Int64].
*/
int get hashCode {
int bottom = ((_m & 0x3ff) << _BITS) | _l;
int top = (_h << 12) | ((_m >> 10) & 0xfff);
return bottom ^ top;
}
Int64 abs() {
return this < 0 ? -this : this;
}
/**
* Returns the number of leading zeros in this [Int64] as an [int]
* between 0 and 64.
*/
int numberOfLeadingZeros() {
int b2 = Int32._numberOfLeadingZeros(_h);
if (b2 == 32) {
int b1 = Int32._numberOfLeadingZeros(_m);
if (b1 == 32) {
return Int32._numberOfLeadingZeros(_l) + 32;
} else {
return b1 + _BITS2 - (32 - _BITS);
}
} else {
return b2 - (32 - _BITS2);
}
}
/**
* Returns the number of trailing zeros in this [Int64] as an [int]
* between 0 and 64.
*/
int numberOfTrailingZeros() {
int zeros = Int32._numberOfTrailingZeros(_l);
if (zeros < 32) {
return zeros;
}
zeros = Int32._numberOfTrailingZeros(_m);
if (zeros < 32) {
return _BITS + zeros;
}
zeros = Int32._numberOfTrailingZeros(_h);
if (zeros < 32) {
return _BITS01 + zeros;
}
// All zeros
return 64;
}
List<int> toBytes() {
List<int> result = new List<int>(8);
result[0] = _l & 0xff;
result[1] = (_l >> 8) & 0xff;
result[2] = ((_m << 6) & 0xfc) | ((_l >> 16) & 0x3f);
result[3] = (_m >> 2) & 0xff;
result[4] = (_m >> 10) & 0xff;
result[5] = ((_h << 4) & 0xf0) | ((_m >> 18) & 0xf);
result[6] = (_h >> 4) & 0xff;
result[7] = (_h >> 12) & 0xff;
return result;
}
int toInt() {
int l = _l;
int m = _m;
int h = _h;
bool negative = false;
if ((_h & _SIGN_BIT_MASK) != 0) {
l = ~_l & _MASK;
m = ~_m & _MASK;
h = ~_h & _MASK2;
negative = true;
}
int result;
if (_haveBigInts) {
result = (h << _BITS01) | (m << _BITS) | l;
} else {
result = (h * 17592186044416) + (m * 4194304) + l;
}
return negative ? -result - 1 : result;
}
/**
* Returns an [Int32] containing the low 32 bits of this [Int64].
*/
Int32 toInt32() {
return new Int32.fromInt(((_m & 0x3ff) << _BITS) | _l);
}
/**
* Returns [this].
*/
Int64 toInt64() => this;
/**
* Returns the value of this [Int64] as a decimal [String].
*/
String toString() => _toRadixString(10);
// TODO(rice) - Make this faster by avoiding arithmetic.
String toHexString() {
Int64 x = new Int64._copy(this);
if (isZero) {
return "0";
}
String hexStr = "";
Int64 digit_f = new Int64.fromInt(0xf);
while (!x.isZero) {
int digit = x._l & 0xf;
hexStr = "${_hexDigit(digit)}$hexStr";
x = x.shiftRightUnsigned(4);
}
return hexStr;
}
String toRadixString(int radix) {
if ((radix <= 1) || (radix > 36)) {
throw new ArgumentError("Bad radix: $radix");
}
return _toRadixString(radix);
}
String _toRadixString(int radix) {
int d0 = _l;
int d1 = _m;
int d2 = _h;
if (d0 == 0 && d1 == 0 && d2 == 0) return '0';
String sign = '';
if ((d2 & _SIGN_BIT_MASK) != 0) {
sign = '-';
// Negate in-place.
d0 = 0 - d0;
int borrow = (d0 >> _BITS) & 1;
d0 &= _MASK;
d1 = 0 - d1 - borrow;
borrow = (d1 >> _BITS) & 1;
d1 &= _MASK;
d2 = 0 - d2 - borrow;
d2 &= _MASK2;
// d2, d1, d0 now are an unsigned 64 bit integer for MIN_VALUE and an
// unsigned 63 bit integer for other values.
}
// Rearrange components into five components where all but the most
// significant are 10 bits wide.
//
// d4, d3, d4, d1, d0: 24 + 10 + 10 + 10 + 10 bits
//
// The choice of 10 bits allows a remainder of 20 bits to be scaled by 10
// bits and added during division while keeping all intermediate values
// within 30 bits (unsigned small integer range for 32 bit implementations
// of Dart VM and V8).
//
// 6 6 5 4 3 2 1
// 3210987654321098765432109876543210987654321098765432109876543210
// [--------d2--------][---------d1---------][---------d0---------]
// -->
// [----------d4----------][---d3---][---d2---][---d1---][---d0---]
int d4 = (d2 << 4) | (d1 >> 18);
int d3 = (d1 >> 8) & 0x3ff;
d2 = ((d1 << 2) | (d0 >> 20)) & 0x3ff;
d1 = (d0 >> 10) & 0x3ff;
d0 = d0 & 0x3ff;
int fatRadix = _fatRadixTable[radix];
// Generate chunks of digits. In radix 10, generate 6 digits per chunk.
//
// This loop generates at most 3 chunks, so we store the chunks in locals
// rather than a list. We are trying to generate digits 20 bits at a time
// until we have only 30 bits left. 20 + 20 + 30 > 64 would imply that we
// need only two chunks, but radix values 17-19 and 33-36 generate only 15
// or 16 bits per iteration, so sometimes the third chunk is needed.
String chunk1 = "", chunk2 = "", chunk3 = "";
while (!(d4 == 0 && d3 == 0)) {
int q = d4 ~/ fatRadix;
int r = d4 - q * fatRadix;
d4 = q;
d3 += r << 10;
q = d3 ~/ fatRadix;
r = d3 - q * fatRadix;
d3 = q;
d2 += r << 10;
q = d2 ~/ fatRadix;
r = d2 - q * fatRadix;
d2 = q;
d1 += r << 10;
q = d1 ~/ fatRadix;
r = d1 - q * fatRadix;
d1 = q;
d0 += r << 10;
q = d0 ~/ fatRadix;
r = d0 - q * fatRadix;
d0 = q;
assert(chunk2 == "");
chunk3 = chunk2;
chunk2 = chunk1;
// Adding [fatRadix] Forces an extra digit which we discard to get a fixed
// width. E.g. (1000000 + 123) -> "1000123" -> "000123". An alternative
// would be to pad to the left with zeroes.
chunk1 = (fatRadix + r).toRadixString(radix).substring(1);
}
int residue = (d2 << 20) + (d1 << 10) + d0;
String leadingDigits = residue == 0 ? '' : residue.toRadixString(radix);
return '$sign$leadingDigits$chunk1$chunk2$chunk3';
}
// Table of 'fat' radix values. Each entry for index `i` is the largest power
// of `i` whose remainder fits in 20 bits.
static const _fatRadixTable = const <int>[
0,
0,
2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2
* 2,
3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3,
4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4,
5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
6 * 6 * 6 * 6 * 6 * 6 * 6,
7 * 7 * 7 * 7 * 7 * 7 * 7,
8 * 8 * 8 * 8 * 8 * 8,
9 * 9 * 9 * 9 * 9 * 9,
10 * 10 * 10 * 10 * 10 * 10,
11 * 11 * 11 * 11 * 11,
12 * 12 * 12 * 12 * 12,
13 * 13 * 13 * 13 * 13,
14 * 14 * 14 * 14 * 14,
15 * 15 * 15 * 15 * 15,
16 * 16 * 16 * 16 * 16,
17 * 17 * 17 * 17,
18 * 18 * 18 * 18,
19 * 19 * 19 * 19,
20 * 20 * 20 * 20,
21 * 21 * 21 * 21,
22 * 22 * 22 * 22,
23 * 23 * 23 * 23,
24 * 24 * 24 * 24,
25 * 25 * 25 * 25,
26 * 26 * 26 * 26,
27 * 27 * 27 * 27,
28 * 28 * 28 * 28,
29 * 29 * 29 * 29,
30 * 30 * 30 * 30,
31 * 31 * 31 * 31,
32 * 32 * 32 * 32,
33 * 33 * 33,
34 * 34 * 34,
35 * 35 * 35,
36 * 36 * 36
];
String toDebugString() {
return "Int64[_l=$_l, _m=$_m, _h=$_h]";
}
/**
* Constructs an [Int64] with a given bitwise representation. No validation
* is performed.
*/
Int64._bits(int this._l, int this._m, int this._h);
/**
* Constructs an [Int64] with the same value as an existing [Int64].
*/
Int64._copy(Int64 other)
: _l = other._l,
_m = other._m,
_h = other._h;
// Determine whether the platform supports ints greater than 2^53
// without loss of precision.
static bool _haveBigIntsCached = null;
static bool get _haveBigInts {
if (_haveBigIntsCached == null) {
var x = 9007199254740992;
// Defeat compile-time constant folding.
if (2 + 2 != 4) {
x = 0;
}
var y = x + 1;
var same = y == x;
_haveBigIntsCached = !same;
}
return _haveBigIntsCached;
}
String _hexDigit(int digit) => "0123456789ABCDEF"[digit];
// Implementation of '~/' and '%'.
// Note: mutates [this].
void _negate() {
int neg0 = (~_l + 1) & _MASK;
int neg1 = (~_m + (neg0 == 0 ? 1 : 0)) & _MASK;
int neg2 = (~_h + ((neg0 == 0 && neg1 == 0) ? 1 : 0)) & _MASK2;
_l = neg0;
_m = neg1;
_h = neg2;
}
// Note: mutates [this].
void _setBit(int bit) {
if (bit < _BITS) {
_l |= 0x1 << bit;
} else if (bit < _BITS01) {
_m |= 0x1 << (bit - _BITS);
} else {
_h |= 0x1 << (bit - _BITS01);
}
}
// Note: mutates [this].
void _toShru1() {
int a2 = _h;
int a1 = _m;
int a0 = _l;
_h = a2 >> 1;
_m = (a1 >> 1) | ((a2 & 0x1) << (_BITS - 1));
_l = (a0 >> 1) | ((a1 & 0x1) << (_BITS - 1));
}
// Work around dart2js bugs with negative arguments to '>>' operator.
static int _shiftRight(int x, int n) {
if (x >= 0) {
return x >> n;
} else {
int shifted = x >> n;
if (shifted >= 0x80000000) {
shifted -= 4294967296;
}
return shifted;
}
}
/**
* Attempt to subtract b from a if a >= b:
*
* if (a >= b) {
* a -= b;
* return true;
* } else {
* return false;
* }
*/
// Note: mutates [a].
static bool _trialSubtract(Int64 a, Int64 b) {
// Early exit.
int sum2 = a._h - b._h;
if (sum2 < 0) {
return false;
}
int sum0 = a._l - b._l;
int sum1 = a._m - b._m + _shiftRight(sum0, _BITS);
sum2 += _shiftRight(sum1, _BITS);
if (sum2 < 0) {
return false;
}
a._l = sum0 & _MASK;
a._m = sum1 & _MASK;
a._h = sum2 & _MASK2;
return true;
}
// Note: mutates [a] via _trialSubtract.
static Int64 _divModHelper(Int64 a, Int64 b,
bool negative, bool aIsNegative, bool aIsMinValue,
bool computeRemainder) {
// Align the leading one bits of a and b by shifting b left.
int shift = b.numberOfLeadingZeros() - a.numberOfLeadingZeros();
Int64 bshift = b << shift;
// Quotient must be a new instance since we mutate it.
Int64 quotient = new Int64();
while (shift >= 0) {
bool gte = _trialSubtract(a, bshift);
if (gte) {
quotient._setBit(shift);
if (a.isZero) {
break;
}
}
bshift._toShru1();
shift--;
}
if (negative) {
quotient._negate();
}
if (computeRemainder) {
if (aIsNegative) {
_remainder = -a;
if (aIsMinValue) {
_remainder = _remainder - ONE;
}
} else {
_remainder = a;
}
}
return quotient;
}
Int64 _divModByMinValue(bool computeRemainder) {
// MIN_VALUE / MIN_VALUE == 1, remainder = 0
// (x != MIN_VALUE) / MIN_VALUE == 0, remainder == x
if (isMinValue) {
if (computeRemainder) {
_remainder = ZERO;
}
return ONE;
}
if (computeRemainder) {
_remainder = this;
}
return ZERO;
}
/**
* this &= ((1L << bits) - 1)
*/
// Note: mutates [this].
Int64 _maskRight(int bits) {
int b0, b1, b2;
if (bits <= _BITS) {
b0 = _l & ((1 << bits) - 1);
b1 = b2 = 0;
} else if (bits <= _BITS01) {
b0 = _l;
b1 = _m & ((1 << (bits - _BITS)) - 1);
b2 = 0;
} else {
b0 = _l;
b1 = _m;
b2 = _h & ((1 << (bits - _BITS01)) - 1);
}
_l = b0;
_m = b1;
_h = b2;
}
static Int64 _divModByShift(Int64 a, int bpower, bool negative, bool aIsCopy,
bool aIsNegative, bool computeRemainder) {
Int64 c = a >> bpower;
if (negative) {
c._negate();
}
if (computeRemainder) {
if (!aIsCopy) {
a = new Int64._copy(a);
}
a._maskRight(bpower);
if (aIsNegative) {
a._negate();
}
_remainder = a;
}
return c;
}
/**
* Return the exact log base 2 of this, or -1 if this is not a power of two.
*/
int _powerOfTwo() {
// Power of two or 0.
int l = _l;
if ((l & (l - 1)) != 0) {
return -1;
}
int m = _m;
if ((m & (m - 1)) != 0) {
return -1;
}
int h = _h;
if ((h & (h - 1)) != 0) {
return -1;
}
if (h == 0 && m == 0 && l == 0) {
return -1;
}
if (h == 0 && m == 0 && l != 0) {
return Int32._numberOfTrailingZeros(l);
}
if (h == 0 && m != 0 && l == 0) {
return Int32._numberOfTrailingZeros(m) + _BITS;
}
if (h != 0 && m == 0 && l == 0) {
return Int32._numberOfTrailingZeros(h) + _BITS01;
}
return -1;
}
static Int64 _divMod(Int64 a, Int64 b, bool computeRemainder) {
if (b.isZero) {
throw new IntegerDivisionByZeroException();
}
if (a.isZero) {
if (computeRemainder) {
_remainder = ZERO;
}
return ZERO;
}
// MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0.
if (b.isMinValue) {
return a._divModByMinValue(computeRemainder);
}
// Normalize b to abs(b), keeping track of the parity in 'negative'.
// We can do this because we have already ensured that b != MIN_VALUE.
bool negative = false;
if (b.isNegative) {
b = -b;
negative = !negative;
}
// If b == 2^n, bpower will be n, otherwise it will be -1.
int bpower = b._powerOfTwo();
// True if the original value of a is negative.
bool aIsNegative = false;
// True if the original value of a is Int64.MIN_VALUE.
bool aIsMinValue = false;
/*
* Normalize a to a positive value, keeping track of the sign change in
* 'negative' (which tracks the sign of both a and b and is used to
* determine the sign of the quotient) and 'aIsNegative' (which is used to
* determine the sign of the remainder).
*
* For all values of a except MIN_VALUE, we can just negate a and modify
* negative and aIsNegative appropriately. When a == MIN_VALUE, negation is
* not possible without overflowing 64 bits, so instead of computing
* abs(MIN_VALUE) / abs(b) we compute (abs(MIN_VALUE) - 1) / abs(b). The
* only circumstance under which these quotients differ is when b is a power
* of two, which will divide abs(MIN_VALUE) == 2^64 exactly. In this case,
* we can get the proper result by shifting MIN_VALUE in unsigned fashion.
*
* We make a single copy of a before the first operation that needs to
* modify its value.
*/
bool aIsCopy = false;
if (a.isMinValue) {
aIsMinValue = true;
aIsNegative = true;
// If b is not a power of two, treat -a as MAX_VALUE (instead of the
// actual value (MAX_VALUE + 1)).
if (bpower == -1) {
a = new Int64._copy(MAX_VALUE);
aIsCopy = true;
negative = !negative;
} else {
// Signed shift of MIN_VALUE produces the right answer.
Int64 c = a >> bpower;
if (negative) {
c._negate();
}
if (computeRemainder) {
_remainder = ZERO;
}
return c;
}
} else if (a.isNegative) {
aIsNegative = true;
a = -a;
aIsCopy = true;
negative = !negative;
}
// Now both a and b are non-negative.
// If b is a power of two, just shift.
if (bpower != -1) {
return _divModByShift(a, bpower, negative, aIsCopy, aIsNegative,
computeRemainder);
}
// If a < b, the quotient is 0 and the remainder is a.
if (a < b) {
if (computeRemainder) {
if (aIsNegative) {
_remainder = -a;
} else {
_remainder = aIsCopy ? a : new Int64._copy(a);
}
}
return ZERO;
}
// Generate the quotient using bit-at-a-time long division.
return _divModHelper(aIsCopy ? a : new Int64._copy(a), b, negative,
aIsNegative, aIsMinValue, computeRemainder);
}
}