circom/ports/c/buildasm/old/buildzqfield.js
ports/c/buildasm/old/buildzqfield.jsRaw
1const bigInt=require("big-integer");
2
3
4
5
6
7class ZqBuilder {
8 constructor(q, name) {
9 this.q=bigInt(q);
10 this.h = [];
11 this.c = [];
12 this.name = name;
13 }
14
15 build() {
16 this._buildHeaders();
17 this._buildAdd();
18 this._buildMul();
19
20 this.c.push(""); this.h.push("");
21 return [this.h.join("\n"), this.c.join("\n")];
22 }
23
24 _buildHeaders() {
25 this.n64 = Math.floor((this.q.bitLength() - 1) / 64)+1;
26 this.h.push("typedef unsigned long long u64;");
27 this.h.push(`typedef u64 ${this.name}Element[${this.n64}];`);
28 this.h.push(`typedef u64 *P${this.name}Element;`);
29 this.h.push(`extern ${this.name}Element ${this.name}_q;`);
30 this.h.push(`#define ${this.name}_N64 ${this.n64}`);
31 this.c.push(`#include "${this.name.toLowerCase()}.h"`);
32 this._defineConstant(`${this.name}_q`, this.q);
33 this.c.push(""); this.h.push("");
34 }
35
36 _defineConstant(n, v) {
37 let S = `${this.name}Element ${n}={`;
38 const mask = bigInt("FFFFFFFFFFFFFFFF", 16);
39 for (let i=0; i<this.n64; i++) {
40 if (i>0) S = S+",";
41 let shex = v.shiftRight(i*64).and(mask).toString(16);
42 while (shex <16) shex = "0" + shex;
43 S = S + "0x" + shex + "ULL";
44 }
45 S += "};";
46 this.c.push(S);
47 }
48
49 _buildAdd() {
50 this.h.push(`void ${this.name}_add(P${this.name}Element r, P${this.name}Element a, P${this.name}Element b);`);
51 this.c.push(`void ${this.name}_add(P${this.name}Element r, P${this.name}Element a, P${this.name}Element b) {`);
52 this.c.push(" __asm__ __volatile__ (");
53 for (let i=0; i<this.n64; i++) {
54 this.c.push(` "movq ${i*8}(%2), %%rax;"`);
55 this.c.push(` "${i==0 ? "addq" : "adcq"} ${i*8}(%1), %%rax;"`);
56 this.c.push(` "movq %%rax, ${i*8}(%0);"`);
57 }
58 this.c.push(" \"jc SQ;\"");
59 for (let i=0; i<this.n64; i++) {
60 if (i>0) {
61 this.c.push(` "movq ${(this.n64 - i-1)*8}(%0), %%rax;"`);
62 }
63 this.c.push(` "cmp ${(this.n64 - i-1)*8}(%3), %%rax;"`);
64 this.c.push(" \"jg SQ;\"");
65 this.c.push(" \"jl DONE;\"");
66 }
67 this.c.push(" \"SQ:\"");
68 for (let i=0; i<this.n64; i++) {
69 this.c.push(` "movq ${i*8}(%3), %%rax;"`);
70 this.c.push(` "${i==0 ? "subq" : "sbbq"} %%rax, ${i*8}(%0);"`);
71 }
72 this.c.push(" \"DONE:\"");
73 this.c.push(` :: "r" (r), "r" (a), "r" (b), "r" (${this.name}_q) : "%rax", "memory");`);
74 this.c.push("}\n");
75 }
76
77 _buildMul() {
78
79 let r0, r1, r2;
80 function setR(step) {
81 if ((step % 3) == 0) {
82 r0 = "%%r8";
83 r1 = "%%r9";
84 r2 = "%%r10";
85 } else if ((step % 3) == 1) {
86 r0 = "%%r9";
87 r1 = "%%r10";
88 r2 = "%%r8";
89 } else {
90 r0 = "%%r10";
91 r1 = "%%r8";
92 r2 = "%%r9";
93 }
94 }
95 const base = bigInt.one.shiftLeft(64);
96 const np64 = base.minus(this.q.modInv(base));
97
98 this.h.push(`void ${this.name}_mul(P${this.name}Element r, P${this.name}Element a, P${this.name}Element b);`);
99 this.c.push(`void ${this.name}_mul(P${this.name}Element r, P${this.name}Element a, P${this.name}Element b) {`);
100 this.c.push(" __asm__ __volatile__ (");
101
102 this.c.push(` "subq $${this.n64*8}, %%rsp;"`);
103 this.c.push(` "movq $0x${np64.toString(16)}, %%r11;"`);
104 this.c.push(" \"movq $0x0, %%r8;\"");
105 this.c.push(" \"movq $0x0, %%r9;\"");
106 this.c.push(" \"movq $0x0, %%r10;\"");
107
108 for (let i=0; i<this.n64*2; i++) {
109 setR(i);
110
111 for (let o1=Math.max(0, i-this.n64+1); (o1<=i)&&(o1<this.n64); o1++) {
112 const o2= i-o1;
113 this.c.push(` "movq ${o1*8}(%1), %%rax;"`);
114 this.c.push(` "mulq ${o2*8}(%2);"`);
115 this.c.push(` "addq %%rax, ${r0};"`);
116 this.c.push(` "adcq %%rdx, ${r1};"`);
117 this.c.push(` "adcq $0x0, ${r2};"`);
118 }
119
120 for (let j=i-1; j>=0; j--) {
121 if (((i-j)<this.n64)&&(j<this.n64)) {
122 this.c.push(` "movq ${j*8}(%%rsp), %%rax;"`);
123 this.c.push(` "mulq ${(i-j)*8}(%3);"`);
124 this.c.push(` "addq %%rax, ${r0};"`);
125 this.c.push(` "adcq %%rdx, ${r1};"`);
126 this.c.push(` "adcq $0x0, ${r2};"`);
127 }
128 }
129
130 if (i<this.n64) {
131 this.c.push(` "movq ${r0}, %%rax;"`);
132 this.c.push(" \"mulq %%r11;\"");
133 this.c.push(` "movq %%rax, ${i*8}(%%rsp);"`);
134 this.c.push(" \"mulq (%3);\"");
135 this.c.push(` "addq %%rax, ${r0};"`);
136 this.c.push(` "adcq %%rdx, ${r1};"`);
137 this.c.push(` "adcq $0x0, ${r2};"`);
138 } else {
139 this.c.push(` "movq ${r0}, ${(i-this.n64)*8}(%0);"`);
140 this.c.push(` "movq $0, ${r0};"`);
141 }
142 }
143
144 this.c.push(` "cmp $0, ${r1};"`);
145 this.c.push(" \"jne SQ2;\"");
146 for (let i=0; i<this.n64; i++) {
147 this.c.push(` "movq ${(this.n64 - i-1)*8}(%0), %%rax;"`);
148 this.c.push(` "cmp ${(this.n64 - i-1)*8}(%3), %%rax;"`);
149 this.c.push(" \"jg SQ2;\"");
150 this.c.push(" \"jl DONE2;\"");
151 }
152 this.c.push(" \"SQ2:\"");
153 for (let i=0; i<this.n64; i++) {
154 this.c.push(` "movq ${i*8}(%3), %%rax;"`);
155 this.c.push(` "${i==0 ? "subq" : "sbbq"} %%rax, ${i*8}(%0);"`);
156 }
157 this.c.push(" \"DONE2:\"");
158 this.c.push(` "addq $${this.n64*8}, %%rsp;"`);
159
160 this.c.push(` :: "r" (r), "r" (a), "r" (b), "r" (${this.name}_q) : "%rax", "%rdx", "%r8", "%r9", "%r10", "%r11", "memory");`);
161 this.c.push("}\n");
162 }
163
164 _buildIDiv() {
165 this.h.push(`void ${this.name}_idiv(P${this.name}Element r, P${this.name}Element a, P${this.name}Element b);`);
166 this.c.push(`void ${this.name}_idiv(P${this.name}Element r, P${this.name}Element a, P${this.name}Element b) {`);
167 this.c.push(" __asm__ __volatile__ (");
168 this.c.push(" \"pxor %%xmm0, %%xmm0;\""); // Comparison Register
169 if (this.n64 == 1) {
170 this.c.push(` "mov %%rax, $${this.n64 - 8};"`);
171
172 } else {
173 this.c.push(` "mov %%rax, $${this.n64 -16};"`);
174 }
175
176 this.c.push(` :: "r" (r), "r" (a), "r" (b), "r" (${this.name}_q) : "%rax", "%rdx", "%r8", "%r9", "%r10", "%r11", "memory");`);
177 this.c.push("}\n");
178 }
179}
180
181var runningAsScript = !module.parent;
182
183if (runningAsScript) {
184 const fs = require("fs");
185 var argv = require("yargs")
186 .usage("Usage: $0 -q [primeNum] -n [name] -oc [out .c file] -oh [out .h file]")
187 .demandOption(["q","n"])
188 .alias("q", "prime")
189 .alias("n", "name")
190 .argv;
191
192 const q = bigInt(argv.q);
193
194 const cFileName = (argv.oc) ? argv.oc : argv.name.toLowerCase() + ".c";
195 const hFileName = (argv.oh) ? argv.oh : argv.name.toLowerCase() + ".h";
196
197 const builder = new ZqBuilder(q, argv.name);
198
199 const res = builder.build();
200
201 fs.writeFileSync(hFileName, res[0], "utf8");
202 fs.writeFileSync(cFileName, res[1], "utf8");
203} else {
204 module.exports = function(q, name) {
205 const builder = new ZqBuilder(q, name);
206 return builder.build();
207 };
208}
209