simple-squiggle

A restricted subset of Squiggle
Log | Files | Refs | README

bitwise.js (9456B)

      1 "use strict";
      2 
      3 Object.defineProperty(exports, "__esModule", {
      4   value: true
      5 });
      6 exports.bitAndBigNumber = bitAndBigNumber;
      7 exports.bitNotBigNumber = bitNotBigNumber;
      8 exports.bitOrBigNumber = bitOrBigNumber;
      9 exports.bitXor = bitXor;
     10 exports.bitwise = bitwise;
     11 exports.leftShiftBigNumber = leftShiftBigNumber;
     12 exports.rightArithShiftBigNumber = rightArithShiftBigNumber;
     13 
     14 /**
     15  * Bitwise and for Bignumbers
     16  *
     17  * Special Cases:
     18  *   N &  n =  N
     19  *   n &  0 =  0
     20  *   n & -1 =  n
     21  *   n &  n =  n
     22  *   I &  I =  I
     23  *  -I & -I = -I
     24  *   I & -I =  0
     25  *   I &  n =  n
     26  *   I & -n =  I
     27  *  -I &  n =  0
     28  *  -I & -n = -I
     29  *
     30  * @param {BigNumber} x
     31  * @param {BigNumber} y
     32  * @return {BigNumber} Result of `x` & `y`, is fully precise
     33  * @private
     34  */
     35 function bitAndBigNumber(x, y) {
     36   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
     37     throw new Error('Integers expected in function bitAnd');
     38   }
     39 
     40   var BigNumber = x.constructor;
     41 
     42   if (x.isNaN() || y.isNaN()) {
     43     return new BigNumber(NaN);
     44   }
     45 
     46   if (x.isZero() || y.eq(-1) || x.eq(y)) {
     47     return x;
     48   }
     49 
     50   if (y.isZero() || x.eq(-1)) {
     51     return y;
     52   }
     53 
     54   if (!x.isFinite() || !y.isFinite()) {
     55     if (!x.isFinite() && !y.isFinite()) {
     56       if (x.isNegative() === y.isNegative()) {
     57         return x;
     58       }
     59 
     60       return new BigNumber(0);
     61     }
     62 
     63     if (!x.isFinite()) {
     64       if (y.isNegative()) {
     65         return x;
     66       }
     67 
     68       if (x.isNegative()) {
     69         return new BigNumber(0);
     70       }
     71 
     72       return y;
     73     }
     74 
     75     if (!y.isFinite()) {
     76       if (x.isNegative()) {
     77         return y;
     78       }
     79 
     80       if (y.isNegative()) {
     81         return new BigNumber(0);
     82       }
     83 
     84       return x;
     85     }
     86   }
     87 
     88   return bitwise(x, y, function (a, b) {
     89     return a & b;
     90   });
     91 }
     92 /**
     93  * Bitwise not
     94  * @param {BigNumber} x
     95  * @return {BigNumber} Result of ~`x`, fully precise
     96  *
     97  */
     98 
     99 
    100 function bitNotBigNumber(x) {
    101   if (x.isFinite() && !x.isInteger()) {
    102     throw new Error('Integer expected in function bitNot');
    103   }
    104 
    105   var BigNumber = x.constructor;
    106   var prevPrec = BigNumber.precision;
    107   BigNumber.config({
    108     precision: 1E9
    109   });
    110   var result = x.plus(new BigNumber(1));
    111   result.s = -result.s || null;
    112   BigNumber.config({
    113     precision: prevPrec
    114   });
    115   return result;
    116 }
    117 /**
    118  * Bitwise OR for BigNumbers
    119  *
    120  * Special Cases:
    121  *   N |  n =  N
    122  *   n |  0 =  n
    123  *   n | -1 = -1
    124  *   n |  n =  n
    125  *   I |  I =  I
    126  *  -I | -I = -I
    127  *   I | -n = -1
    128  *   I | -I = -1
    129  *   I |  n =  I
    130  *  -I |  n = -I
    131  *  -I | -n = -n
    132  *
    133  * @param {BigNumber} x
    134  * @param {BigNumber} y
    135  * @return {BigNumber} Result of `x` | `y`, fully precise
    136  */
    137 
    138 
    139 function bitOrBigNumber(x, y) {
    140   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
    141     throw new Error('Integers expected in function bitOr');
    142   }
    143 
    144   var BigNumber = x.constructor;
    145 
    146   if (x.isNaN() || y.isNaN()) {
    147     return new BigNumber(NaN);
    148   }
    149 
    150   var negOne = new BigNumber(-1);
    151 
    152   if (x.isZero() || y.eq(negOne) || x.eq(y)) {
    153     return y;
    154   }
    155 
    156   if (y.isZero() || x.eq(negOne)) {
    157     return x;
    158   }
    159 
    160   if (!x.isFinite() || !y.isFinite()) {
    161     if (!x.isFinite() && !x.isNegative() && y.isNegative() || x.isNegative() && !y.isNegative() && !y.isFinite()) {
    162       return negOne;
    163     }
    164 
    165     if (x.isNegative() && y.isNegative()) {
    166       return x.isFinite() ? x : y;
    167     }
    168 
    169     return x.isFinite() ? y : x;
    170   }
    171 
    172   return bitwise(x, y, function (a, b) {
    173     return a | b;
    174   });
    175 }
    176 /**
    177  * Applies bitwise function to numbers
    178  * @param {BigNumber} x
    179  * @param {BigNumber} y
    180  * @param {function (a, b)} func
    181  * @return {BigNumber}
    182  */
    183 
    184 
    185 function bitwise(x, y, func) {
    186   var BigNumber = x.constructor;
    187   var xBits, yBits;
    188   var xSign = +(x.s < 0);
    189   var ySign = +(y.s < 0);
    190 
    191   if (xSign) {
    192     xBits = decCoefficientToBinaryString(bitNotBigNumber(x));
    193 
    194     for (var i = 0; i < xBits.length; ++i) {
    195       xBits[i] ^= 1;
    196     }
    197   } else {
    198     xBits = decCoefficientToBinaryString(x);
    199   }
    200 
    201   if (ySign) {
    202     yBits = decCoefficientToBinaryString(bitNotBigNumber(y));
    203 
    204     for (var _i = 0; _i < yBits.length; ++_i) {
    205       yBits[_i] ^= 1;
    206     }
    207   } else {
    208     yBits = decCoefficientToBinaryString(y);
    209   }
    210 
    211   var minBits, maxBits, minSign;
    212 
    213   if (xBits.length <= yBits.length) {
    214     minBits = xBits;
    215     maxBits = yBits;
    216     minSign = xSign;
    217   } else {
    218     minBits = yBits;
    219     maxBits = xBits;
    220     minSign = ySign;
    221   }
    222 
    223   var shortLen = minBits.length;
    224   var longLen = maxBits.length;
    225   var expFuncVal = func(xSign, ySign) ^ 1;
    226   var outVal = new BigNumber(expFuncVal ^ 1);
    227   var twoPower = new BigNumber(1);
    228   var two = new BigNumber(2);
    229   var prevPrec = BigNumber.precision;
    230   BigNumber.config({
    231     precision: 1E9
    232   });
    233 
    234   while (shortLen > 0) {
    235     if (func(minBits[--shortLen], maxBits[--longLen]) === expFuncVal) {
    236       outVal = outVal.plus(twoPower);
    237     }
    238 
    239     twoPower = twoPower.times(two);
    240   }
    241 
    242   while (longLen > 0) {
    243     if (func(minSign, maxBits[--longLen]) === expFuncVal) {
    244       outVal = outVal.plus(twoPower);
    245     }
    246 
    247     twoPower = twoPower.times(two);
    248   }
    249 
    250   BigNumber.config({
    251     precision: prevPrec
    252   });
    253 
    254   if (expFuncVal === 0) {
    255     outVal.s = -outVal.s;
    256   }
    257 
    258   return outVal;
    259 }
    260 /* Extracted from decimal.js, and edited to specialize. */
    261 
    262 
    263 function decCoefficientToBinaryString(x) {
    264   // Convert to string
    265   var a = x.d; // array with digits
    266 
    267   var r = a[0] + '';
    268 
    269   for (var i = 1; i < a.length; ++i) {
    270     var s = a[i] + '';
    271 
    272     for (var z = 7 - s.length; z--;) {
    273       s = '0' + s;
    274     }
    275 
    276     r += s;
    277   }
    278 
    279   var j = r.length;
    280 
    281   while (r.charAt(j) === '0') {
    282     j--;
    283   }
    284 
    285   var xe = x.e;
    286   var str = r.slice(0, j + 1 || 1);
    287   var strL = str.length;
    288 
    289   if (xe > 0) {
    290     if (++xe > strL) {
    291       // Append zeros.
    292       xe -= strL;
    293 
    294       while (xe--) {
    295         str += '0';
    296       }
    297     } else if (xe < strL) {
    298       str = str.slice(0, xe) + '.' + str.slice(xe);
    299     }
    300   } // Convert from base 10 (decimal) to base 2
    301 
    302 
    303   var arr = [0];
    304 
    305   for (var _i2 = 0; _i2 < str.length;) {
    306     var arrL = arr.length;
    307 
    308     while (arrL--) {
    309       arr[arrL] *= 10;
    310     }
    311 
    312     arr[0] += parseInt(str.charAt(_i2++)); // convert to int
    313 
    314     for (var _j = 0; _j < arr.length; ++_j) {
    315       if (arr[_j] > 1) {
    316         if (arr[_j + 1] === null || arr[_j + 1] === undefined) {
    317           arr[_j + 1] = 0;
    318         }
    319 
    320         arr[_j + 1] += arr[_j] >> 1;
    321         arr[_j] &= 1;
    322       }
    323     }
    324   }
    325 
    326   return arr.reverse();
    327 }
    328 /**
    329  * Bitwise XOR for BigNumbers
    330  *
    331  * Special Cases:
    332  *   N ^  n =  N
    333  *   n ^  0 =  n
    334  *   n ^  n =  0
    335  *   n ^ -1 = ~n
    336  *   I ^  n =  I
    337  *   I ^ -n = -I
    338  *   I ^ -I = -1
    339  *  -I ^  n = -I
    340  *  -I ^ -n =  I
    341  *
    342  * @param {BigNumber} x
    343  * @param {BigNumber} y
    344  * @return {BigNumber} Result of `x` ^ `y`, fully precise
    345  *
    346  */
    347 
    348 
    349 function bitXor(x, y) {
    350   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
    351     throw new Error('Integers expected in function bitXor');
    352   }
    353 
    354   var BigNumber = x.constructor;
    355 
    356   if (x.isNaN() || y.isNaN()) {
    357     return new BigNumber(NaN);
    358   }
    359 
    360   if (x.isZero()) {
    361     return y;
    362   }
    363 
    364   if (y.isZero()) {
    365     return x;
    366   }
    367 
    368   if (x.eq(y)) {
    369     return new BigNumber(0);
    370   }
    371 
    372   var negOne = new BigNumber(-1);
    373 
    374   if (x.eq(negOne)) {
    375     return bitNotBigNumber(y);
    376   }
    377 
    378   if (y.eq(negOne)) {
    379     return bitNotBigNumber(x);
    380   }
    381 
    382   if (!x.isFinite() || !y.isFinite()) {
    383     if (!x.isFinite() && !y.isFinite()) {
    384       return negOne;
    385     }
    386 
    387     return new BigNumber(x.isNegative() === y.isNegative() ? Infinity : -Infinity);
    388   }
    389 
    390   return bitwise(x, y, function (a, b) {
    391     return a ^ b;
    392   });
    393 }
    394 /**
    395  * Bitwise left shift
    396  *
    397  * Special Cases:
    398  *  n << -n = N
    399  *  n <<  N = N
    400  *  N <<  n = N
    401  *  n <<  0 = n
    402  *  0 <<  n = 0
    403  *  I <<  I = N
    404  *  I <<  n = I
    405  *  n <<  I = I
    406  *
    407  * @param {BigNumber} x
    408  * @param {BigNumber} y
    409  * @return {BigNumber} Result of `x` << `y`
    410  *
    411  */
    412 
    413 
    414 function leftShiftBigNumber(x, y) {
    415   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
    416     throw new Error('Integers expected in function leftShift');
    417   }
    418 
    419   var BigNumber = x.constructor;
    420 
    421   if (x.isNaN() || y.isNaN() || y.isNegative() && !y.isZero()) {
    422     return new BigNumber(NaN);
    423   }
    424 
    425   if (x.isZero() || y.isZero()) {
    426     return x;
    427   }
    428 
    429   if (!x.isFinite() && !y.isFinite()) {
    430     return new BigNumber(NaN);
    431   } // Math.pow(2, y) is fully precise for y < 55, and fast
    432 
    433 
    434   if (y.lt(55)) {
    435     return x.times(Math.pow(2, y.toNumber()) + '');
    436   }
    437 
    438   return x.times(new BigNumber(2).pow(y));
    439 }
    440 /*
    441  * Special Cases:
    442  *   n >> -n =  N
    443  *   n >>  N =  N
    444  *   N >>  n =  N
    445  *   I >>  I =  N
    446  *   n >>  0 =  n
    447  *   I >>  n =  I
    448  *  -I >>  n = -I
    449  *  -I >>  I = -I
    450  *   n >>  I =  I
    451  *  -n >>  I = -1
    452  *   0 >>  n =  0
    453  *
    454  * @param {BigNumber} value
    455  * @param {BigNumber} value
    456  * @return {BigNumber} Result of `x` >> `y`
    457  *
    458  */
    459 
    460 
    461 function rightArithShiftBigNumber(x, y) {
    462   if (x.isFinite() && !x.isInteger() || y.isFinite() && !y.isInteger()) {
    463     throw new Error('Integers expected in function rightArithShift');
    464   }
    465 
    466   var BigNumber = x.constructor;
    467 
    468   if (x.isNaN() || y.isNaN() || y.isNegative() && !y.isZero()) {
    469     return new BigNumber(NaN);
    470   }
    471 
    472   if (x.isZero() || y.isZero()) {
    473     return x;
    474   }
    475 
    476   if (!y.isFinite()) {
    477     if (x.isNegative()) {
    478       return new BigNumber(-1);
    479     }
    480 
    481     if (!x.isFinite()) {
    482       return new BigNumber(NaN);
    483     }
    484 
    485     return new BigNumber(0);
    486   } // Math.pow(2, y) is fully precise for y < 55, and fast
    487 
    488 
    489   if (y.lt(55)) {
    490     return x.div(Math.pow(2, y.toNumber()) + '').floor();
    491   }
    492 
    493   return x.div(new BigNumber(2).pow(y)).floor();
    494 }