x86_64 assembly pack: tolerate spaces in source directory name.
[openssl.git] / crypto / bn / asm / x86_64-mont5.pl
1 #! /usr/bin/env perl
2 # Copyright 2011-2016 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 # August 2011.
18 #
19 # Companion to x86_64-mont.pl that optimizes cache-timing attack
20 # countermeasures. The subroutines are produced by replacing bp[i]
21 # references in their x86_64-mont.pl counterparts with cache-neutral
22 # references to powers table computed in BN_mod_exp_mont_consttime.
23 # In addition subroutine that scatters elements of the powers table
24 # is implemented, so that scatter-/gathering can be tuned without
25 # bn_exp.c modifications.
26
27 # August 2013.
28 #
29 # Add MULX/AD*X code paths and additional interfaces to optimize for
30 # branch prediction unit. For input lengths that are multiples of 8
31 # the np argument is not just modulus value, but one interleaved
32 # with 0. This is to optimize post-condition...
33
34 $flavour = shift;
35 $output  = shift;
36 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
37
38 $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
39
40 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
41 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
42 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
43 die "can't locate x86_64-xlate.pl";
44
45 open OUT,"| \"$^X\" \"$xlate\" $flavour \"$output\"";
46 *STDOUT=*OUT;
47
48 if (`$ENV{CC} -Wa,-v -c -o /dev/null -x assembler /dev/null 2>&1`
49                 =~ /GNU assembler version ([2-9]\.[0-9]+)/) {
50         $addx = ($1>=2.23);
51 }
52
53 if (!$addx && $win64 && ($flavour =~ /nasm/ || $ENV{ASM} =~ /nasm/) &&
54             `nasm -v 2>&1` =~ /NASM version ([2-9]\.[0-9]+)/) {
55         $addx = ($1>=2.10);
56 }
57
58 if (!$addx && $win64 && ($flavour =~ /masm/ || $ENV{ASM} =~ /ml64/) &&
59             `ml64 2>&1` =~ /Version ([0-9]+)\./) {
60         $addx = ($1>=12);
61 }
62
63 if (!$addx && `$ENV{CC} -v 2>&1` =~ /((?:^clang|LLVM) version|.*based on LLVM) ([3-9])\.([0-9]+)/) {
64         my $ver = $2 + $3/100.0;        # 3.1->3.01, 3.10->3.10
65         $addx = ($ver>=3.03);
66 }
67
68 # int bn_mul_mont_gather5(
69 $rp="%rdi";     # BN_ULONG *rp,
70 $ap="%rsi";     # const BN_ULONG *ap,
71 $bp="%rdx";     # const BN_ULONG *bp,
72 $np="%rcx";     # const BN_ULONG *np,
73 $n0="%r8";      # const BN_ULONG *n0,
74 $num="%r9";     # int num,
75                 # int idx);     # 0 to 2^5-1, "index" in $bp holding
76                                 # pre-computed powers of a', interlaced
77                                 # in such manner that b[0] is $bp[idx],
78                                 # b[1] is [2^5+idx], etc.
79 $lo0="%r10";
80 $hi0="%r11";
81 $hi1="%r13";
82 $i="%r14";
83 $j="%r15";
84 $m0="%rbx";
85 $m1="%rbp";
86
87 $code=<<___;
88 .text
89
90 .extern OPENSSL_ia32cap_P
91
92 .globl  bn_mul_mont_gather5
93 .type   bn_mul_mont_gather5,\@function,6
94 .align  64
95 bn_mul_mont_gather5:
96         test    \$7,${num}d
97         jnz     .Lmul_enter
98 ___
99 $code.=<<___ if ($addx);
100         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
101 ___
102 $code.=<<___;
103         jmp     .Lmul4x_enter
104
105 .align  16
106 .Lmul_enter:
107         mov     ${num}d,${num}d
108         mov     %rsp,%rax
109         movd    `($win64?56:8)`(%rsp),%xmm5     # load 7th argument
110         lea     .Linc(%rip),%r10
111         push    %rbx
112         push    %rbp
113         push    %r12
114         push    %r13
115         push    %r14
116         push    %r15
117
118         lea     2($num),%r11
119         neg     %r11
120         lea     -264(%rsp,%r11,8),%rsp  # tp=alloca(8*(num+2)+256+8)
121         and     \$-1024,%rsp            # minimize TLB usage
122
123         mov     %rax,8(%rsp,$num,8)     # tp[num+1]=%rsp
124 .Lmul_body:
125         # An OS-agnostic version of __chkstk.
126         #
127         # Some OSes (Windows) insist on stack being "wired" to
128         # physical memory in strictly sequential manner, i.e. if stack
129         # allocation spans two pages, then reference to farmost one can
130         # be punishable by SEGV. But page walking can do good even on
131         # other OSes, because it guarantees that villain thread hits
132         # the guard page before it can make damage to innocent one...
133         sub     %rsp,%rax
134         and     \$-4096,%rax
135 .Lmul_page_walk:
136         mov     (%rsp,%rax),%r11
137         sub     \$4096,%rax
138         .byte   0x2e                    # predict non-taken
139         jnc     .Lmul_page_walk
140
141         lea     128($bp),%r12           # reassign $bp (+size optimization)
142 ___
143                 $bp="%r12";
144                 $STRIDE=2**5*8;         # 5 is "window size"
145                 $N=$STRIDE/4;           # should match cache line size
146 $code.=<<___;
147         movdqa  0(%r10),%xmm0           # 00000001000000010000000000000000
148         movdqa  16(%r10),%xmm1          # 00000002000000020000000200000002
149         lea     24-112(%rsp,$num,8),%r10# place the mask after tp[num+3] (+ICache optimization)
150         and     \$-16,%r10
151
152         pshufd  \$0,%xmm5,%xmm5         # broadcast index
153         movdqa  %xmm1,%xmm4
154         movdqa  %xmm1,%xmm2
155 ___
156 ########################################################################
157 # calculate mask by comparing 0..31 to index and save result to stack
158 #
159 $code.=<<___;
160         paddd   %xmm0,%xmm1
161         pcmpeqd %xmm5,%xmm0             # compare to 1,0
162         .byte   0x67
163         movdqa  %xmm4,%xmm3
164 ___
165 for($k=0;$k<$STRIDE/16-4;$k+=4) {
166 $code.=<<___;
167         paddd   %xmm1,%xmm2
168         pcmpeqd %xmm5,%xmm1             # compare to 3,2
169         movdqa  %xmm0,`16*($k+0)+112`(%r10)
170         movdqa  %xmm4,%xmm0
171
172         paddd   %xmm2,%xmm3
173         pcmpeqd %xmm5,%xmm2             # compare to 5,4
174         movdqa  %xmm1,`16*($k+1)+112`(%r10)
175         movdqa  %xmm4,%xmm1
176
177         paddd   %xmm3,%xmm0
178         pcmpeqd %xmm5,%xmm3             # compare to 7,6
179         movdqa  %xmm2,`16*($k+2)+112`(%r10)
180         movdqa  %xmm4,%xmm2
181
182         paddd   %xmm0,%xmm1
183         pcmpeqd %xmm5,%xmm0
184         movdqa  %xmm3,`16*($k+3)+112`(%r10)
185         movdqa  %xmm4,%xmm3
186 ___
187 }
188 $code.=<<___;                           # last iteration can be optimized
189         paddd   %xmm1,%xmm2
190         pcmpeqd %xmm5,%xmm1
191         movdqa  %xmm0,`16*($k+0)+112`(%r10)
192
193         paddd   %xmm2,%xmm3
194         .byte   0x67
195         pcmpeqd %xmm5,%xmm2
196         movdqa  %xmm1,`16*($k+1)+112`(%r10)
197
198         pcmpeqd %xmm5,%xmm3
199         movdqa  %xmm2,`16*($k+2)+112`(%r10)
200         pand    `16*($k+0)-128`($bp),%xmm0      # while it's still in register
201
202         pand    `16*($k+1)-128`($bp),%xmm1
203         pand    `16*($k+2)-128`($bp),%xmm2
204         movdqa  %xmm3,`16*($k+3)+112`(%r10)
205         pand    `16*($k+3)-128`($bp),%xmm3
206         por     %xmm2,%xmm0
207         por     %xmm3,%xmm1
208 ___
209 for($k=0;$k<$STRIDE/16-4;$k+=4) {
210 $code.=<<___;
211         movdqa  `16*($k+0)-128`($bp),%xmm4
212         movdqa  `16*($k+1)-128`($bp),%xmm5
213         movdqa  `16*($k+2)-128`($bp),%xmm2
214         pand    `16*($k+0)+112`(%r10),%xmm4
215         movdqa  `16*($k+3)-128`($bp),%xmm3
216         pand    `16*($k+1)+112`(%r10),%xmm5
217         por     %xmm4,%xmm0
218         pand    `16*($k+2)+112`(%r10),%xmm2
219         por     %xmm5,%xmm1
220         pand    `16*($k+3)+112`(%r10),%xmm3
221         por     %xmm2,%xmm0
222         por     %xmm3,%xmm1
223 ___
224 }
225 $code.=<<___;
226         por     %xmm1,%xmm0
227         pshufd  \$0x4e,%xmm0,%xmm1
228         por     %xmm1,%xmm0
229         lea     $STRIDE($bp),$bp
230         movq    %xmm0,$m0               # m0=bp[0]
231
232         mov     ($n0),$n0               # pull n0[0] value
233         mov     ($ap),%rax
234
235         xor     $i,$i                   # i=0
236         xor     $j,$j                   # j=0
237
238         mov     $n0,$m1
239         mulq    $m0                     # ap[0]*bp[0]
240         mov     %rax,$lo0
241         mov     ($np),%rax
242
243         imulq   $lo0,$m1                # "tp[0]"*n0
244         mov     %rdx,$hi0
245
246         mulq    $m1                     # np[0]*m1
247         add     %rax,$lo0               # discarded
248         mov     8($ap),%rax
249         adc     \$0,%rdx
250         mov     %rdx,$hi1
251
252         lea     1($j),$j                # j++
253         jmp     .L1st_enter
254
255 .align  16
256 .L1st:
257         add     %rax,$hi1
258         mov     ($ap,$j,8),%rax
259         adc     \$0,%rdx
260         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
261         mov     $lo0,$hi0
262         adc     \$0,%rdx
263         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
264         mov     %rdx,$hi1
265
266 .L1st_enter:
267         mulq    $m0                     # ap[j]*bp[0]
268         add     %rax,$hi0
269         mov     ($np,$j,8),%rax
270         adc     \$0,%rdx
271         lea     1($j),$j                # j++
272         mov     %rdx,$lo0
273
274         mulq    $m1                     # np[j]*m1
275         cmp     $num,$j
276         jne     .L1st                   # note that upon exit $j==$num, so
277                                         # they can be used interchangeably
278
279         add     %rax,$hi1
280         adc     \$0,%rdx
281         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
282         adc     \$0,%rdx
283         mov     $hi1,-16(%rsp,$num,8)   # tp[num-1]
284         mov     %rdx,$hi1
285         mov     $lo0,$hi0
286
287         xor     %rdx,%rdx
288         add     $hi0,$hi1
289         adc     \$0,%rdx
290         mov     $hi1,-8(%rsp,$num,8)
291         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
292
293         lea     1($i),$i                # i++
294         jmp     .Louter
295 .align  16
296 .Louter:
297         lea     24+128(%rsp,$num,8),%rdx        # where 256-byte mask is (+size optimization)
298         and     \$-16,%rdx
299         pxor    %xmm4,%xmm4
300         pxor    %xmm5,%xmm5
301 ___
302 for($k=0;$k<$STRIDE/16;$k+=4) {
303 $code.=<<___;
304         movdqa  `16*($k+0)-128`($bp),%xmm0
305         movdqa  `16*($k+1)-128`($bp),%xmm1
306         movdqa  `16*($k+2)-128`($bp),%xmm2
307         movdqa  `16*($k+3)-128`($bp),%xmm3
308         pand    `16*($k+0)-128`(%rdx),%xmm0
309         pand    `16*($k+1)-128`(%rdx),%xmm1
310         por     %xmm0,%xmm4
311         pand    `16*($k+2)-128`(%rdx),%xmm2
312         por     %xmm1,%xmm5
313         pand    `16*($k+3)-128`(%rdx),%xmm3
314         por     %xmm2,%xmm4
315         por     %xmm3,%xmm5
316 ___
317 }
318 $code.=<<___;
319         por     %xmm5,%xmm4
320         pshufd  \$0x4e,%xmm4,%xmm0
321         por     %xmm4,%xmm0
322         lea     $STRIDE($bp),$bp
323
324         mov     ($ap),%rax              # ap[0]
325         movq    %xmm0,$m0               # m0=bp[i]
326
327         xor     $j,$j                   # j=0
328         mov     $n0,$m1
329         mov     (%rsp),$lo0
330
331         mulq    $m0                     # ap[0]*bp[i]
332         add     %rax,$lo0               # ap[0]*bp[i]+tp[0]
333         mov     ($np),%rax
334         adc     \$0,%rdx
335
336         imulq   $lo0,$m1                # tp[0]*n0
337         mov     %rdx,$hi0
338
339         mulq    $m1                     # np[0]*m1
340         add     %rax,$lo0               # discarded
341         mov     8($ap),%rax
342         adc     \$0,%rdx
343         mov     8(%rsp),$lo0            # tp[1]
344         mov     %rdx,$hi1
345
346         lea     1($j),$j                # j++
347         jmp     .Linner_enter
348
349 .align  16
350 .Linner:
351         add     %rax,$hi1
352         mov     ($ap,$j,8),%rax
353         adc     \$0,%rdx
354         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
355         mov     (%rsp,$j,8),$lo0
356         adc     \$0,%rdx
357         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
358         mov     %rdx,$hi1
359
360 .Linner_enter:
361         mulq    $m0                     # ap[j]*bp[i]
362         add     %rax,$hi0
363         mov     ($np,$j,8),%rax
364         adc     \$0,%rdx
365         add     $hi0,$lo0               # ap[j]*bp[i]+tp[j]
366         mov     %rdx,$hi0
367         adc     \$0,$hi0
368         lea     1($j),$j                # j++
369
370         mulq    $m1                     # np[j]*m1
371         cmp     $num,$j
372         jne     .Linner                 # note that upon exit $j==$num, so
373                                         # they can be used interchangeably
374         add     %rax,$hi1
375         adc     \$0,%rdx
376         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
377         mov     (%rsp,$num,8),$lo0
378         adc     \$0,%rdx
379         mov     $hi1,-16(%rsp,$num,8)   # tp[num-1]
380         mov     %rdx,$hi1
381
382         xor     %rdx,%rdx
383         add     $hi0,$hi1
384         adc     \$0,%rdx
385         add     $lo0,$hi1               # pull upmost overflow bit
386         adc     \$0,%rdx
387         mov     $hi1,-8(%rsp,$num,8)
388         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
389
390         lea     1($i),$i                # i++
391         cmp     $num,$i
392         jb      .Louter
393
394         xor     $i,$i                   # i=0 and clear CF!
395         mov     (%rsp),%rax             # tp[0]
396         lea     (%rsp),$ap              # borrow ap for tp
397         mov     $num,$j                 # j=num
398         jmp     .Lsub
399 .align  16
400 .Lsub:  sbb     ($np,$i,8),%rax
401         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[i]
402         mov     8($ap,$i,8),%rax        # tp[i+1]
403         lea     1($i),$i                # i++
404         dec     $j                      # doesnn't affect CF!
405         jnz     .Lsub
406
407         sbb     \$0,%rax                # handle upmost overflow bit
408         xor     $i,$i
409         and     %rax,$ap
410         not     %rax
411         mov     $rp,$np
412         and     %rax,$np
413         mov     $num,$j                 # j=num
414         or      $np,$ap                 # ap=borrow?tp:rp
415 .align  16
416 .Lcopy:                                 # copy or in-place refresh
417         mov     ($ap,$i,8),%rax
418         mov     $i,(%rsp,$i,8)          # zap temporary vector
419         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]
420         lea     1($i),$i
421         sub     \$1,$j
422         jnz     .Lcopy
423
424         mov     8(%rsp,$num,8),%rsi     # restore %rsp
425         mov     \$1,%rax
426
427         mov     -48(%rsi),%r15
428         mov     -40(%rsi),%r14
429         mov     -32(%rsi),%r13
430         mov     -24(%rsi),%r12
431         mov     -16(%rsi),%rbp
432         mov     -8(%rsi),%rbx
433         lea     (%rsi),%rsp
434 .Lmul_epilogue:
435         ret
436 .size   bn_mul_mont_gather5,.-bn_mul_mont_gather5
437 ___
438 {{{
439 my @A=("%r10","%r11");
440 my @N=("%r13","%rdi");
441 $code.=<<___;
442 .type   bn_mul4x_mont_gather5,\@function,6
443 .align  32
444 bn_mul4x_mont_gather5:
445 .Lmul4x_enter:
446 ___
447 $code.=<<___ if ($addx);
448         and     \$0x80108,%r11d
449         cmp     \$0x80108,%r11d         # check for AD*X+BMI2+BMI1
450         je      .Lmulx4x_enter
451 ___
452 $code.=<<___;
453         .byte   0x67
454         mov     %rsp,%rax
455         push    %rbx
456         push    %rbp
457         push    %r12
458         push    %r13
459         push    %r14
460         push    %r15
461
462         .byte   0x67
463         shl     \$3,${num}d             # convert $num to bytes
464         lea     ($num,$num,2),%r10      # 3*$num in bytes
465         neg     $num                    # -$num
466
467         ##############################################################
468         # Ensure that stack frame doesn't alias with $rptr+3*$num
469         # modulo 4096, which covers ret[num], am[num] and n[num]
470         # (see bn_exp.c). This is done to allow memory disambiguation
471         # logic do its magic. [Extra [num] is allocated in order
472         # to align with bn_power5's frame, which is cleansed after
473         # completing exponentiation. Extra 256 bytes is for power mask
474         # calculated from 7th argument, the index.]
475         #
476         lea     -320(%rsp,$num,2),%r11
477         sub     $rp,%r11
478         and     \$4095,%r11
479         cmp     %r11,%r10
480         jb      .Lmul4xsp_alt
481         sub     %r11,%rsp               # align with $rp
482         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*num*8+256)
483         jmp     .Lmul4xsp_done
484
485 .align  32
486 .Lmul4xsp_alt:
487         lea     4096-320(,$num,2),%r10
488         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*num*8+256)
489         sub     %r10,%r11
490         mov     \$0,%r10
491         cmovc   %r10,%r11
492         sub     %r11,%rsp
493 .Lmul4xsp_done:
494         and     \$-64,%rsp
495         mov     %rax,%r11
496         sub     %rsp,%r11
497         and     \$-4096,%r11
498 .Lmul4x_page_walk:
499         mov     (%rsp,%r11),%r10
500         sub     \$4096,%r11
501         .byte   0x2e                    # predict non-taken
502         jnc     .Lmul4x_page_walk
503
504         neg     $num
505
506         mov     %rax,40(%rsp)
507 .Lmul4x_body:
508
509         call    mul4x_internal
510
511         mov     40(%rsp),%rsi           # restore %rsp
512         mov     \$1,%rax
513
514         mov     -48(%rsi),%r15
515         mov     -40(%rsi),%r14
516         mov     -32(%rsi),%r13
517         mov     -24(%rsi),%r12
518         mov     -16(%rsi),%rbp
519         mov     -8(%rsi),%rbx
520         lea     (%rsi),%rsp
521 .Lmul4x_epilogue:
522         ret
523 .size   bn_mul4x_mont_gather5,.-bn_mul4x_mont_gather5
524
525 .type   mul4x_internal,\@abi-omnipotent
526 .align  32
527 mul4x_internal:
528         shl     \$5,$num                # $num was in bytes
529         movd    `($win64?56:8)`(%rax),%xmm5     # load 7th argument, index
530         lea     .Linc(%rip),%rax
531         lea     128(%rdx,$num),%r13     # end of powers table (+size optimization)
532         shr     \$5,$num                # restore $num
533 ___
534                 $bp="%r12";
535                 $STRIDE=2**5*8;         # 5 is "window size"
536                 $N=$STRIDE/4;           # should match cache line size
537                 $tp=$i;
538 $code.=<<___;
539         movdqa  0(%rax),%xmm0           # 00000001000000010000000000000000
540         movdqa  16(%rax),%xmm1          # 00000002000000020000000200000002
541         lea     88-112(%rsp,$num),%r10  # place the mask after tp[num+1] (+ICache optimization)
542         lea     128(%rdx),$bp           # size optimization
543
544         pshufd  \$0,%xmm5,%xmm5         # broadcast index
545         movdqa  %xmm1,%xmm4
546         .byte   0x67,0x67
547         movdqa  %xmm1,%xmm2
548 ___
549 ########################################################################
550 # calculate mask by comparing 0..31 to index and save result to stack
551 #
552 $code.=<<___;
553         paddd   %xmm0,%xmm1
554         pcmpeqd %xmm5,%xmm0             # compare to 1,0
555         .byte   0x67
556         movdqa  %xmm4,%xmm3
557 ___
558 for($i=0;$i<$STRIDE/16-4;$i+=4) {
559 $code.=<<___;
560         paddd   %xmm1,%xmm2
561         pcmpeqd %xmm5,%xmm1             # compare to 3,2
562         movdqa  %xmm0,`16*($i+0)+112`(%r10)
563         movdqa  %xmm4,%xmm0
564
565         paddd   %xmm2,%xmm3
566         pcmpeqd %xmm5,%xmm2             # compare to 5,4
567         movdqa  %xmm1,`16*($i+1)+112`(%r10)
568         movdqa  %xmm4,%xmm1
569
570         paddd   %xmm3,%xmm0
571         pcmpeqd %xmm5,%xmm3             # compare to 7,6
572         movdqa  %xmm2,`16*($i+2)+112`(%r10)
573         movdqa  %xmm4,%xmm2
574
575         paddd   %xmm0,%xmm1
576         pcmpeqd %xmm5,%xmm0
577         movdqa  %xmm3,`16*($i+3)+112`(%r10)
578         movdqa  %xmm4,%xmm3
579 ___
580 }
581 $code.=<<___;                           # last iteration can be optimized
582         paddd   %xmm1,%xmm2
583         pcmpeqd %xmm5,%xmm1
584         movdqa  %xmm0,`16*($i+0)+112`(%r10)
585
586         paddd   %xmm2,%xmm3
587         .byte   0x67
588         pcmpeqd %xmm5,%xmm2
589         movdqa  %xmm1,`16*($i+1)+112`(%r10)
590
591         pcmpeqd %xmm5,%xmm3
592         movdqa  %xmm2,`16*($i+2)+112`(%r10)
593         pand    `16*($i+0)-128`($bp),%xmm0      # while it's still in register
594
595         pand    `16*($i+1)-128`($bp),%xmm1
596         pand    `16*($i+2)-128`($bp),%xmm2
597         movdqa  %xmm3,`16*($i+3)+112`(%r10)
598         pand    `16*($i+3)-128`($bp),%xmm3
599         por     %xmm2,%xmm0
600         por     %xmm3,%xmm1
601 ___
602 for($i=0;$i<$STRIDE/16-4;$i+=4) {
603 $code.=<<___;
604         movdqa  `16*($i+0)-128`($bp),%xmm4
605         movdqa  `16*($i+1)-128`($bp),%xmm5
606         movdqa  `16*($i+2)-128`($bp),%xmm2
607         pand    `16*($i+0)+112`(%r10),%xmm4
608         movdqa  `16*($i+3)-128`($bp),%xmm3
609         pand    `16*($i+1)+112`(%r10),%xmm5
610         por     %xmm4,%xmm0
611         pand    `16*($i+2)+112`(%r10),%xmm2
612         por     %xmm5,%xmm1
613         pand    `16*($i+3)+112`(%r10),%xmm3
614         por     %xmm2,%xmm0
615         por     %xmm3,%xmm1
616 ___
617 }
618 $code.=<<___;
619         por     %xmm1,%xmm0
620         pshufd  \$0x4e,%xmm0,%xmm1
621         por     %xmm1,%xmm0
622         lea     $STRIDE($bp),$bp
623         movq    %xmm0,$m0               # m0=bp[0]
624
625         mov     %r13,16+8(%rsp)         # save end of b[num]
626         mov     $rp, 56+8(%rsp)         # save $rp
627
628         mov     ($n0),$n0               # pull n0[0] value
629         mov     ($ap),%rax
630         lea     ($ap,$num),$ap          # end of a[num]
631         neg     $num
632
633         mov     $n0,$m1
634         mulq    $m0                     # ap[0]*bp[0]
635         mov     %rax,$A[0]
636         mov     ($np),%rax
637
638         imulq   $A[0],$m1               # "tp[0]"*n0
639         lea     64+8(%rsp),$tp
640         mov     %rdx,$A[1]
641
642         mulq    $m1                     # np[0]*m1
643         add     %rax,$A[0]              # discarded
644         mov     8($ap,$num),%rax
645         adc     \$0,%rdx
646         mov     %rdx,$N[1]
647
648         mulq    $m0
649         add     %rax,$A[1]
650         mov     8*1($np),%rax
651         adc     \$0,%rdx
652         mov     %rdx,$A[0]
653
654         mulq    $m1
655         add     %rax,$N[1]
656         mov     16($ap,$num),%rax
657         adc     \$0,%rdx
658         add     $A[1],$N[1]
659         lea     4*8($num),$j            # j=4
660         lea     8*4($np),$np
661         adc     \$0,%rdx
662         mov     $N[1],($tp)
663         mov     %rdx,$N[0]
664         jmp     .L1st4x
665
666 .align  32
667 .L1st4x:
668         mulq    $m0                     # ap[j]*bp[0]
669         add     %rax,$A[0]
670         mov     -8*2($np),%rax
671         lea     32($tp),$tp
672         adc     \$0,%rdx
673         mov     %rdx,$A[1]
674
675         mulq    $m1                     # np[j]*m1
676         add     %rax,$N[0]
677         mov     -8($ap,$j),%rax
678         adc     \$0,%rdx
679         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
680         adc     \$0,%rdx
681         mov     $N[0],-24($tp)          # tp[j-1]
682         mov     %rdx,$N[1]
683
684         mulq    $m0                     # ap[j]*bp[0]
685         add     %rax,$A[1]
686         mov     -8*1($np),%rax
687         adc     \$0,%rdx
688         mov     %rdx,$A[0]
689
690         mulq    $m1                     # np[j]*m1
691         add     %rax,$N[1]
692         mov     ($ap,$j),%rax
693         adc     \$0,%rdx
694         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
695         adc     \$0,%rdx
696         mov     $N[1],-16($tp)          # tp[j-1]
697         mov     %rdx,$N[0]
698
699         mulq    $m0                     # ap[j]*bp[0]
700         add     %rax,$A[0]
701         mov     8*0($np),%rax
702         adc     \$0,%rdx
703         mov     %rdx,$A[1]
704
705         mulq    $m1                     # np[j]*m1
706         add     %rax,$N[0]
707         mov     8($ap,$j),%rax
708         adc     \$0,%rdx
709         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
710         adc     \$0,%rdx
711         mov     $N[0],-8($tp)           # tp[j-1]
712         mov     %rdx,$N[1]
713
714         mulq    $m0                     # ap[j]*bp[0]
715         add     %rax,$A[1]
716         mov     8*1($np),%rax
717         adc     \$0,%rdx
718         mov     %rdx,$A[0]
719
720         mulq    $m1                     # np[j]*m1
721         add     %rax,$N[1]
722         mov     16($ap,$j),%rax
723         adc     \$0,%rdx
724         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
725         lea     8*4($np),$np
726         adc     \$0,%rdx
727         mov     $N[1],($tp)             # tp[j-1]
728         mov     %rdx,$N[0]
729
730         add     \$32,$j                 # j+=4
731         jnz     .L1st4x
732
733         mulq    $m0                     # ap[j]*bp[0]
734         add     %rax,$A[0]
735         mov     -8*2($np),%rax
736         lea     32($tp),$tp
737         adc     \$0,%rdx
738         mov     %rdx,$A[1]
739
740         mulq    $m1                     # np[j]*m1
741         add     %rax,$N[0]
742         mov     -8($ap),%rax
743         adc     \$0,%rdx
744         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
745         adc     \$0,%rdx
746         mov     $N[0],-24($tp)          # tp[j-1]
747         mov     %rdx,$N[1]
748
749         mulq    $m0                     # ap[j]*bp[0]
750         add     %rax,$A[1]
751         mov     -8*1($np),%rax
752         adc     \$0,%rdx
753         mov     %rdx,$A[0]
754
755         mulq    $m1                     # np[j]*m1
756         add     %rax,$N[1]
757         mov     ($ap,$num),%rax         # ap[0]
758         adc     \$0,%rdx
759         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
760         adc     \$0,%rdx
761         mov     $N[1],-16($tp)          # tp[j-1]
762         mov     %rdx,$N[0]
763
764         lea     ($np,$num),$np          # rewind $np
765
766         xor     $N[1],$N[1]
767         add     $A[0],$N[0]
768         adc     \$0,$N[1]
769         mov     $N[0],-8($tp)
770
771         jmp     .Louter4x
772
773 .align  32
774 .Louter4x:
775         lea     16+128($tp),%rdx        # where 256-byte mask is (+size optimization)
776         pxor    %xmm4,%xmm4
777         pxor    %xmm5,%xmm5
778 ___
779 for($i=0;$i<$STRIDE/16;$i+=4) {
780 $code.=<<___;
781         movdqa  `16*($i+0)-128`($bp),%xmm0
782         movdqa  `16*($i+1)-128`($bp),%xmm1
783         movdqa  `16*($i+2)-128`($bp),%xmm2
784         movdqa  `16*($i+3)-128`($bp),%xmm3
785         pand    `16*($i+0)-128`(%rdx),%xmm0
786         pand    `16*($i+1)-128`(%rdx),%xmm1
787         por     %xmm0,%xmm4
788         pand    `16*($i+2)-128`(%rdx),%xmm2
789         por     %xmm1,%xmm5
790         pand    `16*($i+3)-128`(%rdx),%xmm3
791         por     %xmm2,%xmm4
792         por     %xmm3,%xmm5
793 ___
794 }
795 $code.=<<___;
796         por     %xmm5,%xmm4
797         pshufd  \$0x4e,%xmm4,%xmm0
798         por     %xmm4,%xmm0
799         lea     $STRIDE($bp),$bp
800         movq    %xmm0,$m0               # m0=bp[i]
801
802         mov     ($tp,$num),$A[0]
803         mov     $n0,$m1
804         mulq    $m0                     # ap[0]*bp[i]
805         add     %rax,$A[0]              # ap[0]*bp[i]+tp[0]
806         mov     ($np),%rax
807         adc     \$0,%rdx
808
809         imulq   $A[0],$m1               # tp[0]*n0
810         mov     %rdx,$A[1]
811         mov     $N[1],($tp)             # store upmost overflow bit
812
813         lea     ($tp,$num),$tp          # rewind $tp
814
815         mulq    $m1                     # np[0]*m1
816         add     %rax,$A[0]              # "$N[0]", discarded
817         mov     8($ap,$num),%rax
818         adc     \$0,%rdx
819         mov     %rdx,$N[1]
820
821         mulq    $m0                     # ap[j]*bp[i]
822         add     %rax,$A[1]
823         mov     8*1($np),%rax
824         adc     \$0,%rdx
825         add     8($tp),$A[1]            # +tp[1]
826         adc     \$0,%rdx
827         mov     %rdx,$A[0]
828
829         mulq    $m1                     # np[j]*m1
830         add     %rax,$N[1]
831         mov     16($ap,$num),%rax
832         adc     \$0,%rdx
833         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[i]+tp[j]
834         lea     4*8($num),$j            # j=4
835         lea     8*4($np),$np
836         adc     \$0,%rdx
837         mov     %rdx,$N[0]
838         jmp     .Linner4x
839
840 .align  32
841 .Linner4x:
842         mulq    $m0                     # ap[j]*bp[i]
843         add     %rax,$A[0]
844         mov     -8*2($np),%rax
845         adc     \$0,%rdx
846         add     16($tp),$A[0]           # ap[j]*bp[i]+tp[j]
847         lea     32($tp),$tp
848         adc     \$0,%rdx
849         mov     %rdx,$A[1]
850
851         mulq    $m1                     # np[j]*m1
852         add     %rax,$N[0]
853         mov     -8($ap,$j),%rax
854         adc     \$0,%rdx
855         add     $A[0],$N[0]
856         adc     \$0,%rdx
857         mov     $N[1],-32($tp)          # tp[j-1]
858         mov     %rdx,$N[1]
859
860         mulq    $m0                     # ap[j]*bp[i]
861         add     %rax,$A[1]
862         mov     -8*1($np),%rax
863         adc     \$0,%rdx
864         add     -8($tp),$A[1]
865         adc     \$0,%rdx
866         mov     %rdx,$A[0]
867
868         mulq    $m1                     # np[j]*m1
869         add     %rax,$N[1]
870         mov     ($ap,$j),%rax
871         adc     \$0,%rdx
872         add     $A[1],$N[1]
873         adc     \$0,%rdx
874         mov     $N[0],-24($tp)          # tp[j-1]
875         mov     %rdx,$N[0]
876
877         mulq    $m0                     # ap[j]*bp[i]
878         add     %rax,$A[0]
879         mov     8*0($np),%rax
880         adc     \$0,%rdx
881         add     ($tp),$A[0]             # ap[j]*bp[i]+tp[j]
882         adc     \$0,%rdx
883         mov     %rdx,$A[1]
884
885         mulq    $m1                     # np[j]*m1
886         add     %rax,$N[0]
887         mov     8($ap,$j),%rax
888         adc     \$0,%rdx
889         add     $A[0],$N[0]
890         adc     \$0,%rdx
891         mov     $N[1],-16($tp)          # tp[j-1]
892         mov     %rdx,$N[1]
893
894         mulq    $m0                     # ap[j]*bp[i]
895         add     %rax,$A[1]
896         mov     8*1($np),%rax
897         adc     \$0,%rdx
898         add     8($tp),$A[1]
899         adc     \$0,%rdx
900         mov     %rdx,$A[0]
901
902         mulq    $m1                     # np[j]*m1
903         add     %rax,$N[1]
904         mov     16($ap,$j),%rax
905         adc     \$0,%rdx
906         add     $A[1],$N[1]
907         lea     8*4($np),$np
908         adc     \$0,%rdx
909         mov     $N[0],-8($tp)           # tp[j-1]
910         mov     %rdx,$N[0]
911
912         add     \$32,$j                 # j+=4
913         jnz     .Linner4x
914
915         mulq    $m0                     # ap[j]*bp[i]
916         add     %rax,$A[0]
917         mov     -8*2($np),%rax
918         adc     \$0,%rdx
919         add     16($tp),$A[0]           # ap[j]*bp[i]+tp[j]
920         lea     32($tp),$tp
921         adc     \$0,%rdx
922         mov     %rdx,$A[1]
923
924         mulq    $m1                     # np[j]*m1
925         add     %rax,$N[0]
926         mov     -8($ap),%rax
927         adc     \$0,%rdx
928         add     $A[0],$N[0]
929         adc     \$0,%rdx
930         mov     $N[1],-32($tp)          # tp[j-1]
931         mov     %rdx,$N[1]
932
933         mulq    $m0                     # ap[j]*bp[i]
934         add     %rax,$A[1]
935         mov     $m1,%rax
936         mov     -8*1($np),$m1
937         adc     \$0,%rdx
938         add     -8($tp),$A[1]
939         adc     \$0,%rdx
940         mov     %rdx,$A[0]
941
942         mulq    $m1                     # np[j]*m1
943         add     %rax,$N[1]
944         mov     ($ap,$num),%rax         # ap[0]
945         adc     \$0,%rdx
946         add     $A[1],$N[1]
947         adc     \$0,%rdx
948         mov     $N[0],-24($tp)          # tp[j-1]
949         mov     %rdx,$N[0]
950
951         mov     $N[1],-16($tp)          # tp[j-1]
952         lea     ($np,$num),$np          # rewind $np
953
954         xor     $N[1],$N[1]
955         add     $A[0],$N[0]
956         adc     \$0,$N[1]
957         add     ($tp),$N[0]             # pull upmost overflow bit
958         adc     \$0,$N[1]               # upmost overflow bit
959         mov     $N[0],-8($tp)
960
961         cmp     16+8(%rsp),$bp
962         jb      .Louter4x
963 ___
964 if (1) {
965 $code.=<<___;
966         xor     %rax,%rax
967         sub     $N[0],$m1               # compare top-most words
968         adc     $j,$j                   # $j is zero
969         or      $j,$N[1]
970         sub     $N[1],%rax              # %rax=-$N[1]
971         lea     ($tp,$num),%rbx         # tptr in .sqr4x_sub
972         mov     ($np),%r12
973         lea     ($np),%rbp              # nptr in .sqr4x_sub
974         mov     %r9,%rcx
975         sar     \$3+2,%rcx
976         mov     56+8(%rsp),%rdi         # rptr in .sqr4x_sub
977         dec     %r12                    # so that after 'not' we get -n[0]
978         xor     %r10,%r10
979         mov     8*1(%rbp),%r13
980         mov     8*2(%rbp),%r14
981         mov     8*3(%rbp),%r15
982         jmp     .Lsqr4x_sub_entry
983 ___
984 } else {
985 my @ri=("%rax",$bp,$m0,$m1);
986 my $rp="%rdx";
987 $code.=<<___
988         xor     \$1,$N[1]
989         lea     ($tp,$num),$tp          # rewind $tp
990         sar     \$5,$num                # cf=0
991         lea     ($np,$N[1],8),$np
992         mov     56+8(%rsp),$rp          # restore $rp
993         jmp     .Lsub4x
994
995 .align  32
996 .Lsub4x:
997         .byte   0x66
998         mov     8*0($tp),@ri[0]
999         mov     8*1($tp),@ri[1]
1000         .byte   0x66
1001         sbb     16*0($np),@ri[0]
1002         mov     8*2($tp),@ri[2]
1003         sbb     16*1($np),@ri[1]
1004         mov     3*8($tp),@ri[3]
1005         lea     4*8($tp),$tp
1006         sbb     16*2($np),@ri[2]
1007         mov     @ri[0],8*0($rp)
1008         sbb     16*3($np),@ri[3]
1009         lea     16*4($np),$np
1010         mov     @ri[1],8*1($rp)
1011         mov     @ri[2],8*2($rp)
1012         mov     @ri[3],8*3($rp)
1013         lea     8*4($rp),$rp
1014
1015         inc     $num
1016         jnz     .Lsub4x
1017
1018         ret
1019 ___
1020 }
1021 $code.=<<___;
1022 .size   mul4x_internal,.-mul4x_internal
1023 ___
1024 }}}
1025 \f{{{
1026 ######################################################################
1027 # void bn_power5(
1028 my $rptr="%rdi";        # BN_ULONG *rptr,
1029 my $aptr="%rsi";        # const BN_ULONG *aptr,
1030 my $bptr="%rdx";        # const void *table,
1031 my $nptr="%rcx";        # const BN_ULONG *nptr,
1032 my $n0  ="%r8";         # const BN_ULONG *n0);
1033 my $num ="%r9";         # int num, has to be divisible by 8
1034                         # int pwr 
1035
1036 my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
1037 my @A0=("%r10","%r11");
1038 my @A1=("%r12","%r13");
1039 my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
1040
1041 $code.=<<___;
1042 .globl  bn_power5
1043 .type   bn_power5,\@function,6
1044 .align  32
1045 bn_power5:
1046 ___
1047 $code.=<<___ if ($addx);
1048         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
1049         and     \$0x80108,%r11d
1050         cmp     \$0x80108,%r11d         # check for AD*X+BMI2+BMI1
1051         je      .Lpowerx5_enter
1052 ___
1053 $code.=<<___;
1054         mov     %rsp,%rax
1055         push    %rbx
1056         push    %rbp
1057         push    %r12
1058         push    %r13
1059         push    %r14
1060         push    %r15
1061
1062         shl     \$3,${num}d             # convert $num to bytes
1063         lea     ($num,$num,2),%r10d     # 3*$num
1064         neg     $num
1065         mov     ($n0),$n0               # *n0
1066
1067         ##############################################################
1068         # Ensure that stack frame doesn't alias with $rptr+3*$num
1069         # modulo 4096, which covers ret[num], am[num] and n[num]
1070         # (see bn_exp.c). This is done to allow memory disambiguation
1071         # logic do its magic. [Extra 256 bytes is for power mask
1072         # calculated from 7th argument, the index.]
1073         #
1074         lea     -320(%rsp,$num,2),%r11
1075         sub     $rptr,%r11
1076         and     \$4095,%r11
1077         cmp     %r11,%r10
1078         jb      .Lpwr_sp_alt
1079         sub     %r11,%rsp               # align with $aptr
1080         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*num*8+256)
1081         jmp     .Lpwr_sp_done
1082
1083 .align  32
1084 .Lpwr_sp_alt:
1085         lea     4096-320(,$num,2),%r10
1086         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*num*8+256)
1087         sub     %r10,%r11
1088         mov     \$0,%r10
1089         cmovc   %r10,%r11
1090         sub     %r11,%rsp
1091 .Lpwr_sp_done:
1092         and     \$-64,%rsp
1093         mov     %rax,%r11
1094         sub     %rsp,%r11
1095         and     \$-4096,%r11
1096 .Lpwr_page_walk:
1097         mov     (%rsp,%r11),%r10
1098         sub     \$4096,%r11
1099         .byte   0x2e                    # predict non-taken
1100         jnc     .Lpwr_page_walk
1101
1102         mov     $num,%r10       
1103         neg     $num
1104
1105         ##############################################################
1106         # Stack layout
1107         #
1108         # +0    saved $num, used in reduction section
1109         # +8    &t[2*$num], used in reduction section
1110         # +32   saved *n0
1111         # +40   saved %rsp
1112         # +48   t[2*$num]
1113         #
1114         mov     $n0,  32(%rsp)
1115         mov     %rax, 40(%rsp)          # save original %rsp
1116 .Lpower5_body:
1117         movq    $rptr,%xmm1             # save $rptr, used in sqr8x
1118         movq    $nptr,%xmm2             # save $nptr
1119         movq    %r10, %xmm3             # -$num, used in sqr8x
1120         movq    $bptr,%xmm4
1121
1122         call    __bn_sqr8x_internal
1123         call    __bn_post4x_internal
1124         call    __bn_sqr8x_internal
1125         call    __bn_post4x_internal
1126         call    __bn_sqr8x_internal
1127         call    __bn_post4x_internal
1128         call    __bn_sqr8x_internal
1129         call    __bn_post4x_internal
1130         call    __bn_sqr8x_internal
1131         call    __bn_post4x_internal
1132
1133         movq    %xmm2,$nptr
1134         movq    %xmm4,$bptr
1135         mov     $aptr,$rptr
1136         mov     40(%rsp),%rax
1137         lea     32(%rsp),$n0
1138
1139         call    mul4x_internal
1140
1141         mov     40(%rsp),%rsi           # restore %rsp
1142         mov     \$1,%rax
1143         mov     -48(%rsi),%r15
1144         mov     -40(%rsi),%r14
1145         mov     -32(%rsi),%r13
1146         mov     -24(%rsi),%r12
1147         mov     -16(%rsi),%rbp
1148         mov     -8(%rsi),%rbx
1149         lea     (%rsi),%rsp
1150 .Lpower5_epilogue:
1151         ret
1152 .size   bn_power5,.-bn_power5
1153
1154 .globl  bn_sqr8x_internal
1155 .hidden bn_sqr8x_internal
1156 .type   bn_sqr8x_internal,\@abi-omnipotent
1157 .align  32
1158 bn_sqr8x_internal:
1159 __bn_sqr8x_internal:
1160         ##############################################################
1161         # Squaring part:
1162         #
1163         # a) multiply-n-add everything but a[i]*a[i];
1164         # b) shift result of a) by 1 to the left and accumulate
1165         #    a[i]*a[i] products;
1166         #
1167         ##############################################################
1168         #                                                     a[1]a[0]
1169         #                                                 a[2]a[0]
1170         #                                             a[3]a[0]
1171         #                                             a[2]a[1]
1172         #                                         a[4]a[0]
1173         #                                         a[3]a[1]
1174         #                                     a[5]a[0]
1175         #                                     a[4]a[1]
1176         #                                     a[3]a[2]
1177         #                                 a[6]a[0]
1178         #                                 a[5]a[1]
1179         #                                 a[4]a[2]
1180         #                             a[7]a[0]
1181         #                             a[6]a[1]
1182         #                             a[5]a[2]
1183         #                             a[4]a[3]
1184         #                         a[7]a[1]
1185         #                         a[6]a[2]
1186         #                         a[5]a[3]
1187         #                     a[7]a[2]
1188         #                     a[6]a[3]
1189         #                     a[5]a[4]
1190         #                 a[7]a[3]
1191         #                 a[6]a[4]
1192         #             a[7]a[4]
1193         #             a[6]a[5]
1194         #         a[7]a[5]
1195         #     a[7]a[6]
1196         #                                                     a[1]a[0]
1197         #                                                 a[2]a[0]
1198         #                                             a[3]a[0]
1199         #                                         a[4]a[0]
1200         #                                     a[5]a[0]
1201         #                                 a[6]a[0]
1202         #                             a[7]a[0]
1203         #                                             a[2]a[1]
1204         #                                         a[3]a[1]
1205         #                                     a[4]a[1]
1206         #                                 a[5]a[1]
1207         #                             a[6]a[1]
1208         #                         a[7]a[1]
1209         #                                     a[3]a[2]
1210         #                                 a[4]a[2]
1211         #                             a[5]a[2]
1212         #                         a[6]a[2]
1213         #                     a[7]a[2]
1214         #                             a[4]a[3]
1215         #                         a[5]a[3]
1216         #                     a[6]a[3]
1217         #                 a[7]a[3]
1218         #                     a[5]a[4]
1219         #                 a[6]a[4]
1220         #             a[7]a[4]
1221         #             a[6]a[5]
1222         #         a[7]a[5]
1223         #     a[7]a[6]
1224         #                                                         a[0]a[0]
1225         #                                                 a[1]a[1]
1226         #                                         a[2]a[2]
1227         #                                 a[3]a[3]
1228         #                         a[4]a[4]
1229         #                 a[5]a[5]
1230         #         a[6]a[6]
1231         # a[7]a[7]
1232
1233         lea     32(%r10),$i             # $i=-($num-32)
1234         lea     ($aptr,$num),$aptr      # end of a[] buffer, ($aptr,$i)=&ap[2]
1235
1236         mov     $num,$j                 # $j=$num
1237
1238                                         # comments apply to $num==8 case
1239         mov     -32($aptr,$i),$a0       # a[0]
1240         lea     48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
1241         mov     -24($aptr,$i),%rax      # a[1]
1242         lea     -32($tptr,$i),$tptr     # end of tp[] window, &tp[2*$num-"$i"]
1243         mov     -16($aptr,$i),$ai       # a[2]
1244         mov     %rax,$a1
1245
1246         mul     $a0                     # a[1]*a[0]
1247         mov     %rax,$A0[0]             # a[1]*a[0]
1248          mov    $ai,%rax                # a[2]
1249         mov     %rdx,$A0[1]
1250         mov     $A0[0],-24($tptr,$i)    # t[1]
1251
1252         mul     $a0                     # a[2]*a[0]
1253         add     %rax,$A0[1]
1254          mov    $ai,%rax
1255         adc     \$0,%rdx
1256         mov     $A0[1],-16($tptr,$i)    # t[2]
1257         mov     %rdx,$A0[0]
1258
1259
1260          mov    -8($aptr,$i),$ai        # a[3]
1261         mul     $a1                     # a[2]*a[1]
1262         mov     %rax,$A1[0]             # a[2]*a[1]+t[3]
1263          mov    $ai,%rax
1264         mov     %rdx,$A1[1]
1265
1266          lea    ($i),$j
1267         mul     $a0                     # a[3]*a[0]
1268         add     %rax,$A0[0]             # a[3]*a[0]+a[2]*a[1]+t[3]
1269          mov    $ai,%rax
1270         mov     %rdx,$A0[1]
1271         adc     \$0,$A0[1]
1272         add     $A1[0],$A0[0]
1273         adc     \$0,$A0[1]
1274         mov     $A0[0],-8($tptr,$j)     # t[3]
1275         jmp     .Lsqr4x_1st
1276
1277 .align  32
1278 .Lsqr4x_1st:
1279          mov    ($aptr,$j),$ai          # a[4]
1280         mul     $a1                     # a[3]*a[1]
1281         add     %rax,$A1[1]             # a[3]*a[1]+t[4]
1282          mov    $ai,%rax
1283         mov     %rdx,$A1[0]
1284         adc     \$0,$A1[0]
1285
1286         mul     $a0                     # a[4]*a[0]
1287         add     %rax,$A0[1]             # a[4]*a[0]+a[3]*a[1]+t[4]
1288          mov    $ai,%rax                # a[3]
1289          mov    8($aptr,$j),$ai         # a[5]
1290         mov     %rdx,$A0[0]
1291         adc     \$0,$A0[0]
1292         add     $A1[1],$A0[1]
1293         adc     \$0,$A0[0]
1294
1295
1296         mul     $a1                     # a[4]*a[3]
1297         add     %rax,$A1[0]             # a[4]*a[3]+t[5]
1298          mov    $ai,%rax
1299          mov    $A0[1],($tptr,$j)       # t[4]
1300         mov     %rdx,$A1[1]
1301         adc     \$0,$A1[1]
1302
1303         mul     $a0                     # a[5]*a[2]
1304         add     %rax,$A0[0]             # a[5]*a[2]+a[4]*a[3]+t[5]
1305          mov    $ai,%rax
1306          mov    16($aptr,$j),$ai        # a[6]
1307         mov     %rdx,$A0[1]
1308         adc     \$0,$A0[1]
1309         add     $A1[0],$A0[0]
1310         adc     \$0,$A0[1]
1311
1312         mul     $a1                     # a[5]*a[3]
1313         add     %rax,$A1[1]             # a[5]*a[3]+t[6]
1314          mov    $ai,%rax
1315          mov    $A0[0],8($tptr,$j)      # t[5]
1316         mov     %rdx,$A1[0]
1317         adc     \$0,$A1[0]
1318
1319         mul     $a0                     # a[6]*a[2]
1320         add     %rax,$A0[1]             # a[6]*a[2]+a[5]*a[3]+t[6]
1321          mov    $ai,%rax                # a[3]
1322          mov    24($aptr,$j),$ai        # a[7]
1323         mov     %rdx,$A0[0]
1324         adc     \$0,$A0[0]
1325         add     $A1[1],$A0[1]
1326         adc     \$0,$A0[0]
1327
1328
1329         mul     $a1                     # a[6]*a[5]
1330         add     %rax,$A1[0]             # a[6]*a[5]+t[7]
1331          mov    $ai,%rax
1332          mov    $A0[1],16($tptr,$j)     # t[6]
1333         mov     %rdx,$A1[1]
1334         adc     \$0,$A1[1]
1335          lea    32($j),$j
1336
1337         mul     $a0                     # a[7]*a[4]
1338         add     %rax,$A0[0]             # a[7]*a[4]+a[6]*a[5]+t[6]
1339          mov    $ai,%rax
1340         mov     %rdx,$A0[1]
1341         adc     \$0,$A0[1]
1342         add     $A1[0],$A0[0]
1343         adc     \$0,$A0[1]
1344         mov     $A0[0],-8($tptr,$j)     # t[7]
1345
1346         cmp     \$0,$j
1347         jne     .Lsqr4x_1st
1348
1349         mul     $a1                     # a[7]*a[5]
1350         add     %rax,$A1[1]
1351         lea     16($i),$i
1352         adc     \$0,%rdx
1353         add     $A0[1],$A1[1]
1354         adc     \$0,%rdx
1355
1356         mov     $A1[1],($tptr)          # t[8]
1357         mov     %rdx,$A1[0]
1358         mov     %rdx,8($tptr)           # t[9]
1359         jmp     .Lsqr4x_outer
1360
1361 .align  32
1362 .Lsqr4x_outer:                          # comments apply to $num==6 case
1363         mov     -32($aptr,$i),$a0       # a[0]
1364         lea     48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
1365         mov     -24($aptr,$i),%rax      # a[1]
1366         lea     -32($tptr,$i),$tptr     # end of tp[] window, &tp[2*$num-"$i"]
1367         mov     -16($aptr,$i),$ai       # a[2]
1368         mov     %rax,$a1
1369
1370         mul     $a0                     # a[1]*a[0]
1371         mov     -24($tptr,$i),$A0[0]    # t[1]
1372         add     %rax,$A0[0]             # a[1]*a[0]+t[1]
1373          mov    $ai,%rax                # a[2]
1374         adc     \$0,%rdx
1375         mov     $A0[0],-24($tptr,$i)    # t[1]
1376         mov     %rdx,$A0[1]
1377
1378         mul     $a0                     # a[2]*a[0]
1379         add     %rax,$A0[1]
1380          mov    $ai,%rax
1381         adc     \$0,%rdx
1382         add     -16($tptr,$i),$A0[1]    # a[2]*a[0]+t[2]
1383         mov     %rdx,$A0[0]
1384         adc     \$0,$A0[0]
1385         mov     $A0[1],-16($tptr,$i)    # t[2]
1386
1387         xor     $A1[0],$A1[0]
1388
1389          mov    -8($aptr,$i),$ai        # a[3]
1390         mul     $a1                     # a[2]*a[1]
1391         add     %rax,$A1[0]             # a[2]*a[1]+t[3]
1392          mov    $ai,%rax
1393         adc     \$0,%rdx
1394         add     -8($tptr,$i),$A1[0]
1395         mov     %rdx,$A1[1]
1396         adc     \$0,$A1[1]
1397
1398         mul     $a0                     # a[3]*a[0]
1399         add     %rax,$A0[0]             # a[3]*a[0]+a[2]*a[1]+t[3]
1400          mov    $ai,%rax
1401         adc     \$0,%rdx
1402         add     $A1[0],$A0[0]
1403         mov     %rdx,$A0[1]
1404         adc     \$0,$A0[1]
1405         mov     $A0[0],-8($tptr,$i)     # t[3]
1406
1407         lea     ($i),$j
1408         jmp     .Lsqr4x_inner
1409
1410 .align  32
1411 .Lsqr4x_inner:
1412          mov    ($aptr,$j),$ai          # a[4]
1413         mul     $a1                     # a[3]*a[1]
1414         add     %rax,$A1[1]             # a[3]*a[1]+t[4]
1415          mov    $ai,%rax
1416         mov     %rdx,$A1[0]
1417         adc     \$0,$A1[0]
1418         add     ($tptr,$j),$A1[1]
1419         adc     \$0,$A1[0]
1420
1421         .byte   0x67
1422         mul     $a0                     # a[4]*a[0]
1423         add     %rax,$A0[1]             # a[4]*a[0]+a[3]*a[1]+t[4]
1424          mov    $ai,%rax                # a[3]
1425          mov    8($aptr,$j),$ai         # a[5]
1426         mov     %rdx,$A0[0]
1427         adc     \$0,$A0[0]
1428         add     $A1[1],$A0[1]
1429         adc     \$0,$A0[0]
1430
1431         mul     $a1                     # a[4]*a[3]
1432         add     %rax,$A1[0]             # a[4]*a[3]+t[5]
1433         mov     $A0[1],($tptr,$j)       # t[4]
1434          mov    $ai,%rax
1435         mov     %rdx,$A1[1]
1436         adc     \$0,$A1[1]
1437         add     8($tptr,$j),$A1[0]
1438         lea     16($j),$j               # j++
1439         adc     \$0,$A1[1]
1440
1441         mul     $a0                     # a[5]*a[2]
1442         add     %rax,$A0[0]             # a[5]*a[2]+a[4]*a[3]+t[5]
1443          mov    $ai,%rax
1444         adc     \$0,%rdx
1445         add     $A1[0],$A0[0]
1446         mov     %rdx,$A0[1]
1447         adc     \$0,$A0[1]
1448         mov     $A0[0],-8($tptr,$j)     # t[5], "preloaded t[1]" below
1449
1450         cmp     \$0,$j
1451         jne     .Lsqr4x_inner
1452
1453         .byte   0x67
1454         mul     $a1                     # a[5]*a[3]
1455         add     %rax,$A1[1]
1456         adc     \$0,%rdx
1457         add     $A0[1],$A1[1]
1458         adc     \$0,%rdx
1459
1460         mov     $A1[1],($tptr)          # t[6], "preloaded t[2]" below
1461         mov     %rdx,$A1[0]
1462         mov     %rdx,8($tptr)           # t[7], "preloaded t[3]" below
1463
1464         add     \$16,$i
1465         jnz     .Lsqr4x_outer
1466
1467                                         # comments apply to $num==4 case
1468         mov     -32($aptr),$a0          # a[0]
1469         lea     48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
1470         mov     -24($aptr),%rax         # a[1]
1471         lea     -32($tptr,$i),$tptr     # end of tp[] window, &tp[2*$num-"$i"]
1472         mov     -16($aptr),$ai          # a[2]
1473         mov     %rax,$a1
1474
1475         mul     $a0                     # a[1]*a[0]
1476         add     %rax,$A0[0]             # a[1]*a[0]+t[1], preloaded t[1]
1477          mov    $ai,%rax                # a[2]
1478         mov     %rdx,$A0[1]
1479         adc     \$0,$A0[1]
1480
1481         mul     $a0                     # a[2]*a[0]
1482         add     %rax,$A0[1]
1483          mov    $ai,%rax
1484          mov    $A0[0],-24($tptr)       # t[1]
1485         mov     %rdx,$A0[0]
1486         adc     \$0,$A0[0]
1487         add     $A1[1],$A0[1]           # a[2]*a[0]+t[2], preloaded t[2]
1488          mov    -8($aptr),$ai           # a[3]
1489         adc     \$0,$A0[0]
1490
1491         mul     $a1                     # a[2]*a[1]
1492         add     %rax,$A1[0]             # a[2]*a[1]+t[3], preloaded t[3]
1493          mov    $ai,%rax
1494          mov    $A0[1],-16($tptr)       # t[2]
1495         mov     %rdx,$A1[1]
1496         adc     \$0,$A1[1]
1497
1498         mul     $a0                     # a[3]*a[0]
1499         add     %rax,$A0[0]             # a[3]*a[0]+a[2]*a[1]+t[3]
1500          mov    $ai,%rax
1501         mov     %rdx,$A0[1]
1502         adc     \$0,$A0[1]
1503         add     $A1[0],$A0[0]
1504         adc     \$0,$A0[1]
1505         mov     $A0[0],-8($tptr)        # t[3]
1506
1507         mul     $a1                     # a[3]*a[1]
1508         add     %rax,$A1[1]
1509          mov    -16($aptr),%rax         # a[2]
1510         adc     \$0,%rdx
1511         add     $A0[1],$A1[1]
1512         adc     \$0,%rdx
1513
1514         mov     $A1[1],($tptr)          # t[4]
1515         mov     %rdx,$A1[0]
1516         mov     %rdx,8($tptr)           # t[5]
1517
1518         mul     $ai                     # a[2]*a[3]
1519 ___
1520 {
1521 my ($shift,$carry)=($a0,$a1);
1522 my @S=(@A1,$ai,$n0);
1523 $code.=<<___;
1524          add    \$16,$i
1525          xor    $shift,$shift
1526          sub    $num,$i                 # $i=16-$num
1527          xor    $carry,$carry
1528
1529         add     $A1[0],%rax             # t[5]
1530         adc     \$0,%rdx
1531         mov     %rax,8($tptr)           # t[5]
1532         mov     %rdx,16($tptr)          # t[6]
1533         mov     $carry,24($tptr)        # t[7]
1534
1535          mov    -16($aptr,$i),%rax      # a[0]
1536         lea     48+8(%rsp),$tptr
1537          xor    $A0[0],$A0[0]           # t[0]
1538          mov    8($tptr),$A0[1]         # t[1]
1539
1540         lea     ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
1541         shr     \$63,$A0[0]
1542         lea     ($j,$A0[1],2),$S[1]     # t[2*i+1]<<1 |
1543         shr     \$63,$A0[1]
1544         or      $A0[0],$S[1]            # | t[2*i]>>63
1545          mov    16($tptr),$A0[0]        # t[2*i+2]      # prefetch
1546         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1547         mul     %rax                    # a[i]*a[i]
1548         neg     $carry                  # mov $carry,cf
1549          mov    24($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1550         adc     %rax,$S[0]
1551          mov    -8($aptr,$i),%rax       # a[i+1]        # prefetch
1552         mov     $S[0],($tptr)
1553         adc     %rdx,$S[1]
1554
1555         lea     ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
1556          mov    $S[1],8($tptr)
1557          sbb    $carry,$carry           # mov cf,$carry
1558         shr     \$63,$A0[0]
1559         lea     ($j,$A0[1],2),$S[3]     # t[2*i+1]<<1 |
1560         shr     \$63,$A0[1]
1561         or      $A0[0],$S[3]            # | t[2*i]>>63
1562          mov    32($tptr),$A0[0]        # t[2*i+2]      # prefetch
1563         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1564         mul     %rax                    # a[i]*a[i]
1565         neg     $carry                  # mov $carry,cf
1566          mov    40($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1567         adc     %rax,$S[2]
1568          mov    0($aptr,$i),%rax        # a[i+1]        # prefetch
1569         mov     $S[2],16($tptr)
1570         adc     %rdx,$S[3]
1571         lea     16($i),$i
1572         mov     $S[3],24($tptr)
1573         sbb     $carry,$carry           # mov cf,$carry
1574         lea     64($tptr),$tptr
1575         jmp     .Lsqr4x_shift_n_add
1576
1577 .align  32
1578 .Lsqr4x_shift_n_add:
1579         lea     ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
1580         shr     \$63,$A0[0]
1581         lea     ($j,$A0[1],2),$S[1]     # t[2*i+1]<<1 |
1582         shr     \$63,$A0[1]
1583         or      $A0[0],$S[1]            # | t[2*i]>>63
1584          mov    -16($tptr),$A0[0]       # t[2*i+2]      # prefetch
1585         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1586         mul     %rax                    # a[i]*a[i]
1587         neg     $carry                  # mov $carry,cf
1588          mov    -8($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1589         adc     %rax,$S[0]
1590          mov    -8($aptr,$i),%rax       # a[i+1]        # prefetch
1591         mov     $S[0],-32($tptr)
1592         adc     %rdx,$S[1]
1593
1594         lea     ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
1595          mov    $S[1],-24($tptr)
1596          sbb    $carry,$carry           # mov cf,$carry
1597         shr     \$63,$A0[0]
1598         lea     ($j,$A0[1],2),$S[3]     # t[2*i+1]<<1 |
1599         shr     \$63,$A0[1]
1600         or      $A0[0],$S[3]            # | t[2*i]>>63
1601          mov    0($tptr),$A0[0]         # t[2*i+2]      # prefetch
1602         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1603         mul     %rax                    # a[i]*a[i]
1604         neg     $carry                  # mov $carry,cf
1605          mov    8($tptr),$A0[1]         # t[2*i+2+1]    # prefetch
1606         adc     %rax,$S[2]
1607          mov    0($aptr,$i),%rax        # a[i+1]        # prefetch
1608         mov     $S[2],-16($tptr)
1609         adc     %rdx,$S[3]
1610
1611         lea     ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
1612          mov    $S[3],-8($tptr)
1613          sbb    $carry,$carry           # mov cf,$carry
1614         shr     \$63,$A0[0]
1615         lea     ($j,$A0[1],2),$S[1]     # t[2*i+1]<<1 |
1616         shr     \$63,$A0[1]
1617         or      $A0[0],$S[1]            # | t[2*i]>>63
1618          mov    16($tptr),$A0[0]        # t[2*i+2]      # prefetch
1619         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1620         mul     %rax                    # a[i]*a[i]
1621         neg     $carry                  # mov $carry,cf
1622          mov    24($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1623         adc     %rax,$S[0]
1624          mov    8($aptr,$i),%rax        # a[i+1]        # prefetch
1625         mov     $S[0],0($tptr)
1626         adc     %rdx,$S[1]
1627
1628         lea     ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
1629          mov    $S[1],8($tptr)
1630          sbb    $carry,$carry           # mov cf,$carry
1631         shr     \$63,$A0[0]
1632         lea     ($j,$A0[1],2),$S[3]     # t[2*i+1]<<1 |
1633         shr     \$63,$A0[1]
1634         or      $A0[0],$S[3]            # | t[2*i]>>63
1635          mov    32($tptr),$A0[0]        # t[2*i+2]      # prefetch
1636         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1637         mul     %rax                    # a[i]*a[i]
1638         neg     $carry                  # mov $carry,cf
1639          mov    40($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1640         adc     %rax,$S[2]
1641          mov    16($aptr,$i),%rax       # a[i+1]        # prefetch
1642         mov     $S[2],16($tptr)
1643         adc     %rdx,$S[3]
1644         mov     $S[3],24($tptr)
1645         sbb     $carry,$carry           # mov cf,$carry
1646         lea     64($tptr),$tptr
1647         add     \$32,$i
1648         jnz     .Lsqr4x_shift_n_add
1649
1650         lea     ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
1651         .byte   0x67
1652         shr     \$63,$A0[0]
1653         lea     ($j,$A0[1],2),$S[1]     # t[2*i+1]<<1 |
1654         shr     \$63,$A0[1]
1655         or      $A0[0],$S[1]            # | t[2*i]>>63
1656          mov    -16($tptr),$A0[0]       # t[2*i+2]      # prefetch
1657         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1658         mul     %rax                    # a[i]*a[i]
1659         neg     $carry                  # mov $carry,cf
1660          mov    -8($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1661         adc     %rax,$S[0]
1662          mov    -8($aptr),%rax          # a[i+1]        # prefetch
1663         mov     $S[0],-32($tptr)
1664         adc     %rdx,$S[1]
1665
1666         lea     ($shift,$A0[0],2),$S[2] # t[2*i]<<1|shift
1667          mov    $S[1],-24($tptr)
1668          sbb    $carry,$carry           # mov cf,$carry
1669         shr     \$63,$A0[0]
1670         lea     ($j,$A0[1],2),$S[3]     # t[2*i+1]<<1 |
1671         shr     \$63,$A0[1]
1672         or      $A0[0],$S[3]            # | t[2*i]>>63
1673         mul     %rax                    # a[i]*a[i]
1674         neg     $carry                  # mov $carry,cf
1675         adc     %rax,$S[2]
1676         adc     %rdx,$S[3]
1677         mov     $S[2],-16($tptr)
1678         mov     $S[3],-8($tptr)
1679 ___
1680 }\f
1681 ######################################################################
1682 # Montgomery reduction part, "word-by-word" algorithm.
1683 #
1684 # This new path is inspired by multiple submissions from Intel, by
1685 # Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
1686 # Vinodh Gopal...
1687 {
1688 my ($nptr,$tptr,$carry,$m0)=("%rbp","%rdi","%rsi","%rbx");
1689
1690 $code.=<<___;
1691         movq    %xmm2,$nptr
1692 __bn_sqr8x_reduction:
1693         xor     %rax,%rax
1694         lea     ($nptr,$num),%rcx       # end of n[]
1695         lea     48+8(%rsp,$num,2),%rdx  # end of t[] buffer
1696         mov     %rcx,0+8(%rsp)
1697         lea     48+8(%rsp,$num),$tptr   # end of initial t[] window
1698         mov     %rdx,8+8(%rsp)
1699         neg     $num
1700         jmp     .L8x_reduction_loop
1701
1702 .align  32
1703 .L8x_reduction_loop:
1704         lea     ($tptr,$num),$tptr      # start of current t[] window
1705         .byte   0x66
1706         mov     8*0($tptr),$m0
1707         mov     8*1($tptr),%r9
1708         mov     8*2($tptr),%r10
1709         mov     8*3($tptr),%r11
1710         mov     8*4($tptr),%r12
1711         mov     8*5($tptr),%r13
1712         mov     8*6($tptr),%r14
1713         mov     8*7($tptr),%r15
1714         mov     %rax,(%rdx)             # store top-most carry bit
1715         lea     8*8($tptr),$tptr
1716
1717         .byte   0x67
1718         mov     $m0,%r8
1719         imulq   32+8(%rsp),$m0          # n0*a[0]
1720         mov     8*0($nptr),%rax         # n[0]
1721         mov     \$8,%ecx
1722         jmp     .L8x_reduce
1723
1724 .align  32
1725 .L8x_reduce:
1726         mulq    $m0
1727          mov    8*1($nptr),%rax         # n[1]
1728         neg     %r8
1729         mov     %rdx,%r8
1730         adc     \$0,%r8
1731
1732         mulq    $m0
1733         add     %rax,%r9
1734          mov    8*2($nptr),%rax
1735         adc     \$0,%rdx
1736         add     %r9,%r8
1737          mov    $m0,48-8+8(%rsp,%rcx,8) # put aside n0*a[i]
1738         mov     %rdx,%r9
1739         adc     \$0,%r9
1740
1741         mulq    $m0
1742         add     %rax,%r10
1743          mov    8*3($nptr),%rax
1744         adc     \$0,%rdx
1745         add     %r10,%r9
1746          mov    32+8(%rsp),$carry       # pull n0, borrow $carry
1747         mov     %rdx,%r10
1748         adc     \$0,%r10
1749
1750         mulq    $m0
1751         add     %rax,%r11
1752          mov    8*4($nptr),%rax
1753         adc     \$0,%rdx
1754          imulq  %r8,$carry              # modulo-scheduled
1755         add     %r11,%r10
1756         mov     %rdx,%r11
1757         adc     \$0,%r11
1758
1759         mulq    $m0
1760         add     %rax,%r12
1761          mov    8*5($nptr),%rax
1762         adc     \$0,%rdx
1763         add     %r12,%r11
1764         mov     %rdx,%r12
1765         adc     \$0,%r12
1766
1767         mulq    $m0
1768         add     %rax,%r13
1769          mov    8*6($nptr),%rax
1770         adc     \$0,%rdx
1771         add     %r13,%r12
1772         mov     %rdx,%r13
1773         adc     \$0,%r13
1774
1775         mulq    $m0
1776         add     %rax,%r14
1777          mov    8*7($nptr),%rax
1778         adc     \$0,%rdx
1779         add     %r14,%r13
1780         mov     %rdx,%r14
1781         adc     \$0,%r14
1782
1783         mulq    $m0
1784          mov    $carry,$m0              # n0*a[i]
1785         add     %rax,%r15
1786          mov    8*0($nptr),%rax         # n[0]
1787         adc     \$0,%rdx
1788         add     %r15,%r14
1789         mov     %rdx,%r15
1790         adc     \$0,%r15
1791
1792         dec     %ecx
1793         jnz     .L8x_reduce
1794
1795         lea     8*8($nptr),$nptr
1796         xor     %rax,%rax
1797         mov     8+8(%rsp),%rdx          # pull end of t[]
1798         cmp     0+8(%rsp),$nptr         # end of n[]?
1799         jae     .L8x_no_tail
1800
1801         .byte   0x66
1802         add     8*0($tptr),%r8
1803         adc     8*1($tptr),%r9
1804         adc     8*2($tptr),%r10
1805         adc     8*3($tptr),%r11
1806         adc     8*4($tptr),%r12
1807         adc     8*5($tptr),%r13
1808         adc     8*6($tptr),%r14
1809         adc     8*7($tptr),%r15
1810         sbb     $carry,$carry           # top carry
1811
1812         mov     48+56+8(%rsp),$m0       # pull n0*a[0]
1813         mov     \$8,%ecx
1814         mov     8*0($nptr),%rax
1815         jmp     .L8x_tail
1816
1817 .align  32
1818 .L8x_tail:
1819         mulq    $m0
1820         add     %rax,%r8
1821          mov    8*1($nptr),%rax
1822          mov    %r8,($tptr)             # save result
1823         mov     %rdx,%r8
1824         adc     \$0,%r8
1825
1826         mulq    $m0
1827         add     %rax,%r9
1828          mov    8*2($nptr),%rax
1829         adc     \$0,%rdx
1830         add     %r9,%r8
1831          lea    8($tptr),$tptr          # $tptr++
1832         mov     %rdx,%r9
1833         adc     \$0,%r9
1834
1835         mulq    $m0
1836         add     %rax,%r10
1837          mov    8*3($nptr),%rax
1838         adc     \$0,%rdx
1839         add     %r10,%r9
1840         mov     %rdx,%r10
1841         adc     \$0,%r10
1842
1843         mulq    $m0
1844         add     %rax,%r11
1845          mov    8*4($nptr),%rax
1846         adc     \$0,%rdx
1847         add     %r11,%r10
1848         mov     %rdx,%r11
1849         adc     \$0,%r11
1850
1851         mulq    $m0
1852         add     %rax,%r12
1853          mov    8*5($nptr),%rax
1854         adc     \$0,%rdx
1855         add     %r12,%r11
1856         mov     %rdx,%r12
1857         adc     \$0,%r12
1858
1859         mulq    $m0
1860         add     %rax,%r13
1861          mov    8*6($nptr),%rax
1862         adc     \$0,%rdx
1863         add     %r13,%r12
1864         mov     %rdx,%r13
1865         adc     \$0,%r13
1866
1867         mulq    $m0
1868         add     %rax,%r14
1869          mov    8*7($nptr),%rax
1870         adc     \$0,%rdx
1871         add     %r14,%r13
1872         mov     %rdx,%r14
1873         adc     \$0,%r14
1874
1875         mulq    $m0
1876          mov    48-16+8(%rsp,%rcx,8),$m0# pull n0*a[i]
1877         add     %rax,%r15
1878         adc     \$0,%rdx
1879         add     %r15,%r14
1880          mov    8*0($nptr),%rax         # pull n[0]
1881         mov     %rdx,%r15
1882         adc     \$0,%r15
1883
1884         dec     %ecx
1885         jnz     .L8x_tail
1886
1887         lea     8*8($nptr),$nptr
1888         mov     8+8(%rsp),%rdx          # pull end of t[]
1889         cmp     0+8(%rsp),$nptr         # end of n[]?
1890         jae     .L8x_tail_done          # break out of loop
1891
1892          mov    48+56+8(%rsp),$m0       # pull n0*a[0]
1893         neg     $carry
1894          mov    8*0($nptr),%rax         # pull n[0]
1895         adc     8*0($tptr),%r8
1896         adc     8*1($tptr),%r9
1897         adc     8*2($tptr),%r10
1898         adc     8*3($tptr),%r11
1899         adc     8*4($tptr),%r12
1900         adc     8*5($tptr),%r13
1901         adc     8*6($tptr),%r14
1902         adc     8*7($tptr),%r15
1903         sbb     $carry,$carry           # top carry
1904
1905         mov     \$8,%ecx
1906         jmp     .L8x_tail
1907
1908 .align  32
1909 .L8x_tail_done:
1910         add     (%rdx),%r8              # can this overflow?
1911         adc     \$0,%r9
1912         adc     \$0,%r10
1913         adc     \$0,%r11
1914         adc     \$0,%r12
1915         adc     \$0,%r13
1916         adc     \$0,%r14
1917         adc     \$0,%r15                # can't overflow, because we
1918                                         # started with "overhung" part
1919                                         # of multiplication
1920         xor     %rax,%rax
1921
1922         neg     $carry
1923 .L8x_no_tail:
1924         adc     8*0($tptr),%r8
1925         adc     8*1($tptr),%r9
1926         adc     8*2($tptr),%r10
1927         adc     8*3($tptr),%r11
1928         adc     8*4($tptr),%r12
1929         adc     8*5($tptr),%r13
1930         adc     8*6($tptr),%r14
1931         adc     8*7($tptr),%r15
1932         adc     \$0,%rax                # top-most carry
1933          mov    -8($nptr),%rcx          # np[num-1]
1934          xor    $carry,$carry
1935
1936         movq    %xmm2,$nptr             # restore $nptr
1937
1938         mov     %r8,8*0($tptr)          # store top 512 bits
1939         mov     %r9,8*1($tptr)
1940          movq   %xmm3,$num              # $num is %r9, can't be moved upwards
1941         mov     %r10,8*2($tptr)
1942         mov     %r11,8*3($tptr)
1943         mov     %r12,8*4($tptr)
1944         mov     %r13,8*5($tptr)
1945         mov     %r14,8*6($tptr)
1946         mov     %r15,8*7($tptr)
1947         lea     8*8($tptr),$tptr
1948
1949         cmp     %rdx,$tptr              # end of t[]?
1950         jb      .L8x_reduction_loop
1951         ret
1952 .size   bn_sqr8x_internal,.-bn_sqr8x_internal
1953 ___
1954 }\f
1955 ##############################################################
1956 # Post-condition, 4x unrolled
1957 #
1958 {
1959 my ($tptr,$nptr)=("%rbx","%rbp");
1960 $code.=<<___;
1961 .type   __bn_post4x_internal,\@abi-omnipotent
1962 .align  32
1963 __bn_post4x_internal:
1964         mov     8*0($nptr),%r12
1965         lea     (%rdi,$num),$tptr       # %rdi was $tptr above
1966         mov     $num,%rcx
1967         movq    %xmm1,$rptr             # restore $rptr
1968         neg     %rax
1969         movq    %xmm1,$aptr             # prepare for back-to-back call
1970         sar     \$3+2,%rcx
1971         dec     %r12                    # so that after 'not' we get -n[0]
1972         xor     %r10,%r10
1973         mov     8*1($nptr),%r13
1974         mov     8*2($nptr),%r14
1975         mov     8*3($nptr),%r15
1976         jmp     .Lsqr4x_sub_entry
1977
1978 .align  16
1979 .Lsqr4x_sub:
1980         mov     8*0($nptr),%r12
1981         mov     8*1($nptr),%r13
1982         mov     8*2($nptr),%r14
1983         mov     8*3($nptr),%r15
1984 .Lsqr4x_sub_entry:
1985         lea     8*4($nptr),$nptr
1986         not     %r12
1987         not     %r13
1988         not     %r14
1989         not     %r15
1990         and     %rax,%r12
1991         and     %rax,%r13
1992         and     %rax,%r14
1993         and     %rax,%r15
1994
1995         neg     %r10                    # mov %r10,%cf
1996         adc     8*0($tptr),%r12
1997         adc     8*1($tptr),%r13
1998         adc     8*2($tptr),%r14
1999         adc     8*3($tptr),%r15
2000         mov     %r12,8*0($rptr)
2001         lea     8*4($tptr),$tptr
2002         mov     %r13,8*1($rptr)
2003         sbb     %r10,%r10               # mov %cf,%r10
2004         mov     %r14,8*2($rptr)
2005         mov     %r15,8*3($rptr)
2006         lea     8*4($rptr),$rptr
2007
2008         inc     %rcx                    # pass %cf
2009         jnz     .Lsqr4x_sub
2010
2011         mov     $num,%r10               # prepare for back-to-back call
2012         neg     $num                    # restore $num  
2013         ret
2014 .size   __bn_post4x_internal,.-__bn_post4x_internal
2015 ___
2016 }
2017 {
2018 $code.=<<___;
2019 .globl  bn_from_montgomery
2020 .type   bn_from_montgomery,\@abi-omnipotent
2021 .align  32
2022 bn_from_montgomery:
2023         testl   \$7,`($win64?"48(%rsp)":"%r9d")`
2024         jz      bn_from_mont8x
2025         xor     %eax,%eax
2026         ret
2027 .size   bn_from_montgomery,.-bn_from_montgomery
2028
2029 .type   bn_from_mont8x,\@function,6
2030 .align  32
2031 bn_from_mont8x:
2032         .byte   0x67
2033         mov     %rsp,%rax
2034         push    %rbx
2035         push    %rbp
2036         push    %r12
2037         push    %r13
2038         push    %r14
2039         push    %r15
2040
2041         shl     \$3,${num}d             # convert $num to bytes
2042         lea     ($num,$num,2),%r10      # 3*$num in bytes
2043         neg     $num
2044         mov     ($n0),$n0               # *n0
2045
2046         ##############################################################
2047         # Ensure that stack frame doesn't alias with $rptr+3*$num
2048         # modulo 4096, which covers ret[num], am[num] and n[num]
2049         # (see bn_exp.c). The stack is allocated to aligned with
2050         # bn_power5's frame, and as bn_from_montgomery happens to be
2051         # last operation, we use the opportunity to cleanse it.
2052         #
2053         lea     -320(%rsp,$num,2),%r11
2054         sub     $rptr,%r11
2055         and     \$4095,%r11
2056         cmp     %r11,%r10
2057         jb      .Lfrom_sp_alt
2058         sub     %r11,%rsp               # align with $aptr
2059         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*$num*8+256)
2060         jmp     .Lfrom_sp_done
2061
2062 .align  32
2063 .Lfrom_sp_alt:
2064         lea     4096-320(,$num,2),%r10
2065         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*$num*8+256)
2066         sub     %r10,%r11
2067         mov     \$0,%r10
2068         cmovc   %r10,%r11
2069         sub     %r11,%rsp
2070 .Lfrom_sp_done:
2071         and     \$-64,%rsp
2072         mov     %rax,%r11
2073         sub     %rsp,%r11
2074         and     \$-4096,%r11
2075 .Lfrom_page_walk:
2076         mov     (%rsp,%r11),%r10
2077         sub     \$4096,%r11
2078         .byte   0x2e                    # predict non-taken
2079         jnc     .Lfrom_page_walk
2080
2081         mov     $num,%r10
2082         neg     $num
2083
2084         ##############################################################
2085         # Stack layout
2086         #
2087         # +0    saved $num, used in reduction section
2088         # +8    &t[2*$num], used in reduction section
2089         # +32   saved *n0
2090         # +40   saved %rsp
2091         # +48   t[2*$num]
2092         #
2093         mov     $n0,  32(%rsp)
2094         mov     %rax, 40(%rsp)          # save original %rsp
2095 .Lfrom_body:
2096         mov     $num,%r11
2097         lea     48(%rsp),%rax
2098         pxor    %xmm0,%xmm0
2099         jmp     .Lmul_by_1
2100
2101 .align  32
2102 .Lmul_by_1:
2103         movdqu  ($aptr),%xmm1
2104         movdqu  16($aptr),%xmm2
2105         movdqu  32($aptr),%xmm3
2106         movdqa  %xmm0,(%rax,$num)
2107         movdqu  48($aptr),%xmm4
2108         movdqa  %xmm0,16(%rax,$num)
2109         .byte   0x48,0x8d,0xb6,0x40,0x00,0x00,0x00      # lea   64($aptr),$aptr
2110         movdqa  %xmm1,(%rax)
2111         movdqa  %xmm0,32(%rax,$num)
2112         movdqa  %xmm2,16(%rax)
2113         movdqa  %xmm0,48(%rax,$num)
2114         movdqa  %xmm3,32(%rax)
2115         movdqa  %xmm4,48(%rax)
2116         lea     64(%rax),%rax
2117         sub     \$64,%r11
2118         jnz     .Lmul_by_1
2119
2120         movq    $rptr,%xmm1
2121         movq    $nptr,%xmm2
2122         .byte   0x67
2123         mov     $nptr,%rbp
2124         movq    %r10, %xmm3             # -num
2125 ___
2126 $code.=<<___ if ($addx);
2127         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
2128         and     \$0x80108,%r11d
2129         cmp     \$0x80108,%r11d         # check for AD*X+BMI2+BMI1
2130         jne     .Lfrom_mont_nox
2131
2132         lea     (%rax,$num),$rptr
2133         call    __bn_sqrx8x_reduction
2134         call    __bn_postx4x_internal
2135
2136         pxor    %xmm0,%xmm0
2137         lea     48(%rsp),%rax
2138         mov     40(%rsp),%rsi           # restore %rsp
2139         jmp     .Lfrom_mont_zero
2140
2141 .align  32
2142 .Lfrom_mont_nox:
2143 ___
2144 $code.=<<___;
2145         call    __bn_sqr8x_reduction
2146         call    __bn_post4x_internal
2147
2148         pxor    %xmm0,%xmm0
2149         lea     48(%rsp),%rax
2150         mov     40(%rsp),%rsi           # restore %rsp
2151         jmp     .Lfrom_mont_zero
2152
2153 .align  32
2154 .Lfrom_mont_zero:
2155         movdqa  %xmm0,16*0(%rax)
2156         movdqa  %xmm0,16*1(%rax)
2157         movdqa  %xmm0,16*2(%rax)
2158         movdqa  %xmm0,16*3(%rax)
2159         lea     16*4(%rax),%rax
2160         sub     \$32,$num
2161         jnz     .Lfrom_mont_zero
2162
2163         mov     \$1,%rax
2164         mov     -48(%rsi),%r15
2165         mov     -40(%rsi),%r14
2166         mov     -32(%rsi),%r13
2167         mov     -24(%rsi),%r12
2168         mov     -16(%rsi),%rbp
2169         mov     -8(%rsi),%rbx
2170         lea     (%rsi),%rsp
2171 .Lfrom_epilogue:
2172         ret
2173 .size   bn_from_mont8x,.-bn_from_mont8x
2174 ___
2175 }
2176 }}}
2177 \f
2178 if ($addx) {{{
2179 my $bp="%rdx";  # restore original value
2180
2181 $code.=<<___;
2182 .type   bn_mulx4x_mont_gather5,\@function,6
2183 .align  32
2184 bn_mulx4x_mont_gather5:
2185 .Lmulx4x_enter:
2186         mov     %rsp,%rax
2187         push    %rbx
2188         push    %rbp
2189         push    %r12
2190         push    %r13
2191         push    %r14
2192         push    %r15
2193
2194         shl     \$3,${num}d             # convert $num to bytes
2195         lea     ($num,$num,2),%r10      # 3*$num in bytes
2196         neg     $num                    # -$num
2197         mov     ($n0),$n0               # *n0
2198
2199         ##############################################################
2200         # Ensure that stack frame doesn't alias with $rptr+3*$num
2201         # modulo 4096, which covers ret[num], am[num] and n[num]
2202         # (see bn_exp.c). This is done to allow memory disambiguation
2203         # logic do its magic. [Extra [num] is allocated in order
2204         # to align with bn_power5's frame, which is cleansed after
2205         # completing exponentiation. Extra 256 bytes is for power mask
2206         # calculated from 7th argument, the index.]
2207         #
2208         lea     -320(%rsp,$num,2),%r11
2209         sub     $rp,%r11
2210         and     \$4095,%r11
2211         cmp     %r11,%r10
2212         jb      .Lmulx4xsp_alt
2213         sub     %r11,%rsp               # align with $aptr
2214         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*$num*8+256)
2215         jmp     .Lmulx4xsp_done
2216
2217 .Lmulx4xsp_alt:
2218         lea     4096-320(,$num,2),%r10
2219         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*$num*8+256)
2220         sub     %r10,%r11
2221         mov     \$0,%r10
2222         cmovc   %r10,%r11
2223         sub     %r11,%rsp
2224 .Lmulx4xsp_done:        
2225         and     \$-64,%rsp              # ensure alignment
2226         mov     %rax,%r11
2227         sub     %rsp,%r11
2228         and     \$-4096,%r11
2229 .Lmulx4x_page_walk:
2230         mov     (%rsp,%r11),%r10
2231         sub     \$4096,%r11
2232         .byte   0x2e                    # predict non-taken
2233         jnc     .Lmulx4x_page_walk
2234
2235         ##############################################################
2236         # Stack layout
2237         # +0    -num
2238         # +8    off-loaded &b[i]
2239         # +16   end of b[num]
2240         # +24   inner counter
2241         # +32   saved n0
2242         # +40   saved %rsp
2243         # +48
2244         # +56   saved rp
2245         # +64   tmp[num+1]
2246         #
2247         mov     $n0, 32(%rsp)           # save *n0
2248         mov     %rax,40(%rsp)           # save original %rsp
2249 .Lmulx4x_body:
2250         call    mulx4x_internal
2251
2252         mov     40(%rsp),%rsi           # restore %rsp
2253         mov     \$1,%rax
2254
2255         mov     -48(%rsi),%r15
2256         mov     -40(%rsi),%r14
2257         mov     -32(%rsi),%r13
2258         mov     -24(%rsi),%r12
2259         mov     -16(%rsi),%rbp
2260         mov     -8(%rsi),%rbx
2261         lea     (%rsi),%rsp
2262 .Lmulx4x_epilogue:
2263         ret
2264 .size   bn_mulx4x_mont_gather5,.-bn_mulx4x_mont_gather5
2265
2266 .type   mulx4x_internal,\@abi-omnipotent
2267 .align  32
2268 mulx4x_internal:
2269         mov     $num,8(%rsp)            # save -$num (it was in bytes)
2270         mov     $num,%r10
2271         neg     $num                    # restore $num
2272         shl     \$5,$num
2273         neg     %r10                    # restore $num
2274         lea     128($bp,$num),%r13      # end of powers table (+size optimization)
2275         shr     \$5+5,$num
2276         movd    `($win64?56:8)`(%rax),%xmm5     # load 7th argument
2277         sub     \$1,$num
2278         lea     .Linc(%rip),%rax
2279         mov     %r13,16+8(%rsp)         # end of b[num]
2280         mov     $num,24+8(%rsp)         # inner counter
2281         mov     $rp, 56+8(%rsp)         # save $rp
2282 ___
2283 my ($aptr, $bptr, $nptr, $tptr, $mi,  $bi,  $zero, $num)=
2284    ("%rsi","%rdi","%rcx","%rbx","%r8","%r9","%rbp","%rax");
2285 my $rptr=$bptr;
2286 my $STRIDE=2**5*8;              # 5 is "window size"
2287 my $N=$STRIDE/4;                # should match cache line size
2288 $code.=<<___;
2289         movdqa  0(%rax),%xmm0           # 00000001000000010000000000000000
2290         movdqa  16(%rax),%xmm1          # 00000002000000020000000200000002
2291         lea     88-112(%rsp,%r10),%r10  # place the mask after tp[num+1] (+ICache optimizaton)
2292         lea     128($bp),$bptr          # size optimization
2293
2294         pshufd  \$0,%xmm5,%xmm5         # broadcast index
2295         movdqa  %xmm1,%xmm4
2296         .byte   0x67
2297         movdqa  %xmm1,%xmm2
2298 ___
2299 ########################################################################
2300 # calculate mask by comparing 0..31 to index and save result to stack
2301 #
2302 $code.=<<___;
2303         .byte   0x67
2304         paddd   %xmm0,%xmm1
2305         pcmpeqd %xmm5,%xmm0             # compare to 1,0
2306         movdqa  %xmm4,%xmm3
2307 ___
2308 for($i=0;$i<$STRIDE/16-4;$i+=4) {
2309 $code.=<<___;
2310         paddd   %xmm1,%xmm2
2311         pcmpeqd %xmm5,%xmm1             # compare to 3,2
2312         movdqa  %xmm0,`16*($i+0)+112`(%r10)
2313         movdqa  %xmm4,%xmm0
2314
2315         paddd   %xmm2,%xmm3
2316         pcmpeqd %xmm5,%xmm2             # compare to 5,4
2317         movdqa  %xmm1,`16*($i+1)+112`(%r10)
2318         movdqa  %xmm4,%xmm1
2319
2320         paddd   %xmm3,%xmm0
2321         pcmpeqd %xmm5,%xmm3             # compare to 7,6
2322         movdqa  %xmm2,`16*($i+2)+112`(%r10)
2323         movdqa  %xmm4,%xmm2
2324
2325         paddd   %xmm0,%xmm1
2326         pcmpeqd %xmm5,%xmm0
2327         movdqa  %xmm3,`16*($i+3)+112`(%r10)
2328         movdqa  %xmm4,%xmm3
2329 ___
2330 }
2331 $code.=<<___;                           # last iteration can be optimized
2332         .byte   0x67
2333         paddd   %xmm1,%xmm2
2334         pcmpeqd %xmm5,%xmm1
2335         movdqa  %xmm0,`16*($i+0)+112`(%r10)
2336
2337         paddd   %xmm2,%xmm3
2338         pcmpeqd %xmm5,%xmm2
2339         movdqa  %xmm1,`16*($i+1)+112`(%r10)
2340
2341         pcmpeqd %xmm5,%xmm3
2342         movdqa  %xmm2,`16*($i+2)+112`(%r10)
2343
2344         pand    `16*($i+0)-128`($bptr),%xmm0    # while it's still in register
2345         pand    `16*($i+1)-128`($bptr),%xmm1
2346         pand    `16*($i+2)-128`($bptr),%xmm2
2347         movdqa  %xmm3,`16*($i+3)+112`(%r10)
2348         pand    `16*($i+3)-128`($bptr),%xmm3
2349         por     %xmm2,%xmm0
2350         por     %xmm3,%xmm1
2351 ___
2352 for($i=0;$i<$STRIDE/16-4;$i+=4) {
2353 $code.=<<___;
2354         movdqa  `16*($i+0)-128`($bptr),%xmm4
2355         movdqa  `16*($i+1)-128`($bptr),%xmm5
2356         movdqa  `16*($i+2)-128`($bptr),%xmm2
2357         pand    `16*($i+0)+112`(%r10),%xmm4
2358         movdqa  `16*($i+3)-128`($bptr),%xmm3
2359         pand    `16*($i+1)+112`(%r10),%xmm5
2360         por     %xmm4,%xmm0
2361         pand    `16*($i+2)+112`(%r10),%xmm2
2362         por     %xmm5,%xmm1
2363         pand    `16*($i+3)+112`(%r10),%xmm3
2364         por     %xmm2,%xmm0
2365         por     %xmm3,%xmm1
2366 ___
2367 }
2368 $code.=<<___;
2369         pxor    %xmm1,%xmm0
2370         pshufd  \$0x4e,%xmm0,%xmm1
2371         por     %xmm1,%xmm0
2372         lea     $STRIDE($bptr),$bptr
2373         movq    %xmm0,%rdx              # bp[0]
2374         lea     64+8*4+8(%rsp),$tptr
2375
2376         mov     %rdx,$bi
2377         mulx    0*8($aptr),$mi,%rax     # a[0]*b[0]
2378         mulx    1*8($aptr),%r11,%r12    # a[1]*b[0]
2379         add     %rax,%r11
2380         mulx    2*8($aptr),%rax,%r13    # ...
2381         adc     %rax,%r12
2382         adc     \$0,%r13
2383         mulx    3*8($aptr),%rax,%r14
2384
2385         mov     $mi,%r15
2386         imulq   32+8(%rsp),$mi          # "t[0]"*n0
2387         xor     $zero,$zero             # cf=0, of=0
2388         mov     $mi,%rdx
2389
2390         mov     $bptr,8+8(%rsp)         # off-load &b[i]
2391
2392         lea     4*8($aptr),$aptr
2393         adcx    %rax,%r13
2394         adcx    $zero,%r14              # cf=0
2395
2396         mulx    0*8($nptr),%rax,%r10
2397         adcx    %rax,%r15               # discarded
2398         adox    %r11,%r10
2399         mulx    1*8($nptr),%rax,%r11
2400         adcx    %rax,%r10
2401         adox    %r12,%r11
2402         mulx    2*8($nptr),%rax,%r12
2403         mov     24+8(%rsp),$bptr        # counter value
2404         mov     %r10,-8*4($tptr)
2405         adcx    %rax,%r11
2406         adox    %r13,%r12
2407         mulx    3*8($nptr),%rax,%r15
2408          mov    $bi,%rdx
2409         mov     %r11,-8*3($tptr)
2410         adcx    %rax,%r12
2411         adox    $zero,%r15              # of=0
2412         lea     4*8($nptr),$nptr
2413         mov     %r12,-8*2($tptr)
2414         jmp     .Lmulx4x_1st
2415
2416 .align  32
2417 .Lmulx4x_1st:
2418         adcx    $zero,%r15              # cf=0, modulo-scheduled
2419         mulx    0*8($aptr),%r10,%rax    # a[4]*b[0]
2420         adcx    %r14,%r10
2421         mulx    1*8($aptr),%r11,%r14    # a[5]*b[0]
2422         adcx    %rax,%r11
2423         mulx    2*8($aptr),%r12,%rax    # ...
2424         adcx    %r14,%r12
2425         mulx    3*8($aptr),%r13,%r14
2426          .byte  0x67,0x67
2427          mov    $mi,%rdx
2428         adcx    %rax,%r13
2429         adcx    $zero,%r14              # cf=0
2430         lea     4*8($aptr),$aptr
2431         lea     4*8($tptr),$tptr
2432
2433         adox    %r15,%r10
2434         mulx    0*8($nptr),%rax,%r15
2435         adcx    %rax,%r10
2436         adox    %r15,%r11
2437         mulx    1*8($nptr),%rax,%r15
2438         adcx    %rax,%r11
2439         adox    %r15,%r12
2440         mulx    2*8($nptr),%rax,%r15
2441         mov     %r10,-5*8($tptr)
2442         adcx    %rax,%r12
2443         mov     %r11,-4*8($tptr)
2444         adox    %r15,%r13
2445         mulx    3*8($nptr),%rax,%r15
2446          mov    $bi,%rdx
2447         mov     %r12,-3*8($tptr)
2448         adcx    %rax,%r13
2449         adox    $zero,%r15
2450         lea     4*8($nptr),$nptr
2451         mov     %r13,-2*8($tptr)
2452
2453         dec     $bptr                   # of=0, pass cf
2454         jnz     .Lmulx4x_1st
2455
2456         mov     8(%rsp),$num            # load -num
2457         adc     $zero,%r15              # modulo-scheduled
2458         lea     ($aptr,$num),$aptr      # rewind $aptr
2459         add     %r15,%r14
2460         mov     8+8(%rsp),$bptr         # re-load &b[i]
2461         adc     $zero,$zero             # top-most carry
2462         mov     %r14,-1*8($tptr)
2463         jmp     .Lmulx4x_outer
2464
2465 .align  32
2466 .Lmulx4x_outer:
2467         lea     16-256($tptr),%r10      # where 256-byte mask is (+density control)
2468         pxor    %xmm4,%xmm4
2469         .byte   0x67,0x67
2470         pxor    %xmm5,%xmm5
2471 ___
2472 for($i=0;$i<$STRIDE/16;$i+=4) {
2473 $code.=<<___;
2474         movdqa  `16*($i+0)-128`($bptr),%xmm0
2475         movdqa  `16*($i+1)-128`($bptr),%xmm1
2476         movdqa  `16*($i+2)-128`($bptr),%xmm2
2477         pand    `16*($i+0)+256`(%r10),%xmm0
2478         movdqa  `16*($i+3)-128`($bptr),%xmm3
2479         pand    `16*($i+1)+256`(%r10),%xmm1
2480         por     %xmm0,%xmm4
2481         pand    `16*($i+2)+256`(%r10),%xmm2
2482         por     %xmm1,%xmm5
2483         pand    `16*($i+3)+256`(%r10),%xmm3
2484         por     %xmm2,%xmm4
2485         por     %xmm3,%xmm5
2486 ___
2487 }
2488 $code.=<<___;
2489         por     %xmm5,%xmm4
2490         pshufd  \$0x4e,%xmm4,%xmm0
2491         por     %xmm4,%xmm0
2492         lea     $STRIDE($bptr),$bptr
2493         movq    %xmm0,%rdx              # m0=bp[i]
2494
2495         mov     $zero,($tptr)           # save top-most carry
2496         lea     4*8($tptr,$num),$tptr   # rewind $tptr
2497         mulx    0*8($aptr),$mi,%r11     # a[0]*b[i]
2498         xor     $zero,$zero             # cf=0, of=0
2499         mov     %rdx,$bi
2500         mulx    1*8($aptr),%r14,%r12    # a[1]*b[i]
2501         adox    -4*8($tptr),$mi         # +t[0]
2502         adcx    %r14,%r11
2503         mulx    2*8($aptr),%r15,%r13    # ...
2504         adox    -3*8($tptr),%r11
2505         adcx    %r15,%r12
2506         mulx    3*8($aptr),%rdx,%r14
2507         adox    -2*8($tptr),%r12
2508         adcx    %rdx,%r13
2509         lea     ($nptr,$num),$nptr      # rewind $nptr
2510         lea     4*8($aptr),$aptr
2511         adox    -1*8($tptr),%r13
2512         adcx    $zero,%r14
2513         adox    $zero,%r14
2514
2515         mov     $mi,%r15
2516         imulq   32+8(%rsp),$mi          # "t[0]"*n0
2517
2518         mov     $mi,%rdx
2519         xor     $zero,$zero             # cf=0, of=0
2520         mov     $bptr,8+8(%rsp)         # off-load &b[i]
2521
2522         mulx    0*8($nptr),%rax,%r10
2523         adcx    %rax,%r15               # discarded
2524         adox    %r11,%r10
2525         mulx    1*8($nptr),%rax,%r11
2526         adcx    %rax,%r10
2527         adox    %r12,%r11
2528         mulx    2*8($nptr),%rax,%r12
2529         adcx    %rax,%r11
2530         adox    %r13,%r12
2531         mulx    3*8($nptr),%rax,%r15
2532          mov    $bi,%rdx
2533         mov     24+8(%rsp),$bptr        # counter value
2534         mov     %r10,-8*4($tptr)
2535         adcx    %rax,%r12
2536         mov     %r11,-8*3($tptr)
2537         adox    $zero,%r15              # of=0
2538         mov     %r12,-8*2($tptr)
2539         lea     4*8($nptr),$nptr
2540         jmp     .Lmulx4x_inner
2541
2542 .align  32
2543 .Lmulx4x_inner:
2544         mulx    0*8($aptr),%r10,%rax    # a[4]*b[i]
2545         adcx    $zero,%r15              # cf=0, modulo-scheduled
2546         adox    %r14,%r10
2547         mulx    1*8($aptr),%r11,%r14    # a[5]*b[i]
2548         adcx    0*8($tptr),%r10
2549         adox    %rax,%r11
2550         mulx    2*8($aptr),%r12,%rax    # ...
2551         adcx    1*8($tptr),%r11
2552         adox    %r14,%r12
2553         mulx    3*8($aptr),%r13,%r14
2554          mov    $mi,%rdx
2555         adcx    2*8($tptr),%r12
2556         adox    %rax,%r13
2557         adcx    3*8($tptr),%r13
2558         adox    $zero,%r14              # of=0
2559         lea     4*8($aptr),$aptr
2560         lea     4*8($tptr),$tptr
2561         adcx    $zero,%r14              # cf=0
2562
2563         adox    %r15,%r10
2564         mulx    0*8($nptr),%rax,%r15
2565         adcx    %rax,%r10
2566         adox    %r15,%r11
2567         mulx    1*8($nptr),%rax,%r15
2568         adcx    %rax,%r11
2569         adox    %r15,%r12
2570         mulx    2*8($nptr),%rax,%r15
2571         mov     %r10,-5*8($tptr)
2572         adcx    %rax,%r12
2573         adox    %r15,%r13
2574         mov     %r11,-4*8($tptr)
2575         mulx    3*8($nptr),%rax,%r15
2576          mov    $bi,%rdx
2577         lea     4*8($nptr),$nptr
2578         mov     %r12,-3*8($tptr)
2579         adcx    %rax,%r13
2580         adox    $zero,%r15
2581         mov     %r13,-2*8($tptr)
2582
2583         dec     $bptr                   # of=0, pass cf
2584         jnz     .Lmulx4x_inner
2585
2586         mov     0+8(%rsp),$num          # load -num
2587         adc     $zero,%r15              # modulo-scheduled
2588         sub     0*8($tptr),$bptr        # pull top-most carry to %cf
2589         mov     8+8(%rsp),$bptr         # re-load &b[i]
2590         mov     16+8(%rsp),%r10
2591         adc     %r15,%r14
2592         lea     ($aptr,$num),$aptr      # rewind $aptr
2593         adc     $zero,$zero             # top-most carry
2594         mov     %r14,-1*8($tptr)
2595
2596         cmp     %r10,$bptr
2597         jb      .Lmulx4x_outer
2598
2599         mov     -8($nptr),%r10
2600         mov     $zero,%r8
2601         mov     ($nptr,$num),%r12
2602         lea     ($nptr,$num),%rbp       # rewind $nptr
2603         mov     $num,%rcx
2604         lea     ($tptr,$num),%rdi       # rewind $tptr
2605         xor     %eax,%eax
2606         xor     %r15,%r15
2607         sub     %r14,%r10               # compare top-most words
2608         adc     %r15,%r15
2609         or      %r15,%r8
2610         sar     \$3+2,%rcx
2611         sub     %r8,%rax                # %rax=-%r8
2612         mov     56+8(%rsp),%rdx         # restore rp
2613         dec     %r12                    # so that after 'not' we get -n[0]
2614         mov     8*1(%rbp),%r13
2615         xor     %r8,%r8
2616         mov     8*2(%rbp),%r14
2617         mov     8*3(%rbp),%r15
2618         jmp     .Lsqrx4x_sub_entry      # common post-condition
2619 .size   mulx4x_internal,.-mulx4x_internal
2620 ___
2621 }\f{
2622 ######################################################################
2623 # void bn_power5(
2624 my $rptr="%rdi";        # BN_ULONG *rptr,
2625 my $aptr="%rsi";        # const BN_ULONG *aptr,
2626 my $bptr="%rdx";        # const void *table,
2627 my $nptr="%rcx";        # const BN_ULONG *nptr,
2628 my $n0  ="%r8";         # const BN_ULONG *n0);
2629 my $num ="%r9";         # int num, has to be divisible by 8
2630                         # int pwr);
2631
2632 my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
2633 my @A0=("%r10","%r11");
2634 my @A1=("%r12","%r13");
2635 my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
2636
2637 $code.=<<___;
2638 .type   bn_powerx5,\@function,6
2639 .align  32
2640 bn_powerx5:
2641 .Lpowerx5_enter:
2642         mov     %rsp,%rax
2643         push    %rbx
2644         push    %rbp
2645         push    %r12
2646         push    %r13
2647         push    %r14
2648         push    %r15
2649
2650         shl     \$3,${num}d             # convert $num to bytes
2651         lea     ($num,$num,2),%r10      # 3*$num in bytes
2652         neg     $num
2653         mov     ($n0),$n0               # *n0
2654
2655         ##############################################################
2656         # Ensure that stack frame doesn't alias with $rptr+3*$num
2657         # modulo 4096, which covers ret[num], am[num] and n[num]
2658         # (see bn_exp.c). This is done to allow memory disambiguation
2659         # logic do its magic. [Extra 256 bytes is for power mask
2660         # calculated from 7th argument, the index.]
2661         #
2662         lea     -320(%rsp,$num,2),%r11
2663         sub     $rptr,%r11
2664         and     \$4095,%r11
2665         cmp     %r11,%r10
2666         jb      .Lpwrx_sp_alt
2667         sub     %r11,%rsp               # align with $aptr
2668         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*$num*8+256)
2669         jmp     .Lpwrx_sp_done
2670
2671 .align  32
2672 .Lpwrx_sp_alt:
2673         lea     4096-320(,$num,2),%r10
2674         lea     -320(%rsp,$num,2),%rsp  # alloca(frame+2*$num*8+256)
2675         sub     %r10,%r11
2676         mov     \$0,%r10
2677         cmovc   %r10,%r11
2678         sub     %r11,%rsp
2679 .Lpwrx_sp_done:
2680         and     \$-64,%rsp
2681         mov     %rax,%r11
2682         sub     %rsp,%r11
2683         and     \$-4096,%r11
2684 .Lpwrx_page_walk:
2685         mov     (%rsp,%r11),%r10
2686         sub     \$4096,%r11
2687         .byte   0x2e                    # predict non-taken
2688         jnc     .Lpwrx_page_walk
2689
2690         mov     $num,%r10       
2691         neg     $num
2692
2693         ##############################################################
2694         # Stack layout
2695         #
2696         # +0    saved $num, used in reduction section
2697         # +8    &t[2*$num], used in reduction section
2698         # +16   intermediate carry bit
2699         # +24   top-most carry bit, used in reduction section
2700         # +32   saved *n0
2701         # +40   saved %rsp
2702         # +48   t[2*$num]
2703         #
2704         pxor    %xmm0,%xmm0
2705         movq    $rptr,%xmm1             # save $rptr
2706         movq    $nptr,%xmm2             # save $nptr
2707         movq    %r10, %xmm3             # -$num
2708         movq    $bptr,%xmm4
2709         mov     $n0,  32(%rsp)
2710         mov     %rax, 40(%rsp)          # save original %rsp
2711 .Lpowerx5_body:
2712
2713         call    __bn_sqrx8x_internal
2714         call    __bn_postx4x_internal
2715         call    __bn_sqrx8x_internal
2716         call    __bn_postx4x_internal
2717         call    __bn_sqrx8x_internal
2718         call    __bn_postx4x_internal
2719         call    __bn_sqrx8x_internal
2720         call    __bn_postx4x_internal
2721         call    __bn_sqrx8x_internal
2722         call    __bn_postx4x_internal
2723
2724         mov     %r10,$num               # -num
2725         mov     $aptr,$rptr
2726         movq    %xmm2,$nptr
2727         movq    %xmm4,$bptr
2728         mov     40(%rsp),%rax
2729
2730         call    mulx4x_internal
2731
2732         mov     40(%rsp),%rsi           # restore %rsp
2733         mov     \$1,%rax
2734
2735         mov     -48(%rsi),%r15
2736         mov     -40(%rsi),%r14
2737         mov     -32(%rsi),%r13
2738         mov     -24(%rsi),%r12
2739         mov     -16(%rsi),%rbp
2740         mov     -8(%rsi),%rbx
2741         lea     (%rsi),%rsp
2742 .Lpowerx5_epilogue:
2743         ret
2744 .size   bn_powerx5,.-bn_powerx5
2745
2746 .globl  bn_sqrx8x_internal
2747 .hidden bn_sqrx8x_internal
2748 .type   bn_sqrx8x_internal,\@abi-omnipotent
2749 .align  32
2750 bn_sqrx8x_internal:
2751 __bn_sqrx8x_internal:
2752         ##################################################################
2753         # Squaring part:
2754         #
2755         # a) multiply-n-add everything but a[i]*a[i];
2756         # b) shift result of a) by 1 to the left and accumulate
2757         #    a[i]*a[i] products;
2758         #
2759         ##################################################################
2760         # a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
2761         #                                                     a[1]a[0]
2762         #                                                 a[2]a[0]
2763         #                                             a[3]a[0]
2764         #                                             a[2]a[1]
2765         #                                         a[3]a[1]
2766         #                                     a[3]a[2]
2767         #
2768         #                                         a[4]a[0]
2769         #                                     a[5]a[0]
2770         #                                 a[6]a[0]
2771         #                             a[7]a[0]
2772         #                                     a[4]a[1]
2773         #                                 a[5]a[1]
2774         #                             a[6]a[1]
2775         #                         a[7]a[1]
2776         #                                 a[4]a[2]
2777         #                             a[5]a[2]
2778         #                         a[6]a[2]
2779         #                     a[7]a[2]
2780         #                             a[4]a[3]
2781         #                         a[5]a[3]
2782         #                     a[6]a[3]
2783         #                 a[7]a[3]
2784         #
2785         #                     a[5]a[4]
2786         #                 a[6]a[4]
2787         #             a[7]a[4]
2788         #             a[6]a[5]
2789         #         a[7]a[5]
2790         #     a[7]a[6]
2791         # a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
2792 ___
2793 {
2794 my ($zero,$carry)=("%rbp","%rcx");
2795 my $aaptr=$zero;
2796 $code.=<<___;
2797         lea     48+8(%rsp),$tptr
2798         lea     ($aptr,$num),$aaptr
2799         mov     $num,0+8(%rsp)                  # save $num
2800         mov     $aaptr,8+8(%rsp)                # save end of $aptr
2801         jmp     .Lsqr8x_zero_start
2802
2803 .align  32
2804 .byte   0x66,0x66,0x66,0x2e,0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00
2805 .Lsqrx8x_zero:
2806         .byte   0x3e
2807         movdqa  %xmm0,0*8($tptr)
2808         movdqa  %xmm0,2*8($tptr)
2809         movdqa  %xmm0,4*8($tptr)
2810         movdqa  %xmm0,6*8($tptr)
2811 .Lsqr8x_zero_start:                     # aligned at 32
2812         movdqa  %xmm0,8*8($tptr)
2813         movdqa  %xmm0,10*8($tptr)
2814         movdqa  %xmm0,12*8($tptr)
2815         movdqa  %xmm0,14*8($tptr)
2816         lea     16*8($tptr),$tptr
2817         sub     \$64,$num
2818         jnz     .Lsqrx8x_zero
2819
2820         mov     0*8($aptr),%rdx         # a[0], modulo-scheduled
2821         #xor    %r9,%r9                 # t[1], ex-$num, zero already
2822         xor     %r10,%r10
2823         xor     %r11,%r11
2824         xor     %r12,%r12
2825         xor     %r13,%r13
2826         xor     %r14,%r14
2827         xor     %r15,%r15
2828         lea     48+8(%rsp),$tptr
2829         xor     $zero,$zero             # cf=0, cf=0
2830         jmp     .Lsqrx8x_outer_loop
2831
2832 .align  32
2833 .Lsqrx8x_outer_loop:
2834         mulx    1*8($aptr),%r8,%rax     # a[1]*a[0]
2835         adcx    %r9,%r8                 # a[1]*a[0]+=t[1]
2836         adox    %rax,%r10
2837         mulx    2*8($aptr),%r9,%rax     # a[2]*a[0]
2838         adcx    %r10,%r9
2839         adox    %rax,%r11
2840         .byte   0xc4,0xe2,0xab,0xf6,0x86,0x18,0x00,0x00,0x00    # mulx  3*8($aptr),%r10,%rax    # ...
2841         adcx    %r11,%r10
2842         adox    %rax,%r12
2843         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x20,0x00,0x00,0x00    # mulx  4*8($aptr),%r11,%rax
2844         adcx    %r12,%r11
2845         adox    %rax,%r13
2846         mulx    5*8($aptr),%r12,%rax
2847         adcx    %r13,%r12
2848         adox    %rax,%r14
2849         mulx    6*8($aptr),%r13,%rax
2850         adcx    %r14,%r13
2851         adox    %r15,%rax
2852         mulx    7*8($aptr),%r14,%r15
2853          mov    1*8($aptr),%rdx         # a[1]
2854         adcx    %rax,%r14
2855         adox    $zero,%r15
2856         adc     8*8($tptr),%r15
2857         mov     %r8,1*8($tptr)          # t[1]
2858         mov     %r9,2*8($tptr)          # t[2]
2859         sbb     $carry,$carry           # mov %cf,$carry
2860         xor     $zero,$zero             # cf=0, of=0
2861
2862
2863         mulx    2*8($aptr),%r8,%rbx     # a[2]*a[1]
2864         mulx    3*8($aptr),%r9,%rax     # a[3]*a[1]
2865         adcx    %r10,%r8
2866         adox    %rbx,%r9
2867         mulx    4*8($aptr),%r10,%rbx    # ...
2868         adcx    %r11,%r9
2869         adox    %rax,%r10
2870         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x28,0x00,0x00,0x00    # mulx  5*8($aptr),%r11,%rax
2871         adcx    %r12,%r10
2872         adox    %rbx,%r11
2873         .byte   0xc4,0xe2,0x9b,0xf6,0x9e,0x30,0x00,0x00,0x00    # mulx  6*8($aptr),%r12,%rbx
2874         adcx    %r13,%r11
2875         adox    %r14,%r12
2876         .byte   0xc4,0x62,0x93,0xf6,0xb6,0x38,0x00,0x00,0x00    # mulx  7*8($aptr),%r13,%r14
2877          mov    2*8($aptr),%rdx         # a[2]
2878         adcx    %rax,%r12
2879         adox    %rbx,%r13
2880         adcx    %r15,%r13
2881         adox    $zero,%r14              # of=0
2882         adcx    $zero,%r14              # cf=0
2883
2884         mov     %r8,3*8($tptr)          # t[3]
2885         mov     %r9,4*8($tptr)          # t[4]
2886
2887         mulx    3*8($aptr),%r8,%rbx     # a[3]*a[2]
2888         mulx    4*8($aptr),%r9,%rax     # a[4]*a[2]
2889         adcx    %r10,%r8
2890         adox    %rbx,%r9
2891         mulx    5*8($aptr),%r10,%rbx    # ...
2892         adcx    %r11,%r9
2893         adox    %rax,%r10
2894         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x30,0x00,0x00,0x00    # mulx  6*8($aptr),%r11,%rax
2895         adcx    %r12,%r10
2896         adox    %r13,%r11
2897         .byte   0xc4,0x62,0x9b,0xf6,0xae,0x38,0x00,0x00,0x00    # mulx  7*8($aptr),%r12,%r13
2898         .byte   0x3e
2899          mov    3*8($aptr),%rdx         # a[3]
2900         adcx    %rbx,%r11
2901         adox    %rax,%r12
2902         adcx    %r14,%r12
2903         mov     %r8,5*8($tptr)          # t[5]
2904         mov     %r9,6*8($tptr)          # t[6]
2905          mulx   4*8($aptr),%r8,%rax     # a[4]*a[3]
2906         adox    $zero,%r13              # of=0
2907         adcx    $zero,%r13              # cf=0
2908
2909         mulx    5*8($aptr),%r9,%rbx     # a[5]*a[3]
2910         adcx    %r10,%r8
2911         adox    %rax,%r9
2912         mulx    6*8($aptr),%r10,%rax    # ...
2913         adcx    %r11,%r9
2914         adox    %r12,%r10
2915         mulx    7*8($aptr),%r11,%r12
2916          mov    4*8($aptr),%rdx         # a[4]
2917          mov    5*8($aptr),%r14         # a[5]
2918         adcx    %rbx,%r10
2919         adox    %rax,%r11
2920          mov    6*8($aptr),%r15         # a[6]
2921         adcx    %r13,%r11
2922         adox    $zero,%r12              # of=0
2923         adcx    $zero,%r12              # cf=0
2924
2925         mov     %r8,7*8($tptr)          # t[7]
2926         mov     %r9,8*8($tptr)          # t[8]
2927
2928         mulx    %r14,%r9,%rax           # a[5]*a[4]
2929          mov    7*8($aptr),%r8          # a[7]
2930         adcx    %r10,%r9
2931         mulx    %r15,%r10,%rbx          # a[6]*a[4]
2932         adox    %rax,%r10
2933         adcx    %r11,%r10
2934         mulx    %r8,%r11,%rax           # a[7]*a[4]
2935          mov    %r14,%rdx               # a[5]
2936         adox    %rbx,%r11
2937         adcx    %r12,%r11
2938         #adox   $zero,%rax              # of=0
2939         adcx    $zero,%rax              # cf=0
2940
2941         mulx    %r15,%r14,%rbx          # a[6]*a[5]
2942         mulx    %r8,%r12,%r13           # a[7]*a[5]
2943          mov    %r15,%rdx               # a[6]
2944          lea    8*8($aptr),$aptr
2945         adcx    %r14,%r11
2946         adox    %rbx,%r12
2947         adcx    %rax,%r12
2948         adox    $zero,%r13
2949
2950         .byte   0x67,0x67
2951         mulx    %r8,%r8,%r14            # a[7]*a[6]
2952         adcx    %r8,%r13
2953         adcx    $zero,%r14
2954
2955         cmp     8+8(%rsp),$aptr
2956         je      .Lsqrx8x_outer_break
2957
2958         neg     $carry                  # mov $carry,%cf
2959         mov     \$-8,%rcx
2960         mov     $zero,%r15
2961         mov     8*8($tptr),%r8
2962         adcx    9*8($tptr),%r9          # +=t[9]
2963         adcx    10*8($tptr),%r10        # ...
2964         adcx    11*8($tptr),%r11
2965         adc     12*8($tptr),%r12
2966         adc     13*8($tptr),%r13
2967         adc     14*8($tptr),%r14
2968         adc     15*8($tptr),%r15
2969         lea     ($aptr),$aaptr
2970         lea     2*64($tptr),$tptr
2971         sbb     %rax,%rax               # mov %cf,$carry
2972
2973         mov     -64($aptr),%rdx         # a[0]
2974         mov     %rax,16+8(%rsp)         # offload $carry
2975         mov     $tptr,24+8(%rsp)
2976
2977         #lea    8*8($tptr),$tptr        # see 2*8*8($tptr) above
2978         xor     %eax,%eax               # cf=0, of=0
2979         jmp     .Lsqrx8x_loop
2980
2981 .align  32
2982 .Lsqrx8x_loop:
2983         mov     %r8,%rbx
2984         mulx    0*8($aaptr),%rax,%r8    # a[8]*a[i]
2985         adcx    %rax,%rbx               # +=t[8]
2986         adox    %r9,%r8
2987
2988         mulx    1*8($aaptr),%rax,%r9    # ...
2989         adcx    %rax,%r8
2990         adox    %r10,%r9
2991
2992         mulx    2*8($aaptr),%rax,%r10
2993         adcx    %rax,%r9
2994         adox    %r11,%r10
2995
2996         mulx    3*8($aaptr),%rax,%r11
2997         adcx    %rax,%r10
2998         adox    %r12,%r11
2999
3000         .byte   0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00    # mulx  4*8($aaptr),%rax,%r12
3001         adcx    %rax,%r11
3002         adox    %r13,%r12
3003
3004         mulx    5*8($aaptr),%rax,%r13
3005         adcx    %rax,%r12
3006         adox    %r14,%r13
3007
3008         mulx    6*8($aaptr),%rax,%r14
3009          mov    %rbx,($tptr,%rcx,8)     # store t[8+i]
3010          mov    \$0,%ebx
3011         adcx    %rax,%r13
3012         adox    %r15,%r14
3013
3014         .byte   0xc4,0x62,0xfb,0xf6,0xbd,0x38,0x00,0x00,0x00    # mulx  7*8($aaptr),%rax,%r15
3015          mov    8($aptr,%rcx,8),%rdx    # a[i]
3016         adcx    %rax,%r14
3017         adox    %rbx,%r15               # %rbx is 0, of=0
3018         adcx    %rbx,%r15               # cf=0
3019
3020         .byte   0x67
3021         inc     %rcx                    # of=0
3022         jnz     .Lsqrx8x_loop
3023
3024         lea     8*8($aaptr),$aaptr
3025         mov     \$-8,%rcx
3026         cmp     8+8(%rsp),$aaptr        # done?
3027         je      .Lsqrx8x_break
3028
3029         sub     16+8(%rsp),%rbx         # mov 16(%rsp),%cf
3030         .byte   0x66
3031         mov     -64($aptr),%rdx
3032         adcx    0*8($tptr),%r8
3033         adcx    1*8($tptr),%r9
3034         adc     2*8($tptr),%r10
3035         adc     3*8($tptr),%r11
3036         adc     4*8($tptr),%r12
3037         adc     5*8($tptr),%r13
3038         adc     6*8($tptr),%r14
3039         adc     7*8($tptr),%r15
3040         lea     8*8($tptr),$tptr
3041         .byte   0x67
3042         sbb     %rax,%rax               # mov %cf,%rax
3043         xor     %ebx,%ebx               # cf=0, of=0
3044         mov     %rax,16+8(%rsp)         # offload carry
3045         jmp     .Lsqrx8x_loop
3046
3047 .align  32
3048 .Lsqrx8x_break:
3049         sub     16+8(%rsp),%r8          # consume last carry
3050         mov     24+8(%rsp),$carry       # initial $tptr, borrow $carry
3051         mov     0*8($aptr),%rdx         # a[8], modulo-scheduled
3052         xor     %ebp,%ebp               # xor   $zero,$zero
3053         mov     %r8,0*8($tptr)
3054         cmp     $carry,$tptr            # cf=0, of=0
3055         je      .Lsqrx8x_outer_loop
3056
3057         mov     %r9,1*8($tptr)
3058          mov    1*8($carry),%r9
3059         mov     %r10,2*8($tptr)
3060          mov    2*8($carry),%r10
3061         mov     %r11,3*8($tptr)
3062          mov    3*8($carry),%r11
3063         mov     %r12,4*8($tptr)
3064          mov    4*8($carry),%r12
3065         mov     %r13,5*8($tptr)
3066          mov    5*8($carry),%r13
3067         mov     %r14,6*8($tptr)
3068          mov    6*8($carry),%r14
3069         mov     %r15,7*8($tptr)
3070          mov    7*8($carry),%r15
3071         mov     $carry,$tptr
3072         jmp     .Lsqrx8x_outer_loop
3073
3074 .align  32
3075 .Lsqrx8x_outer_break:
3076         mov     %r9,9*8($tptr)          # t[9]
3077          movq   %xmm3,%rcx              # -$num
3078         mov     %r10,10*8($tptr)        # ...
3079         mov     %r11,11*8($tptr)
3080         mov     %r12,12*8($tptr)
3081         mov     %r13,13*8($tptr)
3082         mov     %r14,14*8($tptr)
3083 ___
3084 }\f{
3085 my $i="%rcx";
3086 $code.=<<___;
3087         lea     48+8(%rsp),$tptr
3088         mov     ($aptr,$i),%rdx         # a[0]
3089
3090         mov     8($tptr),$A0[1]         # t[1]
3091         xor     $A0[0],$A0[0]           # t[0], of=0, cf=0
3092         mov     0+8(%rsp),$num          # restore $num
3093         adox    $A0[1],$A0[1]
3094          mov    16($tptr),$A1[0]        # t[2]  # prefetch
3095          mov    24($tptr),$A1[1]        # t[3]  # prefetch
3096         #jmp    .Lsqrx4x_shift_n_add    # happens to be aligned
3097
3098 .align  32
3099 .Lsqrx4x_shift_n_add:
3100         mulx    %rdx,%rax,%rbx
3101          adox   $A1[0],$A1[0]
3102         adcx    $A0[0],%rax
3103          .byte  0x48,0x8b,0x94,0x0e,0x08,0x00,0x00,0x00 # mov   8($aptr,$i),%rdx        # a[i+1]        # prefetch
3104          .byte  0x4c,0x8b,0x97,0x20,0x00,0x00,0x00      # mov   32($tptr),$A0[0]        # t[2*i+4]      # prefetch
3105          adox   $A1[1],$A1[1]
3106         adcx    $A0[1],%rbx
3107          mov    40($tptr),$A0[1]                # t[2*i+4+1]    # prefetch
3108         mov     %rax,0($tptr)
3109         mov     %rbx,8($tptr)
3110
3111         mulx    %rdx,%rax,%rbx
3112          adox   $A0[0],$A0[0]
3113         adcx    $A1[0],%rax
3114          mov    16($aptr,$i),%rdx       # a[i+2]        # prefetch
3115          mov    48($tptr),$A1[0]        # t[2*i+6]      # prefetch
3116          adox   $A0[1],$A0[1]
3117         adcx    $A1[1],%rbx
3118          mov    56($tptr),$A1[1]        # t[2*i+6+1]    # prefetch
3119         mov     %rax,16($tptr)
3120         mov     %rbx,24($tptr)
3121
3122         mulx    %rdx,%rax,%rbx
3123          adox   $A1[0],$A1[0]
3124         adcx    $A0[0],%rax
3125          mov    24($aptr,$i),%rdx       # a[i+3]        # prefetch
3126          lea    32($i),$i
3127          mov    64($tptr),$A0[0]        # t[2*i+8]      # prefetch
3128          adox   $A1[1],$A1[1]
3129         adcx    $A0[1],%rbx
3130          mov    72($tptr),$A0[1]        # t[2*i+8+1]    # prefetch
3131         mov     %rax,32($tptr)
3132         mov     %rbx,40($tptr)
3133
3134         mulx    %rdx,%rax,%rbx
3135          adox   $A0[0],$A0[0]
3136         adcx    $A1[0],%rax
3137         jrcxz   .Lsqrx4x_shift_n_add_break
3138          .byte  0x48,0x8b,0x94,0x0e,0x00,0x00,0x00,0x00 # mov   0($aptr,$i),%rdx        # a[i+4]        # prefetch
3139          adox   $A0[1],$A0[1]
3140         adcx    $A1[1],%rbx
3141          mov    80($tptr),$A1[0]        # t[2*i+10]     # prefetch
3142          mov    88($tptr),$A1[1]        # t[2*i+10+1]   # prefetch
3143         mov     %rax,48($tptr)
3144         mov     %rbx,56($tptr)
3145         lea     64($tptr),$tptr
3146         nop
3147         jmp     .Lsqrx4x_shift_n_add
3148
3149 .align  32
3150 .Lsqrx4x_shift_n_add_break:
3151         adcx    $A1[1],%rbx
3152         mov     %rax,48($tptr)
3153         mov     %rbx,56($tptr)
3154         lea     64($tptr),$tptr         # end of t[] buffer
3155 ___
3156 }\f
3157 ######################################################################
3158 # Montgomery reduction part, "word-by-word" algorithm.
3159 #
3160 # This new path is inspired by multiple submissions from Intel, by
3161 # Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
3162 # Vinodh Gopal...
3163 {
3164 my ($nptr,$carry,$m0)=("%rbp","%rsi","%rdx");
3165
3166 $code.=<<___;
3167         movq    %xmm2,$nptr
3168 __bn_sqrx8x_reduction:
3169         xor     %eax,%eax               # initial top-most carry bit
3170         mov     32+8(%rsp),%rbx         # n0
3171         mov     48+8(%rsp),%rdx         # "%r8", 8*0($tptr)
3172         lea     -8*8($nptr,$num),%rcx   # end of n[]
3173         #lea    48+8(%rsp,$num,2),$tptr # end of t[] buffer
3174         mov     %rcx, 0+8(%rsp)         # save end of n[]
3175         mov     $tptr,8+8(%rsp)         # save end of t[]
3176
3177         lea     48+8(%rsp),$tptr                # initial t[] window
3178         jmp     .Lsqrx8x_reduction_loop
3179
3180 .align  32
3181 .Lsqrx8x_reduction_loop:
3182         mov     8*1($tptr),%r9
3183         mov     8*2($tptr),%r10
3184         mov     8*3($tptr),%r11
3185         mov     8*4($tptr),%r12
3186         mov     %rdx,%r8
3187         imulq   %rbx,%rdx               # n0*a[i]
3188         mov     8*5($tptr),%r13
3189         mov     8*6($tptr),%r14
3190         mov     8*7($tptr),%r15
3191         mov     %rax,24+8(%rsp)         # store top-most carry bit
3192
3193         lea     8*8($tptr),$tptr
3194         xor     $carry,$carry           # cf=0,of=0
3195         mov     \$-8,%rcx
3196         jmp     .Lsqrx8x_reduce
3197
3198 .align  32
3199 .Lsqrx8x_reduce:
3200         mov     %r8, %rbx
3201         mulx    8*0($nptr),%rax,%r8     # n[0]
3202         adcx    %rbx,%rax               # discarded
3203         adox    %r9,%r8
3204
3205         mulx    8*1($nptr),%rbx,%r9     # n[1]
3206         adcx    %rbx,%r8
3207         adox    %r10,%r9
3208
3209         mulx    8*2($nptr),%rbx,%r10
3210         adcx    %rbx,%r9
3211         adox    %r11,%r10
3212
3213         mulx    8*3($nptr),%rbx,%r11
3214         adcx    %rbx,%r10
3215         adox    %r12,%r11
3216
3217         .byte   0xc4,0x62,0xe3,0xf6,0xa5,0x20,0x00,0x00,0x00    # mulx  8*4($nptr),%rbx,%r12
3218          mov    %rdx,%rax
3219          mov    %r8,%rdx
3220         adcx    %rbx,%r11
3221         adox    %r13,%r12
3222
3223          mulx   32+8(%rsp),%rbx,%rdx    # %rdx discarded
3224          mov    %rax,%rdx
3225          mov    %rax,64+48+8(%rsp,%rcx,8)       # put aside n0*a[i]
3226
3227         mulx    8*5($nptr),%rax,%r13
3228         adcx    %rax,%r12
3229         adox    %r14,%r13
3230
3231         mulx    8*6($nptr),%rax,%r14
3232         adcx    %rax,%r13
3233         adox    %r15,%r14
3234
3235         mulx    8*7($nptr),%rax,%r15
3236          mov    %rbx,%rdx
3237         adcx    %rax,%r14
3238         adox    $carry,%r15             # $carry is 0
3239         adcx    $carry,%r15             # cf=0
3240
3241         .byte   0x67,0x67,0x67
3242         inc     %rcx                    # of=0
3243         jnz     .Lsqrx8x_reduce
3244
3245         mov     $carry,%rax             # xor   %rax,%rax
3246         cmp     0+8(%rsp),$nptr         # end of n[]?
3247         jae     .Lsqrx8x_no_tail
3248
3249         mov     48+8(%rsp),%rdx         # pull n0*a[0]
3250         add     8*0($tptr),%r8
3251         lea     8*8($nptr),$nptr
3252         mov     \$-8,%rcx
3253         adcx    8*1($tptr),%r9
3254         adcx    8*2($tptr),%r10
3255         adc     8*3($tptr),%r11
3256         adc     8*4($tptr),%r12
3257         adc     8*5($tptr),%r13
3258         adc     8*6($tptr),%r14
3259         adc     8*7($tptr),%r15
3260         lea     8*8($tptr),$tptr
3261         sbb     %rax,%rax               # top carry
3262
3263         xor     $carry,$carry           # of=0, cf=0
3264         mov     %rax,16+8(%rsp)
3265         jmp     .Lsqrx8x_tail
3266
3267 .align  32
3268 .Lsqrx8x_tail:
3269         mov     %r8,%rbx
3270         mulx    8*0($nptr),%rax,%r8
3271         adcx    %rax,%rbx
3272         adox    %r9,%r8
3273
3274         mulx    8*1($nptr),%rax,%r9
3275         adcx    %rax,%r8
3276         adox    %r10,%r9
3277
3278         mulx    8*2($nptr),%rax,%r10
3279         adcx    %rax,%r9
3280         adox    %r11,%r10
3281
3282         mulx    8*3($nptr),%rax,%r11
3283         adcx    %rax,%r10
3284         adox    %r12,%r11
3285
3286         .byte   0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00    # mulx  8*4($nptr),%rax,%r12
3287         adcx    %rax,%r11
3288         adox    %r13,%r12
3289
3290         mulx    8*5($nptr),%rax,%r13
3291         adcx    %rax,%r12
3292         adox    %r14,%r13
3293
3294         mulx    8*6($nptr),%rax,%r14
3295         adcx    %rax,%r13
3296         adox    %r15,%r14
3297
3298         mulx    8*7($nptr),%rax,%r15
3299          mov    72+48+8(%rsp,%rcx,8),%rdx       # pull n0*a[i]
3300         adcx    %rax,%r14
3301         adox    $carry,%r15