| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 part of fixnum; | 5 part of fixnum; |
| 6 | 6 |
| 7 /** | 7 /** |
| 8 * An immutable 64-bit signed integer, in the range [-2^63, 2^63 - 1]. | 8 * An immutable 64-bit signed integer, in the range [-2^63, 2^63 - 1]. |
| 9 * Arithmetic operations may overflow in order to maintain this range. | 9 * Arithmetic operations may overflow in order to maintain this range. |
| 10 */ | 10 */ |
| 11 class int64 implements intx { | 11 class Int64 implements Intx { |
| 12 | 12 |
| 13 // A 64-bit integer is represented internally as three non-negative | 13 // A 64-bit integer is represented internally as three non-negative |
| 14 // integers, storing the 22 low, 22 middle, and 20 high bits of the | 14 // integers, storing the 22 low, 22 middle, and 20 high bits of the |
| 15 // 64-bit value. _l (low) and _m (middle) are in the range | 15 // 64-bit value. _l (low) and _m (middle) are in the range |
| 16 // [0, 2^22 - 1] and _h (high) is in the range [0, 2^20 - 1]. | 16 // [0, 2^22 - 1] and _h (high) is in the range [0, 2^20 - 1]. |
| 17 int _l, _m, _h; | 17 int _l, _m, _h; |
| 18 | 18 |
| 19 // Note: instances of int64 are immutable outside of this library, | 19 // Note: instances of [Int64] are immutable outside of this library, |
| 20 // therefore we may return a reference to an existing instance. | 20 // therefore we may return a reference to an existing instance. |
| 21 // We take care to perform mutation only on internally-generated | 21 // We take care to perform mutation only on internally-generated |
| 22 // instances before they are exposed to external code. | 22 // instances before they are exposed to external code. |
| 23 | 23 |
| 24 // Note: several functions require _BITS == 22 -- do not change this value. | 24 // Note: several functions require _BITS == 22 -- do not change this value. |
| 25 static const int _BITS = 22; | 25 static const int _BITS = 22; |
| 26 static const int _BITS01 = 44; // 2 * _BITS | 26 static const int _BITS01 = 44; // 2 * _BITS |
| 27 static const int _BITS2 = 20; // 64 - _BITS01 | 27 static const int _BITS2 = 20; // 64 - _BITS01 |
| 28 static const int _MASK = 4194303; // (1 << _BITS) - 1 | 28 static const int _MASK = 4194303; // (1 << _BITS) - 1 |
| 29 static const int _MASK_2 = 1048575; // (1 << _BITS2) - 1 | 29 static const int _MASK_2 = 1048575; // (1 << _BITS2) - 1 |
| 30 static const int _SIGN_BIT = 19; // _BITS2 - 1 | 30 static const int _SIGN_BIT = 19; // _BITS2 - 1 |
| 31 static const int _SIGN_BIT_VALUE = 524288; // 1 << _SIGN_BIT | 31 static const int _SIGN_BIT_VALUE = 524288; // 1 << _SIGN_BIT |
| 32 | 32 |
| 33 // Cached constants | 33 // Cached constants |
| 34 static int64 _MAX_VALUE; | 34 static Int64 _MAX_VALUE; |
| 35 static int64 _MIN_VALUE; | 35 static Int64 _MIN_VALUE; |
| 36 static int64 _ZERO; | 36 static Int64 _ZERO; |
| 37 static int64 _ONE; | 37 static Int64 _ONE; |
| 38 static int64 _TWO; | 38 static Int64 _TWO; |
| 39 | 39 |
| 40 // Precompute the radix strings for MIN_VALUE to avoid the problem | 40 // Precompute the radix strings for MIN_VALUE to avoid the problem |
| 41 // of overflow of -MIN_VALUE. | 41 // of overflow of -MIN_VALUE. |
| 42 static List<String> _minValues = const <String>[ | 42 static List<String> _minValues = const <String>[ |
| 43 null, null, | 43 null, null, |
| 44 "-1000000000000000000000000000000000000000000000000000000000000000", // 2 | 44 "-1000000000000000000000000000000000000000000000000000000000000000", // 2 |
| 45 "-2021110011022210012102010021220101220222", // base 3 | 45 "-2021110011022210012102010021220101220222", // base 3 |
| 46 "-20000000000000000000000000000000", // base 4 | 46 "-20000000000000000000000000000000", // base 4 |
| 47 "-1104332401304422434310311213", // base 5 | 47 "-1104332401304422434310311213", // base 5 |
| 48 "-1540241003031030222122212", // base 6 | 48 "-1540241003031030222122212", // base 6 |
| 49 "-22341010611245052052301", // base 7 | 49 "-22341010611245052052301", // base 7 |
| 50 "-1000000000000000000000", // base 8 | 50 "-1000000000000000000000", // base 8 |
| 51 "-67404283172107811828", // base 9 | 51 "-67404283172107811828", // base 9 |
| 52 "-9223372036854775808", // base 10 | 52 "-9223372036854775808", // base 10 |
| 53 "-1728002635214590698", // base 11 | 53 "-1728002635214590698", // base 11 |
| 54 "-41A792678515120368", // base 12 | 54 "-41A792678515120368", // base 12 |
| 55 "-10B269549075433C38", // base 13 | 55 "-10B269549075433C38", // base 13 |
| 56 "-4340724C6C71DC7A8", // base 14 | 56 "-4340724C6C71DC7A8", // base 14 |
| 57 "-160E2AD3246366808", // base 15 | 57 "-160E2AD3246366808", // base 15 |
| 58 "-8000000000000000" // base 16 | 58 "-8000000000000000" // base 16 |
| 59 ]; | 59 ]; |
| 60 | 60 |
| 61 // The remainder of the last divide operation. | 61 // The remainder of the last divide operation. |
| 62 static int64 _remainder; | 62 static Int64 _remainder; |
| 63 | 63 |
| 64 /** | 64 /** |
| 65 * The maximum positive value attainable by an [int64], namely | 65 * The maximum positive value attainable by an [Int64], namely |
| 66 * 9,223,372,036,854,775,807. | 66 * 9,223,372,036,854,775,807. |
| 67 */ | 67 */ |
| 68 static int64 get MAX_VALUE { | 68 static Int64 get MAX_VALUE { |
| 69 if (_MAX_VALUE == null) { | 69 if (_MAX_VALUE == null) { |
| 70 _MAX_VALUE = new int64._bits(_MASK, _MASK, _MASK_2 >> 1); | 70 _MAX_VALUE = new Int64._bits(_MASK, _MASK, _MASK_2 >> 1); |
| 71 } | 71 } |
| 72 return _MAX_VALUE; | 72 return _MAX_VALUE; |
| 73 } | 73 } |
| 74 | 74 |
| 75 /** | 75 /** |
| 76 * The minimum positive value attainable by an [int64], namely | 76 * The minimum positive value attainable by an [Int64], namely |
| 77 * -9,223,372,036,854,775,808. | 77 * -9,223,372,036,854,775,808. |
| 78 */ | 78 */ |
| 79 static int64 get MIN_VALUE { | 79 static Int64 get MIN_VALUE { |
| 80 if (_MIN_VALUE == null) { | 80 if (_MIN_VALUE == null) { |
| 81 _MIN_VALUE = new int64._bits(0, 0, _SIGN_BIT_VALUE); | 81 _MIN_VALUE = new Int64._bits(0, 0, _SIGN_BIT_VALUE); |
| 82 } | 82 } |
| 83 return _MIN_VALUE; | 83 return _MIN_VALUE; |
| 84 } | 84 } |
| 85 | 85 |
| 86 /** | 86 /** |
| 87 * An [int64] constant equal to 0. | 87 * An [Int64] constant equal to 0. |
| 88 */ | 88 */ |
| 89 static int64 get ZERO { | 89 static Int64 get ZERO { |
| 90 if (_ZERO == null) { | 90 if (_ZERO == null) { |
| 91 _ZERO = new int64(); | 91 _ZERO = new Int64(); |
| 92 } | 92 } |
| 93 return _ZERO; | 93 return _ZERO; |
| 94 } | 94 } |
| 95 | 95 |
| 96 /** | 96 /** |
| 97 * An [int64] constant equal to 1. | 97 * An [Int64] constant equal to 1. |
| 98 */ | 98 */ |
| 99 static int64 get ONE { | 99 static Int64 get ONE { |
| 100 if (_ONE == null) { | 100 if (_ONE == null) { |
| 101 _ONE = new int64._bits(1, 0, 0); | 101 _ONE = new Int64._bits(1, 0, 0); |
| 102 } | 102 } |
| 103 return _ONE; | 103 return _ONE; |
| 104 } | 104 } |
| 105 | 105 |
| 106 /** | 106 /** |
| 107 * An [int64] constant equal to 2. | 107 * An [Int64] constant equal to 2. |
| 108 */ | 108 */ |
| 109 static int64 get TWO { | 109 static Int64 get TWO { |
| 110 if (_TWO == null) { | 110 if (_TWO == null) { |
| 111 _TWO = new int64._bits(2, 0, 0); | 111 _TWO = new Int64._bits(2, 0, 0); |
| 112 } | 112 } |
| 113 return _TWO; | 113 return _TWO; |
| 114 } | 114 } |
| 115 | 115 |
| 116 /** | 116 /** |
| 117 * Parses a [String] in a given [radix] between 2 and 16 and returns an | 117 * Parses a [String] in a given [radix] between 2 and 16 and returns an |
| 118 * [int64]. | 118 * [Int64]. |
| 119 */ | 119 */ |
| 120 // TODO(rice) - make this faster by converting several digits at once. | 120 // TODO(rice) - make this faster by converting several digits at once. |
| 121 static int64 parseRadix(String s, int radix) { | 121 static Int64 parseRadix(String s, int radix) { |
| 122 if ((radix <= 1) || (radix > 16)) { | 122 if ((radix <= 1) || (radix > 16)) { |
| 123 throw "Bad radix: $radix"; | 123 throw "Bad radix: $radix"; |
| 124 } | 124 } |
| 125 int64 x = ZERO; | 125 Int64 x = ZERO; |
| 126 int i = 0; | 126 int i = 0; |
| 127 bool negative = false; | 127 bool negative = false; |
| 128 if (s[0] == '-') { | 128 if (s[0] == '-') { |
| 129 negative = true; | 129 negative = true; |
| 130 i++; | 130 i++; |
| 131 } | 131 } |
| 132 for (; i < s.length; i++) { | 132 for (; i < s.length; i++) { |
| 133 int c = s.codeUnitAt(i); | 133 int c = s.codeUnitAt(i); |
| 134 int digit = int32._decodeHex(c); | 134 int digit = Int32._decodeHex(c); |
| 135 if (digit < 0 || digit >= radix) { | 135 if (digit < 0 || digit >= radix) { |
| 136 throw new Exception("Non-radix char code: $c"); | 136 throw new Exception("Non-radix char code: $c"); |
| 137 } | 137 } |
| 138 x = (x * radix) + digit; | 138 x = (x * radix) + digit; |
| 139 } | 139 } |
| 140 return negative ? -x : x; | 140 return negative ? -x : x; |
| 141 } | 141 } |
| 142 | 142 |
| 143 /** | 143 /** |
| 144 * Parses a decimal [String] and returns an [int64]. | 144 * Parses a decimal [String] and returns an [Int64]. |
| 145 */ | 145 */ |
| 146 static int64 parseInt(String s) => parseRadix(s, 10); | 146 static Int64 parseInt(String s) => parseRadix(s, 10); |
| 147 | 147 |
| 148 /** | 148 /** |
| 149 * Parses a hexadecimal [String] and returns an [int64]. | 149 * Parses a hexadecimal [String] and returns an [Int64]. |
| 150 */ | 150 */ |
| 151 static int64 parseHex(String s) => parseRadix(s, 16); | 151 static Int64 parseHex(String s) => parseRadix(s, 16); |
| 152 | 152 |
| 153 // | 153 // |
| 154 // Public constructors | 154 // Public constructors |
| 155 // | 155 // |
| 156 | 156 |
| 157 /** | 157 /** |
| 158 * Constructs an [int64] equal to 0. | 158 * Constructs an [Int64] equal to 0. |
| 159 */ | 159 */ |
| 160 int64() : _l = 0, _m = 0, _h = 0; | 160 Int64() : _l = 0, _m = 0, _h = 0; |
| 161 | 161 |
| 162 /** | 162 /** |
| 163 * Constructs an [int64] with a given [int] value. | 163 * Constructs an [Int64] with a given [int] value. |
| 164 */ | 164 */ |
| 165 int64.fromInt(int value) { | 165 Int64.fromInt(int value) { |
| 166 bool negative = false; | 166 bool negative = false; |
| 167 if (value < 0) { | 167 if (value < 0) { |
| 168 negative = true; | 168 negative = true; |
| 169 value = -value - 1; | 169 value = -value - 1; |
| 170 } | 170 } |
| 171 if (_haveBigInts) { | 171 if (_haveBigInts) { |
| 172 _l = value & _MASK; | 172 _l = value & _MASK; |
| 173 _m = (value >> _BITS) & _MASK; | 173 _m = (value >> _BITS) & _MASK; |
| 174 _h = (value >> _BITS01) & _MASK_2; | 174 _h = (value >> _BITS01) & _MASK_2; |
| 175 } else { | 175 } else { |
| 176 // Avoid using bitwise operations that coerce their input to 32 bits. | 176 // Avoid using bitwise operations that coerce their input to 32 bits. |
| 177 _h = value ~/ 17592186044416; // 2^44 | 177 _h = value ~/ 17592186044416; // 2^44 |
| 178 value -= _h * 17592186044416; | 178 value -= _h * 17592186044416; |
| 179 _m = value ~/ 4194304; // 2^22 | 179 _m = value ~/ 4194304; // 2^22 |
| 180 value -= _m * 4194304; | 180 value -= _m * 4194304; |
| 181 _l = value; | 181 _l = value; |
| 182 } | 182 } |
| 183 | 183 |
| 184 if (negative) { | 184 if (negative) { |
| 185 _l = ~_l & _MASK; | 185 _l = ~_l & _MASK; |
| 186 _m = ~_m & _MASK; | 186 _m = ~_m & _MASK; |
| 187 _h = ~_h & _MASK_2; | 187 _h = ~_h & _MASK_2; |
| 188 } | 188 } |
| 189 } | 189 } |
| 190 | 190 |
| 191 factory int64.fromBytes(List<int> bytes) { | 191 factory Int64.fromBytes(List<int> bytes) { |
| 192 int top = bytes[7] & 0xff; | 192 int top = bytes[7] & 0xff; |
| 193 top <<= 8; | 193 top <<= 8; |
| 194 top |= bytes[6] & 0xff; | 194 top |= bytes[6] & 0xff; |
| 195 top <<= 8; | 195 top <<= 8; |
| 196 top |= bytes[5] & 0xff; | 196 top |= bytes[5] & 0xff; |
| 197 top <<= 8; | 197 top <<= 8; |
| 198 top |= bytes[4] & 0xff; | 198 top |= bytes[4] & 0xff; |
| 199 | 199 |
| 200 int bottom = bytes[3] & 0xff; | 200 int bottom = bytes[3] & 0xff; |
| 201 bottom <<= 8; | 201 bottom <<= 8; |
| 202 bottom |= bytes[2] & 0xff; | 202 bottom |= bytes[2] & 0xff; |
| 203 bottom <<= 8; | 203 bottom <<= 8; |
| 204 bottom |= bytes[1] & 0xff; | 204 bottom |= bytes[1] & 0xff; |
| 205 bottom <<= 8; | 205 bottom <<= 8; |
| 206 bottom |= bytes[0] & 0xff; | 206 bottom |= bytes[0] & 0xff; |
| 207 | 207 |
| 208 return new int64.fromInts(top, bottom); | 208 return new Int64.fromInts(top, bottom); |
| 209 } | 209 } |
| 210 | 210 |
| 211 factory int64.fromBytesBigEndian(List<int> bytes) { | 211 factory Int64.fromBytesBigEndian(List<int> bytes) { |
| 212 int top = bytes[0] & 0xff; | 212 int top = bytes[0] & 0xff; |
| 213 top <<= 8; | 213 top <<= 8; |
| 214 top |= bytes[1] & 0xff; | 214 top |= bytes[1] & 0xff; |
| 215 top <<= 8; | 215 top <<= 8; |
| 216 top |= bytes[2] & 0xff; | 216 top |= bytes[2] & 0xff; |
| 217 top <<= 8; | 217 top <<= 8; |
| 218 top |= bytes[3] & 0xff; | 218 top |= bytes[3] & 0xff; |
| 219 | 219 |
| 220 int bottom = bytes[4] & 0xff; | 220 int bottom = bytes[4] & 0xff; |
| 221 bottom <<= 8; | 221 bottom <<= 8; |
| 222 bottom |= bytes[5] & 0xff; | 222 bottom |= bytes[5] & 0xff; |
| 223 bottom <<= 8; | 223 bottom <<= 8; |
| 224 bottom |= bytes[6] & 0xff; | 224 bottom |= bytes[6] & 0xff; |
| 225 bottom <<= 8; | 225 bottom <<= 8; |
| 226 bottom |= bytes[7] & 0xff; | 226 bottom |= bytes[7] & 0xff; |
| 227 | 227 |
| 228 return new int64.fromInts(top, bottom); | 228 return new Int64.fromInts(top, bottom); |
| 229 } | 229 } |
| 230 | 230 |
| 231 /** | 231 /** |
| 232 * Constructs an [int64] from a pair of 32-bit integers having the value | 232 * Constructs an [Int64] from a pair of 32-bit integers having the value |
| 233 * [:((top & 0xffffffff) << 32) | (bottom & 0xffffffff):]. | 233 * [:((top & 0xffffffff) << 32) | (bottom & 0xffffffff):]. |
| 234 */ | 234 */ |
| 235 int64.fromInts(int top, int bottom) { | 235 Int64.fromInts(int top, int bottom) { |
| 236 top &= 0xffffffff; | 236 top &= 0xffffffff; |
| 237 bottom &= 0xffffffff; | 237 bottom &= 0xffffffff; |
| 238 _l = bottom & _MASK; | 238 _l = bottom & _MASK; |
| 239 _m = ((top & 0xfff) << 10) | ((bottom >> _BITS) & 0x3ff); | 239 _m = ((top & 0xfff) << 10) | ((bottom >> _BITS) & 0x3ff); |
| 240 _h = (top >> 12) & _MASK_2; | 240 _h = (top >> 12) & _MASK_2; |
| 241 } | 241 } |
| 242 | 242 |
| 243 // Returns the [int64] representation of the specified value. Throws | 243 // Returns the [Int64] representation of the specified value. Throws |
| 244 // [ArgumentError] for non-integer arguments. | 244 // [ArgumentError] for non-integer arguments. |
| 245 int64 _promote(val) { | 245 Int64 _promote(val) { |
| 246 if (val is int64) { | 246 if (val is Int64) { |
| 247 return val; | 247 return val; |
| 248 } else if (val is int) { | 248 } else if (val is int) { |
| 249 return new int64.fromInt(val); | 249 return new Int64.fromInt(val); |
| 250 } else if (val is int32) { | 250 } else if (val is Int32) { |
| 251 return val.toInt64(); | 251 return val.toInt64(); |
| 252 } | 252 } |
| 253 throw new ArgumentError(val); | 253 throw new ArgumentError(val); |
| 254 } | 254 } |
| 255 | 255 |
| 256 int64 operator +(other) { | 256 Int64 operator +(other) { |
| 257 int64 o = _promote(other); | 257 Int64 o = _promote(other); |
| 258 int sum0 = _l + o._l; | 258 int sum0 = _l + o._l; |
| 259 int sum1 = _m + o._m + _shiftRight(sum0, _BITS); | 259 int sum1 = _m + o._m + _shiftRight(sum0, _BITS); |
| 260 int sum2 = _h + o._h + _shiftRight(sum1, _BITS); | 260 int sum2 = _h + o._h + _shiftRight(sum1, _BITS); |
| 261 | 261 |
| 262 int64 result = new int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); | 262 Int64 result = new Int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); |
| 263 return result; | 263 return result; |
| 264 } | 264 } |
| 265 | 265 |
| 266 int64 operator -(other) { | 266 Int64 operator -(other) { |
| 267 int64 o = _promote(other); | 267 Int64 o = _promote(other); |
| 268 int sum0 = _l - o._l; | 268 int sum0 = _l - o._l; |
| 269 int sum1 = _m - o._m + _shiftRight(sum0, _BITS); | 269 int sum1 = _m - o._m + _shiftRight(sum0, _BITS); |
| 270 int sum2 = _h - o._h + _shiftRight(sum1, _BITS); | 270 int sum2 = _h - o._h + _shiftRight(sum1, _BITS); |
| 271 | 271 |
| 272 int64 result = new int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); | 272 Int64 result = new Int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); |
| 273 return result; | 273 return result; |
| 274 } | 274 } |
| 275 | 275 |
| 276 int64 operator -() { | 276 Int64 operator -() { |
| 277 // Like 0 - this. | 277 // Like 0 - this. |
| 278 int sum0 = -_l; | 278 int sum0 = -_l; |
| 279 int sum1 = -_m + _shiftRight(sum0, _BITS); | 279 int sum1 = -_m + _shiftRight(sum0, _BITS); |
| 280 int sum2 = -_h + _shiftRight(sum1, _BITS); | 280 int sum2 = -_h + _shiftRight(sum1, _BITS); |
| 281 | 281 |
| 282 return new int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); | 282 return new Int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); |
| 283 } | 283 } |
| 284 | 284 |
| 285 int64 operator *(other) { | 285 Int64 operator *(other) { |
| 286 int64 o = _promote(other); | 286 Int64 o = _promote(other); |
| 287 | 287 |
| 288 // Grab 13-bit chunks. | 288 // Grab 13-bit chunks. |
| 289 int a0 = _l & 0x1fff; | 289 int a0 = _l & 0x1fff; |
| 290 int a1 = (_l >> 13) | ((_m & 0xf) << 9); | 290 int a1 = (_l >> 13) | ((_m & 0xf) << 9); |
| 291 int a2 = (_m >> 4) & 0x1fff; | 291 int a2 = (_m >> 4) & 0x1fff; |
| 292 int a3 = (_m >> 17) | ((_h & 0xff) << 5); | 292 int a3 = (_m >> 17) | ((_h & 0xff) << 5); |
| 293 int a4 = (_h & 0xfff00) >> 8; | 293 int a4 = (_h & 0xfff00) >> 8; |
| 294 | 294 |
| 295 int b0 = o._l & 0x1fff; | 295 int b0 = o._l & 0x1fff; |
| 296 int b1 = (o._l >> 13) | ((o._m & 0xf) << 9); | 296 int b1 = (o._l >> 13) | ((o._m & 0xf) << 9); |
| (...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 356 int c24 = (p4 & 0xfff) << 8; | 356 int c24 = (p4 & 0xfff) << 8; |
| 357 int c2 = c22 + c23 + c24; | 357 int c2 = c22 + c23 + c24; |
| 358 | 358 |
| 359 // Propagate high bits from c0 -> c1, c1 -> c2. | 359 // Propagate high bits from c0 -> c1, c1 -> c2. |
| 360 c1 += c0 >> _BITS; | 360 c1 += c0 >> _BITS; |
| 361 c0 &= _MASK; | 361 c0 &= _MASK; |
| 362 c2 += c1 >> _BITS; | 362 c2 += c1 >> _BITS; |
| 363 c1 &= _MASK; | 363 c1 &= _MASK; |
| 364 c2 &= _MASK_2; | 364 c2 &= _MASK_2; |
| 365 | 365 |
| 366 return new int64._bits(c0, c1, c2); | 366 return new Int64._bits(c0, c1, c2); |
| 367 } | 367 } |
| 368 | 368 |
| 369 int64 operator %(other) { | 369 Int64 operator %(other) { |
| 370 if (other.isZero) { | 370 if (other.isZero) { |
| 371 throw new IntegerDivisionByZeroException(); | 371 throw new IntegerDivisionByZeroException(); |
| 372 } | 372 } |
| 373 if (this.isZero) { | 373 if (this.isZero) { |
| 374 return ZERO; | 374 return ZERO; |
| 375 } | 375 } |
| 376 int64 o = _promote(other).abs(); | 376 Int64 o = _promote(other).abs(); |
| 377 _divMod(this, o, true); | 377 _divMod(this, o, true); |
| 378 return _remainder < 0 ? (_remainder + o) : _remainder; | 378 return _remainder < 0 ? (_remainder + o) : _remainder; |
| 379 } | 379 } |
| 380 | 380 |
| 381 int64 operator ~/(other) => _divMod(this, _promote(other), false); | 381 Int64 operator ~/(other) => _divMod(this, _promote(other), false); |
| 382 | 382 |
| 383 // int64 remainder(other) => this - (this ~/ other) * other; | 383 // Int64 remainder(other) => this - (this ~/ other) * other; |
| 384 int64 remainder(other) { | 384 Int64 remainder(other) { |
| 385 if (other.isZero) { | 385 if (other.isZero) { |
| 386 throw new IntegerDivisionByZeroException(); | 386 throw new IntegerDivisionByZeroException(); |
| 387 } | 387 } |
| 388 int64 o = _promote(other).abs(); | 388 Int64 o = _promote(other).abs(); |
| 389 _divMod(this, o, true); | 389 _divMod(this, o, true); |
| 390 return _remainder; | 390 return _remainder; |
| 391 } | 391 } |
| 392 | 392 |
| 393 int64 operator &(other) { | 393 Int64 operator &(other) { |
| 394 int64 o = _promote(other); | 394 Int64 o = _promote(other); |
| 395 int a0 = _l & o._l; | 395 int a0 = _l & o._l; |
| 396 int a1 = _m & o._m; | 396 int a1 = _m & o._m; |
| 397 int a2 = _h & o._h; | 397 int a2 = _h & o._h; |
| 398 return new int64._bits(a0, a1, a2); | 398 return new Int64._bits(a0, a1, a2); |
| 399 } | 399 } |
| 400 | 400 |
| 401 int64 operator |(other) { | 401 Int64 operator |(other) { |
| 402 int64 o = _promote(other); | 402 Int64 o = _promote(other); |
| 403 int a0 = _l | o._l; | 403 int a0 = _l | o._l; |
| 404 int a1 = _m | o._m; | 404 int a1 = _m | o._m; |
| 405 int a2 = _h | o._h; | 405 int a2 = _h | o._h; |
| 406 return new int64._bits(a0, a1, a2); | 406 return new Int64._bits(a0, a1, a2); |
| 407 } | 407 } |
| 408 | 408 |
| 409 int64 operator ^(other) { | 409 Int64 operator ^(other) { |
| 410 int64 o = _promote(other); | 410 Int64 o = _promote(other); |
| 411 int a0 = _l ^ o._l; | 411 int a0 = _l ^ o._l; |
| 412 int a1 = _m ^ o._m; | 412 int a1 = _m ^ o._m; |
| 413 int a2 = _h ^ o._h; | 413 int a2 = _h ^ o._h; |
| 414 return new int64._bits(a0, a1, a2); | 414 return new Int64._bits(a0, a1, a2); |
| 415 } | 415 } |
| 416 | 416 |
| 417 int64 operator ~() { | 417 Int64 operator ~() { |
| 418 var result = new int64._bits((~_l) & _MASK, (~_m) & _MASK, (~_h) & _MASK_2); | 418 var result = new Int64._bits((~_l) & _MASK, (~_m) & _MASK, (~_h) & _MASK_2); |
| 419 return result; | 419 return result; |
| 420 } | 420 } |
| 421 | 421 |
| 422 int64 operator <<(int n) { | 422 Int64 operator <<(int n) { |
| 423 if (n < 0) { | 423 if (n < 0) { |
| 424 throw new ArgumentError("$n"); | 424 throw new ArgumentError("$n"); |
| 425 } | 425 } |
| 426 n &= 63; | 426 n &= 63; |
| 427 | 427 |
| 428 int res0, res1, res2; | 428 int res0, res1, res2; |
| 429 if (n < _BITS) { | 429 if (n < _BITS) { |
| 430 res0 = _l << n; | 430 res0 = _l << n; |
| 431 res1 = (_m << n) | (_l >> (_BITS - n)); | 431 res1 = (_m << n) | (_l >> (_BITS - n)); |
| 432 res2 = (_h << n) | (_m >> (_BITS - n)); | 432 res2 = (_h << n) | (_m >> (_BITS - n)); |
| 433 } else if (n < _BITS01) { | 433 } else if (n < _BITS01) { |
| 434 res0 = 0; | 434 res0 = 0; |
| 435 res1 = _l << (n - _BITS); | 435 res1 = _l << (n - _BITS); |
| 436 res2 = (_m << (n - _BITS)) | (_l >> (_BITS01 - n)); | 436 res2 = (_m << (n - _BITS)) | (_l >> (_BITS01 - n)); |
| 437 } else { | 437 } else { |
| 438 res0 = 0; | 438 res0 = 0; |
| 439 res1 = 0; | 439 res1 = 0; |
| 440 res2 = _l << (n - _BITS01); | 440 res2 = _l << (n - _BITS01); |
| 441 } | 441 } |
| 442 | 442 |
| 443 return new int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); | 443 return new Int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); |
| 444 } | 444 } |
| 445 | 445 |
| 446 int64 operator >>(int n) { | 446 Int64 operator >>(int n) { |
| 447 if (n < 0) { | 447 if (n < 0) { |
| 448 throw new ArgumentError("$n"); | 448 throw new ArgumentError("$n"); |
| 449 } | 449 } |
| 450 n &= 63; | 450 n &= 63; |
| 451 | 451 |
| 452 int res0, res1, res2; | 452 int res0, res1, res2; |
| 453 | 453 |
| 454 // Sign extend h(a). | 454 // Sign extend h(a). |
| 455 int a2 = _h; | 455 int a2 = _h; |
| 456 bool negative = (a2 & _SIGN_BIT_VALUE) != 0; | 456 bool negative = (a2 & _SIGN_BIT_VALUE) != 0; |
| (...skipping 17 matching lines...) Expand all Loading... |
| 474 res0 = _shiftRight(_m, n - _BITS) | (a2 << (_BITS01 - n)); | 474 res0 = _shiftRight(_m, n - _BITS) | (a2 << (_BITS01 - n)); |
| 475 } else { | 475 } else { |
| 476 res2 = negative ? _MASK_2 : 0; | 476 res2 = negative ? _MASK_2 : 0; |
| 477 res1 = negative ? _MASK : 0; | 477 res1 = negative ? _MASK : 0; |
| 478 res0 = _shiftRight(a2, n - _BITS01); | 478 res0 = _shiftRight(a2, n - _BITS01); |
| 479 if (negative) { | 479 if (negative) { |
| 480 res0 |= _MASK & ~(_MASK >> (n - _BITS01)); | 480 res0 |= _MASK & ~(_MASK >> (n - _BITS01)); |
| 481 } | 481 } |
| 482 } | 482 } |
| 483 | 483 |
| 484 return new int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); | 484 return new Int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); |
| 485 } | 485 } |
| 486 | 486 |
| 487 int64 shiftRightUnsigned(int n) { | 487 Int64 shiftRightUnsigned(int n) { |
| 488 if (n < 0) { | 488 if (n < 0) { |
| 489 throw new ArgumentError("$n"); | 489 throw new ArgumentError("$n"); |
| 490 } | 490 } |
| 491 n &= 63; | 491 n &= 63; |
| 492 | 492 |
| 493 int res0, res1, res2; | 493 int res0, res1, res2; |
| 494 int a2 = _h & _MASK_2; // Ensure a2 is positive. | 494 int a2 = _h & _MASK_2; // Ensure a2 is positive. |
| 495 if (n < _BITS) { | 495 if (n < _BITS) { |
| 496 res2 = a2 >> n; | 496 res2 = a2 >> n; |
| 497 res1 = (_m >> n) | (a2 << (_BITS - n)); | 497 res1 = (_m >> n) | (a2 << (_BITS - n)); |
| 498 res0 = (_l >> n) | (_m << (_BITS - n)); | 498 res0 = (_l >> n) | (_m << (_BITS - n)); |
| 499 } else if (n < _BITS01) { | 499 } else if (n < _BITS01) { |
| 500 res2 = 0; | 500 res2 = 0; |
| 501 res1 = a2 >> (n - _BITS); | 501 res1 = a2 >> (n - _BITS); |
| 502 res0 = (_m >> (n - _BITS)) | (_h << (_BITS01 - n)); | 502 res0 = (_m >> (n - _BITS)) | (_h << (_BITS01 - n)); |
| 503 } else { | 503 } else { |
| 504 res2 = 0; | 504 res2 = 0; |
| 505 res1 = 0; | 505 res1 = 0; |
| 506 res0 = a2 >> (n - _BITS01); | 506 res0 = a2 >> (n - _BITS01); |
| 507 } | 507 } |
| 508 | 508 |
| 509 return new int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); | 509 return new Int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); |
| 510 } | 510 } |
| 511 | 511 |
| 512 /** | 512 /** |
| 513 * Returns [true] if this [int64] has the same numeric value as the | 513 * Returns [true] if this [Int64] has the same numeric value as the |
| 514 * given object. The argument may be an [int] or an [intx]. | 514 * given object. The argument may be an [int] or an [Intx]. |
| 515 */ | 515 */ |
| 516 bool operator ==(other) { | 516 bool operator ==(other) { |
| 517 int64 o; | 517 Int64 o; |
| 518 if (other is int64) { | 518 if (other is Int64) { |
| 519 o = other; | 519 o = other; |
| 520 } else if (other is int) { | 520 } else if (other is int) { |
| 521 o = new int64.fromInt(other); | 521 o = new Int64.fromInt(other); |
| 522 } else if (other is int32) { | 522 } else if (other is Int32) { |
| 523 o = other.toInt64(); | 523 o = other.toInt64(); |
| 524 } | 524 } |
| 525 if (o != null) { | 525 if (o != null) { |
| 526 return _l == o._l && _m == o._m && _h == o._h; | 526 return _l == o._l && _m == o._m && _h == o._h; |
| 527 } | 527 } |
| 528 return false; | 528 return false; |
| 529 } | 529 } |
| 530 | 530 |
| 531 int compareTo(Comparable other) { | 531 int compareTo(Comparable other) { |
| 532 int64 o = _promote(other); | 532 Int64 o = _promote(other); |
| 533 int signa = _h >> (_BITS2 - 1); | 533 int signa = _h >> (_BITS2 - 1); |
| 534 int signb = o._h >> (_BITS2 - 1); | 534 int signb = o._h >> (_BITS2 - 1); |
| 535 if (signa != signb) { | 535 if (signa != signb) { |
| 536 return signa == 0 ? 1 : -1; | 536 return signa == 0 ? 1 : -1; |
| 537 } | 537 } |
| 538 if (_h > o._h) { | 538 if (_h > o._h) { |
| 539 return 1; | 539 return 1; |
| 540 } else if (_h < o._h) { | 540 } else if (_h < o._h) { |
| 541 return -1; | 541 return -1; |
| 542 } | 542 } |
| (...skipping 27 matching lines...) Expand all Loading... |
| 570 } | 570 } |
| 571 | 571 |
| 572 bool get isEven => (_l & 0x1) == 0; | 572 bool get isEven => (_l & 0x1) == 0; |
| 573 bool get isMaxValue => (_h == _MASK_2 >> 1) && _m == _MASK && _l == _MASK; | 573 bool get isMaxValue => (_h == _MASK_2 >> 1) && _m == _MASK && _l == _MASK; |
| 574 bool get isMinValue => _h == _SIGN_BIT_VALUE && _m == 0 && _l == 0; | 574 bool get isMinValue => _h == _SIGN_BIT_VALUE && _m == 0 && _l == 0; |
| 575 bool get isNegative => (_h >> (_BITS2 - 1)) != 0; | 575 bool get isNegative => (_h >> (_BITS2 - 1)) != 0; |
| 576 bool get isOdd => (_l & 0x1) == 1; | 576 bool get isOdd => (_l & 0x1) == 1; |
| 577 bool get isZero => _h == 0 && _m == 0 && _l == 0; | 577 bool get isZero => _h == 0 && _m == 0 && _l == 0; |
| 578 | 578 |
| 579 /** | 579 /** |
| 580 * Returns a hash code based on all the bits of this [int64]. | 580 * Returns a hash code based on all the bits of this [Int64]. |
| 581 */ | 581 */ |
| 582 int get hashCode { | 582 int get hashCode { |
| 583 int bottom = ((_m & 0x3ff) << _BITS) | _l; | 583 int bottom = ((_m & 0x3ff) << _BITS) | _l; |
| 584 int top = (_h << 12) | ((_m >> 10) & 0xfff); | 584 int top = (_h << 12) | ((_m >> 10) & 0xfff); |
| 585 return bottom ^ top; | 585 return bottom ^ top; |
| 586 } | 586 } |
| 587 | 587 |
| 588 int64 abs() { | 588 Int64 abs() { |
| 589 return this < 0 ? -this : this; | 589 return this < 0 ? -this : this; |
| 590 } | 590 } |
| 591 | 591 |
| 592 /** | 592 /** |
| 593 * Returns the number of leading zeros in this [int64] as an [int] | 593 * Returns the number of leading zeros in this [Int64] as an [int] |
| 594 * between 0 and 64. | 594 * between 0 and 64. |
| 595 */ | 595 */ |
| 596 int numberOfLeadingZeros() { | 596 int numberOfLeadingZeros() { |
| 597 int b2 = int32._numberOfLeadingZeros(_h); | 597 int b2 = Int32._numberOfLeadingZeros(_h); |
| 598 if (b2 == 32) { | 598 if (b2 == 32) { |
| 599 int b1 = int32._numberOfLeadingZeros(_m); | 599 int b1 = Int32._numberOfLeadingZeros(_m); |
| 600 if (b1 == 32) { | 600 if (b1 == 32) { |
| 601 return int32._numberOfLeadingZeros(_l) + 32; | 601 return Int32._numberOfLeadingZeros(_l) + 32; |
| 602 } else { | 602 } else { |
| 603 return b1 + _BITS2 - (32 - _BITS); | 603 return b1 + _BITS2 - (32 - _BITS); |
| 604 } | 604 } |
| 605 } else { | 605 } else { |
| 606 return b2 - (32 - _BITS2); | 606 return b2 - (32 - _BITS2); |
| 607 } | 607 } |
| 608 } | 608 } |
| 609 | 609 |
| 610 /** | 610 /** |
| 611 * Returns the number of trailing zeros in this [int64] as an [int] | 611 * Returns the number of trailing zeros in this [Int64] as an [int] |
| 612 * between 0 and 64. | 612 * between 0 and 64. |
| 613 */ | 613 */ |
| 614 int numberOfTrailingZeros() { | 614 int numberOfTrailingZeros() { |
| 615 int zeros = int32._numberOfTrailingZeros(_l); | 615 int zeros = Int32._numberOfTrailingZeros(_l); |
| 616 if (zeros < 32) { | 616 if (zeros < 32) { |
| 617 return zeros; | 617 return zeros; |
| 618 } | 618 } |
| 619 | 619 |
| 620 zeros = int32._numberOfTrailingZeros(_m); | 620 zeros = Int32._numberOfTrailingZeros(_m); |
| 621 if (zeros < 32) { | 621 if (zeros < 32) { |
| 622 return _BITS + zeros; | 622 return _BITS + zeros; |
| 623 } | 623 } |
| 624 | 624 |
| 625 zeros = int32._numberOfTrailingZeros(_h); | 625 zeros = Int32._numberOfTrailingZeros(_h); |
| 626 if (zeros < 32) { | 626 if (zeros < 32) { |
| 627 return _BITS01 + zeros; | 627 return _BITS01 + zeros; |
| 628 } | 628 } |
| 629 // All zeros | 629 // All zeros |
| 630 return 64; | 630 return 64; |
| 631 } | 631 } |
| 632 | 632 |
| 633 List<int> toBytes() { | 633 List<int> toBytes() { |
| 634 List<int> result = new List<int>(8); | 634 List<int> result = new List<int>(8); |
| 635 result[0] = _l & 0xff; | 635 result[0] = _l & 0xff; |
| (...skipping 22 matching lines...) Expand all Loading... |
| 658 int result; | 658 int result; |
| 659 if (_haveBigInts) { | 659 if (_haveBigInts) { |
| 660 result = (h << _BITS01) | (m << _BITS) | l; | 660 result = (h << _BITS01) | (m << _BITS) | l; |
| 661 } else { | 661 } else { |
| 662 result = (h * 17592186044416) + (m * 4194304) + l; | 662 result = (h * 17592186044416) + (m * 4194304) + l; |
| 663 } | 663 } |
| 664 return negative ? -result - 1 : result; | 664 return negative ? -result - 1 : result; |
| 665 } | 665 } |
| 666 | 666 |
| 667 /** | 667 /** |
| 668 * Returns an [int32] containing the low 32 bits of this [int64]. | 668 * Returns an [Int32] containing the low 32 bits of this [Int64]. |
| 669 */ | 669 */ |
| 670 int32 toInt32() { | 670 Int32 toInt32() { |
| 671 return new int32.fromInt(((_m & 0x3ff) << _BITS) | _l); | 671 return new Int32.fromInt(((_m & 0x3ff) << _BITS) | _l); |
| 672 } | 672 } |
| 673 | 673 |
| 674 /** | 674 /** |
| 675 * Returns [this]. | 675 * Returns [this]. |
| 676 */ | 676 */ |
| 677 int64 toInt64() => this; | 677 Int64 toInt64() => this; |
| 678 | 678 |
| 679 /** | 679 /** |
| 680 * Returns the value of this [int64] as a decimal [String]. | 680 * Returns the value of this [Int64] as a decimal [String]. |
| 681 */ | 681 */ |
| 682 // TODO(rice) - Make this faster by converting several digits at once. | 682 // TODO(rice) - Make this faster by converting several digits at once. |
| 683 String toString() { | 683 String toString() { |
| 684 int64 a = this; | 684 Int64 a = this; |
| 685 if (a.isZero) { | 685 if (a.isZero) { |
| 686 return "0"; | 686 return "0"; |
| 687 } | 687 } |
| 688 if (a.isMinValue) { | 688 if (a.isMinValue) { |
| 689 return "-9223372036854775808"; | 689 return "-9223372036854775808"; |
| 690 } | 690 } |
| 691 | 691 |
| 692 String result = ""; | 692 String result = ""; |
| 693 bool negative = false; | 693 bool negative = false; |
| 694 if (a.isNegative) { | 694 if (a.isNegative) { |
| 695 negative = true; | 695 negative = true; |
| 696 a = -a; | 696 a = -a; |
| 697 } | 697 } |
| 698 | 698 |
| 699 int64 ten = new int64._bits(10, 0, 0); | 699 Int64 ten = new Int64._bits(10, 0, 0); |
| 700 while (!a.isZero) { | 700 while (!a.isZero) { |
| 701 a = _divMod(a, ten, true); | 701 a = _divMod(a, ten, true); |
| 702 result = "${_remainder._l}$result"; | 702 result = "${_remainder._l}$result"; |
| 703 } | 703 } |
| 704 if (negative) { | 704 if (negative) { |
| 705 result = "-$result"; | 705 result = "-$result"; |
| 706 } | 706 } |
| 707 return result; | 707 return result; |
| 708 } | 708 } |
| 709 | 709 |
| 710 // TODO(rice) - Make this faster by avoiding arithmetic. | 710 // TODO(rice) - Make this faster by avoiding arithmetic. |
| 711 String toHexString() { | 711 String toHexString() { |
| 712 int64 x = new int64._copy(this); | 712 Int64 x = new Int64._copy(this); |
| 713 if (isZero) { | 713 if (isZero) { |
| 714 return "0"; | 714 return "0"; |
| 715 } | 715 } |
| 716 String hexStr = ""; | 716 String hexStr = ""; |
| 717 int64 digit_f = new int64.fromInt(0xf); | 717 Int64 digit_f = new Int64.fromInt(0xf); |
| 718 while (!x.isZero) { | 718 while (!x.isZero) { |
| 719 int digit = x._l & 0xf; | 719 int digit = x._l & 0xf; |
| 720 hexStr = "${_hexDigit(digit)}$hexStr"; | 720 hexStr = "${_hexDigit(digit)}$hexStr"; |
| 721 x = x.shiftRightUnsigned(4); | 721 x = x.shiftRightUnsigned(4); |
| 722 } | 722 } |
| 723 return hexStr; | 723 return hexStr; |
| 724 } | 724 } |
| 725 | 725 |
| 726 String toRadixString(int radix) { | 726 String toRadixString(int radix) { |
| 727 if ((radix <= 1) || (radix > 16)) { | 727 if ((radix <= 1) || (radix > 16)) { |
| 728 throw "Bad radix: $radix"; | 728 throw "Bad radix: $radix"; |
| 729 } | 729 } |
| 730 int64 a = this; | 730 Int64 a = this; |
| 731 if (a.isZero) { | 731 if (a.isZero) { |
| 732 return "0"; | 732 return "0"; |
| 733 } | 733 } |
| 734 if (a.isMinValue) { | 734 if (a.isMinValue) { |
| 735 return _minValues[radix]; | 735 return _minValues[radix]; |
| 736 } | 736 } |
| 737 | 737 |
| 738 String result = ""; | 738 String result = ""; |
| 739 bool negative = false; | 739 bool negative = false; |
| 740 if (a.isNegative) { | 740 if (a.isNegative) { |
| 741 negative = true; | 741 negative = true; |
| 742 a = -a; | 742 a = -a; |
| 743 } | 743 } |
| 744 | 744 |
| 745 int64 r = new int64._bits(radix, 0, 0); | 745 Int64 r = new Int64._bits(radix, 0, 0); |
| 746 while (!a.isZero) { | 746 while (!a.isZero) { |
| 747 a = _divMod(a, r, true); | 747 a = _divMod(a, r, true); |
| 748 result = "${_hexDigit(_remainder._l)}$result"; | 748 result = "${_hexDigit(_remainder._l)}$result"; |
| 749 } | 749 } |
| 750 return negative ? "-$result" : result; | 750 return negative ? "-$result" : result; |
| 751 } | 751 } |
| 752 | 752 |
| 753 String toDebugString() { | 753 String toDebugString() { |
| 754 return "int64[_l=$_l, _m=$_m, _h=$_h]"; | 754 return "Int64[_l=$_l, _m=$_m, _h=$_h]"; |
| 755 } | 755 } |
| 756 | 756 |
| 757 /** | 757 /** |
| 758 * Constructs an [int64] with a given bitwise representation. No validation | 758 * Constructs an [Int64] with a given bitwise representation. No validation |
| 759 * is performed. | 759 * is performed. |
| 760 */ | 760 */ |
| 761 int64._bits(int this._l, int this._m, int this._h); | 761 Int64._bits(int this._l, int this._m, int this._h); |
| 762 | 762 |
| 763 /** | 763 /** |
| 764 * Constructs an [int64] with the same value as an existing [int64]. | 764 * Constructs an [Int64] with the same value as an existing [Int64]. |
| 765 */ | 765 */ |
| 766 int64._copy(int64 other) { | 766 Int64._copy(Int64 other) { |
| 767 _l = other._l; | 767 _l = other._l; |
| 768 _m = other._m; | 768 _m = other._m; |
| 769 _h = other._h; | 769 _h = other._h; |
| 770 } | 770 } |
| 771 | 771 |
| 772 // Determine whether the platform supports ints greater than 2^53 | 772 // Determine whether the platform supports ints greater than 2^53 |
| 773 // without loss of precision. | 773 // without loss of precision. |
| 774 static bool _haveBigIntsCached = null; | 774 static bool _haveBigIntsCached = null; |
| 775 | 775 |
| 776 static bool get _haveBigInts { | 776 static bool get _haveBigInts { |
| (...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 841 * Attempt to subtract b from a if a >= b: | 841 * Attempt to subtract b from a if a >= b: |
| 842 * | 842 * |
| 843 * if (a >= b) { | 843 * if (a >= b) { |
| 844 * a -= b; | 844 * a -= b; |
| 845 * return true; | 845 * return true; |
| 846 * } else { | 846 * } else { |
| 847 * return false; | 847 * return false; |
| 848 * } | 848 * } |
| 849 */ | 849 */ |
| 850 // Note: mutates [a]. | 850 // Note: mutates [a]. |
| 851 static bool _trialSubtract(int64 a, int64 b) { | 851 static bool _trialSubtract(Int64 a, Int64 b) { |
| 852 // Early exit. | 852 // Early exit. |
| 853 int sum2 = a._h - b._h; | 853 int sum2 = a._h - b._h; |
| 854 if (sum2 < 0) { | 854 if (sum2 < 0) { |
| 855 return false; | 855 return false; |
| 856 } | 856 } |
| 857 | 857 |
| 858 int sum0 = a._l - b._l; | 858 int sum0 = a._l - b._l; |
| 859 int sum1 = a._m - b._m + _shiftRight(sum0, _BITS); | 859 int sum1 = a._m - b._m + _shiftRight(sum0, _BITS); |
| 860 sum2 += _shiftRight(sum1, _BITS); | 860 sum2 += _shiftRight(sum1, _BITS); |
| 861 | 861 |
| 862 if (sum2 < 0) { | 862 if (sum2 < 0) { |
| 863 return false; | 863 return false; |
| 864 } | 864 } |
| 865 | 865 |
| 866 a._l = sum0 & _MASK; | 866 a._l = sum0 & _MASK; |
| 867 a._m = sum1 & _MASK; | 867 a._m = sum1 & _MASK; |
| 868 a._h = sum2 & _MASK_2; | 868 a._h = sum2 & _MASK_2; |
| 869 | 869 |
| 870 return true; | 870 return true; |
| 871 } | 871 } |
| 872 | 872 |
| 873 // Note: mutates [a] via _trialSubtract. | 873 // Note: mutates [a] via _trialSubtract. |
| 874 static int64 _divModHelper(int64 a, int64 b, | 874 static Int64 _divModHelper(Int64 a, Int64 b, |
| 875 bool negative, bool aIsNegative, bool aIsMinValue, | 875 bool negative, bool aIsNegative, bool aIsMinValue, |
| 876 bool computeRemainder) { | 876 bool computeRemainder) { |
| 877 // Align the leading one bits of a and b by shifting b left. | 877 // Align the leading one bits of a and b by shifting b left. |
| 878 int shift = b.numberOfLeadingZeros() - a.numberOfLeadingZeros(); | 878 int shift = b.numberOfLeadingZeros() - a.numberOfLeadingZeros(); |
| 879 int64 bshift = b << shift; | 879 Int64 bshift = b << shift; |
| 880 | 880 |
| 881 // Quotient must be a new instance since we mutate it. | 881 // Quotient must be a new instance since we mutate it. |
| 882 int64 quotient = new int64(); | 882 Int64 quotient = new Int64(); |
| 883 while (shift >= 0) { | 883 while (shift >= 0) { |
| 884 bool gte = _trialSubtract(a, bshift); | 884 bool gte = _trialSubtract(a, bshift); |
| 885 if (gte) { | 885 if (gte) { |
| 886 quotient._setBit(shift); | 886 quotient._setBit(shift); |
| 887 if (a.isZero) { | 887 if (a.isZero) { |
| 888 break; | 888 break; |
| 889 } | 889 } |
| 890 } | 890 } |
| 891 | 891 |
| 892 bshift._toShru1(); | 892 bshift._toShru1(); |
| (...skipping 11 matching lines...) Expand all Loading... |
| 904 _remainder = _remainder - ONE; | 904 _remainder = _remainder - ONE; |
| 905 } | 905 } |
| 906 } else { | 906 } else { |
| 907 _remainder = a; | 907 _remainder = a; |
| 908 } | 908 } |
| 909 } | 909 } |
| 910 | 910 |
| 911 return quotient; | 911 return quotient; |
| 912 } | 912 } |
| 913 | 913 |
| 914 int64 _divModByMinValue(bool computeRemainder) { | 914 Int64 _divModByMinValue(bool computeRemainder) { |
| 915 // MIN_VALUE / MIN_VALUE == 1, remainder = 0 | 915 // MIN_VALUE / MIN_VALUE == 1, remainder = 0 |
| 916 // (x != MIN_VALUE) / MIN_VALUE == 0, remainder == x | 916 // (x != MIN_VALUE) / MIN_VALUE == 0, remainder == x |
| 917 if (isMinValue) { | 917 if (isMinValue) { |
| 918 if (computeRemainder) { | 918 if (computeRemainder) { |
| 919 _remainder = ZERO; | 919 _remainder = ZERO; |
| 920 } | 920 } |
| 921 return ONE; | 921 return ONE; |
| 922 } | 922 } |
| 923 if (computeRemainder) { | 923 if (computeRemainder) { |
| 924 _remainder = this; | 924 _remainder = this; |
| 925 } | 925 } |
| 926 return ZERO; | 926 return ZERO; |
| 927 } | 927 } |
| 928 | 928 |
| 929 /** | 929 /** |
| 930 * this &= ((1L << bits) - 1) | 930 * this &= ((1L << bits) - 1) |
| 931 */ | 931 */ |
| 932 // Note: mutates [this]. | 932 // Note: mutates [this]. |
| 933 int64 _maskRight(int bits) { | 933 Int64 _maskRight(int bits) { |
| 934 int b0, b1, b2; | 934 int b0, b1, b2; |
| 935 if (bits <= _BITS) { | 935 if (bits <= _BITS) { |
| 936 b0 = _l & ((1 << bits) - 1); | 936 b0 = _l & ((1 << bits) - 1); |
| 937 b1 = b2 = 0; | 937 b1 = b2 = 0; |
| 938 } else if (bits <= _BITS01) { | 938 } else if (bits <= _BITS01) { |
| 939 b0 = _l; | 939 b0 = _l; |
| 940 b1 = _m & ((1 << (bits - _BITS)) - 1); | 940 b1 = _m & ((1 << (bits - _BITS)) - 1); |
| 941 b2 = 0; | 941 b2 = 0; |
| 942 } else { | 942 } else { |
| 943 b0 = _l; | 943 b0 = _l; |
| 944 b1 = _m; | 944 b1 = _m; |
| 945 b2 = _h & ((1 << (bits - _BITS01)) - 1); | 945 b2 = _h & ((1 << (bits - _BITS01)) - 1); |
| 946 } | 946 } |
| 947 | 947 |
| 948 _l = b0; | 948 _l = b0; |
| 949 _m = b1; | 949 _m = b1; |
| 950 _h = b2; | 950 _h = b2; |
| 951 } | 951 } |
| 952 | 952 |
| 953 static int64 _divModByShift(int64 a, int bpower, bool negative, bool aIsCopy, | 953 static Int64 _divModByShift(Int64 a, int bpower, bool negative, bool aIsCopy, |
| 954 bool aIsNegative, bool computeRemainder) { | 954 bool aIsNegative, bool computeRemainder) { |
| 955 int64 c = a >> bpower; | 955 Int64 c = a >> bpower; |
| 956 if (negative) { | 956 if (negative) { |
| 957 c._negate(); | 957 c._negate(); |
| 958 } | 958 } |
| 959 | 959 |
| 960 if (computeRemainder) { | 960 if (computeRemainder) { |
| 961 if (!aIsCopy) { | 961 if (!aIsCopy) { |
| 962 a = new int64._copy(a); | 962 a = new Int64._copy(a); |
| 963 } | 963 } |
| 964 a._maskRight(bpower); | 964 a._maskRight(bpower); |
| 965 if (aIsNegative) { | 965 if (aIsNegative) { |
| 966 a._negate(); | 966 a._negate(); |
| 967 } | 967 } |
| 968 _remainder = a; | 968 _remainder = a; |
| 969 } | 969 } |
| 970 return c; | 970 return c; |
| 971 } | 971 } |
| 972 | 972 |
| (...skipping 11 matching lines...) Expand all Loading... |
| 984 return -1; | 984 return -1; |
| 985 } | 985 } |
| 986 int h = _h; | 986 int h = _h; |
| 987 if ((h & (h - 1)) != 0) { | 987 if ((h & (h - 1)) != 0) { |
| 988 return -1; | 988 return -1; |
| 989 } | 989 } |
| 990 if (h == 0 && m == 0 && l == 0) { | 990 if (h == 0 && m == 0 && l == 0) { |
| 991 return -1; | 991 return -1; |
| 992 } | 992 } |
| 993 if (h == 0 && m == 0 && l != 0) { | 993 if (h == 0 && m == 0 && l != 0) { |
| 994 return int32._numberOfTrailingZeros(l); | 994 return Int32._numberOfTrailingZeros(l); |
| 995 } | 995 } |
| 996 if (h == 0 && m != 0 && l == 0) { | 996 if (h == 0 && m != 0 && l == 0) { |
| 997 return int32._numberOfTrailingZeros(m) + _BITS; | 997 return Int32._numberOfTrailingZeros(m) + _BITS; |
| 998 } | 998 } |
| 999 if (h != 0 && m == 0 && l == 0) { | 999 if (h != 0 && m == 0 && l == 0) { |
| 1000 return int32._numberOfTrailingZeros(h) + _BITS01; | 1000 return Int32._numberOfTrailingZeros(h) + _BITS01; |
| 1001 } | 1001 } |
| 1002 | 1002 |
| 1003 return -1; | 1003 return -1; |
| 1004 } | 1004 } |
| 1005 | 1005 |
| 1006 static int64 _divMod(int64 a, int64 b, bool computeRemainder) { | 1006 static Int64 _divMod(Int64 a, Int64 b, bool computeRemainder) { |
| 1007 if (b.isZero) { | 1007 if (b.isZero) { |
| 1008 throw new IntegerDivisionByZeroException(); | 1008 throw new IntegerDivisionByZeroException(); |
| 1009 } | 1009 } |
| 1010 if (a.isZero) { | 1010 if (a.isZero) { |
| 1011 if (computeRemainder) { | 1011 if (computeRemainder) { |
| 1012 _remainder = ZERO; | 1012 _remainder = ZERO; |
| 1013 } | 1013 } |
| 1014 return ZERO; | 1014 return ZERO; |
| 1015 } | 1015 } |
| 1016 // MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0. | 1016 // MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0. |
| 1017 if (b.isMinValue) { | 1017 if (b.isMinValue) { |
| 1018 return a._divModByMinValue(computeRemainder); | 1018 return a._divModByMinValue(computeRemainder); |
| 1019 } | 1019 } |
| 1020 // Normalize b to abs(b), keeping track of the parity in 'negative'. | 1020 // Normalize b to abs(b), keeping track of the parity in 'negative'. |
| 1021 // We can do this because we have already ensured that b != MIN_VALUE. | 1021 // We can do this because we have already ensured that b != MIN_VALUE. |
| 1022 bool negative = false; | 1022 bool negative = false; |
| 1023 if (b.isNegative) { | 1023 if (b.isNegative) { |
| 1024 b = -b; | 1024 b = -b; |
| 1025 negative = !negative; | 1025 negative = !negative; |
| 1026 } | 1026 } |
| 1027 // If b == 2^n, bpower will be n, otherwise it will be -1. | 1027 // If b == 2^n, bpower will be n, otherwise it will be -1. |
| 1028 int bpower = b._powerOfTwo(); | 1028 int bpower = b._powerOfTwo(); |
| 1029 | 1029 |
| 1030 // True if the original value of a is negative. | 1030 // True if the original value of a is negative. |
| 1031 bool aIsNegative = false; | 1031 bool aIsNegative = false; |
| 1032 // True if the original value of a is int64.MIN_VALUE. | 1032 // True if the original value of a is Int64.MIN_VALUE. |
| 1033 bool aIsMinValue = false; | 1033 bool aIsMinValue = false; |
| 1034 | 1034 |
| 1035 /* | 1035 /* |
| 1036 * Normalize a to a positive value, keeping track of the sign change in | 1036 * Normalize a to a positive value, keeping track of the sign change in |
| 1037 * 'negative' (which tracks the sign of both a and b and is used to | 1037 * 'negative' (which tracks the sign of both a and b and is used to |
| 1038 * determine the sign of the quotient) and 'aIsNegative' (which is used to | 1038 * determine the sign of the quotient) and 'aIsNegative' (which is used to |
| 1039 * determine the sign of the remainder). | 1039 * determine the sign of the remainder). |
| 1040 * | 1040 * |
| 1041 * For all values of a except MIN_VALUE, we can just negate a and modify | 1041 * For all values of a except MIN_VALUE, we can just negate a and modify |
| 1042 * negative and aIsNegative appropriately. When a == MIN_VALUE, negation is | 1042 * negative and aIsNegative appropriately. When a == MIN_VALUE, negation is |
| 1043 * not possible without overflowing 64 bits, so instead of computing | 1043 * not possible without overflowing 64 bits, so instead of computing |
| 1044 * abs(MIN_VALUE) / abs(b) we compute (abs(MIN_VALUE) - 1) / abs(b). The | 1044 * abs(MIN_VALUE) / abs(b) we compute (abs(MIN_VALUE) - 1) / abs(b). The |
| 1045 * only circumstance under which these quotients differ is when b is a power | 1045 * only circumstance under which these quotients differ is when b is a power |
| 1046 * of two, which will divide abs(MIN_VALUE) == 2^64 exactly. In this case, | 1046 * of two, which will divide abs(MIN_VALUE) == 2^64 exactly. In this case, |
| 1047 * we can get the proper result by shifting MIN_VALUE in unsigned fashion. | 1047 * we can get the proper result by shifting MIN_VALUE in unsigned fashion. |
| 1048 * | 1048 * |
| 1049 * We make a single copy of a before the first operation that needs to | 1049 * We make a single copy of a before the first operation that needs to |
| 1050 * modify its value. | 1050 * modify its value. |
| 1051 */ | 1051 */ |
| 1052 bool aIsCopy = false; | 1052 bool aIsCopy = false; |
| 1053 if (a.isMinValue) { | 1053 if (a.isMinValue) { |
| 1054 aIsMinValue = true; | 1054 aIsMinValue = true; |
| 1055 aIsNegative = true; | 1055 aIsNegative = true; |
| 1056 // If b is not a power of two, treat -a as MAX_VALUE (instead of the | 1056 // If b is not a power of two, treat -a as MAX_VALUE (instead of the |
| 1057 // actual value (MAX_VALUE + 1)). | 1057 // actual value (MAX_VALUE + 1)). |
| 1058 if (bpower == -1) { | 1058 if (bpower == -1) { |
| 1059 a = new int64._copy(MAX_VALUE); | 1059 a = new Int64._copy(MAX_VALUE); |
| 1060 aIsCopy = true; | 1060 aIsCopy = true; |
| 1061 negative = !negative; | 1061 negative = !negative; |
| 1062 } else { | 1062 } else { |
| 1063 // Signed shift of MIN_VALUE produces the right answer. | 1063 // Signed shift of MIN_VALUE produces the right answer. |
| 1064 int64 c = a >> bpower; | 1064 Int64 c = a >> bpower; |
| 1065 if (negative) { | 1065 if (negative) { |
| 1066 c._negate(); | 1066 c._negate(); |
| 1067 } | 1067 } |
| 1068 if (computeRemainder) { | 1068 if (computeRemainder) { |
| 1069 _remainder = ZERO; | 1069 _remainder = ZERO; |
| 1070 } | 1070 } |
| 1071 return c; | 1071 return c; |
| 1072 } | 1072 } |
| 1073 } else if (a.isNegative) { | 1073 } else if (a.isNegative) { |
| 1074 aIsNegative = true; | 1074 aIsNegative = true; |
| 1075 a = -a; | 1075 a = -a; |
| 1076 aIsCopy = true; | 1076 aIsCopy = true; |
| 1077 negative = !negative; | 1077 negative = !negative; |
| 1078 } | 1078 } |
| 1079 | 1079 |
| 1080 // Now both a and b are non-negative. | 1080 // Now both a and b are non-negative. |
| 1081 // If b is a power of two, just shift. | 1081 // If b is a power of two, just shift. |
| 1082 if (bpower != -1) { | 1082 if (bpower != -1) { |
| 1083 return _divModByShift(a, bpower, negative, aIsCopy, aIsNegative, | 1083 return _divModByShift(a, bpower, negative, aIsCopy, aIsNegative, |
| 1084 computeRemainder); | 1084 computeRemainder); |
| 1085 } | 1085 } |
| 1086 | 1086 |
| 1087 // If a < b, the quotient is 0 and the remainder is a. | 1087 // If a < b, the quotient is 0 and the remainder is a. |
| 1088 if (a < b) { | 1088 if (a < b) { |
| 1089 if (computeRemainder) { | 1089 if (computeRemainder) { |
| 1090 if (aIsNegative) { | 1090 if (aIsNegative) { |
| 1091 _remainder = -a; | 1091 _remainder = -a; |
| 1092 } else { | 1092 } else { |
| 1093 _remainder = aIsCopy ? a : new int64._copy(a); | 1093 _remainder = aIsCopy ? a : new Int64._copy(a); |
| 1094 } | 1094 } |
| 1095 } | 1095 } |
| 1096 return ZERO; | 1096 return ZERO; |
| 1097 } | 1097 } |
| 1098 | 1098 |
| 1099 // Generate the quotient using bit-at-a-time long division. | 1099 // Generate the quotient using bit-at-a-time long division. |
| 1100 return _divModHelper(aIsCopy ? a : new int64._copy(a), b, negative, | 1100 return _divModHelper(aIsCopy ? a : new Int64._copy(a), b, negative, |
| 1101 aIsNegative, aIsMinValue, computeRemainder); | 1101 aIsNegative, aIsMinValue, computeRemainder); |
| 1102 } | 1102 } |
| 1103 } | 1103 } |
| OLD | NEW |