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