Martin@438: // empty line needed here
Martin@445: Number.prototype.add32 = function(x) { return (this + x) | 0; };
Martin@445: Number.prototype.sub32 = function(x) { return (this - x) | 0; };
Martin@445: Number.prototype.mul32 = function(x) { 
Martin@445:     return (((this * (x >> 16)) << 16) + this * (x & 0xFFFF)) | 0;
Martin@438: };
Martin@439: 
Martin@445: Number.prototype.toInt8 = function()  { return (this << 24) >> 24; };
Martin@582: Number.prototype.toInt16 = function() { return (this << 16) >> 16; };
Martin@582: 
Martin@615: var __m32 = 0xFFFFFFFF;
Martin@615: 
Martin@594: Number.prototype.next32 = function(low) {
Martin@594:   if (this === 0) {
Martin@594:     return low;
Martin@594:   }
Martin@594:   var l = new Number(low);
Martin@616:   l.hi = this | 0;
Martin@594:   return l;
Martin@582: };
Martin@582: 
Martin@594: Number.prototype.high32 = function() { 
Martin@615:     return this.hi ? this.hi : (Math.floor(this / (__m32+1))) | 0;
Martin@594: };
Martin@594: Number.prototype.toInt32 = function() { return this | 0; };
Martin@594: Number.prototype.toFP = function() {
Martin@615:     return this.hi ? this.hi * (__m32+1) + this : this;
Martin@594: };
Martin@594: Number.prototype.toLong = function() {
Martin@615:     var hi = (this > __m32) ? (Math.floor(this / (__m32+1))) | 0 : 0;
Martin@616:     return hi.next32(Math.floor(this % (__m32+1)));
Martin@607: };
Martin@607: 
Martin@607: Number.prototype.toExactString = function() {
Martin@607:     if (this.hi) {
Martin@607:         var res = 0;
Martin@607:         var a = [ 6,9,2,7,6,9,4,9,2,4 ];
Martin@607:         var s = '';
Martin@607:         var digit;
Martin@675:         var neg = this.hi < 0;
Martin@675:         if (neg) {
Martin@675:             var x = this.neg64();
Martin@675:             var hi = x.hi;
Martin@675:             var low = x;
Martin@675:         } else {
Martin@675:             var hi = this.hi;
Martin@675:             var low = this;
Martin@675:         }
Martin@607:         for (var i = 0; i < a.length; i++) {
Martin@607:             res += hi * a[i];
Martin@607:             var low_digit = low % 10;
Martin@607:             digit = (res % 10) + low_digit;
Martin@607: 
Martin@607:             low = Math.floor(low / 10);
Martin@607:             res = Math.floor(res / 10);
Martin@607: 
Martin@607:             if (digit >= 10) {
Martin@607:                 digit -= 10;
Martin@607:                 res++;
Martin@607:             }
Martin@607:             s = String(digit).concat(s);
Martin@607:         }
Martin@675:         return (neg ? '-' : '').concat(res).concat(s);
Martin@607:     }
Martin@607:     return String(this);
Martin@607: };
Martin@594: 
Martin@594: Number.prototype.add64 = function(x) {
Martin@594:     var low = this + x;
Martin@594:     carry = 0;
Martin@615:     if (low > __m32) {
Martin@594:         carry = 1;
Martin@615:         low -= (__m32+1);
Martin@594:     }
Martin@615:     var hi = (this.high32() + x.high32() + carry) | 0;
Martin@594:     return hi.next32(low);
Martin@582: };
Martin@582: 
Martin@620: Number.prototype.sub64 = function(x) {
Martin@620:     var low = this - x;
Martin@620:     carry = 0;
Martin@620:     if (low < 0) {
Martin@620:         carry = 1;
Martin@620:         low += (__m32+1);
Martin@620:     }
Martin@620:     var hi = (this.high32() - x.high32() - carry) | 0;
Martin@620:     return hi.next32(low);
Martin@620: };
Martin@620: 
Martin@657: Number.prototype.mul64 = function(x) {
Martin@657:     var low = this.mul32(x);
Martin@657:     low += (low < 0) ? (__m32+1) : 0;
Martin@657:     // first count upper 32 bits of (this.low * x.low)
Martin@657:     var hi_hi = 0;
Martin@657:     var hi_low = 0;
Martin@657:     var m = 1;
Martin@657:     for (var i = 0; i < 32; i++) {
Martin@657:         if (x & m) {
Martin@657:             hi_hi += this >>> 16;
Martin@657:             hi_low += this & 0xFFFF
Martin@657:         }
Martin@657:         hi_low >>= 1;
Martin@657:         hi_low += (hi_hi & 1) ? 0x8000 : 0;
Martin@657:         hi_hi >>= 1;
Martin@657:         m <<= 1;
Martin@657:     }
Martin@657:     var hi = (hi_hi << 16) + hi_low;
Martin@657:     
Martin@657:     var m1 = this.high32().mul32(x);
Martin@657:     var m2 = this.mul32(x.high32());
Martin@657:     hi = hi.add32(m1).add32(m2);
Martin@657:     
Martin@657:     return hi.next32(low);
Martin@657: };
Martin@657: 
Martin@615: Number.prototype.and64 = function(x) {
Martin@615:     var low = this & x;
Martin@627:     low += (low < 0) ? (__m32+1) : 0;
Martin@615:     if (this.hi && x.hi) {
Martin@615:         var hi = this.hi & x.hi;
Martin@615:         return hi.next32(low);
Martin@615:     };
Martin@615:     return low;
Martin@615: };
Martin@615: 
Martin@627: Number.prototype.or64 = function(x) {
Martin@627:     var low = this | x;
Martin@627:     low += (low < 0) ? (__m32+1) : 0;
Martin@627:     if (this.hi || x.hi) {
Martin@627:         var hi = this.hi | x.hi;
Martin@627:         return hi.next32(low);
Martin@627:     };
Martin@627:     return low;
Martin@627: };
Martin@627: 
Martin@628: Number.prototype.xor64 = function(x) {
Martin@628:     var low = this ^ x;
Martin@628:     low += (low < 0) ? (__m32+1) : 0;
Martin@628:     if (this.hi || x.hi) {
Martin@628:         var hi = this.hi ^ x.hi;
Martin@628:         return hi.next32(low);
Martin@628:     };
Martin@628:     return low;
Martin@628: };
Martin@628: 
Martin@594: Number.prototype.shl64 = function(x) {
Martin@616:     if (x >= 32) {
Martin@629:         var hi = this << (x - 32);
Martin@594:         return hi.next32(0);
Martin@594:     } else {
Martin@629:         var hi = this.high32() << x;
Martin@615:         var low_reminder = this >> (32 - x);
Martin@594:         hi |= low_reminder;
Martin@594:         var low = this << x;
Martin@616:         low += (low < 0) ? (__m32+1) : 0;
Martin@594:         return hi.next32(low);
Martin@594:     }
Martin@582: };
Martin@582: 
Martin@615: Number.prototype.shr64 = function(x) {
Martin@619:     if (x >= 32) {
Martin@629:         var low = this.high32() >> (x - 32);
Martin@619:         low += (low < 0) ? (__m32+1) : 0;
Martin@615:         return low;
Martin@615:     } else {
Martin@629:         var low = this >> x;
Martin@619:         var hi_reminder = this.high32() << (32 - x);
Martin@615:         low |= hi_reminder;
Martin@619:         low += (low < 0) ? (__m32+1) : 0;
Martin@615:         var hi = this.high32() >> x;
Martin@615:         return hi.next32(low);
Martin@615:     }
Martin@615: };
Martin@615: 
Martin@629: Number.prototype.ushr64 = function(x) {
Martin@629:     if (x >= 32) {
Martin@629:         var low = this.high32() >>> (x - 32);
Martin@629:         low += (low < 0) ? (__m32+1) : 0;
Martin@629:         return low;
Martin@629:     } else {
Martin@629:         var low = this >>> x;
Martin@629:         var hi_reminder = this.high32() << (32 - x);
Martin@629:         low |= hi_reminder;
Martin@629:         low += (low < 0) ? (__m32+1) : 0;
Martin@629:         var hi = this.high32() >>> x;
Martin@629:         return hi.next32(low);
Martin@629:     }
Martin@629: };
Martin@629: 
Martin@594: Number.prototype.compare64 = function(x) {
lubomir@680:     if (this.high32() === x.high32()) {
lubomir@680:         return (this < x) ? -1 : ((this > x) ? 1 : 0);
Martin@582:     }
lubomir@680:     return (this.high32() < x.high32()) ? -1 : 1;
Martin@582: };
Martin@630: 
Martin@630: Number.prototype.neg64 = function() {
Martin@630:     var hi = this.high32();
Martin@630:     var low = this;
Martin@630:     if ((hi === 0) && (low < 0)) { return -low; }
Martin@630:     hi = ~hi;
Martin@630:     low = ~low;
Martin@630:     low += (low < 0) ? (__m32+1) : 0;
Martin@669:     var ret = hi.next32(low);
Martin@669:     return ret.add64(1);
Martin@630: };
lubomir@676: 
lubomir@678: (function(numberPrototype) {
lubomir@676:     function __Int64(hi32, lo32) {
lubomir@676:         this.hi32 = hi32 | 0;
lubomir@676:         this.lo32 = lo32 | 0;
lubomir@676: 
lubomir@676:         this.get32 = function(bitIndex) {
lubomir@676:             var v0;
lubomir@676:             var v1;
lubomir@676:             bitIndex += 32;
lubomir@676:             var selector = bitIndex >>> 5;
lubomir@676:             switch (selector) {
lubomir@676:                 case 0:
lubomir@676:                     v0 = 0;
lubomir@676:                     v1 = this.lo32;
lubomir@676:                     break;
lubomir@676:                 case 1:
lubomir@676:                     v0 = this.lo32;
lubomir@676:                     v1 = this.hi32;
lubomir@676:                     break;
lubomir@676:                 case 2:
lubomir@676:                     v0 = this.hi32;
lubomir@676:                     v1 = 0;
lubomir@676:                     break
lubomir@676:                 default:
lubomir@676:                     return 0;
lubomir@676:             }
lubomir@676: 
lubomir@676:             var shift = bitIndex & 31;
lubomir@676:             if (shift === 0) {
lubomir@676:                 return v0;
lubomir@676:             }
lubomir@676: 
lubomir@676:             return (v1 << (32 - shift)) | (v0 >>> shift);
lubomir@676:         }
lubomir@676: 
lubomir@676:         this.get16 = function(bitIndex) {
lubomir@676:             return this.get32(bitIndex) & 0xffff;
lubomir@676:         }
lubomir@676: 
lubomir@676:         this.set16 = function(bitIndex, value) {
lubomir@676:             bitIndex += 32;
lubomir@676:             var shift = bitIndex & 15;
lubomir@676:             var svalue = (value & 0xffff) << shift; 
lubomir@676:             var smask = 0xffff << shift;
lubomir@676:             var selector = bitIndex >>> 4;
lubomir@676:             switch (selector) {
lubomir@676:                 case 0:
lubomir@676:                     break;
lubomir@676:                 case 1:
lubomir@676:                     this.lo32 = (this.lo32 & ~(smask >>> 16))
lubomir@676:                                     | (svalue >>> 16);
lubomir@676:                     break;
lubomir@676:                 case 2:
lubomir@676:                     this.lo32 = (this.lo32 & ~smask) | svalue;
lubomir@676:                     break;
lubomir@676:                 case 3:
lubomir@676:                     this.lo32 = (this.lo32 & ~(smask << 16))
lubomir@676:                                     | (svalue << 16);
lubomir@676:                     this.hi32 = (this.hi32 & ~(smask >>> 16))
lubomir@676:                                     | (svalue >>> 16);
lubomir@676:                     break;
lubomir@676:                 case 4:
lubomir@676:                     this.hi32 = (this.hi32 & ~smask) | svalue;
lubomir@676:                     break;
lubomir@676:                 case 5:
lubomir@676:                     this.hi32 = (this.hi32 & ~(smask << 16))
lubomir@676:                                     | (svalue << 16);
lubomir@676:                     break;
lubomir@676:             }
lubomir@676:         }
lubomir@676: 
lubomir@676:         this.getDigit = function(index, shift) {
lubomir@676:             return this.get16((index << 4) - shift);
lubomir@676:         }
lubomir@676: 
lubomir@676:         this.getTwoDigits = function(index, shift) {
lubomir@676:             return this.get32(((index - 1) << 4) - shift);
lubomir@676:         }
lubomir@676: 
lubomir@676:         this.setDigit = function(index, shift, value) {
lubomir@676:             this.set16((index << 4) - shift, value);
lubomir@676:         }
lubomir@676: 
lubomir@676:         this.countSignificantDigits = function() {
lubomir@676:             var sd;
lubomir@676:             var remaining;
lubomir@676: 
lubomir@676:             if (this.hi32 === 0) {
lubomir@676:                 if (this.lo32 === 0) {
lubomir@676:                     return 0;
lubomir@676:                 }
lubomir@676: 
lubomir@676:                 sd = 2;
lubomir@676:                 remaining = this.lo32;
lubomir@676:             } else {
lubomir@676:                 sd = 4;
lubomir@676:                 remaining = this.hi32;
lubomir@676:             }
lubomir@676: 
lubomir@676:             if (remaining < 0) {
lubomir@676:                 return sd;
lubomir@676:             }
lubomir@676: 
lubomir@676:             return (remaining < 65536) ? sd - 1 : sd;
lubomir@676:         }
lubomir@676:         
lubomir@676:         this.toNumber = function() {
lubomir@676:             var lo32 = this.lo32;
lubomir@676:             if (lo32 < 0) {
lubomir@676:                 lo32 += 0x100000000;
lubomir@676:             }
lubomir@676: 
lubomir@676:             return this.hi32.next32(lo32);
lubomir@676:         }
lubomir@676:     }
lubomir@676: 
lubomir@676:     function __countLeadingZeroes16(number) {
lubomir@676:         var nlz = 0;
lubomir@676: 
lubomir@676:         if (number < 256) {
lubomir@676:             nlz += 8;
lubomir@676:             number <<= 8;
lubomir@676:         }
lubomir@676: 
lubomir@676:         if (number < 4096) {
lubomir@676:             nlz += 4;
lubomir@676:             number <<= 4;
lubomir@676:         }
lubomir@676: 
lubomir@676:         if (number < 16384) {
lubomir@676:             nlz += 2;
lubomir@676:             number <<= 2;
lubomir@676:         }
lubomir@676: 
lubomir@676:         return (number < 32768) ? nlz + 1 : nlz;
lubomir@676:     }
lubomir@676:     
lubomir@676:     // q = u / v; r = u - q * v;
lubomir@676:     // v != 0
lubomir@676:     function __div64(q, r, u, v) {
lubomir@676:         var m = u.countSignificantDigits();
lubomir@676:         var n = v.countSignificantDigits();
lubomir@676: 
lubomir@676:         q.hi32 = q.lo32 = 0;
lubomir@676: 
lubomir@676:         if (n === 1) {
lubomir@676:             // v has single digit
lubomir@676:             var vd = v.getDigit(0, 0);
lubomir@676:             var carry = 0;
lubomir@676:             for (var i = m - 1; i >= 0; --i) {
lubomir@676:                 var ui = (carry << 16) | u.getDigit(i, 0);
lubomir@676:                 if (ui < 0) {
lubomir@676:                     ui += 0x100000000;
lubomir@676:                 }
lubomir@676:                 var qi = (ui / vd) | 0;
lubomir@676:                 q.setDigit(i, 0, qi);
lubomir@676:                 carry = ui - qi * vd;
lubomir@676:             }
lubomir@676: 
lubomir@676:             r.hi32 = 0;
lubomir@676:             r.lo32 = carry;
lubomir@676:             return;
lubomir@676:         }
lubomir@676: 
lubomir@676:         r.hi32 = u.hi32;  
lubomir@676:         r.lo32 = u.lo32;
lubomir@676: 
lubomir@676:         if (m < n) {
lubomir@676:             return;
lubomir@676:         }
lubomir@676: 
lubomir@676:         // Normalize
lubomir@676:         var nrm = __countLeadingZeroes16(v.getDigit(n - 1, 0));
lubomir@676: 
lubomir@676:         var vd1 = v.getDigit(n - 1, nrm);                
lubomir@676:         var vd0 = v.getDigit(n - 2, nrm);
lubomir@676:         for (var j = m - n; j >= 0; --j) {
lubomir@676:             // Calculate qj estimate
lubomir@676:             var ud21 = r.getTwoDigits(j + n, nrm);
lubomir@676:             var ud2 = ud21 >>> 16;
lubomir@676:             if (ud21 < 0) {
lubomir@676:                 ud21 += 0x100000000;
lubomir@676:             }
lubomir@676: 
lubomir@676:             var qest = (ud2 === vd1) ? 0xFFFF : ((ud21 / vd1) | 0);
lubomir@676:             var rest = ud21 - qest * vd1;
lubomir@676: 
lubomir@676:             // 0 <= (qest - qj) <= 2
lubomir@676: 
lubomir@676:             // Refine qj estimate
lubomir@676:             var ud0 = r.getDigit(j + n - 2, nrm);
lubomir@676:             while ((qest * vd0) > ((rest * 0x10000) + ud0)) {
lubomir@676:                 --qest;
lubomir@676:                 rest += vd1;
lubomir@676:             }
lubomir@676: 
lubomir@676:             // 0 <= (qest - qj) <= 1
lubomir@676:             
lubomir@676:             // Multiply and subtract
lubomir@676:             var carry = 0;
lubomir@676:             for (var i = 0; i < n; ++i) {
lubomir@676:                 var vi = qest * v.getDigit(i, nrm);
lubomir@676:                 var ui = r.getDigit(i + j, nrm) - carry - (vi & 0xffff);
lubomir@676:                 r.setDigit(i + j, nrm, ui);
lubomir@676:                 carry = (vi >>> 16) - (ui >> 16);
lubomir@676:             }
lubomir@676:             var uj = ud2 - carry;
lubomir@676: 
lubomir@676:             if (uj < 0) {
lubomir@676:                 // qest - qj = 1
lubomir@676: 
lubomir@676:                 // Add back
lubomir@676:                 --qest;
lubomir@676:                 var carry = 0;
lubomir@676:                 for (var i = 0; i < n; ++i) {
lubomir@676:                     var ui = r.getDigit(i + j, nrm) + v.getDigit(i, nrm)
lubomir@676:                                  + carry;
lubomir@676:                     r.setDigit(i + j, nrm, ui);
lubomir@676:                     carry = ui >> 16;
lubomir@676:                 }
lubomir@676:                 uj += carry;
lubomir@676:             }
lubomir@676: 
lubomir@676:             q.setDigit(j, 0, qest);
lubomir@676:             r.setDigit(j + n, nrm, uj);
lubomir@676:         }
lubomir@676:     }
lubomir@676:     
lubomir@676:     numberPrototype.div64 = function(x) {
lubomir@676:         var negateResult = false;
lubomir@676:         var u, v;
lubomir@676:         
lubomir@676:         if ((this.high32() & 0x80000000) != 0) {
lubomir@676:             u = this.neg64();
lubomir@676:             negateResult = !negateResult;
lubomir@676:         } else {
lubomir@676:             u = this;        
lubomir@676:         }
lubomir@676: 
lubomir@676:         if ((x.high32() & 0x80000000) != 0) {
lubomir@676:             v = x.neg64();
lubomir@676:             negateResult = !negateResult;
lubomir@676:         } else {
lubomir@676:             v = x;
lubomir@676:         }
lubomir@676: 
lubomir@676:         if ((v === 0) && (v.high32() === 0)) {
lubomir@676:             // TODO: throw
lubomir@676:         }
lubomir@676: 
lubomir@676:         if (u.high32() === 0) {
lubomir@676:             if (v.high32() === 0) {
lubomir@676:                 var result = (u / v) | 0;
lubomir@676:                 return negateResult ? result.neg64() : result; 
lubomir@676:             }
lubomir@676: 
lubomir@676:             return 0;
lubomir@676:         }
lubomir@676: 
lubomir@676:         var u64 = new __Int64(u.high32(), u);
lubomir@676:         var v64 = new __Int64(v.high32(), v);
lubomir@676:         var q64 = new __Int64(0, 0);
lubomir@676:         var r64 = new __Int64(0, 0);
lubomir@676: 
lubomir@676:         __div64(q64, r64, u64, v64);
lubomir@676: 
lubomir@676:         var result = q64.toNumber();
lubomir@676:         return negateResult ? result.neg64() : result; 
lubomir@676:     }
lubomir@676: 
lubomir@676:     numberPrototype.mod64 = function(x) {
lubomir@676:         var negateResult = false;
lubomir@676:         var u, v;
lubomir@676:         
lubomir@676:         if ((this.high32() & 0x80000000) != 0) {
lubomir@676:             u = this.neg64();
lubomir@676:             negateResult = !negateResult;
lubomir@676:         } else {
lubomir@676:             u = this;        
lubomir@676:         }
lubomir@676: 
lubomir@676:         if ((x.high32() & 0x80000000) != 0) {
lubomir@676:             v = x.neg64();
lubomir@676:         } else {
lubomir@676:             v = x;
lubomir@676:         }
lubomir@676: 
lubomir@676:         if ((v === 0) && (v.high32() === 0)) {
lubomir@676:             // TODO: throw
lubomir@676:         }
lubomir@676: 
lubomir@676:         if (u.high32() === 0) {
lubomir@676:             var result = (v.high32() === 0) ? (u % v) : u;
lubomir@676:             return negateResult ? result.neg64() : result; 
lubomir@676:         }
lubomir@676: 
lubomir@676:         var u64 = new __Int64(u.high32(), u);
lubomir@676:         var v64 = new __Int64(v.high32(), v);
lubomir@676:         var q64 = new __Int64(0, 0);
lubomir@676:         var r64 = new __Int64(0, 0);
lubomir@676: 
lubomir@676:         __div64(q64, r64, u64, v64);
lubomir@676: 
lubomir@676:         var result = r64.toNumber();
lubomir@676:         return negateResult ? result.neg64() : result; 
lubomir@676:     }
lubomir@678: })(Number.prototype);