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