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