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