circom/ports/c/builder.js
ports/c/builder.jsRaw
1const streamFromMultiArray = require("../../src/streamfromarray_txt.js");
2const utils = require("../../src/utils");
3const assert = require("assert");
4const Scalar = require("ffjavascript").Scalar;
5const F1Field = require("ffjavascript").F1Field;
6const BigArray = require("../../src/bigarray");
7
8function ref2src(c) {
9 if ((c[0] == "R")||(c[0] == "RI")) {
10 return c[1];
11 } else if (c[0] == "V") {
12 return c[1].toString();
13 } else if (c[0] == "C") {
14 return `(ctx->circuit->constants + ${c[1]})`;
15 } else if (c[0] == "CC") {
16 return "__cIdx";
17 } else {
18 assert(false);
19 }
20}
21
22class CodeBuilderC {
23 constructor() {
24 this.ops = [];
25 }
26
27 addComment(comment) {
28 this.ops.push({op: "COMMENT", comment});
29 }
30
31 addBlock(block) {
32 this.ops.push({op: "BLOCK", block});
33 }
34
35 calcOffset(dLabel, offsets) {
36 this.ops.push({op: "CALCOFFSETS", dLabel, offsets});
37 }
38
39 assign(dLabel, src, sOffset) {
40 this.ops.push({op: "ASSIGN", dLabel, src, sOffset});
41 }
42
43 getSubComponentOffset(dLabel, component, hash, hashLabel) {
44 this.ops.push({op: "GETSUBCOMPONENTOFFSET", dLabel, component, hash, hashLabel});
45 }
46
47 getSubComponentSizes(dLabel, component, hash, hashLabel) {
48 this.ops.push({op: "GETSUBCOMPONENTSIZES", dLabel, component, hash, hashLabel});
49 }
50
51 getSignalOffset(dLabel, component, hash, hashLabel) {
52 this.ops.push({op: "GETSIGNALOFFSET", dLabel, component, hash, hashLabel});
53 }
54
55 getSignalSizes(dLabel, component, hash, hashLabel) {
56 this.ops.push({op: "GETSIGNALSIZES", dLabel, component, hash, hashLabel});
57 }
58
59 setSignal(component, signal, value) {
60 this.ops.push({op: "SETSIGNAL", component, signal, value});
61 }
62
63 getSignal(dLabel, component, signal) {
64 this.ops.push({op: "GETSIGNAL", dLabel, component, signal});
65 }
66
67 copyN(dLabel, offset, src, n) {
68 this.ops.push({op: "COPYN", dLabel, offset, src, n});
69 }
70
71 copyNRet(src, n) {
72 this.ops.push({op: "COPYNRET", src, n});
73 }
74
75 fieldOp(dLabel, fOp, params) {
76 this.ops.push({op: "FOP", dLabel, fOp, params});
77 }
78
79 ret() {
80 this.ops.push({op: "RET"});
81 }
82
83 addLoop(condLabel, body) {
84 this.ops.push({op: "LOOP", condLabel, body});
85 }
86
87 addIf(condLabel, thenCode, elseCode) {
88 this.ops.push({op: "IF", condLabel, thenCode, elseCode});
89 }
90
91 fnCall(fnName, retLabel, params) {
92 this.ops.push({op: "FNCALL", fnName, retLabel, params});
93 }
94
95 checkConstraint(a, b, strErr) {
96 this.ops.push({op: "CHECKCONSTRAINT", a, b, strErr});
97 }
98
99 log(val) {
100 this.ops.push({op: "LOG", val});
101 }
102
103 concat(cb) {
104 this.ops.push(...cb.ops);
105 }
106
107 hasCode() {
108 for (let i=0; i<this.ops.length; i++) {
109 if (this.ops[i].op != "COMMENT") return true;
110 }
111 return false;
112 }
113
114 _buildOffset(offsets) {
115 let rN=0;
116 let S = "";
117 offsets.forEach((o) => {
118 if ((o[0][0] == "V") && (o[1][0]== "V")) {
119 rN += o[0][1]*o[1][1];
120 return;
121 }
122 let f="";
123 if (o[0][0] == "V") {
124 if (o[0][1]==0) return;
125 f += o[0][1];
126 } else if (o[0][0] == "RI") {
127 if (o[0][1]==0) return;
128 f += o[0][1];
129 } else if (o[0][0] == "R") {
130 f += `Fr_toInt(${o[0][1]})`;
131 } else {
132 assert(false);
133 }
134 if (o[1][0] == "V") {
135 if (o[1][1]==0) return;
136 if (o[1][1]>1) {
137 f += "*" + o[1][1];
138 }
139 } else if (o[1][0] == "RS") {
140 f += `*${o[1][1]}[${o[1][2]}]`;
141 } else {
142 assert(false);
143 }
144 if (S!="") S+= " + ";
145 S += f;
146 });
147 if (rN>0) {
148 S = `${rN} + ${S}`;
149 }
150 return S;
151 }
152
153 build(code) {
154 this.ops.forEach( (o) => {
155 if (o.op == "COMMENT") {
156 code.push(`/* ${o.comment} */`);
157 } else if (o.op == "BLOCK") {
158 const codeBlock=[];
159 o.block.build(codeBlock);
160 code.push(utils.ident(codeBlock));
161 } else if (o.op == "CALCOFFSETS") {
162 code.push(`${o.dLabel} = ${this._buildOffset(o.offsets)};`);
163 } else if (o.op == "ASSIGN") {
164 const oS = ref2src(o.sOffset);
165 if (oS != "0") {
166 code.push(`${o.dLabel} = ${ref2src(o.src)} + ${oS};`);
167 } else {
168 code.push(`${o.dLabel} = ${ref2src(o.src)};`);
169 }
170 } else if (o.op == "GETSUBCOMPONENTOFFSET") {
171 code.push(`${o.dLabel} = ctx->getSubComponentOffset(${ref2src(o.component)}, 0x${o.hash}LL /* ${o.hashLabel} */);`);
172 } else if (o.op == "GETSUBCOMPONENTSIZES") {
173 code.push(`${o.dLabel} = ctx->getSubComponentSizes(${ref2src(o.component)}, 0x${o.hash}LL /* ${o.hashLabel} */);`);
174 } else if (o.op == "GETSIGNALOFFSET") {
175 code.push(`${o.dLabel} = ctx->getSignalOffset(${ref2src(o.component)}, 0x${o.hash}LL /* ${o.hashLabel} */);`);
176 } else if (o.op == "GETSIGNALSIZES") {
177 code.push(`${o.dLabel} = ctx->getSignalSizes(${ref2src(o.component)}, 0x${o.hash}LL /* ${o.hashLabel} */);`);
178 } else if (o.op == "SETSIGNAL") {
179 code.push(`ctx->setSignal(__cIdx, ${ref2src(o.component)}, ${ref2src(o.signal)}, ${ref2src(o.value)});`);
180 } else if (o.op == "GETSIGNAL") {
181 code.push(`ctx->getSignal(__cIdx, ${ref2src(o.component)}, ${ref2src(o.signal)}, ${o.dLabel});`);
182 } else if (o.op == "COPYN") {
183 const oS = ref2src(o.offset);
184 const dLabel = (oS != "0") ? (o.dLabel + "+" + oS) : o.dLabel;
185 code.push(`Fr_copyn(${dLabel}, ${ref2src(o.src)}, ${o.n});`);
186 } else if (o.op == "COPYNRET") {
187 code.push(`Fr_copyn(__retValue, ${ref2src(o.src)}, ${o.n});`);
188 } else if (o.op == "RET") {
189 code.push("goto returnFunc;");
190 } else if (o.op == "FOP") {
191 let paramsS = "";
192 for (let i=0; i<o.params.length; i++) {
193 if (i>0) paramsS += ", ";
194 paramsS += ref2src(o.params[i]);
195 }
196 code.push(`Fr_${o.fOp}(${o.dLabel}, ${paramsS});`);
197 } else if (o.op == "LOOP") {
198 code.push(`while (Fr_isTrue(${o.condLabel})) {`);
199 const body = [];
200 o.body.build(body);
201 code.push(utils.ident(body));
202 code.push("}");
203 } else if (o.op == "IF") {
204 code.push(`if (Fr_isTrue(${o.condLabel})) {`);
205 const thenCode = [];
206 o.thenCode.build(thenCode);
207 code.push(utils.ident(thenCode));
208 if (o.elseCode) {
209 code.push("} else {");
210 const elseCode = [];
211 o.elseCode.build(elseCode);
212 code.push(utils.ident(elseCode));
213 }
214 code.push("}");
215 } else if (o.op == "FNCALL") {
216 code.push(`${o.fnName}(ctx, ${o.retLabel}, ${o.params.join(",")});`);
217 } else if (o.op == "CHECKCONSTRAINT") {
218 code.push(`ctx->checkConstraint(__cIdx, ${ref2src(o.a)}, ${ref2src(o.b)}, "${o.strErr}");`);
219 } else if (o.op == "LOG") {
220 code.push(`ctx->log(${ref2src(o.val)});`);
221 }
222 });
223 }
224}
225
226class FunctionBuilderC {
227
228 constructor(name, instanceDef, type) {
229 this.name = name;
230 this.instanceDef = instanceDef;
231 this.type = type; // "COMPONENT" or "FUNCTIOM"
232 this.definedFrElements = [];
233 this.definedIntElements = [];
234 this.definedSizeElements = [];
235 this.definedPFrElements = [];
236 this.initializedElements = [];
237 this.initializedSignalOffset = [];
238 this.initializedSignalSizes = [];
239
240 }
241
242 defineFrElements(dLabel, size) {
243 this.definedFrElements.push({dLabel, size});
244 }
245
246 defineIntElement(dLabel) {
247 this.definedIntElements.push({dLabel});
248 }
249
250 defineSizesElement(dLabel) {
251 this.definedSizeElements.push({dLabel});
252 }
253
254 definePFrElement(dLabel) {
255 this.definedPFrElements.push({dLabel});
256 }
257
258 initializeFrElement(dLabel, offset, idConstant) {
259 this.initializedElements.push({dLabel, offset, idConstant});
260 }
261
262 initializeSignalOffset(dLabel, component, hash, hashLabel) {
263 this.initializedSignalOffset.push({dLabel, component, hash, hashLabel});
264 }
265
266 initializeSignalSizes(dLabel, component, hash, hashLabel) {
267 this.initializedSignalSizes.push({dLabel, component, hash, hashLabel});
268 }
269
270 setParams(params) {
271 this.params = params;
272 }
273
274 _buildHeader(code) {
275 this.definedFrElements.forEach( (o) => {
276 code.push(`FrElement ${o.dLabel}[${o.size}];`);
277 });
278 this.definedIntElements.forEach( (o) => {
279 code.push(`int ${o.dLabel};`);
280 });
281 this.definedSizeElements.forEach( (o) => {
282 code.push(`Circom_Sizes ${o.dLabel};`);
283 });
284 this.definedPFrElements.forEach( (o) => {
285 code.push(`PFrElement ${o.dLabel};`);
286 });
287 this.initializedElements.forEach( (o) => {
288 code.push(`Fr_copy(&(${o.dLabel}[${o.offset}]), ctx->circuit->constants +${o.idConstant});`);
289 });
290 this.initializedSignalOffset.forEach( (o) => {
291 code.push(`${o.dLabel} = ctx->getSignalOffset(${ref2src(o.component)}, 0x${o.hash}LL /* ${o.hashLabel} */);`);
292 });
293 this.initializedSignalSizes.forEach( (o) => {
294 code.push(`${o.dLabel} = ctx->getSignalSizes(${ref2src(o.component)}, 0x${o.hash}LL /* ${o.hashLabel} */);`);
295 });
296 }
297
298 _buildFooter(code) {
299 }
300
301 newCodeBuilder() {
302 return new CodeBuilderC();
303 }
304
305 setBody(body) {
306 this.body = body;
307 }
308
309 build(code) {
310 code.push(
311 "/*",
312 this.instanceDef,
313 "*/"
314 );
315
316 if (this.type=="COMPONENT") {
317 code.push(`void ${this.name}(Circom_CalcWit *ctx, int __cIdx) {`);
318 } else if (this.type=="FUNCTION") {
319 let sParams = "";
320 for (let i=0;i<this.params.length;i++ ) sParams += `, PFrElement ${this.params[i]}`;
321 code.push(`void ${this.name}(Circom_CalcWit *ctx, PFrElement __retValue ${sParams}) {`);
322 } else {
323 assert(false);
324 }
325
326 const fnCode = [];
327 this._buildHeader(fnCode);
328 this.body.build(fnCode);
329 if (this.type=="COMPONENT") {
330 fnCode.push("ctx->finished(__cIdx);");
331 } else if (this.type=="FUNCTION") {
332 fnCode.push("returnFunc: ;");
333 } else {
334 assert(false);
335 }
336 this._buildFooter(fnCode);
337
338 code.push(utils.ident(fnCode));
339 code.push("}");
340 }
341
342}
343
344class BuilderC {
345 constructor(p, verbose) {
346 this.F = new F1Field(p);
347
348 this.hashMaps={};
349 this.componentEntriesTables=new BigArray();
350 this.sizes ={};
351 this.constants = [];
352 this.functions = [];
353 this.components = new BigArray();
354 this.usedConstants = {};
355 this.verbose = verbose;
356 }
357
358 setHeader(header) {
359 this.header=header;
360 }
361
362 // ht is an array of 256 element that can be undefined or [Hash, Idx, KeyName] elements.
363 addHashMap(name, hm) {
364 this.hashMaps[name] = hm;
365 }
366
367 addComponentEntriesTable(name, cet) {
368 this.componentEntriesTables.push({
369 name: name,
370 cet: cet
371 });
372 }
373
374 addSizes(name, accSizes) {
375 this.sizes[name] = accSizes;
376 }
377
378 addConstant(c) {
379 c = this.F.e(c);
380 const cS = c.toString();
381 if (typeof this.usedConstants[cS] != "undefined") return this.usedConstants[cS];
382 this.constants.push(c);
383 this.usedConstants[cS] = this.constants.length - 1;
384 return this.constants.length - 1;
385 }
386
387 addFunction(fnBuilder) {
388 this.functions.push(fnBuilder);
389 }
390
391 addComponent(component) {
392 this.components.push(component);
393 }
394
395 setMapIsInput(map) {
396 this.mapIsInput = map;
397 }
398
399 setWit2Sig(wit2sig) {
400 this.wit2sig = wit2sig;
401 }
402
403
404 newComponentFunctionBuilder(name, instanceDef) {
405 return new FunctionBuilderC(name, instanceDef, "COMPONENT");
406 }
407
408 newFunctionBuilder(name, instanceDef) {
409 return new FunctionBuilderC(name, instanceDef, "FUNCTION");
410 }
411
412
413 // Body functions
414
415 _buildHeader(code) {
416 code.push(
417 "#include \"circom.h\"",
418 "#include \"calcwit.h\"",
419 `#define NSignals ${this.header.NSignals}`,
420 `#define NComponents ${this.header.NComponents}`,
421 `#define NOutputs ${this.header.NOutputs}`,
422 `#define NInputs ${this.header.NInputs}`,
423 `#define NVars ${this.header.NVars}`,
424 `#define __P__ "${this.header.P.toString()}"`,
425 ""
426 );
427 }
428
429 _buildHashMaps(code) {
430
431 code.push("// Hash Maps ");
432 for (let hmName in this.hashMaps ) {
433 const hm = this.hashMaps[hmName];
434
435 let c = `Circom_HashEntry ${hmName}[256] = {`;
436 for (let i=0; i<256; i++) {
437 c += i>0 ? "," : "";
438 if (hm[i]) {
439 c += `{0x${hm[i][0]}LL, ${hm[i][1]}} /* ${hm[i][2]} */`;
440 } else {
441 c += "{0,0}";
442 }
443 }
444 c += "};";
445 code.push(c);
446 }
447
448 }
449
450 _buildComponentEntriesTables(code) {
451 code.push("// Component Entry tables");
452 for (let i=0; i< this.componentEntriesTables.length; i++) {
453 if ((this.verbose)&&(i%100000 ==0)) console.log(`_buildComponentEntriesTables ${i}/${this.componentEntriesTables.length}`);
454 const cetName = this.componentEntriesTables[i].name;
455 const cet = this.componentEntriesTables[i].cet;
456
457 code.push(`Circom_ComponentEntry ${cetName}[${cet.length}] = {`);
458 for (let j=0; j<cet.length; j++) {
459 const ty = cet[j].type == "S" ? "_typeSignal" : "_typeComponent";
460 code.push(` ${j>0?",":" "}{${cet[j].offset},${cet[j].sizeName}, ${ty}}`);
461 }
462 code.push("};");
463 }
464 }
465
466 _buildSizes(code) {
467 code.push("// Sizes");
468 for (let sName in this.sizes) {
469 const accSizes = this.sizes[sName];
470
471 let c = `Circom_Size ${sName}[${accSizes.length}] = {`;
472 for (let i=0; i<accSizes.length; i++) {
473 if (i>0) c += ",";
474 c += accSizes[i];
475 }
476 c += "};";
477 code.push(c);
478 }
479 }
480
481 _buildConstants(code) {
482 const self = this;
483
484 code.push("// Constants");
485 code.push(`FrElement _constants[${self.constants.length}] = {`);
486 for (let i=0; i<self.constants.length; i++) {
487 if ((this.verbose)&&(i%1000000 ==0)) console.log(`_buildConstants ${i}/${this.constants.length}`);
488 code.push((i>0 ? "," : " ") + "{" + number2Code(self.constants[i]) + "}");
489 }
490 code.push("};");
491
492 function number2Code(n) {
493 const minShort = self.F.neg(self.F.e("80000000"));
494 const maxShort = self.F.e("7FFFFFFF", 16);
495
496 if ( (self.F.geq(n, minShort))
497 &&(self.F.leq(n, maxShort)))
498 {
499 if (self.F.geq(n, self.F.zero)) {
500 return addShortMontgomeryPositive(n);
501 } else {
502 return addShortMontgomeryNegative(n);
503 }
504 }
505
506 return addLongMontgomery(n);
507
508
509 function addShortMontgomeryPositive(a) {
510 return `${a.toString()}, 0x40000000, { ${getLongString(toMontgomery(a))} }`;
511 }
512
513
514 function addShortMontgomeryNegative(a) {
515 const b = -Scalar.toNumber(self.F.neg(a));
516 return `${b.toString()}, 0x40000000, { ${getLongString(toMontgomery(a))} }`;
517 }
518
519 function addLongMontgomery(a) {
520 return `0, 0xC0000000, { ${getLongString(toMontgomery(a))} }`;
521 }
522
523 function getLongString(a) {
524 let S = "";
525 const arr = Scalar.toArray(a, 0x100000000);
526 for (let i=0; i<self.F.n64*2; i+=2) {
527 const idx = arr.length-2-i;
528
529 if (i>0) S = S + ",";
530
531 if ( idx >=0) {
532 let msb = arr[idx].toString(16);
533 while (msb.length<8) msb = "0" + msb;
534
535 let lsb = arr[idx+1].toString(16);
536 while (lsb.length<8) lsb = "0" + lsb;
537
538 S += "0x" + msb + lsb + "LL";
539 } else {
540 S += "0LL";
541 }
542 }
543
544 return S;
545 }
546
547 function toMontgomery(a) {
548 return self.F.mul(a, self.F.R);
549 }
550
551 }
552 }
553
554 _buildFunctions(code) {
555 for (let i=0; i<this.functions.length; i++) {
556 const cfb = this.functions[i];
557 cfb.build(code);
558 }
559 }
560
561 _buildComponents(code) {
562 code.push("// Components");
563 code.push(`Circom_Component _components[${this.components.length}] = {`);
564 for (let i=0; i<this.components.length; i++) {
565 if ((this.verbose)&&(i%1000000 ==0)) console.log(`_buildComponents ${i}/${this.components.length}`);
566 const c = this.components[i];
567 const sep = i>0 ? " ," : " ";
568 code.push(`${sep}{${c.hashMapName}, ${c.entryTableName}, ${c.functionName}, ${c.nInSignals}, ${c.newThread}}`);
569 }
570 code.push("};");
571 }
572
573 _buildMapIsInput(code) {
574 code.push("// mapIsInput");
575 code.push(`u32 _mapIsInput[${this.mapIsInput.length}] = {`);
576 let line = "";
577 for (let i=0; i<this.mapIsInput.length; i++) {
578 if ((this.verbose)&&(i%1000000 ==0)) console.log(`_buildMapIsInput ${i}/${this.mapIsInput.length}`);
579 line += i>0 ? ", " : " ";
580 line += toHex(this.mapIsInput[i]);
581 if (((i+1) % 64)==0) {
582 code.push(" "+line);
583 line = "";
584 }
585 }
586 if (line != "") code.push(" "+line);
587 code.push("};");
588
589 function toHex(number) {
590 if (number < 0) number = 0xFFFFFFFF + number + 1;
591 let S=number.toString(16).toUpperCase();
592 while (S.length<8) S = "0" + S;
593 return "0x"+S;
594 }
595 }
596
597 _buildWit2Sig(code) {
598 code.push("// Witness to Signal Table");
599 code.push(`int _wit2sig[${this.wit2sig.length}] = {`);
600 let line = "";
601 for (let i=0; i<this.wit2sig.length; i++) {
602 if ((this.verbose)&&(i%1000000 ==0)) console.log(`_buildWit2Sig ${i}/${this.wit2sig.length}`);
603 line += i>0 ? "," : " ";
604 line += this.wit2sig[i];
605 if (((i+1) % 64) == 0) {
606 code.push(" "+line);
607 line = "";
608 }
609 }
610 if (line != "") code.push(" "+line);
611 code.push("};");
612 }
613
614 _buildCircuitVar(code) {
615
616 code.push(
617 "// Circuit Variable",
618 "Circom_Circuit _circuit = {" ,
619 " NSignals,",
620 " NComponents,",
621 " NInputs,",
622 " NOutputs,",
623 " NVars,",
624 " _wit2sig,",
625 " _components,",
626 " _mapIsInput,",
627 " _constants,",
628 " __P__",
629 "};"
630 );
631 }
632
633
634 async build(fd) {
635 const encoder = new TextEncoder("utf-8");
636 const code=new BigArray();
637 this._buildHeader(code);
638 this._buildSizes(code);
639 this._buildConstants(code);
640 this._buildHashMaps(code);
641 this._buildComponentEntriesTables(code);
642 this._buildFunctions(code);
643 this._buildComponents(code);
644 this._buildMapIsInput(code);
645 this._buildWit2Sig(code);
646 this._buildCircuitVar(code);
647 await writeCode(code);
648
649 async function writeCode(c) {
650 if (c.push) {
651 for (let i=0; i<c.length; i++) {
652 await writeCode(c[i]);
653 }
654 } else if (typeof c === "string") {
655 await fd.write(encoder.encode(c + "\n"));
656 }
657 }
658 }
659}
660
661
662module.exports = BuilderC;