Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1342)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: pkg/fixnum/lib/src/int64.dart

Issue 1909043004: Moved pkg/fixnum to github (Closed) Base URL: https://github.com/dart-lang/sdk.git@master
Patch Set: Created 4 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « pkg/fixnum/lib/src/int32.dart ('k') | pkg/fixnum/lib/src/intx.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: pkg/fixnum/lib/src/int64.dart
diff --git a/pkg/fixnum/lib/src/int64.dart b/pkg/fixnum/lib/src/int64.dart
deleted file mode 100644
index 7770eb17354c938163ca8cbac7a865be3cf01e60..0000000000000000000000000000000000000000
--- a/pkg/fixnum/lib/src/int64.dart
+++ /dev/null
@@ -1,1002 +0,0 @@
-// 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].
- //
- // The values being assigned to _l, _m and _h in initialization are masked to
- // force them into the above ranges. Sometimes we know that the value is a
- // small non-negative integer but the dart2js compiler can't infer that, so a
- // few of the masking operations are not needed for correctness but are
- // helpful for dart2js code quality.
-
- final int _l, _m, _h;
-
- // 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 = 1 << _SIGN_BIT;
-
- /**
- * The maximum positive value attainable by an [Int64], namely
- * 9,223,372,036,854,775,807.
- */
- static const Int64 MAX_VALUE = const Int64._bits(_MASK, _MASK, _MASK2 >> 1);
-
- /**
- * The minimum positive value attainable by an [Int64], namely
- * -9,223,372,036,854,775,808.
- */
- static const Int64 MIN_VALUE = const Int64._bits(0, 0, _SIGN_BIT_MASK);
-
- /**
- * An [Int64] constant equal to 0.
- */
- static const Int64 ZERO = const Int64._bits(0, 0, 0);
-
- /**
- * An [Int64] constant equal to 1.
- */
- static const Int64 ONE = const Int64._bits(1, 0, 0);
-
- /**
- * An [Int64] constant equal to 2.
- */
- static const Int64 TWO = const Int64._bits(2, 0, 0);
-
- /**
- * Constructs an [Int64] with a given bitwise representation. No validation
- * is performed.
- */
- const Int64._bits(int this._l, int this._m, int this._h);
-
- /**
- * Parses a [String] in a given [radix] between 2 and 36 and returns an
- * [Int64].
- */
- static Int64 parseRadix(String s, int radix) {
- return _parseRadix(s, Int32._validateRadix(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 FormatException("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 & d0;
-
- d1 = d1 * radix + carry;
- carry = d1 >> _BITS;
- d1 = _MASK & d1;
-
- d2 = d2 * radix + carry;
- d2 = _MASK2 & d2;
- }
-
- if (negative) return _negate(d0, d1, d2);
-
- return Int64._masked(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] with a given [int] value; zero by default.
- */
- factory Int64([int value=0]) {
- int v0 = 0, v1 = 0, v2 = 0;
- bool negative = false;
- if (value < 0) {
- negative = true;
- value = -value - 1;
- }
- // Avoid using bitwise operations that in JavaScript coerce their input to
- // 32 bits.
- v2 = value ~/ 17592186044416; // 2^44
- value -= v2 * 17592186044416;
- v1 = value ~/ 4194304; // 2^22
- value -= v1 * 4194304;
- v0 = value;
-
- if (negative) {
- v0 = ~v0;
- v1 = ~v1;
- v2 = ~v2;
- }
- return Int64._masked(v0, v1, v2);
- }
-
- 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 = _MASK & bottom;
- int d1 = ((0xfff & top) << 10) | (0x3ff & (bottom >> _BITS));
- int d2 = _MASK2 & (top >> 12);
- return Int64._masked(d0, d1, d2);
- }
-
- // Returns the [Int64] representation of the specified value. Throws
- // [ArgumentError] for non-integer arguments.
- static Int64 _promote(value) {
- if (value is Int64) {
- return value;
- } else if (value is int) {
- return new Int64(value);
- } else if (value is Int32) {
- return value.toInt64();
- }
- throw new ArgumentError.value(value);
- }
-
- Int64 operator +(other) {
- Int64 o = _promote(other);
- int sum0 = _l + o._l;
- int sum1 = _m + o._m + (sum0 >> _BITS);
- int sum2 = _h + o._h + (sum1 >> _BITS);
- return Int64._masked(sum0, sum1, sum2);
- }
-
- Int64 operator -(other) {
- Int64 o = _promote(other);
- return _sub(_l, _m, _h, o._l, o._m, o._h);
- }
-
- Int64 operator -() => _negate(_l, _m, _h);
-
- 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;
- c2 += c1 >> _BITS;
-
- return Int64._masked(c0, c1, c2);
- }
-
- Int64 operator %(other) => _divide(this, other, _RETURN_MOD);
-
- Int64 operator ~/(other) => _divide(this, other, _RETURN_DIV);
-
- Int64 remainder(other) => _divide(this, other, _RETURN_REM);
-
- Int64 operator &(other) {
- Int64 o = _promote(other);
- int a0 = _l & o._l;
- int a1 = _m & o._m;
- int a2 = _h & o._h;
- return Int64._masked(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 Int64._masked(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 Int64._masked(a0, a1, a2);
- }
-
- Int64 operator ~() {
- return Int64._masked(~_l, ~_m, ~_h);
- }
-
- Int64 operator <<(int n) {
- if (n < 0) {
- throw new ArgumentError.value(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 Int64._masked(res0, res1, res2);
- }
-
- Int64 operator >>(int n) {
- if (n < 0) {
- throw new ArgumentError.value(n);
- }
- n &= 63;
-
- int res0, res1, res2;
-
- // Sign extend h(a).
- int a2 = _h;
- bool negative = (a2 & _SIGN_BIT_MASK) != 0;
- if (negative && _MASK > _MASK2) {
- // Add extra one bits on the left so the sign gets shifted into the wider
- // lower words.
- a2 += (_MASK - _MASK2);
- }
-
- 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 Int64._masked(res0, res1, res2);
- }
-
- Int64 shiftRightUnsigned(int n) {
- if (n < 0) {
- throw new ArgumentError.value(n);
- }
- n &= 63;
-
- int res0, res1, res2;
- int a2 = _MASK2 & _h; // 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 Int64._masked(res0, res1, res2);
- }
-
- /**
- * 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) {
- if (_h == 0 && _m == 0) return _l == other;
- // Since we know one of [_h] or [_m] is non-zero, if [other] fits in the
- // low word then it can't be numerically equal.
- if ((_MASK & other) == other) return false;
- o = new Int64(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(IntX other) =>_compareTo(other);
-
- int _compareTo(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) => _compareTo(other) < 0;
- bool operator <=(other) => _compareTo(other) <= 0;
- bool operator >(other) => this._compareTo(other) > 0;
- bool operator >=(other) => _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 & _SIGN_BIT_MASK) != 0;
- bool get isOdd => (_l & 0x1) == 1;
- bool get isZero => _h == 0 && _m == 0 && _l == 0;
-
- int get bitLength {
- if (isZero) return 0;
- int a0 = _l, a1 = _m, a2 = _h;
- if (isNegative) {
- a0 = _MASK & ~a0;
- a1 = _MASK & ~a1;
- a2 = _MASK2 & ~a2;
- }
- if (a2 != 0) return _BITS01 + a2.bitLength;
- if (a1 != 0) return _BITS + a1.bitLength;
- return a0.bitLength;
- }
-
- /**
- * Returns a hash code based on all the bits of this [Int64].
- */
- int get hashCode {
- // TODO(sra): Should we ensure that hashCode values match corresponding int?
- // i.e. should `new Int64(x).hashCode == x.hashCode`?
- int bottom = ((_m & 0x3ff) << _BITS) | _l;
- int top = (_h << 12) | ((_m >> 10) & 0xfff);
- return bottom ^ top;
- }
-
- Int64 abs() {
- return this.isNegative ? -this : this;
- }
-
- Int64 clamp(lowerLimit, upperLimit) {
- Int64 lower = _promote(lowerLimit);
- Int64 upper = _promote(upperLimit);
- if (this < lower) return lower;
- if (this > upper) return upper;
- return 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;
- }
-
- Int64 toSigned(int width) {
- if (width < 1 || width > 64) throw new RangeError.range(width, 1, 64);
- if (width > _BITS01) {
- return Int64._masked(_l, _m, _h.toSigned(width - _BITS01));
- } else if (width > _BITS) {
- int m = _m.toSigned(width - _BITS);
- return m.isNegative
- ? Int64._masked(_l, m, _MASK2)
- : Int64._masked(_l, m, 0); // Masking for type inferrer.
- } else {
- int l = _l.toSigned(width);
- return l.isNegative
- ? Int64._masked(l, _MASK, _MASK2)
- : Int64._masked(l, 0, 0); // Masking for type inferrer.
- }
- }
-
- Int64 toUnsigned(int width) {
- if (width < 0 || width > 64) throw new RangeError.range(width, 0, 64);
- if (width > _BITS01) {
- int h = _h.toUnsigned(width - _BITS01);
- return Int64._masked(_l, _m, h);
- } else if (width > _BITS) {
- int m = _m.toUnsigned(width - _BITS);
- return Int64._masked(_l, m, 0);
- } else {
- int l = _l.toUnsigned(width);
- return Int64._masked(l, 0, 0);
- }
- }
-
- 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;
- }
-
- double toDouble() => toInt().toDouble();
-
- int toInt() {
- int l = _l;
- int m = _m;
- int h = _h;
- // In the sum we add least significant to most significant so that in
- // JavaScript double arithmetic rounding occurs on only the last addition.
- if ((_h & _SIGN_BIT_MASK) != 0) {
- l = _MASK & ~_l;
- m = _MASK & ~_m;
- h = _MASK2 & ~_h;
- return -((1 + l) + (4194304 * m) + (17592186044416 * h));
- } else {
- return l + (4194304 * m) + (17592186044416 * h);
- }
- }
-
- /**
- * Returns an [Int32] containing the low 32 bits of this [Int64].
- */
- Int32 toInt32() {
- return new Int32(((_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() {
- if (isZero) return "0";
- Int64 x = this;
- String hexStr = "";
- while (!x.isZero) {
- int digit = x._l & 0xf;
- hexStr = "${_hexDigit(digit)}$hexStr";
- x = x.shiftRightUnsigned(4);
- }
- return hexStr;
- }
-
- String toRadixString(int radix) {
- return _toRadixString(Int32._validateRadix(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(chunk3 == "");
- 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]";
- }
-
-
- static Int64 _masked(int a0, int a1, int a2) =>
- new Int64._bits(_MASK & a0, _MASK & a1, _MASK2 & a2);
-
- static Int64 _sub(int a0, int a1, int a2, int b0, int b1, int b2) {
- int diff0 = a0 - b0;
- int diff1 = a1 - b1 - ((diff0 >> _BITS) & 1);
- int diff2 = a2 - b2 - ((diff1 >> _BITS) & 1);
- return _masked(diff0, diff1, diff2);
- }
-
- static Int64 _negate(int b0, int b1, int b2) {
- return _sub(0, 0, 0, b0, b1, b2);
- }
-
- String _hexDigit(int digit) => "0123456789ABCDEF"[digit];
-
- // 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;
- }
- }
-
-
- // Implementation of '~/', '%' and 'remainder'.
-
- static Int64 _divide(Int64 a, other, int what) {
- Int64 b = _promote(other);
- if (b.isZero) {
- throw new IntegerDivisionByZeroException();
- }
- if (a.isZero) return ZERO;
-
- bool aNeg = a.isNegative;
- bool bNeg = b.isNegative;
- a = a.abs();
- b = b.abs();
-
- int a0 = a._l;
- int a1 = a._m;
- int a2 = a._h;
-
- int b0 = b._l;
- int b1 = b._m;
- int b2 = b._h;
- return _divideHelper(a0, a1, a2, aNeg, b0, b1, b2, bNeg, what);
- }
-
- static const _RETURN_DIV = 1;
- static const _RETURN_REM = 2;
- static const _RETURN_MOD = 3;
-
- static _divideHelper(
- // up to 64 bits unsigned in a2/a1/a0 and b2/b1/b0
- int a0, int a1, int a2, bool aNeg, // input A.
- int b0, int b1, int b2, bool bNeg, // input B.
- int what) {
- int q0 = 0, q1 = 0, q2 = 0; // result Q.
- int r0 = 0, r1 = 0, r2 = 0; // result R.
-
- if (b2 == 0 && b1 == 0 && b0 < (1 << (30 - _BITS))) {
- // Small divisor can be handled by single-digit division within Smi range.
- //
- // Handling small divisors here helps the estimate version below by
- // handling cases where the estimate is off by more than a small amount.
-
- q2 = a2 ~/ b0;
- int carry = a2 - q2 * b0;
- int d1 = a1 + (carry << _BITS);
- q1 = d1 ~/ b0;
- carry = d1 - q1 * b0;
- int d0 = a0 + (carry << _BITS);
- q0 = d0 ~/ b0;
- r0 = d0 - q0 * b0;
- } else {
- // Approximate Q = A ~/ B and R = A - Q * B using doubles.
-
- // The floating point approximation is very close to the correct value
- // when floor(A/B) fits in fewer that 53 bits.
-
- // We use double arithmetic for intermediate values. Double arithmetic on
- // non-negative values is exact under the following conditions:
- //
- // - The values are integer values that fit in 53 bits.
- // - Dividing by powers of two (adjusts exponent only).
- // - Floor (zeroes bits with fractional weight).
-
- const double K2 = 17592186044416.0; // 2^44
- const double K1 = 4194304.0; // 2^22
-
- // Approximate double values for [a] and [b].
- double ad = a0 + K1 * a1 + K2 * a2;
- double bd = b0 + K1 * b1 + K2 * b2;
- // Approximate quotient.
- double qd = (ad / bd).floorToDouble();
-
- // Extract components of [qd] using double arithmetic.
- double q2d = (qd / K2).floorToDouble();
- qd = qd - K2 * q2d;
- double q1d = (qd / K1).floorToDouble();
- double q0d = qd - K1 * q1d;
- q2 = q2d.toInt();
- q1 = q1d.toInt();
- q0 = q0d.toInt();
-
- assert(q0 + K1 * q1 + K2 * q2 == (ad / bd).floorToDouble());
- assert(q2 == 0 || b2 == 0); // Q and B can't both be big since Q*B <= A.
-
- // P = Q * B, using doubles to hold intermediates.
- // We don't need all partial sums since Q*B <= A.
- double p0d = q0d * b0;
- double p0carry = (p0d / K1).floorToDouble();
- p0d = p0d - p0carry * K1;
- double p1d = q1d * b0 + q0d * b1 + p0carry;
- double p1carry = (p1d / K1).floorToDouble();
- p1d = p1d - p1carry * K1;
- double p2d = q2d * b0 + q1d * b1 + q0d * b2 + p1carry;
- assert(p2d <= _MASK2); // No partial sum overflow.
-
- // R = A - P
- int diff0 = a0 - p0d.toInt();
- int diff1 = a1 - p1d.toInt() - ((diff0 >> _BITS) & 1);
- int diff2 = a2 - p2d.toInt() - ((diff1 >> _BITS) & 1);
- r0 = _MASK & diff0;
- r1 = _MASK & diff1;
- r2 = _MASK2 & diff2;
-
- // while (R < 0 || R >= B)
- // adjust R towards [0, B)
- while (
- r2 >= _SIGN_BIT_MASK ||
- r2 > b2 ||
- (r2 == b2 && (r1 > b1 || (r1 == b1 && r0 >= b0)))) {
- // Direction multiplier for adjustment.
- int m = (r2 & _SIGN_BIT_MASK) == 0 ? 1 : -1;
- // R = R - B or R = R + B
- int d0 = r0 - m * b0;
- int d1 = r1 - m * (b1 + ((d0 >> _BITS) & 1));
- int d2 = r2 - m * (b2 + ((d1 >> _BITS) & 1));
- r0 = _MASK & d0;
- r1 = _MASK & d1;
- r2 = _MASK2 & d2;
-
- // Q = Q + 1 or Q = Q - 1
- d0 = q0 + m;
- d1 = q1 + m * ((d0 >> _BITS) & 1);
- d2 = q2 + m * ((d1 >> _BITS) & 1);
- q0 = _MASK & d0;
- q1 = _MASK & d1;
- q2 = _MASK2 & d2;
- }
- }
-
- // 0 <= R < B
- assert(Int64.ZERO <= new Int64._bits(r0, r1, r2));
- assert(r2 < b2 || // Handles case where B = -(MIN_VALUE)
- new Int64._bits(r0, r1, r2) < new Int64._bits(b0, b1, b2));
-
- assert(what == _RETURN_DIV || what == _RETURN_MOD || what == _RETURN_REM);
- if (what == _RETURN_DIV) {
- if (aNeg != bNeg) return _negate(q0, q1, q2);
- return Int64._masked(q0, q1, q2); // Masking for type inferrer.
- }
-
- if (!aNeg) {
- return Int64._masked(r0, r1, r2); // Masking for type inferrer.
- }
-
- if (what == _RETURN_MOD) {
- if (r0 == 0 && r1 == 0 && r2 == 0) {
- return ZERO;
- } else {
- return _sub(b0, b1, b2, r0, r1, r2);
- }
- } else {
- return _negate(r0, r1, r2);
- }
- }
-}
« no previous file with comments | « pkg/fixnum/lib/src/int32.dart ('k') | pkg/fixnum/lib/src/intx.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698