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