websnark/src/build_f1m.js
src/build_f1m.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
20const bigInt = require("big-integer");
21const buildInt = require("./build_int.js");
22const utils = require("./utils.js");
23
24module.exports = function buildF1m(module, _q, _prefix, _intPrefix) {
25 const q = bigInt(_q);
26 const n64 = Math.floor((q.minus(1).bitLength() - 1)/64) +1;
27 const n32 = n64*2;
28 const n8 = n64*8;
29
30 const prefix = _prefix || "f1m";
31 if (module.modules[prefix]) return prefix; // already builded
32
33 const intPrefix = buildInt(module, n64, _intPrefix);
34 const pq = module.alloc(n8, utils.bigInt2BytesLE(q, n8));
35
36 const pR2 = module.alloc(utils.bigInt2BytesLE(bigInt.one.shiftLeft(n64*64).square().mod(q), n8));
37 const pOne = module.alloc(utils.bigInt2BytesLE(bigInt.one.shiftLeft(n64*64).mod(q), n8));
38 const pZero = module.alloc(utils.bigInt2BytesLE(bigInt.zero, n8));
39 module.modules[prefix] = {
40 pq: pq,
41 pR2: pR2,
42 n64: n64,
43 q: q,
44 pOne: pOne,
45 pZero: pZero
46 };
47
48 function buildOne() {
49 const f = module.addFunction(prefix+"_one");
50 f.addParam("pr", "i32");
51
52 const c = f.getCodeBuilder();
53
54 f.addCode(c.call(prefix + "_copy", c.i32_const(pOne), c.getLocal("pr")));
55 }
56
57 function buildAdd() {
58 const f = module.addFunction(prefix+"_add");
59 f.addParam("x", "i32");
60 f.addParam("y", "i32");
61 f.addParam("r", "i32");
62
63 const c = f.getCodeBuilder();
64
65 f.addCode(
66 c.if(
67 c.call(intPrefix+"_add", c.getLocal("x"), c.getLocal("y"), c.getLocal("r")),
68 c.drop(c.call(intPrefix+"_sub", c.getLocal("r"), c.i32_const(pq), c.getLocal("r"))),
69 c.if(
70 c.call(intPrefix+"_gte", c.getLocal("r"), c.i32_const(pq) ),
71 c.drop(c.call(intPrefix+"_sub", c.getLocal("r"), c.i32_const(pq), c.getLocal("r"))),
72 )
73 )
74 );
75 }
76
77 function buildSub() {
78 const f = module.addFunction(prefix+"_sub");
79 f.addParam("x", "i32");
80 f.addParam("y", "i32");
81 f.addParam("r", "i32");
82
83 const c = f.getCodeBuilder();
84
85 f.addCode(
86 c.if(
87 c.call(intPrefix+"_sub", c.getLocal("x"), c.getLocal("y"), c.getLocal("r")),
88 c.drop(c.call(intPrefix+"_add", c.getLocal("r"), c.i32_const(pq), c.getLocal("r")))
89 )
90 );
91 }
92
93 function buildNeg() {
94 const f = module.addFunction(prefix+"_neg");
95 f.addParam("x", "i32");
96 f.addParam("r", "i32");
97
98 const c = f.getCodeBuilder();
99
100 f.addCode(
101 c.if(
102 c.i32_eqz( c.call(intPrefix + "_isZero", c.getLocal("x"))),
103 c.drop(c.call(intPrefix+"_sub", c.i32_const(pq), c.getLocal("x"), c.getLocal("r"))),
104 )
105 );
106 }
107
108
109 function buildMReduct() {
110 const carries = module.alloc(n32*n32*8);
111
112 const f = module.addFunction(prefix+"_mReduct");
113 f.addParam("t", "i32");
114 f.addParam("r", "i32");
115 f.addLocal("np32", "i64");
116 f.addLocal("c", "i64");
117 f.addLocal("m", "i64");
118
119 const c = f.getCodeBuilder();
120
121 const np32 = bigInt("100000000",16).minus( q.modInv(bigInt("100000000",16))).toJSNumber();
122
123 f.addCode(c.setLocal("np32", c.i64_const(np32)));
124
125 for (let i=0; i<n32; i++) {
126 f.addCode(c.setLocal("c", c.i64_const(0)));
127
128 f.addCode(
129 c.setLocal(
130 "m",
131 c.i64_and(
132 c.i64_mul(
133 c.i64_load32_u(c.getLocal("t"), i*4),
134 c.getLocal("np32")
135 ),
136 c.i64_const("0xFFFFFFFF")
137 )
138 )
139 );
140
141 for (let j=0; j<n32; j++) {
142
143 f.addCode(
144 c.setLocal("c",
145 c.i64_add(
146 c.i64_add(
147 c.i64_load32_u(c.getLocal("t"), (i+j)*4),
148 c.i64_shr_u(c.getLocal("c"), c.i64_const(32))
149 ),
150 c.i64_mul(
151 c.i64_load32_u(c.i32_const(pq), j*4),
152 c.getLocal("m")
153 )
154 )
155 )
156 );
157
158 f.addCode(
159 c.i64_store32(
160 c.getLocal("t"),
161 (i+j)*4,
162 c.getLocal("c")
163 )
164 );
165 }
166
167 f.addCode(
168 c.i64_store32(
169 c.i32_const(carries),
170 i*4,
171 c.i64_shr_u(c.getLocal("c"), c.i64_const(32))
172 )
173 );
174 }
175
176 f.addCode(
177 c.call(
178 prefix+"_add",
179 c.i32_const(carries),
180 c.i32_add(
181 c.getLocal("t"),
182 c.i32_const(n32*4)
183 ),
184 c.getLocal("r")
185 )
186 );
187 }
188
189
190 function buildMul() {
191
192 const pAux2 = module.alloc(n8*2);
193
194 const f = module.addFunction(prefix+"_mul");
195 f.addParam("x", "i32");
196 f.addParam("y", "i32");
197 f.addParam("r", "i32");
198
199 const c = f.getCodeBuilder();
200 f.addCode(c.call(intPrefix + "_mul", c.getLocal("x"), c.getLocal("y"), c.i32_const(pAux2) ));
201 f.addCode(c.call(prefix + "_mReduct", c.i32_const(pAux2), c.getLocal("r")));
202 }
203
204
205 function buildToMontgomery() {
206 const f = module.addFunction(prefix+"_toMontgomery");
207 f.addParam("x", "i32");
208 f.addParam("r", "i32");
209
210 const c = f.getCodeBuilder();
211 f.addCode(c.call(prefix+"_mul", c.getLocal("x"), c.i32_const(pR2), c.getLocal("r")));
212 }
213
214 function buildFromMontgomery() {
215
216 const pAux2 = module.alloc(n8*2);
217
218 const f = module.addFunction(prefix+"_fromMontgomery");
219 f.addParam("x", "i32");
220 f.addParam("r", "i32");
221
222 const c = f.getCodeBuilder();
223 f.addCode(c.call(intPrefix + "_copy", c.getLocal("x"), c.i32_const(pAux2) ));
224 f.addCode(c.call(intPrefix + "_zero", c.i32_const(pAux2 + n8) ));
225 f.addCode(c.call(prefix+"_mReduct", c.i32_const(pAux2), c.getLocal("r")));
226 }
227
228 function buildInverse() {
229
230 const f = module.addFunction(prefix+ "_inverse");
231 f.addParam("x", "i32");
232 f.addParam("r", "i32");
233
234 const c = f.getCodeBuilder();
235 f.addCode(c.call(prefix + "_fromMontgomery", c.getLocal("x"), c.getLocal("r")));
236 f.addCode(c.call(intPrefix + "_inverseMod", c.getLocal("r"), c.i32_const(pq), c.getLocal("r")));
237 f.addCode(c.call(prefix + "_toMontgomery", c.getLocal("r"), c.getLocal("r")));
238 }
239
240 buildAdd();
241 buildSub();
242 buildNeg();
243 buildMReduct();
244 buildMul();
245 buildToMontgomery();
246 buildFromMontgomery();
247 buildInverse();
248 module.exportFunction(prefix + "_add");
249 module.exportFunction(prefix + "_sub");
250 module.exportFunction(prefix + "_neg");
251 module.exportFunction(prefix + "_mReduct");
252 module.exportFunction(prefix + "_mul");
253 module.exportFunction(prefix + "_fromMontgomery");
254 module.exportFunction(prefix + "_toMontgomery");
255 module.exportFunction(prefix + "_inverse");
256 module.exportFunction(intPrefix + "_copy", prefix+"_copy");
257 module.exportFunction(intPrefix + "_zero", prefix+"_zero");
258 module.exportFunction(intPrefix + "_isZero", prefix+"_isZero");
259 module.exportFunction(intPrefix + "_eq", prefix+"_eq");
260 buildOne();
261 module.exportFunction(prefix + "_one");
262
263 return prefix;
264};