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; rawMontgomeryMul1
149;;;;;;;;;;;;;;;;;;;;;;
150; Multiply two elements in montgomery form
151; Params:
152; rsi <= Pointer to the long data of element 1
153; rdx <= second operand
154; rdi <= Pointer to the long data of result
155; Modified registers:
156; r8, r9, 10, r11, rax, rcx
157;;;;;;;;;;;;;;;;;;;;;;
158<%
159montgomeryTemplate("rawMontgomeryMul1", function(i, r0, r1, r2) {
160 // Same Digit
161 if (i<n64) {
162%>
163 mov rax, [rsi + <%= 8*i %>]
164 mul rcx
165 add <%= r0 %>, rax
166 adc <%= r1 %>, rdx
167 adc <%= r2 %>, 0x0
168<%
169 } // Same digit
170})
171%>
172
173
174;;;;;;;;;;;;;;;;;;;;;;
175; rawFromMontgomery
176;;;;;;;;;;;;;;;;;;;;;;
177; Multiply two elements in montgomery form
178; Params:
179; rsi <= Pointer to the long data of element 1
180; rdi <= Pointer to the long data of result
181; Modified registers:
182; r8, r9, 10, r11, rax, rcx
183;;;;;;;;;;;;;;;;;;;;;;
184<%
185montgomeryTemplate("rawFromMontgomery", function(i, r0, r1, r2) {
186 // Same Digit
187 if (i<n64) {
188%>
189 add <%= r0 %>, [rdi + <%= 8*i %>]
190 adc <%= r1 %>, 0x0
191 adc <%= r2 %>, 0x0
192<%
193 } // Same digit
194})
195%>
196
197;;;;;;;;;;;;;;;;;;;;;;
198; toMontgomery
199;;;;;;;;;;;;;;;;;;;;;;
200; Convert a number to Montgomery
201; rdi <= Pointer element to convert
202; Modified registers:
203; r8, r9, 10, r11, rax, rcx
204;;;;;;;;;;;;;;;;;;;;
205<%=name%>_toMontgomery:
206 mov rax, [rdi]
207 bts rax, 62 ; check if montgomery
208 jc toMontgomery_doNothing
209 bts rax, 63
210 jc toMontgomeryLong
211
212toMontgomeryShort:
213 mov [rdi], rax
214 add rdi, 8
215 push rsi
216 lea rsi, [R2]
217 movsx rdx, eax
218 cmp rdx, 0
219 js negMontgomeryShort
220posMontgomeryShort:
221 call rawMontgomeryMul1
222 pop rsi
223 sub rdi, 8
224 ret
225
226negMontgomeryShort:
227 neg rdx ; Do the multiplication positive and then negate the result.
228 call rawMontgomeryMul1
229 mov rsi, rdi
230 call rawNegL
231 pop rsi
232 sub rdi, 8
233 ret
234
235
236toMontgomeryLong:
237 mov [rdi], rax
238 add rdi, 8
239 push rsi
240 mov rdx, rdi
241 lea rsi, [R2]
242 call rawMontgomeryMul
243 pop rsi
244 sub rdi, 8
245
246toMontgomery_doNothing:
247 ret
248
249;;;;;;;;;;;;;;;;;;;;;;
250; toNormal
251;;;;;;;;;;;;;;;;;;;;;;
252; Convert a number from Montgomery
253; rdi <= Pointer element to convert
254; Modified registers:
255; r8, r9, 10, r11, rax, rcx
256;;;;;;;;;;;;;;;;;;;;
257<%=name%>_toNormal:
258 mov rax, [rdi]
259 btc rax, 62 ; check if montgomery
260 jnc fromMontgomery_doNothing
261 bt rax, 63 ; if short, it means it's converted
262 jnc fromMontgomery_doNothing
263
264fromMontgomeryLong:
265 mov [rdi], rax
266 add rdi, 8
267 call rawFromMontgomery
268 sub rdi, 8
269
270fromMontgomery_doNothing:
271 ret
272
273