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