Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(152)

Side by Side Diff: pkg/fixnum/lib/src/int64.dart

Issue 21085005: Rename int{x,32,64} to Int{X,32,64} in line with naming guidelines. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 7 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
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
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
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
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
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
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
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
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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698