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