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