| 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 part of fixnum; | |
| 6 | |
| 7 /** | |
| 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. | |
| 10 */ | |
| 11 class Int64 implements IntX { | |
| 12 | |
| 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 | |
| 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]. | |
| 17 // | |
| 18 // The values being assigned to _l, _m and _h in initialization are masked to | |
| 19 // force them into the above ranges. Sometimes we know that the value is a | |
| 20 // small non-negative integer but the dart2js compiler can't infer that, so a | |
| 21 // few of the masking operations are not needed for correctness but are | |
| 22 // helpful for dart2js code quality. | |
| 23 | |
| 24 final int _l, _m, _h; | |
| 25 | |
| 26 // Note: several functions require _BITS == 22 -- do not change this value. | |
| 27 static const int _BITS = 22; | |
| 28 static const int _BITS01 = 44; // 2 * _BITS | |
| 29 static const int _BITS2 = 20; // 64 - _BITS01 | |
| 30 static const int _MASK = 4194303; // (1 << _BITS) - 1 | |
| 31 static const int _MASK2 = 1048575; // (1 << _BITS2) - 1 | |
| 32 static const int _SIGN_BIT = 19; // _BITS2 - 1 | |
| 33 static const int _SIGN_BIT_MASK = 1 << _SIGN_BIT; | |
| 34 | |
| 35 /** | |
| 36 * The maximum positive value attainable by an [Int64], namely | |
| 37 * 9,223,372,036,854,775,807. | |
| 38 */ | |
| 39 static const Int64 MAX_VALUE = const Int64._bits(_MASK, _MASK, _MASK2 >> 1); | |
| 40 | |
| 41 /** | |
| 42 * The minimum positive value attainable by an [Int64], namely | |
| 43 * -9,223,372,036,854,775,808. | |
| 44 */ | |
| 45 static const Int64 MIN_VALUE = const Int64._bits(0, 0, _SIGN_BIT_MASK); | |
| 46 | |
| 47 /** | |
| 48 * An [Int64] constant equal to 0. | |
| 49 */ | |
| 50 static const Int64 ZERO = const Int64._bits(0, 0, 0); | |
| 51 | |
| 52 /** | |
| 53 * An [Int64] constant equal to 1. | |
| 54 */ | |
| 55 static const Int64 ONE = const Int64._bits(1, 0, 0); | |
| 56 | |
| 57 /** | |
| 58 * An [Int64] constant equal to 2. | |
| 59 */ | |
| 60 static const Int64 TWO = const Int64._bits(2, 0, 0); | |
| 61 | |
| 62 /** | |
| 63 * Constructs an [Int64] with a given bitwise representation. No validation | |
| 64 * is performed. | |
| 65 */ | |
| 66 const Int64._bits(int this._l, int this._m, int this._h); | |
| 67 | |
| 68 /** | |
| 69 * Parses a [String] in a given [radix] between 2 and 36 and returns an | |
| 70 * [Int64]. | |
| 71 */ | |
| 72 static Int64 parseRadix(String s, int radix) { | |
| 73 return _parseRadix(s, Int32._validateRadix(radix)); | |
| 74 } | |
| 75 | |
| 76 static Int64 _parseRadix(String s, int radix) { | |
| 77 int i = 0; | |
| 78 bool negative = false; | |
| 79 if (s[0] == '-') { | |
| 80 negative = true; | |
| 81 i++; | |
| 82 } | |
| 83 int d0 = 0, d1 = 0, d2 = 0; // low, middle, high components. | |
| 84 for (; i < s.length; i++) { | |
| 85 int c = s.codeUnitAt(i); | |
| 86 int digit = Int32._decodeDigit(c); | |
| 87 if (digit < 0 || digit >= radix) { | |
| 88 throw new FormatException("Non-radix char code: $c"); | |
| 89 } | |
| 90 | |
| 91 // [radix] and [digit] are at most 6 bits, component is 22, so we can | |
| 92 // multiply and add within 30 bit temporary values. | |
| 93 d0 = d0 * radix + digit; | |
| 94 int carry = d0 >> _BITS; | |
| 95 d0 = _MASK & d0; | |
| 96 | |
| 97 d1 = d1 * radix + carry; | |
| 98 carry = d1 >> _BITS; | |
| 99 d1 = _MASK & d1; | |
| 100 | |
| 101 d2 = d2 * radix + carry; | |
| 102 d2 = _MASK2 & d2; | |
| 103 } | |
| 104 | |
| 105 if (negative) return _negate(d0, d1, d2); | |
| 106 | |
| 107 return Int64._masked(d0, d1, d2); | |
| 108 } | |
| 109 | |
| 110 /** | |
| 111 * Parses a decimal [String] and returns an [Int64]. | |
| 112 */ | |
| 113 static Int64 parseInt(String s) => _parseRadix(s, 10); | |
| 114 | |
| 115 /** | |
| 116 * Parses a hexadecimal [String] and returns an [Int64]. | |
| 117 */ | |
| 118 static Int64 parseHex(String s) => _parseRadix(s, 16); | |
| 119 | |
| 120 // | |
| 121 // Public constructors | |
| 122 // | |
| 123 | |
| 124 /** | |
| 125 * Constructs an [Int64] with a given [int] value; zero by default. | |
| 126 */ | |
| 127 factory Int64([int value=0]) { | |
| 128 int v0 = 0, v1 = 0, v2 = 0; | |
| 129 bool negative = false; | |
| 130 if (value < 0) { | |
| 131 negative = true; | |
| 132 value = -value - 1; | |
| 133 } | |
| 134 // Avoid using bitwise operations that in JavaScript coerce their input to | |
| 135 // 32 bits. | |
| 136 v2 = value ~/ 17592186044416; // 2^44 | |
| 137 value -= v2 * 17592186044416; | |
| 138 v1 = value ~/ 4194304; // 2^22 | |
| 139 value -= v1 * 4194304; | |
| 140 v0 = value; | |
| 141 | |
| 142 if (negative) { | |
| 143 v0 = ~v0; | |
| 144 v1 = ~v1; | |
| 145 v2 = ~v2; | |
| 146 } | |
| 147 return Int64._masked(v0, v1, v2); | |
| 148 } | |
| 149 | |
| 150 factory Int64.fromBytes(List<int> bytes) { | |
| 151 int top = bytes[7] & 0xff; | |
| 152 top <<= 8; | |
| 153 top |= bytes[6] & 0xff; | |
| 154 top <<= 8; | |
| 155 top |= bytes[5] & 0xff; | |
| 156 top <<= 8; | |
| 157 top |= bytes[4] & 0xff; | |
| 158 | |
| 159 int bottom = bytes[3] & 0xff; | |
| 160 bottom <<= 8; | |
| 161 bottom |= bytes[2] & 0xff; | |
| 162 bottom <<= 8; | |
| 163 bottom |= bytes[1] & 0xff; | |
| 164 bottom <<= 8; | |
| 165 bottom |= bytes[0] & 0xff; | |
| 166 | |
| 167 return new Int64.fromInts(top, bottom); | |
| 168 } | |
| 169 | |
| 170 factory Int64.fromBytesBigEndian(List<int> bytes) { | |
| 171 int top = bytes[0] & 0xff; | |
| 172 top <<= 8; | |
| 173 top |= bytes[1] & 0xff; | |
| 174 top <<= 8; | |
| 175 top |= bytes[2] & 0xff; | |
| 176 top <<= 8; | |
| 177 top |= bytes[3] & 0xff; | |
| 178 | |
| 179 int bottom = bytes[4] & 0xff; | |
| 180 bottom <<= 8; | |
| 181 bottom |= bytes[5] & 0xff; | |
| 182 bottom <<= 8; | |
| 183 bottom |= bytes[6] & 0xff; | |
| 184 bottom <<= 8; | |
| 185 bottom |= bytes[7] & 0xff; | |
| 186 | |
| 187 return new Int64.fromInts(top, bottom); | |
| 188 } | |
| 189 | |
| 190 /** | |
| 191 * Constructs an [Int64] from a pair of 32-bit integers having the value | |
| 192 * [:((top & 0xffffffff) << 32) | (bottom & 0xffffffff):]. | |
| 193 */ | |
| 194 factory Int64.fromInts(int top, int bottom) { | |
| 195 top &= 0xffffffff; | |
| 196 bottom &= 0xffffffff; | |
| 197 int d0 = _MASK & bottom; | |
| 198 int d1 = ((0xfff & top) << 10) | (0x3ff & (bottom >> _BITS)); | |
| 199 int d2 = _MASK2 & (top >> 12); | |
| 200 return Int64._masked(d0, d1, d2); | |
| 201 } | |
| 202 | |
| 203 // Returns the [Int64] representation of the specified value. Throws | |
| 204 // [ArgumentError] for non-integer arguments. | |
| 205 static Int64 _promote(value) { | |
| 206 if (value is Int64) { | |
| 207 return value; | |
| 208 } else if (value is int) { | |
| 209 return new Int64(value); | |
| 210 } else if (value is Int32) { | |
| 211 return value.toInt64(); | |
| 212 } | |
| 213 throw new ArgumentError.value(value); | |
| 214 } | |
| 215 | |
| 216 Int64 operator +(other) { | |
| 217 Int64 o = _promote(other); | |
| 218 int sum0 = _l + o._l; | |
| 219 int sum1 = _m + o._m + (sum0 >> _BITS); | |
| 220 int sum2 = _h + o._h + (sum1 >> _BITS); | |
| 221 return Int64._masked(sum0, sum1, sum2); | |
| 222 } | |
| 223 | |
| 224 Int64 operator -(other) { | |
| 225 Int64 o = _promote(other); | |
| 226 return _sub(_l, _m, _h, o._l, o._m, o._h); | |
| 227 } | |
| 228 | |
| 229 Int64 operator -() => _negate(_l, _m, _h); | |
| 230 | |
| 231 Int64 operator *(other) { | |
| 232 Int64 o = _promote(other); | |
| 233 | |
| 234 // Grab 13-bit chunks. | |
| 235 int a0 = _l & 0x1fff; | |
| 236 int a1 = (_l >> 13) | ((_m & 0xf) << 9); | |
| 237 int a2 = (_m >> 4) & 0x1fff; | |
| 238 int a3 = (_m >> 17) | ((_h & 0xff) << 5); | |
| 239 int a4 = (_h & 0xfff00) >> 8; | |
| 240 | |
| 241 int b0 = o._l & 0x1fff; | |
| 242 int b1 = (o._l >> 13) | ((o._m & 0xf) << 9); | |
| 243 int b2 = (o._m >> 4) & 0x1fff; | |
| 244 int b3 = (o._m >> 17) | ((o._h & 0xff) << 5); | |
| 245 int b4 = (o._h & 0xfff00) >> 8; | |
| 246 | |
| 247 // Compute partial products. | |
| 248 // Optimization: if b is small, avoid multiplying by parts that are 0. | |
| 249 int p0 = a0 * b0; // << 0 | |
| 250 int p1 = a1 * b0; // << 13 | |
| 251 int p2 = a2 * b0; // << 26 | |
| 252 int p3 = a3 * b0; // << 39 | |
| 253 int p4 = a4 * b0; // << 52 | |
| 254 | |
| 255 if (b1 != 0) { | |
| 256 p1 += a0 * b1; | |
| 257 p2 += a1 * b1; | |
| 258 p3 += a2 * b1; | |
| 259 p4 += a3 * b1; | |
| 260 } | |
| 261 if (b2 != 0) { | |
| 262 p2 += a0 * b2; | |
| 263 p3 += a1 * b2; | |
| 264 p4 += a2 * b2; | |
| 265 } | |
| 266 if (b3 != 0) { | |
| 267 p3 += a0 * b3; | |
| 268 p4 += a1 * b3; | |
| 269 } | |
| 270 if (b4 != 0) { | |
| 271 p4 += a0 * b4; | |
| 272 } | |
| 273 | |
| 274 // Accumulate into 22-bit chunks: | |
| 275 // .........................................c10|...................c00| | |
| 276 // |....................|..................xxxx|xxxxxxxxxxxxxxxxxxxxxx| p0 | |
| 277 // |....................|......................|......................| | |
| 278 // |....................|...................c11|......c01.............| | |
| 279 // |....................|....xxxxxxxxxxxxxxxxxx|xxxxxxxxx.............| p1 | |
| 280 // |....................|......................|......................| | |
| 281 // |.................c22|...............c12....|......................| | |
| 282 // |..........xxxxxxxxxx|xxxxxxxxxxxxxxxxxx....|......................| p2 | |
| 283 // |....................|......................|......................| | |
| 284 // |.................c23|..c13.................|......................| | |
| 285 // |xxxxxxxxxxxxxxxxxxxx|xxxxx.................|......................| p3 | |
| 286 // |....................|......................|......................| | |
| 287 // |.........c24........|......................|......................| | |
| 288 // |xxxxxxxxxxxx........|......................|......................| p4 | |
| 289 | |
| 290 int c00 = p0 & 0x3fffff; | |
| 291 int c01 = (p1 & 0x1ff) << 13; | |
| 292 int c0 = c00 + c01; | |
| 293 | |
| 294 int c10 = p0 >> 22; | |
| 295 int c11 = p1 >> 9; | |
| 296 int c12 = (p2 & 0x3ffff) << 4; | |
| 297 int c13 = (p3 & 0x1f) << 17; | |
| 298 int c1 = c10 + c11 + c12 + c13; | |
| 299 | |
| 300 int c22 = p2 >> 18; | |
| 301 int c23 = p3 >> 5; | |
| 302 int c24 = (p4 & 0xfff) << 8; | |
| 303 int c2 = c22 + c23 + c24; | |
| 304 | |
| 305 // Propagate high bits from c0 -> c1, c1 -> c2. | |
| 306 c1 += c0 >> _BITS; | |
| 307 c2 += c1 >> _BITS; | |
| 308 | |
| 309 return Int64._masked(c0, c1, c2); | |
| 310 } | |
| 311 | |
| 312 Int64 operator %(other) => _divide(this, other, _RETURN_MOD); | |
| 313 | |
| 314 Int64 operator ~/(other) => _divide(this, other, _RETURN_DIV); | |
| 315 | |
| 316 Int64 remainder(other) => _divide(this, other, _RETURN_REM); | |
| 317 | |
| 318 Int64 operator &(other) { | |
| 319 Int64 o = _promote(other); | |
| 320 int a0 = _l & o._l; | |
| 321 int a1 = _m & o._m; | |
| 322 int a2 = _h & o._h; | |
| 323 return Int64._masked(a0, a1, a2); | |
| 324 } | |
| 325 | |
| 326 Int64 operator |(other) { | |
| 327 Int64 o = _promote(other); | |
| 328 int a0 = _l | o._l; | |
| 329 int a1 = _m | o._m; | |
| 330 int a2 = _h | o._h; | |
| 331 return Int64._masked(a0, a1, a2); | |
| 332 } | |
| 333 | |
| 334 Int64 operator ^(other) { | |
| 335 Int64 o = _promote(other); | |
| 336 int a0 = _l ^ o._l; | |
| 337 int a1 = _m ^ o._m; | |
| 338 int a2 = _h ^ o._h; | |
| 339 return Int64._masked(a0, a1, a2); | |
| 340 } | |
| 341 | |
| 342 Int64 operator ~() { | |
| 343 return Int64._masked(~_l, ~_m, ~_h); | |
| 344 } | |
| 345 | |
| 346 Int64 operator <<(int n) { | |
| 347 if (n < 0) { | |
| 348 throw new ArgumentError.value(n); | |
| 349 } | |
| 350 n &= 63; | |
| 351 | |
| 352 int res0, res1, res2; | |
| 353 if (n < _BITS) { | |
| 354 res0 = _l << n; | |
| 355 res1 = (_m << n) | (_l >> (_BITS - n)); | |
| 356 res2 = (_h << n) | (_m >> (_BITS - n)); | |
| 357 } else if (n < _BITS01) { | |
| 358 res0 = 0; | |
| 359 res1 = _l << (n - _BITS); | |
| 360 res2 = (_m << (n - _BITS)) | (_l >> (_BITS01 - n)); | |
| 361 } else { | |
| 362 res0 = 0; | |
| 363 res1 = 0; | |
| 364 res2 = _l << (n - _BITS01); | |
| 365 } | |
| 366 | |
| 367 return Int64._masked(res0, res1, res2); | |
| 368 } | |
| 369 | |
| 370 Int64 operator >>(int n) { | |
| 371 if (n < 0) { | |
| 372 throw new ArgumentError.value(n); | |
| 373 } | |
| 374 n &= 63; | |
| 375 | |
| 376 int res0, res1, res2; | |
| 377 | |
| 378 // Sign extend h(a). | |
| 379 int a2 = _h; | |
| 380 bool negative = (a2 & _SIGN_BIT_MASK) != 0; | |
| 381 if (negative && _MASK > _MASK2) { | |
| 382 // Add extra one bits on the left so the sign gets shifted into the wider | |
| 383 // lower words. | |
| 384 a2 += (_MASK - _MASK2); | |
| 385 } | |
| 386 | |
| 387 if (n < _BITS) { | |
| 388 res2 = _shiftRight(a2, n); | |
| 389 if (negative) { | |
| 390 res2 |= _MASK2 & ~(_MASK2 >> n); | |
| 391 } | |
| 392 res1 = _shiftRight(_m, n) | (a2 << (_BITS - n)); | |
| 393 res0 = _shiftRight(_l, n) | (_m << (_BITS - n)); | |
| 394 } else if (n < _BITS01) { | |
| 395 res2 = negative ? _MASK2 : 0; | |
| 396 res1 = _shiftRight(a2, n - _BITS); | |
| 397 if (negative) { | |
| 398 res1 |= _MASK & ~(_MASK >> (n - _BITS)); | |
| 399 } | |
| 400 res0 = _shiftRight(_m, n - _BITS) | (a2 << (_BITS01 - n)); | |
| 401 } else { | |
| 402 res2 = negative ? _MASK2 : 0; | |
| 403 res1 = negative ? _MASK : 0; | |
| 404 res0 = _shiftRight(a2, n - _BITS01); | |
| 405 if (negative) { | |
| 406 res0 |= _MASK & ~(_MASK >> (n - _BITS01)); | |
| 407 } | |
| 408 } | |
| 409 | |
| 410 return Int64._masked(res0, res1, res2); | |
| 411 } | |
| 412 | |
| 413 Int64 shiftRightUnsigned(int n) { | |
| 414 if (n < 0) { | |
| 415 throw new ArgumentError.value(n); | |
| 416 } | |
| 417 n &= 63; | |
| 418 | |
| 419 int res0, res1, res2; | |
| 420 int a2 = _MASK2 & _h; // Ensure a2 is positive. | |
| 421 if (n < _BITS) { | |
| 422 res2 = a2 >> n; | |
| 423 res1 = (_m >> n) | (a2 << (_BITS - n)); | |
| 424 res0 = (_l >> n) | (_m << (_BITS - n)); | |
| 425 } else if (n < _BITS01) { | |
| 426 res2 = 0; | |
| 427 res1 = a2 >> (n - _BITS); | |
| 428 res0 = (_m >> (n - _BITS)) | (_h << (_BITS01 - n)); | |
| 429 } else { | |
| 430 res2 = 0; | |
| 431 res1 = 0; | |
| 432 res0 = a2 >> (n - _BITS01); | |
| 433 } | |
| 434 | |
| 435 return Int64._masked(res0, res1, res2); | |
| 436 } | |
| 437 | |
| 438 /** | |
| 439 * Returns [:true:] if this [Int64] has the same numeric value as the | |
| 440 * given object. The argument may be an [int] or an [IntX]. | |
| 441 */ | |
| 442 bool operator ==(other) { | |
| 443 Int64 o; | |
| 444 if (other is Int64) { | |
| 445 o = other; | |
| 446 } else if (other is int) { | |
| 447 if (_h == 0 && _m == 0) return _l == other; | |
| 448 // Since we know one of [_h] or [_m] is non-zero, if [other] fits in the | |
| 449 // low word then it can't be numerically equal. | |
| 450 if ((_MASK & other) == other) return false; | |
| 451 o = new Int64(other); | |
| 452 } else if (other is Int32) { | |
| 453 o = other.toInt64(); | |
| 454 } | |
| 455 if (o != null) { | |
| 456 return _l == o._l && _m == o._m && _h == o._h; | |
| 457 } | |
| 458 return false; | |
| 459 } | |
| 460 | |
| 461 int compareTo(IntX other) =>_compareTo(other); | |
| 462 | |
| 463 int _compareTo(other) { | |
| 464 Int64 o = _promote(other); | |
| 465 int signa = _h >> (_BITS2 - 1); | |
| 466 int signb = o._h >> (_BITS2 - 1); | |
| 467 if (signa != signb) { | |
| 468 return signa == 0 ? 1 : -1; | |
| 469 } | |
| 470 if (_h > o._h) { | |
| 471 return 1; | |
| 472 } else if (_h < o._h) { | |
| 473 return -1; | |
| 474 } | |
| 475 if (_m > o._m) { | |
| 476 return 1; | |
| 477 } else if (_m < o._m) { | |
| 478 return -1; | |
| 479 } | |
| 480 if (_l > o._l) { | |
| 481 return 1; | |
| 482 } else if (_l < o._l) { | |
| 483 return -1; | |
| 484 } | |
| 485 return 0; | |
| 486 } | |
| 487 | |
| 488 bool operator <(other) => _compareTo(other) < 0; | |
| 489 bool operator <=(other) => _compareTo(other) <= 0; | |
| 490 bool operator >(other) => this._compareTo(other) > 0; | |
| 491 bool operator >=(other) => _compareTo(other) >= 0; | |
| 492 | |
| 493 bool get isEven => (_l & 0x1) == 0; | |
| 494 bool get isMaxValue => (_h == _MASK2 >> 1) && _m == _MASK && _l == _MASK; | |
| 495 bool get isMinValue => _h == _SIGN_BIT_MASK && _m == 0 && _l == 0; | |
| 496 bool get isNegative => (_h & _SIGN_BIT_MASK) != 0; | |
| 497 bool get isOdd => (_l & 0x1) == 1; | |
| 498 bool get isZero => _h == 0 && _m == 0 && _l == 0; | |
| 499 | |
| 500 int get bitLength { | |
| 501 if (isZero) return 0; | |
| 502 int a0 = _l, a1 = _m, a2 = _h; | |
| 503 if (isNegative) { | |
| 504 a0 = _MASK & ~a0; | |
| 505 a1 = _MASK & ~a1; | |
| 506 a2 = _MASK2 & ~a2; | |
| 507 } | |
| 508 if (a2 != 0) return _BITS01 + a2.bitLength; | |
| 509 if (a1 != 0) return _BITS + a1.bitLength; | |
| 510 return a0.bitLength; | |
| 511 } | |
| 512 | |
| 513 /** | |
| 514 * Returns a hash code based on all the bits of this [Int64]. | |
| 515 */ | |
| 516 int get hashCode { | |
| 517 // TODO(sra): Should we ensure that hashCode values match corresponding int? | |
| 518 // i.e. should `new Int64(x).hashCode == x.hashCode`? | |
| 519 int bottom = ((_m & 0x3ff) << _BITS) | _l; | |
| 520 int top = (_h << 12) | ((_m >> 10) & 0xfff); | |
| 521 return bottom ^ top; | |
| 522 } | |
| 523 | |
| 524 Int64 abs() { | |
| 525 return this.isNegative ? -this : this; | |
| 526 } | |
| 527 | |
| 528 Int64 clamp(lowerLimit, upperLimit) { | |
| 529 Int64 lower = _promote(lowerLimit); | |
| 530 Int64 upper = _promote(upperLimit); | |
| 531 if (this < lower) return lower; | |
| 532 if (this > upper) return upper; | |
| 533 return this; | |
| 534 } | |
| 535 | |
| 536 /** | |
| 537 * Returns the number of leading zeros in this [Int64] as an [int] | |
| 538 * between 0 and 64. | |
| 539 */ | |
| 540 int numberOfLeadingZeros() { | |
| 541 int b2 = Int32._numberOfLeadingZeros(_h); | |
| 542 if (b2 == 32) { | |
| 543 int b1 = Int32._numberOfLeadingZeros(_m); | |
| 544 if (b1 == 32) { | |
| 545 return Int32._numberOfLeadingZeros(_l) + 32; | |
| 546 } else { | |
| 547 return b1 + _BITS2 - (32 - _BITS); | |
| 548 } | |
| 549 } else { | |
| 550 return b2 - (32 - _BITS2); | |
| 551 } | |
| 552 } | |
| 553 | |
| 554 /** | |
| 555 * Returns the number of trailing zeros in this [Int64] as an [int] | |
| 556 * between 0 and 64. | |
| 557 */ | |
| 558 int numberOfTrailingZeros() { | |
| 559 int zeros = Int32._numberOfTrailingZeros(_l); | |
| 560 if (zeros < 32) { | |
| 561 return zeros; | |
| 562 } | |
| 563 | |
| 564 zeros = Int32._numberOfTrailingZeros(_m); | |
| 565 if (zeros < 32) { | |
| 566 return _BITS + zeros; | |
| 567 } | |
| 568 | |
| 569 zeros = Int32._numberOfTrailingZeros(_h); | |
| 570 if (zeros < 32) { | |
| 571 return _BITS01 + zeros; | |
| 572 } | |
| 573 // All zeros | |
| 574 return 64; | |
| 575 } | |
| 576 | |
| 577 Int64 toSigned(int width) { | |
| 578 if (width < 1 || width > 64) throw new RangeError.range(width, 1, 64); | |
| 579 if (width > _BITS01) { | |
| 580 return Int64._masked(_l, _m, _h.toSigned(width - _BITS01)); | |
| 581 } else if (width > _BITS) { | |
| 582 int m = _m.toSigned(width - _BITS); | |
| 583 return m.isNegative | |
| 584 ? Int64._masked(_l, m, _MASK2) | |
| 585 : Int64._masked(_l, m, 0); // Masking for type inferrer. | |
| 586 } else { | |
| 587 int l = _l.toSigned(width); | |
| 588 return l.isNegative | |
| 589 ? Int64._masked(l, _MASK, _MASK2) | |
| 590 : Int64._masked(l, 0, 0); // Masking for type inferrer. | |
| 591 } | |
| 592 } | |
| 593 | |
| 594 Int64 toUnsigned(int width) { | |
| 595 if (width < 0 || width > 64) throw new RangeError.range(width, 0, 64); | |
| 596 if (width > _BITS01) { | |
| 597 int h = _h.toUnsigned(width - _BITS01); | |
| 598 return Int64._masked(_l, _m, h); | |
| 599 } else if (width > _BITS) { | |
| 600 int m = _m.toUnsigned(width - _BITS); | |
| 601 return Int64._masked(_l, m, 0); | |
| 602 } else { | |
| 603 int l = _l.toUnsigned(width); | |
| 604 return Int64._masked(l, 0, 0); | |
| 605 } | |
| 606 } | |
| 607 | |
| 608 List<int> toBytes() { | |
| 609 List<int> result = new List<int>(8); | |
| 610 result[0] = _l & 0xff; | |
| 611 result[1] = (_l >> 8) & 0xff; | |
| 612 result[2] = ((_m << 6) & 0xfc) | ((_l >> 16) & 0x3f); | |
| 613 result[3] = (_m >> 2) & 0xff; | |
| 614 result[4] = (_m >> 10) & 0xff; | |
| 615 result[5] = ((_h << 4) & 0xf0) | ((_m >> 18) & 0xf); | |
| 616 result[6] = (_h >> 4) & 0xff; | |
| 617 result[7] = (_h >> 12) & 0xff; | |
| 618 return result; | |
| 619 } | |
| 620 | |
| 621 double toDouble() => toInt().toDouble(); | |
| 622 | |
| 623 int toInt() { | |
| 624 int l = _l; | |
| 625 int m = _m; | |
| 626 int h = _h; | |
| 627 // In the sum we add least significant to most significant so that in | |
| 628 // JavaScript double arithmetic rounding occurs on only the last addition. | |
| 629 if ((_h & _SIGN_BIT_MASK) != 0) { | |
| 630 l = _MASK & ~_l; | |
| 631 m = _MASK & ~_m; | |
| 632 h = _MASK2 & ~_h; | |
| 633 return -((1 + l) + (4194304 * m) + (17592186044416 * h)); | |
| 634 } else { | |
| 635 return l + (4194304 * m) + (17592186044416 * h); | |
| 636 } | |
| 637 } | |
| 638 | |
| 639 /** | |
| 640 * Returns an [Int32] containing the low 32 bits of this [Int64]. | |
| 641 */ | |
| 642 Int32 toInt32() { | |
| 643 return new Int32(((_m & 0x3ff) << _BITS) | _l); | |
| 644 } | |
| 645 | |
| 646 /** | |
| 647 * Returns [this]. | |
| 648 */ | |
| 649 Int64 toInt64() => this; | |
| 650 | |
| 651 /** | |
| 652 * Returns the value of this [Int64] as a decimal [String]. | |
| 653 */ | |
| 654 String toString() => _toRadixString(10); | |
| 655 | |
| 656 // TODO(rice) - Make this faster by avoiding arithmetic. | |
| 657 String toHexString() { | |
| 658 if (isZero) return "0"; | |
| 659 Int64 x = this; | |
| 660 String hexStr = ""; | |
| 661 while (!x.isZero) { | |
| 662 int digit = x._l & 0xf; | |
| 663 hexStr = "${_hexDigit(digit)}$hexStr"; | |
| 664 x = x.shiftRightUnsigned(4); | |
| 665 } | |
| 666 return hexStr; | |
| 667 } | |
| 668 | |
| 669 String toRadixString(int radix) { | |
| 670 return _toRadixString(Int32._validateRadix(radix)); | |
| 671 } | |
| 672 | |
| 673 String _toRadixString(int radix) { | |
| 674 int d0 = _l; | |
| 675 int d1 = _m; | |
| 676 int d2 = _h; | |
| 677 | |
| 678 if (d0 == 0 && d1 == 0 && d2 == 0) return '0'; | |
| 679 | |
| 680 String sign = ''; | |
| 681 if ((d2 & _SIGN_BIT_MASK) != 0) { | |
| 682 sign = '-'; | |
| 683 | |
| 684 // Negate in-place. | |
| 685 d0 = 0 - d0; | |
| 686 int borrow = (d0 >> _BITS) & 1; | |
| 687 d0 &= _MASK; | |
| 688 d1 = 0 - d1 - borrow; | |
| 689 borrow = (d1 >> _BITS) & 1; | |
| 690 d1 &= _MASK; | |
| 691 d2 = 0 - d2 - borrow; | |
| 692 d2 &= _MASK2; | |
| 693 // d2, d1, d0 now are an unsigned 64 bit integer for MIN_VALUE and an | |
| 694 // unsigned 63 bit integer for other values. | |
| 695 } | |
| 696 | |
| 697 // Rearrange components into five components where all but the most | |
| 698 // significant are 10 bits wide. | |
| 699 // | |
| 700 // d4, d3, d4, d1, d0: 24 + 10 + 10 + 10 + 10 bits | |
| 701 // | |
| 702 // The choice of 10 bits allows a remainder of 20 bits to be scaled by 10 | |
| 703 // bits and added during division while keeping all intermediate values | |
| 704 // within 30 bits (unsigned small integer range for 32 bit implementations | |
| 705 // of Dart VM and V8). | |
| 706 // | |
| 707 // 6 6 5 4 3 2 1 | |
| 708 // 3210987654321098765432109876543210987654321098765432109876543210 | |
| 709 // [--------d2--------][---------d1---------][---------d0---------] | |
| 710 // --> | |
| 711 // [----------d4----------][---d3---][---d2---][---d1---][---d0---] | |
| 712 | |
| 713 | |
| 714 int d4 = (d2 << 4) | (d1 >> 18); | |
| 715 int d3 = (d1 >> 8) & 0x3ff; | |
| 716 d2 = ((d1 << 2) | (d0 >> 20)) & 0x3ff; | |
| 717 d1 = (d0 >> 10) & 0x3ff; | |
| 718 d0 = d0 & 0x3ff; | |
| 719 | |
| 720 int fatRadix = _fatRadixTable[radix]; | |
| 721 | |
| 722 // Generate chunks of digits. In radix 10, generate 6 digits per chunk. | |
| 723 // | |
| 724 // This loop generates at most 3 chunks, so we store the chunks in locals | |
| 725 // rather than a list. We are trying to generate digits 20 bits at a time | |
| 726 // until we have only 30 bits left. 20 + 20 + 30 > 64 would imply that we | |
| 727 // need only two chunks, but radix values 17-19 and 33-36 generate only 15 | |
| 728 // or 16 bits per iteration, so sometimes the third chunk is needed. | |
| 729 | |
| 730 String chunk1 = "", chunk2 = "", chunk3 = ""; | |
| 731 | |
| 732 while (!(d4 == 0 && d3 == 0)) { | |
| 733 int q = d4 ~/ fatRadix; | |
| 734 int r = d4 - q * fatRadix; | |
| 735 d4 = q; | |
| 736 d3 += r << 10; | |
| 737 | |
| 738 q = d3 ~/ fatRadix; | |
| 739 r = d3 - q * fatRadix; | |
| 740 d3 = q; | |
| 741 d2 += r << 10; | |
| 742 | |
| 743 q = d2 ~/ fatRadix; | |
| 744 r = d2 - q * fatRadix; | |
| 745 d2 = q; | |
| 746 d1 += r << 10; | |
| 747 | |
| 748 q = d1 ~/ fatRadix; | |
| 749 r = d1 - q * fatRadix; | |
| 750 d1 = q; | |
| 751 d0 += r << 10; | |
| 752 | |
| 753 q = d0 ~/ fatRadix; | |
| 754 r = d0 - q * fatRadix; | |
| 755 d0 = q; | |
| 756 | |
| 757 assert(chunk3 == ""); | |
| 758 chunk3 = chunk2; | |
| 759 chunk2 = chunk1; | |
| 760 // Adding [fatRadix] Forces an extra digit which we discard to get a fixed | |
| 761 // width. E.g. (1000000 + 123) -> "1000123" -> "000123". An alternative | |
| 762 // would be to pad to the left with zeroes. | |
| 763 chunk1 = (fatRadix + r).toRadixString(radix).substring(1); | |
| 764 } | |
| 765 int residue = (d2 << 20) + (d1 << 10) + d0; | |
| 766 String leadingDigits = residue == 0 ? '' : residue.toRadixString(radix); | |
| 767 return '$sign$leadingDigits$chunk1$chunk2$chunk3'; | |
| 768 } | |
| 769 | |
| 770 // Table of 'fat' radix values. Each entry for index `i` is the largest power | |
| 771 // of `i` whose remainder fits in 20 bits. | |
| 772 static const _fatRadixTable = const <int>[ | |
| 773 0, | |
| 774 0, | |
| 775 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 | |
| 776 * 2, | |
| 777 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3, | |
| 778 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4 * 4, | |
| 779 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, | |
| 780 6 * 6 * 6 * 6 * 6 * 6 * 6, | |
| 781 7 * 7 * 7 * 7 * 7 * 7 * 7, | |
| 782 8 * 8 * 8 * 8 * 8 * 8, | |
| 783 9 * 9 * 9 * 9 * 9 * 9, | |
| 784 10 * 10 * 10 * 10 * 10 * 10, | |
| 785 11 * 11 * 11 * 11 * 11, | |
| 786 12 * 12 * 12 * 12 * 12, | |
| 787 13 * 13 * 13 * 13 * 13, | |
| 788 14 * 14 * 14 * 14 * 14, | |
| 789 15 * 15 * 15 * 15 * 15, | |
| 790 16 * 16 * 16 * 16 * 16, | |
| 791 17 * 17 * 17 * 17, | |
| 792 18 * 18 * 18 * 18, | |
| 793 19 * 19 * 19 * 19, | |
| 794 20 * 20 * 20 * 20, | |
| 795 21 * 21 * 21 * 21, | |
| 796 22 * 22 * 22 * 22, | |
| 797 23 * 23 * 23 * 23, | |
| 798 24 * 24 * 24 * 24, | |
| 799 25 * 25 * 25 * 25, | |
| 800 26 * 26 * 26 * 26, | |
| 801 27 * 27 * 27 * 27, | |
| 802 28 * 28 * 28 * 28, | |
| 803 29 * 29 * 29 * 29, | |
| 804 30 * 30 * 30 * 30, | |
| 805 31 * 31 * 31 * 31, | |
| 806 32 * 32 * 32 * 32, | |
| 807 33 * 33 * 33, | |
| 808 34 * 34 * 34, | |
| 809 35 * 35 * 35, | |
| 810 36 * 36 * 36 | |
| 811 ]; | |
| 812 | |
| 813 String toDebugString() { | |
| 814 return "Int64[_l=$_l, _m=$_m, _h=$_h]"; | |
| 815 } | |
| 816 | |
| 817 | |
| 818 static Int64 _masked(int a0, int a1, int a2) => | |
| 819 new Int64._bits(_MASK & a0, _MASK & a1, _MASK2 & a2); | |
| 820 | |
| 821 static Int64 _sub(int a0, int a1, int a2, int b0, int b1, int b2) { | |
| 822 int diff0 = a0 - b0; | |
| 823 int diff1 = a1 - b1 - ((diff0 >> _BITS) & 1); | |
| 824 int diff2 = a2 - b2 - ((diff1 >> _BITS) & 1); | |
| 825 return _masked(diff0, diff1, diff2); | |
| 826 } | |
| 827 | |
| 828 static Int64 _negate(int b0, int b1, int b2) { | |
| 829 return _sub(0, 0, 0, b0, b1, b2); | |
| 830 } | |
| 831 | |
| 832 String _hexDigit(int digit) => "0123456789ABCDEF"[digit]; | |
| 833 | |
| 834 // Work around dart2js bugs with negative arguments to '>>' operator. | |
| 835 static int _shiftRight(int x, int n) { | |
| 836 if (x >= 0) { | |
| 837 return x >> n; | |
| 838 } else { | |
| 839 int shifted = x >> n; | |
| 840 if (shifted >= 0x80000000) { | |
| 841 shifted -= 4294967296; | |
| 842 } | |
| 843 return shifted; | |
| 844 } | |
| 845 } | |
| 846 | |
| 847 | |
| 848 // Implementation of '~/', '%' and 'remainder'. | |
| 849 | |
| 850 static Int64 _divide(Int64 a, other, int what) { | |
| 851 Int64 b = _promote(other); | |
| 852 if (b.isZero) { | |
| 853 throw new IntegerDivisionByZeroException(); | |
| 854 } | |
| 855 if (a.isZero) return ZERO; | |
| 856 | |
| 857 bool aNeg = a.isNegative; | |
| 858 bool bNeg = b.isNegative; | |
| 859 a = a.abs(); | |
| 860 b = b.abs(); | |
| 861 | |
| 862 int a0 = a._l; | |
| 863 int a1 = a._m; | |
| 864 int a2 = a._h; | |
| 865 | |
| 866 int b0 = b._l; | |
| 867 int b1 = b._m; | |
| 868 int b2 = b._h; | |
| 869 return _divideHelper(a0, a1, a2, aNeg, b0, b1, b2, bNeg, what); | |
| 870 } | |
| 871 | |
| 872 static const _RETURN_DIV = 1; | |
| 873 static const _RETURN_REM = 2; | |
| 874 static const _RETURN_MOD = 3; | |
| 875 | |
| 876 static _divideHelper( | |
| 877 // up to 64 bits unsigned in a2/a1/a0 and b2/b1/b0 | |
| 878 int a0, int a1, int a2, bool aNeg, // input A. | |
| 879 int b0, int b1, int b2, bool bNeg, // input B. | |
| 880 int what) { | |
| 881 int q0 = 0, q1 = 0, q2 = 0; // result Q. | |
| 882 int r0 = 0, r1 = 0, r2 = 0; // result R. | |
| 883 | |
| 884 if (b2 == 0 && b1 == 0 && b0 < (1 << (30 - _BITS))) { | |
| 885 // Small divisor can be handled by single-digit division within Smi range. | |
| 886 // | |
| 887 // Handling small divisors here helps the estimate version below by | |
| 888 // handling cases where the estimate is off by more than a small amount. | |
| 889 | |
| 890 q2 = a2 ~/ b0; | |
| 891 int carry = a2 - q2 * b0; | |
| 892 int d1 = a1 + (carry << _BITS); | |
| 893 q1 = d1 ~/ b0; | |
| 894 carry = d1 - q1 * b0; | |
| 895 int d0 = a0 + (carry << _BITS); | |
| 896 q0 = d0 ~/ b0; | |
| 897 r0 = d0 - q0 * b0; | |
| 898 } else { | |
| 899 // Approximate Q = A ~/ B and R = A - Q * B using doubles. | |
| 900 | |
| 901 // The floating point approximation is very close to the correct value | |
| 902 // when floor(A/B) fits in fewer that 53 bits. | |
| 903 | |
| 904 // We use double arithmetic for intermediate values. Double arithmetic on | |
| 905 // non-negative values is exact under the following conditions: | |
| 906 // | |
| 907 // - The values are integer values that fit in 53 bits. | |
| 908 // - Dividing by powers of two (adjusts exponent only). | |
| 909 // - Floor (zeroes bits with fractional weight). | |
| 910 | |
| 911 const double K2 = 17592186044416.0; // 2^44 | |
| 912 const double K1 = 4194304.0; // 2^22 | |
| 913 | |
| 914 // Approximate double values for [a] and [b]. | |
| 915 double ad = a0 + K1 * a1 + K2 * a2; | |
| 916 double bd = b0 + K1 * b1 + K2 * b2; | |
| 917 // Approximate quotient. | |
| 918 double qd = (ad / bd).floorToDouble(); | |
| 919 | |
| 920 // Extract components of [qd] using double arithmetic. | |
| 921 double q2d = (qd / K2).floorToDouble(); | |
| 922 qd = qd - K2 * q2d; | |
| 923 double q1d = (qd / K1).floorToDouble(); | |
| 924 double q0d = qd - K1 * q1d; | |
| 925 q2 = q2d.toInt(); | |
| 926 q1 = q1d.toInt(); | |
| 927 q0 = q0d.toInt(); | |
| 928 | |
| 929 assert(q0 + K1 * q1 + K2 * q2 == (ad / bd).floorToDouble()); | |
| 930 assert(q2 == 0 || b2 == 0); // Q and B can't both be big since Q*B <= A. | |
| 931 | |
| 932 // P = Q * B, using doubles to hold intermediates. | |
| 933 // We don't need all partial sums since Q*B <= A. | |
| 934 double p0d = q0d * b0; | |
| 935 double p0carry = (p0d / K1).floorToDouble(); | |
| 936 p0d = p0d - p0carry * K1; | |
| 937 double p1d = q1d * b0 + q0d * b1 + p0carry; | |
| 938 double p1carry = (p1d / K1).floorToDouble(); | |
| 939 p1d = p1d - p1carry * K1; | |
| 940 double p2d = q2d * b0 + q1d * b1 + q0d * b2 + p1carry; | |
| 941 assert(p2d <= _MASK2); // No partial sum overflow. | |
| 942 | |
| 943 // R = A - P | |
| 944 int diff0 = a0 - p0d.toInt(); | |
| 945 int diff1 = a1 - p1d.toInt() - ((diff0 >> _BITS) & 1); | |
| 946 int diff2 = a2 - p2d.toInt() - ((diff1 >> _BITS) & 1); | |
| 947 r0 = _MASK & diff0; | |
| 948 r1 = _MASK & diff1; | |
| 949 r2 = _MASK2 & diff2; | |
| 950 | |
| 951 // while (R < 0 || R >= B) | |
| 952 // adjust R towards [0, B) | |
| 953 while ( | |
| 954 r2 >= _SIGN_BIT_MASK || | |
| 955 r2 > b2 || | |
| 956 (r2 == b2 && (r1 > b1 || (r1 == b1 && r0 >= b0)))) { | |
| 957 // Direction multiplier for adjustment. | |
| 958 int m = (r2 & _SIGN_BIT_MASK) == 0 ? 1 : -1; | |
| 959 // R = R - B or R = R + B | |
| 960 int d0 = r0 - m * b0; | |
| 961 int d1 = r1 - m * (b1 + ((d0 >> _BITS) & 1)); | |
| 962 int d2 = r2 - m * (b2 + ((d1 >> _BITS) & 1)); | |
| 963 r0 = _MASK & d0; | |
| 964 r1 = _MASK & d1; | |
| 965 r2 = _MASK2 & d2; | |
| 966 | |
| 967 // Q = Q + 1 or Q = Q - 1 | |
| 968 d0 = q0 + m; | |
| 969 d1 = q1 + m * ((d0 >> _BITS) & 1); | |
| 970 d2 = q2 + m * ((d1 >> _BITS) & 1); | |
| 971 q0 = _MASK & d0; | |
| 972 q1 = _MASK & d1; | |
| 973 q2 = _MASK2 & d2; | |
| 974 } | |
| 975 } | |
| 976 | |
| 977 // 0 <= R < B | |
| 978 assert(Int64.ZERO <= new Int64._bits(r0, r1, r2)); | |
| 979 assert(r2 < b2 || // Handles case where B = -(MIN_VALUE) | |
| 980 new Int64._bits(r0, r1, r2) < new Int64._bits(b0, b1, b2)); | |
| 981 | |
| 982 assert(what == _RETURN_DIV || what == _RETURN_MOD || what == _RETURN_REM); | |
| 983 if (what == _RETURN_DIV) { | |
| 984 if (aNeg != bNeg) return _negate(q0, q1, q2); | |
| 985 return Int64._masked(q0, q1, q2); // Masking for type inferrer. | |
| 986 } | |
| 987 | |
| 988 if (!aNeg) { | |
| 989 return Int64._masked(r0, r1, r2); // Masking for type inferrer. | |
| 990 } | |
| 991 | |
| 992 if (what == _RETURN_MOD) { | |
| 993 if (r0 == 0 && r1 == 0 && r2 == 0) { | |
| 994 return ZERO; | |
| 995 } else { | |
| 996 return _sub(b0, b1, b2, r0, r1, r2); | |
| 997 } | |
| 998 } else { | |
| 999 return _negate(r0, r1, r2); | |
| 1000 } | |
| 1001 } | |
| 1002 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1909043004:
Moved pkg/fixnum to github (Closed)
Base URL: https://github.com/dart-lang/sdk.git@master