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 function buildMulw() {
432 const f = module.addFunction(prefix+"__mulw");
433 f.addParam("pscalars", "i32");
434 f.addParam("ppoints", "i32");
435 f.addParam("w", "i32"); // Window size Max 8
436 f.addParam("pr", "i32");
437 f.addLocal("i", "i32");
438
439 const c = f.getCodeBuilder();
440
441 const psels = module.alloc(scalarN8 * 8);
442
443 f.addCode(c.call(
444 prefix + "__packbits",
445 c.getLocal("pscalars"),
446 c.getLocal("w"),
447 c.i32_const(psels)
448 ));
449
450 f.addCode(c.call(
451 curvePrefix + "_zero",
452 c.getLocal("pr"),
453 ));
454
455 f.addCode(c.call(
456 prefix + "__ptable_reset",
457 c.getLocal("ppoints"),
458 c.getLocal("w")
459 ));
460
461
462 f.addCode(c.setLocal("i", c.i32_const(0)));
463 f.addCode(c.block(c.loop(
464 c.br_if(
465 1,
466 c.i32_eq(
467 c.getLocal("i"),
468 c.i32_const(scalarN8 * 8)
469 )
470 ),
471
472 c.call(curvePrefix + "_double",
473 c.getLocal("pr"),
474 c.getLocal("pr"),
475 ),
476 c.call(curvePrefix + "_add",
477 c.getLocal("pr"),
478 c.call(
479 prefix + "__ptable_get",
480 c.i32_load8_u(
481 c.i32_sub(
482 c.i32_const(psels + scalarN8 * 8 -1),
483 c.getLocal("i")
484 )
485 )
486 ),
487 c.getLocal("pr"),
488 ),
489
490 c.setLocal("i", c.i32_add(c.getLocal("i"), c.i32_const(1))),
491 c.br(0)
492 )));
493
494 }
495
496
497 function buildMultiexp() {
498 const f = module.addFunction(prefix+"_multiexp");
499 f.addParam("pscalars", "i32");
500 f.addParam("ppoints", "i32");
501 f.addParam("n", "i32"); // Number of points
502 f.addParam("w", "i32"); // Window size Max 8
503 f.addParam("pr", "i32");
504 f.addLocal("ps", "i32");
505 f.addLocal("pp", "i32");
506 f.addLocal("wf", "i32");
507 f.addLocal("lastps", "i32");
508
509 const c = f.getCodeBuilder();
510
511 const aux = c.i32_const(module.alloc(pointN8));
512
513 f.addCode(c.setLocal("ps", c.getLocal("pscalars")));
514 f.addCode(c.setLocal("pp", c.getLocal("ppoints")));
515
516 f.addCode(c.setLocal(
517 "lastps",
518 c.i32_add(
519 c.getLocal("ps"),
520 c.i32_mul(
521 c.i32_mul(
522 c.i32_div_u(
523 c.getLocal("n"),
524 c.getLocal("w")
525 ),
526 c.getLocal("w")
527 ),
528 c.i32_const(scalarN8)
529 )
530 )
531 ));
532
533 f.addCode(c.block(c.loop(
534 c.br_if(
535 1,
536 c.i32_eq(
537 c.getLocal("ps"),
538 c.getLocal("lastps")
539 )
540 ),
541
542 c.call(prefix + "__mulw", c.getLocal("ps"), c.getLocal("pp"), c.getLocal("w"), aux),
543 c.call(curvePrefix + "_add", aux, c.getLocal("pr"), c.getLocal("pr")),
544
545 c.setLocal(
546 "ps",
547 c.i32_add(
548 c.getLocal("ps"),
549 c.i32_mul(
550 c.i32_const(scalarN8),
551 c.getLocal("w")
552 )
553 )
554 ),
555
556 c.setLocal(
557 "pp",
558 c.i32_add(
559 c.getLocal("pp"),
560 c.i32_mul(
561 c.i32_const(pointFieldN8*2),
562 c.getLocal("w")
563 )
564 )
565 ),
566
567 c.br(0)
568 )));
569
570 f.addCode(c.setLocal("wf", c.i32_rem_u(c.getLocal("n"), c.getLocal("w"))));
571
572 f.addCode(c.if(
573 c.getLocal("wf"),
574 [
575 ...c.call(prefix + "__mulw", c.getLocal("ps"), c.getLocal("pp"), c.getLocal("wf"), aux),
576 ...c.call(curvePrefix + "_add", aux, c.getLocal("pr"), c.getLocal("pr")),
577 ]
578 ));
579 }
580
581 buildSetSet();
582 buildSetIsSet();
583 buildPTableReset();
584 buildPTableGet();
585 buildPackBits();
586 buildMulw();
587 buildMultiexp();
588 module.exportFunction(prefix+"_multiexp");
589
590
591};