websnark/src/build_f2m.js
src/build_f2m.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 buildF2m(module, pNonResidue, prefix, f1mPrefix) {
21
22 if (module.modules[prefix]) return prefix; // already builded
23
24 const f1n8 = module.modules[f1mPrefix].n64*8;
25 module.modules[prefix] = {
26 n64: module.modules[f1mPrefix].n64*2
27 };
28
29 function buildAdd() {
30 const f = module.addFunction(prefix+"_add");
31 f.addParam("x", "i32");
32 f.addParam("y", "i32");
33 f.addParam("r", "i32");
34
35 const c = f.getCodeBuilder();
36
37 const x0 = c.getLocal("x");
38 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
39 const y0 = c.getLocal("y");
40 const y1 = c.i32_add(c.getLocal("y"), c.i32_const(f1n8));
41 const r0 = c.getLocal("r");
42 const r1 = c.i32_add(c.getLocal("r"), c.i32_const(f1n8));
43
44 f.addCode(
45 c.call(f1mPrefix+"_add", x0, y0, r0),
46 c.call(f1mPrefix+"_add", x1, y1, r1),
47 );
48 }
49
50 function buildSub() {
51 const f = module.addFunction(prefix+"_sub");
52 f.addParam("x", "i32");
53 f.addParam("y", "i32");
54 f.addParam("r", "i32");
55
56 const c = f.getCodeBuilder();
57
58 const x0 = c.getLocal("x");
59 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
60 const y0 = c.getLocal("y");
61 const y1 = c.i32_add(c.getLocal("y"), c.i32_const(f1n8));
62 const r0 = c.getLocal("r");
63 const r1 = c.i32_add(c.getLocal("r"), c.i32_const(f1n8));
64
65 f.addCode(
66 c.call(f1mPrefix+"_sub", x0, y0, r0),
67 c.call(f1mPrefix+"_sub", x1, y1, r1),
68 );
69 }
70
71 function buildNeg() {
72 const f = module.addFunction(prefix+"_neg");
73 f.addParam("x", "i32");
74 f.addParam("r", "i32");
75
76 const c = f.getCodeBuilder();
77
78 const x0 = c.getLocal("x");
79 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
80 const r0 = c.getLocal("r");
81 const r1 = c.i32_add(c.getLocal("r"), c.i32_const(f1n8));
82
83 f.addCode(
84 c.call(f1mPrefix+"_neg", x0, r0),
85 c.call(f1mPrefix+"_neg", x1, r1),
86 );
87 }
88
89 function buildMul() {
90 const f = module.addFunction(prefix+"_mul");
91 f.addParam("x", "i32");
92 f.addParam("y", "i32");
93 f.addParam("r", "i32");
94
95 const c = f.getCodeBuilder();
96
97 const x0 = c.getLocal("x");
98 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
99 const y0 = c.getLocal("y");
100 const y1 = c.i32_add(c.getLocal("y"), c.i32_const(f1n8));
101 const r0 = c.getLocal("r");
102 const r1 = c.i32_add(c.getLocal("r"), c.i32_const(f1n8));
103
104 const A = c.i32_const(module.alloc(f1n8));
105 const B = c.i32_const(module.alloc(f1n8));
106 const C = c.i32_const(module.alloc(f1n8));
107 const D = c.i32_const(module.alloc(f1n8));
108
109
110 f.addCode(
111 c.call(f1mPrefix + "_mul", x0, y0, A), // A = x0*y0
112 c.call(f1mPrefix + "_mul", x1, y1, B), // B = x1*y1
113
114 c.call(f1mPrefix + "_add", x0, x1, C), // C = x0 + x1
115 c.call(f1mPrefix + "_add", y0, y1, D), // D = y0 + y1
116 c.call(f1mPrefix + "_mul", C, D, C), // C = (x0 + x1)*(y0 + y1) = x0*y0+x0*y1+x1*y0+x1*y1
117
118 c.call(f1mPrefix + "_mul", B, c.i32_const(pNonResidue), r0), // r0 = nr*(x1*y1)
119 c.call(f1mPrefix + "_add", A, r0, r0), // r0 = x0*y0 + nr*(x1*y1)
120 c.call(f1mPrefix + "_add", A, B, r1), // r1 = x0*y0+x1*y1
121 c.call(f1mPrefix + "_sub", C, r1, r1) // r1 = x0*y0+x0*y1+x1*y0+x1*y1 - x0*y0+x1*y1 = x0*y1+x1*y0
122 );
123
124 }
125
126
127 function buildToMontgomery() {
128 const f = module.addFunction(prefix+"_toMontgomery");
129 f.addParam("x", "i32");
130 f.addParam("r", "i32");
131
132 const c = f.getCodeBuilder();
133
134 const x0 = c.getLocal("x");
135 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
136 const r0 = c.getLocal("r");
137 const r1 = c.i32_add(c.getLocal("r"), c.i32_const(f1n8));
138
139 f.addCode(
140 c.call(f1mPrefix+"_toMontgomery", x0, r0),
141 c.call(f1mPrefix+"_toMontgomery", x1, r1)
142 );
143 }
144
145 function buildFromMontgomery() {
146 const f = module.addFunction(prefix+"_fromMontgomery");
147 f.addParam("x", "i32");
148 f.addParam("r", "i32");
149
150 const c = f.getCodeBuilder();
151
152 const x0 = c.getLocal("x");
153 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
154 const r0 = c.getLocal("r");
155 const r1 = c.i32_add(c.getLocal("r"), c.i32_const(f1n8));
156
157 f.addCode(
158 c.call(f1mPrefix+"_fromMontgomery", x0, r0),
159 c.call(f1mPrefix+"_fromMontgomery", x1, r1)
160 );
161 }
162
163 function buildCopy() {
164 const f = module.addFunction(prefix+"_copy");
165 f.addParam("x", "i32");
166 f.addParam("r", "i32");
167
168 const c = f.getCodeBuilder();
169
170 const x0 = c.getLocal("x");
171 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
172 const r0 = c.getLocal("r");
173 const r1 = c.i32_add(c.getLocal("r"), c.i32_const(f1n8));
174
175 f.addCode(
176 c.call(f1mPrefix+"_copy", x0, r0),
177 c.call(f1mPrefix+"_copy", x1, r1)
178 );
179 }
180
181 function buildZero() {
182 const f = module.addFunction(prefix+"_zero");
183 f.addParam("x", "i32");
184
185 const c = f.getCodeBuilder();
186
187 const x0 = c.getLocal("x");
188 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
189
190 f.addCode(
191 c.call(f1mPrefix+"_zero", x0),
192 c.call(f1mPrefix+"_zero", x1)
193 );
194 }
195
196 function buildOne() {
197 const f = module.addFunction(prefix+"_one");
198 f.addParam("x", "i32");
199
200 const c = f.getCodeBuilder();
201
202 const x0 = c.getLocal("x");
203 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
204
205 f.addCode(
206 c.call(f1mPrefix+"_one", x0),
207 c.call(f1mPrefix+"_zero", x1)
208 );
209 }
210
211 function buildEq() {
212 const f = module.addFunction(prefix+"_eq");
213 f.addParam("x", "i32");
214 f.addParam("y", "i32");
215 f.setReturnType("i32");
216
217 const c = f.getCodeBuilder();
218
219 const x0 = c.getLocal("x");
220 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
221 const y0 = c.getLocal("y");
222 const y1 = c.i32_add(c.getLocal("y"), c.i32_const(f1n8));
223
224 f.addCode(
225 c.i32_and(
226 c.call(f1mPrefix+"_eq", x0, y0),
227 c.call(f1mPrefix+"_eq", x1, y1)
228 )
229 );
230 }
231
232 function buildIsZero() {
233 const f = module.addFunction(prefix+"_isZero");
234 f.addParam("x", "i32");
235 f.setReturnType("i32");
236
237 const c = f.getCodeBuilder();
238
239 const x0 = c.getLocal("x");
240 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
241
242 f.addCode(
243 c.i32_and(
244 c.call(f1mPrefix+"_isZero", x0),
245 c.call(f1mPrefix+"_isZero", x1)
246 )
247 );
248 }
249
250 function buildInverse() {
251 const f = module.addFunction(prefix+"_inverse");
252 f.addParam("x", "i32");
253 f.addParam("r", "i32");
254
255 const c = f.getCodeBuilder();
256
257 const x0 = c.getLocal("x");
258 const x1 = c.i32_add(c.getLocal("x"), c.i32_const(f1n8));
259 const r0 = c.getLocal("r");
260 const r1 = c.i32_add(c.getLocal("r"), c.i32_const(f1n8));
261
262 const t0 = c.i32_const(module.alloc(f1n8));
263 const t1 = c.i32_const(module.alloc(f1n8));
264 const t2 = c.i32_const(module.alloc(f1n8));
265 const t3 = c.i32_const(module.alloc(f1n8));
266
267 f.addCode(
268 c.call(f1mPrefix+"_mul", x0, x0, t0),
269 c.call(f1mPrefix+"_mul", x1, x1, t1),
270 c.call(f1mPrefix+"_mul", t1, c.i32_const(pNonResidue), t2),
271 c.call(f1mPrefix+"_sub", t0, t2, t2),
272 c.call(f1mPrefix+"_inverse", t2, t3),
273
274 c.call(f1mPrefix+"_mul", x0, t3, r0),
275 c.call(f1mPrefix+"_mul", x1, t3, r1),
276 c.call(f1mPrefix+"_neg", r1, r1),
277 );
278 }
279
280 buildIsZero();
281 buildZero();
282 buildOne();
283 buildCopy();
284 buildMul();
285 buildAdd();
286 buildSub();
287 buildNeg();
288 buildToMontgomery();
289 buildFromMontgomery();
290 buildEq();
291 buildInverse();
292
293 module.exportFunction(prefix + "_isZero");
294 module.exportFunction(prefix + "_zero");
295 module.exportFunction(prefix + "_one");
296 module.exportFunction(prefix + "_copy");
297 module.exportFunction(prefix + "_mul");
298 module.exportFunction(prefix + "_add");
299 module.exportFunction(prefix + "_sub");
300 module.exportFunction(prefix + "_neg");
301 module.exportFunction(prefix + "_fromMontgomery");
302 module.exportFunction(prefix + "_toMontgomery");
303 module.exportFunction(prefix + "_eq");
304 module.exportFunction(prefix + "_inverse");
305
306 return prefix;
307};