circom/src/build.js
src/build.jsRaw
1/*
2 Copyright 2018 0KIMS association.
3
4 This file is part of circom (Zero Knowledge Circuit Compiler).
5
6 circom 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 circom 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 circom. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20const assert = require("assert");
21const utils = require("./utils");
22const gen = require("./gencode").gen;
23const createRefs = require("./gencode").createRefs;
24
25module.exports = build;
26
27
28function build(ctx) {
29 ctx.definedFunctions = {};
30 ctx.functionCodes = [];
31 ctx.buildFunction = buildFunction;
32 ctx.conditionalCodeHeader = "";
33 ctx.codes_sizes = [];
34 ctx.definedSizes = {};
35 ctx.addSizes = addSizes;
36 ctx.addConstant = addConstant;
37 ctx.addConstant(ctx.F.zero);
38 ctx.addConstant(ctx.F.one);
39
40 if (ctx.verbose) console.log("buildHeader...");
41 buildHeader(ctx);
42 if (ctx.verbose) console.log("buildEntryTables...");
43 buildEntryTables(ctx);
44 ctx.globalNames = ctx.uniqueNames;
45
46 if (ctx.verbose) console.log("buildCode...");
47 buildCode(ctx);
48
49 if (ctx.verbose) console.log("buildComponentsArray...");
50 buildComponentsArray(ctx);
51
52 if (ctx.verbose) console.log("buildMapIsInput...");
53 buildMapIsInput(ctx);
54
55 if (ctx.verbose) console.log("buildWit2Sig...");
56 buildWit2Sig(ctx);
57
58}
59
60function buildEntryTables(ctx) {
61
62 const definedHashMaps = {};
63 for (let i=0; i<ctx.components.length; i++) {
64 if (ctx.verbose && (i%100000 ==0)) console.log(`buildEntryTables component: ${i}/${ctx.components.length}`);
65 const {htName, htMap} = addHashTable(i);
66
67 const componentEntriesTableName = ctx.getUniqueName("_entryTable" + ctx.components[i].template);
68
69 const componentEntriesTable = [];
70 for (let j=0; j<htMap.length; j++) {
71 const entry = ctx.components[i].names.o[htMap[j]];
72 const sizeName = ctx.addSizes(entry.sizes);
73 componentEntriesTable.push({
74 offset: entry.offset,
75 sizeName: sizeName,
76 type: entry.type
77 });
78 }
79
80 ctx.builder.addComponentEntriesTable(componentEntriesTableName, componentEntriesTable);
81
82 ctx.components[i].htName = htName;
83 ctx.components[i].etName = componentEntriesTableName;
84 }
85
86
87 return;
88
89 function addHashTable(cIdx) {
90 const keys = Object.keys(ctx.components[cIdx].names.o);
91 assert(keys.length<128);
92 keys.sort((a,b) => ((a>b) ? 1 : -1));
93 const h = utils.fnvHash(keys.join(","));
94 if (definedHashMaps[h]) return definedHashMaps[h];
95 definedHashMaps[h] = {};
96 definedHashMaps[h].htName = ctx.getUniqueName("_ht"+ctx.components[cIdx].template);
97 definedHashMaps[h].htMap = [];
98 const t = [];
99 for (let i=0; i<keys.length; i++) {
100 definedHashMaps[h].htMap[i] = keys[i];
101
102 const h2 = utils.fnvHash(keys[i]);
103 let pos = parseInt(h2.slice(-2), 16);
104 while (t[pos]) pos = (pos + 1) % 256;
105 t[pos] = [h2, i, keys[i]];
106 }
107 ctx.builder.addHashMap(definedHashMaps[h].htName, t);
108
109 return definedHashMaps[h];
110 }
111}
112
113function buildCode(ctx) {
114
115 const fDefined = {};
116
117 const fnComponents = [];
118 for (let i=0; i<ctx.components.length; i++) {
119 if (ctx.verbose && (i%1000 ==0)) console.log(`buildCode component: ${i}/${ctx.components.length}`);
120 const {h, instanceDef} = hashComponentCall(ctx, i);
121 const fName = ctx.components[i].template+"_"+h;
122 if (!fDefined[fName]) {
123
124
125 ctx.scopes = [{}];
126 ctx.conditionalCode = false;
127 ctx.fnBuilder = ctx.builder.newComponentFunctionBuilder(fName, instanceDef);
128 ctx.codeBuilder = ctx.fnBuilder.newCodeBuilder();
129 ctx.uniqueNames = Object.assign({},ctx.globalNames);
130 ctx.refs = [];
131 ctx.fileName = ctx.templates[ctx.components[i].template].fileName;
132 ctx.filePath = ctx.templates[ctx.components[i].template].filePath;
133 ctx.getSignalSizesCache = {};
134 ctx.getSignalOffsetCache = {};
135
136 for (let p in ctx.components[i].params) {
137 if (ctx.scopes[0][p]) return ctx.throwError(`Repeated parameter at ${ctx.components[i].template}: ${p}`);
138 const refId = ctx.refs.length;
139 ctx.refs.push({
140 type: "BIGINT",
141 used: false,
142 value: utils.flatArray(ctx.components[i].params[p]),
143 sizes: utils.accSizes(utils.extractSizes(ctx.components[i].params[p])),
144 label: ctx.getUniqueName(p)
145 });
146 ctx.scopes[0][p] = refId;
147 }
148
149 createRefs(ctx, ctx.templates[ctx.components[i].template].block);
150 if (ctx.error) return;
151
152 gen(ctx, ctx.templates[ctx.components[i].template].block);
153 if (ctx.error) return;
154
155 ctx.fnBuilder.setBody(ctx.codeBuilder);
156
157 ctx.builder.addFunction(ctx.fnBuilder);
158
159 fDefined[fName] = true;
160 }
161 ctx.components[i].fnName = fName;
162 }
163
164 return fnComponents;
165}
166
167function buildComponentsArray(ctx) {
168 for (let i=0; i< ctx.components.length; i++) {
169 if (ctx.verbose && (i%10000 ==0)) console.log(`buildComponentsArray component: ${i}/${ctx.components.length}`);
170 let newThread;
171 if (ctx.newThreadTemplates) {
172 if (ctx.newThreadTemplates.test(ctx.components[i].template)) {
173 newThread = true;
174 } else {
175 newThread = false;
176 }
177 } else {
178 newThread = false;
179 }
180 ctx.builder.addComponent({
181 hashMapName: ctx.components[i].htName,
182 entryTableName: ctx.components[i].etName,
183 functionName: ctx.components[i].fnName,
184 nInSignals: ctx.components[i].nInSignals,
185 newThread: newThread
186 });
187 }
188}
189
190
191function buildHeader(ctx) {
192 ctx.builder.setHeader({
193 NSignals: ctx.signals.length,
194 NComponents: ctx.components.length,
195 NInputs: ctx.components[ ctx.getComponentIdx("main") ].nInSignals,
196 NOutputs: ctx.totals[ ctx.stOUTPUT ],
197 NVars: ctx.totals[ctx.stONE] + ctx.totals[ctx.stOUTPUT] + ctx.totals[ctx.stPUBINPUT] + ctx.totals[ctx.stPRVINPUT] + ctx.totals[ctx.stINTERNAL],
198 P: ctx.F.p
199 });
200}
201
202function buildMapIsInput(ctx) {
203 let i;
204 let map = [];
205 let acc = 0;
206 for (i=0; i<ctx.signals.length; i++) {
207 if (ctx.verbose && (i%100000 ==0)) console.log(`buildMapIsInput signal: ${i}/${ctx.signals.length}`);
208 if (ctx.signals[i].o & ctx.IN) {
209 acc = acc | (1 << (i%32) );
210 }
211 if ((i+1)%32==0) {
212 map.push(acc);
213 acc = 0;
214 }
215 }
216 if ((i%32) != 0) {
217 map.push(acc);
218 }
219
220 ctx.builder.setMapIsInput(map);
221}
222
223
224
225function buildWit2Sig(ctx) {
226 const NVars =
227 ctx.totals[ctx.stONE] +
228 ctx.totals[ctx.stOUTPUT] +
229 ctx.totals[ctx.stPUBINPUT] +
230 ctx.totals[ctx.stPRVINPUT] +
231 ctx.totals[ctx.stINTERNAL];
232 const arr = Array(NVars);
233 for (let i=0; i<ctx.signals.length; i++) {
234 if (ctx.verbose && (i%100000 ==0)) console.log(`buildWit2Sig signal: ${i}/${ctx.signals.length}`);
235 const outIdx = ctx.signals[i].id;
236 if (ctx.signals[i].e>=0) continue; // If has an alias, continue..
237 assert(typeof outIdx != "undefined", `Signal ${i} does not have index`);
238 if (outIdx>=NVars) continue; // Is a constant or a discarded variable
239 if (typeof arr[ctx.signals[i].id] == "undefined") {
240 arr[outIdx] = i;
241 }
242 }
243
244 ctx.builder.setWit2Sig(arr);
245}
246
247
248
249function addSizes(_sizes) {
250 const sizes = _sizes || [];
251 let name = "sizes";
252 for (let i=0; i<sizes.length;i++) {
253 name+="_"+sizes[i];
254 }
255 if (name=="sizes") name="sizes_0";
256
257 if (this.definedSizes[name]) return this.definedSizes[name];
258 const labelName = this.getUniqueName(name);
259 this.definedSizes[name] = labelName;
260
261 const accSizes = utils.accSizes(sizes);
262
263 this.builder.addSizes(labelName, accSizes);
264
265 let code = `Circom_Size ${labelName}[${accSizes.length}] = {`;
266 for (let i=0; i<accSizes.length; i++) {
267 if (i>0) code += ",";
268 code += accSizes[i];
269 }
270 code += "};\n";
271 this.codes_sizes.push(code);
272
273 return labelName;
274}
275
276function addConstant(c) {
277 return this.builder.addConstant(c);
278}
279
280function buildFunction(name, paramValues) {
281 const ctx = this;
282 const {h, instanceDef} = hashFunctionCall(ctx, name, paramValues);
283
284 if (ctx.definedFunctions[h]) return ctx.definedFunctions[h];
285
286 const res = {
287 fnName: `${name}_${h}`
288 };
289
290 const oldRefs = ctx.refs;
291 const oldConditionalCode = ctx.conditionalCode;
292 const oldCodeBuilder = ctx.codeBuilder;
293 const oldFnBuilder = ctx.fnBuilder;
294
295 const oldUniqueNames = ctx.uniqueNames;
296 const oldFileName = ctx.fileName;
297 const oldFilePath = ctx.oldFilePath;
298 const oldReturnSizes = ctx.returnSizes;
299 const oldReturnValue = ctx.returnValue;
300
301
302 ctx.scopes = [{}];
303 ctx.refs = [];
304 ctx.conditionalCode = false;
305 ctx.fnBuilder = ctx.builder.newFunctionBuilder(`${name}_${h}`, instanceDef, ctx.functions[name].params);
306 ctx.codeBuilder = ctx.fnBuilder.newCodeBuilder();
307 ctx.uniqueNames = Object.assign({},ctx.globalNames);
308 ctx.returnValue = null;
309 ctx.returnSizes = null;
310 ctx.fileName = ctx.functions[name].fileName;
311 ctx.filePath = ctx.functions[name].filePath;
312
313 let paramLabels = [];
314
315 for (let i=0; i<ctx.functions[name].params.length; i++) {
316
317 if (paramValues[i].used) {
318 paramLabels.push(ctx.functions[name].params[i]);
319 const idRef = ctx.refs.length;
320 ctx.refs.push({
321 type: "BIGINT",
322 used: true,
323 sizes: paramValues[i].sizes,
324 label: ctx.functions[name].params[i],
325 });
326 ctx.scopes[0][ctx.functions[name].params[i]] = idRef;
327 } else {
328 const idRef = ctx.refs.length;
329 ctx.refs.push({
330 type: "BIGINT",
331 used: false,
332 sizes: paramValues[i].sizes,
333 label: ctx.functions[name].params[i],
334 value: paramValues[i].value
335 });
336 ctx.scopes[0][ctx.functions[name].params[i]] = idRef;
337 }
338 }
339
340 ctx.fnBuilder.setParams(paramLabels);
341
342 createRefs(ctx, ctx.functions[name].block);
343 if (ctx.error) return;
344
345 gen(ctx, ctx.functions[name].block);
346 if (ctx.error) return;
347
348 if (ctx.returnValue == null) {
349 if (ctx.returnSizes == null) assert(false, `Funciont ${name} does not return any value`);
350
351 ctx.fnBuilder.setBody(ctx.codeBuilder);
352 ctx.builder.addFunction(ctx.fnBuilder);
353
354 res.type = "VARVAL_CONSTSIZE";
355 res.returnSizes = ctx.returnSizes;
356 } else {
357 res.type = "CONSTVAL";
358 res.returnValue = ctx.returnValue;
359 res.returnSizes = ctx.returnSizes;
360 }
361
362 ctx.refs = oldRefs;
363 ctx.conditionalCode = oldConditionalCode;
364 ctx.codeBuilder = oldCodeBuilder;
365 ctx.fnBuilder = oldFnBuilder;
366 ctx.uniqueNames = oldUniqueNames;
367 ctx.fileName = oldFileName;
368 ctx.filePath = oldFilePath;
369 ctx.returnSizes = oldReturnSizes;
370 ctx.returnValue = oldReturnValue;
371
372 ctx.definedFunctions[h] = res;
373
374 return res;
375}
376
377
378function hashComponentCall(ctx, cIdx) {
379 // TODO: At the moment generate a diferent function for each instance of the component
380 const constParams = [];
381 for (let p in ctx.components[cIdx].params) {
382 constParams.push(p + "=" + value2str(ctx.F, ctx.components[cIdx].params[p]));
383 }
384
385 for (let n in ctx.components[cIdx].names.o) {
386 const entry = ctx.components[cIdx].names.o[n];
387 if ((entry.type == "S")&&(ctx.signals[entry.offset].o & ctx.IN)) {
388 travelSizes(n, entry.offset, entry.sizes, (prefix, offset) => {
389 if (utils.isDefined(ctx.signals[offset].v)) {
390 constParams.push(prefix + "=" + ctx.F.e(ctx.signals[offset].v));
391 }
392 });
393 }
394 }
395
396 let instanceDef = ctx.components[cIdx].template;
397 if (constParams.length>0) {
398 instanceDef += "\n";
399 constParams.sort();
400 instanceDef += constParams.join("\n");
401 }
402 const h = utils.fnvHash(instanceDef);
403 return {h, instanceDef};
404
405 function travelSizes(prefix, offset, sizes, fn) {
406 if (sizes.length == 0) {
407 fn(prefix, offset);
408 return 1;
409 } else {
410 let o = offset;
411 for (let i=0; i<sizes[0]; i++) {
412 o += travelSizes(prefix + "[" + i + "]", o, sizes.slice(1), fn);
413 }
414 return o-offset;
415 }
416 }
417}
418
419function hashFunctionCall(ctx, name, paramValues) {
420 // TODO
421 const constParams = [];
422 for (let i=0; i<ctx.functions[name].params.length; i++) {
423 if (!paramValues[i].used) {
424 constParams.push(ctx.functions[name].params[i] + utils.accSizes2Str(paramValues[i].sizes) + "=" + value2str(ctx.F, paramValues[i].value));
425 }
426 }
427 let instanceDef = name;
428 if (constParams.length>0) {
429 instanceDef += "\n";
430 constParams.sort();
431 instanceDef += constParams.join("\n");
432 }
433
434 const h = utils.fnvHash(instanceDef);
435 return {h, instanceDef};
436}
437
438function value2str(F, v) {
439 if (Array.isArray(v)) {
440 let S="[";
441 for (let i=0; i<v.length; i++) {
442 if (i>0) S+=",";
443 S+=value2str(F, v[i]);
444 }
445 S+="]";
446 return S;
447 } else {
448 return F.toString(F.e(v));
449 }
450}