1 /***************************************
  2  * Copyright 2011, 2012 GlobWeb contributors.
  3  *
  4  * This file is part of GlobWeb.
  5  *
  6  * GlobWeb is free software: you can redistribute it and/or modify
  7  * it under the terms of the GNU Lesser General Public License as published by
  8  * the Free Software Foundation, version 3 of the License, or
  9  * (at your option) any later version.
 10  *
 11  * GlobWeb is distributed in the hope that it will be useful,
 12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 14  * GNU Lesser General Public License for more details.
 15  *
 16  * You should have received a copy of the GNU General Public License
 17  * along with GlobWeb. If not, see <http://www.gnu.org/licenses/>.
 18  ***************************************/
 19 /***************************************
 20  * Copyright 2009 The Closure Library Authors. All Rights Reserved. (Apache License, Version 2.0)
 21  * Copyright 2011, 2012 GlobWeb contributors.
 22  *
 23  * This file is part of GlobWeb.
 24  *
 25  * GlobWeb is free software: you can redistribute it and/or modify
 26  * it under the terms of the GNU Lesser General Public License as published by
 27  * the Free Software Foundation, version 3 of the License, or
 28  * (at your option) any later version.
 29  *
 30  * GlobWeb is distributed in the hope that it will be useful,
 31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 33  * GNU Lesser General Public License for more details.
 34  *
 35  * You should have received a copy of the GNU General Public License
 36  * along with GlobWeb. If not, see <http://www.gnu.org/licenses/>.
 37  ***************************************/
 38 
 39 define(function() {
 40 
 41 
 42 /**************************************************************************************************************/
 43 
 44 /**
 45 *	@constructor Long
 46 *	Long class for only unsigned integers
 47 */
 48 
 49 /**
 50  * Constructs a 64-bit two's-complement integer, given its low and high 32-bit
 51  * values as *signed* integers.  See the from* functions below for more
 52  * convenient ways of constructing Longs.
 53  *
 54  * The internal representation of a long is the two given signed, 32-bit values.
 55  * We use 32-bit pieces because these are the size of integers on which
 56  * Javascript performs bit-operations.  For operations like addition and
 57  * multiplication, we split each number into 16-bit pieces, which can easily be
 58  * multiplied within Javascript's floating-point representation without overflow
 59  * or change in sign.
 60  *
 61  * In the algorithms below, we frequently reduce the negative case to the
 62  * positive case by negating the input(s) and then post-processing the result.
 63  * Note that we must ALWAYS check specially whether those values are MIN_VALUE
 64  * (-2^63) because -MIN_VALUE == MIN_VALUE (since 2^63 cannot be represented as
 65  * a positive number, it overflows back into a negative).  Not handling this
 66  * case would often result in infinite recursion.
 67  *
 68  * @param {number} low  The low (signed) 32 bits of the long.
 69  * @param {number} high  The high (signed) 32 bits of the long.
 70  * @constructor
 71  */
 72 var Long = function(low, high) {
 73   /**
 74    * @type {number}
 75    * @private
 76    */
 77   this.low_ = low | 0;  // force into 32 signed bits.
 78 
 79   /**
 80    * @type {number}
 81    * @private
 82    */
 83   this.high_ = high | 0;  // force into 32 signed bits.
 84 };
 85 
 86 /**
 87  * A cache of the Long representations of small integer values.
 88  * @type {!Object}
 89  * @private
 90  */
 91 Long.IntCache_ = {};
 92 
 93 /**
 94  * Returns a Long representing the given (32-bit) integer value.
 95  * @param {number} value The 32-bit integer in question.
 96  * @return {!Long} The corresponding Long value.
 97  */
 98 Long.fromInt = function(value) {
 99   if (-128 <= value && value < 128) {
100     var cachedObj = Long.IntCache_[value];
101     if (cachedObj) {
102       return cachedObj;
103     }
104   }
105 
106   var obj = new Long(value | 0, value < 0 ? -1 : 0);
107   if (-128 <= value && value < 128) {
108     Long.IntCache_[value] = obj;
109   }
110   return obj;
111 };
112 
113 /**
114  * Returns a Long representing the given value, provided that it is a finite
115  * number.  Otherwise, zero is returned.
116  * @param {number} value The number in question.
117  * @return {!Long} The corresponding Long value.
118  */
119 Long.fromNumber = function(value) {
120   if (isNaN(value) || !isFinite(value)) {
121     return Long.ZERO;
122   } else if (value <= -Long.TWO_PWR_63_DBL_) {
123     return Long.MIN_VALUE;
124   } else if (value + 1 >= Long.TWO_PWR_63_DBL_) {
125     return Long.MAX_VALUE;
126   } else if (value < 0) {
127     return Long.fromNumber(-value).negate();
128   } else {
129     return new Long(
130         (value % Long.TWO_PWR_32_DBL_) | 0,
131         (value / Long.TWO_PWR_32_DBL_) | 0);
132   }
133 };
134 
135 /**
136  * Returns a Long representing the 64-bit integer that comes by concatenating
137  * the given high and low bits.  Each is assumed to use 32 bits.
138  * @param {number} lowBits The low 32-bits.
139  * @param {number} highBits The high 32-bits.
140  * @return {!Long} The corresponding Long value.
141  */
142 Long.fromBits = function(lowBits, highBits) {
143   return new Long(lowBits, highBits);
144 };
145 
146 /**
147  * Number used repeated below in calculations.  This must appear before the
148  * first call to any from* function below.
149  * @type {number}
150  * @private
151  */
152 Long.TWO_PWR_16_DBL_ = 1 << 16;
153 
154 
155 /**
156  * @type {number}
157  * @private
158  */
159 Long.TWO_PWR_24_DBL_ = 1 << 24;
160 
161 
162 /**
163  * @type {number}
164  * @private
165  */
166 Long.TWO_PWR_32_DBL_ =
167     Long.TWO_PWR_16_DBL_ * Long.TWO_PWR_16_DBL_;
168 
169 
170 /**
171  * @type {number}
172  * @private
173  */
174 Long.TWO_PWR_64_DBL_ =
175     Long.TWO_PWR_32_DBL_ * Long.TWO_PWR_32_DBL_;
176 
177 
178 /**
179  * @type {number}
180  * @private
181  */
182 Long.TWO_PWR_63_DBL_ =
183     Long.TWO_PWR_64_DBL_ / 2;
184 
185 
186 /** @type {!Long} */
187 Long.ZERO = Long.fromInt(0);
188 
189 
190 /** @type {!Long} */
191 Long.ONE = Long.fromInt(1);
192 
193 /** @type {!Long} */
194 Long.MAX_VALUE =
195     Long.fromBits(0xFFFFFFFF | 0, 0x7FFFFFFF | 0);
196 
197 
198 /** @type {!Long} */
199 Long.MIN_VALUE = Long.fromBits(0, 0x80000000 | 0);
200 
201 /**
202  * @type {!Long}
203  * @private
204  */
205 Long.TWO_PWR_24_ = Long.fromInt(1 << 24);
206 
207 
208 /** @return {number} The value, assuming it is a 32-bit integer. */
209 Long.prototype.toInt = function() {
210   return this.low_;
211 };
212 
213 /** @return {number} The closest floating-point representation to this value. */
214 Long.prototype.toNumber = function() {
215   return this.high_ * Long.TWO_PWR_32_DBL_ +
216          this.getLowBitsUnsigned();
217 };
218 
219 /** @return {number} The low 32-bits as an unsigned value. */
220 Long.prototype.getLowBitsUnsigned = function() {
221   return (this.low_ >= 0) ?
222       this.low_ : Long.TWO_PWR_32_DBL_ + this.low_;
223 };
224 
225 /** @return {boolean} Whether this value is zero. */
226 Long.prototype.isZero = function() {
227   return this.high_ == 0 && this.low_ == 0;
228 };
229 
230 
231 /** @return {boolean} Whether this value is negative. */
232 Long.prototype.isNegative = function() {
233   return this.high_ < 0;
234 };
235 
236 
237 /** @return {boolean} Whether this value is odd. */
238 Long.prototype.isOdd = function() {
239   return (this.low_ & 1) == 1;
240 };
241 
242 
243 /**
244  * @param {Long} other Long to compare against.
245  * @return {boolean} Whether this Long equals the other.
246  */
247 Long.prototype.equals = function(other) {
248   return (this.high_ == other.high_) && (this.low_ == other.low_);
249 };
250 
251 /**
252  * @param {Long} other Long to compare against.
253  * @return {boolean} Whether this Long is less than the other.
254  */
255 Long.prototype.lessThan = function(other) {
256   return this.compare(other) < 0;
257 };
258 
259 /**
260  * @param {Long} other Long to compare against.
261  * @return {boolean} Whether this Long is greater than or equal to the other.
262  */
263 Long.prototype.greaterThanOrEqual = function(other) {
264   return this.compare(other) >= 0;
265 };
266 
267 
268 /**
269  * Compares this Long with the given one.
270  * @param {Long} other Long to compare against.
271  * @return {number} 0 if they are the same, 1 if the this is greater, and -1
272  *     if the given one is greater.
273  */
274 Long.prototype.compare = function(other) {
275   if (this.equals(other)) {
276     return 0;
277   }
278 
279   var thisNeg = this.isNegative();
280   var otherNeg = other.isNegative();
281   if (thisNeg && !otherNeg) {
282     return -1;
283   }
284   if (!thisNeg && otherNeg) {
285     return 1;
286   }
287 
288   // at this point, the signs are the same, so subtraction will not overflow
289   if (this.subtract(other).isNegative()) {
290     return -1;
291   } else {
292     return 1;
293   }
294 };
295 
296 /** @return {!Long} The negation of this value. */
297 Long.prototype.negate = function() {
298   if (this.equals(Long.MIN_VALUE)) {
299     return Long.MIN_VALUE;
300   } else {
301     return this.not().add(Long.ONE);
302   }
303 };
304 
305 
306 /**
307  * Returns the sum of this and the given Long.
308  * @param {Long} other Long to add to this one.
309  * @return {!Long} The sum of this and the given Long.
310  */
311 Long.prototype.add = function(other) {
312   // Divide each number into 4 chunks of 16 bits, and then sum the chunks.
313 
314   var a48 = this.high_ >>> 16;
315   var a32 = this.high_ & 0xFFFF;
316   var a16 = this.low_ >>> 16;
317   var a00 = this.low_ & 0xFFFF;
318 
319   var b48 = other.high_ >>> 16;
320   var b32 = other.high_ & 0xFFFF;
321   var b16 = other.low_ >>> 16;
322   var b00 = other.low_ & 0xFFFF;
323 
324   var c48 = 0, c32 = 0, c16 = 0, c00 = 0;
325   c00 += a00 + b00;
326   c16 += c00 >>> 16;
327   c00 &= 0xFFFF;
328   c16 += a16 + b16;
329   c32 += c16 >>> 16;
330   c16 &= 0xFFFF;
331   c32 += a32 + b32;
332   c48 += c32 >>> 16;
333   c32 &= 0xFFFF;
334   c48 += a48 + b48;
335   c48 &= 0xFFFF;
336   return Long.fromBits((c16 << 16) | c00, (c48 << 16) | c32);
337 };
338 
339 
340 /**
341  * Returns the difference of this and the given Long.
342  * @param {Long} other Long to subtract from this.
343  * @return {!Long} The difference of this and the given Long.
344  */
345 Long.prototype.subtract = function(other) {
346   return this.add(other.negate());
347 };
348 
349 
350 /**
351  * Returns the product of this and the given long.
352  * @param {Long} other Long to multiply with this.
353  * @return {!Long} The product of this and the other.
354  */
355 Long.prototype.multiply = function(other) {
356   if (this.isZero()) {
357     return Long.ZERO;
358   } else if (other.isZero()) {
359     return Long.ZERO;
360   }
361 
362   if (this.equals(Long.MIN_VALUE)) {
363     return other.isOdd() ? Long.MIN_VALUE : Long.ZERO;
364   } else if (other.equals(Long.MIN_VALUE)) {
365     return this.isOdd() ? Long.MIN_VALUE : Long.ZERO;
366   }
367 
368   if (this.isNegative()) {
369     if (other.isNegative()) {
370       return this.negate().multiply(other.negate());
371     } else {
372       return this.negate().multiply(other).negate();
373     }
374   } else if (other.isNegative()) {
375     return this.multiply(other.negate()).negate();
376   }
377 
378   // If both longs are small, use float multiplication
379   if (this.lessThan(Long.TWO_PWR_24_) &&
380       other.lessThan(Long.TWO_PWR_24_)) {
381     return Long.fromNumber(this.toNumber() * other.toNumber());
382   }
383 
384   // Divide each long into 4 chunks of 16 bits, and then add up 4x4 products.
385   // We can skip products that would overflow.
386 
387   var a48 = this.high_ >>> 16;
388   var a32 = this.high_ & 0xFFFF;
389   var a16 = this.low_ >>> 16;
390   var a00 = this.low_ & 0xFFFF;
391 
392   var b48 = other.high_ >>> 16;
393   var b32 = other.high_ & 0xFFFF;
394   var b16 = other.low_ >>> 16;
395   var b00 = other.low_ & 0xFFFF;
396 
397   var c48 = 0, c32 = 0, c16 = 0, c00 = 0;
398   c00 += a00 * b00;
399   c16 += c00 >>> 16;
400   c00 &= 0xFFFF;
401   c16 += a16 * b00;
402   c32 += c16 >>> 16;
403   c16 &= 0xFFFF;
404   c16 += a00 * b16;
405   c32 += c16 >>> 16;
406   c16 &= 0xFFFF;
407   c32 += a32 * b00;
408   c48 += c32 >>> 16;
409   c32 &= 0xFFFF;
410   c32 += a16 * b16;
411   c48 += c32 >>> 16;
412   c32 &= 0xFFFF;
413   c32 += a00 * b32;
414   c48 += c32 >>> 16;
415   c32 &= 0xFFFF;
416   c48 += a48 * b00 + a32 * b16 + a16 * b32 + a00 * b48;
417   c48 &= 0xFFFF;
418   return Long.fromBits((c16 << 16) | c00, (c48 << 16) | c32);
419 };
420 
421 /** @return {!Long} The bitwise-NOT of this value. */
422 Long.prototype.not = function() {
423   return Long.fromBits(~this.low_, ~this.high_);
424 };
425 
426 
427 /**
428  * Returns the bitwise-AND of this Long and the given one.
429  * @param {Long} other The Long with which to AND.
430  * @return {!Long} The bitwise-AND of this and the other.
431  */
432 Long.prototype.and = function(other) {
433   return Long.fromBits(this.low_ & other.low_,
434                                  this.high_ & other.high_);
435 };
436 
437 
438 /**
439  * Returns the bitwise-OR of this Long and the given one.
440  * @param {Long} other The Long with which to OR.
441  * @return {!Long} The bitwise-OR of this and the other.
442  */
443 Long.prototype.or = function(other) {
444   return Long.fromBits(this.low_ | other.low_,
445                                  this.high_ | other.high_);
446 };
447 
448 /**
449  * Returns this Long with bits shifted to the right by the given amount, with
450  * the new top bits matching the current sign bit.
451  * @param {number} numBits The number of bits by which to shift.
452  * @return {!Long} This shifted to the right by the given amount, with
453  *     zeros placed into the new leading bits.
454  */
455 Long.prototype.shiftRightUnsigned = function(numBits) {
456   numBits &= 63;
457   if (numBits == 0) {
458     return this;
459   } else {
460     var high = this.high_;
461     if (numBits < 32) {
462       var low = this.low_;
463       return Long.fromBits(
464           (low >>> numBits) | (high << (32 - numBits)),
465           high >>> numBits);
466     } else if (numBits == 32) {
467       return Long.fromBits(high, 0);
468     } else {
469       return Long.fromBits(high >>> (numBits - 32), 0);
470     }
471   }
472 };
473 
474 /**************************************************************************************************************/
475 
476 return Long;
477 
478 });
479