1 |
|
2 | const globalThis = typeof window !== 'undefined' ? window : typeof global !== 'undefined' ? global : typeof self !== 'undefined' ? self : {};
|
3 |
|
4 | import { c as createCommonjsModule, a as commonjsGlobal } from './openpgp.mjs';
|
5 |
|
6 | var bn = createCommonjsModule(function (module) {
|
7 | (function (module, exports) {
|
8 |
|
9 |
|
10 | function assert (val, msg) {
|
11 | if (!val) throw new Error(msg || 'Assertion failed');
|
12 | }
|
13 |
|
14 |
|
15 |
|
16 | function inherits (ctor, superCtor) {
|
17 | ctor.super_ = superCtor;
|
18 | var TempCtor = function () {};
|
19 | TempCtor.prototype = superCtor.prototype;
|
20 | ctor.prototype = new TempCtor();
|
21 | ctor.prototype.constructor = ctor;
|
22 | }
|
23 |
|
24 |
|
25 |
|
26 | function BN (number, base, endian) {
|
27 | if (BN.isBN(number)) {
|
28 | return number;
|
29 | }
|
30 |
|
31 | this.negative = 0;
|
32 | this.words = null;
|
33 | this.length = 0;
|
34 |
|
35 |
|
36 | this.red = null;
|
37 |
|
38 | if (number !== null) {
|
39 | if (base === 'le' || base === 'be') {
|
40 | endian = base;
|
41 | base = 10;
|
42 | }
|
43 |
|
44 | this._init(number || 0, base || 10, endian || 'be');
|
45 | }
|
46 | }
|
47 | if (typeof module === 'object') {
|
48 | module.exports = BN;
|
49 | } else {
|
50 | exports.BN = BN;
|
51 | }
|
52 |
|
53 | BN.BN = BN;
|
54 | BN.wordSize = 26;
|
55 |
|
56 | var Buffer;
|
57 | try {
|
58 | Buffer = void('buffer').Buffer;
|
59 | } catch (e) {
|
60 | }
|
61 |
|
62 | BN.isBN = function isBN (num) {
|
63 | if (num instanceof BN) {
|
64 | return true;
|
65 | }
|
66 |
|
67 | return num !== null && typeof num === 'object' &&
|
68 | num.constructor.wordSize === BN.wordSize && Array.isArray(num.words);
|
69 | };
|
70 |
|
71 | BN.max = function max (left, right) {
|
72 | if (left.cmp(right) > 0) return left;
|
73 | return right;
|
74 | };
|
75 |
|
76 | BN.min = function min (left, right) {
|
77 | if (left.cmp(right) < 0) return left;
|
78 | return right;
|
79 | };
|
80 |
|
81 | BN.prototype._init = function init (number, base, endian) {
|
82 | if (typeof number === 'number') {
|
83 | return this._initNumber(number, base, endian);
|
84 | }
|
85 |
|
86 | if (typeof number === 'object') {
|
87 | return this._initArray(number, base, endian);
|
88 | }
|
89 |
|
90 | if (base === 'hex') {
|
91 | base = 16;
|
92 | }
|
93 | assert(base === (base | 0) && base >= 2 && base <= 36);
|
94 |
|
95 | number = number.toString().replace(/\s+/g, '');
|
96 | var start = 0;
|
97 | if (number[0] === '-') {
|
98 | start++;
|
99 | }
|
100 |
|
101 | if (base === 16) {
|
102 | this._parseHex(number, start);
|
103 | } else {
|
104 | this._parseBase(number, base, start);
|
105 | }
|
106 |
|
107 | if (number[0] === '-') {
|
108 | this.negative = 1;
|
109 | }
|
110 |
|
111 | this.strip();
|
112 |
|
113 | if (endian !== 'le') return;
|
114 |
|
115 | this._initArray(this.toArray(), base, endian);
|
116 | };
|
117 |
|
118 | BN.prototype._initNumber = function _initNumber (number, base, endian) {
|
119 | if (number < 0) {
|
120 | this.negative = 1;
|
121 | number = -number;
|
122 | }
|
123 | if (number < 0x4000000) {
|
124 | this.words = [ number & 0x3ffffff ];
|
125 | this.length = 1;
|
126 | } else if (number < 0x10000000000000) {
|
127 | this.words = [
|
128 | number & 0x3ffffff,
|
129 | (number / 0x4000000) & 0x3ffffff
|
130 | ];
|
131 | this.length = 2;
|
132 | } else {
|
133 | assert(number < 0x20000000000000);
|
134 | this.words = [
|
135 | number & 0x3ffffff,
|
136 | (number / 0x4000000) & 0x3ffffff,
|
137 | 1
|
138 | ];
|
139 | this.length = 3;
|
140 | }
|
141 |
|
142 | if (endian !== 'le') return;
|
143 |
|
144 |
|
145 | this._initArray(this.toArray(), base, endian);
|
146 | };
|
147 |
|
148 | BN.prototype._initArray = function _initArray (number, base, endian) {
|
149 |
|
150 | assert(typeof number.length === 'number');
|
151 | if (number.length <= 0) {
|
152 | this.words = [ 0 ];
|
153 | this.length = 1;
|
154 | return this;
|
155 | }
|
156 |
|
157 | this.length = Math.ceil(number.length / 3);
|
158 | this.words = new Array(this.length);
|
159 | for (var i = 0; i < this.length; i++) {
|
160 | this.words[i] = 0;
|
161 | }
|
162 |
|
163 | var j, w;
|
164 | var off = 0;
|
165 | if (endian === 'be') {
|
166 | for (i = number.length - 1, j = 0; i >= 0; i -= 3) {
|
167 | w = number[i] | (number[i - 1] << 8) | (number[i - 2] << 16);
|
168 | this.words[j] |= (w << off) & 0x3ffffff;
|
169 | this.words[j + 1] = (w >>> (26 - off)) & 0x3ffffff;
|
170 | off += 24;
|
171 | if (off >= 26) {
|
172 | off -= 26;
|
173 | j++;
|
174 | }
|
175 | }
|
176 | } else if (endian === 'le') {
|
177 | for (i = 0, j = 0; i < number.length; i += 3) {
|
178 | w = number[i] | (number[i + 1] << 8) | (number[i + 2] << 16);
|
179 | this.words[j] |= (w << off) & 0x3ffffff;
|
180 | this.words[j + 1] = (w >>> (26 - off)) & 0x3ffffff;
|
181 | off += 24;
|
182 | if (off >= 26) {
|
183 | off -= 26;
|
184 | j++;
|
185 | }
|
186 | }
|
187 | }
|
188 | return this.strip();
|
189 | };
|
190 |
|
191 | function parseHex (str, start, end) {
|
192 | var r = 0;
|
193 | var len = Math.min(str.length, end);
|
194 | for (var i = start; i < len; i++) {
|
195 | var c = str.charCodeAt(i) - 48;
|
196 |
|
197 | r <<= 4;
|
198 |
|
199 |
|
200 | if (c >= 49 && c <= 54) {
|
201 | r |= c - 49 + 0xa;
|
202 |
|
203 |
|
204 | } else if (c >= 17 && c <= 22) {
|
205 | r |= c - 17 + 0xa;
|
206 |
|
207 |
|
208 | } else {
|
209 | r |= c & 0xf;
|
210 | }
|
211 | }
|
212 | return r;
|
213 | }
|
214 |
|
215 | BN.prototype._parseHex = function _parseHex (number, start) {
|
216 |
|
217 | this.length = Math.ceil((number.length - start) / 6);
|
218 | this.words = new Array(this.length);
|
219 | for (var i = 0; i < this.length; i++) {
|
220 | this.words[i] = 0;
|
221 | }
|
222 |
|
223 | var j, w;
|
224 |
|
225 | var off = 0;
|
226 | for (i = number.length - 6, j = 0; i >= start; i -= 6) {
|
227 | w = parseHex(number, i, i + 6);
|
228 | this.words[j] |= (w << off) & 0x3ffffff;
|
229 |
|
230 | this.words[j + 1] |= w >>> (26 - off) & 0x3fffff;
|
231 | off += 24;
|
232 | if (off >= 26) {
|
233 | off -= 26;
|
234 | j++;
|
235 | }
|
236 | }
|
237 | if (i + 6 !== start) {
|
238 | w = parseHex(number, start, i + 6);
|
239 | this.words[j] |= (w << off) & 0x3ffffff;
|
240 | this.words[j + 1] |= w >>> (26 - off) & 0x3fffff;
|
241 | }
|
242 | this.strip();
|
243 | };
|
244 |
|
245 | function parseBase (str, start, end, mul) {
|
246 | var r = 0;
|
247 | var len = Math.min(str.length, end);
|
248 | for (var i = start; i < len; i++) {
|
249 | var c = str.charCodeAt(i) - 48;
|
250 |
|
251 | r *= mul;
|
252 |
|
253 |
|
254 | if (c >= 49) {
|
255 | r += c - 49 + 0xa;
|
256 |
|
257 |
|
258 | } else if (c >= 17) {
|
259 | r += c - 17 + 0xa;
|
260 |
|
261 |
|
262 | } else {
|
263 | r += c;
|
264 | }
|
265 | }
|
266 | return r;
|
267 | }
|
268 |
|
269 | BN.prototype._parseBase = function _parseBase (number, base, start) {
|
270 |
|
271 | this.words = [ 0 ];
|
272 | this.length = 1;
|
273 |
|
274 |
|
275 | for (var limbLen = 0, limbPow = 1; limbPow <= 0x3ffffff; limbPow *= base) {
|
276 | limbLen++;
|
277 | }
|
278 | limbLen--;
|
279 | limbPow = (limbPow / base) | 0;
|
280 |
|
281 | var total = number.length - start;
|
282 | var mod = total % limbLen;
|
283 | var end = Math.min(total, total - mod) + start;
|
284 |
|
285 | var word = 0;
|
286 | for (var i = start; i < end; i += limbLen) {
|
287 | word = parseBase(number, i, i + limbLen, base);
|
288 |
|
289 | this.imuln(limbPow);
|
290 | if (this.words[0] + word < 0x4000000) {
|
291 | this.words[0] += word;
|
292 | } else {
|
293 | this._iaddn(word);
|
294 | }
|
295 | }
|
296 |
|
297 | if (mod !== 0) {
|
298 | var pow = 1;
|
299 | word = parseBase(number, i, number.length, base);
|
300 |
|
301 | for (i = 0; i < mod; i++) {
|
302 | pow *= base;
|
303 | }
|
304 |
|
305 | this.imuln(pow);
|
306 | if (this.words[0] + word < 0x4000000) {
|
307 | this.words[0] += word;
|
308 | } else {
|
309 | this._iaddn(word);
|
310 | }
|
311 | }
|
312 | };
|
313 |
|
314 | BN.prototype.copy = function copy (dest) {
|
315 | dest.words = new Array(this.length);
|
316 | for (var i = 0; i < this.length; i++) {
|
317 | dest.words[i] = this.words[i];
|
318 | }
|
319 | dest.length = this.length;
|
320 | dest.negative = this.negative;
|
321 | dest.red = this.red;
|
322 | };
|
323 |
|
324 | BN.prototype.clone = function clone () {
|
325 | var r = new BN(null);
|
326 | this.copy(r);
|
327 | return r;
|
328 | };
|
329 |
|
330 | BN.prototype._expand = function _expand (size) {
|
331 | while (this.length < size) {
|
332 | this.words[this.length++] = 0;
|
333 | }
|
334 | return this;
|
335 | };
|
336 |
|
337 |
|
338 | BN.prototype.strip = function strip () {
|
339 | while (this.length > 1 && this.words[this.length - 1] === 0) {
|
340 | this.length--;
|
341 | }
|
342 | return this._normSign();
|
343 | };
|
344 |
|
345 | BN.prototype._normSign = function _normSign () {
|
346 |
|
347 | if (this.length === 1 && this.words[0] === 0) {
|
348 | this.negative = 0;
|
349 | }
|
350 | return this;
|
351 | };
|
352 |
|
353 | BN.prototype.inspect = function inspect () {
|
354 | return (this.red ? '<BN-R: ' : '<BN: ') + this.toString(16) + '>';
|
355 | };
|
356 |
|
357 | |
358 |
|
359 |
|
360 |
|
361 |
|
362 |
|
363 |
|
364 |
|
365 |
|
366 |
|
367 |
|
368 |
|
369 |
|
370 |
|
371 |
|
372 |
|
373 |
|
374 |
|
375 |
|
376 |
|
377 |
|
378 |
|
379 |
|
380 |
|
381 |
|
382 |
|
383 |
|
384 |
|
385 |
|
386 |
|
387 | var zeros = [
|
388 | '',
|
389 | '0',
|
390 | '00',
|
391 | '000',
|
392 | '0000',
|
393 | '00000',
|
394 | '000000',
|
395 | '0000000',
|
396 | '00000000',
|
397 | '000000000',
|
398 | '0000000000',
|
399 | '00000000000',
|
400 | '000000000000',
|
401 | '0000000000000',
|
402 | '00000000000000',
|
403 | '000000000000000',
|
404 | '0000000000000000',
|
405 | '00000000000000000',
|
406 | '000000000000000000',
|
407 | '0000000000000000000',
|
408 | '00000000000000000000',
|
409 | '000000000000000000000',
|
410 | '0000000000000000000000',
|
411 | '00000000000000000000000',
|
412 | '000000000000000000000000',
|
413 | '0000000000000000000000000'
|
414 | ];
|
415 |
|
416 | var groupSizes = [
|
417 | 0, 0,
|
418 | 25, 16, 12, 11, 10, 9, 8,
|
419 | 8, 7, 7, 7, 7, 6, 6,
|
420 | 6, 6, 6, 6, 6, 5, 5,
|
421 | 5, 5, 5, 5, 5, 5, 5,
|
422 | 5, 5, 5, 5, 5, 5, 5
|
423 | ];
|
424 |
|
425 | var groupBases = [
|
426 | 0, 0,
|
427 | 33554432, 43046721, 16777216, 48828125, 60466176, 40353607, 16777216,
|
428 | 43046721, 10000000, 19487171, 35831808, 62748517, 7529536, 11390625,
|
429 | 16777216, 24137569, 34012224, 47045881, 64000000, 4084101, 5153632,
|
430 | 6436343, 7962624, 9765625, 11881376, 14348907, 17210368, 20511149,
|
431 | 24300000, 28629151, 33554432, 39135393, 45435424, 52521875, 60466176
|
432 | ];
|
433 |
|
434 | BN.prototype.toString = function toString (base, padding) {
|
435 | base = base || 10;
|
436 | padding = padding | 0 || 1;
|
437 |
|
438 | var out;
|
439 | if (base === 16 || base === 'hex') {
|
440 | out = '';
|
441 | var off = 0;
|
442 | var carry = 0;
|
443 | for (var i = 0; i < this.length; i++) {
|
444 | var w = this.words[i];
|
445 | var word = (((w << off) | carry) & 0xffffff).toString(16);
|
446 | carry = (w >>> (24 - off)) & 0xffffff;
|
447 | if (carry !== 0 || i !== this.length - 1) {
|
448 | out = zeros[6 - word.length] + word + out;
|
449 | } else {
|
450 | out = word + out;
|
451 | }
|
452 | off += 2;
|
453 | if (off >= 26) {
|
454 | off -= 26;
|
455 | i--;
|
456 | }
|
457 | }
|
458 | if (carry !== 0) {
|
459 | out = carry.toString(16) + out;
|
460 | }
|
461 | while (out.length % padding !== 0) {
|
462 | out = '0' + out;
|
463 | }
|
464 | if (this.negative !== 0) {
|
465 | out = '-' + out;
|
466 | }
|
467 | return out;
|
468 | }
|
469 |
|
470 | if (base === (base | 0) && base >= 2 && base <= 36) {
|
471 |
|
472 | var groupSize = groupSizes[base];
|
473 |
|
474 | var groupBase = groupBases[base];
|
475 | out = '';
|
476 | var c = this.clone();
|
477 | c.negative = 0;
|
478 | while (!c.isZero()) {
|
479 | var r = c.modn(groupBase).toString(base);
|
480 | c = c.idivn(groupBase);
|
481 |
|
482 | if (!c.isZero()) {
|
483 | out = zeros[groupSize - r.length] + r + out;
|
484 | } else {
|
485 | out = r + out;
|
486 | }
|
487 | }
|
488 | if (this.isZero()) {
|
489 | out = '0' + out;
|
490 | }
|
491 | while (out.length % padding !== 0) {
|
492 | out = '0' + out;
|
493 | }
|
494 | if (this.negative !== 0) {
|
495 | out = '-' + out;
|
496 | }
|
497 | return out;
|
498 | }
|
499 |
|
500 | assert(false, 'Base should be between 2 and 36');
|
501 | };
|
502 |
|
503 | BN.prototype.toNumber = function toNumber () {
|
504 | var ret = this.words[0];
|
505 | if (this.length === 2) {
|
506 | ret += this.words[1] * 0x4000000;
|
507 | } else if (this.length === 3 && this.words[2] === 0x01) {
|
508 |
|
509 | ret += 0x10000000000000 + (this.words[1] * 0x4000000);
|
510 | } else if (this.length > 2) {
|
511 | assert(false, 'Number can only safely store up to 53 bits');
|
512 | }
|
513 | return (this.negative !== 0) ? -ret : ret;
|
514 | };
|
515 |
|
516 | BN.prototype.toJSON = function toJSON () {
|
517 | return this.toString(16);
|
518 | };
|
519 |
|
520 | BN.prototype.toBuffer = function toBuffer (endian, length) {
|
521 | assert(typeof Buffer !== 'undefined');
|
522 | return this.toArrayLike(Buffer, endian, length);
|
523 | };
|
524 |
|
525 | BN.prototype.toArray = function toArray (endian, length) {
|
526 | return this.toArrayLike(Array, endian, length);
|
527 | };
|
528 |
|
529 | BN.prototype.toArrayLike = function toArrayLike (ArrayType, endian, length) {
|
530 | var byteLength = this.byteLength();
|
531 | var reqLength = length || Math.max(1, byteLength);
|
532 | assert(byteLength <= reqLength, 'byte array longer than desired length');
|
533 | assert(reqLength > 0, 'Requested array length <= 0');
|
534 |
|
535 | this.strip();
|
536 | var littleEndian = endian === 'le';
|
537 | var res = new ArrayType(reqLength);
|
538 |
|
539 | var b, i;
|
540 | var q = this.clone();
|
541 | if (!littleEndian) {
|
542 |
|
543 | for (i = 0; i < reqLength - byteLength; i++) {
|
544 | res[i] = 0;
|
545 | }
|
546 |
|
547 | for (i = 0; !q.isZero(); i++) {
|
548 | b = q.andln(0xff);
|
549 | q.iushrn(8);
|
550 |
|
551 | res[reqLength - i - 1] = b;
|
552 | }
|
553 | } else {
|
554 | for (i = 0; !q.isZero(); i++) {
|
555 | b = q.andln(0xff);
|
556 | q.iushrn(8);
|
557 |
|
558 | res[i] = b;
|
559 | }
|
560 |
|
561 | for (; i < reqLength; i++) {
|
562 | res[i] = 0;
|
563 | }
|
564 | }
|
565 |
|
566 | return res;
|
567 | };
|
568 |
|
569 | if (Math.clz32) {
|
570 | BN.prototype._countBits = function _countBits (w) {
|
571 | return 32 - Math.clz32(w);
|
572 | };
|
573 | } else {
|
574 | BN.prototype._countBits = function _countBits (w) {
|
575 | var t = w;
|
576 | var r = 0;
|
577 | if (t >= 0x1000) {
|
578 | r += 13;
|
579 | t >>>= 13;
|
580 | }
|
581 | if (t >= 0x40) {
|
582 | r += 7;
|
583 | t >>>= 7;
|
584 | }
|
585 | if (t >= 0x8) {
|
586 | r += 4;
|
587 | t >>>= 4;
|
588 | }
|
589 | if (t >= 0x02) {
|
590 | r += 2;
|
591 | t >>>= 2;
|
592 | }
|
593 | return r + t;
|
594 | };
|
595 | }
|
596 |
|
597 | BN.prototype._zeroBits = function _zeroBits (w) {
|
598 |
|
599 | if (w === 0) return 26;
|
600 |
|
601 | var t = w;
|
602 | var r = 0;
|
603 | if ((t & 0x1fff) === 0) {
|
604 | r += 13;
|
605 | t >>>= 13;
|
606 | }
|
607 | if ((t & 0x7f) === 0) {
|
608 | r += 7;
|
609 | t >>>= 7;
|
610 | }
|
611 | if ((t & 0xf) === 0) {
|
612 | r += 4;
|
613 | t >>>= 4;
|
614 | }
|
615 | if ((t & 0x3) === 0) {
|
616 | r += 2;
|
617 | t >>>= 2;
|
618 | }
|
619 | if ((t & 0x1) === 0) {
|
620 | r++;
|
621 | }
|
622 | return r;
|
623 | };
|
624 |
|
625 |
|
626 | BN.prototype.bitLength = function bitLength () {
|
627 | var w = this.words[this.length - 1];
|
628 | var hi = this._countBits(w);
|
629 | return (this.length - 1) * 26 + hi;
|
630 | };
|
631 |
|
632 | function toBitArray (num) {
|
633 | var w = new Array(num.bitLength());
|
634 |
|
635 | for (var bit = 0; bit < w.length; bit++) {
|
636 | var off = (bit / 26) | 0;
|
637 | var wbit = bit % 26;
|
638 |
|
639 | w[bit] = (num.words[off] & (1 << wbit)) >>> wbit;
|
640 | }
|
641 |
|
642 | return w;
|
643 | }
|
644 |
|
645 |
|
646 | BN.prototype.zeroBits = function zeroBits () {
|
647 | if (this.isZero()) return 0;
|
648 |
|
649 | var r = 0;
|
650 | for (var i = 0; i < this.length; i++) {
|
651 | var b = this._zeroBits(this.words[i]);
|
652 | r += b;
|
653 | if (b !== 26) break;
|
654 | }
|
655 | return r;
|
656 | };
|
657 |
|
658 | BN.prototype.byteLength = function byteLength () {
|
659 | return Math.ceil(this.bitLength() / 8);
|
660 | };
|
661 |
|
662 | BN.prototype.toTwos = function toTwos (width) {
|
663 | if (this.negative !== 0) {
|
664 | return this.abs().inotn(width).iaddn(1);
|
665 | }
|
666 | return this.clone();
|
667 | };
|
668 |
|
669 | BN.prototype.fromTwos = function fromTwos (width) {
|
670 | if (this.testn(width - 1)) {
|
671 | return this.notn(width).iaddn(1).ineg();
|
672 | }
|
673 | return this.clone();
|
674 | };
|
675 |
|
676 | BN.prototype.isNeg = function isNeg () {
|
677 | return this.negative !== 0;
|
678 | };
|
679 |
|
680 |
|
681 | BN.prototype.neg = function neg () {
|
682 | return this.clone().ineg();
|
683 | };
|
684 |
|
685 | BN.prototype.ineg = function ineg () {
|
686 | if (!this.isZero()) {
|
687 | this.negative ^= 1;
|
688 | }
|
689 |
|
690 | return this;
|
691 | };
|
692 |
|
693 |
|
694 | BN.prototype.iuor = function iuor (num) {
|
695 | while (this.length < num.length) {
|
696 | this.words[this.length++] = 0;
|
697 | }
|
698 |
|
699 | for (var i = 0; i < num.length; i++) {
|
700 | this.words[i] = this.words[i] | num.words[i];
|
701 | }
|
702 |
|
703 | return this.strip();
|
704 | };
|
705 |
|
706 | BN.prototype.ior = function ior (num) {
|
707 | assert((this.negative | num.negative) === 0);
|
708 | return this.iuor(num);
|
709 | };
|
710 |
|
711 |
|
712 | BN.prototype.or = function or (num) {
|
713 | if (this.length > num.length) return this.clone().ior(num);
|
714 | return num.clone().ior(this);
|
715 | };
|
716 |
|
717 | BN.prototype.uor = function uor (num) {
|
718 | if (this.length > num.length) return this.clone().iuor(num);
|
719 | return num.clone().iuor(this);
|
720 | };
|
721 |
|
722 |
|
723 | BN.prototype.iuand = function iuand (num) {
|
724 |
|
725 | var b;
|
726 | if (this.length > num.length) {
|
727 | b = num;
|
728 | } else {
|
729 | b = this;
|
730 | }
|
731 |
|
732 | for (var i = 0; i < b.length; i++) {
|
733 | this.words[i] = this.words[i] & num.words[i];
|
734 | }
|
735 |
|
736 | this.length = b.length;
|
737 |
|
738 | return this.strip();
|
739 | };
|
740 |
|
741 | BN.prototype.iand = function iand (num) {
|
742 | assert((this.negative | num.negative) === 0);
|
743 | return this.iuand(num);
|
744 | };
|
745 |
|
746 |
|
747 | BN.prototype.and = function and (num) {
|
748 | if (this.length > num.length) return this.clone().iand(num);
|
749 | return num.clone().iand(this);
|
750 | };
|
751 |
|
752 | BN.prototype.uand = function uand (num) {
|
753 | if (this.length > num.length) return this.clone().iuand(num);
|
754 | return num.clone().iuand(this);
|
755 | };
|
756 |
|
757 |
|
758 | BN.prototype.iuxor = function iuxor (num) {
|
759 |
|
760 | var a;
|
761 | var b;
|
762 | if (this.length > num.length) {
|
763 | a = this;
|
764 | b = num;
|
765 | } else {
|
766 | a = num;
|
767 | b = this;
|
768 | }
|
769 |
|
770 | for (var i = 0; i < b.length; i++) {
|
771 | this.words[i] = a.words[i] ^ b.words[i];
|
772 | }
|
773 |
|
774 | if (this !== a) {
|
775 | for (; i < a.length; i++) {
|
776 | this.words[i] = a.words[i];
|
777 | }
|
778 | }
|
779 |
|
780 | this.length = a.length;
|
781 |
|
782 | return this.strip();
|
783 | };
|
784 |
|
785 | BN.prototype.ixor = function ixor (num) {
|
786 | assert((this.negative | num.negative) === 0);
|
787 | return this.iuxor(num);
|
788 | };
|
789 |
|
790 |
|
791 | BN.prototype.xor = function xor (num) {
|
792 | if (this.length > num.length) return this.clone().ixor(num);
|
793 | return num.clone().ixor(this);
|
794 | };
|
795 |
|
796 | BN.prototype.uxor = function uxor (num) {
|
797 | if (this.length > num.length) return this.clone().iuxor(num);
|
798 | return num.clone().iuxor(this);
|
799 | };
|
800 |
|
801 |
|
802 | BN.prototype.inotn = function inotn (width) {
|
803 | assert(typeof width === 'number' && width >= 0);
|
804 |
|
805 | var bytesNeeded = Math.ceil(width / 26) | 0;
|
806 | var bitsLeft = width % 26;
|
807 |
|
808 |
|
809 | this._expand(bytesNeeded);
|
810 |
|
811 | if (bitsLeft > 0) {
|
812 | bytesNeeded--;
|
813 | }
|
814 |
|
815 |
|
816 | for (var i = 0; i < bytesNeeded; i++) {
|
817 | this.words[i] = ~this.words[i] & 0x3ffffff;
|
818 | }
|
819 |
|
820 |
|
821 | if (bitsLeft > 0) {
|
822 | this.words[i] = ~this.words[i] & (0x3ffffff >> (26 - bitsLeft));
|
823 | }
|
824 |
|
825 |
|
826 | return this.strip();
|
827 | };
|
828 |
|
829 | BN.prototype.notn = function notn (width) {
|
830 | return this.clone().inotn(width);
|
831 | };
|
832 |
|
833 |
|
834 | BN.prototype.setn = function setn (bit, val) {
|
835 | assert(typeof bit === 'number' && bit >= 0);
|
836 |
|
837 | var off = (bit / 26) | 0;
|
838 | var wbit = bit % 26;
|
839 |
|
840 | this._expand(off + 1);
|
841 |
|
842 | if (val) {
|
843 | this.words[off] = this.words[off] | (1 << wbit);
|
844 | } else {
|
845 | this.words[off] = this.words[off] & ~(1 << wbit);
|
846 | }
|
847 |
|
848 | return this.strip();
|
849 | };
|
850 |
|
851 |
|
852 | BN.prototype.iadd = function iadd (num) {
|
853 | var r;
|
854 |
|
855 |
|
856 | if (this.negative !== 0 && num.negative === 0) {
|
857 | this.negative = 0;
|
858 | r = this.isub(num);
|
859 | this.negative ^= 1;
|
860 | return this._normSign();
|
861 |
|
862 |
|
863 | } else if (this.negative === 0 && num.negative !== 0) {
|
864 | num.negative = 0;
|
865 | r = this.isub(num);
|
866 | num.negative = 1;
|
867 | return r._normSign();
|
868 | }
|
869 |
|
870 |
|
871 | var a, b;
|
872 | if (this.length > num.length) {
|
873 | a = this;
|
874 | b = num;
|
875 | } else {
|
876 | a = num;
|
877 | b = this;
|
878 | }
|
879 |
|
880 | var carry = 0;
|
881 | for (var i = 0; i < b.length; i++) {
|
882 | r = (a.words[i] | 0) + (b.words[i] | 0) + carry;
|
883 | this.words[i] = r & 0x3ffffff;
|
884 | carry = r >>> 26;
|
885 | }
|
886 | for (; carry !== 0 && i < a.length; i++) {
|
887 | r = (a.words[i] | 0) + carry;
|
888 | this.words[i] = r & 0x3ffffff;
|
889 | carry = r >>> 26;
|
890 | }
|
891 |
|
892 | this.length = a.length;
|
893 | if (carry !== 0) {
|
894 | this.words[this.length] = carry;
|
895 | this.length++;
|
896 |
|
897 | } else if (a !== this) {
|
898 | for (; i < a.length; i++) {
|
899 | this.words[i] = a.words[i];
|
900 | }
|
901 | }
|
902 |
|
903 | return this;
|
904 | };
|
905 |
|
906 |
|
907 | BN.prototype.add = function add (num) {
|
908 | var res;
|
909 | if (num.negative !== 0 && this.negative === 0) {
|
910 | num.negative = 0;
|
911 | res = this.sub(num);
|
912 | num.negative ^= 1;
|
913 | return res;
|
914 | } else if (num.negative === 0 && this.negative !== 0) {
|
915 | this.negative = 0;
|
916 | res = num.sub(this);
|
917 | this.negative = 1;
|
918 | return res;
|
919 | }
|
920 |
|
921 | if (this.length > num.length) return this.clone().iadd(num);
|
922 |
|
923 | return num.clone().iadd(this);
|
924 | };
|
925 |
|
926 |
|
927 | BN.prototype.isub = function isub (num) {
|
928 |
|
929 | if (num.negative !== 0) {
|
930 | num.negative = 0;
|
931 | var r = this.iadd(num);
|
932 | num.negative = 1;
|
933 | return r._normSign();
|
934 |
|
935 |
|
936 | } else if (this.negative !== 0) {
|
937 | this.negative = 0;
|
938 | this.iadd(num);
|
939 | this.negative = 1;
|
940 | return this._normSign();
|
941 | }
|
942 |
|
943 |
|
944 | var cmp = this.cmp(num);
|
945 |
|
946 |
|
947 | if (cmp === 0) {
|
948 | this.negative = 0;
|
949 | this.length = 1;
|
950 | this.words[0] = 0;
|
951 | return this;
|
952 | }
|
953 |
|
954 |
|
955 | var a, b;
|
956 | if (cmp > 0) {
|
957 | a = this;
|
958 | b = num;
|
959 | } else {
|
960 | a = num;
|
961 | b = this;
|
962 | }
|
963 |
|
964 | var carry = 0;
|
965 | for (var i = 0; i < b.length; i++) {
|
966 | r = (a.words[i] | 0) - (b.words[i] | 0) + carry;
|
967 | carry = r >> 26;
|
968 | this.words[i] = r & 0x3ffffff;
|
969 | }
|
970 | for (; carry !== 0 && i < a.length; i++) {
|
971 | r = (a.words[i] | 0) + carry;
|
972 | carry = r >> 26;
|
973 | this.words[i] = r & 0x3ffffff;
|
974 | }
|
975 |
|
976 |
|
977 | if (carry === 0 && i < a.length && a !== this) {
|
978 | for (; i < a.length; i++) {
|
979 | this.words[i] = a.words[i];
|
980 | }
|
981 | }
|
982 |
|
983 | this.length = Math.max(this.length, i);
|
984 |
|
985 | if (a !== this) {
|
986 | this.negative = 1;
|
987 | }
|
988 |
|
989 | return this.strip();
|
990 | };
|
991 |
|
992 |
|
993 | BN.prototype.sub = function sub (num) {
|
994 | return this.clone().isub(num);
|
995 | };
|
996 |
|
997 | function smallMulTo (self, num, out) {
|
998 | out.negative = num.negative ^ self.negative;
|
999 | var len = (self.length + num.length) | 0;
|
1000 | out.length = len;
|
1001 | len = (len - 1) | 0;
|
1002 |
|
1003 |
|
1004 | var a = self.words[0] | 0;
|
1005 | var b = num.words[0] | 0;
|
1006 | var r = a * b;
|
1007 |
|
1008 | var lo = r & 0x3ffffff;
|
1009 | var carry = (r / 0x4000000) | 0;
|
1010 | out.words[0] = lo;
|
1011 |
|
1012 | for (var k = 1; k < len; k++) {
|
1013 |
|
1014 |
|
1015 | var ncarry = carry >>> 26;
|
1016 | var rword = carry & 0x3ffffff;
|
1017 | var maxJ = Math.min(k, num.length - 1);
|
1018 | for (var j = Math.max(0, k - self.length + 1); j <= maxJ; j++) {
|
1019 | var i = (k - j) | 0;
|
1020 | a = self.words[i] | 0;
|
1021 | b = num.words[j] | 0;
|
1022 | r = a * b + rword;
|
1023 | ncarry += (r / 0x4000000) | 0;
|
1024 | rword = r & 0x3ffffff;
|
1025 | }
|
1026 | out.words[k] = rword | 0;
|
1027 | carry = ncarry | 0;
|
1028 | }
|
1029 | if (carry !== 0) {
|
1030 | out.words[k] = carry | 0;
|
1031 | } else {
|
1032 | out.length--;
|
1033 | }
|
1034 |
|
1035 | return out.strip();
|
1036 | }
|
1037 |
|
1038 |
|
1039 |
|
1040 |
|
1041 | var comb10MulTo = function comb10MulTo (self, num, out) {
|
1042 | var a = self.words;
|
1043 | var b = num.words;
|
1044 | var o = out.words;
|
1045 | var c = 0;
|
1046 | var lo;
|
1047 | var mid;
|
1048 | var hi;
|
1049 | var a0 = a[0] | 0;
|
1050 | var al0 = a0 & 0x1fff;
|
1051 | var ah0 = a0 >>> 13;
|
1052 | var a1 = a[1] | 0;
|
1053 | var al1 = a1 & 0x1fff;
|
1054 | var ah1 = a1 >>> 13;
|
1055 | var a2 = a[2] | 0;
|
1056 | var al2 = a2 & 0x1fff;
|
1057 | var ah2 = a2 >>> 13;
|
1058 | var a3 = a[3] | 0;
|
1059 | var al3 = a3 & 0x1fff;
|
1060 | var ah3 = a3 >>> 13;
|
1061 | var a4 = a[4] | 0;
|
1062 | var al4 = a4 & 0x1fff;
|
1063 | var ah4 = a4 >>> 13;
|
1064 | var a5 = a[5] | 0;
|
1065 | var al5 = a5 & 0x1fff;
|
1066 | var ah5 = a5 >>> 13;
|
1067 | var a6 = a[6] | 0;
|
1068 | var al6 = a6 & 0x1fff;
|
1069 | var ah6 = a6 >>> 13;
|
1070 | var a7 = a[7] | 0;
|
1071 | var al7 = a7 & 0x1fff;
|
1072 | var ah7 = a7 >>> 13;
|
1073 | var a8 = a[8] | 0;
|
1074 | var al8 = a8 & 0x1fff;
|
1075 | var ah8 = a8 >>> 13;
|
1076 | var a9 = a[9] | 0;
|
1077 | var al9 = a9 & 0x1fff;
|
1078 | var ah9 = a9 >>> 13;
|
1079 | var b0 = b[0] | 0;
|
1080 | var bl0 = b0 & 0x1fff;
|
1081 | var bh0 = b0 >>> 13;
|
1082 | var b1 = b[1] | 0;
|
1083 | var bl1 = b1 & 0x1fff;
|
1084 | var bh1 = b1 >>> 13;
|
1085 | var b2 = b[2] | 0;
|
1086 | var bl2 = b2 & 0x1fff;
|
1087 | var bh2 = b2 >>> 13;
|
1088 | var b3 = b[3] | 0;
|
1089 | var bl3 = b3 & 0x1fff;
|
1090 | var bh3 = b3 >>> 13;
|
1091 | var b4 = b[4] | 0;
|
1092 | var bl4 = b4 & 0x1fff;
|
1093 | var bh4 = b4 >>> 13;
|
1094 | var b5 = b[5] | 0;
|
1095 | var bl5 = b5 & 0x1fff;
|
1096 | var bh5 = b5 >>> 13;
|
1097 | var b6 = b[6] | 0;
|
1098 | var bl6 = b6 & 0x1fff;
|
1099 | var bh6 = b6 >>> 13;
|
1100 | var b7 = b[7] | 0;
|
1101 | var bl7 = b7 & 0x1fff;
|
1102 | var bh7 = b7 >>> 13;
|
1103 | var b8 = b[8] | 0;
|
1104 | var bl8 = b8 & 0x1fff;
|
1105 | var bh8 = b8 >>> 13;
|
1106 | var b9 = b[9] | 0;
|
1107 | var bl9 = b9 & 0x1fff;
|
1108 | var bh9 = b9 >>> 13;
|
1109 |
|
1110 | out.negative = self.negative ^ num.negative;
|
1111 | out.length = 19;
|
1112 |
|
1113 | lo = Math.imul(al0, bl0);
|
1114 | mid = Math.imul(al0, bh0);
|
1115 | mid = (mid + Math.imul(ah0, bl0)) | 0;
|
1116 | hi = Math.imul(ah0, bh0);
|
1117 | var w0 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1118 | c = (((hi + (mid >>> 13)) | 0) + (w0 >>> 26)) | 0;
|
1119 | w0 &= 0x3ffffff;
|
1120 |
|
1121 | lo = Math.imul(al1, bl0);
|
1122 | mid = Math.imul(al1, bh0);
|
1123 | mid = (mid + Math.imul(ah1, bl0)) | 0;
|
1124 | hi = Math.imul(ah1, bh0);
|
1125 | lo = (lo + Math.imul(al0, bl1)) | 0;
|
1126 | mid = (mid + Math.imul(al0, bh1)) | 0;
|
1127 | mid = (mid + Math.imul(ah0, bl1)) | 0;
|
1128 | hi = (hi + Math.imul(ah0, bh1)) | 0;
|
1129 | var w1 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1130 | c = (((hi + (mid >>> 13)) | 0) + (w1 >>> 26)) | 0;
|
1131 | w1 &= 0x3ffffff;
|
1132 |
|
1133 | lo = Math.imul(al2, bl0);
|
1134 | mid = Math.imul(al2, bh0);
|
1135 | mid = (mid + Math.imul(ah2, bl0)) | 0;
|
1136 | hi = Math.imul(ah2, bh0);
|
1137 | lo = (lo + Math.imul(al1, bl1)) | 0;
|
1138 | mid = (mid + Math.imul(al1, bh1)) | 0;
|
1139 | mid = (mid + Math.imul(ah1, bl1)) | 0;
|
1140 | hi = (hi + Math.imul(ah1, bh1)) | 0;
|
1141 | lo = (lo + Math.imul(al0, bl2)) | 0;
|
1142 | mid = (mid + Math.imul(al0, bh2)) | 0;
|
1143 | mid = (mid + Math.imul(ah0, bl2)) | 0;
|
1144 | hi = (hi + Math.imul(ah0, bh2)) | 0;
|
1145 | var w2 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1146 | c = (((hi + (mid >>> 13)) | 0) + (w2 >>> 26)) | 0;
|
1147 | w2 &= 0x3ffffff;
|
1148 |
|
1149 | lo = Math.imul(al3, bl0);
|
1150 | mid = Math.imul(al3, bh0);
|
1151 | mid = (mid + Math.imul(ah3, bl0)) | 0;
|
1152 | hi = Math.imul(ah3, bh0);
|
1153 | lo = (lo + Math.imul(al2, bl1)) | 0;
|
1154 | mid = (mid + Math.imul(al2, bh1)) | 0;
|
1155 | mid = (mid + Math.imul(ah2, bl1)) | 0;
|
1156 | hi = (hi + Math.imul(ah2, bh1)) | 0;
|
1157 | lo = (lo + Math.imul(al1, bl2)) | 0;
|
1158 | mid = (mid + Math.imul(al1, bh2)) | 0;
|
1159 | mid = (mid + Math.imul(ah1, bl2)) | 0;
|
1160 | hi = (hi + Math.imul(ah1, bh2)) | 0;
|
1161 | lo = (lo + Math.imul(al0, bl3)) | 0;
|
1162 | mid = (mid + Math.imul(al0, bh3)) | 0;
|
1163 | mid = (mid + Math.imul(ah0, bl3)) | 0;
|
1164 | hi = (hi + Math.imul(ah0, bh3)) | 0;
|
1165 | var w3 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1166 | c = (((hi + (mid >>> 13)) | 0) + (w3 >>> 26)) | 0;
|
1167 | w3 &= 0x3ffffff;
|
1168 |
|
1169 | lo = Math.imul(al4, bl0);
|
1170 | mid = Math.imul(al4, bh0);
|
1171 | mid = (mid + Math.imul(ah4, bl0)) | 0;
|
1172 | hi = Math.imul(ah4, bh0);
|
1173 | lo = (lo + Math.imul(al3, bl1)) | 0;
|
1174 | mid = (mid + Math.imul(al3, bh1)) | 0;
|
1175 | mid = (mid + Math.imul(ah3, bl1)) | 0;
|
1176 | hi = (hi + Math.imul(ah3, bh1)) | 0;
|
1177 | lo = (lo + Math.imul(al2, bl2)) | 0;
|
1178 | mid = (mid + Math.imul(al2, bh2)) | 0;
|
1179 | mid = (mid + Math.imul(ah2, bl2)) | 0;
|
1180 | hi = (hi + Math.imul(ah2, bh2)) | 0;
|
1181 | lo = (lo + Math.imul(al1, bl3)) | 0;
|
1182 | mid = (mid + Math.imul(al1, bh3)) | 0;
|
1183 | mid = (mid + Math.imul(ah1, bl3)) | 0;
|
1184 | hi = (hi + Math.imul(ah1, bh3)) | 0;
|
1185 | lo = (lo + Math.imul(al0, bl4)) | 0;
|
1186 | mid = (mid + Math.imul(al0, bh4)) | 0;
|
1187 | mid = (mid + Math.imul(ah0, bl4)) | 0;
|
1188 | hi = (hi + Math.imul(ah0, bh4)) | 0;
|
1189 | var w4 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1190 | c = (((hi + (mid >>> 13)) | 0) + (w4 >>> 26)) | 0;
|
1191 | w4 &= 0x3ffffff;
|
1192 |
|
1193 | lo = Math.imul(al5, bl0);
|
1194 | mid = Math.imul(al5, bh0);
|
1195 | mid = (mid + Math.imul(ah5, bl0)) | 0;
|
1196 | hi = Math.imul(ah5, bh0);
|
1197 | lo = (lo + Math.imul(al4, bl1)) | 0;
|
1198 | mid = (mid + Math.imul(al4, bh1)) | 0;
|
1199 | mid = (mid + Math.imul(ah4, bl1)) | 0;
|
1200 | hi = (hi + Math.imul(ah4, bh1)) | 0;
|
1201 | lo = (lo + Math.imul(al3, bl2)) | 0;
|
1202 | mid = (mid + Math.imul(al3, bh2)) | 0;
|
1203 | mid = (mid + Math.imul(ah3, bl2)) | 0;
|
1204 | hi = (hi + Math.imul(ah3, bh2)) | 0;
|
1205 | lo = (lo + Math.imul(al2, bl3)) | 0;
|
1206 | mid = (mid + Math.imul(al2, bh3)) | 0;
|
1207 | mid = (mid + Math.imul(ah2, bl3)) | 0;
|
1208 | hi = (hi + Math.imul(ah2, bh3)) | 0;
|
1209 | lo = (lo + Math.imul(al1, bl4)) | 0;
|
1210 | mid = (mid + Math.imul(al1, bh4)) | 0;
|
1211 | mid = (mid + Math.imul(ah1, bl4)) | 0;
|
1212 | hi = (hi + Math.imul(ah1, bh4)) | 0;
|
1213 | lo = (lo + Math.imul(al0, bl5)) | 0;
|
1214 | mid = (mid + Math.imul(al0, bh5)) | 0;
|
1215 | mid = (mid + Math.imul(ah0, bl5)) | 0;
|
1216 | hi = (hi + Math.imul(ah0, bh5)) | 0;
|
1217 | var w5 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1218 | c = (((hi + (mid >>> 13)) | 0) + (w5 >>> 26)) | 0;
|
1219 | w5 &= 0x3ffffff;
|
1220 |
|
1221 | lo = Math.imul(al6, bl0);
|
1222 | mid = Math.imul(al6, bh0);
|
1223 | mid = (mid + Math.imul(ah6, bl0)) | 0;
|
1224 | hi = Math.imul(ah6, bh0);
|
1225 | lo = (lo + Math.imul(al5, bl1)) | 0;
|
1226 | mid = (mid + Math.imul(al5, bh1)) | 0;
|
1227 | mid = (mid + Math.imul(ah5, bl1)) | 0;
|
1228 | hi = (hi + Math.imul(ah5, bh1)) | 0;
|
1229 | lo = (lo + Math.imul(al4, bl2)) | 0;
|
1230 | mid = (mid + Math.imul(al4, bh2)) | 0;
|
1231 | mid = (mid + Math.imul(ah4, bl2)) | 0;
|
1232 | hi = (hi + Math.imul(ah4, bh2)) | 0;
|
1233 | lo = (lo + Math.imul(al3, bl3)) | 0;
|
1234 | mid = (mid + Math.imul(al3, bh3)) | 0;
|
1235 | mid = (mid + Math.imul(ah3, bl3)) | 0;
|
1236 | hi = (hi + Math.imul(ah3, bh3)) | 0;
|
1237 | lo = (lo + Math.imul(al2, bl4)) | 0;
|
1238 | mid = (mid + Math.imul(al2, bh4)) | 0;
|
1239 | mid = (mid + Math.imul(ah2, bl4)) | 0;
|
1240 | hi = (hi + Math.imul(ah2, bh4)) | 0;
|
1241 | lo = (lo + Math.imul(al1, bl5)) | 0;
|
1242 | mid = (mid + Math.imul(al1, bh5)) | 0;
|
1243 | mid = (mid + Math.imul(ah1, bl5)) | 0;
|
1244 | hi = (hi + Math.imul(ah1, bh5)) | 0;
|
1245 | lo = (lo + Math.imul(al0, bl6)) | 0;
|
1246 | mid = (mid + Math.imul(al0, bh6)) | 0;
|
1247 | mid = (mid + Math.imul(ah0, bl6)) | 0;
|
1248 | hi = (hi + Math.imul(ah0, bh6)) | 0;
|
1249 | var w6 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1250 | c = (((hi + (mid >>> 13)) | 0) + (w6 >>> 26)) | 0;
|
1251 | w6 &= 0x3ffffff;
|
1252 |
|
1253 | lo = Math.imul(al7, bl0);
|
1254 | mid = Math.imul(al7, bh0);
|
1255 | mid = (mid + Math.imul(ah7, bl0)) | 0;
|
1256 | hi = Math.imul(ah7, bh0);
|
1257 | lo = (lo + Math.imul(al6, bl1)) | 0;
|
1258 | mid = (mid + Math.imul(al6, bh1)) | 0;
|
1259 | mid = (mid + Math.imul(ah6, bl1)) | 0;
|
1260 | hi = (hi + Math.imul(ah6, bh1)) | 0;
|
1261 | lo = (lo + Math.imul(al5, bl2)) | 0;
|
1262 | mid = (mid + Math.imul(al5, bh2)) | 0;
|
1263 | mid = (mid + Math.imul(ah5, bl2)) | 0;
|
1264 | hi = (hi + Math.imul(ah5, bh2)) | 0;
|
1265 | lo = (lo + Math.imul(al4, bl3)) | 0;
|
1266 | mid = (mid + Math.imul(al4, bh3)) | 0;
|
1267 | mid = (mid + Math.imul(ah4, bl3)) | 0;
|
1268 | hi = (hi + Math.imul(ah4, bh3)) | 0;
|
1269 | lo = (lo + Math.imul(al3, bl4)) | 0;
|
1270 | mid = (mid + Math.imul(al3, bh4)) | 0;
|
1271 | mid = (mid + Math.imul(ah3, bl4)) | 0;
|
1272 | hi = (hi + Math.imul(ah3, bh4)) | 0;
|
1273 | lo = (lo + Math.imul(al2, bl5)) | 0;
|
1274 | mid = (mid + Math.imul(al2, bh5)) | 0;
|
1275 | mid = (mid + Math.imul(ah2, bl5)) | 0;
|
1276 | hi = (hi + Math.imul(ah2, bh5)) | 0;
|
1277 | lo = (lo + Math.imul(al1, bl6)) | 0;
|
1278 | mid = (mid + Math.imul(al1, bh6)) | 0;
|
1279 | mid = (mid + Math.imul(ah1, bl6)) | 0;
|
1280 | hi = (hi + Math.imul(ah1, bh6)) | 0;
|
1281 | lo = (lo + Math.imul(al0, bl7)) | 0;
|
1282 | mid = (mid + Math.imul(al0, bh7)) | 0;
|
1283 | mid = (mid + Math.imul(ah0, bl7)) | 0;
|
1284 | hi = (hi + Math.imul(ah0, bh7)) | 0;
|
1285 | var w7 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1286 | c = (((hi + (mid >>> 13)) | 0) + (w7 >>> 26)) | 0;
|
1287 | w7 &= 0x3ffffff;
|
1288 |
|
1289 | lo = Math.imul(al8, bl0);
|
1290 | mid = Math.imul(al8, bh0);
|
1291 | mid = (mid + Math.imul(ah8, bl0)) | 0;
|
1292 | hi = Math.imul(ah8, bh0);
|
1293 | lo = (lo + Math.imul(al7, bl1)) | 0;
|
1294 | mid = (mid + Math.imul(al7, bh1)) | 0;
|
1295 | mid = (mid + Math.imul(ah7, bl1)) | 0;
|
1296 | hi = (hi + Math.imul(ah7, bh1)) | 0;
|
1297 | lo = (lo + Math.imul(al6, bl2)) | 0;
|
1298 | mid = (mid + Math.imul(al6, bh2)) | 0;
|
1299 | mid = (mid + Math.imul(ah6, bl2)) | 0;
|
1300 | hi = (hi + Math.imul(ah6, bh2)) | 0;
|
1301 | lo = (lo + Math.imul(al5, bl3)) | 0;
|
1302 | mid = (mid + Math.imul(al5, bh3)) | 0;
|
1303 | mid = (mid + Math.imul(ah5, bl3)) | 0;
|
1304 | hi = (hi + Math.imul(ah5, bh3)) | 0;
|
1305 | lo = (lo + Math.imul(al4, bl4)) | 0;
|
1306 | mid = (mid + Math.imul(al4, bh4)) | 0;
|
1307 | mid = (mid + Math.imul(ah4, bl4)) | 0;
|
1308 | hi = (hi + Math.imul(ah4, bh4)) | 0;
|
1309 | lo = (lo + Math.imul(al3, bl5)) | 0;
|
1310 | mid = (mid + Math.imul(al3, bh5)) | 0;
|
1311 | mid = (mid + Math.imul(ah3, bl5)) | 0;
|
1312 | hi = (hi + Math.imul(ah3, bh5)) | 0;
|
1313 | lo = (lo + Math.imul(al2, bl6)) | 0;
|
1314 | mid = (mid + Math.imul(al2, bh6)) | 0;
|
1315 | mid = (mid + Math.imul(ah2, bl6)) | 0;
|
1316 | hi = (hi + Math.imul(ah2, bh6)) | 0;
|
1317 | lo = (lo + Math.imul(al1, bl7)) | 0;
|
1318 | mid = (mid + Math.imul(al1, bh7)) | 0;
|
1319 | mid = (mid + Math.imul(ah1, bl7)) | 0;
|
1320 | hi = (hi + Math.imul(ah1, bh7)) | 0;
|
1321 | lo = (lo + Math.imul(al0, bl8)) | 0;
|
1322 | mid = (mid + Math.imul(al0, bh8)) | 0;
|
1323 | mid = (mid + Math.imul(ah0, bl8)) | 0;
|
1324 | hi = (hi + Math.imul(ah0, bh8)) | 0;
|
1325 | var w8 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1326 | c = (((hi + (mid >>> 13)) | 0) + (w8 >>> 26)) | 0;
|
1327 | w8 &= 0x3ffffff;
|
1328 |
|
1329 | lo = Math.imul(al9, bl0);
|
1330 | mid = Math.imul(al9, bh0);
|
1331 | mid = (mid + Math.imul(ah9, bl0)) | 0;
|
1332 | hi = Math.imul(ah9, bh0);
|
1333 | lo = (lo + Math.imul(al8, bl1)) | 0;
|
1334 | mid = (mid + Math.imul(al8, bh1)) | 0;
|
1335 | mid = (mid + Math.imul(ah8, bl1)) | 0;
|
1336 | hi = (hi + Math.imul(ah8, bh1)) | 0;
|
1337 | lo = (lo + Math.imul(al7, bl2)) | 0;
|
1338 | mid = (mid + Math.imul(al7, bh2)) | 0;
|
1339 | mid = (mid + Math.imul(ah7, bl2)) | 0;
|
1340 | hi = (hi + Math.imul(ah7, bh2)) | 0;
|
1341 | lo = (lo + Math.imul(al6, bl3)) | 0;
|
1342 | mid = (mid + Math.imul(al6, bh3)) | 0;
|
1343 | mid = (mid + Math.imul(ah6, bl3)) | 0;
|
1344 | hi = (hi + Math.imul(ah6, bh3)) | 0;
|
1345 | lo = (lo + Math.imul(al5, bl4)) | 0;
|
1346 | mid = (mid + Math.imul(al5, bh4)) | 0;
|
1347 | mid = (mid + Math.imul(ah5, bl4)) | 0;
|
1348 | hi = (hi + Math.imul(ah5, bh4)) | 0;
|
1349 | lo = (lo + Math.imul(al4, bl5)) | 0;
|
1350 | mid = (mid + Math.imul(al4, bh5)) | 0;
|
1351 | mid = (mid + Math.imul(ah4, bl5)) | 0;
|
1352 | hi = (hi + Math.imul(ah4, bh5)) | 0;
|
1353 | lo = (lo + Math.imul(al3, bl6)) | 0;
|
1354 | mid = (mid + Math.imul(al3, bh6)) | 0;
|
1355 | mid = (mid + Math.imul(ah3, bl6)) | 0;
|
1356 | hi = (hi + Math.imul(ah3, bh6)) | 0;
|
1357 | lo = (lo + Math.imul(al2, bl7)) | 0;
|
1358 | mid = (mid + Math.imul(al2, bh7)) | 0;
|
1359 | mid = (mid + Math.imul(ah2, bl7)) | 0;
|
1360 | hi = (hi + Math.imul(ah2, bh7)) | 0;
|
1361 | lo = (lo + Math.imul(al1, bl8)) | 0;
|
1362 | mid = (mid + Math.imul(al1, bh8)) | 0;
|
1363 | mid = (mid + Math.imul(ah1, bl8)) | 0;
|
1364 | hi = (hi + Math.imul(ah1, bh8)) | 0;
|
1365 | lo = (lo + Math.imul(al0, bl9)) | 0;
|
1366 | mid = (mid + Math.imul(al0, bh9)) | 0;
|
1367 | mid = (mid + Math.imul(ah0, bl9)) | 0;
|
1368 | hi = (hi + Math.imul(ah0, bh9)) | 0;
|
1369 | var w9 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1370 | c = (((hi + (mid >>> 13)) | 0) + (w9 >>> 26)) | 0;
|
1371 | w9 &= 0x3ffffff;
|
1372 |
|
1373 | lo = Math.imul(al9, bl1);
|
1374 | mid = Math.imul(al9, bh1);
|
1375 | mid = (mid + Math.imul(ah9, bl1)) | 0;
|
1376 | hi = Math.imul(ah9, bh1);
|
1377 | lo = (lo + Math.imul(al8, bl2)) | 0;
|
1378 | mid = (mid + Math.imul(al8, bh2)) | 0;
|
1379 | mid = (mid + Math.imul(ah8, bl2)) | 0;
|
1380 | hi = (hi + Math.imul(ah8, bh2)) | 0;
|
1381 | lo = (lo + Math.imul(al7, bl3)) | 0;
|
1382 | mid = (mid + Math.imul(al7, bh3)) | 0;
|
1383 | mid = (mid + Math.imul(ah7, bl3)) | 0;
|
1384 | hi = (hi + Math.imul(ah7, bh3)) | 0;
|
1385 | lo = (lo + Math.imul(al6, bl4)) | 0;
|
1386 | mid = (mid + Math.imul(al6, bh4)) | 0;
|
1387 | mid = (mid + Math.imul(ah6, bl4)) | 0;
|
1388 | hi = (hi + Math.imul(ah6, bh4)) | 0;
|
1389 | lo = (lo + Math.imul(al5, bl5)) | 0;
|
1390 | mid = (mid + Math.imul(al5, bh5)) | 0;
|
1391 | mid = (mid + Math.imul(ah5, bl5)) | 0;
|
1392 | hi = (hi + Math.imul(ah5, bh5)) | 0;
|
1393 | lo = (lo + Math.imul(al4, bl6)) | 0;
|
1394 | mid = (mid + Math.imul(al4, bh6)) | 0;
|
1395 | mid = (mid + Math.imul(ah4, bl6)) | 0;
|
1396 | hi = (hi + Math.imul(ah4, bh6)) | 0;
|
1397 | lo = (lo + Math.imul(al3, bl7)) | 0;
|
1398 | mid = (mid + Math.imul(al3, bh7)) | 0;
|
1399 | mid = (mid + Math.imul(ah3, bl7)) | 0;
|
1400 | hi = (hi + Math.imul(ah3, bh7)) | 0;
|
1401 | lo = (lo + Math.imul(al2, bl8)) | 0;
|
1402 | mid = (mid + Math.imul(al2, bh8)) | 0;
|
1403 | mid = (mid + Math.imul(ah2, bl8)) | 0;
|
1404 | hi = (hi + Math.imul(ah2, bh8)) | 0;
|
1405 | lo = (lo + Math.imul(al1, bl9)) | 0;
|
1406 | mid = (mid + Math.imul(al1, bh9)) | 0;
|
1407 | mid = (mid + Math.imul(ah1, bl9)) | 0;
|
1408 | hi = (hi + Math.imul(ah1, bh9)) | 0;
|
1409 | var w10 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1410 | c = (((hi + (mid >>> 13)) | 0) + (w10 >>> 26)) | 0;
|
1411 | w10 &= 0x3ffffff;
|
1412 |
|
1413 | lo = Math.imul(al9, bl2);
|
1414 | mid = Math.imul(al9, bh2);
|
1415 | mid = (mid + Math.imul(ah9, bl2)) | 0;
|
1416 | hi = Math.imul(ah9, bh2);
|
1417 | lo = (lo + Math.imul(al8, bl3)) | 0;
|
1418 | mid = (mid + Math.imul(al8, bh3)) | 0;
|
1419 | mid = (mid + Math.imul(ah8, bl3)) | 0;
|
1420 | hi = (hi + Math.imul(ah8, bh3)) | 0;
|
1421 | lo = (lo + Math.imul(al7, bl4)) | 0;
|
1422 | mid = (mid + Math.imul(al7, bh4)) | 0;
|
1423 | mid = (mid + Math.imul(ah7, bl4)) | 0;
|
1424 | hi = (hi + Math.imul(ah7, bh4)) | 0;
|
1425 | lo = (lo + Math.imul(al6, bl5)) | 0;
|
1426 | mid = (mid + Math.imul(al6, bh5)) | 0;
|
1427 | mid = (mid + Math.imul(ah6, bl5)) | 0;
|
1428 | hi = (hi + Math.imul(ah6, bh5)) | 0;
|
1429 | lo = (lo + Math.imul(al5, bl6)) | 0;
|
1430 | mid = (mid + Math.imul(al5, bh6)) | 0;
|
1431 | mid = (mid + Math.imul(ah5, bl6)) | 0;
|
1432 | hi = (hi + Math.imul(ah5, bh6)) | 0;
|
1433 | lo = (lo + Math.imul(al4, bl7)) | 0;
|
1434 | mid = (mid + Math.imul(al4, bh7)) | 0;
|
1435 | mid = (mid + Math.imul(ah4, bl7)) | 0;
|
1436 | hi = (hi + Math.imul(ah4, bh7)) | 0;
|
1437 | lo = (lo + Math.imul(al3, bl8)) | 0;
|
1438 | mid = (mid + Math.imul(al3, bh8)) | 0;
|
1439 | mid = (mid + Math.imul(ah3, bl8)) | 0;
|
1440 | hi = (hi + Math.imul(ah3, bh8)) | 0;
|
1441 | lo = (lo + Math.imul(al2, bl9)) | 0;
|
1442 | mid = (mid + Math.imul(al2, bh9)) | 0;
|
1443 | mid = (mid + Math.imul(ah2, bl9)) | 0;
|
1444 | hi = (hi + Math.imul(ah2, bh9)) | 0;
|
1445 | var w11 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1446 | c = (((hi + (mid >>> 13)) | 0) + (w11 >>> 26)) | 0;
|
1447 | w11 &= 0x3ffffff;
|
1448 |
|
1449 | lo = Math.imul(al9, bl3);
|
1450 | mid = Math.imul(al9, bh3);
|
1451 | mid = (mid + Math.imul(ah9, bl3)) | 0;
|
1452 | hi = Math.imul(ah9, bh3);
|
1453 | lo = (lo + Math.imul(al8, bl4)) | 0;
|
1454 | mid = (mid + Math.imul(al8, bh4)) | 0;
|
1455 | mid = (mid + Math.imul(ah8, bl4)) | 0;
|
1456 | hi = (hi + Math.imul(ah8, bh4)) | 0;
|
1457 | lo = (lo + Math.imul(al7, bl5)) | 0;
|
1458 | mid = (mid + Math.imul(al7, bh5)) | 0;
|
1459 | mid = (mid + Math.imul(ah7, bl5)) | 0;
|
1460 | hi = (hi + Math.imul(ah7, bh5)) | 0;
|
1461 | lo = (lo + Math.imul(al6, bl6)) | 0;
|
1462 | mid = (mid + Math.imul(al6, bh6)) | 0;
|
1463 | mid = (mid + Math.imul(ah6, bl6)) | 0;
|
1464 | hi = (hi + Math.imul(ah6, bh6)) | 0;
|
1465 | lo = (lo + Math.imul(al5, bl7)) | 0;
|
1466 | mid = (mid + Math.imul(al5, bh7)) | 0;
|
1467 | mid = (mid + Math.imul(ah5, bl7)) | 0;
|
1468 | hi = (hi + Math.imul(ah5, bh7)) | 0;
|
1469 | lo = (lo + Math.imul(al4, bl8)) | 0;
|
1470 | mid = (mid + Math.imul(al4, bh8)) | 0;
|
1471 | mid = (mid + Math.imul(ah4, bl8)) | 0;
|
1472 | hi = (hi + Math.imul(ah4, bh8)) | 0;
|
1473 | lo = (lo + Math.imul(al3, bl9)) | 0;
|
1474 | mid = (mid + Math.imul(al3, bh9)) | 0;
|
1475 | mid = (mid + Math.imul(ah3, bl9)) | 0;
|
1476 | hi = (hi + Math.imul(ah3, bh9)) | 0;
|
1477 | var w12 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1478 | c = (((hi + (mid >>> 13)) | 0) + (w12 >>> 26)) | 0;
|
1479 | w12 &= 0x3ffffff;
|
1480 |
|
1481 | lo = Math.imul(al9, bl4);
|
1482 | mid = Math.imul(al9, bh4);
|
1483 | mid = (mid + Math.imul(ah9, bl4)) | 0;
|
1484 | hi = Math.imul(ah9, bh4);
|
1485 | lo = (lo + Math.imul(al8, bl5)) | 0;
|
1486 | mid = (mid + Math.imul(al8, bh5)) | 0;
|
1487 | mid = (mid + Math.imul(ah8, bl5)) | 0;
|
1488 | hi = (hi + Math.imul(ah8, bh5)) | 0;
|
1489 | lo = (lo + Math.imul(al7, bl6)) | 0;
|
1490 | mid = (mid + Math.imul(al7, bh6)) | 0;
|
1491 | mid = (mid + Math.imul(ah7, bl6)) | 0;
|
1492 | hi = (hi + Math.imul(ah7, bh6)) | 0;
|
1493 | lo = (lo + Math.imul(al6, bl7)) | 0;
|
1494 | mid = (mid + Math.imul(al6, bh7)) | 0;
|
1495 | mid = (mid + Math.imul(ah6, bl7)) | 0;
|
1496 | hi = (hi + Math.imul(ah6, bh7)) | 0;
|
1497 | lo = (lo + Math.imul(al5, bl8)) | 0;
|
1498 | mid = (mid + Math.imul(al5, bh8)) | 0;
|
1499 | mid = (mid + Math.imul(ah5, bl8)) | 0;
|
1500 | hi = (hi + Math.imul(ah5, bh8)) | 0;
|
1501 | lo = (lo + Math.imul(al4, bl9)) | 0;
|
1502 | mid = (mid + Math.imul(al4, bh9)) | 0;
|
1503 | mid = (mid + Math.imul(ah4, bl9)) | 0;
|
1504 | hi = (hi + Math.imul(ah4, bh9)) | 0;
|
1505 | var w13 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1506 | c = (((hi + (mid >>> 13)) | 0) + (w13 >>> 26)) | 0;
|
1507 | w13 &= 0x3ffffff;
|
1508 |
|
1509 | lo = Math.imul(al9, bl5);
|
1510 | mid = Math.imul(al9, bh5);
|
1511 | mid = (mid + Math.imul(ah9, bl5)) | 0;
|
1512 | hi = Math.imul(ah9, bh5);
|
1513 | lo = (lo + Math.imul(al8, bl6)) | 0;
|
1514 | mid = (mid + Math.imul(al8, bh6)) | 0;
|
1515 | mid = (mid + Math.imul(ah8, bl6)) | 0;
|
1516 | hi = (hi + Math.imul(ah8, bh6)) | 0;
|
1517 | lo = (lo + Math.imul(al7, bl7)) | 0;
|
1518 | mid = (mid + Math.imul(al7, bh7)) | 0;
|
1519 | mid = (mid + Math.imul(ah7, bl7)) | 0;
|
1520 | hi = (hi + Math.imul(ah7, bh7)) | 0;
|
1521 | lo = (lo + Math.imul(al6, bl8)) | 0;
|
1522 | mid = (mid + Math.imul(al6, bh8)) | 0;
|
1523 | mid = (mid + Math.imul(ah6, bl8)) | 0;
|
1524 | hi = (hi + Math.imul(ah6, bh8)) | 0;
|
1525 | lo = (lo + Math.imul(al5, bl9)) | 0;
|
1526 | mid = (mid + Math.imul(al5, bh9)) | 0;
|
1527 | mid = (mid + Math.imul(ah5, bl9)) | 0;
|
1528 | hi = (hi + Math.imul(ah5, bh9)) | 0;
|
1529 | var w14 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1530 | c = (((hi + (mid >>> 13)) | 0) + (w14 >>> 26)) | 0;
|
1531 | w14 &= 0x3ffffff;
|
1532 |
|
1533 | lo = Math.imul(al9, bl6);
|
1534 | mid = Math.imul(al9, bh6);
|
1535 | mid = (mid + Math.imul(ah9, bl6)) | 0;
|
1536 | hi = Math.imul(ah9, bh6);
|
1537 | lo = (lo + Math.imul(al8, bl7)) | 0;
|
1538 | mid = (mid + Math.imul(al8, bh7)) | 0;
|
1539 | mid = (mid + Math.imul(ah8, bl7)) | 0;
|
1540 | hi = (hi + Math.imul(ah8, bh7)) | 0;
|
1541 | lo = (lo + Math.imul(al7, bl8)) | 0;
|
1542 | mid = (mid + Math.imul(al7, bh8)) | 0;
|
1543 | mid = (mid + Math.imul(ah7, bl8)) | 0;
|
1544 | hi = (hi + Math.imul(ah7, bh8)) | 0;
|
1545 | lo = (lo + Math.imul(al6, bl9)) | 0;
|
1546 | mid = (mid + Math.imul(al6, bh9)) | 0;
|
1547 | mid = (mid + Math.imul(ah6, bl9)) | 0;
|
1548 | hi = (hi + Math.imul(ah6, bh9)) | 0;
|
1549 | var w15 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1550 | c = (((hi + (mid >>> 13)) | 0) + (w15 >>> 26)) | 0;
|
1551 | w15 &= 0x3ffffff;
|
1552 |
|
1553 | lo = Math.imul(al9, bl7);
|
1554 | mid = Math.imul(al9, bh7);
|
1555 | mid = (mid + Math.imul(ah9, bl7)) | 0;
|
1556 | hi = Math.imul(ah9, bh7);
|
1557 | lo = (lo + Math.imul(al8, bl8)) | 0;
|
1558 | mid = (mid + Math.imul(al8, bh8)) | 0;
|
1559 | mid = (mid + Math.imul(ah8, bl8)) | 0;
|
1560 | hi = (hi + Math.imul(ah8, bh8)) | 0;
|
1561 | lo = (lo + Math.imul(al7, bl9)) | 0;
|
1562 | mid = (mid + Math.imul(al7, bh9)) | 0;
|
1563 | mid = (mid + Math.imul(ah7, bl9)) | 0;
|
1564 | hi = (hi + Math.imul(ah7, bh9)) | 0;
|
1565 | var w16 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1566 | c = (((hi + (mid >>> 13)) | 0) + (w16 >>> 26)) | 0;
|
1567 | w16 &= 0x3ffffff;
|
1568 |
|
1569 | lo = Math.imul(al9, bl8);
|
1570 | mid = Math.imul(al9, bh8);
|
1571 | mid = (mid + Math.imul(ah9, bl8)) | 0;
|
1572 | hi = Math.imul(ah9, bh8);
|
1573 | lo = (lo + Math.imul(al8, bl9)) | 0;
|
1574 | mid = (mid + Math.imul(al8, bh9)) | 0;
|
1575 | mid = (mid + Math.imul(ah8, bl9)) | 0;
|
1576 | hi = (hi + Math.imul(ah8, bh9)) | 0;
|
1577 | var w17 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1578 | c = (((hi + (mid >>> 13)) | 0) + (w17 >>> 26)) | 0;
|
1579 | w17 &= 0x3ffffff;
|
1580 |
|
1581 | lo = Math.imul(al9, bl9);
|
1582 | mid = Math.imul(al9, bh9);
|
1583 | mid = (mid + Math.imul(ah9, bl9)) | 0;
|
1584 | hi = Math.imul(ah9, bh9);
|
1585 | var w18 = (((c + lo) | 0) + ((mid & 0x1fff) << 13)) | 0;
|
1586 | c = (((hi + (mid >>> 13)) | 0) + (w18 >>> 26)) | 0;
|
1587 | w18 &= 0x3ffffff;
|
1588 | o[0] = w0;
|
1589 | o[1] = w1;
|
1590 | o[2] = w2;
|
1591 | o[3] = w3;
|
1592 | o[4] = w4;
|
1593 | o[5] = w5;
|
1594 | o[6] = w6;
|
1595 | o[7] = w7;
|
1596 | o[8] = w8;
|
1597 | o[9] = w9;
|
1598 | o[10] = w10;
|
1599 | o[11] = w11;
|
1600 | o[12] = w12;
|
1601 | o[13] = w13;
|
1602 | o[14] = w14;
|
1603 | o[15] = w15;
|
1604 | o[16] = w16;
|
1605 | o[17] = w17;
|
1606 | o[18] = w18;
|
1607 | if (c !== 0) {
|
1608 | o[19] = c;
|
1609 | out.length++;
|
1610 | }
|
1611 | return out;
|
1612 | };
|
1613 |
|
1614 |
|
1615 | if (!Math.imul) {
|
1616 | comb10MulTo = smallMulTo;
|
1617 | }
|
1618 |
|
1619 | function bigMulTo (self, num, out) {
|
1620 | out.negative = num.negative ^ self.negative;
|
1621 | out.length = self.length + num.length;
|
1622 |
|
1623 | var carry = 0;
|
1624 | var hncarry = 0;
|
1625 | for (var k = 0; k < out.length - 1; k++) {
|
1626 |
|
1627 |
|
1628 | var ncarry = hncarry;
|
1629 | hncarry = 0;
|
1630 | var rword = carry & 0x3ffffff;
|
1631 | var maxJ = Math.min(k, num.length - 1);
|
1632 | for (var j = Math.max(0, k - self.length + 1); j <= maxJ; j++) {
|
1633 | var i = k - j;
|
1634 | var a = self.words[i] | 0;
|
1635 | var b = num.words[j] | 0;
|
1636 | var r = a * b;
|
1637 |
|
1638 | var lo = r & 0x3ffffff;
|
1639 | ncarry = (ncarry + ((r / 0x4000000) | 0)) | 0;
|
1640 | lo = (lo + rword) | 0;
|
1641 | rword = lo & 0x3ffffff;
|
1642 | ncarry = (ncarry + (lo >>> 26)) | 0;
|
1643 |
|
1644 | hncarry += ncarry >>> 26;
|
1645 | ncarry &= 0x3ffffff;
|
1646 | }
|
1647 | out.words[k] = rword;
|
1648 | carry = ncarry;
|
1649 | ncarry = hncarry;
|
1650 | }
|
1651 | if (carry !== 0) {
|
1652 | out.words[k] = carry;
|
1653 | } else {
|
1654 | out.length--;
|
1655 | }
|
1656 |
|
1657 | return out.strip();
|
1658 | }
|
1659 |
|
1660 | function jumboMulTo (self, num, out) {
|
1661 | var fftm = new FFTM();
|
1662 | return fftm.mulp(self, num, out);
|
1663 | }
|
1664 |
|
1665 | BN.prototype.mulTo = function mulTo (num, out) {
|
1666 | var res;
|
1667 | var len = this.length + num.length;
|
1668 | if (this.length === 10 && num.length === 10) {
|
1669 | res = comb10MulTo(this, num, out);
|
1670 | } else if (len < 63) {
|
1671 | res = smallMulTo(this, num, out);
|
1672 | } else if (len < 1024) {
|
1673 | res = bigMulTo(this, num, out);
|
1674 | } else {
|
1675 | res = jumboMulTo(this, num, out);
|
1676 | }
|
1677 |
|
1678 | return res;
|
1679 | };
|
1680 |
|
1681 |
|
1682 |
|
1683 |
|
1684 | function FFTM (x, y) {
|
1685 | this.x = x;
|
1686 | this.y = y;
|
1687 | }
|
1688 |
|
1689 | FFTM.prototype.makeRBT = function makeRBT (N) {
|
1690 | var t = new Array(N);
|
1691 | var l = BN.prototype._countBits(N) - 1;
|
1692 | for (var i = 0; i < N; i++) {
|
1693 | t[i] = this.revBin(i, l, N);
|
1694 | }
|
1695 |
|
1696 | return t;
|
1697 | };
|
1698 |
|
1699 |
|
1700 | FFTM.prototype.revBin = function revBin (x, l, N) {
|
1701 | if (x === 0 || x === N - 1) return x;
|
1702 |
|
1703 | var rb = 0;
|
1704 | for (var i = 0; i < l; i++) {
|
1705 | rb |= (x & 1) << (l - i - 1);
|
1706 | x >>= 1;
|
1707 | }
|
1708 |
|
1709 | return rb;
|
1710 | };
|
1711 |
|
1712 |
|
1713 |
|
1714 | FFTM.prototype.permute = function permute (rbt, rws, iws, rtws, itws, N) {
|
1715 | for (var i = 0; i < N; i++) {
|
1716 | rtws[i] = rws[rbt[i]];
|
1717 | itws[i] = iws[rbt[i]];
|
1718 | }
|
1719 | };
|
1720 |
|
1721 | FFTM.prototype.transform = function transform (rws, iws, rtws, itws, N, rbt) {
|
1722 | this.permute(rbt, rws, iws, rtws, itws, N);
|
1723 |
|
1724 | for (var s = 1; s < N; s <<= 1) {
|
1725 | var l = s << 1;
|
1726 |
|
1727 | var rtwdf = Math.cos(2 * Math.PI / l);
|
1728 | var itwdf = Math.sin(2 * Math.PI / l);
|
1729 |
|
1730 | for (var p = 0; p < N; p += l) {
|
1731 | var rtwdf_ = rtwdf;
|
1732 | var itwdf_ = itwdf;
|
1733 |
|
1734 | for (var j = 0; j < s; j++) {
|
1735 | var re = rtws[p + j];
|
1736 | var ie = itws[p + j];
|
1737 |
|
1738 | var ro = rtws[p + j + s];
|
1739 | var io = itws[p + j + s];
|
1740 |
|
1741 | var rx = rtwdf_ * ro - itwdf_ * io;
|
1742 |
|
1743 | io = rtwdf_ * io + itwdf_ * ro;
|
1744 | ro = rx;
|
1745 |
|
1746 | rtws[p + j] = re + ro;
|
1747 | itws[p + j] = ie + io;
|
1748 |
|
1749 | rtws[p + j + s] = re - ro;
|
1750 | itws[p + j + s] = ie - io;
|
1751 |
|
1752 |
|
1753 | if (j !== l) {
|
1754 | rx = rtwdf * rtwdf_ - itwdf * itwdf_;
|
1755 |
|
1756 | itwdf_ = rtwdf * itwdf_ + itwdf * rtwdf_;
|
1757 | rtwdf_ = rx;
|
1758 | }
|
1759 | }
|
1760 | }
|
1761 | }
|
1762 | };
|
1763 |
|
1764 | FFTM.prototype.guessLen13b = function guessLen13b (n, m) {
|
1765 | var N = Math.max(m, n) | 1;
|
1766 | var odd = N & 1;
|
1767 | var i = 0;
|
1768 | for (N = N / 2 | 0; N; N = N >>> 1) {
|
1769 | i++;
|
1770 | }
|
1771 |
|
1772 | return 1 << i + 1 + odd;
|
1773 | };
|
1774 |
|
1775 | FFTM.prototype.conjugate = function conjugate (rws, iws, N) {
|
1776 | if (N <= 1) return;
|
1777 |
|
1778 | for (var i = 0; i < N / 2; i++) {
|
1779 | var t = rws[i];
|
1780 |
|
1781 | rws[i] = rws[N - i - 1];
|
1782 | rws[N - i - 1] = t;
|
1783 |
|
1784 | t = iws[i];
|
1785 |
|
1786 | iws[i] = -iws[N - i - 1];
|
1787 | iws[N - i - 1] = -t;
|
1788 | }
|
1789 | };
|
1790 |
|
1791 | FFTM.prototype.normalize13b = function normalize13b (ws, N) {
|
1792 | var carry = 0;
|
1793 | for (var i = 0; i < N / 2; i++) {
|
1794 | var w = Math.round(ws[2 * i + 1] / N) * 0x2000 +
|
1795 | Math.round(ws[2 * i] / N) +
|
1796 | carry;
|
1797 |
|
1798 | ws[i] = w & 0x3ffffff;
|
1799 |
|
1800 | if (w < 0x4000000) {
|
1801 | carry = 0;
|
1802 | } else {
|
1803 | carry = w / 0x4000000 | 0;
|
1804 | }
|
1805 | }
|
1806 |
|
1807 | return ws;
|
1808 | };
|
1809 |
|
1810 | FFTM.prototype.convert13b = function convert13b (ws, len, rws, N) {
|
1811 | var carry = 0;
|
1812 | for (var i = 0; i < len; i++) {
|
1813 | carry = carry + (ws[i] | 0);
|
1814 |
|
1815 | rws[2 * i] = carry & 0x1fff; carry = carry >>> 13;
|
1816 | rws[2 * i + 1] = carry & 0x1fff; carry = carry >>> 13;
|
1817 | }
|
1818 |
|
1819 |
|
1820 | for (i = 2 * len; i < N; ++i) {
|
1821 | rws[i] = 0;
|
1822 | }
|
1823 |
|
1824 | assert(carry === 0);
|
1825 | assert((carry & ~0x1fff) === 0);
|
1826 | };
|
1827 |
|
1828 | FFTM.prototype.stub = function stub (N) {
|
1829 | var ph = new Array(N);
|
1830 | for (var i = 0; i < N; i++) {
|
1831 | ph[i] = 0;
|
1832 | }
|
1833 |
|
1834 | return ph;
|
1835 | };
|
1836 |
|
1837 | FFTM.prototype.mulp = function mulp (x, y, out) {
|
1838 | var N = 2 * this.guessLen13b(x.length, y.length);
|
1839 |
|
1840 | var rbt = this.makeRBT(N);
|
1841 |
|
1842 | var _ = this.stub(N);
|
1843 |
|
1844 | var rws = new Array(N);
|
1845 | var rwst = new Array(N);
|
1846 | var iwst = new Array(N);
|
1847 |
|
1848 | var nrws = new Array(N);
|
1849 | var nrwst = new Array(N);
|
1850 | var niwst = new Array(N);
|
1851 |
|
1852 | var rmws = out.words;
|
1853 | rmws.length = N;
|
1854 |
|
1855 | this.convert13b(x.words, x.length, rws, N);
|
1856 | this.convert13b(y.words, y.length, nrws, N);
|
1857 |
|
1858 | this.transform(rws, _, rwst, iwst, N, rbt);
|
1859 | this.transform(nrws, _, nrwst, niwst, N, rbt);
|
1860 |
|
1861 | for (var i = 0; i < N; i++) {
|
1862 | var rx = rwst[i] * nrwst[i] - iwst[i] * niwst[i];
|
1863 | iwst[i] = rwst[i] * niwst[i] + iwst[i] * nrwst[i];
|
1864 | rwst[i] = rx;
|
1865 | }
|
1866 |
|
1867 | this.conjugate(rwst, iwst, N);
|
1868 | this.transform(rwst, iwst, rmws, _, N, rbt);
|
1869 | this.conjugate(rmws, _, N);
|
1870 | this.normalize13b(rmws, N);
|
1871 |
|
1872 | out.negative = x.negative ^ y.negative;
|
1873 | out.length = x.length + y.length;
|
1874 | return out.strip();
|
1875 | };
|
1876 |
|
1877 |
|
1878 | BN.prototype.mul = function mul (num) {
|
1879 | var out = new BN(null);
|
1880 | out.words = new Array(this.length + num.length);
|
1881 | return this.mulTo(num, out);
|
1882 | };
|
1883 |
|
1884 |
|
1885 | BN.prototype.mulf = function mulf (num) {
|
1886 | var out = new BN(null);
|
1887 | out.words = new Array(this.length + num.length);
|
1888 | return jumboMulTo(this, num, out);
|
1889 | };
|
1890 |
|
1891 |
|
1892 | BN.prototype.imul = function imul (num) {
|
1893 | return this.clone().mulTo(num, this);
|
1894 | };
|
1895 |
|
1896 | BN.prototype.imuln = function imuln (num) {
|
1897 | assert(typeof num === 'number');
|
1898 | assert(num < 0x4000000);
|
1899 |
|
1900 |
|
1901 | var carry = 0;
|
1902 | for (var i = 0; i < this.length; i++) {
|
1903 | var w = (this.words[i] | 0) * num;
|
1904 | var lo = (w & 0x3ffffff) + (carry & 0x3ffffff);
|
1905 | carry >>= 26;
|
1906 | carry += (w / 0x4000000) | 0;
|
1907 |
|
1908 | carry += lo >>> 26;
|
1909 | this.words[i] = lo & 0x3ffffff;
|
1910 | }
|
1911 |
|
1912 | if (carry !== 0) {
|
1913 | this.words[i] = carry;
|
1914 | this.length++;
|
1915 | }
|
1916 |
|
1917 | return this;
|
1918 | };
|
1919 |
|
1920 | BN.prototype.muln = function muln (num) {
|
1921 | return this.clone().imuln(num);
|
1922 | };
|
1923 |
|
1924 |
|
1925 | BN.prototype.sqr = function sqr () {
|
1926 | return this.mul(this);
|
1927 | };
|
1928 |
|
1929 |
|
1930 | BN.prototype.isqr = function isqr () {
|
1931 | return this.imul(this.clone());
|
1932 | };
|
1933 |
|
1934 |
|
1935 | BN.prototype.pow = function pow (num) {
|
1936 | var w = toBitArray(num);
|
1937 | if (w.length === 0) return new BN(1);
|
1938 |
|
1939 |
|
1940 | var res = this;
|
1941 | for (var i = 0; i < w.length; i++, res = res.sqr()) {
|
1942 | if (w[i] !== 0) break;
|
1943 | }
|
1944 |
|
1945 | if (++i < w.length) {
|
1946 | for (var q = res.sqr(); i < w.length; i++, q = q.sqr()) {
|
1947 | if (w[i] === 0) continue;
|
1948 |
|
1949 | res = res.mul(q);
|
1950 | }
|
1951 | }
|
1952 |
|
1953 | return res;
|
1954 | };
|
1955 |
|
1956 |
|
1957 | BN.prototype.iushln = function iushln (bits) {
|
1958 | assert(typeof bits === 'number' && bits >= 0);
|
1959 | var r = bits % 26;
|
1960 | var s = (bits - r) / 26;
|
1961 | var carryMask = (0x3ffffff >>> (26 - r)) << (26 - r);
|
1962 | var i;
|
1963 |
|
1964 | if (r !== 0) {
|
1965 | var carry = 0;
|
1966 |
|
1967 | for (i = 0; i < this.length; i++) {
|
1968 | var newCarry = this.words[i] & carryMask;
|
1969 | var c = ((this.words[i] | 0) - newCarry) << r;
|
1970 | this.words[i] = c | carry;
|
1971 | carry = newCarry >>> (26 - r);
|
1972 | }
|
1973 |
|
1974 | if (carry) {
|
1975 | this.words[i] = carry;
|
1976 | this.length++;
|
1977 | }
|
1978 | }
|
1979 |
|
1980 | if (s !== 0) {
|
1981 | for (i = this.length - 1; i >= 0; i--) {
|
1982 | this.words[i + s] = this.words[i];
|
1983 | }
|
1984 |
|
1985 | for (i = 0; i < s; i++) {
|
1986 | this.words[i] = 0;
|
1987 | }
|
1988 |
|
1989 | this.length += s;
|
1990 | }
|
1991 |
|
1992 | return this.strip();
|
1993 | };
|
1994 |
|
1995 | BN.prototype.ishln = function ishln (bits) {
|
1996 |
|
1997 | assert(this.negative === 0);
|
1998 | return this.iushln(bits);
|
1999 | };
|
2000 |
|
2001 |
|
2002 |
|
2003 |
|
2004 | BN.prototype.iushrn = function iushrn (bits, hint, extended) {
|
2005 | assert(typeof bits === 'number' && bits >= 0);
|
2006 | var h;
|
2007 | if (hint) {
|
2008 | h = (hint - (hint % 26)) / 26;
|
2009 | } else {
|
2010 | h = 0;
|
2011 | }
|
2012 |
|
2013 | var r = bits % 26;
|
2014 | var s = Math.min((bits - r) / 26, this.length);
|
2015 | var mask = 0x3ffffff ^ ((0x3ffffff >>> r) << r);
|
2016 | var maskedWords = extended;
|
2017 |
|
2018 | h -= s;
|
2019 | h = Math.max(0, h);
|
2020 |
|
2021 |
|
2022 | if (maskedWords) {
|
2023 | for (var i = 0; i < s; i++) {
|
2024 | maskedWords.words[i] = this.words[i];
|
2025 | }
|
2026 | maskedWords.length = s;
|
2027 | }
|
2028 |
|
2029 | if (s === 0) ; else if (this.length > s) {
|
2030 | this.length -= s;
|
2031 | for (i = 0; i < this.length; i++) {
|
2032 | this.words[i] = this.words[i + s];
|
2033 | }
|
2034 | } else {
|
2035 | this.words[0] = 0;
|
2036 | this.length = 1;
|
2037 | }
|
2038 |
|
2039 | var carry = 0;
|
2040 | for (i = this.length - 1; i >= 0 && (carry !== 0 || i >= h); i--) {
|
2041 | var word = this.words[i] | 0;
|
2042 | this.words[i] = (carry << (26 - r)) | (word >>> r);
|
2043 | carry = word & mask;
|
2044 | }
|
2045 |
|
2046 |
|
2047 | if (maskedWords && carry !== 0) {
|
2048 | maskedWords.words[maskedWords.length++] = carry;
|
2049 | }
|
2050 |
|
2051 | if (this.length === 0) {
|
2052 | this.words[0] = 0;
|
2053 | this.length = 1;
|
2054 | }
|
2055 |
|
2056 | return this.strip();
|
2057 | };
|
2058 |
|
2059 | BN.prototype.ishrn = function ishrn (bits, hint, extended) {
|
2060 |
|
2061 | assert(this.negative === 0);
|
2062 | return this.iushrn(bits, hint, extended);
|
2063 | };
|
2064 |
|
2065 |
|
2066 | BN.prototype.shln = function shln (bits) {
|
2067 | return this.clone().ishln(bits);
|
2068 | };
|
2069 |
|
2070 | BN.prototype.ushln = function ushln (bits) {
|
2071 | return this.clone().iushln(bits);
|
2072 | };
|
2073 |
|
2074 |
|
2075 | BN.prototype.shrn = function shrn (bits) {
|
2076 | return this.clone().ishrn(bits);
|
2077 | };
|
2078 |
|
2079 | BN.prototype.ushrn = function ushrn (bits) {
|
2080 | return this.clone().iushrn(bits);
|
2081 | };
|
2082 |
|
2083 |
|
2084 | BN.prototype.testn = function testn (bit) {
|
2085 | assert(typeof bit === 'number' && bit >= 0);
|
2086 | var r = bit % 26;
|
2087 | var s = (bit - r) / 26;
|
2088 | var q = 1 << r;
|
2089 |
|
2090 |
|
2091 | if (this.length <= s) return false;
|
2092 |
|
2093 |
|
2094 | var w = this.words[s];
|
2095 |
|
2096 | return !!(w & q);
|
2097 | };
|
2098 |
|
2099 |
|
2100 | BN.prototype.imaskn = function imaskn (bits) {
|
2101 | assert(typeof bits === 'number' && bits >= 0);
|
2102 | var r = bits % 26;
|
2103 | var s = (bits - r) / 26;
|
2104 |
|
2105 | assert(this.negative === 0, 'imaskn works only with positive numbers');
|
2106 |
|
2107 | if (this.length <= s) {
|
2108 | return this;
|
2109 | }
|
2110 |
|
2111 | if (r !== 0) {
|
2112 | s++;
|
2113 | }
|
2114 | this.length = Math.min(s, this.length);
|
2115 |
|
2116 | if (r !== 0) {
|
2117 | var mask = 0x3ffffff ^ ((0x3ffffff >>> r) << r);
|
2118 | this.words[this.length - 1] &= mask;
|
2119 | }
|
2120 |
|
2121 | return this.strip();
|
2122 | };
|
2123 |
|
2124 |
|
2125 | BN.prototype.maskn = function maskn (bits) {
|
2126 | return this.clone().imaskn(bits);
|
2127 | };
|
2128 |
|
2129 |
|
2130 | BN.prototype.iaddn = function iaddn (num) {
|
2131 | assert(typeof num === 'number');
|
2132 | assert(num < 0x4000000);
|
2133 | if (num < 0) return this.isubn(-num);
|
2134 |
|
2135 |
|
2136 | if (this.negative !== 0) {
|
2137 | if (this.length === 1 && (this.words[0] | 0) < num) {
|
2138 | this.words[0] = num - (this.words[0] | 0);
|
2139 | this.negative = 0;
|
2140 | return this;
|
2141 | }
|
2142 |
|
2143 | this.negative = 0;
|
2144 | this.isubn(num);
|
2145 | this.negative = 1;
|
2146 | return this;
|
2147 | }
|
2148 |
|
2149 |
|
2150 | return this._iaddn(num);
|
2151 | };
|
2152 |
|
2153 | BN.prototype._iaddn = function _iaddn (num) {
|
2154 | this.words[0] += num;
|
2155 |
|
2156 |
|
2157 | for (var i = 0; i < this.length && this.words[i] >= 0x4000000; i++) {
|
2158 | this.words[i] -= 0x4000000;
|
2159 | if (i === this.length - 1) {
|
2160 | this.words[i + 1] = 1;
|
2161 | } else {
|
2162 | this.words[i + 1]++;
|
2163 | }
|
2164 | }
|
2165 | this.length = Math.max(this.length, i + 1);
|
2166 |
|
2167 | return this;
|
2168 | };
|
2169 |
|
2170 |
|
2171 | BN.prototype.isubn = function isubn (num) {
|
2172 | assert(typeof num === 'number');
|
2173 | assert(num < 0x4000000);
|
2174 | if (num < 0) return this.iaddn(-num);
|
2175 |
|
2176 | if (this.negative !== 0) {
|
2177 | this.negative = 0;
|
2178 | this.iaddn(num);
|
2179 | this.negative = 1;
|
2180 | return this;
|
2181 | }
|
2182 |
|
2183 | this.words[0] -= num;
|
2184 |
|
2185 | if (this.length === 1 && this.words[0] < 0) {
|
2186 | this.words[0] = -this.words[0];
|
2187 | this.negative = 1;
|
2188 | } else {
|
2189 |
|
2190 | for (var i = 0; i < this.length && this.words[i] < 0; i++) {
|
2191 | this.words[i] += 0x4000000;
|
2192 | this.words[i + 1] -= 1;
|
2193 | }
|
2194 | }
|
2195 |
|
2196 | return this.strip();
|
2197 | };
|
2198 |
|
2199 | BN.prototype.addn = function addn (num) {
|
2200 | return this.clone().iaddn(num);
|
2201 | };
|
2202 |
|
2203 | BN.prototype.subn = function subn (num) {
|
2204 | return this.clone().isubn(num);
|
2205 | };
|
2206 |
|
2207 | BN.prototype.iabs = function iabs () {
|
2208 | this.negative = 0;
|
2209 |
|
2210 | return this;
|
2211 | };
|
2212 |
|
2213 | BN.prototype.abs = function abs () {
|
2214 | return this.clone().iabs();
|
2215 | };
|
2216 |
|
2217 | BN.prototype._ishlnsubmul = function _ishlnsubmul (num, mul, shift) {
|
2218 | var len = num.length + shift;
|
2219 | var i;
|
2220 |
|
2221 | this._expand(len);
|
2222 |
|
2223 | var w;
|
2224 | var carry = 0;
|
2225 | for (i = 0; i < num.length; i++) {
|
2226 | w = (this.words[i + shift] | 0) + carry;
|
2227 | var right = (num.words[i] | 0) * mul;
|
2228 | w -= right & 0x3ffffff;
|
2229 | carry = (w >> 26) - ((right / 0x4000000) | 0);
|
2230 | this.words[i + shift] = w & 0x3ffffff;
|
2231 | }
|
2232 | for (; i < this.length - shift; i++) {
|
2233 | w = (this.words[i + shift] | 0) + carry;
|
2234 | carry = w >> 26;
|
2235 | this.words[i + shift] = w & 0x3ffffff;
|
2236 | }
|
2237 |
|
2238 | if (carry === 0) return this.strip();
|
2239 |
|
2240 |
|
2241 | assert(carry === -1);
|
2242 | carry = 0;
|
2243 | for (i = 0; i < this.length; i++) {
|
2244 | w = -(this.words[i] | 0) + carry;
|
2245 | carry = w >> 26;
|
2246 | this.words[i] = w & 0x3ffffff;
|
2247 | }
|
2248 | this.negative = 1;
|
2249 |
|
2250 | return this.strip();
|
2251 | };
|
2252 |
|
2253 | BN.prototype._wordDiv = function _wordDiv (num, mode) {
|
2254 | var shift = this.length - num.length;
|
2255 |
|
2256 | var a = this.clone();
|
2257 | var b = num;
|
2258 |
|
2259 |
|
2260 | var bhi = b.words[b.length - 1] | 0;
|
2261 | var bhiBits = this._countBits(bhi);
|
2262 | shift = 26 - bhiBits;
|
2263 | if (shift !== 0) {
|
2264 | b = b.ushln(shift);
|
2265 | a.iushln(shift);
|
2266 | bhi = b.words[b.length - 1] | 0;
|
2267 | }
|
2268 |
|
2269 |
|
2270 | var m = a.length - b.length;
|
2271 | var q;
|
2272 |
|
2273 | if (mode !== 'mod') {
|
2274 | q = new BN(null);
|
2275 | q.length = m + 1;
|
2276 | q.words = new Array(q.length);
|
2277 | for (var i = 0; i < q.length; i++) {
|
2278 | q.words[i] = 0;
|
2279 | }
|
2280 | }
|
2281 |
|
2282 | var diff = a.clone()._ishlnsubmul(b, 1, m);
|
2283 | if (diff.negative === 0) {
|
2284 | a = diff;
|
2285 | if (q) {
|
2286 | q.words[m] = 1;
|
2287 | }
|
2288 | }
|
2289 |
|
2290 | for (var j = m - 1; j >= 0; j--) {
|
2291 | var qj = (a.words[b.length + j] | 0) * 0x4000000 +
|
2292 | (a.words[b.length + j - 1] | 0);
|
2293 |
|
2294 |
|
2295 |
|
2296 | qj = Math.min((qj / bhi) | 0, 0x3ffffff);
|
2297 |
|
2298 | a._ishlnsubmul(b, qj, j);
|
2299 | while (a.negative !== 0) {
|
2300 | qj--;
|
2301 | a.negative = 0;
|
2302 | a._ishlnsubmul(b, 1, j);
|
2303 | if (!a.isZero()) {
|
2304 | a.negative ^= 1;
|
2305 | }
|
2306 | }
|
2307 | if (q) {
|
2308 | q.words[j] = qj;
|
2309 | }
|
2310 | }
|
2311 | if (q) {
|
2312 | q.strip();
|
2313 | }
|
2314 | a.strip();
|
2315 |
|
2316 |
|
2317 | if (mode !== 'div' && shift !== 0) {
|
2318 | a.iushrn(shift);
|
2319 | }
|
2320 |
|
2321 | return {
|
2322 | div: q || null,
|
2323 | mod: a
|
2324 | };
|
2325 | };
|
2326 |
|
2327 |
|
2328 |
|
2329 |
|
2330 |
|
2331 | BN.prototype.divmod = function divmod (num, mode, positive) {
|
2332 | assert(!num.isZero());
|
2333 |
|
2334 | if (this.isZero()) {
|
2335 | return {
|
2336 | div: new BN(0),
|
2337 | mod: new BN(0)
|
2338 | };
|
2339 | }
|
2340 |
|
2341 | var div, mod, res;
|
2342 | if (this.negative !== 0 && num.negative === 0) {
|
2343 | res = this.neg().divmod(num, mode);
|
2344 |
|
2345 | if (mode !== 'mod') {
|
2346 | div = res.div.neg();
|
2347 | }
|
2348 |
|
2349 | if (mode !== 'div') {
|
2350 | mod = res.mod.neg();
|
2351 | if (positive && mod.negative !== 0) {
|
2352 | mod.iadd(num);
|
2353 | }
|
2354 | }
|
2355 |
|
2356 | return {
|
2357 | div: div,
|
2358 | mod: mod
|
2359 | };
|
2360 | }
|
2361 |
|
2362 | if (this.negative === 0 && num.negative !== 0) {
|
2363 | res = this.divmod(num.neg(), mode);
|
2364 |
|
2365 | if (mode !== 'mod') {
|
2366 | div = res.div.neg();
|
2367 | }
|
2368 |
|
2369 | return {
|
2370 | div: div,
|
2371 | mod: res.mod
|
2372 | };
|
2373 | }
|
2374 |
|
2375 | if ((this.negative & num.negative) !== 0) {
|
2376 | res = this.neg().divmod(num.neg(), mode);
|
2377 |
|
2378 | if (mode !== 'div') {
|
2379 | mod = res.mod.neg();
|
2380 | if (positive && mod.negative !== 0) {
|
2381 | mod.isub(num);
|
2382 | }
|
2383 | }
|
2384 |
|
2385 | return {
|
2386 | div: res.div,
|
2387 | mod: mod
|
2388 | };
|
2389 | }
|
2390 |
|
2391 |
|
2392 |
|
2393 |
|
2394 | if (num.length > this.length || this.cmp(num) < 0) {
|
2395 | return {
|
2396 | div: new BN(0),
|
2397 | mod: this
|
2398 | };
|
2399 | }
|
2400 |
|
2401 |
|
2402 | if (num.length === 1) {
|
2403 | if (mode === 'div') {
|
2404 | return {
|
2405 | div: this.divn(num.words[0]),
|
2406 | mod: null
|
2407 | };
|
2408 | }
|
2409 |
|
2410 | if (mode === 'mod') {
|
2411 | return {
|
2412 | div: null,
|
2413 | mod: new BN(this.modn(num.words[0]))
|
2414 | };
|
2415 | }
|
2416 |
|
2417 | return {
|
2418 | div: this.divn(num.words[0]),
|
2419 | mod: new BN(this.modn(num.words[0]))
|
2420 | };
|
2421 | }
|
2422 |
|
2423 | return this._wordDiv(num, mode);
|
2424 | };
|
2425 |
|
2426 |
|
2427 | BN.prototype.div = function div (num) {
|
2428 | return this.divmod(num, 'div', false).div;
|
2429 | };
|
2430 |
|
2431 |
|
2432 | BN.prototype.mod = function mod (num) {
|
2433 | return this.divmod(num, 'mod', false).mod;
|
2434 | };
|
2435 |
|
2436 | BN.prototype.umod = function umod (num) {
|
2437 | return this.divmod(num, 'mod', true).mod;
|
2438 | };
|
2439 |
|
2440 |
|
2441 | BN.prototype.divRound = function divRound (num) {
|
2442 | var dm = this.divmod(num);
|
2443 |
|
2444 |
|
2445 | if (dm.mod.isZero()) return dm.div;
|
2446 |
|
2447 | var mod = dm.div.negative !== 0 ? dm.mod.isub(num) : dm.mod;
|
2448 |
|
2449 | var half = num.ushrn(1);
|
2450 | var r2 = num.andln(1);
|
2451 | var cmp = mod.cmp(half);
|
2452 |
|
2453 |
|
2454 | if (cmp < 0 || r2 === 1 && cmp === 0) return dm.div;
|
2455 |
|
2456 |
|
2457 | return dm.div.negative !== 0 ? dm.div.isubn(1) : dm.div.iaddn(1);
|
2458 | };
|
2459 |
|
2460 | BN.prototype.modn = function modn (num) {
|
2461 | assert(num <= 0x3ffffff);
|
2462 | var p = (1 << 26) % num;
|
2463 |
|
2464 | var acc = 0;
|
2465 | for (var i = this.length - 1; i >= 0; i--) {
|
2466 | acc = (p * acc + (this.words[i] | 0)) % num;
|
2467 | }
|
2468 |
|
2469 | return acc;
|
2470 | };
|
2471 |
|
2472 |
|
2473 | BN.prototype.idivn = function idivn (num) {
|
2474 | assert(num <= 0x3ffffff);
|
2475 |
|
2476 | var carry = 0;
|
2477 | for (var i = this.length - 1; i >= 0; i--) {
|
2478 | var w = (this.words[i] | 0) + carry * 0x4000000;
|
2479 | this.words[i] = (w / num) | 0;
|
2480 | carry = w % num;
|
2481 | }
|
2482 |
|
2483 | return this.strip();
|
2484 | };
|
2485 |
|
2486 | BN.prototype.divn = function divn (num) {
|
2487 | return this.clone().idivn(num);
|
2488 | };
|
2489 |
|
2490 | BN.prototype.egcd = function egcd (p) {
|
2491 | assert(p.negative === 0);
|
2492 | assert(!p.isZero());
|
2493 |
|
2494 | var x = this;
|
2495 | var y = p.clone();
|
2496 |
|
2497 | if (x.negative !== 0) {
|
2498 | x = x.umod(p);
|
2499 | } else {
|
2500 | x = x.clone();
|
2501 | }
|
2502 |
|
2503 |
|
2504 | var A = new BN(1);
|
2505 | var B = new BN(0);
|
2506 |
|
2507 |
|
2508 | var C = new BN(0);
|
2509 | var D = new BN(1);
|
2510 |
|
2511 | var g = 0;
|
2512 |
|
2513 | while (x.isEven() && y.isEven()) {
|
2514 | x.iushrn(1);
|
2515 | y.iushrn(1);
|
2516 | ++g;
|
2517 | }
|
2518 |
|
2519 | var yp = y.clone();
|
2520 | var xp = x.clone();
|
2521 |
|
2522 | while (!x.isZero()) {
|
2523 | for (var i = 0, im = 1; (x.words[0] & im) === 0 && i < 26; ++i, im <<= 1);
|
2524 | if (i > 0) {
|
2525 | x.iushrn(i);
|
2526 | while (i-- > 0) {
|
2527 | if (A.isOdd() || B.isOdd()) {
|
2528 | A.iadd(yp);
|
2529 | B.isub(xp);
|
2530 | }
|
2531 |
|
2532 | A.iushrn(1);
|
2533 | B.iushrn(1);
|
2534 | }
|
2535 | }
|
2536 |
|
2537 | for (var j = 0, jm = 1; (y.words[0] & jm) === 0 && j < 26; ++j, jm <<= 1);
|
2538 | if (j > 0) {
|
2539 | y.iushrn(j);
|
2540 | while (j-- > 0) {
|
2541 | if (C.isOdd() || D.isOdd()) {
|
2542 | C.iadd(yp);
|
2543 | D.isub(xp);
|
2544 | }
|
2545 |
|
2546 | C.iushrn(1);
|
2547 | D.iushrn(1);
|
2548 | }
|
2549 | }
|
2550 |
|
2551 | if (x.cmp(y) >= 0) {
|
2552 | x.isub(y);
|
2553 | A.isub(C);
|
2554 | B.isub(D);
|
2555 | } else {
|
2556 | y.isub(x);
|
2557 | C.isub(A);
|
2558 | D.isub(B);
|
2559 | }
|
2560 | }
|
2561 |
|
2562 | return {
|
2563 | a: C,
|
2564 | b: D,
|
2565 | gcd: y.iushln(g)
|
2566 | };
|
2567 | };
|
2568 |
|
2569 |
|
2570 |
|
2571 |
|
2572 | BN.prototype._invmp = function _invmp (p) {
|
2573 | assert(p.negative === 0);
|
2574 | assert(!p.isZero());
|
2575 |
|
2576 | var a = this;
|
2577 | var b = p.clone();
|
2578 |
|
2579 | if (a.negative !== 0) {
|
2580 | a = a.umod(p);
|
2581 | } else {
|
2582 | a = a.clone();
|
2583 | }
|
2584 |
|
2585 | var x1 = new BN(1);
|
2586 | var x2 = new BN(0);
|
2587 |
|
2588 | var delta = b.clone();
|
2589 |
|
2590 | while (a.cmpn(1) > 0 && b.cmpn(1) > 0) {
|
2591 | for (var i = 0, im = 1; (a.words[0] & im) === 0 && i < 26; ++i, im <<= 1);
|
2592 | if (i > 0) {
|
2593 | a.iushrn(i);
|
2594 | while (i-- > 0) {
|
2595 | if (x1.isOdd()) {
|
2596 | x1.iadd(delta);
|
2597 | }
|
2598 |
|
2599 | x1.iushrn(1);
|
2600 | }
|
2601 | }
|
2602 |
|
2603 | for (var j = 0, jm = 1; (b.words[0] & jm) === 0 && j < 26; ++j, jm <<= 1);
|
2604 | if (j > 0) {
|
2605 | b.iushrn(j);
|
2606 | while (j-- > 0) {
|
2607 | if (x2.isOdd()) {
|
2608 | x2.iadd(delta);
|
2609 | }
|
2610 |
|
2611 | x2.iushrn(1);
|
2612 | }
|
2613 | }
|
2614 |
|
2615 | if (a.cmp(b) >= 0) {
|
2616 | a.isub(b);
|
2617 | x1.isub(x2);
|
2618 | } else {
|
2619 | b.isub(a);
|
2620 | x2.isub(x1);
|
2621 | }
|
2622 | }
|
2623 |
|
2624 | var res;
|
2625 | if (a.cmpn(1) === 0) {
|
2626 | res = x1;
|
2627 | } else {
|
2628 | res = x2;
|
2629 | }
|
2630 |
|
2631 | if (res.cmpn(0) < 0) {
|
2632 | res.iadd(p);
|
2633 | }
|
2634 |
|
2635 | return res;
|
2636 | };
|
2637 |
|
2638 | BN.prototype.gcd = function gcd (num) {
|
2639 | if (this.isZero()) return num.abs();
|
2640 | if (num.isZero()) return this.abs();
|
2641 |
|
2642 | var a = this.clone();
|
2643 | var b = num.clone();
|
2644 | a.negative = 0;
|
2645 | b.negative = 0;
|
2646 |
|
2647 |
|
2648 | for (var shift = 0; a.isEven() && b.isEven(); shift++) {
|
2649 | a.iushrn(1);
|
2650 | b.iushrn(1);
|
2651 | }
|
2652 |
|
2653 | do {
|
2654 | while (a.isEven()) {
|
2655 | a.iushrn(1);
|
2656 | }
|
2657 | while (b.isEven()) {
|
2658 | b.iushrn(1);
|
2659 | }
|
2660 |
|
2661 | var r = a.cmp(b);
|
2662 | if (r < 0) {
|
2663 |
|
2664 | var t = a;
|
2665 | a = b;
|
2666 | b = t;
|
2667 | } else if (r === 0 || b.cmpn(1) === 0) {
|
2668 | break;
|
2669 | }
|
2670 |
|
2671 | a.isub(b);
|
2672 | } while (true);
|
2673 |
|
2674 | return b.iushln(shift);
|
2675 | };
|
2676 |
|
2677 |
|
2678 | BN.prototype.invm = function invm (num) {
|
2679 | return this.egcd(num).a.umod(num);
|
2680 | };
|
2681 |
|
2682 | BN.prototype.isEven = function isEven () {
|
2683 | return (this.words[0] & 1) === 0;
|
2684 | };
|
2685 |
|
2686 | BN.prototype.isOdd = function isOdd () {
|
2687 | return (this.words[0] & 1) === 1;
|
2688 | };
|
2689 |
|
2690 |
|
2691 | BN.prototype.andln = function andln (num) {
|
2692 | return this.words[0] & num;
|
2693 | };
|
2694 |
|
2695 |
|
2696 | BN.prototype.bincn = function bincn (bit) {
|
2697 | assert(typeof bit === 'number');
|
2698 | var r = bit % 26;
|
2699 | var s = (bit - r) / 26;
|
2700 | var q = 1 << r;
|
2701 |
|
2702 |
|
2703 | if (this.length <= s) {
|
2704 | this._expand(s + 1);
|
2705 | this.words[s] |= q;
|
2706 | return this;
|
2707 | }
|
2708 |
|
2709 |
|
2710 | var carry = q;
|
2711 | for (var i = s; carry !== 0 && i < this.length; i++) {
|
2712 | var w = this.words[i] | 0;
|
2713 | w += carry;
|
2714 | carry = w >>> 26;
|
2715 | w &= 0x3ffffff;
|
2716 | this.words[i] = w;
|
2717 | }
|
2718 | if (carry !== 0) {
|
2719 | this.words[i] = carry;
|
2720 | this.length++;
|
2721 | }
|
2722 | return this;
|
2723 | };
|
2724 |
|
2725 | BN.prototype.isZero = function isZero () {
|
2726 | return this.length === 1 && this.words[0] === 0;
|
2727 | };
|
2728 |
|
2729 | BN.prototype.cmpn = function cmpn (num) {
|
2730 | var negative = num < 0;
|
2731 |
|
2732 | if (this.negative !== 0 && !negative) return -1;
|
2733 | if (this.negative === 0 && negative) return 1;
|
2734 |
|
2735 | this.strip();
|
2736 |
|
2737 | var res;
|
2738 | if (this.length > 1) {
|
2739 | res = 1;
|
2740 | } else {
|
2741 | if (negative) {
|
2742 | num = -num;
|
2743 | }
|
2744 |
|
2745 | assert(num <= 0x3ffffff, 'Number is too big');
|
2746 |
|
2747 | var w = this.words[0] | 0;
|
2748 | res = w === num ? 0 : w < num ? -1 : 1;
|
2749 | }
|
2750 | if (this.negative !== 0) return -res | 0;
|
2751 | return res;
|
2752 | };
|
2753 |
|
2754 |
|
2755 |
|
2756 |
|
2757 |
|
2758 | BN.prototype.cmp = function cmp (num) {
|
2759 | if (this.negative !== 0 && num.negative === 0) return -1;
|
2760 | if (this.negative === 0 && num.negative !== 0) return 1;
|
2761 |
|
2762 | var res = this.ucmp(num);
|
2763 | if (this.negative !== 0) return -res | 0;
|
2764 | return res;
|
2765 | };
|
2766 |
|
2767 |
|
2768 | BN.prototype.ucmp = function ucmp (num) {
|
2769 |
|
2770 | if (this.length > num.length) return 1;
|
2771 | if (this.length < num.length) return -1;
|
2772 |
|
2773 | var res = 0;
|
2774 | for (var i = this.length - 1; i >= 0; i--) {
|
2775 | var a = this.words[i] | 0;
|
2776 | var b = num.words[i] | 0;
|
2777 |
|
2778 | if (a === b) continue;
|
2779 | if (a < b) {
|
2780 | res = -1;
|
2781 | } else if (a > b) {
|
2782 | res = 1;
|
2783 | }
|
2784 | break;
|
2785 | }
|
2786 | return res;
|
2787 | };
|
2788 |
|
2789 | BN.prototype.gtn = function gtn (num) {
|
2790 | return this.cmpn(num) === 1;
|
2791 | };
|
2792 |
|
2793 | BN.prototype.gt = function gt (num) {
|
2794 | return this.cmp(num) === 1;
|
2795 | };
|
2796 |
|
2797 | BN.prototype.gten = function gten (num) {
|
2798 | return this.cmpn(num) >= 0;
|
2799 | };
|
2800 |
|
2801 | BN.prototype.gte = function gte (num) {
|
2802 | return this.cmp(num) >= 0;
|
2803 | };
|
2804 |
|
2805 | BN.prototype.ltn = function ltn (num) {
|
2806 | return this.cmpn(num) === -1;
|
2807 | };
|
2808 |
|
2809 | BN.prototype.lt = function lt (num) {
|
2810 | return this.cmp(num) === -1;
|
2811 | };
|
2812 |
|
2813 | BN.prototype.lten = function lten (num) {
|
2814 | return this.cmpn(num) <= 0;
|
2815 | };
|
2816 |
|
2817 | BN.prototype.lte = function lte (num) {
|
2818 | return this.cmp(num) <= 0;
|
2819 | };
|
2820 |
|
2821 | BN.prototype.eqn = function eqn (num) {
|
2822 | return this.cmpn(num) === 0;
|
2823 | };
|
2824 |
|
2825 | BN.prototype.eq = function eq (num) {
|
2826 | return this.cmp(num) === 0;
|
2827 | };
|
2828 |
|
2829 |
|
2830 |
|
2831 |
|
2832 |
|
2833 | BN.red = function red (num) {
|
2834 | return new Red(num);
|
2835 | };
|
2836 |
|
2837 | BN.prototype.toRed = function toRed (ctx) {
|
2838 | assert(!this.red, 'Already a number in reduction context');
|
2839 | assert(this.negative === 0, 'red works only with positives');
|
2840 | return ctx.convertTo(this)._forceRed(ctx);
|
2841 | };
|
2842 |
|
2843 | BN.prototype.fromRed = function fromRed () {
|
2844 | assert(this.red, 'fromRed works only with numbers in reduction context');
|
2845 | return this.red.convertFrom(this);
|
2846 | };
|
2847 |
|
2848 | BN.prototype._forceRed = function _forceRed (ctx) {
|
2849 | this.red = ctx;
|
2850 | return this;
|
2851 | };
|
2852 |
|
2853 | BN.prototype.forceRed = function forceRed (ctx) {
|
2854 | assert(!this.red, 'Already a number in reduction context');
|
2855 | return this._forceRed(ctx);
|
2856 | };
|
2857 |
|
2858 | BN.prototype.redAdd = function redAdd (num) {
|
2859 | assert(this.red, 'redAdd works only with red numbers');
|
2860 | return this.red.add(this, num);
|
2861 | };
|
2862 |
|
2863 | BN.prototype.redIAdd = function redIAdd (num) {
|
2864 | assert(this.red, 'redIAdd works only with red numbers');
|
2865 | return this.red.iadd(this, num);
|
2866 | };
|
2867 |
|
2868 | BN.prototype.redSub = function redSub (num) {
|
2869 | assert(this.red, 'redSub works only with red numbers');
|
2870 | return this.red.sub(this, num);
|
2871 | };
|
2872 |
|
2873 | BN.prototype.redISub = function redISub (num) {
|
2874 | assert(this.red, 'redISub works only with red numbers');
|
2875 | return this.red.isub(this, num);
|
2876 | };
|
2877 |
|
2878 | BN.prototype.redShl = function redShl (num) {
|
2879 | assert(this.red, 'redShl works only with red numbers');
|
2880 | return this.red.shl(this, num);
|
2881 | };
|
2882 |
|
2883 | BN.prototype.redMul = function redMul (num) {
|
2884 | assert(this.red, 'redMul works only with red numbers');
|
2885 | this.red._verify2(this, num);
|
2886 | return this.red.mul(this, num);
|
2887 | };
|
2888 |
|
2889 | BN.prototype.redIMul = function redIMul (num) {
|
2890 | assert(this.red, 'redMul works only with red numbers');
|
2891 | this.red._verify2(this, num);
|
2892 | return this.red.imul(this, num);
|
2893 | };
|
2894 |
|
2895 | BN.prototype.redSqr = function redSqr () {
|
2896 | assert(this.red, 'redSqr works only with red numbers');
|
2897 | this.red._verify1(this);
|
2898 | return this.red.sqr(this);
|
2899 | };
|
2900 |
|
2901 | BN.prototype.redISqr = function redISqr () {
|
2902 | assert(this.red, 'redISqr works only with red numbers');
|
2903 | this.red._verify1(this);
|
2904 | return this.red.isqr(this);
|
2905 | };
|
2906 |
|
2907 |
|
2908 | BN.prototype.redSqrt = function redSqrt () {
|
2909 | assert(this.red, 'redSqrt works only with red numbers');
|
2910 | this.red._verify1(this);
|
2911 | return this.red.sqrt(this);
|
2912 | };
|
2913 |
|
2914 | BN.prototype.redInvm = function redInvm () {
|
2915 | assert(this.red, 'redInvm works only with red numbers');
|
2916 | this.red._verify1(this);
|
2917 | return this.red.invm(this);
|
2918 | };
|
2919 |
|
2920 |
|
2921 | BN.prototype.redNeg = function redNeg () {
|
2922 | assert(this.red, 'redNeg works only with red numbers');
|
2923 | this.red._verify1(this);
|
2924 | return this.red.neg(this);
|
2925 | };
|
2926 |
|
2927 | BN.prototype.redPow = function redPow (num) {
|
2928 | assert(this.red && !num.red, 'redPow(normalNum)');
|
2929 | this.red._verify1(this);
|
2930 | return this.red.pow(this, num);
|
2931 | };
|
2932 |
|
2933 |
|
2934 | var primes = {
|
2935 | k256: null,
|
2936 | p224: null,
|
2937 | p192: null,
|
2938 | p25519: null
|
2939 | };
|
2940 |
|
2941 |
|
2942 | function MPrime (name, p) {
|
2943 |
|
2944 | this.name = name;
|
2945 | this.p = new BN(p, 16);
|
2946 | this.n = this.p.bitLength();
|
2947 | this.k = new BN(1).iushln(this.n).isub(this.p);
|
2948 |
|
2949 | this.tmp = this._tmp();
|
2950 | }
|
2951 |
|
2952 | MPrime.prototype._tmp = function _tmp () {
|
2953 | var tmp = new BN(null);
|
2954 | tmp.words = new Array(Math.ceil(this.n / 13));
|
2955 | return tmp;
|
2956 | };
|
2957 |
|
2958 | MPrime.prototype.ireduce = function ireduce (num) {
|
2959 |
|
2960 |
|
2961 | var r = num;
|
2962 | var rlen;
|
2963 |
|
2964 | do {
|
2965 | this.split(r, this.tmp);
|
2966 | r = this.imulK(r);
|
2967 | r = r.iadd(this.tmp);
|
2968 | rlen = r.bitLength();
|
2969 | } while (rlen > this.n);
|
2970 |
|
2971 | var cmp = rlen < this.n ? -1 : r.ucmp(this.p);
|
2972 | if (cmp === 0) {
|
2973 | r.words[0] = 0;
|
2974 | r.length = 1;
|
2975 | } else if (cmp > 0) {
|
2976 | r.isub(this.p);
|
2977 | } else {
|
2978 | r.strip();
|
2979 | }
|
2980 |
|
2981 | return r;
|
2982 | };
|
2983 |
|
2984 | MPrime.prototype.split = function split (input, out) {
|
2985 | input.iushrn(this.n, 0, out);
|
2986 | };
|
2987 |
|
2988 | MPrime.prototype.imulK = function imulK (num) {
|
2989 | return num.imul(this.k);
|
2990 | };
|
2991 |
|
2992 | function K256 () {
|
2993 | MPrime.call(
|
2994 | this,
|
2995 | 'k256',
|
2996 | 'ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f');
|
2997 | }
|
2998 | inherits(K256, MPrime);
|
2999 |
|
3000 | K256.prototype.split = function split (input, output) {
|
3001 |
|
3002 | var mask = 0x3fffff;
|
3003 |
|
3004 | var outLen = Math.min(input.length, 9);
|
3005 | for (var i = 0; i < outLen; i++) {
|
3006 | output.words[i] = input.words[i];
|
3007 | }
|
3008 | output.length = outLen;
|
3009 |
|
3010 | if (input.length <= 9) {
|
3011 | input.words[0] = 0;
|
3012 | input.length = 1;
|
3013 | return;
|
3014 | }
|
3015 |
|
3016 |
|
3017 | var prev = input.words[9];
|
3018 | output.words[output.length++] = prev & mask;
|
3019 |
|
3020 | for (i = 10; i < input.length; i++) {
|
3021 | var next = input.words[i] | 0;
|
3022 | input.words[i - 10] = ((next & mask) << 4) | (prev >>> 22);
|
3023 | prev = next;
|
3024 | }
|
3025 | prev >>>= 22;
|
3026 | input.words[i - 10] = prev;
|
3027 | if (prev === 0 && input.length > 10) {
|
3028 | input.length -= 10;
|
3029 | } else {
|
3030 | input.length -= 9;
|
3031 | }
|
3032 | };
|
3033 |
|
3034 | K256.prototype.imulK = function imulK (num) {
|
3035 |
|
3036 | num.words[num.length] = 0;
|
3037 | num.words[num.length + 1] = 0;
|
3038 | num.length += 2;
|
3039 |
|
3040 |
|
3041 | var lo = 0;
|
3042 | for (var i = 0; i < num.length; i++) {
|
3043 | var w = num.words[i] | 0;
|
3044 | lo += w * 0x3d1;
|
3045 | num.words[i] = lo & 0x3ffffff;
|
3046 | lo = w * 0x40 + ((lo / 0x4000000) | 0);
|
3047 | }
|
3048 |
|
3049 |
|
3050 | if (num.words[num.length - 1] === 0) {
|
3051 | num.length--;
|
3052 | if (num.words[num.length - 1] === 0) {
|
3053 | num.length--;
|
3054 | }
|
3055 | }
|
3056 | return num;
|
3057 | };
|
3058 |
|
3059 | function P224 () {
|
3060 | MPrime.call(
|
3061 | this,
|
3062 | 'p224',
|
3063 | 'ffffffff ffffffff ffffffff ffffffff 00000000 00000000 00000001');
|
3064 | }
|
3065 | inherits(P224, MPrime);
|
3066 |
|
3067 | function P192 () {
|
3068 | MPrime.call(
|
3069 | this,
|
3070 | 'p192',
|
3071 | 'ffffffff ffffffff ffffffff fffffffe ffffffff ffffffff');
|
3072 | }
|
3073 | inherits(P192, MPrime);
|
3074 |
|
3075 | function P25519 () {
|
3076 |
|
3077 | MPrime.call(
|
3078 | this,
|
3079 | '25519',
|
3080 | '7fffffffffffffff ffffffffffffffff ffffffffffffffff ffffffffffffffed');
|
3081 | }
|
3082 | inherits(P25519, MPrime);
|
3083 |
|
3084 | P25519.prototype.imulK = function imulK (num) {
|
3085 |
|
3086 | var carry = 0;
|
3087 | for (var i = 0; i < num.length; i++) {
|
3088 | var hi = (num.words[i] | 0) * 0x13 + carry;
|
3089 | var lo = hi & 0x3ffffff;
|
3090 | hi >>>= 26;
|
3091 |
|
3092 | num.words[i] = lo;
|
3093 | carry = hi;
|
3094 | }
|
3095 | if (carry !== 0) {
|
3096 | num.words[num.length++] = carry;
|
3097 | }
|
3098 | return num;
|
3099 | };
|
3100 |
|
3101 |
|
3102 | BN._prime = function prime (name) {
|
3103 |
|
3104 | if (primes[name]) return primes[name];
|
3105 |
|
3106 | var prime;
|
3107 | if (name === 'k256') {
|
3108 | prime = new K256();
|
3109 | } else if (name === 'p224') {
|
3110 | prime = new P224();
|
3111 | } else if (name === 'p192') {
|
3112 | prime = new P192();
|
3113 | } else if (name === 'p25519') {
|
3114 | prime = new P25519();
|
3115 | } else {
|
3116 | throw new Error('Unknown prime ' + name);
|
3117 | }
|
3118 | primes[name] = prime;
|
3119 |
|
3120 | return prime;
|
3121 | };
|
3122 |
|
3123 |
|
3124 |
|
3125 |
|
3126 | function Red (m) {
|
3127 | if (typeof m === 'string') {
|
3128 | var prime = BN._prime(m);
|
3129 | this.m = prime.p;
|
3130 | this.prime = prime;
|
3131 | } else {
|
3132 | assert(m.gtn(1), 'modulus must be greater than 1');
|
3133 | this.m = m;
|
3134 | this.prime = null;
|
3135 | }
|
3136 | }
|
3137 |
|
3138 | Red.prototype._verify1 = function _verify1 (a) {
|
3139 | assert(a.negative === 0, 'red works only with positives');
|
3140 | assert(a.red, 'red works only with red numbers');
|
3141 | };
|
3142 |
|
3143 | Red.prototype._verify2 = function _verify2 (a, b) {
|
3144 | assert((a.negative | b.negative) === 0, 'red works only with positives');
|
3145 | assert(a.red && a.red === b.red,
|
3146 | 'red works only with red numbers');
|
3147 | };
|
3148 |
|
3149 | Red.prototype.imod = function imod (a) {
|
3150 | if (this.prime) return this.prime.ireduce(a)._forceRed(this);
|
3151 | return a.umod(this.m)._forceRed(this);
|
3152 | };
|
3153 |
|
3154 | Red.prototype.neg = function neg (a) {
|
3155 | if (a.isZero()) {
|
3156 | return a.clone();
|
3157 | }
|
3158 |
|
3159 | return this.m.sub(a)._forceRed(this);
|
3160 | };
|
3161 |
|
3162 | Red.prototype.add = function add (a, b) {
|
3163 | this._verify2(a, b);
|
3164 |
|
3165 | var res = a.add(b);
|
3166 | if (res.cmp(this.m) >= 0) {
|
3167 | res.isub(this.m);
|
3168 | }
|
3169 | return res._forceRed(this);
|
3170 | };
|
3171 |
|
3172 | Red.prototype.iadd = function iadd (a, b) {
|
3173 | this._verify2(a, b);
|
3174 |
|
3175 | var res = a.iadd(b);
|
3176 | if (res.cmp(this.m) >= 0) {
|
3177 | res.isub(this.m);
|
3178 | }
|
3179 | return res;
|
3180 | };
|
3181 |
|
3182 | Red.prototype.sub = function sub (a, b) {
|
3183 | this._verify2(a, b);
|
3184 |
|
3185 | var res = a.sub(b);
|
3186 | if (res.cmpn(0) < 0) {
|
3187 | res.iadd(this.m);
|
3188 | }
|
3189 | return res._forceRed(this);
|
3190 | };
|
3191 |
|
3192 | Red.prototype.isub = function isub (a, b) {
|
3193 | this._verify2(a, b);
|
3194 |
|
3195 | var res = a.isub(b);
|
3196 | if (res.cmpn(0) < 0) {
|
3197 | res.iadd(this.m);
|
3198 | }
|
3199 | return res;
|
3200 | };
|
3201 |
|
3202 | Red.prototype.shl = function shl (a, num) {
|
3203 | this._verify1(a);
|
3204 | return this.imod(a.ushln(num));
|
3205 | };
|
3206 |
|
3207 | Red.prototype.imul = function imul (a, b) {
|
3208 | this._verify2(a, b);
|
3209 | return this.imod(a.imul(b));
|
3210 | };
|
3211 |
|
3212 | Red.prototype.mul = function mul (a, b) {
|
3213 | this._verify2(a, b);
|
3214 | return this.imod(a.mul(b));
|
3215 | };
|
3216 |
|
3217 | Red.prototype.isqr = function isqr (a) {
|
3218 | return this.imul(a, a.clone());
|
3219 | };
|
3220 |
|
3221 | Red.prototype.sqr = function sqr (a) {
|
3222 | return this.mul(a, a);
|
3223 | };
|
3224 |
|
3225 | Red.prototype.sqrt = function sqrt (a) {
|
3226 | if (a.isZero()) return a.clone();
|
3227 |
|
3228 | var mod3 = this.m.andln(3);
|
3229 | assert(mod3 % 2 === 1);
|
3230 |
|
3231 |
|
3232 | if (mod3 === 3) {
|
3233 | var pow = this.m.add(new BN(1)).iushrn(2);
|
3234 | return this.pow(a, pow);
|
3235 | }
|
3236 |
|
3237 |
|
3238 |
|
3239 |
|
3240 | var q = this.m.subn(1);
|
3241 | var s = 0;
|
3242 | while (!q.isZero() && q.andln(1) === 0) {
|
3243 | s++;
|
3244 | q.iushrn(1);
|
3245 | }
|
3246 | assert(!q.isZero());
|
3247 |
|
3248 | var one = new BN(1).toRed(this);
|
3249 | var nOne = one.redNeg();
|
3250 |
|
3251 |
|
3252 |
|
3253 | var lpow = this.m.subn(1).iushrn(1);
|
3254 | var z = this.m.bitLength();
|
3255 | z = new BN(2 * z * z).toRed(this);
|
3256 |
|
3257 | while (this.pow(z, lpow).cmp(nOne) !== 0) {
|
3258 | z.redIAdd(nOne);
|
3259 | }
|
3260 |
|
3261 | var c = this.pow(z, q);
|
3262 | var r = this.pow(a, q.addn(1).iushrn(1));
|
3263 | var t = this.pow(a, q);
|
3264 | var m = s;
|
3265 | while (t.cmp(one) !== 0) {
|
3266 | var tmp = t;
|
3267 | for (var i = 0; tmp.cmp(one) !== 0; i++) {
|
3268 | tmp = tmp.redSqr();
|
3269 | }
|
3270 | assert(i < m);
|
3271 | var b = this.pow(c, new BN(1).iushln(m - i - 1));
|
3272 |
|
3273 | r = r.redMul(b);
|
3274 | c = b.redSqr();
|
3275 | t = t.redMul(c);
|
3276 | m = i;
|
3277 | }
|
3278 |
|
3279 | return r;
|
3280 | };
|
3281 |
|
3282 | Red.prototype.invm = function invm (a) {
|
3283 | var inv = a._invmp(this.m);
|
3284 | if (inv.negative !== 0) {
|
3285 | inv.negative = 0;
|
3286 | return this.imod(inv).redNeg();
|
3287 | } else {
|
3288 | return this.imod(inv);
|
3289 | }
|
3290 | };
|
3291 |
|
3292 | Red.prototype.pow = function pow (a, num) {
|
3293 | if (num.isZero()) return new BN(1).toRed(this);
|
3294 | if (num.cmpn(1) === 0) return a.clone();
|
3295 |
|
3296 | var windowSize = 4;
|
3297 | var wnd = new Array(1 << windowSize);
|
3298 | wnd[0] = new BN(1).toRed(this);
|
3299 | wnd[1] = a;
|
3300 | for (var i = 2; i < wnd.length; i++) {
|
3301 | wnd[i] = this.mul(wnd[i - 1], a);
|
3302 | }
|
3303 |
|
3304 | var res = wnd[0];
|
3305 | var current = 0;
|
3306 | var currentLen = 0;
|
3307 | var start = num.bitLength() % 26;
|
3308 | if (start === 0) {
|
3309 | start = 26;
|
3310 | }
|
3311 |
|
3312 | for (i = num.length - 1; i >= 0; i--) {
|
3313 | var word = num.words[i];
|
3314 | for (var j = start - 1; j >= 0; j--) {
|
3315 | var bit = (word >> j) & 1;
|
3316 | if (res !== wnd[0]) {
|
3317 | res = this.sqr(res);
|
3318 | }
|
3319 |
|
3320 | if (bit === 0 && current === 0) {
|
3321 | currentLen = 0;
|
3322 | continue;
|
3323 | }
|
3324 |
|
3325 | current <<= 1;
|
3326 | current |= bit;
|
3327 | currentLen++;
|
3328 | if (currentLen !== windowSize && (i !== 0 || j !== 0)) continue;
|
3329 |
|
3330 | res = this.mul(res, wnd[current]);
|
3331 | currentLen = 0;
|
3332 | current = 0;
|
3333 | }
|
3334 | start = 26;
|
3335 | }
|
3336 |
|
3337 | return res;
|
3338 | };
|
3339 |
|
3340 | Red.prototype.convertTo = function convertTo (num) {
|
3341 | var r = num.umod(this.m);
|
3342 |
|
3343 | return r === num ? r.clone() : r;
|
3344 | };
|
3345 |
|
3346 | Red.prototype.convertFrom = function convertFrom (num) {
|
3347 | var res = num.clone();
|
3348 | res.red = null;
|
3349 | return res;
|
3350 | };
|
3351 |
|
3352 |
|
3353 |
|
3354 |
|
3355 |
|
3356 | BN.mont = function mont (num) {
|
3357 | return new Mont(num);
|
3358 | };
|
3359 |
|
3360 | function Mont (m) {
|
3361 | Red.call(this, m);
|
3362 |
|
3363 | this.shift = this.m.bitLength();
|
3364 | if (this.shift % 26 !== 0) {
|
3365 | this.shift += 26 - (this.shift % 26);
|
3366 | }
|
3367 |
|
3368 | this.r = new BN(1).iushln(this.shift);
|
3369 | this.r2 = this.imod(this.r.sqr());
|
3370 | this.rinv = this.r._invmp(this.m);
|
3371 |
|
3372 | this.minv = this.rinv.mul(this.r).isubn(1).div(this.m);
|
3373 | this.minv = this.minv.umod(this.r);
|
3374 | this.minv = this.r.sub(this.minv);
|
3375 | }
|
3376 | inherits(Mont, Red);
|
3377 |
|
3378 | Mont.prototype.convertTo = function convertTo (num) {
|
3379 | return this.imod(num.ushln(this.shift));
|
3380 | };
|
3381 |
|
3382 | Mont.prototype.convertFrom = function convertFrom (num) {
|
3383 | var r = this.imod(num.mul(this.rinv));
|
3384 | r.red = null;
|
3385 | return r;
|
3386 | };
|
3387 |
|
3388 | Mont.prototype.imul = function imul (a, b) {
|
3389 | if (a.isZero() || b.isZero()) {
|
3390 | a.words[0] = 0;
|
3391 | a.length = 1;
|
3392 | return a;
|
3393 | }
|
3394 |
|
3395 | var t = a.imul(b);
|
3396 | var c = t.maskn(this.shift).mul(this.minv).imaskn(this.shift).mul(this.m);
|
3397 | var u = t.isub(c).iushrn(this.shift);
|
3398 | var res = u;
|
3399 |
|
3400 | if (u.cmp(this.m) >= 0) {
|
3401 | res = u.isub(this.m);
|
3402 | } else if (u.cmpn(0) < 0) {
|
3403 | res = u.iadd(this.m);
|
3404 | }
|
3405 |
|
3406 | return res._forceRed(this);
|
3407 | };
|
3408 |
|
3409 | Mont.prototype.mul = function mul (a, b) {
|
3410 | if (a.isZero() || b.isZero()) return new BN(0)._forceRed(this);
|
3411 |
|
3412 | var t = a.mul(b);
|
3413 | var c = t.maskn(this.shift).mul(this.minv).imaskn(this.shift).mul(this.m);
|
3414 | var u = t.isub(c).iushrn(this.shift);
|
3415 | var res = u;
|
3416 | if (u.cmp(this.m) >= 0) {
|
3417 | res = u.isub(this.m);
|
3418 | } else if (u.cmpn(0) < 0) {
|
3419 | res = u.iadd(this.m);
|
3420 | }
|
3421 |
|
3422 | return res._forceRed(this);
|
3423 | };
|
3424 |
|
3425 | Mont.prototype.invm = function invm (a) {
|
3426 |
|
3427 | var res = this.imod(a._invmp(this.m).mul(this.r2));
|
3428 | return res._forceRed(this);
|
3429 | };
|
3430 | })(module, commonjsGlobal);
|
3431 | });
|
3432 |
|
3433 | export default bn;
|
3434 | export { bn as __moduleExports };
|