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