// 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].
  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 = 524288; // 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) {
    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 & 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 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] 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;
    }
    if (_haveBigInts) {
      v0 = _MASK & value;
      v1 = _MASK & (value >> _BITS);
      v2 = _MASK2 & (value >> _BITS01);
    } else {
      // Avoid using bitwise operations that 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 = _MASK & ~v0;
      v1 = _MASK & ~v1;
      v2 = _MASK2 & ~v2;
    }
    return new Int64._bits(v0, v1, v2);
  }

  /**
   * Constructs an [Int64] with a given [int] value.
   */
  @deprecated
  factory Int64.fromInt(int value) => new Int64(value);

  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.
  static Int64 _promote(val) {
    if (val is Int64) {
      return val;
    } else if (val is int) {
      return new Int64(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 + (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;
    c0 &= _MASK;
    c2 += c1 >> _BITS;
    c1 &= _MASK;
    c2 &= _MASK2;

    return new Int64._bits(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 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 ~() {
    return Int64._masked(~_l, ~_m, ~_h);
  }

  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 Int64._masked(res0, res1, res2);
  }

  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 && _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(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(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 & _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 ArgumentError(width);
    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) :
          new Int64._bits(_l, m, 0);
    } else {
      int l = _l.toSigned(width);
      return l.isNegative ? Int64._masked(l, _MASK, _MASK2) :
          new Int64._bits(l, 0, 0);
    }
  }

  Int64 toUnsigned(int width) {
    if (width < 0 || width > 64) throw new ArgumentError(width);
    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;
    bool negative = false;
    if ((_h & _SIGN_BIT_MASK) != 0) {
      l = _MASK & ~_l;
      m = _MASK & ~_m;
      h = _MASK2 & ~_h;
      negative = true;
    }

    if (_haveBigInts) {
      int result = (h << _BITS01) | (m << _BITS) | l;
      return negative ? -result - 1 : result;
    } else {
      if (negative) {
        return -((l + 1) + (m * 4194304) + (h * 17592186044416));
      } else {
        return (l + (m * 4194304)) + (h * 17592186044416);
      }
    }
  }

  /**
   * 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 = "";
    Int64 digit_f = new Int64(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(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);
  }

  // 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];


  // 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 new Int64._bits(q0, q1, q2);
    }

    if (!aNeg) return new Int64._bits(r0, r1, r2);

    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);
    }
  }
}