1
  2
  3        global <%=name%>_add
  4        global <%=name%>_mul
  5        global <%=name%>_q
  6        DEFAULT REL
  7
  8        section .text
  9
 10;;;;;;;;;;;;;;;;;;;;;;
 11; add
 12;;;;;;;;;;;;;;;;;;;;;;
 13<%=name%>_add:
 14        ; Add component by component with carry
 15<% for (let i=0; i<n64; i++) { %>
 16        mov rax, [rsi + <%=i*8%>]
 17        <%= i==0 ? "add" : "adc" %> rax, [rdx + <%=i*8%>]
 18        mov [rdi + <%=i*8%>], rax
 19<% } %>
 20        jc add_sq   ; if overflow, substract q
 21
 22        ; Compare with q
 23<% for (let i=0; i<n64; i++) { %>
 24<%    if (i>0) { %>
 25        mov rax, [rdi + <%= (n64-i-1)*8 %>]
 26<%    } %>
 27        cmp rax, [q + <%= (n64-i-1)*8 %>]
 28        jg add_sq
 29        jl add_done
 30<% } %>
 31        ; If equal substract q
 32add_sq:
 33<% for (let i=0; i<n64; i++) { %>
 34        mov rax, [q + <%=i*8%>]
 35        <%= i==0 ? "sub" : "sbb" %> [rdi + <%=i*8%>], rax
 36        mov [rdx + <%=i*8%>], rax
 37<% } %>
 38
 39add_done:
 40        ret
 41
 42
 43;;;;;;;;;;;;;;;;;;;;;;
 44; mul Montgomery
 45;;;;;;;;;;;;;;;;;;;;;;
 46mulM:
 47<%
 48let r0, r1, r2;
 49function setR(step) {
 50    if ((step % 3) == 0) {
 51        r0 = "r8";
 52        r1 = "r9";
 53        r2 = "r10";
 54    } else if ((step % 3) == 1) {
 55        r0 = "r9";
 56        r1 = "r10";
 57        r2 = "r8";
 58    } else {
 59        r0 = "r10";
 60        r1 = "r8";
 61        r2 = "r9";
 62    }
 63}
 64
 65const base = bigInt.one.shiftLeft(64);
 66const np64 = base.minus(q.modInv(base));
 67%>
 68        sub     rsp, <%= n64*8 %>  ; Reserve space for ms
 69        mov     rcx, rdx            ; rdx is needed for multiplications so keep it in cx
 70        mov     r11, 0x<%= np64.toString(16) %> ; np
 71        xor     r8,r8
 72        xor     r9,r9
 73        xor     r10,r10
 74<%
 75// Main loop
 76for (let i=0; i<n64*2; i++) {
 77    setR(i);
 78%>
 79<%
 80    // Same Digit
 81    for (let o1=Math.max(0, i-n64+1); (o1<=i)&&(o1<n64); o1++) {
 82        const o2= i-o1;
 83%>
 84        mov     rax, [rsi + <%= 8*o1 %>]
 85        mul     qword [rcx + <%= 8*o2 %>]
 86        add     <%= r0 %>, rax
 87        adc     <%= r1 %>, rdx
 88        adc     <%= r2 %>, 0x0
 89<%
 90    } // Same digit
 91%>
 92
 93
 94<%
 95    for (let j=i-1; j>=0; j--) { // All ms
 96        if (((i-j)<n64)&&(j<n64)) {
 97%>
 98        mov     rax, [rsp + <%= j*8 %>]
 99        mul     qword [q + <%= (i-j)*8 %>]
100        add     <%= r0 %>, rax
101        adc     <%= r1 %>, rdx
102        adc     <%= r2 %>, 0x0
103<%
104        }
105    } // ms
106%>
107
108<%
109    if (i<n64) {
110%>
111        mov     rax, <%= r0 %>
112        mul     r11
113        mov     [rsp + <%= i*8 %>], rax
114        mul     qword [q]
115        add     <%= r0 %>, rax
116        adc     <%= r1 %>, rdx
117        adc     <%= r2 %>, 0x0
118<%
119    } else {
120%>
121        mov     [rdi + <%= (i-n64)*8 %> ], <%= r0 %>
122        xor     <%= r0 %>,<%= r0 %>
123<%
124    }
125%>
126
127<%
128}   // Main Loop
129%>
130        cmp     <%= r1 %>, 0x0
131        jne     mulM_sq
132        ; Compare with q
133<%
134for (let i=0; i<n64; i++) {
135%>
136        mov rax, [rdi + <%= (n64-i-1)*8 %>]
137        cmp rax, [q + <%= (n64-i-1)*8 %>]
138        jg mulM_sq
139        jl mulM_done
140<%
141}
142%>
143        ; If equal substract q
144
145mulM_sq:
146<%
147for (let i=0; i<n64; i++) {
148%>
149        mov rax, [q + <%= i*8 %>]
150        <%= i==0 ? "sub" : "sbb" %> [rdi + <%= i*8 %>], rax
151        mov [rdx + <%= i*8 %>], rax
152<%
153}
154%>
155
156mulM_done:
157        add rsp, <%= n64*8 %>   ; recover rsp
158        ret
159
160;;;;;;;;;;;;;;;;;;;;;;
161; mul MontgomeryShort
162;;;;;;;;;;;;;;;;;;;;;;
163mulSM:
164
165;;;;;;;;;;;;;;;;;;;;;;
166; mul
167;;;;;;;;;;;;;;;;;;;;;;
168<%=name%>_mul:
169        mov    rax, [rsi]
170        bt     rax, 63
171        jc     l1
172        mov    rcx, [rdx]
173        bt     rcx, 63
174        jc     s1l2
175s1s2:                       ; short first and second
176        mul    ecx
177        jc     rs2l         ; If if doesn't feed in 32 bits convert the result to long
178
179        ; The shorts multiplication is done. copy the val to destination and return
180        mov    [rdi], rax
181        ret
182
183rs2l:                       ; The result in the multiplication doen't feed
184                            ; we have the result in edx:eax we need to convert it to long
185        shl    rdx, 32
186        mov    edx, eax     ; pack edx:eax to rdx
187
188        xor    rax, rax     ; Set the format to long
189        bts    rax, 63
190        mov    [rdi], rax       ; move the first digit
191
192        cmp    rdx, 0       ; check if redx is negative.
193        jl     rs2ln
194
195        ; edx is positive.
196        mov    [rdi + 8], rdx   ; Set the firs digit
197
198        xor    rax, rax     ; Set the remaining digits to 0
199<% for (let i=1; i<n64; i++) { %>
200        mov [rdi + <%= (i+1)*8 %>], rax
201<% } %>
202        ret
203
204        ; edx is negative.
205rs2ln:
206
207        add    rdx, [q]         ; Set the firs digit
208        mov    [rdi + 8], rdx   ;
209
210        mov    rdx, -1          ; all ones
211<% for (let i=1; i<n64; i++) { %>
212        mov    rax, rdx                       ; Add to q
213        adc    rax, [q + <%= i*8 %> ]
214        mov    [rdi + <%= (i+1)*8 %>], rax
215<% } %>
216        ret
217
218l1:
219        mov    rcx, [rdx]
220        bt     rcx, 63
221        jc     ll
222
223l1s2:
224        xor rdx, rdx
225        mov edx, ecx
226        bt  rax, 62
227        jc  lsM
228        jmp lsN
229
230s1l2:
231        mov rsi, rdx
232        xor rdx, rdx
233        mov edx, eax
234        bt  rcx, 62
235        jc  lsM
236        jmp lsN
237
238
239lsN:
240        mov byte [rdi + 3], 0xC0    ; set the result to montgomery
241        add rsi, 8
242        add rdi, 8
243        call mulSM
244        mov rdx, R3
245        call mulM
246        ret
247
248lsM:
249        mov byte [rdi + 3], 0x80    ; set the result to long normal
250        add rsi, 8
251        add rdi, 8
252        call mulSM
253        ret
254
255
256ll:
257
258        bt rax, 62
259        jc lml
260        bt rcx, 62
261        jc lnlm
262
263lnln:
264        mov byte [rdi + 3], 0xC0    ; set the result to long montgomery
265        add rsi, 8
266        add rdi, 8
267        add rdx, 8
268        call mulM
269        mov rdi, rsi
270        mov rdx, R3
271        call mulM
272        ret
273
274lml:
275        bt rcx, 62
276        jc lmlm
277
278lnlm:
279        mov byte [rdi + 3], 0x80    ; set the result to long normal
280        add rsi, 8
281        add rdi, 8
282        add rdx, 8
283        call mulM
284        ret
285
286lmlm:
287        mov byte [rdi + 3], 0xC0    ; set the result to long montgomery
288        add rsi, 8
289        add rdi, 8
290        add rdx, 8
291        call mulM
292        ret
293
294
295        section .data
296<%=name%>_q:
297        dd      0
298        dd      0x80000000
299q       dq      <%= constantElement(q) %>
300R3      dq      <%= constantElement(bigInt.one.shiftLeft(n64*64*3).mod(q)) %>
301
302