Debian Codegraph @

closure-library/closure/goog/math/long.js

raw
1 // Copyright 2009 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview Defines a Long class for representing a 64-bit two's-complement
17 * integer value, which faithfully simulates the behavior of a Java "long". This
18 * implementation is derived from LongLib in GWT.
19 *
20 */
21
22 goog.provide('goog.math.Long');
23
24 goog.require('goog.asserts');
25 goog.require('goog.reflect');
26
27
28
29 /**
30 * Constructs a 64-bit two's-complement integer, given its low and high 32-bit
31 * values as *signed* integers. See the from* functions below for more
32 * convenient ways of constructing Longs.
33 *
34 * The internal representation of a long is the two given signed, 32-bit values.
35 * We use 32-bit pieces because these are the size of integers on which
36 * Javascript performs bit-operations. For operations like addition and
37 * multiplication, we split each number into 16-bit pieces, which can easily be
38 * multiplied within Javascript's floating-point representation without overflow
39 * or change in sign.
40 *
41 * In the algorithms below, we frequently reduce the negative case to the
42 * positive case by negating the input(s) and then post-processing the result.
43 * Note that we must ALWAYS check specially whether those values are MIN_VALUE
44 * (-2^63) because -MIN_VALUE == MIN_VALUE (since 2^63 cannot be represented as
45 * a positive number, it overflows back into a negative). Not handling this
46 * case would often result in infinite recursion.
47 *
48 * @param {number} low The low (signed) 32 bits of the long.
49 * @param {number} high The high (signed) 32 bits of the long.
50 * @struct
51 * @constructor
52 * @final
53 */
54 goog.math.Long = function(low, high) {
55 /**
56 * @type {number}
57 * @private
58 */
59 this.low_ = low | 0; // force into 32 signed bits.
60
61 /**
62 * @type {number}
63 * @private
64 */
65 this.high_ = high | 0; // force into 32 signed bits.
66 };
67
68
69 // NOTE: Common constant values ZERO, ONE, NEG_ONE, etc. are defined below the
70 // from* methods on which they depend.
71
72
73 /**
74 * A cache of the Long representations of small integer values.
75 * @type {!Object<number, !goog.math.Long>}
76 * @private
77 */
78 goog.math.Long.IntCache_ = {};
79
80
81 /**
82 * A cache of the Long representations of common values.
83 * @type {!Object<goog.math.Long.ValueCacheId_, !goog.math.Long>}
84 * @private
85 */
86 goog.math.Long.valueCache_ = {};
87
88 /**
89 * Returns a cached long number representing the given (32-bit) integer value.
90 * @param {number} value The 32-bit integer in question.
91 * @return {!goog.math.Long} The corresponding Long value.
92 * @private
93 */
94 goog.math.Long.getCachedIntValue_ = function(value) {
95 return goog.reflect.cache(goog.math.Long.IntCache_, value, function(val) {
96 return new goog.math.Long(val, val < 0 ? -1 : 0);
97 });
98 };
99
100 /**
101 * The array of maximum values of a Long in string representation for a given
102 * radix between 2 and 36, inclusive.
103 * @private @const {!Array<string>}
104 */
105 goog.math.Long.MAX_VALUE_FOR_RADIX_ = [
106 '', '', // unused
107 '111111111111111111111111111111111111111111111111111111111111111',
108 // base 2
109 '2021110011022210012102010021220101220221', // base 3
110 '13333333333333333333333333333333', // base 4
111 '1104332401304422434310311212', // base 5
112 '1540241003031030222122211', // base 6
113 '22341010611245052052300', // base 7
114 '777777777777777777777', // base 8
115 '67404283172107811827', // base 9
116 '9223372036854775807', // base 10
117 '1728002635214590697', // base 11
118 '41a792678515120367', // base 12
119 '10b269549075433c37', // base 13
120 '4340724c6c71dc7a7', // base 14
121 '160e2ad3246366807', // base 15
122 '7fffffffffffffff', // base 16
123 '33d3d8307b214008', // base 17
124 '16agh595df825fa7', // base 18
125 'ba643dci0ffeehh', // base 19
126 '5cbfjia3fh26ja7', // base 20
127 '2heiciiie82dh97', // base 21
128 '1adaibb21dckfa7', // base 22
129 'i6k448cf4192c2', // base 23
130 'acd772jnc9l0l7', // base 24
131 '64ie1focnn5g77', // base 25
132 '3igoecjbmca687', // base 26
133 '27c48l5b37oaop', // base 27
134 '1bk39f3ah3dmq7', // base 28
135 'q1se8f0m04isb', // base 29
136 'hajppbc1fc207', // base 30
137 'bm03i95hia437', // base 31
138 '7vvvvvvvvvvvv', // base 32
139 '5hg4ck9jd4u37', // base 33
140 '3tdtk1v8j6tpp', // base 34
141 '2pijmikexrxp7', // base 35
142 '1y2p0ij32e8e7' // base 36
143 ];
144
145
146 /**
147 * The array of minimum values of a Long in string representation for a given
148 * radix between 2 and 36, inclusive.
149 * @private @const {!Array<string>}
150 */
151 goog.math.Long.MIN_VALUE_FOR_RADIX_ = [
152 '', '', // unused
153 '-1000000000000000000000000000000000000000000000000000000000000000',
154 // base 2
155 '-2021110011022210012102010021220101220222', // base 3
156 '-20000000000000000000000000000000', // base 4
157 '-1104332401304422434310311213', // base 5
158 '-1540241003031030222122212', // base 6
159 '-22341010611245052052301', // base 7
160 '-1000000000000000000000', // base 8
161 '-67404283172107811828', // base 9
162 '-9223372036854775808', // base 10
163 '-1728002635214590698', // base 11
164 '-41a792678515120368', // base 12
165 '-10b269549075433c38', // base 13
166 '-4340724c6c71dc7a8', // base 14
167 '-160e2ad3246366808', // base 15
168 '-8000000000000000', // base 16
169 '-33d3d8307b214009', // base 17
170 '-16agh595df825fa8', // base 18
171 '-ba643dci0ffeehi', // base 19
172 '-5cbfjia3fh26ja8', // base 20
173 '-2heiciiie82dh98', // base 21
174 '-1adaibb21dckfa8', // base 22
175 '-i6k448cf4192c3', // base 23
176 '-acd772jnc9l0l8', // base 24
177 '-64ie1focnn5g78', // base 25
178 '-3igoecjbmca688', // base 26
179 '-27c48l5b37oaoq', // base 27
180 '-1bk39f3ah3dmq8', // base 28
181 '-q1se8f0m04isc', // base 29
182 '-hajppbc1fc208', // base 30
183 '-bm03i95hia438', // base 31
184 '-8000000000000', // base 32
185 '-5hg4ck9jd4u38', // base 33
186 '-3tdtk1v8j6tpq', // base 34
187 '-2pijmikexrxp8', // base 35
188 '-1y2p0ij32e8e8' // base 36
189 ];
190
191
192 /**
193 * Returns a Long representing the given (32-bit) integer value.
194 * @param {number} value The 32-bit integer in question.
195 * @return {!goog.math.Long} The corresponding Long value.
196 */
197 goog.math.Long.fromInt = function(value) {
198 var intValue = value | 0;
199 goog.asserts.assert(value === intValue, 'value should be a 32-bit integer');
200
201 if (-128 <= intValue && intValue < 128) {
202 return goog.math.Long.getCachedIntValue_(intValue);
203 } else {
204 return new goog.math.Long(intValue, intValue < 0 ? -1 : 0);
205 }
206 };
207
208
209 /**
210 * Returns a Long representing the given value.
211 * NaN will be returned as zero. Infinity is converted to max value and
212 * -Infinity to min value.
213 * @param {number} value The number in question.
214 * @return {!goog.math.Long} The corresponding Long value.
215 */
216 goog.math.Long.fromNumber = function(value) {
217 if (isNaN(value)) {
218 return goog.math.Long.getZero();
219 } else if (value <= -goog.math.Long.TWO_PWR_63_DBL_) {
220 return goog.math.Long.getMinValue();
221 } else if (value + 1 >= goog.math.Long.TWO_PWR_63_DBL_) {
222 return goog.math.Long.getMaxValue();
223 } else if (value < 0) {
224 return goog.math.Long.fromNumber(-value).negate();
225 } else {
226 return new goog.math.Long(
227 (value % goog.math.Long.TWO_PWR_32_DBL_) | 0,
228 (value / goog.math.Long.TWO_PWR_32_DBL_) | 0);
229 }
230 };
231
232
233 /**
234 * Returns a Long representing the 64-bit integer that comes by concatenating
235 * the given high and low bits. Each is assumed to use 32 bits.
236 * @param {number} lowBits The low 32-bits.
237 * @param {number} highBits The high 32-bits.
238 * @return {!goog.math.Long} The corresponding Long value.
239 */
240 goog.math.Long.fromBits = function(lowBits, highBits) {
241 return new goog.math.Long(lowBits, highBits);
242 };
243
244
245 /**
246 * Returns a Long representation of the given string, written using the given
247 * radix.
248 * @param {string} str The textual representation of the Long.
249 * @param {number=} opt_radix The radix in which the text is written.
250 * @return {!goog.math.Long} The corresponding Long value.
251 */
252 goog.math.Long.fromString = function(str, opt_radix) {
253 if (str.length == 0) {
254 throw new Error('number format error: empty string');
255 }
256
257 var radix = opt_radix || 10;
258 if (radix < 2 || 36 < radix) {
259 throw new Error('radix out of range: ' + radix);
260 }
261
262 if (str.charAt(0) == '-') {
263 return goog.math.Long.fromString(str.substring(1), radix).negate();
264 } else if (str.indexOf('-') >= 0) {
265 throw new Error('number format error: interior "-" character: ' + str);
266 }
267
268 // Do several (8) digits each time through the loop, so as to
269 // minimize the calls to the very expensive emulated div.
270 var radixToPower = goog.math.Long.fromNumber(Math.pow(radix, 8));
271
272 var result = goog.math.Long.getZero();
273 for (var i = 0; i < str.length; i += 8) {
274 var size = Math.min(8, str.length - i);
275 var value = parseInt(str.substring(i, i + size), radix);
276 if (size < 8) {
277 var power = goog.math.Long.fromNumber(Math.pow(radix, size));
278 result = result.multiply(power).add(goog.math.Long.fromNumber(value));
279 } else {
280 result = result.multiply(radixToPower);
281 result = result.add(goog.math.Long.fromNumber(value));
282 }
283 }
284 return result;
285 };
286
287 /**
288 * Returns the boolean value of whether the input string is within a Long's
289 * range. Assumes an input string containing only numeric characters with an
290 * optional preceding '-'.
291 * @param {string} str The textual representation of the Long.
292 * @param {number=} opt_radix The radix in which the text is written.
293 * @return {boolean} Whether the string is within the range of a Long.
294 */
295 goog.math.Long.isStringInRange = function(str, opt_radix) {
296 var radix = opt_radix || 10;
297 if (radix < 2 || 36 < radix) {
298 throw new Error('radix out of range: ' + radix);
299 }
300
301 var extremeValue = (str.charAt(0) == '-') ?
302 goog.math.Long.MIN_VALUE_FOR_RADIX_[radix] :
303 goog.math.Long.MAX_VALUE_FOR_RADIX_[radix];
304
305 if (str.length < extremeValue.length) {
306 return true;
307 } else if (str.length == extremeValue.length && str <= extremeValue) {
308 return true;
309 } else {
310 return false;
311 }
312 };
313
314 // NOTE: the compiler should inline these constant values below and then remove
315 // these variables, so there should be no runtime penalty for these.
316
317
318 /**
319 * Number used repeated below in calculations. This must appear before the
320 * first call to any from* function below.
321 * @type {number}
322 * @private
323 */
324 goog.math.Long.TWO_PWR_16_DBL_ = 1 << 16;
325
326
327 /**
328 * @type {number}
329 * @private
330 */
331 goog.math.Long.TWO_PWR_32_DBL_ =
332 goog.math.Long.TWO_PWR_16_DBL_ * goog.math.Long.TWO_PWR_16_DBL_;
333
334
335 /**
336 * @type {number}
337 * @private
338 */
339 goog.math.Long.TWO_PWR_64_DBL_ =
340 goog.math.Long.TWO_PWR_32_DBL_ * goog.math.Long.TWO_PWR_32_DBL_;
341
342
343 /**
344 * @type {number}
345 * @private
346 */
347 goog.math.Long.TWO_PWR_63_DBL_ = goog.math.Long.TWO_PWR_64_DBL_ / 2;
348
349
350 /**
351 * @return {!goog.math.Long}
352 * @public
353 */
354 goog.math.Long.getZero = function() {
355 return goog.math.Long.getCachedIntValue_(0);
356 };
357
358
359 /**
360 * @return {!goog.math.Long}
361 * @public
362 */
363 goog.math.Long.getOne = function() {
364 return goog.math.Long.getCachedIntValue_(1);
365 };
366
367
368 /**
369 * @return {!goog.math.Long}
370 * @public
371 */
372 goog.math.Long.getNegOne = function() {
373 return goog.math.Long.getCachedIntValue_(-1);
374 };
375
376
377 /**
378 * @return {!goog.math.Long}
379 * @public
380 */
381 goog.math.Long.getMaxValue = function() {
382 return goog.reflect.cache(
383 goog.math.Long.valueCache_, goog.math.Long.ValueCacheId_.MAX_VALUE,
384 function() {
385 return goog.math.Long.fromBits(0xFFFFFFFF | 0, 0x7FFFFFFF | 0);
386 });
387 };
388
389
390 /**
391 * @return {!goog.math.Long}
392 * @public
393 */
394 goog.math.Long.getMinValue = function() {
395 return goog.reflect.cache(
396 goog.math.Long.valueCache_, goog.math.Long.ValueCacheId_.MIN_VALUE,
397 function() { return goog.math.Long.fromBits(0, 0x80000000 | 0); });
398 };
399
400
401 /**
402 * @return {!goog.math.Long}
403 * @public
404 */
405 goog.math.Long.getTwoPwr24 = function() {
406 return goog.reflect.cache(
407 goog.math.Long.valueCache_, goog.math.Long.ValueCacheId_.TWO_PWR_24,
408 function() { return goog.math.Long.fromInt(1 << 24); });
409 };
410
411
412 /** @return {number} The value, assuming it is a 32-bit integer. */
413 goog.math.Long.prototype.toInt = function() {
414 return this.low_;
415 };
416
417
418 /** @return {number} The closest floating-point representation to this value. */
419 goog.math.Long.prototype.toNumber = function() {
420 return this.high_ * goog.math.Long.TWO_PWR_32_DBL_ +
421 this.getLowBitsUnsigned();
422 };
423
424
425 /**
426 * @param {number=} opt_radix The radix in which the text should be written.
427 * @return {string} The textual representation of this value.
428 * @override
429 */
430 goog.math.Long.prototype.toString = function(opt_radix) {
431 var radix = opt_radix || 10;
432 if (radix < 2 || 36 < radix) {
433 throw new Error('radix out of range: ' + radix);
434 }
435
436 if (this.isZero()) {
437 return '0';
438 }
439
440 if (this.isNegative()) {
441 if (this.equals(goog.math.Long.getMinValue())) {
442 // We need to change the Long value before it can be negated, so we remove
443 // the bottom-most digit in this base and then recurse to do the rest.
444 var radixLong = goog.math.Long.fromNumber(radix);
445 var div = this.div(radixLong);
446 var rem = div.multiply(radixLong).subtract(this);
447 return div.toString(radix) + rem.toInt().toString(radix);
448 } else {
449 return '-' + this.negate().toString(radix);
450 }
451 }
452
453 // Do several (6) digits each time through the loop, so as to
454 // minimize the calls to the very expensive emulated div.
455 var radixToPower = goog.math.Long.fromNumber(Math.pow(radix, 6));
456
457 var rem = this;
458 var result = '';
459 while (true) {
460 var remDiv = rem.div(radixToPower);
461 // The right shifting fixes negative values in the case when
462 // intval >= 2^31; for more details see
463 // https://github.com/google/closure-library/pull/498
464 var intval = rem.subtract(remDiv.multiply(radixToPower)).toInt() >>> 0;
465 var digits = intval.toString(radix);
466
467 rem = remDiv;
468 if (rem.isZero()) {
469 return digits + result;
470 } else {
471 while (digits.length < 6) {
472 digits = '0' + digits;
473 }
474 result = '' + digits + result;
475 }
476 }
477 };
478
479
480 /** @return {number} The high 32-bits as a signed value. */
481 goog.math.Long.prototype.getHighBits = function() {
482 return this.high_;
483 };
484
485
486 /** @return {number} The low 32-bits as a signed value. */
487 goog.math.Long.prototype.getLowBits = function() {
488 return this.low_;
489 };
490
491
492 /** @return {number} The low 32-bits as an unsigned value. */
493 goog.math.Long.prototype.getLowBitsUnsigned = function() {
494 return (this.low_ >= 0) ? this.low_ :
495 goog.math.Long.TWO_PWR_32_DBL_ + this.low_;
496 };
497
498
499 /**
500 * @return {number} Returns the number of bits needed to represent the absolute
501 * value of this Long.
502 */
503 goog.math.Long.prototype.getNumBitsAbs = function() {
504 if (this.isNegative()) {
505 if (this.equals(goog.math.Long.getMinValue())) {
506 return 64;
507 } else {
508 return this.negate().getNumBitsAbs();
509 }
510 } else {
511 var val = this.high_ != 0 ? this.high_ : this.low_;
512 for (var bit = 31; bit > 0; bit--) {
513 if ((val & (1 << bit)) != 0) {
514 break;
515 }
516 }
517 return this.high_ != 0 ? bit + 33 : bit + 1;
518 }
519 };
520
521
522 /** @return {boolean} Whether this value is zero. */
523 goog.math.Long.prototype.isZero = function() {
524 return this.high_ == 0 && this.low_ == 0;
525 };
526
527
528 /** @return {boolean} Whether this value is negative. */
529 goog.math.Long.prototype.isNegative = function() {
530 return this.high_ < 0;
531 };
532
533
534 /** @return {boolean} Whether this value is odd. */
535 goog.math.Long.prototype.isOdd = function() {
536 return (this.low_ & 1) == 1;
537 };
538
539
540 /**
541 * @param {goog.math.Long} other Long to compare against.
542 * @return {boolean} Whether this Long equals the other.
543 */
544 goog.math.Long.prototype.equals = function(other) {
545 return (this.high_ == other.high_) && (this.low_ == other.low_);
546 };
547
548
549 /**
550 * @param {goog.math.Long} other Long to compare against.
551 * @return {boolean} Whether this Long does not equal the other.
552 */
553 goog.math.Long.prototype.notEquals = function(other) {
554 return (this.high_ != other.high_) || (this.low_ != other.low_);
555 };
556
557
558 /**
559 * @param {goog.math.Long} other Long to compare against.
560 * @return {boolean} Whether this Long is less than the other.
561 */
562 goog.math.Long.prototype.lessThan = function(other) {
563 return this.compare(other) < 0;
564 };
565
566
567 /**
568 * @param {goog.math.Long} other Long to compare against.
569 * @return {boolean} Whether this Long is less than or equal to the other.
570 */
571 goog.math.Long.prototype.lessThanOrEqual = function(other) {
572 return this.compare(other) <= 0;
573 };
574
575
576 /**
577 * @param {goog.math.Long} other Long to compare against.
578 * @return {boolean} Whether this Long is greater than the other.
579 */
580 goog.math.Long.prototype.greaterThan = function(other) {
581 return this.compare(other) > 0;
582 };
583
584
585 /**
586 * @param {goog.math.Long} other Long to compare against.
587 * @return {boolean} Whether this Long is greater than or equal to the other.
588 */
589 goog.math.Long.prototype.greaterThanOrEqual = function(other) {
590 return this.compare(other) >= 0;
591 };
592
593
594 /**
595 * Compares this Long with the given one.
596 * @param {goog.math.Long} other Long to compare against.
597 * @return {number} 0 if they are the same, 1 if the this is greater, and -1
598 * if the given one is greater.
599 */
600 goog.math.Long.prototype.compare = function(other) {
601 if (this.equals(other)) {
602 return 0;
603 }
604
605 var thisNeg = this.isNegative();
606 var otherNeg = other.isNegative();
607 if (thisNeg && !otherNeg) {
608 return -1;
609 }
610 if (!thisNeg && otherNeg) {
611 return 1;
612 }
613
614 // at this point, the signs are the same, so subtraction will not overflow
615 if (this.subtract(other).isNegative()) {
616 return -1;
617 } else {
618 return 1;
619 }
620 };
621
622
623 /** @return {!goog.math.Long} The negation of this value. */
624 goog.math.Long.prototype.negate = function() {
625 if (this.equals(goog.math.Long.getMinValue())) {
626 return goog.math.Long.getMinValue();
627 } else {
628 return this.not().add(goog.math.Long.getOne());
629 }
630 };
631
632
633 /**
634 * Returns the sum of this and the given Long.
635 * @param {goog.math.Long} other Long to add to this one.
636 * @return {!goog.math.Long} The sum of this and the given Long.
637 */
638 goog.math.Long.prototype.add = function(other) {
639 // Divide each number into 4 chunks of 16 bits, and then sum the chunks.
640
641 var a48 = this.high_ >>> 16;
642 var a32 = this.high_ & 0xFFFF;
643 var a16 = this.low_ >>> 16;
644 var a00 = this.low_ & 0xFFFF;
645
646 var b48 = other.high_ >>> 16;
647 var b32 = other.high_ & 0xFFFF;
648 var b16 = other.low_ >>> 16;
649 var b00 = other.low_ & 0xFFFF;
650
651 var c48 = 0, c32 = 0, c16 = 0, c00 = 0;
652 c00 += a00 + b00;
653 c16 += c00 >>> 16;
654 c00 &= 0xFFFF;
655 c16 += a16 + b16;
656 c32 += c16 >>> 16;
657 c16 &= 0xFFFF;
658 c32 += a32 + b32;
659 c48 += c32 >>> 16;
660 c32 &= 0xFFFF;
661 c48 += a48 + b48;
662 c48 &= 0xFFFF;
663 return goog.math.Long.fromBits((c16 << 16) | c00, (c48 << 16) | c32);
664 };
665
666
667 /**
668 * Returns the difference of this and the given Long.
669 * @param {goog.math.Long} other Long to subtract from this.
670 * @return {!goog.math.Long} The difference of this and the given Long.
671 */
672 goog.math.Long.prototype.subtract = function(other) {
673 return this.add(other.negate());
674 };
675
676
677 /**
678 * Returns the product of this and the given long.
679 * @param {goog.math.Long} other Long to multiply with this.
680 * @return {!goog.math.Long} The product of this and the other.
681 */
682 goog.math.Long.prototype.multiply = function(other) {
683 if (this.isZero()) {
684 return goog.math.Long.getZero();
685 } else if (other.isZero()) {
686 return goog.math.Long.getZero();
687 }
688
689 if (this.equals(goog.math.Long.getMinValue())) {
690 return other.isOdd() ? goog.math.Long.getMinValue() :
691 goog.math.Long.getZero();
692 } else if (other.equals(goog.math.Long.getMinValue())) {
693 return this.isOdd() ? goog.math.Long.getMinValue() :
694 goog.math.Long.getZero();
695 }
696
697 if (this.isNegative()) {
698 if (other.isNegative()) {
699 return this.negate().multiply(other.negate());
700 } else {
701 return this.negate().multiply(other).negate();
702 }
703 } else if (other.isNegative()) {
704 return this.multiply(other.negate()).negate();
705 }
706
707 // If both longs are small, use float multiplication
708 if (this.lessThan(goog.math.Long.getTwoPwr24()) &&
709 other.lessThan(goog.math.Long.getTwoPwr24())) {
710 return goog.math.Long.fromNumber(this.toNumber() * other.toNumber());
711 }
712
713 // Divide each long into 4 chunks of 16 bits, and then add up 4x4 products.
714 // We can skip products that would overflow.
715
716 var a48 = this.high_ >>> 16;
717 var a32 = this.high_ & 0xFFFF;
718 var a16 = this.low_ >>> 16;
719 var a00 = this.low_ & 0xFFFF;
720
721 var b48 = other.high_ >>> 16;
722 var b32 = other.high_ & 0xFFFF;
723 var b16 = other.low_ >>> 16;
724 var b00 = other.low_ & 0xFFFF;
725
726 var c48 = 0, c32 = 0, c16 = 0, c00 = 0;
727 c00 += a00 * b00;
728 c16 += c00 >>> 16;
729 c00 &= 0xFFFF;
730 c16 += a16 * b00;
731 c32 += c16 >>> 16;
732 c16 &= 0xFFFF;
733 c16 += a00 * b16;
734 c32 += c16 >>> 16;
735 c16 &= 0xFFFF;
736 c32 += a32 * b00;
737 c48 += c32 >>> 16;
738 c32 &= 0xFFFF;
739 c32 += a16 * b16;
740 c48 += c32 >>> 16;
741 c32 &= 0xFFFF;
742 c32 += a00 * b32;
743 c48 += c32 >>> 16;
744 c32 &= 0xFFFF;
745 c48 += a48 * b00 + a32 * b16 + a16 * b32 + a00 * b48;
746 c48 &= 0xFFFF;
747 return goog.math.Long.fromBits((c16 << 16) | c00, (c48 << 16) | c32);
748 };
749
750
751 /**
752 * Returns this Long divided by the given one.
753 * @param {goog.math.Long} other Long by which to divide.
754 * @return {!goog.math.Long} This Long divided by the given one.
755 */
756 goog.math.Long.prototype.div = function(other) {
757 if (other.isZero()) {
758 throw new Error('division by zero');
759 } else if (this.isZero()) {
760 return goog.math.Long.getZero();
761 }
762
763 if (this.equals(goog.math.Long.getMinValue())) {
764 if (other.equals(goog.math.Long.getOne()) ||
765 other.equals(goog.math.Long.getNegOne())) {
766 return goog.math.Long.getMinValue(); // recall -MIN_VALUE == MIN_VALUE
767 } else if (other.equals(goog.math.Long.getMinValue())) {
768 return goog.math.Long.getOne();
769 } else {
770 // At this point, we have |other| >= 2, so |this/other| < |MIN_VALUE|.
771 var halfThis = this.shiftRight(1);
772 var approx = halfThis.div(other).shiftLeft(1);
773 if (approx.equals(goog.math.Long.getZero())) {
774 return other.isNegative() ? goog.math.Long.getOne() :
775 goog.math.Long.getNegOne();
776 } else {
777 var rem = this.subtract(other.multiply(approx));
778 var result = approx.add(rem.div(other));
779 return result;
780 }
781 }
782 } else if (other.equals(goog.math.Long.getMinValue())) {
783 return goog.math.Long.getZero();
784 }
785
786 if (this.isNegative()) {
787 if (other.isNegative()) {
788 return this.negate().div(other.negate());
789 } else {
790 return this.negate().div(other).negate();
791 }
792 } else if (other.isNegative()) {
793 return this.div(other.negate()).negate();
794 }
795
796 // Repeat the following until the remainder is less than other: find a
797 // floating-point that approximates remainder / other *from below*, add this
798 // into the result, and subtract it from the remainder. It is critical that
799 // the approximate value is less than or equal to the real value so that the
800 // remainder never becomes negative.
801 var res = goog.math.Long.getZero();
802 var rem = this;
803 while (rem.greaterThanOrEqual(other)) {
804 // Approximate the result of division. This may be a little greater or
805 // smaller than the actual value.
806 var approx = Math.max(1, Math.floor(rem.toNumber() / other.toNumber()));
807
808 // We will tweak the approximate result by changing it in the 48-th digit or
809 // the smallest non-fractional digit, whichever is larger.
810 var log2 = Math.ceil(Math.log(approx) / Math.LN2);
811 var delta = (log2 <= 48) ? 1 : Math.pow(2, log2 - 48);
812
813 // Decrease the approximation until it is smaller than the remainder. Note
814 // that if it is too large, the product overflows and is negative.
815 var approxRes = goog.math.Long.fromNumber(approx);
816 var approxRem = approxRes.multiply(other);
817 while (approxRem.isNegative() || approxRem.greaterThan(rem)) {
818 approx -= delta;
819 approxRes = goog.math.Long.fromNumber(approx);
820 approxRem = approxRes.multiply(other);
821 }
822
823 // We know the answer can't be zero... and actually, zero would cause
824 // infinite recursion since we would make no progress.
825 if (approxRes.isZero()) {
826 approxRes = goog.math.Long.getOne();
827 }
828
829 res = res.add(approxRes);
830 rem = rem.subtract(approxRem);
831 }
832 return res;
833 };
834
835
836 /**
837 * Returns this Long modulo the given one.
838 * @param {goog.math.Long} other Long by which to mod.
839 * @return {!goog.math.Long} This Long modulo the given one.
840 */
841 goog.math.Long.prototype.modulo = function(other) {
842 return this.subtract(this.div(other).multiply(other));
843 };
844
845
846 /** @return {!goog.math.Long} The bitwise-NOT of this value. */
847 goog.math.Long.prototype.not = function() {
848 return goog.math.Long.fromBits(~this.low_, ~this.high_);
849 };
850
851
852 /**
853 * Returns the bitwise-AND of this Long and the given one.
854 * @param {goog.math.Long} other The Long with which to AND.
855 * @return {!goog.math.Long} The bitwise-AND of this and the other.
856 */
857 goog.math.Long.prototype.and = function(other) {
858 return goog.math.Long.fromBits(
859 this.low_ & other.low_, this.high_ & other.high_);
860 };
861
862
863 /**
864 * Returns the bitwise-OR of this Long and the given one.
865 * @param {goog.math.Long} other The Long with which to OR.
866 * @return {!goog.math.Long} The bitwise-OR of this and the other.
867 */
868 goog.math.Long.prototype.or = function(other) {
869 return goog.math.Long.fromBits(
870 this.low_ | other.low_, this.high_ | other.high_);
871 };
872
873
874 /**
875 * Returns the bitwise-XOR of this Long and the given one.
876 * @param {goog.math.Long} other The Long with which to XOR.
877 * @return {!goog.math.Long} The bitwise-XOR of this and the other.
878 */
879 goog.math.Long.prototype.xor = function(other) {
880 return goog.math.Long.fromBits(
881 this.low_ ^ other.low_, this.high_ ^ other.high_);
882 };
883
884
885 /**
886 * Returns this Long with bits shifted to the left by the given amount.
887 * @param {number} numBits The number of bits by which to shift.
888 * @return {!goog.math.Long} This shifted to the left by the given amount.
889 */
890 goog.math.Long.prototype.shiftLeft = function(numBits) {
891 numBits &= 63;
892 if (numBits == 0) {
893 return this;
894 } else {
895 var low = this.low_;
896 if (numBits < 32) {
897 var high = this.high_;
898 return goog.math.Long.fromBits(
899 low << numBits, (high << numBits) | (low >>> (32 - numBits)));
900 } else {
901 return goog.math.Long.fromBits(0, low << (numBits - 32));
902 }
903 }
904 };
905
906
907 /**
908 * Returns this Long with bits shifted to the right by the given amount.
909 * The new leading bits match the current sign bit.
910 * @param {number} numBits The number of bits by which to shift.
911 * @return {!goog.math.Long} This shifted to the right by the given amount.
912 */
913 goog.math.Long.prototype.shiftRight = function(numBits) {
914 numBits &= 63;
915 if (numBits == 0) {
916 return this;
917 } else {
918 var high = this.high_;
919 if (numBits < 32) {
920 var low = this.low_;
921 return goog.math.Long.fromBits(
922 (low >>> numBits) | (high << (32 - numBits)), high >> numBits);
923 } else {
924 return goog.math.Long.fromBits(
925 high >> (numBits - 32), high >= 0 ? 0 : -1);
926 }
927 }
928 };
929
930
931 /**
932 * Returns this Long with bits shifted to the right by the given amount, with
933 * zeros placed into the new leading bits.
934 * @param {number} numBits The number of bits by which to shift.
935 * @return {!goog.math.Long} This shifted to the right by the given amount, with
936 * zeros placed into the new leading bits.
937 */
938 goog.math.Long.prototype.shiftRightUnsigned = function(numBits) {
939 numBits &= 63;
940 if (numBits == 0) {
941 return this;
942 } else {
943 var high = this.high_;
944 if (numBits < 32) {
945 var low = this.low_;
946 return goog.math.Long.fromBits(
947 (low >>> numBits) | (high << (32 - numBits)), high >>> numBits);
948 } else if (numBits == 32) {
949 return goog.math.Long.fromBits(high, 0);
950 } else {
951 return goog.math.Long.fromBits(high >>> (numBits - 32), 0);
952 }
953 }
954 };
955
956
957 /**
958 * @enum {number} Ids of commonly requested Long instances.
959 * @private
960 */
961 goog.math.Long.ValueCacheId_ = {
962 MAX_VALUE: 1,
963 MIN_VALUE: 2,
964 TWO_PWR_24: 6
965 };