| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 /** | |
| 6 * An immutable 64-bit signed integer, in the range [-2^63, 2^63 - 1]. | |
| 7 * Arithmetic operations may overflow in order to maintain this range. | |
| 8 */ | |
| 9 class int64 implements intx { | |
| 10 | |
| 11 // A 64-bit integer is represented internally as three non-negative | |
| 12 // integers, storing the 22 low, 22 middle, and 20 high bits of the | |
| 13 // 64-bit value. _l (low) and _m (middle) are in the range | |
| 14 // [0, 2^22 - 1] and _h (high) is in the range [0, 2^20 - 1]. | |
| 15 int _l, _m, _h; | |
| 16 | |
| 17 // Note: instances of int64 are immutable outside of this library, | |
| 18 // therefore we may return a reference to an existing instance. | |
| 19 // We take care to perform mutation only on internally-generated | |
| 20 // instances before they are exposed to external code. | |
| 21 | |
| 22 // Note: several functions require _BITS == 22 -- do not change this value. | |
| 23 static final int _BITS = 22; | |
| 24 static final int _BITS01 = 44; // 2 * _BITS | |
| 25 static final int _BITS2 = 20; // 64 - _BITS01 | |
| 26 static final int _MASK = 4194303; // (1 << _BITS) - 1 | |
| 27 static final int _MASK_2 = 1048575; // (1 << _BITS2) - 1 | |
| 28 static final int _SIGN_BIT = 19; // _BITS2 - 1 | |
| 29 static final int _SIGN_BIT_VALUE = 524288; // 1 << _SIGN_BIT | |
| 30 | |
| 31 // Cached constants | |
| 32 static int64 _MAX_VALUE; | |
| 33 static int64 _MIN_VALUE; | |
| 34 static int64 _ZERO; | |
| 35 static int64 _ONE; | |
| 36 static int64 _TWO; | |
| 37 | |
| 38 // Precompute the radix strings for MIN_VALUE to avoid the problem | |
| 39 // of overflow of -MIN_VALUE. | |
| 40 static List<String> _minValues = const <String>[ | |
| 41 null, null, | |
| 42 "-1000000000000000000000000000000000000000000000000000000000000000", // 2 | |
| 43 "-2021110011022210012102010021220101220222", // base 3 | |
| 44 "-20000000000000000000000000000000", // base 4 | |
| 45 "-1104332401304422434310311213", // base 5 | |
| 46 "-1540241003031030222122212", // base 6 | |
| 47 "-22341010611245052052301", // base 7 | |
| 48 "-1000000000000000000000", // base 8 | |
| 49 "-67404283172107811828", // base 9 | |
| 50 "-9223372036854775808", // base 10 | |
| 51 "-1728002635214590698", // base 11 | |
| 52 "-41A792678515120368", // base 12 | |
| 53 "-10B269549075433C38", // base 13 | |
| 54 "-4340724C6C71DC7A8", // base 14 | |
| 55 "-160E2AD3246366808", // base 15 | |
| 56 "-8000000000000000" // base 16 | |
| 57 ]; | |
| 58 | |
| 59 // The remainder of the last divide operation. | |
| 60 static int64 _remainder; | |
| 61 | |
| 62 /** | |
| 63 * The maximum positive value attainable by an [int64], namely | |
| 64 * 9,223,372,036,854,775,807. | |
| 65 */ | |
| 66 static int64 get MAX_VALUE() { | |
| 67 if (_MAX_VALUE == null) { | |
| 68 _MAX_VALUE = new int64._bits(_MASK, _MASK, _MASK_2 >> 1); | |
| 69 } | |
| 70 return _MAX_VALUE; | |
| 71 } | |
| 72 | |
| 73 /** | |
| 74 * The minimum positive value attainable by an [int64], namely | |
| 75 * -9,223,372,036,854,775,808. | |
| 76 */ | |
| 77 static int64 get MIN_VALUE() { | |
| 78 if (_MIN_VALUE == null) { | |
| 79 _MIN_VALUE = new int64._bits(0, 0, _SIGN_BIT_VALUE); | |
| 80 } | |
| 81 return _MIN_VALUE; | |
| 82 } | |
| 83 | |
| 84 /** | |
| 85 * An [int64] constant equal to 0. | |
| 86 */ | |
| 87 static int64 get ZERO() { | |
| 88 if (_ZERO == null) { | |
| 89 _ZERO = new int64(); | |
| 90 } | |
| 91 return _ZERO; | |
| 92 } | |
| 93 | |
| 94 /** | |
| 95 * An [int64] constant equal to 1. | |
| 96 */ | |
| 97 static int64 get ONE() { | |
| 98 if (_ONE == null) { | |
| 99 _ONE = new int64._bits(1, 0, 0); | |
| 100 } | |
| 101 return _ONE; | |
| 102 } | |
| 103 | |
| 104 /** | |
| 105 * An [int64] constant equal to 2. | |
| 106 */ | |
| 107 static int64 get TWO() { | |
| 108 if (_TWO == null) { | |
| 109 _TWO = new int64._bits(2, 0, 0); | |
| 110 } | |
| 111 return _TWO; | |
| 112 } | |
| 113 | |
| 114 /** | |
| 115 * Parses a [String] in a given [radix] between 2 and 16 and returns an | |
| 116 * [int64]. | |
| 117 */ | |
| 118 // TODO(rice) - make this faster by converting several digits at once. | |
| 119 static int64 parseRadix(String s, int radix) { | |
| 120 if ((radix <= 1) || (radix > 16)) { | |
| 121 throw "Bad radix: $radix"; | |
| 122 } | |
| 123 int64 x = ZERO; | |
| 124 int i = 0; | |
| 125 bool negative = false; | |
| 126 if (s[0] == '-') { | |
| 127 negative = true; | |
| 128 i++; | |
| 129 } | |
| 130 for (; i < s.length; i++) { | |
| 131 int c = s.charCodeAt(i); | |
| 132 int digit = int32._decodeHex(c); | |
| 133 if (digit < 0 || digit >= radix) { | |
| 134 throw new Exception("Non-radix char code: $c"); | |
| 135 } | |
| 136 x = (x * radix) + digit; | |
| 137 } | |
| 138 return negative ? -x : x; | |
| 139 } | |
| 140 | |
| 141 /** | |
| 142 * Parses a decimal [String] and returns an [int64]. | |
| 143 */ | |
| 144 static int64 parseInt(String s) => parseRadix(s, 10); | |
| 145 | |
| 146 /** | |
| 147 * Parses a hexadecimal [String] and returns an [int64]. | |
| 148 */ | |
| 149 static int64 parseHex(String s) => parseRadix(s, 16); | |
| 150 | |
| 151 // | |
| 152 // Public constructors | |
| 153 // | |
| 154 | |
| 155 /** | |
| 156 * Constructs an [int64] equal to 0. | |
| 157 */ | |
| 158 int64() : _l = 0, _m = 0, _h = 0; | |
| 159 | |
| 160 /** | |
| 161 * Constructs an [int64] with a given [int] value. | |
| 162 */ | |
| 163 int64.fromInt(int value) { | |
| 164 bool negative = false; | |
| 165 if (value < 0) { | |
| 166 negative = true; | |
| 167 value = -value - 1; | |
| 168 } | |
| 169 if (_haveBigInts) { | |
| 170 _l = value & _MASK; | |
| 171 _m = (value >> _BITS) & _MASK; | |
| 172 _h = (value >> _BITS01) & _MASK_2; | |
| 173 } else { | |
| 174 // Avoid using bitwise operations that coerce their input to 32 bits. | |
| 175 _h = value ~/ 17592186044416; // 2^44 | |
| 176 value -= _h * 17592186044416; | |
| 177 _m = value ~/ 4194304; // 2^22 | |
| 178 value -= _m * 4194304; | |
| 179 _l = value; | |
| 180 } | |
| 181 | |
| 182 if (negative) { | |
| 183 _l = ~_l & _MASK; | |
| 184 _m = ~_m & _MASK; | |
| 185 _h = ~_h & _MASK_2; | |
| 186 } | |
| 187 } | |
| 188 | |
| 189 factory int64.fromBytes(List<int> bytes) { | |
| 190 int top = bytes[7] & 0xff; | |
| 191 top <<= 8; | |
| 192 top |= bytes[6] & 0xff; | |
| 193 top <<= 8; | |
| 194 top |= bytes[5] & 0xff; | |
| 195 top <<= 8; | |
| 196 top |= bytes[4] & 0xff; | |
| 197 | |
| 198 int bottom = bytes[3] & 0xff; | |
| 199 bottom <<= 8; | |
| 200 bottom |= bytes[2] & 0xff; | |
| 201 bottom <<= 8; | |
| 202 bottom |= bytes[1] & 0xff; | |
| 203 bottom <<= 8; | |
| 204 bottom |= bytes[0] & 0xff; | |
| 205 | |
| 206 return new int64.fromInts(top, bottom); | |
| 207 } | |
| 208 | |
| 209 factory int64.fromBytesBigEndian(List<int> bytes) { | |
| 210 int top = bytes[0] & 0xff; | |
| 211 top <<= 8; | |
| 212 top |= bytes[1] & 0xff; | |
| 213 top <<= 8; | |
| 214 top |= bytes[2] & 0xff; | |
| 215 top <<= 8; | |
| 216 top |= bytes[3] & 0xff; | |
| 217 | |
| 218 int bottom = bytes[4] & 0xff; | |
| 219 bottom <<= 8; | |
| 220 bottom |= bytes[5] & 0xff; | |
| 221 bottom <<= 8; | |
| 222 bottom |= bytes[6] & 0xff; | |
| 223 bottom <<= 8; | |
| 224 bottom |= bytes[7] & 0xff; | |
| 225 | |
| 226 return new int64.fromInts(top, bottom); | |
| 227 } | |
| 228 | |
| 229 /** | |
| 230 * Constructs an [int64] from a pair of 32-bit integers having the value | |
| 231 * [:((top & 0xffffffff) << 32) | (bottom & 0xffffffff):]. | |
| 232 */ | |
| 233 int64.fromInts(int top, int bottom) { | |
| 234 top &= 0xffffffff; | |
| 235 bottom &= 0xffffffff; | |
| 236 _l = bottom & _MASK; | |
| 237 _m = ((top & 0xfff) << 10) | ((bottom >> _BITS) & 0x3ff); | |
| 238 _h = (top >> 12) & _MASK_2; | |
| 239 } | |
| 240 | |
| 241 int64 _promote(other) { | |
| 242 if (other == null) { | |
| 243 throw new NullPointerException(); | |
| 244 } else if (other is intx) { | |
| 245 other = other.toInt64(); | |
| 246 } else if (other is int) { | |
| 247 other = new int64.fromInt(other); | |
| 248 } | |
| 249 if (other is !int64) { | |
| 250 throw new Exception("Can't promote $other to int64"); | |
| 251 } | |
| 252 return other; | |
| 253 } | |
| 254 | |
| 255 int64 operator +(other) { | |
| 256 int64 o = _promote(other); | |
| 257 int sum0 = _l + o._l; | |
| 258 int sum1 = _m + o._m + _shiftRight(sum0, _BITS); | |
| 259 int sum2 = _h + o._h + _shiftRight(sum1, _BITS); | |
| 260 | |
| 261 int64 result = new int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); | |
| 262 return result; | |
| 263 } | |
| 264 | |
| 265 int64 operator -(other) { | |
| 266 int64 o = _promote(other); | |
| 267 | |
| 268 int sum0 = _l - o._l; | |
| 269 int sum1 = _m - o._m + _shiftRight(sum0, _BITS); | |
| 270 int sum2 = _h - o._h + _shiftRight(sum1, _BITS); | |
| 271 | |
| 272 int64 result = new int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); | |
| 273 return result; | |
| 274 } | |
| 275 | |
| 276 int64 operator negate() { | |
| 277 // Like 0 - this. | |
| 278 int sum0 = -_l; | |
| 279 int sum1 = -_m + _shiftRight(sum0, _BITS); | |
| 280 int sum2 = -_h + _shiftRight(sum1, _BITS); | |
| 281 | |
| 282 return new int64._bits(sum0 & _MASK, sum1 & _MASK, sum2 & _MASK_2); | |
| 283 } | |
| 284 | |
| 285 int64 operator *(other) { | |
| 286 int64 o = _promote(other); | |
| 287 // Grab 13-bit chunks. | |
| 288 int a0 = _l & 0x1fff; | |
| 289 int a1 = (_l >> 13) | ((_m & 0xf) << 9); | |
| 290 int a2 = (_m >> 4) & 0x1fff; | |
| 291 int a3 = (_m >> 17) | ((_h & 0xff) << 5); | |
| 292 int a4 = (_h & 0xfff00) >> 8; | |
| 293 | |
| 294 int b0 = o._l & 0x1fff; | |
| 295 int b1 = (o._l >> 13) | ((o._m & 0xf) << 9); | |
| 296 int b2 = (o._m >> 4) & 0x1fff; | |
| 297 int b3 = (o._m >> 17) | ((o._h & 0xff) << 5); | |
| 298 int b4 = (o._h & 0xfff00) >> 8; | |
| 299 | |
| 300 // Compute partial products. | |
| 301 // Optimization: if b is small, avoid multiplying by parts that are 0. | |
| 302 int p0 = a0 * b0; // << 0 | |
| 303 int p1 = a1 * b0; // << 13 | |
| 304 int p2 = a2 * b0; // << 26 | |
| 305 int p3 = a3 * b0; // << 39 | |
| 306 int p4 = a4 * b0; // << 52 | |
| 307 | |
| 308 if (b1 != 0) { | |
| 309 p1 += a0 * b1; | |
| 310 p2 += a1 * b1; | |
| 311 p3 += a2 * b1; | |
| 312 p4 += a3 * b1; | |
| 313 } | |
| 314 if (b2 != 0) { | |
| 315 p2 += a0 * b2; | |
| 316 p3 += a1 * b2; | |
| 317 p4 += a2 * b2; | |
| 318 } | |
| 319 if (b3 != 0) { | |
| 320 p3 += a0 * b3; | |
| 321 p4 += a1 * b3; | |
| 322 } | |
| 323 if (b4 != 0) { | |
| 324 p4 += a0 * b4; | |
| 325 } | |
| 326 | |
| 327 // Accumulate into 22-bit chunks: | |
| 328 // .........................................c10|...................c00| | |
| 329 // |....................|..................xxxx|xxxxxxxxxxxxxxxxxxxxxx| p0 | |
| 330 // |....................|......................|......................| | |
| 331 // |....................|...................c11|......c01.............| | |
| 332 // |....................|....xxxxxxxxxxxxxxxxxx|xxxxxxxxx.............| p1 | |
| 333 // |....................|......................|......................| | |
| 334 // |.................c22|...............c12....|......................| | |
| 335 // |..........xxxxxxxxxx|xxxxxxxxxxxxxxxxxx....|......................| p2 | |
| 336 // |....................|......................|......................| | |
| 337 // |.................c23|..c13.................|......................| | |
| 338 // |xxxxxxxxxxxxxxxxxxxx|xxxxx.................|......................| p3 | |
| 339 // |....................|......................|......................| | |
| 340 // |.........c24........|......................|......................| | |
| 341 // |xxxxxxxxxxxx........|......................|......................| p4 | |
| 342 | |
| 343 int c00 = p0 & 0x3fffff; | |
| 344 int c01 = (p1 & 0x1ff) << 13; | |
| 345 int c0 = c00 + c01; | |
| 346 | |
| 347 int c10 = p0 >> 22; | |
| 348 int c11 = p1 >> 9; | |
| 349 int c12 = (p2 & 0x3ffff) << 4; | |
| 350 int c13 = (p3 & 0x1f) << 17; | |
| 351 int c1 = c10 + c11 + c12 + c13; | |
| 352 | |
| 353 int c22 = p2 >> 18; | |
| 354 int c23 = p3 >> 5; | |
| 355 int c24 = (p4 & 0xfff) << 8; | |
| 356 int c2 = c22 + c23 + c24; | |
| 357 | |
| 358 // Propagate high bits from c0 -> c1, c1 -> c2. | |
| 359 c1 += c0 >> _BITS; | |
| 360 c0 &= _MASK; | |
| 361 c2 += c1 >> _BITS; | |
| 362 c1 &= _MASK; | |
| 363 c2 &= _MASK_2; | |
| 364 | |
| 365 return new int64._bits(c0, c1, c2); | |
| 366 } | |
| 367 | |
| 368 int64 operator %(other) { | |
| 369 if (other.isZero()) { | |
| 370 throw new IntegerDivisionByZeroException(); | |
| 371 } | |
| 372 if (this.isZero()) { | |
| 373 return ZERO; | |
| 374 } | |
| 375 int64 o = _promote(other).abs(); | |
| 376 _divMod(this, o, true); | |
| 377 return _remainder < 0 ? (_remainder + o) : _remainder; | |
| 378 } | |
| 379 | |
| 380 int64 operator ~/(other) => _divMod(this, _promote(other), false); | |
| 381 | |
| 382 // int64 remainder(other) => this - (this ~/ other) * other; | |
| 383 int64 remainder(other) { | |
| 384 if (other.isZero()) { | |
| 385 throw new IntegerDivisionByZeroException(); | |
| 386 } | |
| 387 int64 o = _promote(other).abs(); | |
| 388 _divMod(this, o, true); | |
| 389 return _remainder; | |
| 390 } | |
| 391 | |
| 392 int64 operator &(other) { | |
| 393 int64 o = _promote(other); | |
| 394 int a0 = _l & o._l; | |
| 395 int a1 = _m & o._m; | |
| 396 int a2 = _h & o._h; | |
| 397 return new int64._bits(a0, a1, a2); | |
| 398 } | |
| 399 | |
| 400 int64 operator |(other) { | |
| 401 int64 o = _promote(other); | |
| 402 int a0 = _l | o._l; | |
| 403 int a1 = _m | o._m; | |
| 404 int a2 = _h | o._h; | |
| 405 return new int64._bits(a0, a1, a2); | |
| 406 } | |
| 407 | |
| 408 int64 operator ^(other) { | |
| 409 int64 o = _promote(other); | |
| 410 int a0 = _l ^ o._l; | |
| 411 int a1 = _m ^ o._m; | |
| 412 int a2 = _h ^ o._h; | |
| 413 return new int64._bits(a0, a1, a2); | |
| 414 } | |
| 415 | |
| 416 int64 operator ~() { | |
| 417 var result = new int64._bits((~_l) & _MASK, (~_m) & _MASK, (~_h) & _MASK_2); | |
| 418 return result; | |
| 419 } | |
| 420 | |
| 421 int64 operator <<(int n) { | |
| 422 if (n < 0) { | |
| 423 throw new IllegalArgumentException("$n"); | |
| 424 } | |
| 425 n &= 63; | |
| 426 | |
| 427 int res0, res1, res2; | |
| 428 if (n < _BITS) { | |
| 429 res0 = _l << n; | |
| 430 res1 = (_m << n) | (_l >> (_BITS - n)); | |
| 431 res2 = (_h << n) | (_m >> (_BITS - n)); | |
| 432 } else if (n < _BITS01) { | |
| 433 res0 = 0; | |
| 434 res1 = _l << (n - _BITS); | |
| 435 res2 = (_m << (n - _BITS)) | (_l >> (_BITS01 - n)); | |
| 436 } else { | |
| 437 res0 = 0; | |
| 438 res1 = 0; | |
| 439 res2 = _l << (n - _BITS01); | |
| 440 } | |
| 441 | |
| 442 return new int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); | |
| 443 } | |
| 444 | |
| 445 int64 operator >>(int n) { | |
| 446 if (n < 0) { | |
| 447 throw new IllegalArgumentException("$n"); | |
| 448 } | |
| 449 n &= 63; | |
| 450 | |
| 451 int res0, res1, res2; | |
| 452 | |
| 453 // Sign extend h(a). | |
| 454 int a2 = _h; | |
| 455 bool negative = (a2 & _SIGN_BIT_VALUE) != 0; | |
| 456 if (negative) { | |
| 457 a2 += 0x3 << _BITS2; // add extra one bits on the left | |
| 458 } | |
| 459 | |
| 460 if (n < _BITS) { | |
| 461 res2 = _shiftRight(a2, n); | |
| 462 if (negative) { | |
| 463 res2 |= _MASK_2 & ~(_MASK_2 >> n); | |
| 464 } | |
| 465 res1 = _shiftRight(_m, n) | (a2 << (_BITS - n)); | |
| 466 res0 = _shiftRight(_l, n) | (_m << (_BITS - n)); | |
| 467 } else if (n < _BITS01) { | |
| 468 res2 = negative ? _MASK_2 : 0; | |
| 469 res1 = _shiftRight(a2, n - _BITS); | |
| 470 if (negative) { | |
| 471 res1 |= _MASK & ~(_MASK >> (n - _BITS)); | |
| 472 } | |
| 473 res0 = _shiftRight(_m, n - _BITS) | (a2 << (_BITS01 - n)); | |
| 474 } else { | |
| 475 res2 = negative ? _MASK_2 : 0; | |
| 476 res1 = negative ? _MASK : 0; | |
| 477 res0 = _shiftRight(a2, n - _BITS01); | |
| 478 if (negative) { | |
| 479 res0 |= _MASK & ~(_MASK >> (n - _BITS01)); | |
| 480 } | |
| 481 } | |
| 482 | |
| 483 return new int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); | |
| 484 } | |
| 485 | |
| 486 int64 shiftRightUnsigned(int n) { | |
| 487 if (n < 0) { | |
| 488 throw new IllegalArgumentException("$n"); | |
| 489 } | |
| 490 n &= 63; | |
| 491 | |
| 492 int res0, res1, res2; | |
| 493 int a2 = _h & _MASK_2; // Ensure a2 is positive. | |
| 494 if (n < _BITS) { | |
| 495 res2 = a2 >> n; | |
| 496 res1 = (_m >> n) | (a2 << (_BITS - n)); | |
| 497 res0 = (_l >> n) | (_m << (_BITS - n)); | |
| 498 } else if (n < _BITS01) { | |
| 499 res2 = 0; | |
| 500 res1 = a2 >> (n - _BITS); | |
| 501 res0 = (_m >> (n - _BITS)) | (_h << (_BITS01 - n)); | |
| 502 } else { | |
| 503 res2 = 0; | |
| 504 res1 = 0; | |
| 505 res0 = a2 >> (n - _BITS01); | |
| 506 } | |
| 507 | |
| 508 return new int64._bits(res0 & _MASK, res1 & _MASK, res2 & _MASK_2); | |
| 509 } | |
| 510 | |
| 511 /** | |
| 512 * Returns [true] if this [int64] has the same numeric value as the | |
| 513 * given object. The argument may be an [int] or an [intx]. | |
| 514 */ | |
| 515 bool operator ==(other) { | |
| 516 if (other == null) { | |
| 517 return false; | |
| 518 } | |
| 519 int64 o = _promote(other); | |
| 520 return _l == o._l && _m == o._m && _h == o._h; | |
| 521 } | |
| 522 | |
| 523 int compareTo(Comparable other) { | |
| 524 int64 o = _promote(other); | |
| 525 int signa = _h >> (_BITS2 - 1); | |
| 526 int signb = o._h >> (_BITS2 - 1); | |
| 527 if (signa != signb) { | |
| 528 return signa == 0 ? 1 : -1; | |
| 529 } | |
| 530 if (_h > o._h) { | |
| 531 return 1; | |
| 532 } else if (_h < o._h) { | |
| 533 return -1; | |
| 534 } | |
| 535 if (_m > o._m) { | |
| 536 return 1; | |
| 537 } else if (_m < o._m) { | |
| 538 return -1; | |
| 539 } | |
| 540 if (_l > o._l) { | |
| 541 return 1; | |
| 542 } else if (_l < o._l) { | |
| 543 return -1; | |
| 544 } | |
| 545 return 0; | |
| 546 } | |
| 547 | |
| 548 bool operator <(other) { | |
| 549 return this.compareTo(other) < 0; | |
| 550 } | |
| 551 | |
| 552 bool operator <=(other) { | |
| 553 return this.compareTo(other) <= 0; | |
| 554 } | |
| 555 | |
| 556 bool operator >(other) { | |
| 557 return this.compareTo(other) > 0; | |
| 558 } | |
| 559 | |
| 560 bool operator >=(other) { | |
| 561 return this.compareTo(other) >= 0; | |
| 562 } | |
| 563 | |
| 564 bool isEven() => (_l & 0x1) == 0; | |
| 565 bool isMaxValue() => (_h == _MASK_2 >> 1) && _m == _MASK && _l == _MASK; | |
| 566 bool isMinValue() => _h == _SIGN_BIT_VALUE && _m == 0 && _l == 0; | |
| 567 bool isNegative() => (_h >> (_BITS2 - 1)) != 0; | |
| 568 bool isOdd() => (_l & 0x1) == 1; | |
| 569 bool isZero() => _h == 0 && _m == 0 && _l == 0; | |
| 570 | |
| 571 /** | |
| 572 * Returns a hash code based on all the bits of this [int64]. | |
| 573 */ | |
| 574 int hashCode() { | |
| 575 int bottom = ((_m & 0x3ff) << _BITS) | _l; | |
| 576 int top = (_h << 12) | ((_m >> 10) & 0xfff); | |
| 577 return bottom ^ top; | |
| 578 } | |
| 579 | |
| 580 int64 abs() { | |
| 581 return this < 0 ? -this : this; | |
| 582 } | |
| 583 | |
| 584 /** | |
| 585 * Returns the number of leading zeros in this [int64] as an [int] | |
| 586 * between 0 and 64. | |
| 587 */ | |
| 588 int numberOfLeadingZeros() { | |
| 589 int b2 = int32._numberOfLeadingZeros(_h); | |
| 590 if (b2 == 32) { | |
| 591 int b1 = int32._numberOfLeadingZeros(_m); | |
| 592 if (b1 == 32) { | |
| 593 return int32._numberOfLeadingZeros(_l) + 32; | |
| 594 } else { | |
| 595 return b1 + _BITS2 - (32 - _BITS); | |
| 596 } | |
| 597 } else { | |
| 598 return b2 - (32 - _BITS2); | |
| 599 } | |
| 600 } | |
| 601 | |
| 602 /** | |
| 603 * Returns the number of trailing zeros in this [int64] as an [int] | |
| 604 * between 0 and 64. | |
| 605 */ | |
| 606 int numberOfTrailingZeros() { | |
| 607 int zeros = int32._numberOfTrailingZeros(_l); | |
| 608 if (zeros < 32) { | |
| 609 return zeros; | |
| 610 } | |
| 611 | |
| 612 zeros = int32._numberOfTrailingZeros(_m); | |
| 613 if (zeros < 32) { | |
| 614 return _BITS + zeros; | |
| 615 } | |
| 616 | |
| 617 zeros = int32._numberOfTrailingZeros(_h); | |
| 618 if (zeros < 32) { | |
| 619 return _BITS01 + zeros; | |
| 620 } | |
| 621 // All zeros | |
| 622 return 64; | |
| 623 } | |
| 624 | |
| 625 List<int> toBytes() { | |
| 626 List<int> result = new List<int>(8); | |
| 627 result[0] = _l & 0xff; | |
| 628 result[1] = (_l >> 8) & 0xff; | |
| 629 result[2] = ((_m << 6) & 0xfc) | ((_l >> 16) & 0x3f); | |
| 630 result[3] = (_m >> 2) & 0xff; | |
| 631 result[4] = (_m >> 10) & 0xff; | |
| 632 result[5] = ((_h << 4) & 0xf0) | ((_m >> 18) & 0xf); | |
| 633 result[6] = (_h >> 4) & 0xff; | |
| 634 result[7] = (_h >> 12) & 0xff; | |
| 635 return result; | |
| 636 } | |
| 637 | |
| 638 int toInt() { | |
| 639 int l = _l; | |
| 640 int m = _m; | |
| 641 int h = _h; | |
| 642 bool negative = false; | |
| 643 if ((_h & _SIGN_BIT_VALUE) != 0) { | |
| 644 l = ~_l & _MASK; | |
| 645 m = ~_m & _MASK; | |
| 646 h = ~_h & _MASK_2; | |
| 647 negative = true; | |
| 648 } | |
| 649 | |
| 650 int result; | |
| 651 if (_haveBigInts) { | |
| 652 result = (h << _BITS01) | (m << _BITS) | l; | |
| 653 } else { | |
| 654 result = (h * 17592186044416) + (m * 4194304) + l; | |
| 655 } | |
| 656 return negative ? -result - 1 : result; | |
| 657 } | |
| 658 | |
| 659 /** | |
| 660 * Returns an [int32] containing the low 32 bits of this [int64]. | |
| 661 */ | |
| 662 int32 toInt32() { | |
| 663 return new int32.fromInt(((_m & 0x3ff) << _BITS) | _l); | |
| 664 } | |
| 665 | |
| 666 /** | |
| 667 * Returns [this]. | |
| 668 */ | |
| 669 int64 toInt64() => this; | |
| 670 | |
| 671 /** | |
| 672 * Returns the value of this [int64] as a decimal [String]. | |
| 673 */ | |
| 674 // TODO(rice) - Make this faster by converting several digits at once. | |
| 675 String toString() { | |
| 676 int64 a = this; | |
| 677 if (a.isZero()) { | |
| 678 return "0"; | |
| 679 } | |
| 680 if (a.isMinValue()) { | |
| 681 return "-9223372036854775808"; | |
| 682 } | |
| 683 | |
| 684 String result = ""; | |
| 685 bool negative = false; | |
| 686 if (a.isNegative()) { | |
| 687 negative = true; | |
| 688 a = -a; | |
| 689 } | |
| 690 | |
| 691 int64 ten = new int64._bits(10, 0, 0); | |
| 692 while (!a.isZero()) { | |
| 693 a = _divMod(a, ten, true); | |
| 694 result = "${_remainder._l}$result"; | |
| 695 } | |
| 696 if (negative) { | |
| 697 result = "-$result"; | |
| 698 } | |
| 699 return result; | |
| 700 } | |
| 701 | |
| 702 // TODO(rice) - Make this faster by avoiding arithmetic. | |
| 703 String toHexString() { | |
| 704 int64 x = new int64._copy(this); | |
| 705 if (isZero()) { | |
| 706 return "0"; | |
| 707 } | |
| 708 String hexStr = ""; | |
| 709 int64 digit_f = new int64.fromInt(0xf); | |
| 710 while (!x.isZero()) { | |
| 711 int digit = x._l & 0xf; | |
| 712 hexStr = "${_hexDigit(digit)}$hexStr"; | |
| 713 x = x.shiftRightUnsigned(4); | |
| 714 } | |
| 715 return hexStr; | |
| 716 } | |
| 717 | |
| 718 String toRadixString(int radix) { | |
| 719 if ((radix <= 1) || (radix > 16)) { | |
| 720 throw "Bad radix: $radix"; | |
| 721 } | |
| 722 int64 a = this; | |
| 723 if (a.isZero()) { | |
| 724 return "0"; | |
| 725 } | |
| 726 if (a.isMinValue()) { | |
| 727 return _minValues[radix]; | |
| 728 } | |
| 729 | |
| 730 String result = ""; | |
| 731 bool negative = false; | |
| 732 if (a.isNegative()) { | |
| 733 negative = true; | |
| 734 a = -a; | |
| 735 } | |
| 736 | |
| 737 int64 r = new int64._bits(radix, 0, 0); | |
| 738 while (!a.isZero()) { | |
| 739 a = _divMod(a, r, true); | |
| 740 result = "${_hexDigit(_remainder._l)}$result"; | |
| 741 } | |
| 742 return negative ? "-$result" : result; | |
| 743 } | |
| 744 | |
| 745 String toDebugString() { | |
| 746 return "int64[_l=$_l, _m=$_m, _h=$_h]"; | |
| 747 } | |
| 748 | |
| 749 /** | |
| 750 * Constructs an [int64] with a given bitwise representation. No validation | |
| 751 * is performed. | |
| 752 */ | |
| 753 int64._bits(int this._l, int this._m, int this._h); | |
| 754 | |
| 755 /** | |
| 756 * Constructs an [int64] with the same value as an existing [int64]. | |
| 757 */ | |
| 758 int64._copy(int64 other) { | |
| 759 _l = other._l; | |
| 760 _m = other._m; | |
| 761 _h = other._h; | |
| 762 } | |
| 763 | |
| 764 // Determine whether the platform supports ints greater than 2^53 | |
| 765 // without loss of precision. | |
| 766 static bool _haveBigIntsCached = null; | |
| 767 | |
| 768 static bool get _haveBigInts() { | |
| 769 if (_haveBigIntsCached == null) { | |
| 770 var x = 9007199254740992; | |
| 771 // Defeat compile-time constant folding. | |
| 772 if (2 + 2 != 4) { | |
| 773 x = 0; | |
| 774 } | |
| 775 var y = x + 1; | |
| 776 var same = y == x; | |
| 777 _haveBigIntsCached = !same; | |
| 778 } | |
| 779 return _haveBigIntsCached; | |
| 780 } | |
| 781 | |
| 782 String _hexDigit(int digit) => "0123456789ABCDEF"[digit]; | |
| 783 | |
| 784 // Implementation of '~/' and '%'. | |
| 785 | |
| 786 // Note: mutates [this]. | |
| 787 void _negate() { | |
| 788 int neg0 = (~_l + 1) & _MASK; | |
| 789 int neg1 = (~_m + (neg0 == 0 ? 1 : 0)) & _MASK; | |
| 790 int neg2 = (~_h + ((neg0 == 0 && neg1 == 0) ? 1 : 0)) & _MASK_2; | |
| 791 | |
| 792 _l = neg0; | |
| 793 _m = neg1; | |
| 794 _h = neg2; | |
| 795 } | |
| 796 | |
| 797 // Note: mutates [this]. | |
| 798 void _setBit(int bit) { | |
| 799 if (bit < _BITS) { | |
| 800 _l |= 0x1 << bit; | |
| 801 } else if (bit < _BITS01) { | |
| 802 _m |= 0x1 << (bit - _BITS); | |
| 803 } else { | |
| 804 _h |= 0x1 << (bit - _BITS01); | |
| 805 } | |
| 806 } | |
| 807 | |
| 808 // Note: mutates [this]. | |
| 809 void _toShru1() { | |
| 810 int a2 = _h; | |
| 811 int a1 = _m; | |
| 812 int a0 = _l; | |
| 813 | |
| 814 _h = a2 >> 1; | |
| 815 _m = (a1 >> 1) | ((a2 & 0x1) << (_BITS - 1)); | |
| 816 _l = (a0 >> 1) | ((a1 & 0x1) << (_BITS - 1)); | |
| 817 } | |
| 818 | |
| 819 // Work around dart2js bugs with negative arguments to '>>' operator. | |
| 820 static int _shiftRight(int x, int n) { | |
| 821 if (x >= 0) { | |
| 822 return x >> n; | |
| 823 } else { | |
| 824 int shifted = x >> n; | |
| 825 if (shifted >= 0x80000000) { | |
| 826 shifted -= 4294967296; | |
| 827 } | |
| 828 return shifted; | |
| 829 } | |
| 830 } | |
| 831 | |
| 832 /** | |
| 833 * Attempt to subtract b from a if a >= b: | |
| 834 * | |
| 835 * if (a >= b) { | |
| 836 * a -= b; | |
| 837 * return true; | |
| 838 * } else { | |
| 839 * return false; | |
| 840 * } | |
| 841 */ | |
| 842 // Note: mutates [a]. | |
| 843 static bool _trialSubtract(int64 a, int64 b) { | |
| 844 // Early exit. | |
| 845 int sum2 = a._h - b._h; | |
| 846 if (sum2 < 0) { | |
| 847 return false; | |
| 848 } | |
| 849 | |
| 850 int sum0 = a._l - b._l; | |
| 851 int sum1 = a._m - b._m + _shiftRight(sum0, _BITS); | |
| 852 sum2 += _shiftRight(sum1, _BITS); | |
| 853 | |
| 854 if (sum2 < 0) { | |
| 855 return false; | |
| 856 } | |
| 857 | |
| 858 a._l = sum0 & _MASK; | |
| 859 a._m = sum1 & _MASK; | |
| 860 a._h = sum2 & _MASK_2; | |
| 861 | |
| 862 return true; | |
| 863 } | |
| 864 | |
| 865 // Note: mutates [a] via _trialSubtract. | |
| 866 static int64 _divModHelper(int64 a, int64 b, | |
| 867 bool negative, bool aIsNegative, bool aIsMinValue, | |
| 868 bool computeRemainder) { | |
| 869 // Align the leading one bits of a and b by shifting b left. | |
| 870 int shift = b.numberOfLeadingZeros() - a.numberOfLeadingZeros(); | |
| 871 int64 bshift = b << shift; | |
| 872 | |
| 873 // Quotient must be a new instance since we mutate it. | |
| 874 int64 quotient = new int64(); | |
| 875 while (shift >= 0) { | |
| 876 bool gte = _trialSubtract(a, bshift); | |
| 877 if (gte) { | |
| 878 quotient._setBit(shift); | |
| 879 if (a.isZero()) { | |
| 880 break; | |
| 881 } | |
| 882 } | |
| 883 | |
| 884 bshift._toShru1(); | |
| 885 shift--; | |
| 886 } | |
| 887 | |
| 888 if (negative) { | |
| 889 quotient._negate(); | |
| 890 } | |
| 891 | |
| 892 if (computeRemainder) { | |
| 893 if (aIsNegative) { | |
| 894 _remainder = -a; | |
| 895 if (aIsMinValue) { | |
| 896 _remainder = _remainder - ONE; | |
| 897 } | |
| 898 } else { | |
| 899 _remainder = a; | |
| 900 } | |
| 901 } | |
| 902 | |
| 903 return quotient; | |
| 904 } | |
| 905 | |
| 906 int64 _divModByMinValue(bool computeRemainder) { | |
| 907 // MIN_VALUE / MIN_VALUE == 1, remainder = 0 | |
| 908 // (x != MIN_VALUE) / MIN_VALUE == 0, remainder == x | |
| 909 if (isMinValue()) { | |
| 910 if (computeRemainder) { | |
| 911 _remainder = ZERO; | |
| 912 } | |
| 913 return ONE; | |
| 914 } | |
| 915 if (computeRemainder) { | |
| 916 _remainder = this; | |
| 917 } | |
| 918 return ZERO; | |
| 919 } | |
| 920 | |
| 921 /** | |
| 922 * this &= ((1L << bits) - 1) | |
| 923 */ | |
| 924 // Note: mutates [this]. | |
| 925 int64 _maskRight(int bits) { | |
| 926 int b0, b1, b2; | |
| 927 if (bits <= _BITS) { | |
| 928 b0 = _l & ((1 << bits) - 1); | |
| 929 b1 = b2 = 0; | |
| 930 } else if (bits <= _BITS01) { | |
| 931 b0 = _l; | |
| 932 b1 = _m & ((1 << (bits - _BITS)) - 1); | |
| 933 b2 = 0; | |
| 934 } else { | |
| 935 b0 = _l; | |
| 936 b1 = _m; | |
| 937 b2 = _h & ((1 << (bits - _BITS01)) - 1); | |
| 938 } | |
| 939 | |
| 940 _l = b0; | |
| 941 _m = b1; | |
| 942 _h = b2; | |
| 943 } | |
| 944 | |
| 945 int64 _divModByShift(int64 a, int bpower, bool negative, bool aIsCopy, | |
| 946 bool aIsNegative, bool computeRemainder) { | |
| 947 int64 c = a >> bpower; | |
| 948 if (negative) { | |
| 949 c._negate(); | |
| 950 } | |
| 951 | |
| 952 if (computeRemainder) { | |
| 953 if (!aIsCopy) { | |
| 954 a = new int64._copy(a); | |
| 955 } | |
| 956 a._maskRight(bpower); | |
| 957 if (aIsNegative) { | |
| 958 a._negate(); | |
| 959 } | |
| 960 _remainder = a; | |
| 961 } | |
| 962 return c; | |
| 963 } | |
| 964 | |
| 965 /** | |
| 966 * Return the exact log base 2 of this, or -1 if this is not a power of two. | |
| 967 */ | |
| 968 int _powerOfTwo() { | |
| 969 // Power of two or 0. | |
| 970 int l = _l; | |
| 971 if ((l & (l - 1)) != 0) { | |
| 972 return -1; | |
| 973 } | |
| 974 int m = _m; | |
| 975 if ((m & (m - 1)) != 0) { | |
| 976 return -1; | |
| 977 } | |
| 978 int h = _h; | |
| 979 if ((h & (h - 1)) != 0) { | |
| 980 return -1; | |
| 981 } | |
| 982 if (h == 0 && m == 0 && l == 0) { | |
| 983 return -1; | |
| 984 } | |
| 985 if (h == 0 && m == 0 && l != 0) { | |
| 986 return int32._numberOfTrailingZeros(l); | |
| 987 } | |
| 988 if (h == 0 && m != 0 && l == 0) { | |
| 989 return int32._numberOfTrailingZeros(m) + _BITS; | |
| 990 } | |
| 991 if (h != 0 && m == 0 && l == 0) { | |
| 992 return int32._numberOfTrailingZeros(h) + _BITS01; | |
| 993 } | |
| 994 | |
| 995 return -1; | |
| 996 } | |
| 997 | |
| 998 int64 _divMod(int64 a, int64 b, bool computeRemainder) { | |
| 999 if (b.isZero()) { | |
| 1000 throw new IntegerDivisionByZeroException(); | |
| 1001 } | |
| 1002 if (a.isZero()) { | |
| 1003 if (computeRemainder) { | |
| 1004 _remainder = ZERO; | |
| 1005 } | |
| 1006 return ZERO; | |
| 1007 } | |
| 1008 // MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0. | |
| 1009 if (b.isMinValue()) { | |
| 1010 return a._divModByMinValue(computeRemainder); | |
| 1011 } | |
| 1012 // Normalize b to abs(b), keeping track of the parity in 'negative'. | |
| 1013 // We can do this because we have already ensured that b != MIN_VALUE. | |
| 1014 bool negative = false; | |
| 1015 if (b.isNegative()) { | |
| 1016 b = -b; | |
| 1017 negative = !negative; | |
| 1018 } | |
| 1019 // If b == 2^n, bpower will be n, otherwise it will be -1. | |
| 1020 int bpower = b._powerOfTwo(); | |
| 1021 | |
| 1022 // True if the original value of a is negative. | |
| 1023 bool aIsNegative = false; | |
| 1024 // True if the original value of a is int64.MIN_VALUE. | |
| 1025 bool aIsMinValue = false; | |
| 1026 | |
| 1027 /* | |
| 1028 * Normalize a to a positive value, keeping track of the sign change in | |
| 1029 * 'negative' (which tracks the sign of both a and b and is used to | |
| 1030 * determine the sign of the quotient) and 'aIsNegative' (which is used to | |
| 1031 * determine the sign of the remainder). | |
| 1032 * | |
| 1033 * For all values of a except MIN_VALUE, we can just negate a and modify | |
| 1034 * negative and aIsNegative appropriately. When a == MIN_VALUE, negation is | |
| 1035 * not possible without overflowing 64 bits, so instead of computing | |
| 1036 * abs(MIN_VALUE) / abs(b) we compute (abs(MIN_VALUE) - 1) / abs(b). The | |
| 1037 * only circumstance under which these quotients differ is when b is a power | |
| 1038 * of two, which will divide abs(MIN_VALUE) == 2^64 exactly. In this case, | |
| 1039 * we can get the proper result by shifting MIN_VALUE in unsigned fashion. | |
| 1040 * | |
| 1041 * We make a single copy of a before the first operation that needs to | |
| 1042 * modify its value. | |
| 1043 */ | |
| 1044 bool aIsCopy = false; | |
| 1045 if (a.isMinValue()) { | |
| 1046 aIsMinValue = true; | |
| 1047 aIsNegative = true; | |
| 1048 // If b is not a power of two, treat -a as MAX_VALUE (instead of the | |
| 1049 // actual value (MAX_VALUE + 1)). | |
| 1050 if (bpower == -1) { | |
| 1051 a = new int64._copy(MAX_VALUE); | |
| 1052 aIsCopy = true; | |
| 1053 negative = !negative; | |
| 1054 } else { | |
| 1055 // Signed shift of MIN_VALUE produces the right answer. | |
| 1056 int64 c = a >> bpower; | |
| 1057 if (negative) { | |
| 1058 c._negate(); | |
| 1059 } | |
| 1060 if (computeRemainder) { | |
| 1061 _remainder = ZERO; | |
| 1062 } | |
| 1063 return c; | |
| 1064 } | |
| 1065 } else if (a.isNegative()) { | |
| 1066 aIsNegative = true; | |
| 1067 a = -a; | |
| 1068 aIsCopy = true; | |
| 1069 negative = !negative; | |
| 1070 } | |
| 1071 | |
| 1072 // Now both a and b are non-negative. | |
| 1073 // If b is a power of two, just shift. | |
| 1074 if (bpower != -1) { | |
| 1075 return _divModByShift(a, bpower, negative, aIsCopy, aIsNegative, | |
| 1076 computeRemainder); | |
| 1077 } | |
| 1078 | |
| 1079 // If a < b, the quotient is 0 and the remainder is a. | |
| 1080 if (a < b) { | |
| 1081 if (computeRemainder) { | |
| 1082 if (aIsNegative) { | |
| 1083 _remainder = -a; | |
| 1084 } else { | |
| 1085 _remainder = aIsCopy ? a : new int64._copy(a); | |
| 1086 } | |
| 1087 } | |
| 1088 return ZERO; | |
| 1089 } | |
| 1090 | |
| 1091 // Generate the quotient using bit-at-a-time long division. | |
| 1092 return _divModHelper(aIsCopy ? a : new int64._copy(a), b, negative, | |
| 1093 aIsNegative, aIsMinValue, computeRemainder); | |
| 1094 } | |
| 1095 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 10854162:
Move fixnum to from lib/ to pkg/ . Once pub.dartlang.org (Closed)
Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/