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