websnark/src/build_mulacc.js
src/build_mulacc.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 buildMulAcc(windowSize, prefix, curvePrefix, scalarPrefix) {
21 const pointN64 = module.modules[curvePrefix].n64;
22 const pointN8 = pointN64*8;
23 const scalarN64 = module.modules[scalarPrefix].n64;
24 const scalarN8 = scalarN64*8;
25
26 function buildMultiMul64() {
27 const f = module.addFunction(prefix+"__multimul");
28 f.addParam("pscalars", "i32");
29 f.addParam("ppoints", "i32");
30 f.addParam("pr", "i32");
31 f.addLocal("sel");
32 f.addLocal("ppminusone");
33
34 const c = f.getCodeBuilder();
35
36 f.addCode(c.setLocal("sel", c.i32_const(0)));
37 f.addCode(c.setLocal(
38 "ppminusone",
39 c.sub(
40 c.getLocal("ppoints"),
41 c.i32_const(pointN8)
42 )
43 ));
44
45 for (let i=0; i<64; i++) {
46 for (let s=0; s<windowSize; s++) {
47 f.addCode(c.setLocal(
48 "sel",
49 c.i32_or(
50 c.getLocal("sel"),
51 c.i32_and(
52 c.i32_wrap_i64(
53 c.i64_rotl(
54 c.i64_load(
55 c.getLocal("pscalars"),
56 i*scalarN64
57 ),
58 c.i64_const(i+s+1)
59 )
60 ),
61 c.i32_const(1<<s)
62 )
63 )
64 ));
65
66 f.addCode(c.if(
67 c.getLocal("sel"),
68 c.call(
69 curvePrefix + "_add",
70 c.i32_add(
71 c.getLocal("ppminusone"),
72 c.i32_mul(
73 c.getLocal("sel"),
74 c.i32_const(pointN8)
75 )
76 )
77 )
78 ));
79
80 }
81
82 }
83
84 }
85
86
87 function buildMultiMul() {
88 buildMultiMul64();
89 const f = module.addFunction(prefix+"__multimul");
90 f.addParam("pscalars", "i32");
91 f.addParam("ppoints", "i32");
92 f.addParam("pr", "i32");
93
94 const c = f.getCodeBuilder();
95
96 f.addCode(c.call(prefix + "_zero", c.getLocal("pr")));
97
98 for (let i=0; i<scalarN64; i++) {
99 if (i>0) f.addCode(c.call(curvePrefix + "_double"), c.getLocal("pr"));
100 f.addCode(c.call(
101 prefix + "__multimul64",
102 c.i32_add(c.getLocal("pscalars"), c.const(i*8)),
103 c.getLocal("ppoints")
104 ));
105 }
106
107 }
108
109 function buildMulAcc() {
110 buildMultiMul();
111 const f = module.addFunction(prefix+"_mulacc");
112 f.addParam("pscalars", "i32");
113 f.addParam("ppoints", "i32");
114 f.addParam("n", "i32");
115 f.addParam("pr", "i32");
116 f.addLocal("inc", "i32");
117 f.addLocal("pp", "i32");
118 f.addLocal("ps", "i32");
119 f.addLocal("last", "i32");
120
121 const c = f.getCodeBuilder();
122
123 const aux = c.i32_const(module.alloc(pointN8));
124
125 // Check n is windowSize multiple
126 f.addCode(c.if(
127 c.eqz(
128 c.i32_mod(
129 c.getLocal("n"),
130 c.i32_const(windowSize)
131 )
132 ),
133 c.unreachable()
134 ));
135
136 // Set zero the output
137 f.addCode(c.call(prefix + "_zero", c.getLocal("pr")));
138
139 // Calculate the increment
140 f.addCode(c.setLocal(
141 "incPoint",
142 c.i32_const(((1 << windowSize)-1) *pointN8 )
143 ));
144
145 f.addCode(c.setLocal(
146 "incScalar",
147 c.i32_const(windowSize *scalarN8 )
148 ));
149
150 // Calculate Initial
151 f.addCode(c.setLocal(
152 "pp",
153 c.getLocal("ppoints")
154 ));
155
156 f.addCode(c.setLocal(
157 "ps",
158 c.getLocal("pscalars")
159 ));
160
161 // Calculate Last
162 f.addCode(c.setLocal(
163 "last",
164 c.i32_mul(
165 c.getLocal("incPoint"),
166 c.getLocal("n")
167 )
168 ));
169
170 f.addCode(c.block(c.loop(
171 c.br_if(
172 1,
173 c.i32_eq(
174 c.getLocal("pp"),
175 c.getLocal("last")
176 )
177 ),
178
179 c.call(prefix + "__multimul", c.getLocal("ps"), c.getLocal("pp"), aux),
180 c.call(curvePrefix + "_add", aux, c.getLocal("pr"), c.getLocal("pr")),
181
182 c.setLocal(
183 "pp",
184 c.add(
185 c.getLocal("pp"),
186 c.getLocal("incPoint")
187 )
188 ),
189 c.setLocal(
190 "ps",
191 c.add(
192 c.getLocal("ps"),
193 c.getLocal("incScalar")
194 )
195 ),
196 c.br(0)
197 )));
198
199 }
200
201 buildMulAcc();
202 module.exportFunction(prefix+"_mulacc");
203
204
205};