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 utils = require("./utils");
21const assert = require("assert");
22const gen = require("./c_gen");
23
24module.exports = buildC;
25
26
27function buildC(ctx) {
28 ctx.code = "";
29 ctx.tmpNames = {};
30 ctx.getTmpName = getTmpName;
31 ctx.codes_sizes = [];
32 ctx.definedSizes = {};
33 ctx.addSizes = addSizes;
34
35 const entryTables = buildEntryTables(ctx);
36 const code = buildCode(ctx);
37 const compnentsArray = buildComponentsArray(ctx);
38
39 const headder = buildHeader(ctx);
40 const sizes = buildSizes(ctx);
41 const mapIsInput = buildMapIsInput(ctx);
42 const wit2Sig = buildWit2Sig(ctx);
43 const circuitVar = buildCircuitVar(ctx);
44
45 return "" +
46 headder + "\n" +
47 sizes + "\n" +
48 entryTables + "\n" +
49 code + "\n" +
50 compnentsArray + "\n" +
51 mapIsInput + "\n" +
52 wit2Sig +"\n" +
53 circuitVar;
54}
55
56function buildEntryTables(ctx) {
57
58 const codes_hashMaps = [];
59 const codes_componentEntries = [];
60 const definedHashTables = {};
61 for (let i=0; i<ctx.components.length; i++) {
62 const {htName, htMap} = addHashTable(i);
63
64 let code = "";
65 const componentEntriesTableName = ctx.getTmpName("entryTable_" + ctx.components[i].template);
66
67 code += `Circom_ComponentEntry ${componentEntriesTableName}[${htMap.length}] = {\n`;
68 for (let j=0; j<htMap.length; j++) {
69 const entry = ctx.components[i].names.o[htMap[j]];
70 code += j>0 ? " ," : " ";
71 const sizeName = ctx.addSizes(entry.sizes);
72
73 const ty = entry.type == "S" ? "_typeSignal" : "_typeComponent";
74 code += `{${entry.offset},${sizeName}, ${ty}}\n`;
75 }
76 code += "};\n";
77 codes_componentEntries.push(code);
78
79 ctx.components[i].htName = htName;
80 ctx.components[i].etName = componentEntriesTableName;
81 }
82
83
84 return "" +
85 "// HashMaps\n" +
86 codes_hashMaps.join("\n") + "\n" +
87 "\n" +
88 "// Component Entries\n" +
89 codes_componentEntries.join("\n") + "\n" +
90 "\n";
91
92 function addHashTable(cIdx) {
93 const keys = Object.keys(ctx.components[cIdx].names.o);
94 assert(keys.length<128);
95 keys.sort((a,b) => ((a>b) ? 1 : -1));
96 const h = utils.fnvHash(keys.join(","));
97 if (definedHashTables[h]) return definedHashTables[h];
98 definedHashTables[h] = {};
99 definedHashTables[h].htName = ctx.getTmpName("ht_"+ctx.components[cIdx].template);
100 definedHashTables[h].htMap = [];
101 const t = [];
102 for (let i=0; i<keys.length; i++) {
103 definedHashTables[h].htMap[i] = keys[i];
104
105 const h2 = utils.fnvHash(keys[i]);
106 let pos = parseInt(h2.slice(-2), 16);
107 while (t[pos]) pos = (pos + 1) % 256;
108 t[pos] = [h2, i];
109 }
110 let code = `Circom_HashEntry ${definedHashTables[h].htName}[256] = {`;
111 for (let i=0; i<256; i++) {
112 code += i>0 ? "," : "";
113 if (t[i]) {
114 code += `{0x${t[i][0]}LL, ${t[i][1]}} /* ${keys[t[i][1]]} */`;
115 } else {
116 code += "{0,0}";
117 }
118 }
119 code += "};\n";
120
121 codes_hashMaps.push(code);
122
123 return definedHashTables[h];
124 }
125}
126
127function buildCode(ctx) {
128 const globalNames = ctx.tmpNames;
129
130 const fDefined = {};
131
132 const functions = [];
133 for (let f in ctx.functions) {
134 ctx.scope = {};
135 const paramsList = [];
136 for (let p in ctx.functions[f].params) {
137 const param = ctx.functions[f].params[p];
138 paramsList.push("POINTER "+param.name);
139
140 ctx.scope[param.name] = {
141 type: "LOCAL",
142 sels: param.sels,
143 getter: () => { return param.name; },
144 };
145 }
146
147 ctx.code += "void "+f+"(POINTER _ret, "+paramsList.join(",")+") {\n";
148
149 ctx.code += gen(ctx, ctx.functions[f].block);
150 ctx.code += "}";
151 }
152
153 for (let i=0; i<ctx.components.length; i++) {
154 const h = hashComponentCall(ctx, i);
155 const fName = ctx.components[i].template+"_"+h;
156 if (!fDefined[fName]) {
157
158
159 const scope = {_prefix : ""};
160 ctx.scopes = [scope];
161 ctx.nScopes = 0;
162 ctx.code = "";
163 ctx.codeHeader = "// Header\n";
164 ctx.codeFooter = "// Footer\n";
165 ctx.tmpNames = Object.assign({},globalNames);
166
167 for (let p in ctx.components[i].params) {
168 newRef(ctx, "BIGINT", p, ctx.components[i].params[p]);
169 }
170
171 gen(ctx, ctx.templates[ctx.components[i].template].block);
172
173 const S = `void ${fName}(Circom_CalcWit *ctx) {\n` +
174 utils.ident(
175 ctx.codeHeader + "\n" +
176 ctx.code + "\n" +
177 ctx.codeFooter
178 ) +
179 "}\n";
180
181 functions.push(S);
182 }
183 ctx.components[i].fnName = fName;
184 }
185
186 return functions.join("\n");
187}
188
189function buildComponentsArray(ctx) {
190
191 const ccodes = [];
192 ccodes.push(`Circom_Component _components[${ctx.components.length}] = {\n`);
193 for (let i=0; i< ctx.components.length; i++) {
194 ccodes.push(i>0 ? " ," : " ");
195 ccodes.push(`{${ctx.components[i].htName},${ctx.components[i].etName},${ctx.components[i].fnName}, ${ctx.components[i].nInSignals}}\n`);
196 }
197 ccodes.push("};\n");
198 const codeComponents = ccodes.join("");
199
200 return "" +
201 "// Components\n" +
202 codeComponents +
203 "\n";
204}
205
206
207function buildHeader(ctx) {
208 return "#include \"circom.h\"\n" +
209 "#include \"calcwit.h\"\n" +
210 `#define NSignals ${ctx.signals.length}\n` +
211 `#define NComponents ${ctx.components.length}\n` +
212 `#define NInputs ${ctx.components[ ctx.getComponentIdx("main") ].nInSignals}\n`+
213 `#define NOutputs ${ctx.totals[ ctx.stOUTPUT ]}\n`+
214 `#define NVars ${ctx.totals[ctx.stONE] + ctx.totals[ctx.stOUTPUT] + ctx.totals[ctx.stPUBINPUT] + ctx.totals[ctx.stPRVINPUT] + ctx.totals[ctx.stINTERNAL]}\n` +
215 "\n";
216}
217
218function buildSizes(ctx) {
219 return "// Sizes\n" +
220 ctx.codes_sizes.join("\n");
221}
222
223
224function buildMapIsInput(ctx) {
225 const arr = [];
226 let line = "";
227 let acc = 0;
228 let i;
229 for (i=0; i<ctx.signals.length; i++) {
230 if (ctx.signals[i].o & ctx.IN) {
231 acc = acc | (1 << (i%32) );
232 }
233 if ((i+1)%32==0) {
234 line += (i>31) ? "," : " ";
235 line += toHex(acc);
236 acc = 0;
237 if ( i % (32*64) == 0) {
238 arr.push(line);
239 line = "";
240 }
241 }
242 }
243
244 if ((i%32) != 0) {
245 line += (i>31) ? "," : " ";
246 line += toHex(acc);
247 }
248 if (line != "") {
249 arr.push(line);
250 }
251
252 return "// mapIsArray\n" +
253 `u32 _mapIsInput[${Math.floor((ctx.signals.length-1) / 32)+1}] = {\n`+
254 arr.join("\n") + "\n" +
255 "};\n";
256
257 function toHex(number) {
258 if (number < 0) number = 0xFFFFFFFF + number + 1;
259 let S=number.toString(16).toUpperCase();
260 while (S.length<8) S = "0" + S;
261 return "0x"+S;
262 }
263}
264
265
266function buildWit2Sig(ctx) {
267 const codes = [];
268 const NVars =
269 ctx.totals[ctx.stONE] +
270 ctx.totals[ctx.stOUTPUT] +
271 ctx.totals[ctx.stPUBINPUT] +
272 ctx.totals[ctx.stPRVINPUT] +
273 ctx.totals[ctx.stINTERNAL];
274 const arr = Array(NVars);
275 for (let i=0; i<ctx.signals.length; i++) {
276 const outIdx = ctx.signals[i].id;
277 if (typeof outIdx == "undefined") continue;
278 if (ctx.signals[i].e>=0) continue; // If has an alias, continue..
279 assert(outIdx<NVars);
280 if (typeof arr[ctx.signals[i].id] == "undefined") {
281 arr[outIdx] = i;
282 }
283 }
284 codes.push("// Signal Table\n");
285 codes.push(`int _wit2sig[${NVars}] = {\n`);
286 let code = "";
287 for (let i=0; i<NVars; i++) {
288 code += (i>0) ? ",": " ";
289 code += arr[i];
290 if ((i>0)&&(i%64 == 0)) {
291 if (code != "") codes.push(code + "\n");
292 codes.push(code);
293 code =0;
294 }
295 }
296 if (code != "") codes.push(code + "\n");
297 codes.push("};\n");
298
299 return codes.join("");
300
301}
302
303
304function buildCircuitVar() {
305 return "Circom_Circuit _circuit = {\n" +
306 " NSignals,\n"+
307 " NComponents,\n"+
308 " NInputs,\n"+
309 " NOutputs,\n"+
310 " NVars,\n"+
311 " _wit2sig,\n"+
312 " _components,\n"+
313 " _mapIsInput\n"+
314 "};\n";
315}
316
317
318
319function hashComponentCall(ctx, cIdx) {
320 // TODO: At the moment generate a diferent function for each instance of the component
321 return cIdx;
322}
323
324function getTmpName(_suggestedName) {
325 let suggestedName;
326 if (_suggestedName) {
327 suggestedName = trimUnderscore(_suggestedName);
328 } else {
329 suggestedName = "tmp";
330 }
331
332 if (typeof(this.tmpNames[suggestedName]) == "undefined") {
333 this.tmpNames[suggestedName] = 1;
334 return "_"+suggestedName;
335 } else {
336 const name = "_" + suggestedName + "_" + this.tmpNames[suggestedName];
337 this.tmpNames[suggestedName]++;
338 return name;
339 }
340
341 function trimUnderscore(str) {
342 let p1=0;
343 while ((p1 < str.length)&&(str[p1] == "_")) p1++;
344 let p2=str.length;
345 while ((p2 > 0)&&(str[p2-1] == "_")) p2--;
346
347 return str.slice(p1,p2);
348 }
349
350}
351
352function addSizes(_sizes) {
353 const sizes = _sizes || [];
354 let name = "sizes";
355 for (let i=0; i<sizes.length;i++) {
356 name+="_"+sizes[i];
357 }
358 if (name=="sizes") name="sizes_0";
359
360 if (this.definedSizes[name]) return this.definedSizes[name];
361
362 const labelName = this.getTmpName(name);
363 this.definedSizes[name] = labelName;
364
365 const accSizes = utils.accSizes(sizes);
366
367 let code = `Circom_Size ${labelName}[${accSizes.length}] = {`;
368 for (let i=0; i<accSizes.length; i++) {
369 if (i>0) code += ",";
370 code += accSizes[i];
371 }
372 code += "};\n";
373 this.codes_sizes.push(code);
374
375 return labelName;
376}
377