https://g0v.tw/assets/lib/svg-mesh/svg-mesh.js

771  }
772})(REVERSE_TABLE);
773
774//Reverse bits in a 32 bit word
775exports.reverse = function(v) {
776  return  (REVERSE_TABLE[ v         & 0xff] << 24) |
777          (REVERSE_TABLE[(v >>> 8)  & 0xff] << 16) |
778          (REVERSE_TABLE[(v >>> 16) & 0xff] << 8)  |
779           REVERSE_TABLE[(v >>> 24) & 0xff];
780}
781
782//Interleave bits of 2 coordinates with 16 bits.  Useful for fast quadtree codes
783exports.interleave2 = function(x, y) {
784  x &= 0xFFFF;
785  x = (x | (x << 8)) & 0x00FF00FF;
786  x = (x | (x << 4)) & 0x0F0F0F0F;
787  x = (x | (x << 2)) & 0x33333333;
788  x = (x | (x << 1)) & 0x55555555;
789
790  y &= 0xFFFF;
791  y = (y | (y << 8)) & 0x00FF00FF;
792  y = (y | (y << 4)) & 0x0F0F0F0F;
793  y = (y | (y << 2)) & 0x33333333;
794  y = (y | (y << 1)) & 0x55555555;
795
796  return x | (y << 1);
797}
798
799//Extracts the nth interleaved component
800exports.deinterleave2 = function(v, n) {
801  v = (v >>> n) & 0x55555555;
802  v = (v | (v >>> 1))  & 0x33333333;
803  v = (v | (v >>> 2))  & 0x0F0F0F0F;
804  v = (v | (v >>> 4))  & 0x00FF00FF;
805  v = (v | (v >>> 16)) & 0x000FFFF;
806  return (v << 16) >> 16;
807}
808
809
810//Interleave bits of 3 coordinates, each with 10 bits.  Useful for fast octree codes
811exports.interleave3 = function(x, y, z) {
812  x &= 0x3FF;
813  x  = (x | (x<<16)) & 4278190335;
814  x  = (x | (x<<8))  & 251719695;
815  x  = (x | (x<<4))  & 3272356035;
816  x  = (x | (x<<2))  & 1227133513;
817
818  y &= 0x3FF;
819  y  = (y | (y<<16)) & 4278190335;
820  y  = (y | (y<<8))  & 251719695;
821  y  = (y | (y<<4))  & 3272356035;
822  y  = (y | (y<<2))  & 1227133513;
823  x |= (y << 1);
824  
825  z &= 0x3FF;
826  z  = (z | (z<<16)) & 4278190335;
827  z  = (z | (z<<8))  & 251719695;
828  z  = (z | (z<<4))  & 3272356035;
829  z  = (z | (z<<2))  & 1227133513;
830  
831  return x | (z << 2);
832}
833
834//Extracts nth interleaved component of a 3-tuple
835exports.deinterleave3 = function(v, n) {
836  v = (v >>> n)       & 1227133513;
837  v = (v | (v>>>2))   & 3272356035;
838  v = (v | (v>>>4))   & 251719695;
839  v = (v | (v>>>8))   & 4278190335;
840  v = (v | (v>>>16))  & 0x3FF;
841  return (v<<22)>>22;
842}
843
844//Computes next combination in colexicographic order (this is mistakenly called nextPermutation on the bit twiddling hacks page)
845exports.nextCombination = function(v) {
846  var t = v | (v - 1);
847  return (t + 1) | (((~t & -~t) - 1) >>> (countTrailingZeros(v) + 1));
848}
849
850
851},{}],23:[function(require,module,exports){
852(function (module, exports) {
853  'use strict';
854
855  // Utils
856  function assert (val, msg) {
857    if (!val) throw new Error(msg || 'Assertion failed');
858  }
859
860  // Could use `inherits` module, but don't want to move from single file
861  // architecture yet.
862  function inherits (ctor, superCtor) {
863    ctor.super_ = superCtor;
864    var TempCtor = function () {};
865    TempCtor.prototype = superCtor.prototype;
866    ctor.prototype = new TempCtor();
867    ctor.prototype.constructor = ctor;
868  }
869
870  // BN
871
872  function BN (number, base, endian) {
873    if (BN.isBN(number)) {
874      return number;
875    }
876
877    this.negative = 0;
878    this.words = null;
879    this.length = 0;
880
881    // Reduction context
882    this.red = null;
883
884    if (number !== null) {
885      if (base === 'le' || base === 'be') {
886        endian = base;
887        base = 10;
888      }
889
890      this._init(number || 0, base || 10, endian || 'be');
891    }
892  }
893  if (typeof module === 'object') {
894    module.exports = BN;
895  } else {
896    exports.BN = BN;
897  }
898
899  BN.BN = BN;
900  BN.wordSize = 26;
901
902  var Buffer;
903  try {
904    Buffer = require('buffer').Buffer;
905  } catch (e) {
906  }
907
908  BN.isBN = function isBN (num) {
909    if (num instanceof BN) {
910      return true;
911    }
912
913    return num !== null && typeof num === 'object' &&
914      num.constructor.wordSize === BN.wordSize && Array.isArray(num.words);
915  };
916
917  BN.max = function max (left, right) {
918    if (left.cmp(right) > 0) return left;
919    return right;
920  };
921
922  BN.min = function min (left, right) {
923    if (left.cmp(right) < 0) return left;
924    return right;
925  };
926
927  BN.prototype._init = function init (number, base, endian) {
928    if (typeof number === 'number') {
929      return this._initNumber(number, base, endian);
930    }
931
932    if (typeof number === 'object') {
933      return this._initArray(number, base, endian);
934    }
935
936    if (base === 'hex') {
937      base = 16;
938    }
939    assert(base === (base | 0) && base >= 2 && base <= 36);
940
941    number = number.toString().replace(/\s+/g, '');
942    var start = 0;
943    if (number[0] === '-') {
944      start++;
945    }
946
947    if (base === 16) {
948      this._parseHex(number, start);
949    } else {
950      this._parseBase(number, base, start);
951    }
952
953    if (number[0] === '-') {
954      this.negative = 1;
955    }
956
957    this.strip();
958
959    if (endian !== 'le') return;
960
961    this._initArray(this.toArray(), base, endian);
962  };
963
964  BN.prototype._initNumber = function _initNumber (number, base, endian) {
965    if (number < 0) {
966      this.negative = 1;
967      number = -number;
968    }
969    if (number < 0x4000000) {
970      this.words = [ number & 0x3ffffff ];
971      this.length = 1;
972    } else if (number < 0x10000000000000) {
973      this.words = [
974        number & 0x3ffffff,
975        (number / 0x4000000) & 0x3ffffff
976      ];
977      this.length = 2;
978    } else {
979      assert(number < 0x20000000000000); // 2 ^ 53 (unsafe)
980      this.words = [
981        number & 0x3ffffff,
982        (number / 0x4000000) & 0x3ffffff,
983        1
984      ];
985      this.length = 3;
986    }
987
988    if (endian !== 'le') return;
989
990    // Reverse the bytes
991    this._initArray(this.toArray(), base, endian);
992  };
993
994  BN.prototype._initArray = function _initArray (number, base, endian) {
995    // Perhaps a Uint8Array
996    assert(typeof number.length === 'number');
997    if (number.length <= 0) {
998      this.words = [ 0 ];
999      this.length = 1;
1000      return this;
1001    }
1002
1003    this.length = Math.ceil(number.length / 3);
1004    this.words = new Array(this.length);
1005    for (var i = 0; i < this.length; i++) {
1006      this.words[i] = 0;
1007    }
1008
1009    var j, w;
1010    var off = 0;
1011    if (endian === 'be') {
1012      for (i = number.length - 1, j = 0; i >= 0; i -= 3) {
1013        w = number[i] | (number[i - 1] << 8) | (number[i - 2] << 16);
1014        this.words[j] |= (w << off) & 0x3ffffff;
1015        this.words[j + 1] = (w >>> (26 - off)) & 0x3ffffff;
1016        off += 24;
1017        if (off >= 26) {
1018          off -= 26;
1019          j++;
1020        }
1021      }
1022    } else if (endian === 'le') {
1023      for (i = 0, j = 0; i < number.length; i += 3) {
1024        w = number[i] | (number[i + 1] << 8) | (number[i + 2] << 16);
1025        this.words[j] |= (w << off) & 0x3ffffff;
1026        this.words[j + 1] = (w >>> (26 - off)) & 0x3ffffff;
1027        off += 24;
1028        if (off >= 26) {
1029          off -= 26;
1030          j++;
1031        }
1032      }
1033    }
1034    return this.strip();
1035  };
1036
1037  function parseHex (str, start, end) {
1038    var r = 0;
1039    var len = Math.min(str.length, end);
1040    for (var i = start; i < len; i++) {
1041      var c = str.charCodeAt(i) - 48;
1042
1043      r <<= 4;
1044
1045      // 'a' - 'f'
1046      if (c >= 49 && c <= 54) {
1047        r |= c - 49 + 0xa;
1048
1049      // 'A' - 'F'
1050      } else if (c >= 17 && c <= 22) {
1051        r |= c - 17 + 0xa;
1052
1053      // '0' - '9'
1054      } else {
1055        r |= c & 0xf;
1056      }
1057    }
1058    return r;
1059  }
1060
1061  BN.prototype._parseHex = function _parseHex (number, start) {
1062    // Create possibly bigger array to ensure that it fits the number
1063    this.length = Math.ceil((number.length - start) / 6);
1064    this.words = new Array(this.length);
1065    for (var i = 0; i < this.length; i++) {
1066      this.words[i] = 0;
1067    }
1068
1069    var j, w;
1070    // Scan 24-bit chunks and add them to the number
1071    var off = 0;
1072    for (i = number.length - 6, j = 0; i >= start; i -= 6) {
1073      w = parseHex(number, i, i + 6);
1074      this.words[j] |= (w << off) & 0x3ffffff;
1075      // NOTE: `0x3fffff` is intentional here, 26bits max shift + 24bit hex limb
1076      this.words[j + 1] |= w >>> (26 - off) & 0x3fffff;
1077      off += 24;
1078      if (off >= 26) {
1079        off -= 26;
1080        j++;
1081      }
1082    }
1083    if (i + 6 !== start) {
1084      w = parseHex(number, start, i + 6);
1085      this.words[j] |= (w << off) & 0x3ffffff;
1086      this.words[j + 1] |= w >>> (26 - off) & 0x3fffff;
1087    }
1088    this.strip();
1089  };
1090
1091  function parseBase (str, start, end, mul) {
1092    var r = 0;
1093    var len = Math.min(str.length, end);
1094    for (var i = start; i < len; i++) {
1095      var c = str.charCodeAt(i) - 48;
1096
1097      r *= mul;
1098
1099      // 'a'
1100      if (c >= 49) {
1101        r += c - 49 + 0xa;
1102
1103      // 'A'
1104      } else if (c >= 17) {
1105        r += c - 17 + 0xa;
1106
1107      // '0' - '9'
1108      } else {
1109        r += c;
1110      }
1111    }
1112    return r;
1113  }
1114
1115  BN.prototype._parseBase = function _parseBase (number, base, start) {
1116    // Initialize as zero
1117    this.words = [ 0 ];
1118    this.length = 1;
1119
1120    // Find length of limb in base
1121    for (var limbLen = 0, limbPow = 1; limbPow <= 0x3ffffff; limbPow *= base) {
1122      limbLen++;
1123    }
1124    limbLen--;
1125    limbPow = (limbPow / base) | 0;
1126
1127    var total = number.length - start;
1128    var mod = total % limbLen;
1129    var end = Math.min(total, total - mod) + start;
1130
1131    var word = 0;
1132    for (var i = start; i < end; i += limbLen) {
1133      word = parseBase(number, i, i + limbLen, base);
1134
1135      this.imuln(limbPow);
1136      if (this.words[0] + word < 0x4000000) {
1137        this.words[0] += word;
1138      } else {
1139        this._iaddn(word);
1140      }
1141    }
1142
1143    if (mod !== 0) {
1144      var pow = 1;
1145      word = parseBase(number, i, number.length, base);
1146
1147      for (i = 0; i < mod; i++) {
1148        pow *= base;
1149      }
1150
1151      this.imuln(pow);
1152      if (this.words[0] + word < 0x4000000) {
1153        this.words[0] += word;
1154      } else {
1155        this._iaddn(word);
1156      }
1157    }

1157
1158  };
1159
1160  BN.prototype.copy = function copy (dest) {
1161    dest.words = new Array(this.length);
1162    for (var i = 0; i < this.length; i++) {
1163      dest.words[i] = this.words[i];
1164    }
1165    dest.length = this.length;
1166    dest.negative = this.negative;
1167    dest.red = this.red;
1168  };
1169
1170  BN.prototype.clone = function clone () {
1171    var r = new BN(null);
1172    this.copy(r);
1173    return r;
1174  };
1175
1176  BN.prototype._expand = function _expand (size) {
1177    while (this.length < size) {
1178      this.words[this.length++] = 0;
1179    }
1180    return this;
1181  };
1182
1183  // Remove leading `0` from `this`
1184  BN.prototype.strip = function strip () {
1185    while (this.length > 1 && this.words[this.length - 1] === 0) {
1186      this.length--;
1187    }
1188    return this._normSign();
1189  };
1190
1191  BN.prototype._normSign = function _normSign () {
1192    // -0 = 0
1193    if (this.length === 1 && this.words[0] === 0) {
1194      this.negative = 0;
1195    }
1196    return this;
1197  };
1198
1199  BN.prototype.inspect = function inspect () {
1200    return (this.red ? '<BN-R: ' : '<BN: ') + this.toString(16) + '>';
1201  };
1202
1203  /*
1204
1205  var zeros = [];
1206  var groupSizes = [];
1207  var groupBases = [];
1208
1209  var s = '';
1210  var i = -1;
1211  while (++i < BN.wordSize) {
1212    zeros[i] = s;
1213    s += '0';
1214  }
1215  groupSizes[0] = 0;
1216  groupSizes[1] = 0;
1217  groupBases[0] = 0;
1218  groupBases[1] = 0;
1219  var base = 2 - 1;
1220  while (++base < 36 + 1) {
1221    var groupSize = 0;
1222    var groupBase = 1;
1223    while (groupBase < (1 << BN.wordSize) / base) {
1224      groupBase *= base;
1225      groupSize += 1;
1226    }
1227    groupSizes[base] = groupSize;
1228    groupBases[base] = groupBase;
1229  }
1230
1231  */
1232
1233  var zeros = [
1234    '',
1235    '0',
1236    '00',
1237    '000',
1238    '0000',
1239    '00000',
1240    '000000',
1241    '0000000',
1242    '00000000',
1243    '000000000',
1244    '0000000000',
1245    '00000000000',
1246    '000000000000',
1247    '0000000000000',
1248    '00000000000000',
1249    '000000000000000',
1250    '0000000000000000',
1251    '00000000000000000',
1252    '000000000000000000',
1253    '0000000000000000000',
1254    '00000000000000000000',
1255    '000000000000000000000',
1256    '0000000000000000000000',
1257    '00000000000000000000000',
1258    '000000000000000000000000',
1259    '0000000000000000000000000'
1260  ];
1261
1262  var groupSizes = [
1263    0, 0,
1264    25, 16, 12, 11, 10, 9, 8,
1265    8, 7, 7, 7, 7, 6, 6,
1266    6, 6, 6, 6, 6, 5, 5,
1267    5, 5, 5, 5, 5, 5, 5,
1268    5, 5, 5, 5, 5, 5, 5
1269  ];
1270
1271  var groupBases = [
1272    0, 0,
1273    33554432, 43046721, 16777216, 48828125, 60466176, 40353607, 16777216,
1274    43046721, 10000000, 19487171, 35831808, 62748517, 7529536, 11390625,
1275    16777216, 24137569, 34012224, 47045881, 64000000, 4084101, 5153632,
1276    6436343, 7962624, 9765625, 11881376, 14348907, 17210368, 20511149,
1277    24300000, 28629151, 33554432, 39135393, 45435424, 52521875, 60466176
1278  ];
1279
1280  BN.prototype.toString = function toString (base, padding) {
1281    base = base || 10;
1282    padding = padding | 0 || 1;
1283
1284    var out;
1285    if (base === 16 || base === 'hex') {
1286      out = '';
1287      var off = 0;
1288      var carry = 0;
1289      for (var i = 0; i < this.length; i++) {
1290        var w = this.words[i];
1291        var word = (((w << off) | carry) & 0xffffff).toString(16);
1292        carry = (w >>> (24 - off)) & 0xffffff;
1293        if (carry !== 0 || i !== this.length - 1) {
1294          out = zeros[6 - word.length] + word + out;
1295        } else {
1296          out = word + out;
1297        }
1298        off += 2;
1299        if (off >= 26) {
1300          off -= 26;
1301          i--;
1302        }
1303      }
1304      if (carry !== 0) {
1305        out = carry.toString(16) + out;
1306      }
1307      while (out.length % padding !== 0) {
1308        out = '0' + out;
1309      }
1310      if (this.negative !== 0) {
1311        out = '-' + out;
1312      }
1313      return out;
1314    }
1315
1316    if (base === (base | 0) && base >= 2 && base <= 36) {
1317      // var groupSize = Math.floor(BN.wordSize * Math.LN2 / Math.log(base));
1318      var groupSize = groupSizes[base];
1319      // var groupBase = Math.pow(base, groupSize);
1320      var groupBase = groupBases[base];
1321      out = '';
1322      var c = this.clone();
1323      c.negative = 0;
1324      while (!c.isZero()) {
1325        var r = c.modn(groupBase).toString(base);
1326        c = c.idivn(groupBase);
1327
1328        if (!c.isZero()) {
1329          out = zeros[groupSize - r.length] + r + out;
1330        } else {
1331          out = r + out;
1332        }
1333      }
1334      if (this.isZero()) {
1335        out = '0' + out;
1336      }
1337      while (out.length % padding !== 0) {
1338        out = '0' + out;
1339      }
1340      if (this.negative !== 0) {
1341        out = '-' + out;
1342      }
1343      return out;
1344    }
1345
1346    assert(false, 'Base should be between 2 and 36');
1347  };
1348
1349  BN.prototype.toNumber = function toNumber () {
1350    var ret = this.words[0];
1351    if (this.length === 2) {
1352      ret += this.words[1] * 0x4000000;
1353    } else if (this.length === 3 && this.words[2] === 0x01) {
1354      // NOTE: at this stage it is known that the top bit is set
1355      ret += 0x10000000000000 + (this.words[1] * 0x4000000);
1356    } else if (this.length > 2) {
1357      assert(false, 'Number can only safely store up to 53 bits');
1358    }
1359    return (this.negative !== 0) ? -ret : ret;
1360  };
1361
1362  BN.prototype.toJSON = function toJSON () {
1363    return this.toString(16);
1364  };
1365
1366  BN.prototype.toBuffer = function toBuffer (endian, length) {
1367    assert(typeof Buffer !== 'undefined');
1368    return this.toArrayLike(Buffer, endian, length);
1369  };
1370
1371  BN.prototype.toArray = function toArray (endian, length) {
1372    return this.toArrayLike(Array, endian, length);
1373  };
1374
1375  BN.prototype.toArrayLike = function toArrayLike (ArrayType, endian, length) {
1376    var byteLength = this.byteLength();
1377    var reqLength = length || Math.max(1, byteLength);
1378    assert(byteLength <= reqLength, 'byte array longer than desired length');
1379    assert(reqLength > 0, 'Requested array length <= 0');
1380
1381    this.strip();
1382    var littleEndian = endian === 'le';
1383    var res = new ArrayType(reqLength);
1384
1385    var b, i;
1386    var q = this.clone();
1387    if (!littleEndian) {
1388      // Assume big-endian
1389      for (i = 0; i < reqLength - byteLength; i++) {
1390        res[i] = 0;
1391      }
1392
1393      for (i = 0; !q.isZero(); i++) {
1394        b = q.andln(0xff);
1395        q.iushrn(8);
1396
1397        res[reqLength - i - 1] = b;
1398      }
1399    } else {
1400      for (i = 0; !q.isZero(); i++) {
1401        b = q.andln(0xff);
1402        q.iushrn(8);
1403
1404        res[i] = b;
1405      }
1406
1407      for (; i < reqLength; i++) {
1408        res[i] = 0;
1409      }
1410    }
1411
1412    return res;
1413  };
1414
1415  if (Math.clz32) {
1416    BN.prototype._countBits = function _countBits (w) {
1417      return 32 - Math.clz32(w);
1418    };
1419  } else {
1420    BN.prototype._countBits = function _countBits (w) {
1421      var t = w;
1422      var r = 0;
1423      if (t >= 0x1000) {
1424        r += 13;
1425        t >>>= 13;
1426      }
1427      if (t >= 0x40) {
1428        r += 7;
1429        t >>>= 7;
1430      }
1431      if (t >= 0x8) {
1432        r += 4;
1433        t >>>= 4;
1434      }
1435      if (t >= 0x02) {
1436        r += 2;
1437        t >>>= 2;
1438      }
1439      return r + t;
1440    };
1441  }
1442
1443  BN.prototype._zeroBits = function _zeroBits (w) {
1444    // Short-cut
1445    if (w === 0) return 26;
1446
1447    var t = w;
1448    var r = 0;
1449    if ((t & 0x1fff) === 0) {
1450      r += 13;
1451      t >>>= 13;
1452    }
1453    if ((t & 0x7f) === 0) {
1454      r += 7;
1455      t >>>= 7;
1456    }
1457    if ((t & 0xf) === 0) {
1458      r += 4;
1459      t >>>= 4;
1460    }
1461    if ((t & 0x3) === 0) {
1462      r += 2;
1463      t >>>= 2;
1464    }
1465    if ((t & 0x1) === 0) {
1466      r++;
1467    }
1468    return r;
1469  };
1470
1471  // Return number of used bits in a BN
1472  BN.prototype.bitLength = function bitLength () {
1473    var w = this.words[this.length - 1];
1474    var hi = this._countBits(w);
1475    return (this.length - 1) * 26 + hi;
1476  };
1477
1478  function toBitArray (num) {
1479    var w = new Array(num.bitLength());
1480
1481    for (var bit = 0; bit < w.length; bit++) {
1482      var off = (bit / 26) | 0;
1483      var wbit = bit % 26;
1484
1485      w[bit] = (num.words[off] & (1 << wbit)) >>> wbit;
1486    }
1487
1488    return w;
1489  }
1490
1491  // Number of trailing zero bits
1492  BN.prototype.zeroBits = function zeroBits () {
1493    if (this.isZero()) return 0;
1494
1495    var r = 0;
1496    for (var i = 0; i < this.length; i++) {
1497      var b = this._zeroBits(this.words[i]);
1498      r += b;
1499      if (b !== 26) break;
1500    }
1501    return r;
1502  };
1503
1504  BN.prototype.byteLength = function byteLength () {
1505    return Math.ceil(this.bitLength() / 8);
1506  };
1507
1508  BN.prototype.toTwos = function toTwos (width) {
1509    if (this.negative !== 0) {
1510      return this.abs().inotn(width).iaddn(1);
1511    }
1512    return this.clone();
1513  };
1514
1515  BN.prototype.fromTwos = function fromTwos (width) {
1516    if (this.testn(width - 1)) {
1517      return this.notn(width).iaddn(1).ineg();
1518    }
1519    return this.clone();
1520  };
1521
1522  BN.prototype.isNeg = function isNeg () {
1523    return this.negative !== 0;
1524  };
1525
1526  // Return negative clone of `this`
1527  BN.prototype.neg = function neg () {
1528    return this.clone().ineg();
1529  };
1530
1531  BN.prototype.ineg = function ineg () {
1532    if (!this.isZero()) {
1533      this.negative ^= 1;
1534    }
1535
1536    return this;
1537  };
1538
1539  // Or `num` with `this` in-place
1540  BN.prototype.iuor = function iuor (num) {
1541    while (this.length < num.length) {
1542      this.words[this.length++] = 0;
1543    }
1544
1545    for (var i = 0; i < num.length; i++) {
1546      this.words[i] = this.words[i] | num.words[i];
1547    }
1548
1549    return this.strip();
1550  };
1551
1552  BN.prototype.ior = function ior (num) {
1553    assert((this.negative | num.negative) === 0);
1554    return this.iuor(num);
1555  };
1556
1557  // Or `num` with `this`
1558  BN.prototype.or = function or (num) {
1559    if (this.length > num.length) return this.clone().ior(num);
1560    return num.clone().ior(this);
1561  };
1562
1563  BN.prototype.uor = function uor (num) {
1564    if (this.length > num.length) return this.clone().iuor(num);
1565    return num.clone().iuor(this);
1566  };
1567
1568  // And `num` with `this` in-place
1569  BN.prototype.iuand = function iuand (num) {
1570    // b = min-length(num, this)
1571    var b;
1572    if (this.length > num.length) {
1573      b = num;
1574    } else {
1575      b = this;
1576    }
1577
1578    for (var i = 0; i < b.length; i++) {
1579      this.words[i] = this.words[i] & num.words[i];
1580    }
1581
1582    this.length = b.length;
1583
1584    return this.strip();
1585  };
1586
1587  BN.prototype.iand = function iand (num) {
1588    assert((this.negative | num.negative) === 0);
1589    return this.iuand(num);
1590  };
1591
1592  // And `num` with `this`
1593  BN.prototype.and = function and (num) {
1594    if (this.length > num.length) return this.clone().iand(num);
1595    return num.clone().iand(this);
1596  };
1597
1598  BN.prototype.uand = function uand (num) {
1599    if (this.length > num.length) return this.clone().iuand(num);
1600    return num.clone().iuand(this);
1601  };
1602
1603  // Xor `num` with `this` in-place
1604  BN.prototype.iuxor = function iuxor (num) {
1605    // a.length > b.length
1606    var a;
1607    var b;
1608    if (this.length > num.length) {
1609      a = this;
1610      b = num;
1611    } else {
1612      a = num;
1613      b = this;
1614    }
1615
1616    for (var i = 0; i < b.length; i++) {
1617      this.words[i] = a.words[i] ^ b.words[i];
1618    }
1619
1620    if (this !== a) {
1621      for (; i < a.length; i++) {
1622        this.words[i] = a.words[i];
1623      }
1624    }
1625
1626    this.length = a.length;
1627
1628    return this.strip();
1629  };
1630
1631  BN.prototype.ixor = function ixor (num) {
1632    assert((this.negative | num.negative) === 0);
1633    return this.iuxor(num);
1634  };
1635
1636  // Xor `num` with `this`
1637  BN.prototype.xor = function xor (num) {
1638    if (this.length > num.length) return this.clone().ixor(num);
1639    return num.clone().ixor(this);
1640  };
1641
1642  BN.prototype.uxor = function uxor (num) {
1643    if (this.length > num.length) return this.clone().iuxor(num);
1644    return num.clone().iuxor(this);
1645  };
1646
1647  // Not ``this`` with ``width`` bitwidth
1648  BN.prototype.inotn = function inotn (width) {
1649    assert(typeof width === 'number' && width >= 0);
1650
1651    var bytesNeeded = Math.ceil(width / 26) | 0;
1652    var bitsLeft = width % 26;
1653
1654    // Extend the buffer with leading zeroes
1655    this._expand(bytesNeeded);
1656
1657    if (bitsLeft > 0) {
1658      bytesNeeded--;
1659    }
1660
1661    // Handle complete words
1662    for (var i = 0; i < bytesNeeded; i++) {
1663      this.words[i] = ~this.words[i] & 0x3ffffff;
1664    }
1665
1666    // Handle the residue
1667    if (bitsLeft > 0) {
1668      this.words[i] = ~this.words[i] & (0x3ffffff >> (26 - bitsLeft));
1669    }
1670
1671    // And remove leading zeroes
1672    return this.strip();
1673  };
1674
1675  BN.prototype.notn = function notn (width) {
1676    return this.clone().inotn(width);
1677  };
1678
1679  // Set `bit` of `this`
1680  BN.prototype.setn = function setn (bit, val) {
1681    assert(typeof bit === 'number' && bit >= 0);
1682
1683    var off = (bit / 26) | 0;
1684    var wbit = bit % 26;
1685
1686    this._expand(off + 1);
1687
1688    if (val) {
1689      this.words[off] = this.words[off] | (1 << wbit);
1690    } else {
1691      this.words[off] = this.words[off] & ~(1 << wbit);
1692    }
1693
1694    return this.strip();
1695  };
1696
1697  // Add `num` to `this` in-place
1698  BN.prototype.iadd = function iadd (num) {
1699    var r;
1700
1701    // negative + positive
1702    if (this.negative !== 0 && num.negative === 0) {
1703      this.negative = 0;
1704      r = this.isub(num);
1705      this.negative ^= 1;
1706      return this._normSign();
1707
1708    // positive + negative
1709    } else if (this.negative === 0 && num.negative !== 0) {
1710      num.negative = 0;
1711      r = this.isub(num);
1712      num.negative = 1;
1713      return r._normSign();
1714    }
1715
1716    // a.length > b.length
1717    var a, b;
1718    if (this.length > num.length) {
1719      a = this;
1720      b = num;
1721    } else {
1722      a = num;
1723      b = this;
1724    }
1725
1726    var carry = 0;
1727    for (var i = 0; i < b.length; i++) {
1728      r = (a.words[i] | 0) + (b.words[i] | 0) + carry;
1729      this.words[i] = r & 0x3ffffff;
1730      carry = r >>> 26;
1731    }
1732    for (; carry !== 0 && i < a.length; i++) {
1733      r = (a.words[i] | 0) + carry;
1734      this.words[i] = r & 0x3ffffff;
1735      carry = r >>> 26;
1736    }
1737
1738    this.length = a.length;
1739    if (carry !== 0) {
1740      this.words[this.length] = carry;
1741      this.length++;
1742    // Copy the rest of the words
1743    } else if (a !== this) {
1744      for (; i < a.length; i++) {
1745        this.words[i] = a.words[i];
1746      }
1747    }
1748
1749    return this;
1750  };
1751
1752  // Add `num` to `this`
1753  BN.prototype.add = function add (num) {
1754    var res;
1755    if (num.negative !== 0 && this.negative === 0) {
1756      num.negative = 0;
1757      res = this.sub(num);
1758      num.negative ^= 1;
1759      return res;
1760    } else if (num.negative === 0 && this.negative !== 0) {
1761      this.negative = 0;
1762      res = num.sub(this);
1763      this.negative = 1;
1764      return res;
1765    }
1766
1767    if (this.length > num.length) return this.clone().iadd(num);
1768
1769    return num.clone().iadd(this);
1770  };
1771
1772  // Subtract `num` from `this` in-place
1773  BN.prototype.isub = function isub (num) {
1774    // this - (-num) = this + num
1775    if (num.negative !== 0) {
1776      num.negative = 0;
1777      var r = this.iadd(num);
1778      num.negative = 1;
1779      return r._normSign();
1780
1781    // -this - num = -(this + num)
1782    } else if (this.negative !== 0) {
1783      this.negative = 0;
1784      this.iadd(num);
1785      this.negative = 1;
1786      return this._normSign();
1787    }
1788
1789    // At this point both numbers are positive
1790    var cmp = this.cmp(num);
1791
1792    // Optimization - zeroify
1793    if (cmp === 0) {
1794      this.negative = 0;
1795      this.length = 1;
1796      this.words[0] = 0;
1797      return this;
1798    }
1799
1800    // a > b
1801    var a, b;
1802    if (cmp > 0) {
1803      a = this;
1804      b = num;
1805    } else {
1806      a = num;
1807      b = this;
1808    }
1809
1810    var carry = 0;
1811    for (var i = 0; i < b.length; i++) {
1812      r = (a.words[i] | 0) - (b.words[i] | 0) + carry;
1813      carry = r >> 26;
1814      this.words[i] = r & 0x3ffffff;
1815    }
1816    for (; carry !== 0 && i < a.length; i++) {
1817      r = (a.words[i] | 0) + carry;
1818      carry = r >> 26;
1819      this.words[i] = r & 0x3ffffff;
1820    }
1821
1822    // Copy rest of the words
1823    if (carry === 0 && i < a.length && a !== this) {
1824      for (; i < a.length; i++) {
1825        this.words[i] = a.words[i];
1826      }
1827    }
1828
1829    this.length = Math.max(this.length, i);
1830
1831    if (a !== this) {
1832      this.negative = 1;
1833    }
1834
1835    return this.strip();
1836  };
1837
1838  // Subtract `num` from `this`
1839  BN.prototype.sub = function sub (num) {
1840    return this.clone().isub(num);
1841  };
1842
1843  function smallMulTo (self, num, out) {
1844    out.negative = num.negative ^ self.negative;
1845    var len = (self.length + num.length) | 0;
1846    out.length = len;
1847    len = (len - 1) | 0;
1848
1849    // Peel one iteration (compiler can't do it, because of code complexity)
1850    var a = self.words[0] | 0;
1851    var b = num.words[0] | 0;
1852    var r = a * b;
1853
1854    var lo = r & 0x3ffffff;
1855    var carry = (r / 0x4000000) | 0;
1856    out.words[0] = lo;
1857
1858    for (var k = 1; k < len; k++) {
1859      // Sum all words with the same `i + j = k` and accumulate `ncarry`,
1860      // note that ncarry could be >= 0x3ffffff
1861      var ncarry = carry >>> 26;
1862      var rword = carry & 0x3ffffff;
1863      var maxJ = Math.min(k, num.length - 1);
1864      for (var j = Math.max(0, k - self.length + 1); j <= maxJ; j++) {
1865        var i = (k - j) | 0;
1866        a = self.words[i] | 0;
1867        b = num.words[j] | 0;
1868        r = a * b + rword;
1869        ncarry += (r / 0x4000000) | 0;
1870        rword = r & 0x3ffffff;
1871      }
1872      out.words[k] = rword | 0;
1873      carry = ncarry | 0;
1874    }
1875    if (carry !== 0) {
1876      out.words[k] = carry | 0;
1877    } else {
1878      out.length--;
1879    }
1880
1881    return out.strip();
1882  }
1883
1884  // TODO(indutny): it may be reasonable to omit it for users who don't need
1885  // to work with 256-bit numbers, otherwise it gives 20% improvement for 256-bit
1886  // multiplication (like elliptic secp256k1).
1887  var comb10MulTo = function comb10MulTo (self, num, out) {
1888    var a = self.words;
1889    var b = num.words;
1890    var o = out.words;
1891    var c = 0;
1892    var lo;
1893    var mid;
1894    var hi;
1895    var a0 = a[0] | 0;
1896    var al0 = a0 & 0x1fff;
1897    var ah0 = a0 >>> 13;
1898    var a1 = a[1] | 0;
1899    var al1 = a1 & 0x1fff;
1900    var ah1 = a1 >>> 13;
1901    var a2 = a[2] | 0;
1902    var al2 = a2 & 0x1fff;
1903    var ah2 = a2 >>> 13;
1904    var a3 = a[3] | 0;
1905    var al3 = a3 & 0x1fff;
1906    var ah3 = a3 >>> 13;
1907    var a4 = a[4] | 0;
1908    var al4 = a4 & 0x1fff;
1909    var ah4 = a4 >>> 13;
1910    var a5 = a[5] | 0;
1911    var al5 = a5 & 0x1fff;
1912    var ah5 = a5 >>> 13;
1913    var a6 = a[6] | 0;
1914    var al6 = a6 & 0x1fff;
1915    var ah6 = a6 >>> 13;
1916    var a7 = a[7] | 0;
1917    var al7 = a7 & 0x1fff;
1918    var ah7 = a7 >>> 13;
1919    var a8 = a[8] | 0;
1920    var al8 = a8 & 0x1fff;
1921    var ah8 = a8 >>> 13;
1922    var a9 = a[9] | 0;
1923    var al9 = a9 & 0x1fff;
1924    var ah9 = a9 >>> 13;
1925    var b0 = b[0] | 0;
1926    var bl0 = b0 & 0x1fff;
1927    var bh0 = b0 >>> 13;
1928    var b1 = b[1] | 0;
1929    var bl1 = b1 & 0x1fff;
1930    var bh1 = b1 >>> 13;
1931    var b2 = b[2] | 0;
1932    var bl2 = b2 & 0x1fff;
1933    var bh2 = b2 >>> 13;
1934    var b3 = b[3] | 0;
1935    var bl3 = b3 & 0x1fff;
1936    var bh3 = b3 >>> 13;
1937    var b4 = b[4] | 0;
1938    var bl4 = b4 & 0x1fff;
1939    var bh4 = b4 >>> 13;
1940    var b5 = b[5] | 0;
1941    var bl5 = b5 & 0x1fff;
1942    var bh5 = b5 >>> 13;
1943    var b6 = b[6] | 0;
1944    var bl6 = b6 & 0x1fff;
1945    var bh6 = b6 >>> 13;
1946    var b7 = b[7] | 0;
1947    var bl7 = b7 & 0x1fff;
1948    var bh7 = b7 >>> 13;
1949    var b8 = b[8] | 0;
1950    var bl8 = b8 & 0x1fff;
1951    var bh8 = b8 >>> 13;
1952    var b9 = b[9] | 0;
1953    var bl9 = b9 & 0x1fff;
1954    var bh9 = b9 >>> 13;
1955
1956    out.negative = self.negative ^ num.negative;
1957    out.length = 19;
1958    /* k = 0 */
1959    lo = Math.imul(al0, bl0);
1960    mid = Math.imul(al0, bh0);
1961    mid = (mid + Math.imul(ah0, bl0)) | 0;
1962    hi = Math.imul(ah0, bh0);
1963    var w0 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
1964    c = (((hi + (mid >>> 13)) | 0) + (w0 >>> 26)) | 0;
1965    w0 &= 0x3ffffff;
1966    /* k = 1 */
1967    lo = Math.imul(al1, bl0);
1968    mid = Math.imul(al1, bh0);
1969    mid = (mid + Math.imul(ah1, bl0)) | 0;
1970    hi = Math.imul(ah1, bh0);
1971    lo = (lo + Math.imul(al0, bl1)) | 0;
1972    mid = (mid + Math.imul(al0, bh1)) | 0;
1973    mid = (mid + Math.imul(ah0, bl1)) | 0;
1974    hi = (hi + Math.imul(ah0, bh1)) | 0;
1975    var w1 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
1976    c = (((hi + (mid >>> 13)) | 0) + (w1 >>> 26)) | 0;
1977    w1 &= 0x3ffffff;
1978    /* k = 2 */
1979    lo = Math.imul(al2, bl0);
1980    mid = Math.imul(al2, bh0);
1981    mid = (mid + Math.imul(ah2, bl0)) | 0;
1982    hi = Math.imul(ah2, bh0);
1983    lo = (lo + Math.imul(al1, bl1)) | 0;
1984    mid = (mid + Math.imul(al1, bh1)) | 0;
1985    mid = (mid + Math.imul(ah1, bl1)) | 0;
1986    hi = (hi + Math.imul(ah1, bh1)) | 0;
1987    lo = (lo + Math.imul(al0, bl2)) | 0;
1988    mid = (mid + Math.imul(al0, bh2)) | 0;
1989    mid = (mid + Math.imul(ah0, bl2)) | 0;
1990    hi = (hi + Math.imul(ah0, bh2)) | 0;
1991    var w2 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
1992    c = (((hi + (mid >>> 13)) | 0) + (w2 >>> 26)) | 0;
1993    w2 &= 0x3ffffff;
1994    /* k = 3 */
1995    lo = Math.imul(al3, bl0);
1996    mid = Math.imul(al3, bh0);
1997    mid = (mid + Math.imul(ah3, bl0)) | 0;
1998    hi = Math.imul(ah3, bh0);
1999    lo = (lo + Math.imul(al2, bl1)) | 0;
2000    mid = (mid + Math.imul(al2, bh1)) | 0;
2001    mid = (mid + Math.imul(ah2, bl1)) | 0;
2002    hi = (hi + Math.imul(ah2, bh1)) | 0;
2003    lo = (lo + Math.imul(al1, bl2)) | 0;
2004    mid = (mid + Math.imul(al1, bh2)) | 0;
2005    mid = (mid + Math.imul(ah1, bl2)) | 0;
2006    hi = (hi + Math.imul(ah1, bh2)) | 0;
2007    lo = (lo + Math.imul(al0, bl3)) | 0;
2008    mid = (mid + Math.imul(al0, bh3)) | 0;
2009    mid = (mid + Math.imul(ah0, bl3)) | 0;
2010    hi = (hi + Math.imul(ah0, bh3)) | 0;
2011    var w3 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2012    c = (((hi + (mid >>> 13)) | 0) + (w3 >>> 26)) | 0;
2013    w3 &= 0x3ffffff;
2014    /* k = 4 */
2015    lo = Math.imul(al4, bl0);
2016    mid = Math.imul(al4, bh0);
2017    mid = (mid + Math.imul(ah4, bl0)) | 0;
2018    hi = Math.imul(ah4, bh0);
2019    lo = (lo + Math.imul(al3, bl1)) | 0;
2020    mid = (mid + Math.imul(al3, bh1)) | 0;
2021    mid = (mid + Math.imul(ah3, bl1)) | 0;
2022    hi = (hi + Math.imul(ah3, bh1)) | 0;
2023    lo = (lo + Math.imul(al2, bl2)) | 0;
2024    mid = (mid + Math.imul(al2, bh2)) | 0;
2025    mid = (mid + Math.imul(ah2, bl2)) | 0;
2026    hi = (hi + Math.imul(ah2, bh2)) | 0;
2027    lo = (lo + Math.imul(al1, bl3)) | 0;
2028    mid = (mid + Math.imul(al1, bh3)) | 0;
2029    mid = (mid + Math.imul(ah1, bl3)) | 0;
2030    hi = (hi + Math.imul(ah1, bh3)) | 0;
2031    lo = (lo + Math.imul(al0, bl4)) | 0;
2032    mid = (mid + Math.imul(al0, bh4)) | 0;
2033    mid = (mid + Math.imul(ah0, bl4)) | 0;
2034    hi = (hi + Math.imul(ah0, bh4)) | 0;
2035    var w4 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2036    c = (((hi + (mid >>> 13)) | 0) + (w4 >>> 26)) | 0;
2037    w4 &= 0x3ffffff;
2038    /* k = 5 */
2039    lo = Math.imul(al5, bl0);
2040    mid = Math.imul(al5, bh0);
2041    mid = (mid + Math.imul(ah5, bl0)) | 0;
2042    hi = Math.imul(ah5, bh0);
2043    lo = (lo + Math.imul(al4, bl1)) | 0;
2044    mid = (mid + Math.imul(al4, bh1)) | 0;
2045    mid = (mid + Math.imul(ah4, bl1)) | 0;
2046    hi = (hi + Math.imul(ah4, bh1)) | 0;
2047    lo = (lo + Math.imul(al3, bl2)) | 0;
2048    mid = (mid + Math.imul(al3, bh2)) | 0;
2049    mid = (mid + Math.imul(ah3, bl2)) | 0;
2050    hi = (hi + Math.imul(ah3, bh2)) | 0;
2051    lo = (lo + Math.imul(al2, bl3)) | 0;
2052    mid = (mid + Math.imul(al2, bh3)) | 0;
2053    mid = (mid + Math.imul(ah2, bl3)) | 0;
2054    hi = (hi + Math.imul(ah2, bh3)) | 0;
2055    lo = (lo + Math.imul(al1, bl4)) | 0;
2056    mid = (mid + Math.imul(al1, bh4)) | 0;
2057    mid = (mid + Math.imul(ah1, bl4)) | 0;
2058    hi = (hi + Math.imul(ah1, bh4)) | 0;
2059    lo = (lo + Math.imul(al0, bl5)) | 0;
2060    mid = (mid + Math.imul(al0, bh5)) | 0;
2061    mid = (mid + Math.imul(ah0, bl5)) | 0;
2062    hi = (hi + Math.imul(ah0, bh5)) | 0;
2063    var w5 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2064    c = (((hi + (mid >>> 13)) | 0) + (w5 >>> 26)) | 0;
2065    w5 &= 0x3ffffff;
2066    /* k = 6 */
2067    lo = Math.imul(al6, bl0);
2068    mid = Math.imul(al6, bh0);
2069    mid = (mid + Math.imul(ah6, bl0)) | 0;
2070    hi = Math.imul(ah6, bh0);
2071    lo = (lo + Math.imul(al5, bl1)) | 0;
2072    mid = (mid + Math.imul(al5, bh1)) | 0;
2073    mid = (mid + Math.imul(ah5, bl1)) | 0;
2074    hi = (hi + Math.imul(ah5, bh1)) | 0;
2075    lo = (lo + Math.imul(al4, bl2)) | 0;
2076    mid = (mid + Math.imul(al4, bh2)) | 0;
2077    mid = (mid + Math.imul(ah4, bl2)) | 0;
2078    hi = (hi + Math.imul(ah4, bh2)) | 0;
2079    lo = (lo + Math.imul(al3, bl3)) | 0;
2080    mid = (mid + Math.imul(al3, bh3)) | 0;
2081    mid = (mid + Math.imul(ah3, bl3)) | 0;
2082    hi = (hi + Math.imul(ah3, bh3)) | 0;
2083    lo = (lo + Math.imul(al2, bl4)) | 0;
2084    mid = (mid + Math.imul(al2, bh4)) | 0;
2085    mid = (mid + Math.imul(ah2, bl4)) | 0;
2086    hi = (hi + Math.imul(ah2, bh4)) | 0;
2087    lo = (lo + Math.imul(al1, bl5)) | 0;
2088    mid = (mid + Math.imul(al1, bh5)) | 0;
2089    mid = (mid + Math.imul(ah1, bl5)) | 0;
2090    hi = (hi + Math.imul(ah1, bh5)) | 0;
2091    lo = (lo + Math.imul(al0, bl6)) | 0;
2092    mid = (mid + Math.imul(al0, bh6)) | 0;
2093    mid = (mid + Math.imul(ah0, bl6)) | 0;
2094    hi = (hi + Math.imul(ah0, bh6)) | 0;
2095    var w6 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2096    c = (((hi + (mid >>> 13)) | 0) + (w6 >>> 26)) | 0;
2097    w6 &= 0x3ffffff;
2098    /* k = 7 */
2099    lo = Math.imul(al7, bl0);
2100    mid = Math.imul(al7, bh0);
2101    mid = (mid + Math.imul(ah7, bl0)) | 0;
2102    hi = Math.imul(ah7, bh0);
2103    lo = (lo + Math.imul(al6, bl1)) | 0;
2104    mid = (mid + Math.imul(al6, bh1)) | 0;
2105    mid = (mid + Math.imul(ah6, bl1)) | 0;
2106    hi = (hi + Math.imul(ah6, bh1)) | 0;
2107    lo = (lo + Math.imul(al5, bl2)) | 0;
2108    mid = (mid + Math.imul(al5, bh2)) | 0;
2109    mid = (mid + Math.imul(ah5, bl2)) | 0;
2110    hi = (hi + Math.imul(ah5, bh2)) | 0;
2111    lo = (lo + Math.imul(al4, bl3)) | 0;
2112    mid = (mid + Math.imul(al4, bh3)) | 0;
2113    mid = (mid + Math.imul(ah4, bl3)) | 0;
2114    hi = (hi + Math.imul(ah4, bh3)) | 0;
2115    lo = (lo + Math.imul(al3, bl4)) | 0;
2116    mid = (mid + Math.imul(al3, bh4)) | 0;
2117    mid = (mid + Math.imul(ah3, bl4)) | 0;
2118    hi = (hi + Math.imul(ah3, bh4)) | 0;
2119    lo = (lo + Math.imul(al2, bl5)) | 0;
2120    mid = (mid + Math.imul(al2, bh5)) | 0;
2121    mid = (mid + Math.imul(ah2, bl5)) | 0;
2122    hi = (hi + Math.imul(ah2, bh5)) | 0;
2123    lo = (lo + Math.imul(al1, bl6)) | 0;
2124    mid = (mid + Math.imul(al1, bh6)) | 0;
2125    mid = (mid + Math.imul(ah1, bl6)) | 0;
2126    hi = (hi + Math.imul(ah1, bh6)) | 0;
2127    lo = (lo + Math.imul(al0, bl7)) | 0;
2128    mid = (mid + Math.imul(al0, bh7)) | 0;
2129    mid = (mid + Math.imul(ah0, bl7)) | 0;
2130    hi = (hi + Math.imul(ah0, bh7)) | 0;
2131    var w7 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2132    c = (((hi + (mid >>> 13)) | 0) + (w7 >>> 26)) | 0;
2133    w7 &= 0x3ffffff;
2134    /* k = 8 */
2135    lo = Math.imul(al8, bl0);
2136    mid = Math.imul(al8, bh0);
2137    mid = (mid + Math.imul(ah8, bl0)) | 0;
2138    hi = Math.imul(ah8, bh0);
2139    lo = (lo + Math.imul(al7, bl1)) | 0;
2140    mid = (mid + Math.imul(al7, bh1)) | 0;
2141    mid = (mid + Math.imul(ah7, bl1)) | 0;
2142    hi = (hi + Math.imul(ah7, bh1)) | 0;
2143    lo = (lo + Math.imul(al6, bl2)) | 0;
2144    mid = (mid + Math.imul(al6, bh2)) | 0;
2145    mid = (mid + Math.imul(ah6, bl2)) | 0;
2146    hi = (hi + Math.imul(ah6, bh2)) | 0;
2147    lo = (lo + Math.imul(al5, bl3)) | 0;
2148    mid = (mid + Math.imul(al5, bh3)) | 0;
2149    mid = (mid + Math.imul(ah5, bl3)) | 0;
2150    hi = (hi + Math.imul(ah5, bh3)) | 0;
2151    lo = (lo + Math.imul(al4, bl4)) | 0;
2152    mid = (mid + Math.imul(al4, bh4)) | 0;
2153    mid = (mid + Math.imul(ah4, bl4)) | 0;
2154    hi = (hi + Math.imul(ah4, bh4)) | 0;
2155    lo = (lo + Math.imul(al3, bl5)) | 0;
2156    mid = (mid + Math.imul(al3, bh5)) | 0;
2157    mid = (mid + Math.imul(ah3, bl5)) | 0;
2158    hi = (hi + Math.imul(ah3, bh5)) | 0;
2159    lo = (lo + Math.imul(al2, bl6)) | 0;
2160    mid = (mid + Math.imul(al2, bh6)) | 0;
2161    mid = (mid + Math.imul(ah2, bl6)) | 0;
2162    hi = (hi + Math.imul(ah2, bh6)) | 0;
2163    lo = (lo + Math.imul(al1, bl7)) | 0;
2164    mid = (mid + Math.imul(al1, bh7)) | 0;
2165    mid = (mid + Math.imul(ah1, bl7)) | 0;
2166    hi = (hi + Math.imul(ah1, bh7)) | 0;
2167    lo = (lo + Math.imul(al0, bl8)) | 0;
2168    mid = (mid + Math.imul(al0, bh8)) | 0;
2169    mid = (mid + Math.imul(ah0, bl8)) | 0;
2170    hi = (hi + Math.imul(ah0, bh8)) | 0;
2171    var w8 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2172    c = (((hi + (mid >>> 13)) | 0) + (w8 >>> 26)) | 0;
2173    w8 &= 0x3ffffff;
2174    /* k = 9 */
2175    lo = Math.imul(al9, bl0);
2176    mid = Math.imul(al9, bh0);
2177    mid = (mid + Math.imul(ah9, bl0)) | 0;
2178    hi = Math.imul(ah9, bh0);
2179    lo = (lo + Math.imul(al8, bl1)) | 0;
2180    mid = (mid + Math.imul(al8, bh1)) | 0;
2181    mid = (mid + Math.imul(ah8, bl1)) | 0;
2182    hi = (hi + Math.imul(ah8, bh1)) | 0;
2183    lo = (lo + Math.imul(al7, bl2)) | 0;
2184    mid = (mid + Math.imul(al7, bh2)) | 0;
2185    mid = (mid + Math.imul(ah7, bl2)) | 0;
2186    hi = (hi + Math.imul(ah7, bh2)) | 0;
2187    lo = (lo + Math.imul(al6, bl3)) | 0;
2188    mid = (mid + Math.imul(al6, bh3)) | 0;
2189    mid = (mid + Math.imul(ah6, bl3)) | 0;
2190    hi = (hi + Math.imul(ah6, bh3)) | 0;
2191    lo = (lo + Math.imul(al5, bl4)) | 0;
2192    mid = (mid + Math.imul(al5, bh4)) | 0;
2193    mid = (mid + Math.imul(ah5, bl4)) | 0;
2194    hi = (hi + Math.imul(ah5, bh4)) | 0;
2195    lo = (lo + Math.imul(al4, bl5)) | 0;
2196    mid = (mid + Math.imul(al4, bh5)) | 0;
2197    mid = (mid + Math.imul(ah4, bl5)) | 0;
2198    hi = (hi + Math.imul(ah4, bh5)) | 0;
2199    lo = (lo + Math.imul(al3, bl6)) | 0;
2200    mid = (mid + Math.imul(al3, bh6)) | 0;
2201    mid = (mid + Math.imul(ah3, bl6)) | 0;
2202    hi = (hi + Math.imul(ah3, bh6)) | 0;
2203    lo = (lo + Math.imul(al2, bl7)) | 0;
2204    mid = (mid + Math.imul(al2, bh7)) | 0;
2205    mid = (mid + Math.imul(ah2, bl7)) | 0;
2206    hi = (hi + Math.imul(ah2, bh7)) | 0;
2207    lo = (lo + Math.imul(al1, bl8)) | 0;
2208    mid = (mid + Math.imul(al1, bh8)) | 0;
2209    mid = (mid + Math.imul(ah1, bl8)) | 0;
2210    hi = (hi + Math.imul(ah1, bh8)) | 0;
2211    lo = (lo + Math.imul(al0, bl9)) | 0;
2212    mid = (mid + Math.imul(al0, bh9)) | 0;
2213    mid = (mid + Math.imul(ah0, bl9)) | 0;
2214    hi = (hi + Math.imul(ah0, bh9)) | 0;
2215    var w9 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2216    c = (((hi + (mid >>> 13)) | 0) + (w9 >>> 26)) | 0;
2217    w9 &= 0x3ffffff;
2218    /* k = 10 */
2219    lo = Math.imul(al9, bl1);
2220    mid = Math.imul(al9, bh1);
2221    mid = (mid + Math.imul(ah9, bl1)) | 0;
2222    hi = Math.imul(ah9, bh1);
2223    lo = (lo + Math.imul(al8, bl2)) | 0;
2224    mid = (mid + Math.imul(al8, bh2)) | 0;
2225    mid = (mid + Math.imul(ah8, bl2)) | 0;
2226    hi = (hi + Math.imul(ah8, bh2)) | 0;
2227    lo = (lo + Math.imul(al7, bl3)) | 0;
2228    mid = (mid + Math.imul(al7, bh3)) | 0;
2229    mid = (mid + Math.imul(ah7, bl3)) | 0;
2230    hi = (hi + Math.imul(ah7, bh3)) | 0;
2231    lo = (lo + Math.imul(al6, bl4)) | 0;
2232    mid = (mid + Math.imul(al6, bh4)) | 0;
2233    mid = (mid + Math.imul(ah6, bl4)) | 0;
2234    hi = (hi + Math.imul(ah6, bh4)) | 0;
2235    lo = (lo + Math.imul(al5, bl5)) | 0;
2236    mid = (mid + Math.imul(al5, bh5)) | 0;
2237    mid = (mid + Math.imul(ah5, bl5)) | 0;
2238    hi = (hi + Math.imul(ah5, bh5)) | 0;
2239    lo = (lo + Math.imul(al4, bl6)) | 0;
2240    mid = (mid + Math.imul(al4, bh6)) | 0;
2241    mid = (mid + Math.imul(ah4, bl6)) | 0;
2242    hi = (hi + Math.imul(ah4, bh6)) | 0;
2243    lo = (lo + Math.imul(al3, bl7)) | 0;
2244    mid = (mid + Math.imul(al3, bh7)) | 0;
2245    mid = (mid + Math.imul(ah3, bl7)) | 0;
2246    hi = (hi + Math.imul(ah3, bh7)) | 0;
2247    lo = (lo + Math.imul(al2, bl8)) | 0;
2248    mid = (mid + Math.imul(al2, bh8)) | 0;
2249    mid = (mid + Math.imul(ah2, bl8)) | 0;
2250    hi = (hi + Math.imul(ah2, bh8)) | 0;
2251    lo = (lo + Math.imul(al1, bl9)) | 0;
2252    mid = (mid + Math.imul(al1, bh9)) | 0;
2253    mid = (mid + Math.imul(ah1, bl9)) | 0;
2254    hi = (hi + Math.imul(ah1, bh9)) | 0;
2255    var w10 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2256    c = (((hi + (mid >>> 13)) | 0) + (w10 >>> 26)) | 0;
2257    w10 &= 0x3ffffff;
2258    /* k = 11 */
2259    lo = Math.imul(al9, bl2);
2260    mid = Math.imul(al9, bh2);
2261    mid = (mid + Math.imul(ah9, bl2)) | 0;
2262    hi = Math.imul(ah9, bh2);
2263    lo = (lo + Math.imul(al8, bl3)) | 0;
2264    mid = (mid + Math.imul(al8, bh3)) | 0;
2265    mid = (mid + Math.imul(ah8, bl3)) | 0;
2266    hi = (hi + Math.imul(ah8, bh3)) | 0;
2267    lo = (lo + Math.imul(al7, bl4)) | 0;
2268    mid = (mid + Math.imul(al7, bh4)) | 0;
2269    mid = (mid + Math.imul(ah7, bl4)) | 0;
2270    hi = (hi + Math.imul(ah7, bh4)) | 0;
2271    lo = (lo + Math.imul(al6, bl5)) | 0;
2272    mid = (mid + Math.imul(al6, bh5)) | 0;
2273    mid = (mid + Math.imul(ah6, bl5)) | 0;
2274    hi = (hi + Math.imul(ah6, bh5)) | 0;
2275    lo = (lo + Math.imul(al5, bl6)) | 0;
2276    mid = (mid + Math.imul(al5, bh6)) | 0;
2277    mid = (mid + Math.imul(ah5, bl6)) | 0;
2278    hi = (hi + Math.imul(ah5, bh6)) | 0;
2279    lo = (lo + Math.imul(al4, bl7)) | 0;
2280    mid = (mid + Math.imul(al4, bh7)) | 0;
2281    mid = (mid + Math.imul(ah4, bl7)) | 0;
2282    hi = (hi + Math.imul(ah4, bh7)) | 0;
2283    lo = (lo + Math.imul(al3, bl8)) | 0;
2284    mid = (mid + Math.imul(al3, bh8)) | 0;
2285    mid = (mid + Math.imul(ah3, bl8)) | 0;
2286    hi = (hi + Math.imul(ah3, bh8)) | 0;
2287    lo = (lo + Math.imul(al2, bl9)) | 0;
2288    mid = (mid + Math.imul(al2, bh9)) | 0;
2289    mid = (mid + Math.imul(ah2, bl9)) | 0;
2290    hi = (hi + Math.imul(ah2, bh9)) | 0;
2291    var w11 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2292    c = (((hi + (mid >>> 13)) | 0) + (w11 >>> 26)) | 0;
2293    w11 &= 0x3ffffff;
2294    /* k = 12 */
2295    lo = Math.imul(al9, bl3);
2296    mid = Math.imul(al9, bh3);
2297    mid = (mid + Math.imul(ah9, bl3)) | 0;
2298    hi = Math.imul(ah9, bh3);
2299    lo = (lo + Math.imul(al8, bl4)) | 0;
2300    mid = (mid + Math.imul(al8, bh4)) | 0;
2301    mid = (mid + Math.imul(ah8, bl4)) | 0;
2302    hi = (hi + Math.imul(ah8, bh4)) | 0;
2303    lo = (lo + Math.imul(al7, bl5)) | 0;
2304    mid = (mid + Math.imul(al7, bh5)) | 0;
2305    mid = (mid + Math.imul(ah7, bl5)) | 0;
2306    hi = (hi + Math.imul(ah7, bh5)) | 0;
2307    lo = (lo + Math.imul(al6, bl6)) | 0;
2308    mid = (mid + Math.imul(al6, bh6)) | 0;
2309    mid = (mid + Math.imul(ah6, bl6)) | 0;
2310    hi = (hi + Math.imul(ah6, bh6)) | 0;
2311    lo = (lo + Math.imul(al5, bl7)) | 0;
2312    mid = (mid + Math.imul(al5, bh7)) | 0;
2313    mid = (mid + Math.imul(ah5, bl7)) | 0;
2314    hi = (hi + Math.imul(ah5, bh7)) | 0;
2315    lo = (lo + Math.imul(al4, bl8)) | 0;
2316    mid = (mid + Math.imul(al4, bh8)) | 0;
2317    mid = (mid + Math.imul(ah4, bl8)) | 0;
2318    hi = (hi + Math.imul(ah4, bh8)) | 0;
2319    lo = (lo + Math.imul(al3, bl9)) | 0;
2320    mid = (mid + Math.imul(al3, bh9)) | 0;
2321    mid = (mid + Math.imul(ah3, bl9)) | 0;
2322    hi = (hi + Math.imul(ah3, bh9)) | 0;
2323    var w12 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2324    c = (((hi + (mid >>> 13)) | 0) + (w12 >>> 26)) | 0;
2325    w12 &= 0x3ffffff;
2326    /* k = 13 */
2327    lo = Math.imul(al9, bl4);
2328    mid = Math.imul(al9, bh4);
2329    mid = (mid + Math.imul(ah9, bl4)) | 0;
2330    hi = Math.imul(ah9, bh4);
2331    lo = (lo + Math.imul(al8, bl5)) | 0;
2332    mid = (mid + Math.imul(al8, bh5)) | 0;
2333    mid = (mid + Math.imul(ah8, bl5)) | 0;
2334    hi = (hi + Math.imul(ah8, bh5)) | 0;
2335    lo = (lo + Math.imul(al7, bl6)) | 0;
2336    mid = (mid + Math.imul(al7, bh6)) | 0;
2337    mid = (mid + Math.imul(ah7, bl6)) | 0;
2338    hi = (hi + Math.imul(ah7, bh6)) | 0;
2339    lo = (lo + Math.imul(al6, bl7)) | 0;
2340    mid = (mid + Math.imul(al6, bh7)) | 0;
2341    mid = (mid + Math.imul(ah6, bl7)) | 0;
2342    hi = (hi + Math.imul(ah6, bh7)) | 0;
2343    lo = (lo + Math.imul(al5, bl8)) | 0;
2344    mid = (mid + Math.imul(al5, bh8)) | 0;
2345    mid = (mid + Math.imul(ah5, bl8)) | 0;
2346    hi = (hi + Math.imul(ah5, bh8)) | 0;
2347    lo = (lo + Math.imul(al4, bl9)) | 0;
2348    mid = (mid + Math.imul(al4, bh9)) | 0;
2349    mid = (mid + Math.imul(ah4, bl9)) | 0;
2350    hi = (hi + Math.imul(ah4, bh9)) | 0;
2351    var w13 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2352    c = (((hi + (mid >>> 13)) | 0) + (w13 >>> 26)) | 0;
2353    w13 &= 0x3ffffff;
2354    /* k = 14 */
2355    lo = Math.imul(al9, bl5);
2356    mid = Math.imul(al9, bh5);
2357    mid = (mid + Math.imul(ah9, bl5)) | 0;
2358    hi = Math.imul(ah9, bh5);
2359    lo = (lo + Math.imul(al8, bl6)) | 0;
2360    mid = (mid + Math.imul(al8, bh6)) | 0;
2361    mid = (mid + Math.imul(ah8, bl6)) | 0;
2362    hi = (hi + Math.imul(ah8, bh6)) | 0;
2363    lo = (lo + Math.imul(al7, bl7)) | 0;
2364    mid = (mid + Math.imul(al7, bh7)) | 0;
2365    mid = (mid + Math.imul(ah7, bl7)) | 0;
2366    hi = (hi + Math.imul(ah7, bh7)) | 0;
2367    lo = (lo + Math.imul(al6, bl8)) | 0;
2368    mid = (mid + Math.imul(al6, bh8)) | 0;
2369    mid = (mid + Math.imul(ah6, bl8)) | 0;
2370    hi = (hi + Math.imul(ah6, bh8)) | 0;
2371    lo = (lo + Math.imul(al5, bl9)) | 0;
2372    mid = (mid + Math.imul(al5, bh9)) | 0;
2373    mid = (mid + Math.imul(ah5, bl9)) | 0;
2374    hi = (hi + Math.imul(ah5, bh9)) | 0;
2375    var w14 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2376    c = (((hi + (mid >>> 13)) | 0) + (w14 >>> 26)) | 0;
2377    w14 &= 0x3ffffff;
2378    /* k = 15 */
2379    lo = Math.imul(al9, bl6);
2380    mid = Math.imul(al9, bh6);
2381    mid = (mid + Math.imul(ah9, bl6)) | 0;
2382    hi = Math.imul(ah9, bh6);
2383    lo = (lo + Math.imul(al8, bl7)) | 0;
2384    mid = (mid + Math.imul(al8, bh7)) | 0;
2385    mid = (mid + Math.imul(ah8, bl7)) | 0;
2386    hi = (hi + Math.imul(ah8, bh7)) | 0;
2387    lo = (lo + Math.imul(al7, bl8)) | 0;
2388    mid = (mid + Math.imul(al7, bh8)) | 0;
2389    mid = (mid + Math.imul(ah7, bl8)) | 0;
2390    hi = (hi + Math.imul(ah7, bh8)) | 0;
2391    lo = (lo + Math.imul(al6, bl9)) | 0;
2392    mid = (mid + Math.imul(al6, bh9)) | 0;
2393    mid = (mid + Math.imul(ah6, bl9)) | 0;
2394    hi = (hi + Math.imul(ah6, bh9)) | 0;
2395    var w15 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2396    c = (((hi + (mid >>> 13)) | 0) + (w15 >>> 26)) | 0;
2397    w15 &= 0x3ffffff;
2398    /* k = 16 */
2399    lo = Math.imul(al9, bl7);
2400    mid = Math.imul(al9, bh7);
2401    mid = (mid + Math.imul(ah9, bl7)) | 0;
2402    hi = Math.imul(ah9, bh7);
2403    lo = (lo + Math.imul(al8, bl8)) | 0;
2404    mid = (mid + Math.imul(al8, bh8)) | 0;
2405    mid = (mid + Math.imul(ah8, bl8)) | 0;
2406    hi = (hi + Math.imul(ah8, bh8)) | 0;
2407    lo = (lo + Math.imul(al7, bl9)) | 0;
2408    mid = (mid + Math.imul(al7, bh9)) | 0;
2409    mid = (mid + Math.imul(ah7, bl9)) | 0;
2410    hi = (hi + Math.imul(ah7, bh9)) | 0;
2411    var w16 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2412    c = (((hi + (mid >>> 13)) | 0) + (w16 >>> 26)) | 0;
2413    w16 &= 0x3ffffff;
2414    /* k = 17 */
2415    lo = Math.imul(al9, bl8);
2416    mid = Math.imul(al9, bh8);
2417    mid = (mid + Math.imul(ah9, bl8)) | 0;
2418    hi = Math.imul(ah9, bh8);
2419    lo = (lo + Math.imul(al8, bl9)) | 0;
2420    mid = (mid + Math.imul(al8, bh9)) | 0;
2421    mid = (mid + Math.imul(ah8, bl9)) | 0;
2422    hi = (hi + Math.imul(ah8, bh9)) | 0;
2423    var w17 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2424    c = (((hi + (mid >>> 13)) | 0) + (w17 >>> 26)) | 0;
2425    w17 &= 0x3ffffff;
2426    /* k = 18 */
2427    lo = Math.imul(al9, bl9);
2428    mid = Math.imul(al9, bh9);
2429    mid = (mid + Math.imul(ah9, bl9)) | 0;
2430    hi = Math.imul(ah9, bh9);
2431    var w18 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
2432    c = (((hi + (mid >>> 13)) | 0) + (w18 >>> 26)) | 0;
2433    w18 &= 0x3ffffff;
2434    o[0] = w0;
2435    o[1] = w1;
2436    o[2] = w2;
2437    o[3] = w3;
2438    o[4] = w4;
2439    o[5] = w5;
2440    o[6] = w6;
2441    o[7] = w7;
2442    o[8] = w8;
2443    o[9] = w9;
2444    o[10] = w10;
2445    o[11] = w11;
2446    o[12] = w12;
2447    o[13] = w13;
2448    o[14] = w14;
2449    o[15] = w15;
2450    o[16] = w16;
2451    o[17] = w17;
2452    o[18] = w18;
2453    if (c !== 0) {
2454      o[19] = c;
2455      out.length++;
2456    }
2457    return out;
2458  };
2459
2460  // Polyfill comb
2461  if (!Math.imul) {
2462    comb10MulTo = smallMulTo;
2463  }
2464
2465  function bigMulTo (self, num, out) {
2466    out.negative = num.negative ^ self.negative;
2467    out.length = self.length + num.length;
2468
2469    var carry = 0;
2470    var hncarry = 0;
2471    for (var k = 0; k < out.length - 1; k++) {
2472      // Sum all words with the same `i + j = k` and accumulate `ncarry`,
2473      // note that ncarry could be >= 0x3ffffff
2474      var ncarry = hncarry;
2475      hncarry = 0;
2476      var rword = carry & 0x3ffffff;
2477      var maxJ = Math.min(k, num.length - 1);
2478      for (var j = Math.max(0, k - self.length + 1); j <= maxJ; j++) {
2479        var i = k - j;
2480        var a = self.words[i] | 0;
2481        var b = num.words[j] | 0;
2482        var r = a * b;
2483
2484        var lo = r & 0x3ffffff;
2485        ncarry = (ncarry + ((r / 0x4000000) | 0)) | 0;
2486        lo = (lo + rword) | 0;
2487        rword = lo & 0x3ffffff;
2488        ncarry = (ncarry + (lo >>> 26)) | 0;
2489
2490        hncarry += ncarry >>> 26;
2491        ncarry &= 0x3ffffff;
2492      }
2493      out.words[k] = rword;
2494      carry = ncarry;
2495      ncarry = hncarry;
2496    }
2497    if (carry !== 0) {
2498      out.words[k] = carry;
2499    } else {
2500      out.length--;
2501    }
2502
2503    return out.strip();
2504  }
2505
2506  function jumboMulTo (self, num, out) {
2507    var fftm = new FFTM();
2508    return fftm.mulp(self, num, out);
2509  }
2510
2511  BN.prototype.mulTo = function mulTo (num, out) {
2512    var res;
2513    var len = this.length + num.length;
2514    if (this.length === 10 && num.length === 10) {
2515      res = comb10MulTo(this, num, out);
2516    } else if (len < 63) {
2517      res = smallMulTo(this, num, out);
2518    } else if (len < 1024) {
2519      res = bigMulTo(this, num, out);
2520    } else {
2521      res = jumboMulTo(this, num, out);
2522    }
2523
2524    return res;
2525  };
2526
2527  // Cooley-Tukey algorithm for FFT
2528  // slightly revisited to rely on looping instead of recursion
2529
2530  function FFTM (x, y) {
2531    this.x = x;
2532    this.y = y;
2533  }
2534
2535  FFTM.prototype.makeRBT = function makeRBT (N) {
2536    var t = new Array(N);
2537    var l = BN.prototype._countBits(N) - 1;
2538    for (var i = 0; i < N; i++) {
2539      t[i] = this.revBin(i, l, N);
2540    }
2541
2542    return t;
2543  };
2544
2545  // Returns binary-reversed representation of `x`
2546  FFTM.prototype.revBin = function revBin (x, l, N) {
2547    if (x === 0 || x === N - 1) return x;
2548
2549    var rb = 0;
2550    for (var i = 0; i < l; i++) {
2551      rb |= (x & 1) << (l - i - 1);
2552      x >>= 1;
2553    }
2554
2555    return rb;
2556  };
2557
2558  // Performs "tweedling" phase, therefore 'emulating'
2559  // behaviour of the recursive algorithm
2560  FFTM.prototype.permute = function permute (rbt, rws, iws, rtws, itws, N) {
2561    for (var i = 0; i < N; i++) {
2562      rtws[i] = rws[rbt[i]];
2563      itws[i] = iws[rbt[i]];
2564    }
2565  };
2566
2567  FFTM.prototype.transform = function transform (rws, iws, rtws, itws, N, rbt) {
2568    this.permute(rbt, rws, iws, rtws, itws, N);
2569
2570    for (var s = 1; s < N; s <<= 1) {
2571      var l = s << 1;
2572
2573      var rtwdf = Math.cos(2 * Math.PI / l);
2574      var itwdf = Math.sin(2 * Math.PI / l);
2575
2576      for (var p = 0; p < N; p += l) {
2577        var rtwdf_ = rtwdf;
2578        var itwdf_ = itwdf;
2579
2580        for (var j = 0; j < s; j++) {
2581          var re = rtws[p + j];
2582          var ie = itws[p + j];
2583
2584          var ro = rtws[p + j + s];
2585          var io = itws[p + j + s];
2586
2587          var rx = rtwdf_ * ro - itwdf_ * io;
2588
2589          io = rtwdf_ * io + itwdf_ * ro;
2590          ro = rx;
2591
2592          rtws[p + j] = re + ro;
2593          itws[p + j] = ie + io;
2594
2595          rtws[p + j + s] = re - ro;
2596          itws[p + j + s] = ie - io;
2597
2598          /* jshint maxdepth : false */
2599          if (j !== l) {
2600            rx = rtwdf * rtwdf_ - itwdf * itwdf_;
2601
2602            itwdf_ = rtwdf * itwdf_ + itwdf * rtwdf_;
2603            rtwdf_ = rx;
2604          }
2605        }
2606      }
2607    }
2608  };
2609
2610  FFTM.prototype.guessLen13b = function guessLen13b (n, m) {
2611    var N = Math.max(m, n) | 1;
2612    var odd = N & 1;
2613    var i = 0;
2614    for (N = N / 2 | 0; N; N = N >>> 1) {
2615      i++;
2616    }
2617
2618    return 1 << i + 1 + odd;
2619  };
2620
2621  FFTM.prototype.conjugate = function conjugate (rws, iws, N) {
2622    if (N <= 1) return;
2623
2624    for (var i = 0; i < N / 2; i++) {
2625      var t = rws[i];
2626
2627      rws[i] = rws[N - i - 1];
2628      rws[N - i - 1] = t;
2629
2630      t = iws[i];
2631
2632      iws[i] = -iws[N - i - 1];
2633      iws[N - i - 1] = -t;
2634    }
2635  };
2636
2637  FFTM.prototype.normalize13b = function normalize13b (ws, N) {
2638    var carry = 0;
2639    for (var i = 0; i < N / 2; i++) {
2640      var w = Math.round(ws[2 * i + 1] / N) * 0x2000 +
2641        Math.round(ws[2 * i] / N) +
2642        carry;
2643
2644      ws[i] = w & 0x3ffffff;
2645
2646      if (w < 0x4000000) {
2647        carry = 0;
2648      } else {
2649        carry = w / 0x4000000 | 0;
2650      }
2651    }
2652
2653    return ws;
2654  };
2655
2656  FFTM.prototype.convert13b = function convert13b (ws, len, rws, N) {
2657    var carry = 0;
2658    for (var i = 0; i < len; i++) {
2659      carry = carry + (ws[i] | 0);
2660
2661      rws[2 * i] = carry & 0x1fff; carry = carry >>> 13;
2662      rws[2 * i + 1] = carry & 0x1fff; carry = carry >>> 13;
2663    }
2664
2665    // Pad with zeroes
2666    for (i = 2 * len; i < N; ++i) {
2667      rws[i] = 0;
2668    }
2669
2670    assert(carry === 0);
2671    assert((carry & ~0x1fff) === 0);
2672  };
2673
2674  FFTM.prototype.stub = function stub (N) {
2675    var ph = new Array(N);
2676    for (var i = 0; i < N; i++) {
2677      ph[i] = 0;
2678    }
2679
2680    return ph;
2681  };
2682
2683  FFTM.prototype.mulp = function mulp (x, y, out) {
2684    var N = 2 * this.guessLen13b(x.length, y.length);
2685
2686    var rbt = this.makeRBT(N);
2687
2688    var _ = this.stub(N);
2689
2690    var rws = new Array(N);
2691    var rwst = new Array(N);
2692    var iwst = new Array(N);
2693
2694    var nrws = new Array(N);
2695    var nrwst = new Array(N);
2696    var niwst = new Array(N);
2697
2698    var rmws = out.words;
2699    rmws.length = N;
2700
2701    this.convert13b(x.words, x.length, rws, N);
2702    this.convert13b(y.words, y.length, nrws, N);
2703
2704    this.transform(rws, _, rwst, iwst, N, rbt);
2705    this.transform(nrws, _, nrwst, niwst, N, rbt);
2706
2707    for (var i = 0; i < N; i++) {
2708      var rx = rwst[i] * nrwst[i] - iwst[i] * niwst[i];
2709      iwst[i] = rwst[i] * niwst[i] + iwst[i] * nrwst[i];
2710      rwst[i] = rx;
2711    }
2712
2713    this.conjugate(rwst, iwst, N);
2714    this.transform(rwst, iwst, rmws, _, N, rbt);
2715    this.conjugate(rmws, _, N);
2716    this.normalize13b(rmws, N);
2717
2718    out.negative = x.negative ^ y.negative;
2719    out.length = x.length + y.length;
2720    return out.strip();
2721  };
2722
2723  // Multiply `this` by `num`
2724  BN.prototype.mul = function mul (num) {
2725    var out = new BN(null);
2726    out.words = new Array(this.length + num.length);
2727    return this.mulTo(num, out);
2728  };
2729
2730  // Multiply employing FFT
2731  BN.prototype.mulf = function mulf (num) {
2732    var out = new BN(null);
2733    out.words = new Array(this.length + num.length);
2734    return jumboMulTo(this, num, out);
2735  };
2736
2737  // In-place Multiplication
2738  BN.prototype.imul = function imul (num) {
2739    return this.clone().mulTo(num, this);
2740  };
2741
2742  BN.prototype.imuln = function imuln (num) {
2743    assert(typeof num === 'number');
2744    assert(num < 0x4000000);
2745
2746    // Carry
2747    var carry = 0;
2748    for (var i = 0; i < this.length; i++) {
2749      var w = (this.words[i] | 0) * num;
2750      var lo = (w & 0x3ffffff) + (carry & 0x3ffffff);
2751      carry >>= 26;
2752      carry += (w / 0x4000000) | 0;
2753      // NOTE: lo is 27bit maximum
2754      carry += lo >>> 26;
2755      this.words[i] = lo & 0x3ffffff;
2756    }
2757
2758    if (carry !== 0) {
2759      this.words[i] = carry;
2760      this.length++;
2761    }
2762
2763    return this;
2764  };
2765
2766  BN.prototype.muln = function muln (num) {
2767    return this.clone().imuln(num);
2768  };
2769
2770  // `this` * `this`
2771  BN.prototype.sqr = function sqr () {
2772    return this.mul(this);
2773  };
2774
2775  // `this` * `this` in-place
2776  BN.prototype.isqr = function isqr () {
2777    return this.imul(this.clone());
2778  };
2779
2780  // Math.pow(`this`, `num`)
2781  BN.prototype.pow = function pow (num) {
2782    var w = toBitArray(num);
2783    if (w.length === 0) return new BN(1);
2784
2785    // Skip leading zeroes
2786    var res = this;
2787    for (var i = 0; i < w.length; i++, res = res.sqr()) {
2788      if (w[i] !== 0) break;
2789    }
2790
2791    if (++i < w.length) {
2792      for (var q = res.sqr(); i < w.length; i++, q = q.sqr()) {
2793        if (w[i] === 0) continue;
2794
2795        res = res.mul(q);
2796      }
2797    }
2798
2799    return res;
2800  };
2801
2802  // Shift-left in-place
2803  BN.prototype.iushln = function iushln (bits) {
2804    assert(typeof bits === 'number' && bits >= 0);
2805    var r = bits % 26;
2806    var s = (bits - r) / 26;
2807    var carryMask = (0x3ffffff >>> (26 - r)) << (26 - r);
2808    var i;
2809
2810    if (r !== 0) {
2811      var carry = 0;
2812
2813      for (i = 0; i < this.length; i++) {
2814        var newCarry = this.words[i] & carryMask;
2815        var c = ((this.words[i] | 0) - newCarry) << r;
2816        this.words[i] = c | carry;
2817        carry = newCarry >>> (26 - r);
2818      }
2819
2820      if (carry) {
2821        this.words[i] = carry;
2822        this.length++;
2823      }
2824    }
2825
2826    if (s !== 0) {
2827      for (i = this.length - 1; i >= 0; i--) {
2828        this.words[i + s] = this.words[i];
2829      }
2830
2831      for (i = 0; i < s; i++) {
2832        this.words[i] = 0;
2833      }
2834
2835      this.length += s;
2836    }
2837
2838    return this.strip();
2839  };
2840
2841  BN.prototype.ishln = function ishln (bits) {
2842    // TODO(indutny): implement me
2843    assert(this.negative === 0);
2844    return this.iushln(bits);
2845  };
2846
2847  // Shift-right in-place
2848  // NOTE: `hint` is a lowest bit before trailing zeroes
2849  // NOTE: if `extended` is present - it will be filled with destroyed bits
2850  BN.prototype.iushrn = function iushrn (bits, hint, extended) {
2851    assert(typeof bits === 'number' && bits >= 0);
2852    var h;
2853    if (hint) {
2854      h = (hint - (hint % 26)) / 26;
2855    } else {
2856      h = 0;
2857    }
2858
2859    var r = bits % 26;
2860    var s = Math.min((bits - r) / 26, this.length);
2861    var mask = 0x3ffffff ^ ((0x3ffffff >>> r) << r);
2862    var maskedWords = extended;
2863
2864    h -= s;
2865    h = Math.max(0, h);
2866
2867    // Extended mode, copy masked part
2868    if (maskedWords) {
2869      for (var i = 0; i < s; i++) {
2870        maskedWords.words[i] = this.words[i];
2871      }
2872      maskedWords.length = s;
2873    }
2874
2875    if (s === 0) {
2876      // No-op, we should not move anything at all
2877    } else if (this.length > s) {
2878      this.length -= s;
2879      for (i = 0; i < this.length; i++) {
2880        this.words[i] = this.words[i + s];
2881      }
2882    } else {
2883      this.words[0] = 0;
2884      this.length = 1;
2885    }
2886
2887    var carry = 0;
2888    for (i = this.length - 1; i >= 0 && (carry !== 0 || i >= h); i--) {
2889      var word = this.words[i] | 0;
2890      this.words[i] = (carry << (26 - r)) | (word >>> r);
2891      carry = word & mask;
2892    }
2893
2894    // Push carried bits as a mask
2895    if (maskedWords && carry !== 0) {
2896      maskedWords.words[maskedWords.length++] = carry;
2897    }
2898
2899    if (this.length === 0) {
2900      this.words[0] = 0;
2901      this.length = 1;
2902    }
2903
2904    return this.strip();
2905  };
2906
2907  BN.prototype.ishrn = function ishrn (bits, hint, extended) {
2908    // TODO(indutny): implement me
2909    assert(this.negative === 0);
2910    return this.iushrn(bits, hint, extended);
2911  };
2912
2913  // Shift-left
2914  BN.prototype.shln = function shln (bits) {
2915    return this.clone().ishln(bits);
2916  };
2917
2918  BN.prototype.ushln = function ushln (bits) {
2919    return this.clone().iushln(bits);
2920  };
2921
2922  // Shift-right
2923  BN.prototype.shrn = function shrn (bits) {
2924    return this.clone().ishrn(bits);
2925  };
2926
2927  BN.prototype.ushrn = function ushrn (bits) {
2928    return this.clone().iushrn(bits);
2929  };
2930
2931  // Test if n bit is set
2932  BN.prototype.testn = function testn (bit) {
2933    assert(typeof bit === 'number' && bit >= 0);
2934    var r = bit % 26;
2935    var s = (bit - r) / 26;
2936    var q = 1 << r;
2937
2938    // Fast case: bit is much higher than all existing words
2939    if (this.length <= s) return false;
2940
2941    // Check bit and return
2942    var w = this.words[s];
2943
2944    return !!(w & q);
2945  };
2946
2947  // Return only lowers bits of number (in-place)
2948  BN.prototype.imaskn = function imaskn (bits) {
2949    assert(typeof bits === 'number' && bits >= 0);
2950    var r = bits % 26;
2951    var s = (bits - r) / 26;
2952
2953    assert(this.negative === 0, 'imaskn works only with positive numbers');
2954
2955    if (this.length <= s) {
2956      return this;
2957    }
2958
2959    if (r !== 0) {
2960      s++;
2961    }
2962    this.length = Math.min(s, this.length);
2963
2964    if (r !== 0) {
2965      var mask = 0x3ffffff ^ ((0x3ffffff >>> r) << r);
2966      this.words[this.length - 1] &= mask;
2967    }
2968
2969    return this.strip();
2970  };
2971
2972  // Return only lowers bits of number
2973  BN.prototype.maskn = function maskn (bits) {
2974    return this.clone().imaskn(bits);
2975  };
2976
2977  // Add plain number `num` to `this`
2978  BN.prototype.iaddn = function iaddn (num) {
2979    assert(typeof num === 'number');
2980    assert(num < 0x4000000);
2981    if (num < 0) return this.isubn(-num);
2982
2983    // Possible sign change
2984    if (this.negative !== 0) {
2985      if (this.length === 1 && (this.words[0] | 0) < num) {
2986        this.words[0] = num - (this.words[0] | 0);
2987        this.negative = 0;
2988        return this;
2989      }
2990
2991      this.negative = 0;
2992      this.isubn(num);
2993      this.negative = 1;
2994      return this;
2995    }
2996
2997    // Add without checks
2998    return this._iaddn(num);
2999  };
3000
3001  BN.prototype._iaddn = function _iaddn (num) {
3002    this.words[0] += num;
3003
3004    // Carry
3005    for (var i = 0; i < this.length && this.words[i] >= 0x4000000; i++) {
3006      this.words[i] -= 0x4000000;
3007      if (i === this.length - 1) {
3008        this.words[i + 1] = 1;
3009      } else {
3010        this.words[i + 1]++;
3011      }
3012    }
3013    this.length = Math.max(this.length, i + 1);
3014
3015    return this;
3016  };
3017
3018  // Subtract plain number `num` from `this`
3019  BN.prototype.isubn = function isubn (num) {
3020    assert(typeof num === 'number');
3021    assert(num < 0x4000000);
3022    if (num < 0) return this.iaddn(-num);
3023
3024    if (this.negative !== 0) {
3025      this.negative = 0;
3026      this.iaddn(num);
3027      this.negative = 1;
3028      return this;
3029    }
3030
3031    this.words[0] -= num;
3032
3033    if (this.length === 1 && this.words[0] < 0) {
3034      this.words[0] = -this.words[0];
3035      this.negative = 1;
3036    } else {
3037      // Carry
3038      for (var i = 0; i < this.length && this.words[i] < 0; i++) {
3039        this.words[i] += 0x4000000;
3040        this.words[i + 1] -= 1;
3041      }
3042    }
3043
3044    return this.strip();
3045  };
3046
3047  BN.prototype.addn = function addn (num) {
3048    return this.clone().iaddn(num);
3049  };
3050
3051  BN.prototype.subn = function subn (num) {
3052    return this.clone().isubn(num);
3053  };
3054
3055  BN.prototype.iabs = function iabs () {
3056    this.negative = 0;
3057
3058    return this;
3059  };
3060
3061  BN.prototype.abs = function abs () {
3062    return this.clone().iabs();
3063  };
3064
3065  BN.prototype._ishlnsubmul = function _ishlnsubmul (num, mul, shift) {
3066    var len = num.length + shift;
3067    var i;
3068
3069    this._expand(len);
3070
3071    var w;
3072    var carry = 0;
3073    for (i = 0; i < num.length; i++) {
3074      w = (this.words[i + shift] | 0) + carry;
3075      var right = (num.words[i] | 0) * mul;
3076      w -= right & 0x3ffffff;
3077      carry = (w >> 26) - ((right / 0x4000000) | 0);
3078      this.words[i + shift] = w & 0x3ffffff;
3079    }
3080    for (; i < this.length - shift; i++) {
3081      w = (this.words[i + shift] | 0) + carry;
3082      carry = w >> 26;
3083      this.words[i + shift] = w & 0x3ffffff;
3084    }
3085
3086    if (carry === 0) return this.strip();
3087
3088    // Subtraction overflow
3089    assert(carry === -1);
3090    carry = 0;
3091    for (i = 0; i < this.length; i++) {
3092      w = -(this.words[i] | 0) + carry;
3093      carry = w >> 26;
3094      this.words[i] = w & 0x3ffffff;
3095    }
3096    this.negative = 1;
3097
3098    return this.strip();
3099  };
3100
3101  BN.prototype._wordDiv = function _wordDiv (num, mode) {
3102    var shift = this.length - num.length;
3103
3104    var a = this.clone();
3105    var b = num;
3106
3107    // Normalize
3108    var bhi = b.words[b.length - 1] | 0;
3109    var bhiBits = this._countBits(bhi);
3110    shift = 26 - bhiBits;
3111    if (shift !== 0) {
3112      b = b.ushln(shift);
3113      a.iushln(shift);
3114      bhi = b.words[b.length - 1] | 0;
3115    }
3116
3117    // Initialize quotient
3118    var m = a.length - b.length;
3119    var q;
3120
3121    if (mode !== 'mod') {
3122      q = new BN(null);
3123      q.length = m + 1;
3124      q.words = new Array(q.length);
3125      for (var i = 0; i < q.length; i++) {
3126        q.words[i] = 0;
3127      }
3128    }
3129
3130    var diff = a.clone()._ishlnsubmul(b, 1, m);
3131    if (diff.negative === 0) {
3132      a = diff;
3133      if (q) {
3134        q.words[m] = 1;
3135      }
3136    }
3137
3138    for (var j = m - 1; j >= 0; j--) {
3139      var qj = (a.words[b.length + j] | 0) * 0x4000000 +
3140        (a.words[b.length + j - 1] | 0);
3141
3142      // NOTE: (qj / bhi) is (0x3ffffff * 0x4000000 + 0x3ffffff) / 0x2000000 max
3143      // (0x7ffffff)
3144      qj = Math.min((qj / bhi) | 0, 0x3ffffff);
3145
3146      a._ishlnsubmul(b, qj, j);
3147      while (a.negative !== 0) {
3148        qj--;
3149        a.negative = 0;
3150        a._ishlnsubmul(b, 1, j);
3151        if (!a.isZero()) {
3152          a.negative ^= 1;
3153        }
3154      }
3155      if (q) {
3156        q.words[j] = qj;
3157      }
3158    }
3159    if (q) {
3160      q.strip();
3161    }
3162    a.strip();
3163
3164    // Denormalize
3165    if (mode !== 'div' && shift !== 0) {
3166      a.iushrn(shift);
3167    }
3168
3169    return {
3170      div: q || null,
3171      mod: a
3172    };
3173  };
3174
3175  // NOTE: 1) `mode` can be set to `mod` to request mod only,
3176  //       to `div` to request div only, or be absent to
3177  //       request both div & mod
3178  //       2) `positive` is true if unsigned mod is requested
3179  BN.prototype.divmod = function divmod (num, mode, positive) {
3180    assert(!num.isZero());
3181
3182    if (this.isZero()) {
3183      return {
3184        div: new BN(0),
3185        mod: new BN(0)
3186      };
3187    }
3188
3189    var div, mod, res;
3190    if (this.negative !== 0 && num.negative === 0) {
3191      res = this.neg().divmod(num, mode);
3192
3193      if (mode !== 'mod') {
3194        div = res.div.neg();
3195      }
3196
3197      if (mode !== 'div') {
3198        mod = res.mod.neg();
3199        if (positive && mod.negative !== 0) {
3200          mod.iadd(num);
3201        }
3202      }
3203
3204      return {
3205        div: div,
3206        mod: mod
3207      };
3208    }
3209
3210    if (this.negative === 0 && num.negative !== 0) {
3211      res = this.divmod(num.neg(), mode);
3212
3213      if (mode !== 'mod') {
3214        div = res.div.neg();
3215      }
3216
3217      return {
3218        div: div,
3219        mod: res.mod
3220      };
3221    }
3222
3223    if ((this.negative & num.negative) !== 0) {
3224      res = this.neg().divmod(num.neg(), mode);
3225
3226      if (mode !== 'div') {
3227        mod = res.mod.neg();
3228        if (positive && mod.negative !== 0) {
3229          mod.isub(num);
3230        }
3231      }
3232
3233      return {
3234        div: res.div,
3235        mod: mod
3236      };
3237    }
3238
3239    // Both numbers are positive at this point
3240
3241    // Strip both numbers to approximate shift value
3242    if (num.length > this.length || this.cmp(num) < 0) {
3243      return {
3244        div: new BN(0),
3245        mod: this
3246      };
3247    }
3248
3249    // Very short reduction
3250    if (num.length === 1) {
3251      if (mode === 'div') {
3252        return {
3253          div: this.divn(num.words[0]),
3254          mod: null
3255        };
3256      }
3257
3258      if (mode === 'mod') {
3259        return {
3260          div: null,
3261          mod: new BN(this.modn(num.words[0]))
3262        };
3263      }
3264
3265      return {
3266        div: this.divn(num.words[0]),
3267        mod: new BN(this.modn(num.words[0]))
3268      };
3269    }
3270
3271    return this._wordDiv(num, mode);
3272  };
3273
3274  // Find `this` / `num`
3275  BN.prototype.div = function div (num) {
3276    return this.divmod(num, 'div', false).div;
3277  };
3278
3279  // Find `this` % `num`
3280  BN.prototype.mod = function mod (num) {
3281    return this.divmod(num, 'mod', false).mod;
3282  };
3283
3284  BN.prototype.umod = function umod (num) {
3285    return this.divmod(num, 'mod', true).mod;
3286  };
3287
3288  // Find Round(`this` / `num`)
3289  BN.prototype.divRound = function divRound (num) {
3290    var dm = this.divmod(num);
3291
3292    // Fast case - exact division
3293    if (dm.mod.isZero()) return dm.div;
3294
3295    var mod = dm.div.negative !== 0 ? dm.mod.isub(num) : dm.mod;
3296
3297    var half = num.ushrn(1);
3298    var r2 = num.andln(1);
3299    var cmp = mod.cmp(half);
3300
3301    // Round down
3302    if (cmp < 0 || r2 === 1 && cmp === 0) return dm.div;
3303
3304    // Round up
3305    return dm.div.negative !== 0 ? dm.div.isubn(1) : dm.div.iaddn(1);
3306  };
3307
3308  BN.prototype.modn = function modn (num) {
3309    assert(num <= 0x3ffffff);
3310    var p = (1 << 26) % num;
3311
3312    var acc = 0;
3313    for (var i = this.length - 1; i >= 0; i--) {
3314      acc = (p * acc + (this.words[i] | 0)) % num;
3315    }
3316
3317    return acc;
3318  };
3319
3320  // In-place division by number
3321  BN.prototype.idivn = function idivn (num) {
3322    assert(num <= 0x3ffffff);
3323
3324    var carry = 0;
3325    for (var i = this.length - 1; i >= 0; i--) {
3326      var w = (this.words[i] | 0) + carry * 0x4000000;
3327      this.words[i] = (w / num) | 0;
3328      carry = w % num;
3329    }
3330
3331    return this.strip();
3332  };
3333
3334  BN.prototype.divn = function divn (num) {
3335    return this.clone().idivn(num);
3336  };
3337
3338  BN.prototype.egcd = function egcd (p) {
3339    assert(p.negative === 0);
3340    assert(!p.isZero());
3341
3342    var x = this;
3343    var y = p.clone();
3344
3345    if (x.negative !== 0) {
3346      x = x.umod(p);
3347    } else {
3348      x = x.clone();
3349    }
3350
3351    // A * x + B * y = x
3352    var A = new BN(1);
3353    var B = new BN(0);
3354
3355    // C * x + D * y = y
3356    var C = new BN(0);
3357    var D = new BN(1);
3358
3359    var g = 0;
3360
3361    while (x.isEven() && y.isEven()) {
3362      x.iushrn(1);
3363      y.iushrn(1);
3364      ++g;
3365    }
3366
3367    var yp = y.clone();
3368    var xp = x.clone();
3369
3370    while (!x.isZero()) {
3371      for (var i = 0, im = 1; (x.words[0] & im) === 0 && i < 26; ++i, im <<= 1);
3372      if (i > 0) {
3373        x.iushrn(i);
3374        while (i-- > 0) {
3375          if (A.isOdd() || B.isOdd()) {
3376            A.iadd(yp);
3377            B.isub(xp);
3378          }
3379
3380          A.iushrn(1);
3381          B.iushrn(1);
3382        }
3383      }
3384
3385      for (var j = 0, jm = 1; (y.words[0] & jm) === 0 && j < 26; ++j, jm <<= 1);
3386      if (j > 0) {
3387        y.iushrn(j);
3388        while (j-- > 0) {
3389          if (C.isOdd() || D.isOdd()) {
3390            C.iadd(yp);
3391            D.isub(xp);
3392          }
3393
3394          C.iushrn(1);
3395          D.iushrn(1);
3396        }
3397      }
3398
3399      if (x.cmp(y) >= 0) {
3400        x.isub(y);
3401        A.isub(C);
3402        B.isub(D);
3403      } else {
3404        y.isub(x);
3405        C.isub(A);
3406        D.isub(B);
3407      }
3408    }
3409
3410    return {
3411      a: C,
3412      b: D,
3413      gcd: y.iushln(g)
3414    };
3415  };
3416
3417  // This is reduced incarnation of the binary EEA
3418  // above, designated to invert members of the
3419  // _prime_ fields F(p) at a maximal speed
3420  BN.prototype._invmp = function _invmp (p) {
3421    assert(p.negative === 0);
3422    assert(!p.isZero());
3423
3424    var a = this;
3425    var b = p.clone();
3426
3427    if (a.negative !== 0) {
3428      a = a.umod(p);
3429    } else {
3430      a = a.clone();
3431    }
3432
3433    var x1 = new BN(1);
3434    var x2 = new BN(0);
3435
3436    var delta = b.clone();
3437
3438    while (a.cmpn(1) > 0 && b.cmpn(1) > 0) {
3439      for (var i = 0, im = 1; (a.words[0] & im) === 0 && i < 26; ++i, im <<= 1);
3440      if (i > 0) {
3441        a.iushrn(i);
3442        while (i-- > 0) {
3443          if (x1.isOdd()) {
3444            x1.iadd(delta);
3445          }
3446
3447          x1.iushrn(1);
3448        }
3449      }
3450
3451      for (var j = 0, jm = 1; (b.words[0] & jm) === 0 && j < 26; ++j, jm <<= 1);
3452      if (j > 0) {
3453        b.iushrn(j);
3454        while (j-- > 0) {
3455          if (x2.isOdd()) {
3456            x2.iadd(delta);
3457          }
3458
3459          x2.iushrn(1);
3460        }
3461      }
3462
3463      if (a.cmp(b) >= 0) {
3464        a.isub(b);
3465        x1.isub(x2);
3466      } else {
3467        b.isub(a);
3468        x2.isub(x1);
3469      }
3470    }
3471
3472    var res;
3473    if (a.cmpn(1) === 0) {
3474      res = x1;
3475    } else {
3476      res = x2;
3477    }
3478
3479    if (res.cmpn(0) < 0) {
3480      res.iadd(p);
3481    }
3482
3483    return res;
3484  };
3485
3486  BN.prototype.gcd = function gcd (num) {
3487    if (this.isZero()) return num.abs();
3488    if (num.isZero()) return this.abs();
3489
3490    var a = this.clone();
3491    var b = num.clone();
3492    a.negative = 0;
3493    b.negative = 0;
3494
3495    // Remove common factor of two
3496    for (var shift = 0; a.isEven() && b.isEven(); shift++) {
3497      a.iushrn(1);
3498      b.iushrn(1);
3499    }
3500
3501    do {
3502      while (a.isEven()) {
3503        a.iushrn(1);
3504      }
3505      while (b.isEven()) {
3506        b.iushrn(1);
3507      }
3508
3509      var r = a.cmp(b);
3510      if (r < 0) {
3511        // Swap `a` and `b` to make `a` always bigger than `b`
3512        var t = a;
3513        a = b;
3514        b = t;
3515      } else if (r === 0 || b.cmpn(1) === 0) {
3516        break;
3517      }
3518
3519      a.isub(b);
3520    } while (true);
3521
3522    return b.iushln(shift);
3523  };
3524
3525  // Invert number in the field F(num)
3526  BN.prototype.invm = function invm (num) {
3527    return this.egcd(num).a.umod(num);
3528  };
3529
3530  BN.prototype.isEven = function isEven () {
3531    return (this.words[0] & 1) === 0;
3532  };
3533
3534  BN.prototype.isOdd = function isOdd () {
3535    return (this.words[0] & 1) === 1;
3536  };
3537
3538  // And first word and num
3539  BN.prototype.andln = function andln (num) {
3540    return this.words[0] & num;
3541  };
3542
3543  // Increment at the bit position in-line
3544  BN.prototype.bincn = function bincn (bit) {
3545    assert(typeof bit === 'number');
3546    var r = bit % 26;
3547    var s = (bit - r) / 26;
3548    var q = 1 << r;
3549
3550    // Fast case: bit is much higher than all existing words
3551    if (this.length <= s) {
3552      this._expand(s + 1);
3553      this.words[s] |= q;
3554      return this;
3555    }
3556
3557    // Add bit and propagate, if needed
3558    var carry = q;
3559    for (var i = s; carry !== 0 && i < this.length; i++) {
3560      var w = this.words[i] | 0;
3561      w += carry;
3562      carry = w >>> 26;
3563      w &= 0x3ffffff;
3564      this.words[i] = w;
3565    }
3566    if (carry !== 0) {
3567      this.words[i] = carry;
3568      this.length++;
3569    }
3570    return this;
3571  };
3572
3573  BN.prototype.isZero = function isZero () {
3574    return this.length === 1 && this.words[0] === 0;
3575  };
3576
3577  BN.prototype.cmpn = function cmpn (num) {
3578    var negative = num < 0;
3579
3580    if (this.negative !== 0 && !negative) return -1;
3581    if (this.negative === 0 && negative) return 1;
3582
3583    this.strip();
3584
3585    var res;
3586    if (this.length > 1) {
3587      res = 1;
3588    } else {
3589      if (negative) {
3590        num = -num;
3591      }
3592
3593      assert(num <= 0x3ffffff, 'Number is too big');
3594
3595      var w = this.words[0] | 0;
3596      res = w === num ? 0 : w < num ? -1 : 1;
3597    }
3598    if (this.negative !== 0) return -res | 0;
3599    return res;
3600  };
3601
3602  // Compare two numbers and return:
3603  // 1 - if `this` > `num`
3604  // 0 - if `this` == `num`
3605  // -1 - if `this` < `num`
3606  BN.prototype.cmp = function cmp (num) {
3607    if (this.negative !== 0 && num.negative === 0) return -1;
3608    if (this.negative === 0 && num.negative !== 0) return 1;
3609
3610    var res = this.ucmp(num);
3611    if (this.negative !== 0) return -res | 0;
3612    return res;
3613  };
3614
3615  // Unsigned comparison
3616  BN.prototype.ucmp = function ucmp (num) {
3617    // At this point both numbers have the same sign
3618    if (this.length > num.length) return 1;
3619    if (this.length < num.length) return -1;
3620
3621    var res = 0;
3622    for (var i = this.length - 1; i >= 0; i--) {
3623      var a = this.words[i] | 0;
3624      var b = num.words[i] | 0;
3625
3626      if (a === b) continue;
3627      if (a < b) {
3628        res = -1;
3629      } else if (a > b) {
3630        res = 1;
3631      }
3632      break;
3633    }
3634    return res;
3635  };
3636
3637  BN.prototype.gtn = function gtn (num) {
3638    return this.cmpn(num) === 1;
3639  };
3640
3641  BN.prototype.gt = function gt (num) {
3642    return this.cmp(num) === 1;
3643  };
3644
3645  BN.prototype.gten = function gten (num) {
3646    return this.cmpn(num) >= 0;
3647  };
3648
3649  BN.prototype.gte = function gte (num) {
3650    return this.cmp(num) >= 0;
3651  };
3652
3653  BN.prototype.ltn = function ltn (num) {
3654    return this.cmpn(num) === -1;
3655  };
3656
3657  BN.prototype.lt = function lt (num) {
3658    return this.cmp(num) === -1;
3659  };
3660
3661  BN.prototype.lten = function lten (num) {
3662    return this.cmpn(num) <= 0;
3663  };
3664
3665  BN.prototype.lte = function lte (num) {
3666    return this.cmp(num) <= 0;
3667  };
3668
3669  BN.prototype.eqn = function eqn (num) {
3670    return this.cmpn(num) === 0;
3671  };
3672
3673  BN.prototype.eq = function eq (num) {
3674    return this.cmp(num) === 0;
3675  };
3676
3677  //
3678  // A reduce context, could be using montgomery or something better, depending
3679  // on the `m` itself.
3680  //
3681  BN.red = function red (num) {
3682    return new Red(num);
3683  };
3684
3685  BN.prototype.toRed = function toRed (ctx) {
3686    assert(!this.red, 'Already a number in reduction context');
3687    assert(this.negative === 0, 'red works only with positives');
3688    return ctx.convertTo(this)._forceRed(ctx);
3689  };
3690
3691  BN.prototype.fromRed = function fromRed () {
3692    assert(this.red, 'fromRed works only with numbers in reduction context');
3693    return this.red.convertFrom(this);
3694  };
3695
3696  BN.prototype._forceRed = function _forceRed (ctx) {
3697    this.red = ctx;
3698    return this;
3699  };
3700
3701  BN.prototype.forceRed = function forceRed (ctx) {
3702    assert(!this.red, 'Already a number in reduction context');
3703    return this._forceRed(ctx);
3704  };
3705
3706  BN.prototype.redAdd = function redAdd (num) {
3707    assert(this.red, 'redAdd works only with red numbers');
3708    return this.red.add(this, num);
3709  };
3710
3711  BN.prototype.redIAdd = function redIAdd (num) {
3712    assert(this.red, 'redIAdd works only with red numbers');
3713    return this.red.iadd(this, num);
3714  };
3715
3716  BN.prototype.redSub = function redSub (num) {
3717    assert(this.red, 'redSub works only with red numbers');
3718    return this.red.sub(this, num);
3719  };
3720
3721  BN.prototype.redISub = function redISub (num) {
3722    assert(this.red, 'redISub works only with red numbers');
3723    return this.red.isub(this, num);
3724  };
3725
3726  BN.prototype.redShl = function redShl (num) {
3727    assert(this.red, 'redShl works only with red numbers');
3728    return this.red.shl(this, num);
3729  };
3730
3731  BN.prototype.redMul = function redMul (num) {
3732    assert(this.red, 'redMul works only with red numbers');
3733    this.red._verify2(this, num);
3734    return this.red.mul(this, num);
3735  };
3736
3737  BN.prototype.redIMul = function redIMul (num) {
3738    assert(this.red, 'redMul works only with red numbers');
3739    this.red._verify2(this, num);
3740    return this.red.imul(this, num);
3741  };
3742
3743  BN.prototype.redSqr = function redSqr () {
3744    assert(this.red, 'redSqr works only with red numbers');
3745    this.red._verify1(this);
3746    return this.red.sqr(this);
3747  };
3748
3749  BN.prototype.redISqr = function redISqr () {
3750    assert(this.red, 'redISqr works only with red numbers');
3751    this.red._verify1(this);
3752    return this.red.isqr(this);
3753  };
3754
3755  // Square root over p
3756  BN.prototype.redSqrt = function redSqrt () {
3757    assert(this.red, 'redSqrt works only with red numbers');
3758    this.red._verify1(this);
3759    return this.red.sqrt(this);
3760  };
3761