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