rt/emul/mini/src/main/resources/org/apidesign/vm4brwsr/emul/lang/java_lang_Number.js
author Jaroslav Tulach <jaroslav.tulach@apidesign.org>
Wed, 27 Jan 2016 21:37:10 +0100
changeset 1872 df5db062f180
parent 1871 bcbc4c03d35d
child 1873 9af63c578721
permissions -rw-r--r--
Speeding up sieve with long numbers by directly resolving high32
     1 // empty line needed here
     2 
     3 (function(numberPrototype) {
     4     function add32(x, y) {
     5         return (x + y) | 0;
     6     };
     7     function mul32(x, y) {
     8         return (((x * (y >> 16)) << 16) + x * (y & 0xFFFF)) | 0;
     9     };
    10     var __m32 = 0xFFFFFFFF;
    11 
    12     numberPrototype.next32 = function(low) {
    13         if (this === 0) {
    14             return low;
    15         }
    16         var l = new Number(low);
    17         l.hi = this | 0;
    18         return l;
    19     };
    20 
    21     numberPrototype.high32 = function() {
    22         return high32(this);
    23     };
    24     function high32(x) {
    25         return x.hi ? x.hi : (Math.floor(x / (__m32 + 1))) | 0;
    26     };
    27     numberPrototype.toFP = function() {
    28         return this.hi ? this.hi * (__m32 + 1) + this : this;
    29     };
    30     numberPrototype.toLong = function() {
    31         var hi = (this / (__m32 + 1)) | 0;
    32         var low = (this % (__m32 + 1)) | 0;
    33         if (low < 0) {
    34             low += __m32 + 1;
    35         }
    36 
    37         if (this < 0) {
    38             hi -= 1;
    39         }
    40 
    41         return hi.next32(low);
    42     };
    43 
    44     numberPrototype.toExactString = function() {
    45         if (this.hi) {
    46             // check for Long.MIN_VALUE
    47             if ((this.hi == (0x80000000 | 0)) && (this == 0)) {
    48                 return '-9223372036854775808';
    49             }
    50             var res = 0;
    51             var a = [6, 9, 2, 7, 6, 9, 4, 9, 2, 4];
    52             var s = '';
    53             var digit;
    54             var neg = this.hi < 0;
    55             if (neg) {
    56                 var x = neg64(this);
    57                 var hi = x.hi;
    58                 var low = x;
    59             } else {
    60                 var hi = this.hi;
    61                 var low = this;
    62             }
    63             for (var i = 0; i < a.length; i++) {
    64                 res += hi * a[i];
    65                 var low_digit = low % 10;
    66                 digit = (res % 10) + low_digit;
    67 
    68                 low = Math.floor(low / 10);
    69                 res = Math.floor(res / 10);
    70 
    71                 if (digit >= 10) {
    72                     digit -= 10;
    73                     res++;
    74                 }
    75                 s = String(digit).concat(s);
    76             }
    77             s = String(res).concat(s).replace(/^0+/, '');
    78             return (neg ? '-' : '').concat(s);
    79         }
    80         return String(this);
    81     };
    82 
    83     function add64(x, y) {
    84         var low = x + y;
    85         carry = 0;
    86         if (low > __m32) {
    87             carry = 1;
    88             low -= (__m32 + 1);
    89         }
    90         var hi = (high32(x) + high32(y) + carry) | 0;
    91         return hi.next32(low);
    92     };
    93 
    94     function sub64(x, y) {
    95         var low = x - y;
    96         carry = 0;
    97         if (low < 0) {
    98             carry = 1;
    99             low += (__m32 + 1);
   100         }
   101         var hi = (high32(x) - high32(y) - carry) | 0;
   102         return hi.next32(low);
   103     };
   104 
   105     function mul64(x, y) {
   106         var low = mul32(x, y);
   107         low += (low < 0) ? (__m32 + 1) : 0;
   108         // first count upper 32 bits of (x.low * x.low)
   109         var hi_hi = 0;
   110         var hi_low = 0;
   111         var m = 1;
   112         for (var i = 0; i < 32; i++) {
   113             if (y & m) {
   114                 hi_hi += x >>> 16;
   115                 hi_low += x & 0xFFFF
   116             }
   117             hi_low >>= 1;
   118             hi_low += (hi_hi & 1) ? 0x8000 : 0;
   119             hi_hi >>= 1;
   120             m <<= 1;
   121         }
   122         var hi = (hi_hi << 16) + hi_low;
   123 
   124         var m1 = mul32(high32(x), y);
   125         var m2 = mul32(x, high32(y));
   126         hi = add32(add32(hi, m1), m2);
   127 
   128         return hi.next32(low);
   129     };
   130 
   131     function and64(x, y) {
   132         var low = x & y;
   133         low += (low < 0) ? (__m32 + 1) : 0;
   134         if (x.hi && y.hi) {
   135             var hi = x.hi & y.hi;
   136             return hi.next32(low);
   137         }
   138         ;
   139         return low;
   140     };
   141 
   142     function or64(x, y) {
   143         var low = x | y;
   144         low += (low < 0) ? (__m32 + 1) : 0;
   145         if (x.hi || y.hi) {
   146             var hi = x.hi | y.hi;
   147             return hi.next32(low);
   148         }
   149         return low;
   150     };
   151 
   152     function xor64(x, y) {
   153         var low = x ^ y;
   154         low += (low < 0) ? (__m32 + 1) : 0;
   155         if (x.hi || y.hi) {
   156             var hi = x.hi ^ y.hi;
   157             return hi.next32(low);
   158         }
   159         ;
   160         return low;
   161     };
   162 
   163     function shl64(thiz, x) {
   164         x &= 0x3f;
   165         if (x === 0) return thiz;
   166         if (x >= 32) {
   167             var hi = thiz << (x - 32);
   168             return hi.next32(0);
   169         } else {
   170             var hi = high32(thiz) << x;
   171             var low_reminder = thiz >> (32 - x);
   172             hi |= low_reminder;
   173             var low = thiz << x;
   174             low += (low < 0) ? (__m32 + 1) : 0;
   175             return hi.next32(low);
   176         }
   177     };
   178 
   179     function shr64(thiz, x) {
   180         x &= 0x3f;
   181         if (x === 0) return thiz;
   182         if (x >= 32) {
   183             var low = high32(thiz) >> (x - 32);
   184             low += (low < 0) ? (__m32 + 1) : 0;
   185             return low;
   186         } else {
   187             var low = thiz >>> x;
   188             var hi_reminder = high32(thiz) << (32 - x);
   189             low |= hi_reminder;
   190             low += (low < 0) ? (__m32 + 1) : 0;
   191             var hi = high32(thiz) >> x;
   192             return hi.next32(low);
   193         }
   194     };
   195 
   196     function ushr64(thiz, x) {
   197         x &= 0x3f;
   198         if (x === 0) return thiz;
   199         if (x >= 32) {
   200             var low = high32(thiz) >>> (x - 32);
   201             low += (low < 0) ? (__m32 + 1) : 0;
   202             return low;
   203         } else {
   204             var low = thiz >>> x;
   205             var hi_reminder = high32(thiz) << (32 - x);
   206             low |= hi_reminder;
   207             low += (low < 0) ? (__m32 + 1) : 0;
   208             var hi = high32(thiz) >>> x;
   209             return hi.next32(low);
   210         }
   211     };
   212 
   213     function compare64(x, y) {
   214         if (high32(x) === high32(y)) {
   215             return (x < y) ? -1 : ((x > y) ? 1 : 0);
   216         }
   217         return (high32(x) < high32(y)) ? -1 : 1;
   218     };
   219 
   220     function neg64(x) {
   221         var hi = high32(x);
   222         var low = x;
   223         if ((hi === 0) && (low < 0)) {
   224             return -low;
   225         }
   226         hi = ~hi;
   227         low = ~low;
   228         low += (low < 0) ? (__m32 + 1) : 0;
   229         var ret = hi.next32(low);
   230         return add64(ret, 1);
   231     };
   232     
   233     function __handleDivByZero() {
   234         var exception = new vm.java_lang_ArithmeticException;
   235         vm.java_lang_ArithmeticException(false).constructor
   236           .cons__VLjava_lang_String_2.call(exception, "/ by zero");
   237 
   238         throw exception;
   239     }
   240 
   241     function __Int64(hi32, lo32) {
   242         this.hi32 = hi32 | 0;
   243         this.lo32 = lo32 | 0;
   244 
   245         this.get32 = function(bitIndex) {
   246             var v0;
   247             var v1;
   248             bitIndex += 32;
   249             var selector = bitIndex >>> 5;
   250             switch (selector) {
   251                 case 0:
   252                     v0 = 0;
   253                     v1 = this.lo32;
   254                     break;
   255                 case 1:
   256                     v0 = this.lo32;
   257                     v1 = this.hi32;
   258                     break;
   259                 case 2:
   260                     v0 = this.hi32;
   261                     v1 = 0;
   262                     break
   263                 default:
   264                     return 0;
   265             }
   266 
   267             var shift = bitIndex & 31;
   268             if (shift === 0) {
   269                 return v0;
   270             }
   271 
   272             return (v1 << (32 - shift)) | (v0 >>> shift);
   273         }
   274 
   275         this.get16 = function(bitIndex) {
   276             return this.get32(bitIndex) & 0xffff;
   277         }
   278 
   279         this.set16 = function(bitIndex, value) {
   280             bitIndex += 32;
   281             var shift = bitIndex & 15;
   282             var svalue = (value & 0xffff) << shift; 
   283             var smask = 0xffff << shift;
   284             var selector = bitIndex >>> 4;
   285             switch (selector) {
   286                 case 0:
   287                     break;
   288                 case 1:
   289                     this.lo32 = (this.lo32 & ~(smask >>> 16))
   290                                     | (svalue >>> 16);
   291                     break;
   292                 case 2:
   293                     this.lo32 = (this.lo32 & ~smask) | svalue;
   294                     break;
   295                 case 3:
   296                     this.lo32 = (this.lo32 & ~(smask << 16))
   297                                     | (svalue << 16);
   298                     this.hi32 = (this.hi32 & ~(smask >>> 16))
   299                                     | (svalue >>> 16);
   300                     break;
   301                 case 4:
   302                     this.hi32 = (this.hi32 & ~smask) | svalue;
   303                     break;
   304                 case 5:
   305                     this.hi32 = (this.hi32 & ~(smask << 16))
   306                                     | (svalue << 16);
   307                     break;
   308             }
   309         }
   310 
   311         this.getDigit = function(index, shift) {
   312             return this.get16((index << 4) - shift);
   313         }
   314 
   315         this.getTwoDigits = function(index, shift) {
   316             return this.get32(((index - 1) << 4) - shift);
   317         }
   318 
   319         this.setDigit = function(index, shift, value) {
   320             this.set16((index << 4) - shift, value);
   321         }
   322 
   323         this.countSignificantDigits = function() {
   324             var sd;
   325             var remaining;
   326 
   327             if (this.hi32 === 0) {
   328                 if (this.lo32 === 0) {
   329                     return 0;
   330                 }
   331 
   332                 sd = 2;
   333                 remaining = this.lo32;
   334             } else {
   335                 sd = 4;
   336                 remaining = this.hi32;
   337             }
   338 
   339             if (remaining < 0) {
   340                 return sd;
   341             }
   342 
   343             return (remaining < 65536) ? sd - 1 : sd;
   344         }
   345         
   346         this.toNumber = function() {
   347             var lo32 = this.lo32;
   348             if (lo32 < 0) {
   349                 lo32 += 0x100000000;
   350             }
   351 
   352             return this.hi32.next32(lo32);
   353         }
   354     }
   355 
   356     function __countLeadingZeroes16(number) {
   357         var nlz = 0;
   358 
   359         if (number < 256) {
   360             nlz += 8;
   361             number <<= 8;
   362         }
   363 
   364         if (number < 4096) {
   365             nlz += 4;
   366             number <<= 4;
   367         }
   368 
   369         if (number < 16384) {
   370             nlz += 2;
   371             number <<= 2;
   372         }
   373 
   374         return (number < 32768) ? nlz + 1 : nlz;
   375     }
   376     
   377     // q = u / v; r = u - q * v;
   378     // v != 0
   379     function __div64(q, r, u, v) {
   380         var m = u.countSignificantDigits();
   381         var n = v.countSignificantDigits();
   382 
   383         q.hi32 = q.lo32 = 0;
   384 
   385         if (n === 1) {
   386             // v has single digit
   387             var vd = v.getDigit(0, 0);
   388             var carry = 0;
   389             for (var i = m - 1; i >= 0; --i) {
   390                 var ui = (carry << 16) | u.getDigit(i, 0);
   391                 if (ui < 0) {
   392                     ui += 0x100000000;
   393                 }
   394                 var qi = (ui / vd) | 0;
   395                 q.setDigit(i, 0, qi);
   396                 carry = ui - qi * vd;
   397             }
   398 
   399             r.hi32 = 0;
   400             r.lo32 = carry;
   401             return;
   402         }
   403 
   404         r.hi32 = u.hi32;  
   405         r.lo32 = u.lo32;
   406 
   407         if (m < n) {
   408             return;
   409         }
   410 
   411         // Normalize
   412         var nrm = __countLeadingZeroes16(v.getDigit(n - 1, 0));
   413 
   414         var vd1 = v.getDigit(n - 1, nrm);                
   415         var vd0 = v.getDigit(n - 2, nrm);
   416         for (var j = m - n; j >= 0; --j) {
   417             // Calculate qj estimate
   418             var ud21 = r.getTwoDigits(j + n, nrm);
   419             var ud2 = ud21 >>> 16;
   420             if (ud21 < 0) {
   421                 ud21 += 0x100000000;
   422             }
   423 
   424             var qest = (ud2 === vd1) ? 0xFFFF : ((ud21 / vd1) | 0);
   425             var rest = ud21 - qest * vd1;
   426 
   427             // 0 <= (qest - qj) <= 2
   428 
   429             // Refine qj estimate
   430             var ud0 = r.getDigit(j + n - 2, nrm);
   431             while ((qest * vd0) > ((rest * 0x10000) + ud0)) {
   432                 --qest;
   433                 rest += vd1;
   434             }
   435 
   436             // 0 <= (qest - qj) <= 1
   437             
   438             // Multiply and subtract
   439             var carry = 0;
   440             for (var i = 0; i < n; ++i) {
   441                 var vi = qest * v.getDigit(i, nrm);
   442                 var ui = r.getDigit(i + j, nrm) - carry - (vi & 0xffff);
   443                 r.setDigit(i + j, nrm, ui);
   444                 carry = (vi >>> 16) - (ui >> 16);
   445             }
   446             var uj = ud2 - carry;
   447 
   448             if (uj < 0) {
   449                 // qest - qj = 1
   450 
   451                 // Add back
   452                 --qest;
   453                 var carry = 0;
   454                 for (var i = 0; i < n; ++i) {
   455                     var ui = r.getDigit(i + j, nrm) + v.getDigit(i, nrm)
   456                                  + carry;
   457                     r.setDigit(i + j, nrm, ui);
   458                     carry = ui >> 16;
   459                 }
   460                 uj += carry;
   461             }
   462 
   463             q.setDigit(j, 0, qest);
   464             r.setDigit(j + n, nrm, uj);
   465         }
   466     }
   467 
   468     function div64(x, y) {
   469         var negateResult = false;
   470         var u, v;
   471 
   472         if ((high32(x) & 0x80000000) !== 0) {
   473             u = neg64(x);
   474             negateResult = !negateResult;
   475         } else {
   476             u = x;
   477         }
   478 
   479         if ((high32(y) & 0x80000000) !== 0) {
   480             v = neg64(y);
   481             negateResult = !negateResult;
   482         } else {
   483             v = y;
   484         }
   485 
   486         if ((v === 0) && (high32(v) === 0)) {
   487             __handleDivByZero();
   488         }
   489 
   490         if (high32(u) === 0) {
   491             if (high32(v) === 0) {
   492                 var result = (u / v) | 0;
   493                 return negateResult ? neg64(result) : result;
   494             }
   495 
   496             return 0;
   497         }
   498 
   499         var u64 = new __Int64(high32(u), u);
   500         var v64 = new __Int64(high32(v), v);
   501         var q64 = new __Int64(0, 0);
   502         var r64 = new __Int64(0, 0);
   503 
   504         __div64(q64, r64, u64, v64);
   505 
   506         var result = q64.toNumber();
   507         return negateResult ? neg64(result) : result;
   508     }
   509 
   510     function mod64(x, y) {
   511         var negateResult = false;
   512         var u, v;
   513         
   514         if ((high32(x) & 0x80000000) !== 0) {
   515             u = neg64(x);
   516             negateResult = !negateResult;
   517         } else {
   518             u = x;
   519         }
   520 
   521         if ((high32(y) & 0x80000000) !== 0) {
   522             v = neg64(y);
   523         } else {
   524             v = y;
   525         }
   526 
   527         if ((v === 0) && (high32(v) === 0)) {
   528             __handleDivByZero();
   529         }
   530 
   531         if (high32(u) === 0) {
   532             var result = (high32(v) === 0) ? (u % v) : u;
   533             return negateResult ? neg64(result) : result;
   534         }
   535 
   536         var u64 = new __Int64(high32(u), u);
   537         var v64 = new __Int64(high32(v), v);
   538         var q64 = new __Int64(0, 0);
   539         var r64 = new __Int64(0, 0);
   540 
   541         __div64(q64, r64, u64, v64);
   542 
   543         var result = r64.toNumber();
   544         return negateResult ? neg64(result) : result;
   545     }
   546 
   547     var b = numberPrototype['__bit64'] = {};
   548     b.add64 = add64;
   549     b.sub64 = sub64;
   550     b.mul64 = mul64;
   551     b.div64 = div64;
   552     b.mod64 = mod64;
   553     b.and64 = and64;
   554     b.or64 = or64;
   555     b.xor64 = xor64;
   556     b.neg64 = neg64;
   557     b.shl64 = shl64;
   558     b.shr64 = shr64;
   559     b.ushr64 = ushr64;
   560     b.compare64 = compare64;
   561 })(Number.prototype);
   562 
   563 vm.java_lang_Number(false);