websnark/src/build_multiexp.js
src/build_multiexp.jsRaw
1/*
2 Copyright 2019 0KIMS association.
3
4 This file is part of websnark (Web Assembly zkSnark Prover).
5
6 websnark is a free software: you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 websnark is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with websnark. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20module.exports = function buildMultiexp(module, prefix, curvePrefix, pointFieldPrefix, scalarPrefix) {
21
22 const pointFieldN64 = module.modules[pointFieldPrefix].n64;
23 const pointFieldN8 = pointFieldN64*8;
24 const pointN64 = module.modules[curvePrefix].n64;
25 const pointN8 = pointN64*8;
26 const scalarN64 = module.modules[scalarPrefix].n64;
27 const scalarN8 = scalarN64*8;
28
29
30 function buildPackBits() {
31 const f = module.addFunction(prefix+"__packbits");
32 f.addParam("pscalars", "i32");
33 f.addParam("w", "i32"); // 8 max
34 f.addParam("pr", "i32"); // P to result scalarN8*8 bytes
35 f.addLocal("i", "i32");
36 f.addLocal("j", "i32");
37 f.addLocal("w1", "i64");
38 f.addLocal("w2", "i64");
39
40 const c = f.getCodeBuilder();
41
42 f.addCode(c.setLocal("i", c.i32_const(0)));
43 f.addCode(c.block(c.loop(
44 c.br_if(
45 1,
46 c.i32_eq(
47 c.getLocal("i"),
48 c.i32_const(scalarN8)
49 )
50 ),
51
52 c.setLocal("w2", c.i64_const(0)),
53
54 c.setLocal("j", c.i32_const(0)),
55
56 c.block(c.loop(
57 c.br_if(
58 1,
59 c.i32_eq(
60 c.getLocal("j"),
61 c.getLocal("w")
62 )
63 ),
64
65 c.setLocal(
66 "w1",
67 c.i64_load8_u(
68 c.i32_add(
69 c.getLocal("pscalars"),
70 c.i32_add(
71 c.i32_mul(
72 c.getLocal("j"),
73 c.i32_const(scalarN8)
74 ),
75 c.getLocal("i")
76 )
77 )
78 )
79 ),
80
81 c.setLocal(
82 "w1",
83 c.i64_and(
84 c.i64_or(
85 c.getLocal("w1"),
86 c.i64_shl(
87 c.getLocal("w1"),
88 c.i64_const(28)
89 )
90 ),
91 c.i64_const("0x0000000F0000000F")
92 )
93 ),
94
95 c.setLocal(
96 "w1",
97 c.i64_and(
98 c.i64_or(
99 c.getLocal("w1"),
100 c.i64_shl(
101 c.getLocal("w1"),
102 c.i64_const(14)
103 )
104 ),
105 c.i64_const("0x0003000300030003")
106 )
107 ),
108
109 c.setLocal(
110 "w1",
111 c.i64_and(
112 c.i64_or(
113 c.getLocal("w1"),
114 c.i64_shl(
115 c.getLocal("w1"),
116 c.i64_const(7)
117 )
118 ),
119 c.i64_const("0x0101010101010101")
120 )
121 ),
122
123 c.setLocal(
124 "w2",
125 c.i64_or(
126 c.getLocal("w2"),
127 c.i64_shl(
128 c.getLocal("w1"),
129 c.i64_extend_i32_u(c.getLocal("j"))
130 )
131 )
132 ),
133
134
135 c.setLocal("j", c.i32_add(c.getLocal("j"), c.i32_const(1))),
136 c.br(0)
137 )),
138
139 c.i64_store(
140 c.i32_add(
141 c.getLocal("pr"),
142 c.i32_mul(
143 c.getLocal("i"),
144 c.i32_const(8)
145 )
146 ),
147 c.getLocal("w2")
148 ),
149
150 c.setLocal("i", c.i32_add(c.getLocal("i"), c.i32_const(1))),
151 c.br(0)
152 )));
153
154
155 }
156
157 const c1 = [];
158 const c2 = [];
159
160 function nbits(_b) {
161 let c=0;
162 let r=_b;
163 while(r) {
164 if (r&1) c++;
165 r = r>>1;
166 }
167 return c;
168 }
169
170 function split(_b) {
171 const nb1 = nbits(_b) >> 1;
172 let r = _b;
173 let c = 0;
174 if (nb1 == 0) return null;
175 let mask = 0xFFFFFFFF;
176 while (c<nb1) {
177 if (r&1) c++;
178 mask = mask << 1;
179 r = r>>1;
180 }
181 return [(_b & mask), (_b & (~mask))];
182 }
183
184 for (let i=0; i<256; i++) {
185 const a = split(i);
186 if (a) {
187 c1[i] = a[0];
188 c2[i] = a[1];
189 } else {
190 c1[i] = 0;
191 c2[i] = 0;
192 }
193 }
194
195 const ptable = module.alloc(pointN8*256);
196 const pset = module.alloc(32);
197 const composite1 = module.alloc(256, c1);
198 const composite2 = module.alloc(256, c2);
199
200
201 function buildSetSet() {
202 const f = module.addFunction(prefix+"__set_set");
203 f.addParam("idx", "i32");
204 f.addLocal("word", "i32");
205 f.addLocal("mask", "i32");
206
207 const c = f.getCodeBuilder();
208
209 f.addCode(
210 c.setLocal(
211 "word",
212 c.i32_shl(
213 c.i32_shr_u(
214 c.getLocal("idx"),
215 c.i32_const(5)
216 ),
217 c.i32_const(2)
218 )
219 )
220 );
221 f.addCode(
222 c.setLocal(
223 "mask",
224 c.i32_shl(
225 c.i32_const(1),
226 c.i32_and(
227 c.getLocal("idx"),
228 c.i32_const("0x1F")
229 )
230 )
231 )
232 );
233 f.addCode(
234 c.i32_store(
235 c.getLocal("word"),
236 pset,
237 c.i32_or(
238 c.i32_load(
239 c.getLocal("word"),
240 pset
241 ),
242 c.getLocal("mask")
243 )
244 )
245 );
246 }
247
248 function buildSetIsSet() {
249 const f = module.addFunction(prefix+"__set_isSet");
250 f.addParam("idx", "i32");
251 f.setReturnType("i32");
252 f.addLocal("word", "i32");
253 f.addLocal("mask", "i32");
254
255 const c = f.getCodeBuilder();
256
257
258 f.addCode(
259 c.setLocal(
260 "word",
261 c.i32_shl(
262 c.i32_shr_u(
263 c.getLocal("idx"),
264 c.i32_const(5)
265 ),
266 c.i32_const(2)
267 )
268 )
269 );
270 f.addCode(
271 c.setLocal(
272 "mask",
273 c.i32_shl(
274 c.i32_const(1),
275 c.i32_and(
276 c.getLocal("idx"),
277 c.i32_const("0x1F")
278 )
279 )
280 )
281 );
282
283 f.addCode(
284 c.i32_and(
285 c.i32_load(
286 c.getLocal("word"),
287 pset
288 ),
289 c.getLocal("mask")
290 )
291 );
292 }
293
294
295 function buildPTableReset() {
296 const f = module.addFunction(prefix+"__ptable_reset");
297 f.addParam("ppoints", "i32");
298 f.addParam("w", "i32"); // Window size Max 8
299 f.addLocal("ps", "i32");
300 f.addLocal("pd", "i32");
301 f.addLocal("i", "i32");
302 f.addLocal("isZero", "i32");
303
304 const c = f.getCodeBuilder();
305
306 f.addCode(c.setLocal("ps", c.getLocal("ppoints")));
307
308 f.addCode(c.call( curvePrefix + "_zero", c.i32_const(ptable) ));
309
310 f.addCode(c.setLocal("i", c.i32_const(0)));
311 f.addCode(c.block(c.loop(
312 c.br_if(
313 1,
314 c.i32_eq(
315 c.getLocal("i"),
316 c.getLocal("w")
317 )
318 ),
319
320 c.setLocal(
321 "pd",
322 c.i32_add(
323 c.i32_const(ptable),
324 c.i32_mul(
325 c.i32_shl(
326 c.i32_const(1),
327 c.getLocal("i")
328 ),
329 c.i32_const(pointN8)
330 )
331 )
332 ),
333
334
335 c.setLocal("isZero", c.call(pointFieldPrefix + "_isZero", c.getLocal("ps"))),
336
337 c.call( pointFieldPrefix + "_copy", c.getLocal("ps"), c.getLocal("pd")),
338 c.setLocal("ps", c.i32_add(c.getLocal("ps"), c.i32_const(pointFieldN8))),
339 c.setLocal("pd", c.i32_add(c.getLocal("pd"), c.i32_const(pointFieldN8))),
340
341 c.call( pointFieldPrefix + "_copy", c.getLocal("ps"), c.getLocal("pd")),
342 c.setLocal("ps", c.i32_add(c.getLocal("ps"), c.i32_const(pointFieldN8))),
343 c.setLocal("pd", c.i32_add(c.getLocal("pd"), c.i32_const(pointFieldN8))),
344
345 c.if(
346 c.getLocal("isZero"),
347 c.call( pointFieldPrefix + "_zero", c.getLocal("pd")),
348 c.call( pointFieldPrefix + "_one", c.getLocal("pd")),
349 ),
350
351 c.setLocal("i", c.i32_add(c.getLocal("i"), c.i32_const(1))),
352 c.br(0)
353 )));
354
355 // Reset the set
356 f.addCode(c.i64_store( c.i32_const(pset ),c.i64_const("0x0000000100010117")));
357 f.addCode(c.i64_store( c.i32_const(pset+ 8),c.i64_const("0x0000000000000001")));
358 f.addCode(c.i64_store( c.i32_const(pset+16),c.i64_const("0x0000000000000001")));
359 f.addCode(c.i64_store( c.i32_const(pset+24),c.i64_const("0x0000000000000000")));
360
361
362 }
363
364 function buildPTableGet() {
365 const f = module.addFunction(prefix+"__ptable_get");
366 f.addParam("idx", "i32");
367 f.setReturnType("i32");
368 f.addLocal("pr", "i32");
369 f.addLocal("p1", "i32");
370 f.addLocal("p2", "i32");
371
372 const c = f.getCodeBuilder();
373
374 f.addCode(
375 c.setLocal(
376 "pr",
377 c.i32_add(
378 c.i32_const(ptable),
379 c.i32_mul(
380 c.getLocal("idx"),
381 c.i32_const(pointN8)
382 )
383 )
384 )
385 );
386
387 f.addCode(c.if(
388 c.i32_eqz(
389 c.call(
390 prefix + "__set_isSet",
391 c.getLocal("idx")
392 ),
393 ),
394 [
395 ...c.setLocal(
396 "p1",
397 c.call(
398 prefix + "__ptable_get",
399 c.i32_load8_u(
400 c.getLocal("idx"),
401 composite1
402 )
403 )
404 ),
405 ...c.setLocal(
406 "p2",
407 c.call(
408 prefix + "__ptable_get",
409 c.i32_load8_u(
410 c.getLocal("idx"),
411 composite2
412 )
413 )
414 ),
415 ...c.call(
416 curvePrefix + "_add",
417 c.getLocal("p1"),
418 c.getLocal("p2"),
419 c.getLocal("pr")
420 ),
421 ...c.call(
422 prefix + "__set_set",
423 c.getLocal("idx")
424 )
425 ]
426 ));
427
428 f.addCode(c.getLocal("pr"));
429 }
430
431
432 function buildMulw() {
433 const f = module.addFunction(prefix+"__mulw");
434 f.addParam("pscalars", "i32");
435 f.addParam("ppoints", "i32");
436 f.addParam("w", "i32"); // Window size Max 8
437 f.addParam("pr", "i32");
438 f.addLocal("i", "i32");
439
440 const c = f.getCodeBuilder();
441
442 const psels = module.alloc(scalarN8 * 8);
443
444 f.addCode(c.call(
445 prefix + "__packbits",
446 c.getLocal("pscalars"),
447 c.getLocal("w"),
448 c.i32_const(psels)
449 ));
450
451 f.addCode(c.call(
452 curvePrefix + "_zero",
453 c.getLocal("pr"),
454 ));
455
456 f.addCode(c.call(
457 prefix + "__ptable_reset",
458 c.getLocal("ppoints"),
459 c.getLocal("w")
460 ));
461
462
463 f.addCode(c.setLocal("i", c.i32_const(0)));
464 f.addCode(c.block(c.loop(
465 c.br_if(
466 1,
467 c.i32_eq(
468 c.getLocal("i"),
469 c.i32_const(scalarN8 * 8)
470 )
471 ),
472
473 c.call(curvePrefix + "_double",
474 c.getLocal("pr"),
475 c.getLocal("pr"),
476 ),
477 c.call(curvePrefix + "_add",
478 c.getLocal("pr"),
479 c.call(
480 prefix + "__ptable_get",
481 c.i32_load8_u(
482 c.i32_sub(
483 c.i32_const(psels + scalarN8 * 8 -1),
484 c.getLocal("i")
485 )
486 )
487 ),
488 c.getLocal("pr"),
489 ),
490
491 c.setLocal("i", c.i32_add(c.getLocal("i"), c.i32_const(1))),
492 c.br(0)
493 )));
494
495 }
496
497
498 function buildMultiexp() {
499 const f = module.addFunction(prefix+"_multiexp");
500 f.addParam("pscalars", "i32");
501 f.addParam("ppoints", "i32");
502 f.addParam("n", "i32"); // Number of points
503 f.addParam("w", "i32"); // Window size Max 8
504 f.addParam("pr", "i32");
505 f.addLocal("ps", "i32");
506 f.addLocal("pp", "i32");
507 f.addLocal("wf", "i32");
508 f.addLocal("lastps", "i32");
509
510 const c = f.getCodeBuilder();
511
512 const aux = c.i32_const(module.alloc(pointN8));
513
514 f.addCode(c.setLocal("ps", c.getLocal("pscalars")));
515 f.addCode(c.setLocal("pp", c.getLocal("ppoints")));
516
517 f.addCode(c.setLocal(
518 "lastps",
519 c.i32_add(
520 c.getLocal("ps"),
521 c.i32_mul(
522 c.i32_mul(
523 c.i32_div_u(
524 c.getLocal("n"),
525 c.getLocal("w")
526 ),
527 c.getLocal("w")
528 ),
529 c.i32_const(scalarN8)
530 )
531 )
532 ));
533
534 f.addCode(c.block(c.loop(
535 c.br_if(
536 1,
537 c.i32_eq(
538 c.getLocal("ps"),
539 c.getLocal("lastps")
540 )
541 ),
542
543 c.call(prefix + "__mulw", c.getLocal("ps"), c.getLocal("pp"), c.getLocal("w"), aux),
544 c.call(curvePrefix + "_add", aux, c.getLocal("pr"), c.getLocal("pr")),
545
546 c.setLocal(
547 "ps",
548 c.i32_add(
549 c.getLocal("ps"),
550 c.i32_mul(
551 c.i32_const(scalarN8),
552 c.getLocal("w")
553 )
554 )
555 ),
556
557 c.setLocal(
558 "pp",
559 c.i32_add(
560 c.getLocal("pp"),
561 c.i32_mul(
562 c.i32_const(pointFieldN8*2),
563 c.getLocal("w")
564 )
565 )
566 ),
567
568 c.br(0)
569 )));
570
571 f.addCode(c.setLocal("wf", c.i32_rem_u(c.getLocal("n"), c.getLocal("w"))));
572
573 f.addCode(c.if(
574 c.getLocal("wf"),
575 [
576 ...c.call(prefix + "__mulw", c.getLocal("ps"), c.getLocal("pp"), c.getLocal("wf"), aux),
577 ...c.call(curvePrefix + "_add", aux, c.getLocal("pr"), c.getLocal("pr")),
578 ]
579 ));
580 }
581
582
583 function buildMulw2() {
584 const f = module.addFunction(prefix+"__mulw2");
585 f.addParam("pscalars", "i32");
586 f.addParam("ppoints", "i32");
587 f.addParam("w", "i32"); // Window size Max 8
588 f.addParam("pr", "i32");
589 f.addLocal("i", "i32");
590 f.addLocal("pd", "i32");
591
592 const c = f.getCodeBuilder();
593
594 const psels = module.alloc(scalarN8 * 8);
595
596 f.addCode(c.call(
597 prefix + "__packbits",
598 c.getLocal("pscalars"),
599 c.getLocal("w"),
600 c.i32_const(psels)
601 ));
602
603 f.addCode(c.call(
604 prefix + "__ptable_reset",
605 c.getLocal("ppoints"),
606 c.getLocal("w")
607 ));
608
609
610 f.addCode(c.setLocal("i", c.i32_const(0)));
611 f.addCode(c.block(c.loop(
612 c.br_if(
613 1,
614 c.i32_eq(
615 c.getLocal("i"),
616 c.i32_const(scalarN8 * 8)
617 )
618 ),
619
620 c.setLocal(
621 "pd",
622 c.i32_add(
623 c.getLocal("pr"),
624 c.i32_mul(
625 c.getLocal("i"),
626 c.i32_const(pointN8)
627 )
628 )
629 ),
630
631 c.call(curvePrefix + "_add",
632 c.getLocal("pd"),
633 c.call(
634 prefix + "__ptable_get",
635 c.i32_load8_u(
636 c.i32_sub(
637 c.i32_const(psels + scalarN8 * 8 -1),
638 c.getLocal("i")
639 )
640 )
641 ),
642 c.getLocal("pd")
643 ),
644
645 c.setLocal("i", c.i32_add(c.getLocal("i"), c.i32_const(1))),
646 c.br(0)
647 )));
648
649 }
650
651 function buildMultiexp2() {
652 const f = module.addFunction(prefix+"_multiexp2");
653 f.addParam("pscalars", "i32");
654 f.addParam("ppoints", "i32");
655 f.addParam("n", "i32"); // Number of points
656 f.addParam("w", "i32"); // Window size Max 8
657 f.addParam("pr", "i32");
658 f.addLocal("ps", "i32");
659 f.addLocal("pp", "i32");
660 f.addLocal("wf", "i32");
661 f.addLocal("lastps", "i32");
662
663 const c = f.getCodeBuilder();
664
665 const accumulators = c.i32_const(module.alloc(pointN8*scalarN8*8));
666 const aux = c.i32_const(module.alloc(pointN8));
667
668 f.addCode(c.call(prefix + "__resetAccumulators", accumulators, c.i32_const(scalarN8*8)));
669
670 f.addCode(c.setLocal("ps", c.getLocal("pscalars")));
671 f.addCode(c.setLocal("pp", c.getLocal("ppoints")));
672
673 f.addCode(c.setLocal(
674 "lastps",
675 c.i32_add(
676 c.getLocal("ps"),
677 c.i32_mul(
678 c.i32_mul(
679 c.i32_div_u(
680 c.getLocal("n"),
681 c.getLocal("w")
682 ),
683 c.getLocal("w")
684 ),
685 c.i32_const(scalarN8)
686 )
687 )
688 ));
689
690 f.addCode(c.block(c.loop(
691 c.br_if(
692 1,
693 c.i32_eq(
694 c.getLocal("ps"),
695 c.getLocal("lastps")
696 )
697 ),
698
699 c.call(prefix + "__mulw2", c.getLocal("ps"), c.getLocal("pp"), c.getLocal("w"), accumulators),
700
701 c.setLocal(
702 "ps",
703 c.i32_add(
704 c.getLocal("ps"),
705 c.i32_mul(
706 c.i32_const(scalarN8),
707 c.getLocal("w")
708 )
709 )
710 ),
711
712 c.setLocal(
713 "pp",
714 c.i32_add(
715 c.getLocal("pp"),
716 c.i32_mul(
717 c.i32_const(pointFieldN8*2),
718 c.getLocal("w")
719 )
720 )
721 ),
722
723 c.br(0)
724 )));
725
726 f.addCode(c.setLocal("wf", c.i32_rem_u(c.getLocal("n"), c.getLocal("w"))));
727
728 f.addCode(c.if(
729 c.getLocal("wf"),
730 [
731 ...c.call(prefix + "__mulw2", c.getLocal("ps"), c.getLocal("pp"), c.getLocal("wf"), accumulators),
732 ]
733 ));
734
735 f.addCode(c.call(
736 prefix + "__addAccumulators",
737 accumulators,
738 c.i32_const(scalarN8*8),
739 aux
740 ));
741
742 f.addCode(c.call(curvePrefix + "_add", aux, c.getLocal("pr"), c.getLocal("pr")));
743
744 }
745
746 function buildResetAccumulators() {
747 const f = module.addFunction(prefix+"__resetAccumulators");
748 f.addParam("paccumulators", "i32");
749 f.addParam("n", "i32"); // Number of points
750 f.addLocal("i", "i32");
751
752 const c = f.getCodeBuilder();
753
754 f.addCode(c.setLocal("i", c.i32_const(0)));
755 f.addCode(c.block(c.loop(
756 c.br_if(
757 1,
758 c.i32_eq(
759 c.getLocal("i"),
760 c.getLocal("n")
761 )
762 ),
763
764 c.call(
765 curvePrefix + "_zero",
766 c.i32_add(
767 c.getLocal("paccumulators"),
768 c.i32_mul(
769 c.getLocal("i"),
770 c.i32_const(pointN8)
771 )
772 )
773 ),
774
775 c.setLocal("i", c.i32_add(c.getLocal("i"), c.i32_const(1))),
776 c.br(0)
777
778 )));
779 }
780
781 function buildAddAccumulators() {
782 const f = module.addFunction(prefix+"__addAccumulators");
783 f.addParam("paccumulators", "i32");
784 f.addParam("n", "i32"); // Number of points
785 f.addParam("pr", "i32");
786 f.addLocal("i", "i32");
787 f.addLocal("p", "i32");
788
789 const c = f.getCodeBuilder();
790
791/*
792 f.addCode(c.setLocal(
793 "p",
794 c.i32_add(
795 c.getLocal("paccumulators"),
796 c.i32_sub(
797 c.i32_mul(
798 c.getLocal("n"),
799 c.i32_const(pointN8)
800 ),
801 c.i32_const(pointN8)
802 )
803 )
804 ));
805*/
806 f.addCode(c.setLocal("p",c.getLocal("paccumulators")));
807
808 f.addCode(c.call(curvePrefix + "_copy", c.getLocal("p"), c.getLocal("pr")));
809 f.addCode(c.setLocal("p", c.i32_add(c.getLocal("p"), c.i32_const(pointN8))));
810
811 f.addCode(c.setLocal("i", c.i32_const(1)));
812 f.addCode(c.block(c.loop(
813 c.br_if(
814 1,
815 c.i32_eq(
816 c.getLocal("i"),
817 c.getLocal("n")
818 )
819 ),
820
821 c.call(
822 curvePrefix + "_double",
823 c.getLocal("pr"),
824 c.getLocal("pr")
825 ),
826
827 c.call(
828 curvePrefix + "_add",
829 c.getLocal("p"),
830 c.getLocal("pr"),
831 c.getLocal("pr")
832 ),
833
834 c.setLocal("p", c.i32_add(c.getLocal("p"), c.i32_const(pointN8))),
835 c.setLocal("i", c.i32_add(c.getLocal("i"), c.i32_const(1))),
836 c.br(0)
837 )));
838 }
839
840 buildSetSet();
841 buildSetIsSet();
842 buildPTableReset();
843 buildPTableGet();
844 buildPackBits();
845 buildMulw();
846 buildMultiexp();
847
848 buildMulw2();
849 buildResetAccumulators();
850 buildAddAccumulators();
851 buildMultiexp2();
852
853 module.exportFunction(prefix+"_multiexp");
854 module.exportFunction(prefix+"_multiexp2");
855
856
857};