circom/c/buildasm/montgomery.asm.ejs
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 bts rax, 62 ; check if montgomery
249 jc toMontgomery_doNothing
250 bts rax, 63
251 jc toMontgomeryLong
252
253toMontgomeryShort:
254 mov [rdi], rax
255 add rdi, 8
256 push rsi
257 lea rsi, [R2]
258 movsx rdx, eax
259 cmp rdx, 0
260 js negMontgomeryShort
261posMontgomeryShort:
262 call rawMontgomeryMul1
263 pop rsi
264 sub rdi, 8
265 ret
266
267negMontgomeryShort:
268 neg rdx ; Do the multiplication positive and then negate the result.
269 call rawMontgomeryMul1
270 mov rsi, rdi
271 call rawNegL
272 pop rsi
273 sub rdi, 8
274 ret
275
276
277toMontgomeryLong:
278 mov [rdi], rax
279 add rdi, 8
280 push rsi
281 mov rdx, rdi
282 lea rsi, [R2]
283 call rawMontgomeryMul
284 pop rsi
285 sub rdi, 8
286
287toMontgomery_doNothing:
288 ret
289
290;;;;;;;;;;;;;;;;;;;;;;
291; toNormal
292;;;;;;;;;;;;;;;;;;;;;;
293; Convert a number from Montgomery
294; rdi <= Pointer element to convert
295; Modified registers:
296; r8, r9, 10, r11, rax, rcx
297;;;;;;;;;;;;;;;;;;;;
298<%=name%>_toNormal:
299 mov rax, [rdi]
300 btc rax, 62 ; check if montgomery
301 jnc toNormal_doNothing
302 bt rax, 63 ; if short, it means it's converted
303 jnc toNormal_doNothing
304
305toNormalLong:
306 mov [rdi], rax
307 add rdi, 8
308 call rawFromMontgomery
309 sub rdi, 8
310
311toNormal_doNothing:
312 ret
313
314;;;;;;;;;;;;;;;;;;;;;;
315; toLongNormal
316;;;;;;;;;;;;;;;;;;;;;;
317; Convert a number to long normal
318; rdi <= Pointer element to convert
319; Modified registers:
320; r8, r9, 10, r11, rax, rcx
321;;;;;;;;;;;;;;;;;;;;
322<%=name%>_toLongNormal:
323 mov rax, [rdi]
324 bt rax, 62 ; check if montgomery
325 jc toLongNormal_fromMontgomery
326 bt rax, 63 ; check if long
327 jnc toLongNormal_fromShort
328 ret ; It is already long
329
330toLongNormal_fromMontgomery:
331 add rdi, 8
332 call rawFromMontgomery
333 sub rdi, 8
334 ret
335
336toLongNormal_fromShort:
337 mov r8, rsi ; save rsi
338 movsx rsi, eax
339 call rawCopyS2L
340 mov rsi, r8 ; recover rsi
341 ret
342