circom/ports/c/buildasm/montgomery.asm.ejs
ports/c/buildasm/montgomery.asm.ejsRaw
1
2
3
4<%
5//////////////////////
6// montgomeryTemplate
7//////////////////////
8// This function creates functions with the montgomery transformation
9// applied
10// the round hook allows to add diferent code in the iteration
11//
12// All the montgomery functions modifies:
13// r8, r9, 10, r11, rax, rcx
14//////////////////////
15function montgomeryTemplate(fnName, round) {
16 let r0, r1, r2;
17 function setR(step) {
18 if ((step % 3) == 0) {
19 r0 = "r8";
20 r1 = "r9";
21 r2 = "r10";
22 } else if ((step % 3) == 1) {
23 r0 = "r9";
24 r1 = "r10";
25 r2 = "r8";
26 } else {
27 r0 = "r10";
28 r1 = "r8";
29 r2 = "r9";
30 }
31 }
32
33 const base = bigInt.one.shiftLeft(64);
34 const np64 = base.minus(q.modInv(base));
35%>
36<%=fnName%>:
37 sub rsp, <%= n64*8 %> ; Reserve space for ms
38 mov rcx, rdx ; rdx is needed for multiplications so keep it in cx
39 mov r11, 0x<%= np64.toString(16) %> ; np
40 xor r8,r8
41 xor r9,r9
42 xor r10,r10
43<%
44 // Main loop
45 for (let i=0; i<n64*2; i++) {
46 setR(i);
47 round(i, r0, r1, r2);
48%>
49
50<%
51 for (let j=i-1; j>=0; j--) { // All ms
52 if (((i-j)<n64)&&(j<n64)) {
53%>
54 mov rax, [rsp + <%= j*8 %>]
55 mul qword [q + <%= (i-j)*8 %>]
56 add <%= r0 %>, rax
57 adc <%= r1 %>, rdx
58 adc <%= r2 %>, 0x0
59<%
60 }
61 } // ms
62%>
63
64<%
65 if (i<n64) {
66%>
67 mov rax, <%= r0 %>
68 mul r11
69 mov [rsp + <%= i*8 %>], rax
70 mul qword [q]
71 add <%= r0 %>, rax
72 adc <%= r1 %>, rdx
73 adc <%= r2 %>, 0x0
74<%
75 } else {
76%>
77 mov [rdi + <%= (i-n64)*8 %> ], <%= r0 %>
78 xor <%= r0 %>,<%= r0 %>
79<%
80 }
81%>
82
83<%
84 } // Main Loop
85%>
86 test <%= r1 %>, <%= r1 %>
87 jnz <%=fnName%>_mulM_sq
88 ; Compare with q
89<%
90 for (let i=0; i<n64; i++) {
91%>
92 mov rax, [rdi + <%= (n64-i-1)*8 %>]
93 cmp rax, [q + <%= (n64-i-1)*8 %>]
94 jc <%=fnName%>_mulM_done ; q is bigget so done.
95 jnz <%=fnName%>_mulM_sq ; q is lower
96<%
97 }
98%>
99 ; If equal substract q
100
101<%=fnName%>_mulM_sq:
102<%
103 for (let i=0; i<n64; i++) {
104%>
105 mov rax, [q + <%= i*8 %>]
106 <%= i==0 ? "sub" : "sbb" %> [rdi + <%= i*8 %>], rax
107<%
108 }
109%>
110
111<%=fnName%>_mulM_done:
112 mov rdx, rcx ; recover rdx to its original place.
113 add rsp, <%= n64*8 %> ; recover rsp
114 ret
115
116<%
117} // Template
118%>
119
120;;;;;;;;;;;;;;;;;;;;;;
121; rawMontgomeryMul
122;;;;;;;;;;;;;;;;;;;;;;
123; Multiply two elements in montgomery form
124; Params:
125; rsi <= Pointer to the long data of element 1
126; rdx <= Pointer to the long data of element 2
127; rdi <= Pointer to the long data of result
128; Modified registers:
129; r8, r9, 10, r11, rax, rcx
130;;;;;;;;;;;;;;;;;;;;;;
131<%
132montgomeryTemplate("rawMontgomeryMul", function(i, r0, r1, r2) {
133 // Same Digit
134 for (let o1=Math.max(0, i-n64+1); (o1<=i)&&(o1<n64); o1++) {
135 const o2= i-o1;
136%>
137 mov rax, [rsi + <%= 8*o1 %>]
138 mul qword [rcx + <%= 8*o2 %>]
139 add <%= r0 %>, rax
140 adc <%= r1 %>, rdx
141 adc <%= r2 %>, 0x0
142<%
143 } // Same digit
144})
145%>
146
147;;;;;;;;;;;;;;;;;;;;;;
148; rawMontgomerySquare
149;;;;;;;;;;;;;;;;;;;;;;
150; Square an element
151; Params:
152; rsi <= Pointer to the long data of element 1
153; rdi <= Pointer to the long data of result
154; Modified registers:
155; r8, r9, 10, r11, rax, rcx
156;;;;;;;;;;;;;;;;;;;;;;
157<%
158montgomeryTemplate("rawMontgomerySquare", function(i, r0, r1, r2) {
159 // Same Digit
160 for (let o1=Math.max(0, i-n64+1); (o1<((i+1)>>1) )&&(o1<n64); o1++) {
161 const o2= i-o1;
162%>
163 mov rax, [rsi + <%= 8*o1 %>]
164 mul qword [rsi + <%= 8*o2 %>]
165 add <%= r0 %>, rax
166 adc <%= r1 %>, rdx
167 adc <%= r2 %>, 0x0
168 add <%= r0 %>, rax
169 adc <%= r1 %>, rdx
170 adc <%= r2 %>, 0x0
171<%
172 } // Same digit
173%>
174
175<% if (i%2 == 0) { %>
176 mov rax, [rsi + <%= 8*(i/2) %>]
177 mul rax
178 add <%= r0 %>, rax
179 adc <%= r1 %>, rdx
180 adc <%= r2 %>, 0x0
181<% } %>
182
183<%
184})
185%>
186
187
188;;;;;;;;;;;;;;;;;;;;;;
189; rawMontgomeryMul1
190;;;;;;;;;;;;;;;;;;;;;;
191; Multiply two elements in montgomery form
192; Params:
193; rsi <= Pointer to the long data of element 1
194; rdx <= second operand
195; rdi <= Pointer to the long data of result
196; Modified registers:
197; r8, r9, 10, r11, rax, rcx
198;;;;;;;;;;;;;;;;;;;;;;
199<%
200montgomeryTemplate("rawMontgomeryMul1", function(i, r0, r1, r2) {
201 // Same Digit
202 if (i<n64) {
203%>
204 mov rax, [rsi + <%= 8*i %>]
205 mul rcx
206 add <%= r0 %>, rax
207 adc <%= r1 %>, rdx
208 adc <%= r2 %>, 0x0
209<%
210 } // Same digit
211})
212%>
213
214
215;;;;;;;;;;;;;;;;;;;;;;
216; rawFromMontgomery
217;;;;;;;;;;;;;;;;;;;;;;
218; Multiply two elements in montgomery form
219; Params:
220; rsi <= Pointer to the long data of element 1
221; rdi <= Pointer to the long data of result
222; Modified registers:
223; r8, r9, 10, r11, rax, rcx
224;;;;;;;;;;;;;;;;;;;;;;
225<%
226montgomeryTemplate("rawFromMontgomery", function(i, r0, r1, r2) {
227 // Same Digit
228 if (i<n64) {
229%>
230 add <%= r0 %>, [rdi + <%= 8*i %>]
231 adc <%= r1 %>, 0x0
232 adc <%= r2 %>, 0x0
233<%
234 } // Same digit
235})
236%>
237
238;;;;;;;;;;;;;;;;;;;;;;
239; toMontgomery
240;;;;;;;;;;;;;;;;;;;;;;
241; Convert a number to Montgomery
242; rdi <= Pointer element to convert
243; Modified registers:
244; r8, r9, 10, r11, rax, rcx
245;;;;;;;;;;;;;;;;;;;;
246<%=name%>_toMontgomery:
247 mov rax, [rdi]
248 bt rax, 62 ; check if montgomery
249 jc toMontgomery_doNothing
250 bt rax, 63
251 jc toMontgomeryLong
252
253toMontgomeryShort:
254 add rdi, 8
255 push rsi
256 push rdx
257 lea rsi, [R2]
258 movsx rdx, eax
259 cmp rdx, 0
260 js negMontgomeryShort
261posMontgomeryShort:
262 call rawMontgomeryMul1
263 pop rdx
264 pop rsi
265 sub rdi, 8
266 <%= global.setTypeDest("0x40"); %>
267 ret
268
269negMontgomeryShort:
270 neg rdx ; Do the multiplication positive and then negate the result.
271 call rawMontgomeryMul1
272 mov rsi, rdi
273 call rawNegL
274 pop rdx
275 pop rsi
276 sub rdi, 8
277 <%= global.setTypeDest("0x40"); %>
278 ret
279
280
281toMontgomeryLong:
282 mov [rdi], rax
283 add rdi, 8
284 push rsi
285 mov rdx, rdi
286 lea rsi, [R2]
287 call rawMontgomeryMul
288 pop rsi
289 sub rdi, 8
290 <%= global.setTypeDest("0xC0"); %>
291
292
293toMontgomery_doNothing:
294 ret
295
296;;;;;;;;;;;;;;;;;;;;;;
297; toNormal
298;;;;;;;;;;;;;;;;;;;;;;
299; Convert a number from Montgomery
300; rdi <= Pointer element to convert
301; Modified registers:
302; r8, r9, 10, r11, rax, rcx
303;;;;;;;;;;;;;;;;;;;;
304<%=name%>_toNormal:
305 mov rax, [rdi]
306 bt rax, 62 ; check if montgomery
307 jnc toNormal_doNothing
308 bt rax, 63 ; if short, it means it's converted
309 jnc toNormal_doNothing
310
311toNormalLong:
312 add rdi, 8
313 call rawFromMontgomery
314 sub rdi, 8
315 <%= global.setTypeDest("0x80"); %>
316
317toNormal_doNothing:
318 ret
319
320;;;;;;;;;;;;;;;;;;;;;;
321; toLongNormal
322;;;;;;;;;;;;;;;;;;;;;;
323; Convert a number to long normal
324; rdi <= Pointer element to convert
325; Modified registers:
326; r8, r9, 10, r11, rax, rcx
327;;;;;;;;;;;;;;;;;;;;
328<%=name%>_toLongNormal:
329 mov rax, [rdi]
330 bt rax, 62 ; check if montgomery
331 jc toLongNormal_fromMontgomery
332 bt rax, 63 ; check if long
333 jnc toLongNormal_fromShort
334 ret ; It is already long
335
336toLongNormal_fromMontgomery:
337 add rdi, 8
338 call rawFromMontgomery
339 sub rdi, 8
340 <%= global.setTypeDest("0x80"); %>
341 ret
342
343toLongNormal_fromShort:
344 mov r8, rsi ; save rsi
345 movsx rsi, eax
346 call rawCopyS2L
347 mov rsi, r8 ; recover rsi
348 <%= global.setTypeDest("0x80"); %>
349 ret
350