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