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