circom/src/c_build.js
src/c_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("./c_gen").gen;
24const createRefs = require("./c_gen").createRefs;
25
26module.exports = buildC;
27
28
29function buildC(ctx) {
30 ctx.definedFunctions = {};
31 ctx.functionCodes = [];
32 ctx.buildFunction = buildFunction;
33 ctx.code = "";
34 ctx.conditionalCodeHeader = "";
35 ctx.codes_sizes = [];
36 ctx.definedSizes = {};
37 ctx.addSizes = addSizes;
38
39 const entryTables = buildEntryTables(ctx);
40 ctx.globalNames = ctx.uniqueNames;
41
42 const code = buildCode(ctx);
43 const functions = buildFuncFunctions(ctx);
44 const compnentsArray = buildComponentsArray(ctx);
45
46 const headder = buildHeader(ctx);
47 const sizes = buildSizes(ctx);
48 const mapIsInput = buildMapIsInput(ctx);
49 const wit2Sig = buildWit2Sig(ctx);
50 const circuitVar = buildCircuitVar(ctx);
51
52 return "" +
53 headder + "\n" +
54 sizes + "\n" +
55 entryTables + "\n" +
56 functions + "\n" +
57 code + "\n" +
58 compnentsArray + "\n" +
59 mapIsInput + "\n" +
60 wit2Sig +"\n" +
61 circuitVar;
62}
63
64function buildEntryTables(ctx) {
65
66 const codes_hashMaps = [];
67 const codes_componentEntries = [];
68 const definedHashTables = {};
69 for (let i=0; i<ctx.components.length; i++) {
70 const {htName, htMap} = addHashTable(i);
71
72 let code = "";
73 const componentEntriesTableName = ctx.getUniqueName("_entryTable" + ctx.components[i].template);
74
75 code += `Circom_ComponentEntry ${componentEntriesTableName}[${htMap.length}] = {\n`;
76 for (let j=0; j<htMap.length; j++) {
77 const entry = ctx.components[i].names.o[htMap[j]];
78 code += j>0 ? " ," : " ";
79 const sizeName = ctx.addSizes(entry.sizes);
80
81 const ty = entry.type == "S" ? "_typeSignal" : "_typeComponent";
82 code += `{${entry.offset},${sizeName}, ${ty}}\n`;
83 }
84 code += "};\n";
85 codes_componentEntries.push(code);
86
87 ctx.components[i].htName = htName;
88 ctx.components[i].etName = componentEntriesTableName;
89 }
90
91
92 return "" +
93 "// HashMaps\n" +
94 codes_hashMaps.join("\n") + "\n" +
95 "\n" +
96 "// Component Entries\n" +
97 codes_componentEntries.join("\n") + "\n" +
98 "\n";
99
100 function addHashTable(cIdx) {
101 const keys = Object.keys(ctx.components[cIdx].names.o);
102 assert(keys.length<128);
103 keys.sort((a,b) => ((a>b) ? 1 : -1));
104 const h = utils.fnvHash(keys.join(","));
105 if (definedHashTables[h]) return definedHashTables[h];
106 definedHashTables[h] = {};
107 definedHashTables[h].htName = ctx.getUniqueName("_ht"+ctx.components[cIdx].template);
108 definedHashTables[h].htMap = [];
109 const t = [];
110 for (let i=0; i<keys.length; i++) {
111 definedHashTables[h].htMap[i] = keys[i];
112
113 const h2 = utils.fnvHash(keys[i]);
114 let pos = parseInt(h2.slice(-2), 16);
115 while (t[pos]) pos = (pos + 1) % 256;
116 t[pos] = [h2, i];
117 }
118 let code = `Circom_HashEntry ${definedHashTables[h].htName}[256] = {`;
119 for (let i=0; i<256; i++) {
120 code += i>0 ? "," : "";
121 if (t[i]) {
122 code += `{0x${t[i][0]}LL, ${t[i][1]}} /* ${keys[t[i][1]]} */`;
123 } else {
124 code += "{0,0}";
125 }
126 }
127 code += "};\n";
128
129 codes_hashMaps.push(code);
130
131 return definedHashTables[h];
132 }
133}
134
135function buildCode(ctx) {
136
137 const fDefined = {};
138
139 const fnComponents = [];
140 for (let i=0; i<ctx.components.length; i++) {
141 const {h, instanceDef} = hashComponentCall(ctx, i);
142 const fName = ctx.components[i].template+"_"+h;
143 if (!fDefined[fName]) {
144
145
146 ctx.scopes = [{}];
147 ctx.conditionalCode = false;
148 ctx.code = "";
149 ctx.codeHeader = "// Header\n";
150 ctx.codeFooter = "// Footer\n";
151 ctx.uniqueNames = Object.assign({},ctx.globalNames);
152 ctx.refs = [];
153 ctx.fileName = ctx.templates[ctx.components[i].template].fileName;
154 ctx.filePath = ctx.templates[ctx.components[i].template].filePath;
155
156 for (let p in ctx.components[i].params) {
157 if (ctx.scopes[0][p]) return ctx.throwError(`Repeated parameter at ${ctx.components[i].template}: ${p}`);
158 const refId = ctx.refs.length;
159 ctx.refs.push({
160 type: "BIGINT",
161 used: false,
162 value: utils.flatArray(ctx.components[i].params[p]),
163 sizes: utils.accSizes(utils.extractSizes(ctx.components[i].params[p])),
164 label: ctx.getUniqueName(p)
165 });
166 ctx.scopes[0][p] = refId;
167 }
168
169 createRefs(ctx, ctx.templates[ctx.components[i].template].block);
170 if (ctx.error) return;
171
172 gen(ctx, ctx.templates[ctx.components[i].template].block);
173 if (ctx.error) return;
174
175 const S =
176 "/*\n" +
177 instanceDef +
178 "\n*/\n" +
179 `void ${fName}(Circom_CalcWit *ctx, int __cIdx) {\n` +
180 utils.ident(
181 ctx.codeHeader + "\n" +
182 ctx.code + "\n" +
183 "ctx->finished(__cIdx);\n" +
184 ctx.codeFooter
185 ) +
186 "}\n";
187
188 fnComponents.push(S);
189 fDefined[fName] = true;
190 }
191 ctx.components[i].fnName = fName;
192 }
193
194 return fnComponents.join("\n");
195}
196
197function buildFuncFunctions(ctx) {
198 return "// Functions\n" +
199 ctx.functionCodes.join("\n");
200}
201
202function buildComponentsArray(ctx) {
203
204 const ccodes = [];
205 ccodes.push(`Circom_Component _components[${ctx.components.length}] = {\n`);
206 for (let i=0; i< ctx.components.length; i++) {
207 let newThread;
208 if (ctx.newThreadTemplates) {
209 if (ctx.newThreadTemplates.test(ctx.components[i].template)) {
210 newThread = "true";
211 } else {
212 newThread = "false";
213 }
214 } else {
215 newThread = "false";
216 }
217 ccodes.push(i>0 ? " ," : " ");
218 ccodes.push(`{${ctx.components[i].htName},${ctx.components[i].etName},${ctx.components[i].fnName}, ${ctx.components[i].nInSignals}, ${newThread}}\n`);
219 }
220 ccodes.push("};\n");
221 const codeComponents = ccodes.join("");
222
223 return "" +
224 "// Components\n" +
225 codeComponents +
226 "\n";
227}
228
229
230function buildHeader(ctx) {
231 return "#include \"circom.h\"\n" +
232 "#include \"calcwit.h\"\n" +
233 `#define NSignals ${ctx.signals.length}\n` +
234 `#define NComponents ${ctx.components.length}\n` +
235 `#define NInputs ${ctx.components[ ctx.getComponentIdx("main") ].nInSignals}\n`+
236 `#define NOutputs ${ctx.totals[ ctx.stOUTPUT ]}\n`+
237 `#define NVars ${ctx.totals[ctx.stONE] + ctx.totals[ctx.stOUTPUT] + ctx.totals[ctx.stPUBINPUT] + ctx.totals[ctx.stPRVINPUT] + ctx.totals[ctx.stINTERNAL]}\n` +
238 `#define __P__ "${ctx.field.p.toString()}"\n` +
239 "\n";
240}
241
242function buildSizes(ctx) {
243 return "// Sizes\n" +
244 ctx.codes_sizes.join("\n");
245}
246
247
248function buildMapIsInput(ctx) {
249 const arr = [];
250 let line = "";
251 let acc = 0;
252 let i;
253 for (i=0; i<ctx.signals.length; i++) {
254 if (ctx.signals[i].o & ctx.IN) {
255 acc = acc | (1 << (i%32) );
256 }
257 if ((i+1)%32==0) {
258 line += (i>31) ? "," : " ";
259 line += toHex(acc);
260 acc = 0;
261 if ( (i+1) % (32*64) == 0) {
262 arr.push(line);
263 line = "";
264 }
265 }
266 }
267
268 if ((i%32) != 0) {
269 line += (i>31) ? "," : " ";
270 line += toHex(acc);
271 }
272 if (line != "") {
273 arr.push(line);
274 }
275
276 return "// mapIsArray\n" +
277 `u32 _mapIsInput[${Math.floor((ctx.signals.length-1) / 32)+1}] = {\n`+
278 arr.join("\n") + "\n" +
279 "};\n";
280
281 function toHex(number) {
282 if (number < 0) number = 0xFFFFFFFF + number + 1;
283 let S=number.toString(16).toUpperCase();
284 while (S.length<8) S = "0" + S;
285 return "0x"+S;
286 }
287}
288
289
290function buildWit2Sig(ctx) {
291 const codes = [];
292 const NVars =
293 ctx.totals[ctx.stONE] +
294 ctx.totals[ctx.stOUTPUT] +
295 ctx.totals[ctx.stPUBINPUT] +
296 ctx.totals[ctx.stPRVINPUT] +
297 ctx.totals[ctx.stINTERNAL];
298 const arr = Array(NVars);
299 for (let i=0; i<ctx.signals.length; i++) {
300 const outIdx = ctx.signals[i].id;
301 if (ctx.signals[i].e>=0) continue; // If has an alias, continue..
302 assert(typeof outIdx != "undefined", `Signal ${i} does not have index`);
303 if (outIdx>=NVars) continue; // Is a constant or a discarded variable
304 if (typeof arr[ctx.signals[i].id] == "undefined") {
305 arr[outIdx] = i;
306 }
307 }
308 codes.push("// Signal Table\n");
309 codes.push(`int _wit2sig[${NVars}] = {\n`);
310 let code = "";
311 for (let i=0; i<NVars; i++) {
312 code += (i>0) ? ",": " ";
313 code += arr[i];
314 if ((i>0)&&(i%64 == 0)) {
315 if (code != "") {
316 codes.push(code + "\n");
317 } else {
318 codes.push(code);
319 }
320 code ="";
321 }
322 }
323 if (code != "") codes.push(code + "\n");
324 codes.push("};\n");
325
326 return codes.join("");
327
328}
329
330
331function buildCircuitVar() {
332 return "Circom_Circuit _circuit = {\n" +
333 " NSignals,\n"+
334 " NComponents,\n"+
335 " NInputs,\n"+
336 " NOutputs,\n"+
337 " NVars,\n"+
338 " _wit2sig,\n"+
339 " _components,\n"+
340 " _mapIsInput,\n"+
341 " __P__\n" +
342 "};\n";
343}
344
345
346
347
348function addSizes(_sizes) {
349 const sizes = _sizes || [];
350 let name = "sizes";
351 for (let i=0; i<sizes.length;i++) {
352 name+="_"+sizes[i];
353 }
354 if (name=="sizes") name="sizes_0";
355
356 if (this.definedSizes[name]) return this.definedSizes[name];
357 const labelName = this.getUniqueName(name);
358 this.definedSizes[name] = labelName;
359
360 const accSizes = utils.accSizes(sizes);
361
362 let code = `Circom_Size ${labelName}[${accSizes.length}] = {`;
363 for (let i=0; i<accSizes.length; i++) {
364 if (i>0) code += ",";
365 code += accSizes[i];
366 }
367 code += "};\n";
368 this.codes_sizes.push(code);
369
370 return labelName;
371}
372
373function buildFunction(name, paramValues) {
374 const ctx = this;
375 const {h, instanceDef} = hashFunctionCall(ctx, name, paramValues);
376
377 if (ctx.definedFunctions[h]) return ctx.definedFunctions[h];
378
379 const res = {
380 fnName: `${name}_${h}`
381 };
382
383 const oldRefs = ctx.refs;
384 const oldConditionalCode = ctx.conditionalCode;
385 const oldCode = ctx.code;
386 const oldCodeHeader = ctx.codeHeader;
387 const oldCodeFooter = ctx.codeFooter;
388 const oldUniqueNames = ctx.uniqueNames;
389 const oldFileName = ctx.fileName;
390 const oldFilePath = ctx.oldFilePath;
391 const oldReturnSizes = ctx.returnSizes;
392 const oldReturnValue = ctx.returnValue;
393
394
395 ctx.scopes = [{}];
396 ctx.refs = [];
397 ctx.conditionalCode = false;
398 ctx.code = "";
399 ctx.codeHeader = "// Header\n";
400 ctx.codeFooter = "// Footer\n";
401 ctx.uniqueNames = Object.assign({},ctx.globalNames);
402 ctx.returnValue = null;
403 ctx.returnSizes = null;
404 ctx.fileName = ctx.functions[name].fileName;
405 ctx.filePath = ctx.functions[name].filePath;
406
407 let paramsStr = "";
408
409 for (let i=0; i<ctx.functions[name].params.length; i++) {
410
411 if (paramValues[i].used) {
412 paramsStr += `,PBigInt ${ctx.functions[name].params[i]}`;
413 const idRef = ctx.refs.length;
414 ctx.refs.push({
415 type: "BIGINT",
416 used: true,
417 sizes: paramValues[i].sizes,
418 label: ctx.functions[name].params[i],
419 });
420 ctx.scopes[0][ctx.functions[name].params[i]] = idRef;
421 } else {
422 const idRef = ctx.refs.length;
423 ctx.refs.push({
424 type: "BIGINT",
425 used: false,
426 sizes: paramValues[i].sizes,
427 label: ctx.functions[name].params[i],
428 value: paramValues[i].value
429 });
430 ctx.scopes[0][ctx.functions[name].params[i]] = idRef;
431 }
432 }
433
434 createRefs(ctx, ctx.functions[name].block);
435 if (ctx.error) return;
436
437 gen(ctx, ctx.functions[name].block);
438 if (ctx.error) return;
439
440 if (ctx.returnValue == null) {
441 if (ctx.returnSizes == null) assert(false, `Funciont ${name} does not return any value`);
442 res.type = "VARVAL_CONSTSIZE";
443 let code =
444 "/*\n" +
445 instanceDef +
446 "\n*/\n" +
447 `void ${name}_${h}(Circom_CalcWit *ctx, PBigInt __retValue ${paramsStr}) {`;
448 code += utils.ident(ctx.codeHeader);
449 code += utils.ident(ctx.code);
450 code += utils.ident("returnFunc:\n");
451 code += utils.ident(ctx.codeFooter);
452 code += "}\n";
453 res.returnSizes = ctx.returnSizes;
454 ctx.functionCodes.push(code);
455 } else {
456 res.type = "CONSTVAL";
457 res.returnValue = ctx.returnValue;
458 res.returnSizes = ctx.returnSizes;
459 }
460
461 ctx.refs = oldRefs;
462 ctx.conditionalCode = oldConditionalCode;
463 ctx.code = oldCode;
464 ctx.codeHeader = oldCodeHeader;
465 ctx.codeFooter = oldCodeFooter;
466 ctx.uniqueNames = oldUniqueNames;
467 ctx.fileName = oldFileName;
468 ctx.filePath = oldFilePath;
469 ctx.returnSizes = oldReturnSizes;
470 ctx.returnValue = oldReturnValue;
471
472 ctx.definedFunctions[h] = res;
473
474 return res;
475}
476
477
478
479function hashComponentCall(ctx, cIdx) {
480 // TODO: At the moment generate a diferent function for each instance of the component
481 const constParams = [];
482 for (let p in ctx.components[cIdx].params) {
483 constParams.push(p + "=" + value2str(ctx.components[cIdx].params[p]));
484 }
485
486 for (let n in ctx.components[cIdx].names.o) {
487 const entry = ctx.components[cIdx].names.o[n];
488 if ((entry.type == "S")&&(ctx.signals[entry.offset].o & ctx.IN)) {
489 travelSizes(n, entry.offset, entry.sizes, (prefix, offset) => {
490 if (utils.isDefined(ctx.signals[offset].v)) {
491 constParams.push(prefix + "=" + bigInt(ctx.signals[offset].value));
492 }
493 });
494 }
495 }
496
497 let instanceDef = ctx.components[cIdx].template;
498 if (constParams.length>0) {
499 instanceDef += "\n";
500 constParams.sort();
501 instanceDef += constParams.join("\n");
502 }
503 const h = utils.fnvHash(instanceDef);
504 return {h, instanceDef};
505
506 function travelSizes(prefix, offset, sizes, fn) {
507 if (sizes.length == 0) {
508 fn(prefix, offset);
509 return 1;
510 } else {
511 let o = offset;
512 for (let i=0; i<sizes[0]; i++) {
513 o += travelSizes(prefix + "[" + i + "]", o, sizes.slice(1), fn);
514 }
515 return o-offset;
516 }
517 }
518}
519
520function hashFunctionCall(ctx, name, paramValues) {
521 // TODO
522 const constParams = [];
523 for (let i=0; i<ctx.functions[name].params.length; i++) {
524 if (!paramValues[i].used) {
525 constParams.push(ctx.functions[name].params[i] + utils.accSizes2Str(paramValues[i].sizes) + "=" + value2str(paramValues[i].value));
526 }
527 }
528 let instanceDef = name;
529 if (constParams.length>0) {
530 instanceDef += "\n";
531 constParams.sort();
532 instanceDef += constParams.join("\n");
533 }
534
535 const h = utils.fnvHash(instanceDef);
536 return {h, instanceDef};
537}
538
539function value2str(v) {
540 if (Array.isArray(v)) {
541 let S="[";
542 for (let i=0; i<v.length; i++) {
543 if (i>0) S+=",";
544 S+=value2str(v[i]);
545 }
546 S+="]";
547 return S;
548 } else {
549 return bigInt(v).toString();
550 }
551}