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