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