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