New divide algorithm for Int64, final fields

pkg/fixnum/lib/src/int64.dart

 // 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.
+  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
 
-  // 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;
-  }
+  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 Int64 get MIN_VALUE {
-    if (_MIN_VALUE == null) {
-      _MIN_VALUE = new Int64._bits(0, 0, _SIGN_BIT_MASK);
-    }
-    return _MIN_VALUE;
-  }
+  static const Int64 MIN_VALUE = const Int64._bits(0, 0, _SIGN_BIT_MASK);
 
   /**
    * An [Int64] constant equal to 0.
    */
-  static Int64 get ZERO {
-    if (_ZERO == null) {
-      _ZERO = new Int64();
-    }
-    return _ZERO;
-  }
+  static const Int64 ZERO = const Int64._bits(0, 0, 0);
 
   /**
    * An [Int64] constant equal to 1.
    */
-  static Int64 get ONE {
-    if (_ONE == null) {
-      _ONE = new Int64._bits(1, 0, 0);
-    }
-    return _ONE;
-  }
+  static const Int64 ONE = const Int64._bits(1, 0, 0);
 
   /**
    * An [Int64] constant equal to 2.
    */
-  static Int64 get TWO {
-    if (_TWO == null) {
-      _TWO = new Int64._bits(2, 0, 0);
-    }
-    return _TWO;
-  }
+  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);
@@ skipping 11 matching lines @@
       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 = _MASK & d0;
 
       d1 = d1 * radix + carry;
       carry = d1 >> _BITS;
-      d1 &= _MASK;
+      d1 = _MASK & d1;;
 
       d2 = d2 * radix + carry;
-      d2 &= _MASK2;
+      d2 = _MASK2 & d2;
     }
 
-    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;
-    }
+    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] equal to 0.
    */
   Int64() : _l = 0, _m = 0, _h = 0;
 
   /**
    * Constructs an [Int64] with a given [int] value.
    */
-  Int64.fromInt(int value) {
+  factory Int64.fromInt(int value) {
+    int v0 = 0, v1 = 0, v2 = 0;
     bool negative = false;
     if (value < 0) {
       negative = true;
       value = -value - 1;
     }
     if (_haveBigInts) {
-      _l = value & _MASK;
-      _m = (value >> _BITS) & _MASK;
-      _h = (value >> _BITS01) & _MASK2;
+      v0 = _MASK & value;
+      v1 = _MASK & (value >> _BITS);
+      v2 = _MASK2 & (value >> _BITS01);
     } 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;
+      v2 = value ~/ 17592186044416; // 2^44
+      value -= v2 * 17592186044416;
+      v1 = value ~/ 4194304; // 2^22
+      value -= v1 * 4194304;
+      v0 = value;
     }
 
     if (negative) {
-      _l = ~_l & _MASK;
-      _m = ~_m & _MASK;
-      _h = ~_h & _MASK2;
+      v0 = _MASK & ~v0;
+      v1 = _MASK & ~v1;
+      v2 = _MASK2 & ~v2;
     }
+    return new Int64._bits(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;
@@ skipping 37 matching lines @@
     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) {
+  static 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);
+    int sum1 = _m + o._m + (sum0 >> _BITS);
+    int sum2 = _h + o._h + (sum1 >> _BITS);
 
-    Int64 result = new Int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK2);
-    return result;
+    return new Int64._bits(_MASK & sum0, _MASK & sum1, _MASK2 & sum2);

[Chris Bracken, 2013/09/17 01:04:11]

return _masked(sum0, sum1, sum2)

[sra1, 2013/09/17 05:04:36]

Done.

   }
 
   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;
+    return _sub(_l, _m, _h, o._l, o._m, o._h);
   }
 
-  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 -() => _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;
@@ skipping 65 matching lines @@
     // 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) => _divide(this, other, _RETURN_MOD);
 
-  Int64 operator ~/(other) => _divMod(this, _promote(other), false);
+  Int64 operator ~/(other) => _divide(this, other, _RETURN_DIV);
 
-  // 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 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 ~() {
-    var result = new Int64._bits((~_l) & _MASK, (~_m) & _MASK, (~_h) & _MASK2);
-    return result;
+    return new Int64._bits(_MASK & ~_l, _MASK & ~_m, _MASK2 & ~_h);

[Chris Bracken, 2013/09/17 01:04:11]

_masked(~l,...)

[sra1, 2013/09/17 05:04:36]

Done.

   }
 
   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);
+    return new Int64._bits(_MASK & res0, _MASK & res1, _MASK2 & res2);

[Chris Bracken, 2013/09/17 01:04:11]

_masked(res0,...)

[sra1, 2013/09/17 05:04:36]

Done.

   }
 
   Int64 operator >>(int n) {
     if (n < 0) {
       throw new ArgumentError(n);
     }
     n &= 63;
 
     int res0, res1, res2;
 
@@ skipping 20 matching lines @@
       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);
+    return new Int64._bits(_MASK & res0, _MASK & res1, _MASK2 & res2);

[Chris Bracken, 2013/09/17 01:04:11]

_masked(res0,...)

[sra1, 2013/09/17 05:04:36]

Done.

   }
 
   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.
+    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 new Int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK2);
+    return new Int64._bits(_MASK & res0, _MASK & res1, _MASK2 & res2);

[Chris Bracken, 2013/09/17 01:04:11]

_masked(res0,...)

[sra1, 2013/09/17 05:04:36]

Done.

   }
 
   /**
    * 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;
       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;
   }
 
@@ skipping 310 matching lines @@
       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);
+
+  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);
+  }
 
   /**
    * 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
@@ skipping 11 matching lines @@
       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) {
+
+  static Int64 _divide(Int64 a, other, int what) {
+    Int64 b = _promote(other);
     if (b.isZero) {
       throw new IntegerDivisionByZeroException();
     }
-    if (a.isZero) {
-      if (computeRemainder) {
-        _remainder = ZERO;
+    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.
+
+    val(x0,x1,x2) => x0 + 4194304 * x1 + 17592186044416 * x2;
+    demoS(x0,x1,x2) => '$x0 $x1 $x2 (${new Int64._bits(x0,x1,x2)})';
+    demo(x0,x1,x2) => '$x0 $x1 $x2 (${val(x0,x1,x2)})';
+
+    var splat;
+    splat = () {
+      print('divide   A ${demo(a0,a1,a2)}   B ${demo(b0,b1,b2)}');
+      splat = (){};
+    };

[Chris Bracken, 2013/09/17 01:04:11]

delete test code/prints

[sra1, 2013/09/17 05:04:36]

Done.

+
+    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;
+
+      // A = Q * B + R
+      if (new Int64._bits(a0, a1, a2) !=
+          new Int64._bits(q0, q1, q2) * new Int64._bits(b0, b1, b2) +
+          new Int64._bits(r0, r1, r2)) {
+
+        splat();
+
+        print('A($a0, $a1, $a2) == '
+            'Q($q0, $q1, $q2) * B($b0, $b1, $b2)} + R($r0, $r1, $r2)}');
+        print('${new Int64._bits(a0, a1, a2)} == '
+            '${new Int64._bits(q0, q1, q2)} * ${new Int64._bits(b0, b1, b2)} + '
+            '${new Int64._bits(r0, r1, r2)}');
+        print('${new Int64._bits(a0, a1, a2)} == \n'
+            '${new Int64._bits(q0, q1, q2) * new Int64._bits(b0, b1, b2)} + '
+            '${new Int64._bits(r0, r1, r2)}');
+
+        print('${val(a0, a1, a2)} == \n'
+            '${val(q0, q1, q2) * val(b0, b1, b2)} + '
+            '${val(r0, r1, r2)}');
+
+        assert(new Int64._bits(a0, a1, a2) ==
+            new Int64._bits(q0, q1, q2) * new Int64._bits(b0, b1, b2) +
+            new Int64._bits(r0, r1, r2));
       }
-      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;
+
+      // while (R < 0 || R >= B)
+      //  adjust R towards [0, B)
+      int tc = 1;
+      while (
+          r2 >= _SIGN_BIT_MASK ||
+          r2 > b2 ||
+          (r2 == b2 && (r1 > b1 || (r1 == b1 && r0 >= b0)))) {
+        splat();
+        print('  adjust $tc  R ${demoS(r0,r1,r2)}  >=  B ${demo(b0,b1,b2)}'
+            '   Q ${demo(q0,q1,q2)}');
+        if (++tc > 10) throw 123;
+        // 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;
       }
-    } 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);
+    }
+
+    // A = Q * B + R
+    if (new Int64._bits(a0, a1, a2) !=
+        new Int64._bits(q0, q1, q2) * new Int64._bits(b0, b1, b2) +
+        new Int64._bits(r0, r1, r2)) {
+
+      splat();
+
+      print('A($a0, $a1, $a2) == '
+          'Q($q0, $q1, $q2) * B($b0, $b1, $b2)} + R($r0, $r1, $r2)}');
+      print('${new Int64._bits(a0, a1, a2)} == '
+          '${new Int64._bits(q0, q1, q2)} * ${new Int64._bits(b0, b1, b2)} + '
+          '${new Int64._bits(r0, r1, r2)}');
+      print('${new Int64._bits(a0, a1, a2)} == \n'
+          '${new Int64._bits(q0, q1, q2) * new Int64._bits(b0, b1, b2)} + '
+          '${new Int64._bits(r0, r1, r2)}');
+
+      print('${val(a0, a1, a2)} == \n'
+          '${val(q0, q1, q2) * val(b0, b1, b2)} + '
+          '${val(r0, r1, r2)}');
+
+      assert(new Int64._bits(a0, a1, a2) ==
+          new Int64._bits(q0, q1, q2) * new Int64._bits(b0, b1, b2) +
+          new Int64._bits(r0, r1, r2));
+    }
+
+    // 0 <= R < B
+    assert(Int64.ZERO <= new Int64._bits(r0, r1, r2));
+    assert(val(r0, r1, r2) < val(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) {
+      return _sub(b0, b1, b2, r0, r1, r2);

[Chris Bracken, 2013/09/17 01:04:11]

Return 0 where r1==r2==r3==0

[sra1, 2013/09/17 19:42:27]

Done.

+    } else {
+      return _negate(r0, r1, r2);
+    }
   }
 }