Update copyright year
[openssl.git] / crypto / bn / asm / x86_64-mont.pl
1 #! /usr/bin/env perl
2 # Copyright 2005-2018 The OpenSSL Project Authors. All Rights Reserved.
3 #
4 # Licensed under the OpenSSL license (the "License").  You may not use
5 # this file except in compliance with the License.  You can obtain a copy
6 # in the file LICENSE in the source distribution or at
7 # https://www.openssl.org/source/license.html
8
9
10 # ====================================================================
11 # Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
12 # project. The module is, however, dual licensed under OpenSSL and
13 # CRYPTOGAMS licenses depending on where you obtain it. For further
14 # details see http://www.openssl.org/~appro/cryptogams/.
15 # ====================================================================
16
17 # October 2005.
18 #
19 # Montgomery multiplication routine for x86_64. While it gives modest
20 # 9% improvement of rsa4096 sign on Opteron, rsa512 sign runs more
21 # than twice, >2x, as fast. Most common rsa1024 sign is improved by
22 # respectful 50%. It remains to be seen if loop unrolling and
23 # dedicated squaring routine can provide further improvement...
24
25 # July 2011.
26 #
27 # Add dedicated squaring procedure. Performance improvement varies
28 # from platform to platform, but in average it's ~5%/15%/25%/33%
29 # for 512-/1024-/2048-/4096-bit RSA *sign* benchmarks respectively.
30
31 # August 2011.
32 #
33 # Unroll and modulo-schedule inner loops in such manner that they
34 # are "fallen through" for input lengths of 8, which is critical for
35 # 1024-bit RSA *sign*. Average performance improvement in comparison
36 # to *initial* version of this module from 2005 is ~0%/30%/40%/45%
37 # for 512-/1024-/2048-/4096-bit RSA *sign* benchmarks respectively.
38
39 # June 2013.
40 #
41 # Optimize reduction in squaring procedure and improve 1024+-bit RSA
42 # sign performance by 10-16% on Intel Sandy Bridge and later
43 # (virtually same on non-Intel processors).
44
45 # August 2013.
46 #
47 # Add MULX/ADOX/ADCX code path.
48
49 $flavour = shift;
50 $output  = shift;
51 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
52
53 $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
54
55 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
56 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
57 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
58 die "can't locate x86_64-xlate.pl";
59
60 open OUT,"| \"$^X\" \"$xlate\" $flavour \"$output\"";
61 *STDOUT=*OUT;
62
63 if (`$ENV{CC} -Wa,-v -c -o /dev/null -x assembler /dev/null 2>&1`
64                 =~ /GNU assembler version ([2-9]\.[0-9]+)/) {
65         $addx = ($1>=2.23);
66 }
67
68 if (!$addx && $win64 && ($flavour =~ /nasm/ || $ENV{ASM} =~ /nasm/) &&
69             `nasm -v 2>&1` =~ /NASM version ([2-9]\.[0-9]+)/) {
70         $addx = ($1>=2.10);
71 }
72
73 if (!$addx && $win64 && ($flavour =~ /masm/ || $ENV{ASM} =~ /ml64/) &&
74             `ml64 2>&1` =~ /Version ([0-9]+)\./) {
75         $addx = ($1>=12);
76 }
77
78 if (!$addx && `$ENV{CC} -v 2>&1` =~ /((?:^clang|LLVM) version|.*based on LLVM) ([3-9])\.([0-9]+)/) {
79         my $ver = $2 + $3/100.0;        # 3.1->3.01, 3.10->3.10
80         $addx = ($ver>=3.03);
81 }
82
83 # int bn_mul_mont(
84 $rp="%rdi";     # BN_ULONG *rp,
85 $ap="%rsi";     # const BN_ULONG *ap,
86 $bp="%rdx";     # const BN_ULONG *bp,
87 $np="%rcx";     # const BN_ULONG *np,
88 $n0="%r8";      # const BN_ULONG *n0,
89 $num="%r9";     # int num);
90 $lo0="%r10";
91 $hi0="%r11";
92 $hi1="%r13";
93 $i="%r14";
94 $j="%r15";
95 $m0="%rbx";
96 $m1="%rbp";
97
98 $code=<<___;
99 .text
100
101 .extern OPENSSL_ia32cap_P
102
103 .globl  bn_mul_mont
104 .type   bn_mul_mont,\@function,6
105 .align  16
106 bn_mul_mont:
107 .cfi_startproc
108         mov     ${num}d,${num}d
109         mov     %rsp,%rax
110 .cfi_def_cfa_register   %rax
111         test    \$3,${num}d
112         jnz     .Lmul_enter
113         cmp     \$8,${num}d
114         jb      .Lmul_enter
115 ___
116 $code.=<<___ if ($addx);
117         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
118 ___
119 $code.=<<___;
120         cmp     $ap,$bp
121         jne     .Lmul4x_enter
122         test    \$7,${num}d
123         jz      .Lsqr8x_enter
124         jmp     .Lmul4x_enter
125
126 .align  16
127 .Lmul_enter:
128         push    %rbx
129 .cfi_push       %rbx
130         push    %rbp
131 .cfi_push       %rbp
132         push    %r12
133 .cfi_push       %r12
134         push    %r13
135 .cfi_push       %r13
136         push    %r14
137 .cfi_push       %r14
138         push    %r15
139 .cfi_push       %r15
140
141         neg     $num
142         mov     %rsp,%r11
143         lea     -16(%rsp,$num,8),%r10   # future alloca(8*(num+2))
144         neg     $num                    # restore $num
145         and     \$-1024,%r10            # minimize TLB usage
146
147         # An OS-agnostic version of __chkstk.
148         #
149         # Some OSes (Windows) insist on stack being "wired" to
150         # physical memory in strictly sequential manner, i.e. if stack
151         # allocation spans two pages, then reference to farmost one can
152         # be punishable by SEGV. But page walking can do good even on
153         # other OSes, because it guarantees that villain thread hits
154         # the guard page before it can make damage to innocent one...
155         sub     %r10,%r11
156         and     \$-4096,%r11
157         lea     (%r10,%r11),%rsp
158         mov     (%rsp),%r11
159         cmp     %r10,%rsp
160         ja      .Lmul_page_walk
161         jmp     .Lmul_page_walk_done
162
163 .align  16
164 .Lmul_page_walk:
165         lea     -4096(%rsp),%rsp
166         mov     (%rsp),%r11
167         cmp     %r10,%rsp
168         ja      .Lmul_page_walk
169 .Lmul_page_walk_done:
170
171         mov     %rax,8(%rsp,$num,8)     # tp[num+1]=%rsp
172 .cfi_cfa_expression     %rsp+8,$num,8,mul,plus,deref,+8
173 .Lmul_body:
174         mov     $bp,%r12                # reassign $bp
175 ___
176                 $bp="%r12";
177 $code.=<<___;
178         mov     ($n0),$n0               # pull n0[0] value
179         mov     ($bp),$m0               # m0=bp[0]
180         mov     ($ap),%rax
181
182         xor     $i,$i                   # i=0
183         xor     $j,$j                   # j=0
184
185         mov     $n0,$m1
186         mulq    $m0                     # ap[0]*bp[0]
187         mov     %rax,$lo0
188         mov     ($np),%rax
189
190         imulq   $lo0,$m1                # "tp[0]"*n0
191         mov     %rdx,$hi0
192
193         mulq    $m1                     # np[0]*m1
194         add     %rax,$lo0               # discarded
195         mov     8($ap),%rax
196         adc     \$0,%rdx
197         mov     %rdx,$hi1
198
199         lea     1($j),$j                # j++
200         jmp     .L1st_enter
201
202 .align  16
203 .L1st:
204         add     %rax,$hi1
205         mov     ($ap,$j,8),%rax
206         adc     \$0,%rdx
207         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
208         mov     $lo0,$hi0
209         adc     \$0,%rdx
210         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
211         mov     %rdx,$hi1
212
213 .L1st_enter:
214         mulq    $m0                     # ap[j]*bp[0]
215         add     %rax,$hi0
216         mov     ($np,$j,8),%rax
217         adc     \$0,%rdx
218         lea     1($j),$j                # j++
219         mov     %rdx,$lo0
220
221         mulq    $m1                     # np[j]*m1
222         cmp     $num,$j
223         jne     .L1st
224
225         add     %rax,$hi1
226         mov     ($ap),%rax              # ap[0]
227         adc     \$0,%rdx
228         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
229         adc     \$0,%rdx
230         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
231         mov     %rdx,$hi1
232         mov     $lo0,$hi0
233
234         xor     %rdx,%rdx
235         add     $hi0,$hi1
236         adc     \$0,%rdx
237         mov     $hi1,-8(%rsp,$num,8)
238         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
239
240         lea     1($i),$i                # i++
241         jmp     .Louter
242 .align  16
243 .Louter:
244         mov     ($bp,$i,8),$m0          # m0=bp[i]
245         xor     $j,$j                   # j=0
246         mov     $n0,$m1
247         mov     (%rsp),$lo0
248         mulq    $m0                     # ap[0]*bp[i]
249         add     %rax,$lo0               # ap[0]*bp[i]+tp[0]
250         mov     ($np),%rax
251         adc     \$0,%rdx
252
253         imulq   $lo0,$m1                # tp[0]*n0
254         mov     %rdx,$hi0
255
256         mulq    $m1                     # np[0]*m1
257         add     %rax,$lo0               # discarded
258         mov     8($ap),%rax
259         adc     \$0,%rdx
260         mov     8(%rsp),$lo0            # tp[1]
261         mov     %rdx,$hi1
262
263         lea     1($j),$j                # j++
264         jmp     .Linner_enter
265
266 .align  16
267 .Linner:
268         add     %rax,$hi1
269         mov     ($ap,$j,8),%rax
270         adc     \$0,%rdx
271         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
272         mov     (%rsp,$j,8),$lo0
273         adc     \$0,%rdx
274         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
275         mov     %rdx,$hi1
276
277 .Linner_enter:
278         mulq    $m0                     # ap[j]*bp[i]
279         add     %rax,$hi0
280         mov     ($np,$j,8),%rax
281         adc     \$0,%rdx
282         add     $hi0,$lo0               # ap[j]*bp[i]+tp[j]
283         mov     %rdx,$hi0
284         adc     \$0,$hi0
285         lea     1($j),$j                # j++
286
287         mulq    $m1                     # np[j]*m1
288         cmp     $num,$j
289         jne     .Linner
290
291         add     %rax,$hi1
292         mov     ($ap),%rax              # ap[0]
293         adc     \$0,%rdx
294         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
295         mov     (%rsp,$j,8),$lo0
296         adc     \$0,%rdx
297         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
298         mov     %rdx,$hi1
299
300         xor     %rdx,%rdx
301         add     $hi0,$hi1
302         adc     \$0,%rdx
303         add     $lo0,$hi1               # pull upmost overflow bit
304         adc     \$0,%rdx
305         mov     $hi1,-8(%rsp,$num,8)
306         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
307
308         lea     1($i),$i                # i++
309         cmp     $num,$i
310         jb      .Louter
311
312         xor     $i,$i                   # i=0 and clear CF!
313         mov     (%rsp),%rax             # tp[0]
314         mov     $num,$j                 # j=num
315
316 .align  16
317 .Lsub:  sbb     ($np,$i,8),%rax
318         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[i]
319         mov     8(%rsp,$i,8),%rax       # tp[i+1]
320         lea     1($i),$i                # i++
321         dec     $j                      # doesn't affect CF!
322         jnz     .Lsub
323
324         sbb     \$0,%rax                # handle upmost overflow bit
325         mov     \$-1,%rbx
326         xor     %rax,%rbx               # not %rax
327         xor     $i,$i
328         mov     $num,$j                 # j=num
329
330 .Lcopy:                                 # conditional copy
331         mov     ($rp,$i,8),%rcx
332         mov     (%rsp,$i,8),%rdx
333         and     %rbx,%rcx
334         and     %rax,%rdx
335         mov     $num,(%rsp,$i,8)        # zap temporary vector
336         or      %rcx,%rdx
337         mov     %rdx,($rp,$i,8)         # rp[i]=tp[i]
338         lea     1($i),$i
339         sub     \$1,$j
340         jnz     .Lcopy
341
342         mov     8(%rsp,$num,8),%rsi     # restore %rsp
343 .cfi_def_cfa    %rsi,8
344         mov     \$1,%rax
345         mov     -48(%rsi),%r15
346 .cfi_restore    %r15
347         mov     -40(%rsi),%r14
348 .cfi_restore    %r14
349         mov     -32(%rsi),%r13
350 .cfi_restore    %r13
351         mov     -24(%rsi),%r12
352 .cfi_restore    %r12
353         mov     -16(%rsi),%rbp
354 .cfi_restore    %rbp
355         mov     -8(%rsi),%rbx
356 .cfi_restore    %rbx
357         lea     (%rsi),%rsp
358 .cfi_def_cfa_register   %rsp
359 .Lmul_epilogue:
360         ret
361 .cfi_endproc
362 .size   bn_mul_mont,.-bn_mul_mont
363 ___
364 {{{
365 my @A=("%r10","%r11");
366 my @N=("%r13","%rdi");
367 $code.=<<___;
368 .type   bn_mul4x_mont,\@function,6
369 .align  16
370 bn_mul4x_mont:
371 .cfi_startproc
372         mov     ${num}d,${num}d
373         mov     %rsp,%rax
374 .cfi_def_cfa_register   %rax
375 .Lmul4x_enter:
376 ___
377 $code.=<<___ if ($addx);
378         and     \$0x80100,%r11d
379         cmp     \$0x80100,%r11d
380         je      .Lmulx4x_enter
381 ___
382 $code.=<<___;
383         push    %rbx
384 .cfi_push       %rbx
385         push    %rbp
386 .cfi_push       %rbp
387         push    %r12
388 .cfi_push       %r12
389         push    %r13
390 .cfi_push       %r13
391         push    %r14
392 .cfi_push       %r14
393         push    %r15
394 .cfi_push       %r15
395
396         neg     $num
397         mov     %rsp,%r11
398         lea     -32(%rsp,$num,8),%r10   # future alloca(8*(num+4))
399         neg     $num                    # restore
400         and     \$-1024,%r10            # minimize TLB usage
401
402         sub     %r10,%r11
403         and     \$-4096,%r11
404         lea     (%r10,%r11),%rsp
405         mov     (%rsp),%r11
406         cmp     %r10,%rsp
407         ja      .Lmul4x_page_walk
408         jmp     .Lmul4x_page_walk_done
409
410 .Lmul4x_page_walk:
411         lea     -4096(%rsp),%rsp
412         mov     (%rsp),%r11
413         cmp     %r10,%rsp
414         ja      .Lmul4x_page_walk
415 .Lmul4x_page_walk_done:
416
417         mov     %rax,8(%rsp,$num,8)     # tp[num+1]=%rsp
418 .cfi_cfa_expression     %rsp+8,$num,8,mul,plus,deref,+8
419 .Lmul4x_body:
420         mov     $rp,16(%rsp,$num,8)     # tp[num+2]=$rp
421         mov     %rdx,%r12               # reassign $bp
422 ___
423                 $bp="%r12";
424 $code.=<<___;
425         mov     ($n0),$n0               # pull n0[0] value
426         mov     ($bp),$m0               # m0=bp[0]
427         mov     ($ap),%rax
428
429         xor     $i,$i                   # i=0
430         xor     $j,$j                   # j=0
431
432         mov     $n0,$m1
433         mulq    $m0                     # ap[0]*bp[0]
434         mov     %rax,$A[0]
435         mov     ($np),%rax
436
437         imulq   $A[0],$m1               # "tp[0]"*n0
438         mov     %rdx,$A[1]
439
440         mulq    $m1                     # np[0]*m1
441         add     %rax,$A[0]              # discarded
442         mov     8($ap),%rax
443         adc     \$0,%rdx
444         mov     %rdx,$N[1]
445
446         mulq    $m0
447         add     %rax,$A[1]
448         mov     8($np),%rax
449         adc     \$0,%rdx
450         mov     %rdx,$A[0]
451
452         mulq    $m1
453         add     %rax,$N[1]
454         mov     16($ap),%rax
455         adc     \$0,%rdx
456         add     $A[1],$N[1]
457         lea     4($j),$j                # j++
458         adc     \$0,%rdx
459         mov     $N[1],(%rsp)
460         mov     %rdx,$N[0]
461         jmp     .L1st4x
462 .align  16
463 .L1st4x:
464         mulq    $m0                     # ap[j]*bp[0]
465         add     %rax,$A[0]
466         mov     -16($np,$j,8),%rax
467         adc     \$0,%rdx
468         mov     %rdx,$A[1]
469
470         mulq    $m1                     # np[j]*m1
471         add     %rax,$N[0]
472         mov     -8($ap,$j,8),%rax
473         adc     \$0,%rdx
474         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
475         adc     \$0,%rdx
476         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
477         mov     %rdx,$N[1]
478
479         mulq    $m0                     # ap[j]*bp[0]
480         add     %rax,$A[1]
481         mov     -8($np,$j,8),%rax
482         adc     \$0,%rdx
483         mov     %rdx,$A[0]
484
485         mulq    $m1                     # np[j]*m1
486         add     %rax,$N[1]
487         mov     ($ap,$j,8),%rax
488         adc     \$0,%rdx
489         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
490         adc     \$0,%rdx
491         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
492         mov     %rdx,$N[0]
493
494         mulq    $m0                     # ap[j]*bp[0]
495         add     %rax,$A[0]
496         mov     ($np,$j,8),%rax
497         adc     \$0,%rdx
498         mov     %rdx,$A[1]
499
500         mulq    $m1                     # np[j]*m1
501         add     %rax,$N[0]
502         mov     8($ap,$j,8),%rax
503         adc     \$0,%rdx
504         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
505         adc     \$0,%rdx
506         mov     $N[0],-8(%rsp,$j,8)     # tp[j-1]
507         mov     %rdx,$N[1]
508
509         mulq    $m0                     # ap[j]*bp[0]
510         add     %rax,$A[1]
511         mov     8($np,$j,8),%rax
512         adc     \$0,%rdx
513         lea     4($j),$j                # j++
514         mov     %rdx,$A[0]
515
516         mulq    $m1                     # np[j]*m1
517         add     %rax,$N[1]
518         mov     -16($ap,$j,8),%rax
519         adc     \$0,%rdx
520         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
521         adc     \$0,%rdx
522         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
523         mov     %rdx,$N[0]
524         cmp     $num,$j
525         jb      .L1st4x
526
527         mulq    $m0                     # ap[j]*bp[0]
528         add     %rax,$A[0]
529         mov     -16($np,$j,8),%rax
530         adc     \$0,%rdx
531         mov     %rdx,$A[1]
532
533         mulq    $m1                     # np[j]*m1
534         add     %rax,$N[0]
535         mov     -8($ap,$j,8),%rax
536         adc     \$0,%rdx
537         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
538         adc     \$0,%rdx
539         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
540         mov     %rdx,$N[1]
541
542         mulq    $m0                     # ap[j]*bp[0]
543         add     %rax,$A[1]
544         mov     -8($np,$j,8),%rax
545         adc     \$0,%rdx
546         mov     %rdx,$A[0]
547
548         mulq    $m1                     # np[j]*m1
549         add     %rax,$N[1]
550         mov     ($ap),%rax              # ap[0]
551         adc     \$0,%rdx
552         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
553         adc     \$0,%rdx
554         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
555         mov     %rdx,$N[0]
556
557         xor     $N[1],$N[1]
558         add     $A[0],$N[0]
559         adc     \$0,$N[1]
560         mov     $N[0],-8(%rsp,$j,8)
561         mov     $N[1],(%rsp,$j,8)       # store upmost overflow bit
562
563         lea     1($i),$i                # i++
564 .align  4
565 .Louter4x:
566         mov     ($bp,$i,8),$m0          # m0=bp[i]
567         xor     $j,$j                   # j=0
568         mov     (%rsp),$A[0]
569         mov     $n0,$m1
570         mulq    $m0                     # ap[0]*bp[i]
571         add     %rax,$A[0]              # ap[0]*bp[i]+tp[0]
572         mov     ($np),%rax
573         adc     \$0,%rdx
574
575         imulq   $A[0],$m1               # tp[0]*n0
576         mov     %rdx,$A[1]
577
578         mulq    $m1                     # np[0]*m1
579         add     %rax,$A[0]              # "$N[0]", discarded
580         mov     8($ap),%rax
581         adc     \$0,%rdx
582         mov     %rdx,$N[1]
583
584         mulq    $m0                     # ap[j]*bp[i]
585         add     %rax,$A[1]
586         mov     8($np),%rax
587         adc     \$0,%rdx
588         add     8(%rsp),$A[1]           # +tp[1]
589         adc     \$0,%rdx
590         mov     %rdx,$A[0]
591
592         mulq    $m1                     # np[j]*m1
593         add     %rax,$N[1]
594         mov     16($ap),%rax
595         adc     \$0,%rdx
596         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[i]+tp[j]
597         lea     4($j),$j                # j+=2
598         adc     \$0,%rdx
599         mov     $N[1],(%rsp)            # tp[j-1]
600         mov     %rdx,$N[0]
601         jmp     .Linner4x
602 .align  16
603 .Linner4x:
604         mulq    $m0                     # ap[j]*bp[i]
605         add     %rax,$A[0]
606         mov     -16($np,$j,8),%rax
607         adc     \$0,%rdx
608         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
609         adc     \$0,%rdx
610         mov     %rdx,$A[1]
611
612         mulq    $m1                     # np[j]*m1
613         add     %rax,$N[0]
614         mov     -8($ap,$j,8),%rax
615         adc     \$0,%rdx
616         add     $A[0],$N[0]
617         adc     \$0,%rdx
618         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
619         mov     %rdx,$N[1]
620
621         mulq    $m0                     # ap[j]*bp[i]
622         add     %rax,$A[1]
623         mov     -8($np,$j,8),%rax
624         adc     \$0,%rdx
625         add     -8(%rsp,$j,8),$A[1]
626         adc     \$0,%rdx
627         mov     %rdx,$A[0]
628
629         mulq    $m1                     # np[j]*m1
630         add     %rax,$N[1]
631         mov     ($ap,$j,8),%rax
632         adc     \$0,%rdx
633         add     $A[1],$N[1]
634         adc     \$0,%rdx
635         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
636         mov     %rdx,$N[0]
637
638         mulq    $m0                     # ap[j]*bp[i]
639         add     %rax,$A[0]
640         mov     ($np,$j,8),%rax
641         adc     \$0,%rdx
642         add     (%rsp,$j,8),$A[0]       # ap[j]*bp[i]+tp[j]
643         adc     \$0,%rdx
644         mov     %rdx,$A[1]
645
646         mulq    $m1                     # np[j]*m1
647         add     %rax,$N[0]
648         mov     8($ap,$j,8),%rax
649         adc     \$0,%rdx
650         add     $A[0],$N[0]
651         adc     \$0,%rdx
652         mov     $N[0],-8(%rsp,$j,8)     # tp[j-1]
653         mov     %rdx,$N[1]
654
655         mulq    $m0                     # ap[j]*bp[i]
656         add     %rax,$A[1]
657         mov     8($np,$j,8),%rax
658         adc     \$0,%rdx
659         add     8(%rsp,$j,8),$A[1]
660         adc     \$0,%rdx
661         lea     4($j),$j                # j++
662         mov     %rdx,$A[0]
663
664         mulq    $m1                     # np[j]*m1
665         add     %rax,$N[1]
666         mov     -16($ap,$j,8),%rax
667         adc     \$0,%rdx
668         add     $A[1],$N[1]
669         adc     \$0,%rdx
670         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
671         mov     %rdx,$N[0]
672         cmp     $num,$j
673         jb      .Linner4x
674
675         mulq    $m0                     # ap[j]*bp[i]
676         add     %rax,$A[0]
677         mov     -16($np,$j,8),%rax
678         adc     \$0,%rdx
679         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
680         adc     \$0,%rdx
681         mov     %rdx,$A[1]
682
683         mulq    $m1                     # np[j]*m1
684         add     %rax,$N[0]
685         mov     -8($ap,$j,8),%rax
686         adc     \$0,%rdx
687         add     $A[0],$N[0]
688         adc     \$0,%rdx
689         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
690         mov     %rdx,$N[1]
691
692         mulq    $m0                     # ap[j]*bp[i]
693         add     %rax,$A[1]
694         mov     -8($np,$j,8),%rax
695         adc     \$0,%rdx
696         add     -8(%rsp,$j,8),$A[1]
697         adc     \$0,%rdx
698         lea     1($i),$i                # i++
699         mov     %rdx,$A[0]
700
701         mulq    $m1                     # np[j]*m1
702         add     %rax,$N[1]
703         mov     ($ap),%rax              # ap[0]
704         adc     \$0,%rdx
705         add     $A[1],$N[1]
706         adc     \$0,%rdx
707         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
708         mov     %rdx,$N[0]
709
710         xor     $N[1],$N[1]
711         add     $A[0],$N[0]
712         adc     \$0,$N[1]
713         add     (%rsp,$num,8),$N[0]     # pull upmost overflow bit
714         adc     \$0,$N[1]
715         mov     $N[0],-8(%rsp,$j,8)
716         mov     $N[1],(%rsp,$j,8)       # store upmost overflow bit
717
718         cmp     $num,$i
719         jb      .Louter4x
720 ___
721 {
722 my @ri=("%rax","%rdx",$m0,$m1);
723 $code.=<<___;
724         mov     16(%rsp,$num,8),$rp     # restore $rp
725         lea     -4($num),$j
726         mov     0(%rsp),@ri[0]          # tp[0]
727         mov     8(%rsp),@ri[1]          # tp[1]
728         shr     \$2,$j                  # j=num/4-1
729         lea     (%rsp),$ap              # borrow ap for tp
730         xor     $i,$i                   # i=0 and clear CF!
731
732         sub     0($np),@ri[0]
733         mov     16($ap),@ri[2]          # tp[2]
734         mov     24($ap),@ri[3]          # tp[3]
735         sbb     8($np),@ri[1]
736
737 .Lsub4x:
738         mov     @ri[0],0($rp,$i,8)      # rp[i]=tp[i]-np[i]
739         mov     @ri[1],8($rp,$i,8)      # rp[i]=tp[i]-np[i]
740         sbb     16($np,$i,8),@ri[2]
741         mov     32($ap,$i,8),@ri[0]     # tp[i+1]
742         mov     40($ap,$i,8),@ri[1]
743         sbb     24($np,$i,8),@ri[3]
744         mov     @ri[2],16($rp,$i,8)     # rp[i]=tp[i]-np[i]
745         mov     @ri[3],24($rp,$i,8)     # rp[i]=tp[i]-np[i]
746         sbb     32($np,$i,8),@ri[0]
747         mov     48($ap,$i,8),@ri[2]
748         mov     56($ap,$i,8),@ri[3]
749         sbb     40($np,$i,8),@ri[1]
750         lea     4($i),$i                # i++
751         dec     $j                      # doesn't affect CF!
752         jnz     .Lsub4x
753
754         mov     @ri[0],0($rp,$i,8)      # rp[i]=tp[i]-np[i]
755         mov     32($ap,$i,8),@ri[0]     # load overflow bit
756         sbb     16($np,$i,8),@ri[2]
757         mov     @ri[1],8($rp,$i,8)      # rp[i]=tp[i]-np[i]
758         sbb     24($np,$i,8),@ri[3]
759         mov     @ri[2],16($rp,$i,8)     # rp[i]=tp[i]-np[i]
760
761         sbb     \$0,@ri[0]              # handle upmost overflow bit
762         mov     @ri[3],24($rp,$i,8)     # rp[i]=tp[i]-np[i]
763         pxor    %xmm0,%xmm0
764         movq    @ri[0],%xmm4
765         pcmpeqd %xmm5,%xmm5
766         pshufd  \$0,%xmm4,%xmm4
767         mov     $num,$j
768         pxor    %xmm4,%xmm5
769         shr     \$2,$j                  # j=num/4
770         xor     %eax,%eax               # i=0
771
772         jmp     .Lcopy4x
773 .align  16
774 .Lcopy4x:                               # conditional copy
775         movdqa  (%rsp,%rax),%xmm1
776         movdqu  ($rp,%rax),%xmm2
777         pand    %xmm4,%xmm1
778         pand    %xmm5,%xmm2
779         movdqa  16(%rsp,%rax),%xmm3
780         movdqa  %xmm0,(%rsp,%rax)
781         por     %xmm2,%xmm1
782         movdqu  16($rp,%rax),%xmm2
783         movdqu  %xmm1,($rp,%rax)
784         pand    %xmm4,%xmm3
785         pand    %xmm5,%xmm2
786         movdqa  %xmm0,16(%rsp,%rax)
787         por     %xmm2,%xmm3
788         movdqu  %xmm3,16($rp,%rax)
789         lea     32(%rax),%rax
790         dec     $j
791         jnz     .Lcopy4x
792 ___
793 }
794 $code.=<<___;
795         mov     8(%rsp,$num,8),%rsi     # restore %rsp
796 .cfi_def_cfa    %rsi, 8
797         mov     \$1,%rax
798         mov     -48(%rsi),%r15
799 .cfi_restore    %r15
800         mov     -40(%rsi),%r14
801 .cfi_restore    %r14
802         mov     -32(%rsi),%r13
803 .cfi_restore    %r13
804         mov     -24(%rsi),%r12
805 .cfi_restore    %r12
806         mov     -16(%rsi),%rbp
807 .cfi_restore    %rbp
808         mov     -8(%rsi),%rbx
809 .cfi_restore    %rbx
810         lea     (%rsi),%rsp
811 .cfi_def_cfa_register   %rsp
812 .Lmul4x_epilogue:
813         ret
814 .cfi_endproc
815 .size   bn_mul4x_mont,.-bn_mul4x_mont
816 ___
817 }}}
818 \f{{{
819 ######################################################################
820 # void bn_sqr8x_mont(
821 my $rptr="%rdi";        # const BN_ULONG *rptr,
822 my $aptr="%rsi";        # const BN_ULONG *aptr,
823 my $bptr="%rdx";        # not used
824 my $nptr="%rcx";        # const BN_ULONG *nptr,
825 my $n0  ="%r8";         # const BN_ULONG *n0);
826 my $num ="%r9";         # int num, has to be divisible by 8
827
828 my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
829 my @A0=("%r10","%r11");
830 my @A1=("%r12","%r13");
831 my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
832
833 $code.=<<___    if ($addx);
834 .extern bn_sqrx8x_internal              # see x86_64-mont5 module
835 ___
836 $code.=<<___;
837 .extern bn_sqr8x_internal               # see x86_64-mont5 module
838
839 .type   bn_sqr8x_mont,\@function,6
840 .align  32
841 bn_sqr8x_mont:
842 .cfi_startproc
843         mov     %rsp,%rax
844 .cfi_def_cfa_register   %rax
845 .Lsqr8x_enter:
846         push    %rbx
847 .cfi_push       %rbx
848         push    %rbp
849 .cfi_push       %rbp
850         push    %r12
851 .cfi_push       %r12
852         push    %r13
853 .cfi_push       %r13
854         push    %r14
855 .cfi_push       %r14
856         push    %r15
857 .cfi_push       %r15
858 .Lsqr8x_prologue:
859
860         mov     ${num}d,%r10d
861         shl     \$3,${num}d             # convert $num to bytes
862         shl     \$3+2,%r10              # 4*$num
863         neg     $num
864
865         ##############################################################
866         # ensure that stack frame doesn't alias with $aptr modulo
867         # 4096. this is done to allow memory disambiguation logic
868         # do its job.
869         #
870         lea     -64(%rsp,$num,2),%r11
871         mov     %rsp,%rbp
872         mov     ($n0),$n0               # *n0
873         sub     $aptr,%r11
874         and     \$4095,%r11
875         cmp     %r11,%r10
876         jb      .Lsqr8x_sp_alt
877         sub     %r11,%rbp               # align with $aptr
878         lea     -64(%rbp,$num,2),%rbp   # future alloca(frame+2*$num)
879         jmp     .Lsqr8x_sp_done
880
881 .align  32
882 .Lsqr8x_sp_alt:
883         lea     4096-64(,$num,2),%r10   # 4096-frame-2*$num
884         lea     -64(%rbp,$num,2),%rbp   # future alloca(frame+2*$num)
885         sub     %r10,%r11
886         mov     \$0,%r10
887         cmovc   %r10,%r11
888         sub     %r11,%rbp
889 .Lsqr8x_sp_done:
890         and     \$-64,%rbp
891         mov     %rsp,%r11
892         sub     %rbp,%r11
893         and     \$-4096,%r11
894         lea     (%rbp,%r11),%rsp
895         mov     (%rsp),%r10
896         cmp     %rbp,%rsp
897         ja      .Lsqr8x_page_walk
898         jmp     .Lsqr8x_page_walk_done
899
900 .align  16
901 .Lsqr8x_page_walk:
902         lea     -4096(%rsp),%rsp
903         mov     (%rsp),%r10
904         cmp     %rbp,%rsp
905         ja      .Lsqr8x_page_walk
906 .Lsqr8x_page_walk_done:
907
908         mov     $num,%r10
909         neg     $num
910
911         mov     $n0,  32(%rsp)
912         mov     %rax, 40(%rsp)          # save original %rsp
913 .cfi_cfa_expression     %rsp+40,deref,+8
914 .Lsqr8x_body:
915
916         movq    $nptr, %xmm2            # save pointer to modulus
917         pxor    %xmm0,%xmm0
918         movq    $rptr,%xmm1             # save $rptr
919         movq    %r10, %xmm3             # -$num
920 ___
921 $code.=<<___ if ($addx);
922         mov     OPENSSL_ia32cap_P+8(%rip),%eax
923         and     \$0x80100,%eax
924         cmp     \$0x80100,%eax
925         jne     .Lsqr8x_nox
926
927         call    bn_sqrx8x_internal      # see x86_64-mont5 module
928                                         # %rax  top-most carry
929                                         # %rbp  nptr
930                                         # %rcx  -8*num
931                                         # %r8   end of tp[2*num]
932         lea     (%r8,%rcx),%rbx
933         mov     %rcx,$num
934         mov     %rcx,%rdx
935         movq    %xmm1,$rptr
936         sar     \$3+2,%rcx              # %cf=0
937         jmp     .Lsqr8x_sub
938
939 .align  32
940 .Lsqr8x_nox:
941 ___
942 $code.=<<___;
943         call    bn_sqr8x_internal       # see x86_64-mont5 module
944                                         # %rax  top-most carry
945                                         # %rbp  nptr
946                                         # %r8   -8*num
947                                         # %rdi  end of tp[2*num]
948         lea     (%rdi,$num),%rbx
949         mov     $num,%rcx
950         mov     $num,%rdx
951         movq    %xmm1,$rptr
952         sar     \$3+2,%rcx              # %cf=0
953         jmp     .Lsqr8x_sub
954
955 .align  32
956 .Lsqr8x_sub:
957         mov     8*0(%rbx),%r12
958         mov     8*1(%rbx),%r13
959         mov     8*2(%rbx),%r14
960         mov     8*3(%rbx),%r15
961         lea     8*4(%rbx),%rbx
962         sbb     8*0(%rbp),%r12
963         sbb     8*1(%rbp),%r13
964         sbb     8*2(%rbp),%r14
965         sbb     8*3(%rbp),%r15
966         lea     8*4(%rbp),%rbp
967         mov     %r12,8*0($rptr)
968         mov     %r13,8*1($rptr)
969         mov     %r14,8*2($rptr)
970         mov     %r15,8*3($rptr)
971         lea     8*4($rptr),$rptr
972         inc     %rcx                    # preserves %cf
973         jnz     .Lsqr8x_sub
974
975         sbb     \$0,%rax                # top-most carry
976         lea     (%rbx,$num),%rbx        # rewind
977         lea     ($rptr,$num),$rptr      # rewind
978
979         movq    %rax,%xmm1
980         pxor    %xmm0,%xmm0
981         pshufd  \$0,%xmm1,%xmm1
982         mov     40(%rsp),%rsi           # restore %rsp
983 .cfi_def_cfa    %rsi,8
984         jmp     .Lsqr8x_cond_copy
985
986 .align  32
987 .Lsqr8x_cond_copy:
988         movdqa  16*0(%rbx),%xmm2
989         movdqa  16*1(%rbx),%xmm3
990         lea     16*2(%rbx),%rbx
991         movdqu  16*0($rptr),%xmm4
992         movdqu  16*1($rptr),%xmm5
993         lea     16*2($rptr),$rptr
994         movdqa  %xmm0,-16*2(%rbx)       # zero tp
995         movdqa  %xmm0,-16*1(%rbx)
996         movdqa  %xmm0,-16*2(%rbx,%rdx)
997         movdqa  %xmm0,-16*1(%rbx,%rdx)
998         pcmpeqd %xmm1,%xmm0
999         pand    %xmm1,%xmm2
1000         pand    %xmm1,%xmm3
1001         pand    %xmm0,%xmm4
1002         pand    %xmm0,%xmm5
1003         pxor    %xmm0,%xmm0
1004         por     %xmm2,%xmm4
1005         por     %xmm3,%xmm5
1006         movdqu  %xmm4,-16*2($rptr)
1007         movdqu  %xmm5,-16*1($rptr)
1008         add     \$32,$num
1009         jnz     .Lsqr8x_cond_copy
1010
1011         mov     \$1,%rax
1012         mov     -48(%rsi),%r15
1013 .cfi_restore    %r15
1014         mov     -40(%rsi),%r14
1015 .cfi_restore    %r14
1016         mov     -32(%rsi),%r13
1017 .cfi_restore    %r13
1018         mov     -24(%rsi),%r12
1019 .cfi_restore    %r12
1020         mov     -16(%rsi),%rbp
1021 .cfi_restore    %rbp
1022         mov     -8(%rsi),%rbx
1023 .cfi_restore    %rbx
1024         lea     (%rsi),%rsp
1025 .cfi_def_cfa_register   %rsp
1026 .Lsqr8x_epilogue:
1027         ret
1028 .cfi_endproc
1029 .size   bn_sqr8x_mont,.-bn_sqr8x_mont
1030 ___
1031 }}}
1032 \f
1033 if ($addx) {{{
1034 my $bp="%rdx";  # original value
1035
1036 $code.=<<___;
1037 .type   bn_mulx4x_mont,\@function,6
1038 .align  32
1039 bn_mulx4x_mont:
1040 .cfi_startproc
1041         mov     %rsp,%rax
1042 .cfi_def_cfa_register   %rax
1043 .Lmulx4x_enter:
1044         push    %rbx
1045 .cfi_push       %rbx
1046         push    %rbp
1047 .cfi_push       %rbp
1048         push    %r12
1049 .cfi_push       %r12
1050         push    %r13
1051 .cfi_push       %r13
1052         push    %r14
1053 .cfi_push       %r14
1054         push    %r15
1055 .cfi_push       %r15
1056 .Lmulx4x_prologue:
1057
1058         shl     \$3,${num}d             # convert $num to bytes
1059         xor     %r10,%r10
1060         sub     $num,%r10               # -$num
1061         mov     ($n0),$n0               # *n0
1062         lea     -72(%rsp,%r10),%rbp     # future alloca(frame+$num+8)
1063         and     \$-128,%rbp
1064         mov     %rsp,%r11
1065         sub     %rbp,%r11
1066         and     \$-4096,%r11
1067         lea     (%rbp,%r11),%rsp
1068         mov     (%rsp),%r10
1069         cmp     %rbp,%rsp
1070         ja      .Lmulx4x_page_walk
1071         jmp     .Lmulx4x_page_walk_done
1072
1073 .align  16
1074 .Lmulx4x_page_walk:
1075         lea     -4096(%rsp),%rsp
1076         mov     (%rsp),%r10
1077         cmp     %rbp,%rsp
1078         ja      .Lmulx4x_page_walk
1079 .Lmulx4x_page_walk_done:
1080
1081         lea     ($bp,$num),%r10
1082         ##############################################################
1083         # Stack layout
1084         # +0    num
1085         # +8    off-loaded &b[i]
1086         # +16   end of b[num]
1087         # +24   saved n0
1088         # +32   saved rp
1089         # +40   saved %rsp
1090         # +48   inner counter
1091         # +56
1092         # +64   tmp[num+1]
1093         #
1094         mov     $num,0(%rsp)            # save $num
1095         shr     \$5,$num
1096         mov     %r10,16(%rsp)           # end of b[num]
1097         sub     \$1,$num
1098         mov     $n0, 24(%rsp)           # save *n0
1099         mov     $rp, 32(%rsp)           # save $rp
1100         mov     %rax,40(%rsp)           # save original %rsp
1101 .cfi_cfa_expression     %rsp+40,deref,+8
1102         mov     $num,48(%rsp)           # inner counter
1103         jmp     .Lmulx4x_body
1104
1105 .align  32
1106 .Lmulx4x_body:
1107 ___
1108 my ($aptr, $bptr, $nptr, $tptr, $mi,  $bi,  $zero, $num)=
1109    ("%rsi","%rdi","%rcx","%rbx","%r8","%r9","%rbp","%rax");
1110 my $rptr=$bptr;
1111 $code.=<<___;
1112         lea     8($bp),$bptr
1113         mov     ($bp),%rdx              # b[0], $bp==%rdx actually
1114         lea     64+32(%rsp),$tptr
1115         mov     %rdx,$bi
1116
1117         mulx    0*8($aptr),$mi,%rax     # a[0]*b[0]
1118         mulx    1*8($aptr),%r11,%r14    # a[1]*b[0]
1119         add     %rax,%r11
1120         mov     $bptr,8(%rsp)           # off-load &b[i]
1121         mulx    2*8($aptr),%r12,%r13    # ...
1122         adc     %r14,%r12
1123         adc     \$0,%r13
1124
1125         mov     $mi,$bptr               # borrow $bptr
1126         imulq   24(%rsp),$mi            # "t[0]"*n0
1127         xor     $zero,$zero             # cf=0, of=0
1128
1129         mulx    3*8($aptr),%rax,%r14
1130          mov    $mi,%rdx
1131         lea     4*8($aptr),$aptr
1132         adcx    %rax,%r13
1133         adcx    $zero,%r14              # cf=0
1134
1135         mulx    0*8($nptr),%rax,%r10
1136         adcx    %rax,$bptr              # discarded
1137         adox    %r11,%r10
1138         mulx    1*8($nptr),%rax,%r11
1139         adcx    %rax,%r10
1140         adox    %r12,%r11
1141         .byte   0xc4,0x62,0xfb,0xf6,0xa1,0x10,0x00,0x00,0x00    # mulx  2*8($nptr),%rax,%r12
1142         mov     48(%rsp),$bptr          # counter value
1143         mov     %r10,-4*8($tptr)
1144         adcx    %rax,%r11
1145         adox    %r13,%r12
1146         mulx    3*8($nptr),%rax,%r15
1147          mov    $bi,%rdx
1148         mov     %r11,-3*8($tptr)
1149         adcx    %rax,%r12
1150         adox    $zero,%r15              # of=0
1151         lea     4*8($nptr),$nptr
1152         mov     %r12,-2*8($tptr)
1153
1154         jmp     .Lmulx4x_1st
1155
1156 .align  32
1157 .Lmulx4x_1st:
1158         adcx    $zero,%r15              # cf=0, modulo-scheduled
1159         mulx    0*8($aptr),%r10,%rax    # a[4]*b[0]
1160         adcx    %r14,%r10
1161         mulx    1*8($aptr),%r11,%r14    # a[5]*b[0]
1162         adcx    %rax,%r11
1163         mulx    2*8($aptr),%r12,%rax    # ...
1164         adcx    %r14,%r12
1165         mulx    3*8($aptr),%r13,%r14
1166          .byte  0x67,0x67
1167          mov    $mi,%rdx
1168         adcx    %rax,%r13
1169         adcx    $zero,%r14              # cf=0
1170         lea     4*8($aptr),$aptr
1171         lea     4*8($tptr),$tptr
1172
1173         adox    %r15,%r10
1174         mulx    0*8($nptr),%rax,%r15
1175         adcx    %rax,%r10
1176         adox    %r15,%r11
1177         mulx    1*8($nptr),%rax,%r15
1178         adcx    %rax,%r11
1179         adox    %r15,%r12
1180         mulx    2*8($nptr),%rax,%r15
1181         mov     %r10,-5*8($tptr)
1182         adcx    %rax,%r12
1183         mov     %r11,-4*8($tptr)
1184         adox    %r15,%r13
1185         mulx    3*8($nptr),%rax,%r15
1186          mov    $bi,%rdx
1187         mov     %r12,-3*8($tptr)
1188         adcx    %rax,%r13
1189         adox    $zero,%r15
1190         lea     4*8($nptr),$nptr
1191         mov     %r13,-2*8($tptr)
1192
1193         dec     $bptr                   # of=0, pass cf
1194         jnz     .Lmulx4x_1st
1195
1196         mov     0(%rsp),$num            # load num
1197         mov     8(%rsp),$bptr           # re-load &b[i]
1198         adc     $zero,%r15              # modulo-scheduled
1199         add     %r15,%r14
1200         sbb     %r15,%r15               # top-most carry
1201         mov     %r14,-1*8($tptr)
1202         jmp     .Lmulx4x_outer
1203
1204 .align  32
1205 .Lmulx4x_outer:
1206         mov     ($bptr),%rdx            # b[i]
1207         lea     8($bptr),$bptr          # b++
1208         sub     $num,$aptr              # rewind $aptr
1209         mov     %r15,($tptr)            # save top-most carry
1210         lea     64+4*8(%rsp),$tptr
1211         sub     $num,$nptr              # rewind $nptr
1212
1213         mulx    0*8($aptr),$mi,%r11     # a[0]*b[i]
1214         xor     %ebp,%ebp               # xor   $zero,$zero     # cf=0, of=0
1215         mov     %rdx,$bi
1216         mulx    1*8($aptr),%r14,%r12    # a[1]*b[i]
1217         adox    -4*8($tptr),$mi
1218         adcx    %r14,%r11
1219         mulx    2*8($aptr),%r15,%r13    # ...
1220         adox    -3*8($tptr),%r11
1221         adcx    %r15,%r12
1222         adox    -2*8($tptr),%r12
1223         adcx    $zero,%r13
1224         adox    $zero,%r13
1225
1226         mov     $bptr,8(%rsp)           # off-load &b[i]
1227         mov     $mi,%r15
1228         imulq   24(%rsp),$mi            # "t[0]"*n0
1229         xor     %ebp,%ebp               # xor   $zero,$zero     # cf=0, of=0
1230
1231         mulx    3*8($aptr),%rax,%r14
1232          mov    $mi,%rdx
1233         adcx    %rax,%r13
1234         adox    -1*8($tptr),%r13
1235         adcx    $zero,%r14
1236         lea     4*8($aptr),$aptr
1237         adox    $zero,%r14
1238
1239         mulx    0*8($nptr),%rax,%r10
1240         adcx    %rax,%r15               # discarded
1241         adox    %r11,%r10
1242         mulx    1*8($nptr),%rax,%r11
1243         adcx    %rax,%r10
1244         adox    %r12,%r11
1245         mulx    2*8($nptr),%rax,%r12
1246         mov     %r10,-4*8($tptr)
1247         adcx    %rax,%r11
1248         adox    %r13,%r12
1249         mulx    3*8($nptr),%rax,%r15
1250          mov    $bi,%rdx
1251         mov     %r11,-3*8($tptr)
1252         lea     4*8($nptr),$nptr
1253         adcx    %rax,%r12
1254         adox    $zero,%r15              # of=0
1255         mov     48(%rsp),$bptr          # counter value
1256         mov     %r12,-2*8($tptr)
1257
1258         jmp     .Lmulx4x_inner
1259
1260 .align  32
1261 .Lmulx4x_inner:
1262         mulx    0*8($aptr),%r10,%rax    # a[4]*b[i]
1263         adcx    $zero,%r15              # cf=0, modulo-scheduled
1264         adox    %r14,%r10
1265         mulx    1*8($aptr),%r11,%r14    # a[5]*b[i]
1266         adcx    0*8($tptr),%r10
1267         adox    %rax,%r11
1268         mulx    2*8($aptr),%r12,%rax    # ...
1269         adcx    1*8($tptr),%r11
1270         adox    %r14,%r12
1271         mulx    3*8($aptr),%r13,%r14
1272          mov    $mi,%rdx
1273         adcx    2*8($tptr),%r12
1274         adox    %rax,%r13
1275         adcx    3*8($tptr),%r13
1276         adox    $zero,%r14              # of=0
1277         lea     4*8($aptr),$aptr
1278         lea     4*8($tptr),$tptr
1279         adcx    $zero,%r14              # cf=0
1280
1281         adox    %r15,%r10
1282         mulx    0*8($nptr),%rax,%r15
1283         adcx    %rax,%r10
1284         adox    %r15,%r11
1285         mulx    1*8($nptr),%rax,%r15
1286         adcx    %rax,%r11
1287         adox    %r15,%r12
1288         mulx    2*8($nptr),%rax,%r15
1289         mov     %r10,-5*8($tptr)
1290         adcx    %rax,%r12
1291         adox    %r15,%r13
1292         mulx    3*8($nptr),%rax,%r15
1293          mov    $bi,%rdx
1294         mov     %r11,-4*8($tptr)
1295         mov     %r12,-3*8($tptr)
1296         adcx    %rax,%r13
1297         adox    $zero,%r15
1298         lea     4*8($nptr),$nptr
1299         mov     %r13,-2*8($tptr)
1300
1301         dec     $bptr                   # of=0, pass cf
1302         jnz     .Lmulx4x_inner
1303
1304         mov     0(%rsp),$num            # load num
1305         mov     8(%rsp),$bptr           # re-load &b[i]
1306         adc     $zero,%r15              # modulo-scheduled
1307         sub     0*8($tptr),$zero        # pull top-most carry
1308         adc     %r15,%r14
1309         sbb     %r15,%r15               # top-most carry
1310         mov     %r14,-1*8($tptr)
1311
1312         cmp     16(%rsp),$bptr
1313         jne     .Lmulx4x_outer
1314
1315         lea     64(%rsp),$tptr
1316         sub     $num,$nptr              # rewind $nptr
1317         neg     %r15
1318         mov     $num,%rdx
1319         shr     \$3+2,$num              # %cf=0
1320         mov     32(%rsp),$rptr          # restore rp
1321         jmp     .Lmulx4x_sub
1322
1323 .align  32
1324 .Lmulx4x_sub:
1325         mov     8*0($tptr),%r11
1326         mov     8*1($tptr),%r12
1327         mov     8*2($tptr),%r13
1328         mov     8*3($tptr),%r14
1329         lea     8*4($tptr),$tptr
1330         sbb     8*0($nptr),%r11
1331         sbb     8*1($nptr),%r12
1332         sbb     8*2($nptr),%r13
1333         sbb     8*3($nptr),%r14
1334         lea     8*4($nptr),$nptr
1335         mov     %r11,8*0($rptr)
1336         mov     %r12,8*1($rptr)
1337         mov     %r13,8*2($rptr)
1338         mov     %r14,8*3($rptr)
1339         lea     8*4($rptr),$rptr
1340         dec     $num                    # preserves %cf
1341         jnz     .Lmulx4x_sub
1342
1343         sbb     \$0,%r15                # top-most carry
1344         lea     64(%rsp),$tptr
1345         sub     %rdx,$rptr              # rewind
1346
1347         movq    %r15,%xmm1
1348         pxor    %xmm0,%xmm0
1349         pshufd  \$0,%xmm1,%xmm1
1350         mov     40(%rsp),%rsi           # restore %rsp
1351 .cfi_def_cfa    %rsi,8
1352         jmp     .Lmulx4x_cond_copy
1353
1354 .align  32
1355 .Lmulx4x_cond_copy:
1356         movdqa  16*0($tptr),%xmm2
1357         movdqa  16*1($tptr),%xmm3
1358         lea     16*2($tptr),$tptr
1359         movdqu  16*0($rptr),%xmm4
1360         movdqu  16*1($rptr),%xmm5
1361         lea     16*2($rptr),$rptr
1362         movdqa  %xmm0,-16*2($tptr)      # zero tp
1363         movdqa  %xmm0,-16*1($tptr)
1364         pcmpeqd %xmm1,%xmm0
1365         pand    %xmm1,%xmm2
1366         pand    %xmm1,%xmm3
1367         pand    %xmm0,%xmm4
1368         pand    %xmm0,%xmm5
1369         pxor    %xmm0,%xmm0
1370         por     %xmm2,%xmm4
1371         por     %xmm3,%xmm5
1372         movdqu  %xmm4,-16*2($rptr)
1373         movdqu  %xmm5,-16*1($rptr)
1374         sub     \$32,%rdx
1375         jnz     .Lmulx4x_cond_copy
1376
1377         mov     %rdx,($tptr)
1378
1379         mov     \$1,%rax
1380         mov     -48(%rsi),%r15
1381 .cfi_restore    %r15
1382         mov     -40(%rsi),%r14
1383 .cfi_restore    %r14
1384         mov     -32(%rsi),%r13
1385 .cfi_restore    %r13
1386         mov     -24(%rsi),%r12
1387 .cfi_restore    %r12
1388         mov     -16(%rsi),%rbp
1389 .cfi_restore    %rbp
1390         mov     -8(%rsi),%rbx
1391 .cfi_restore    %rbx
1392         lea     (%rsi),%rsp
1393 .cfi_def_cfa_register   %rsp
1394 .Lmulx4x_epilogue:
1395         ret
1396 .cfi_endproc
1397 .size   bn_mulx4x_mont,.-bn_mulx4x_mont
1398 ___
1399 }}}
1400 $code.=<<___;
1401 .asciz  "Montgomery Multiplication for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
1402 .align  16
1403 ___
1404
1405 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
1406 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
1407 if ($win64) {
1408 $rec="%rcx";
1409 $frame="%rdx";
1410 $context="%r8";
1411 $disp="%r9";
1412
1413 $code.=<<___;
1414 .extern __imp_RtlVirtualUnwind
1415 .type   mul_handler,\@abi-omnipotent
1416 .align  16
1417 mul_handler:
1418         push    %rsi
1419         push    %rdi
1420         push    %rbx
1421         push    %rbp
1422         push    %r12
1423         push    %r13
1424         push    %r14
1425         push    %r15
1426         pushfq
1427         sub     \$64,%rsp
1428
1429         mov     120($context),%rax      # pull context->Rax
1430         mov     248($context),%rbx      # pull context->Rip
1431
1432         mov     8($disp),%rsi           # disp->ImageBase
1433         mov     56($disp),%r11          # disp->HandlerData
1434
1435         mov     0(%r11),%r10d           # HandlerData[0]
1436         lea     (%rsi,%r10),%r10        # end of prologue label
1437         cmp     %r10,%rbx               # context->Rip<end of prologue label
1438         jb      .Lcommon_seh_tail
1439
1440         mov     152($context),%rax      # pull context->Rsp
1441
1442         mov     4(%r11),%r10d           # HandlerData[1]
1443         lea     (%rsi,%r10),%r10        # epilogue label
1444         cmp     %r10,%rbx               # context->Rip>=epilogue label
1445         jae     .Lcommon_seh_tail
1446
1447         mov     192($context),%r10      # pull $num
1448         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
1449
1450         jmp     .Lcommon_pop_regs
1451 .size   mul_handler,.-mul_handler
1452
1453 .type   sqr_handler,\@abi-omnipotent
1454 .align  16
1455 sqr_handler:
1456         push    %rsi
1457         push    %rdi
1458         push    %rbx
1459         push    %rbp
1460         push    %r12
1461         push    %r13
1462         push    %r14
1463         push    %r15
1464         pushfq
1465         sub     \$64,%rsp
1466
1467         mov     120($context),%rax      # pull context->Rax
1468         mov     248($context),%rbx      # pull context->Rip
1469
1470         mov     8($disp),%rsi           # disp->ImageBase
1471         mov     56($disp),%r11          # disp->HandlerData
1472
1473         mov     0(%r11),%r10d           # HandlerData[0]
1474         lea     (%rsi,%r10),%r10        # end of prologue label
1475         cmp     %r10,%rbx               # context->Rip<.Lsqr_prologue
1476         jb      .Lcommon_seh_tail
1477
1478         mov     4(%r11),%r10d           # HandlerData[1]
1479         lea     (%rsi,%r10),%r10        # body label
1480         cmp     %r10,%rbx               # context->Rip<.Lsqr_body
1481         jb      .Lcommon_pop_regs
1482
1483         mov     152($context),%rax      # pull context->Rsp
1484
1485         mov     8(%r11),%r10d           # HandlerData[2]
1486         lea     (%rsi,%r10),%r10        # epilogue label
1487         cmp     %r10,%rbx               # context->Rip>=.Lsqr_epilogue
1488         jae     .Lcommon_seh_tail
1489
1490         mov     40(%rax),%rax           # pull saved stack pointer
1491
1492 .Lcommon_pop_regs:
1493         mov     -8(%rax),%rbx
1494         mov     -16(%rax),%rbp
1495         mov     -24(%rax),%r12
1496         mov     -32(%rax),%r13
1497         mov     -40(%rax),%r14
1498         mov     -48(%rax),%r15
1499         mov     %rbx,144($context)      # restore context->Rbx
1500         mov     %rbp,160($context)      # restore context->Rbp
1501         mov     %r12,216($context)      # restore context->R12
1502         mov     %r13,224($context)      # restore context->R13
1503         mov     %r14,232($context)      # restore context->R14
1504         mov     %r15,240($context)      # restore context->R15
1505
1506 .Lcommon_seh_tail:
1507         mov     8(%rax),%rdi
1508         mov     16(%rax),%rsi
1509         mov     %rax,152($context)      # restore context->Rsp
1510         mov     %rsi,168($context)      # restore context->Rsi
1511         mov     %rdi,176($context)      # restore context->Rdi
1512
1513         mov     40($disp),%rdi          # disp->ContextRecord
1514         mov     $context,%rsi           # context
1515         mov     \$154,%ecx              # sizeof(CONTEXT)
1516         .long   0xa548f3fc              # cld; rep movsq
1517
1518         mov     $disp,%rsi
1519         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
1520         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
1521         mov     0(%rsi),%r8             # arg3, disp->ControlPc
1522         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
1523         mov     40(%rsi),%r10           # disp->ContextRecord
1524         lea     56(%rsi),%r11           # &disp->HandlerData
1525         lea     24(%rsi),%r12           # &disp->EstablisherFrame
1526         mov     %r10,32(%rsp)           # arg5
1527         mov     %r11,40(%rsp)           # arg6
1528         mov     %r12,48(%rsp)           # arg7
1529         mov     %rcx,56(%rsp)           # arg8, (NULL)
1530         call    *__imp_RtlVirtualUnwind(%rip)
1531
1532         mov     \$1,%eax                # ExceptionContinueSearch
1533         add     \$64,%rsp
1534         popfq
1535         pop     %r15
1536         pop     %r14
1537         pop     %r13
1538         pop     %r12
1539         pop     %rbp
1540         pop     %rbx
1541         pop     %rdi
1542         pop     %rsi
1543         ret
1544 .size   sqr_handler,.-sqr_handler
1545
1546 .section        .pdata
1547 .align  4
1548         .rva    .LSEH_begin_bn_mul_mont
1549         .rva    .LSEH_end_bn_mul_mont
1550         .rva    .LSEH_info_bn_mul_mont
1551
1552         .rva    .LSEH_begin_bn_mul4x_mont
1553         .rva    .LSEH_end_bn_mul4x_mont
1554         .rva    .LSEH_info_bn_mul4x_mont
1555
1556         .rva    .LSEH_begin_bn_sqr8x_mont
1557         .rva    .LSEH_end_bn_sqr8x_mont
1558         .rva    .LSEH_info_bn_sqr8x_mont
1559 ___
1560 $code.=<<___ if ($addx);
1561         .rva    .LSEH_begin_bn_mulx4x_mont
1562         .rva    .LSEH_end_bn_mulx4x_mont
1563         .rva    .LSEH_info_bn_mulx4x_mont
1564 ___
1565 $code.=<<___;
1566 .section        .xdata
1567 .align  8
1568 .LSEH_info_bn_mul_mont:
1569         .byte   9,0,0,0
1570         .rva    mul_handler
1571         .rva    .Lmul_body,.Lmul_epilogue       # HandlerData[]
1572 .LSEH_info_bn_mul4x_mont:
1573         .byte   9,0,0,0
1574         .rva    mul_handler
1575         .rva    .Lmul4x_body,.Lmul4x_epilogue   # HandlerData[]
1576 .LSEH_info_bn_sqr8x_mont:
1577         .byte   9,0,0,0
1578         .rva    sqr_handler
1579         .rva    .Lsqr8x_prologue,.Lsqr8x_body,.Lsqr8x_epilogue          # HandlerData[]
1580 .align  8
1581 ___
1582 $code.=<<___ if ($addx);
1583 .LSEH_info_bn_mulx4x_mont:
1584         .byte   9,0,0,0
1585         .rva    sqr_handler
1586         .rva    .Lmulx4x_prologue,.Lmulx4x_body,.Lmulx4x_epilogue       # HandlerData[]
1587 .align  8
1588 ___
1589 }
1590
1591 print $code;
1592 close STDOUT;