f3d112f8ff89ca45ba9ee13d0e59c3094deaabaf
[openssl.git] / crypto / bn / asm / x86_64-mont.pl
1 #!/usr/bin/env perl
2
3 # ====================================================================
4 # Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
5 # project. Rights for redistribution and usage in source and binary
6 # forms are granted according to the OpenSSL license.
7 # ====================================================================
8
9 # October 2005.
10 #
11 # Montgomery multiplication routine for x86_64. While it gives modest
12 # 9% improvement of rsa4096 sign on Opteron, rsa512 sign runs more
13 # than twice, >2x, as fast. Most common rsa1024 sign is improved by
14 # respectful 50%. It remains to be seen if loop unrolling and
15 # dedicated squaring routine can provide further improvement...
16
17 $output=shift;
18 open STDOUT,"| $^X ../perlasm/x86_64-xlate.pl $output";
19
20 # int bn_mul_mont(
21 $rp="%rdi";     # BN_ULONG *rp,
22 $ap="%rsi";     # const BN_ULONG *ap,
23 $bp="%rdx";     # const BN_ULONG *bp,
24 $np="%rcx";     # const BN_ULONG *np,
25 $n0="%r8";      # BN_ULONG n0,
26 $num="%r9";     # int num);
27 $lo0="%r10";
28 $hi0="%r11";
29 $bp="%r12";     # reassign $bp
30 $hi1="%r13";
31 $i="%r14";
32 $j="%r15";
33 $m0="%rbx";
34 $m1="%rbp";
35
36 $code=<<___;
37 .text
38
39 .globl  bn_mul_mont
40 .type   bn_mul_mont,\@function,6
41 .align  16
42 bn_mul_mont:
43         push    %rbx
44         push    %rbp
45         push    %r12
46         push    %r13
47         push    %r14
48         push    %r15
49
50         lea     2($num),%rax
51         mov     %rsp,%rbp
52         neg     %rax
53         lea     (%rsp,%rax,8),%rsp      # tp=alloca(8*(num+2))
54         and     \$-1024,%rsp            # minimize TLB usage
55         mov     %rbp,8(%rsp,$num,8)     # tp[num+1]=%rsp
56         mov     %rdx,$bp                # $bp reassigned, remember?
57
58         xor     $i,$i                   # i=0
59         xor     $j,$j                   # j=0
60
61         mov     ($bp),$m0               # m0=bp[0]
62         mov     ($ap),%rax
63         mulq    $m0                     # ap[0]*bp[0]
64         mov     %rax,$lo0
65         mov     %rdx,$hi0
66
67         imulq   $n0,%rax                # "tp[0]"*n0
68         mov     %rax,$m1
69
70         mulq    ($np)                   # np[0]*m1
71         add     $lo0,%rax               # discarded
72         adc     \$0,%rdx
73         mov     %rdx,$hi1
74
75         lea     1($j),$j                # j++
76 .L1st:
77         mov     ($ap,$j,8),%rax
78         mulq    $m0                     # ap[j]*bp[0]
79         add     $hi0,%rax
80         adc     \$0,%rdx
81         mov     %rax,$lo0
82         mov     %rdx,$hi0
83
84         mov     ($np,$j,8),%rax
85         mulq    $m1                     # np[j]*m1
86         add     $hi1,%rax
87         adc     \$0,%rdx
88         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[0]
89         adc     \$0,%rdx
90         mov     %rax,-8(%rsp,$j,8)      # tp[j-1]
91         mov     %rdx,$hi1
92
93         lea     1($j),$j                # j++
94         cmp     $num,$j
95         jl      .L1st
96
97         xor     %rdx,%rdx
98         add     $hi0,$hi1
99         adc     \$0,%rdx
100         mov     $hi1,-8(%rsp,$num,8)
101         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
102
103         lea     1($i),$i                # i++
104 .align  4
105 .Louter:
106         xor     $j,$j                   # j=0
107
108         mov     ($bp,$i,8),$m0          # m0=bp[i]
109         mov     ($ap),%rax              # ap[0]
110         mulq    $m0                     # ap[0]*bp[i]
111         add     (%rsp),%rax             # ap[0]*bp[i]+tp[0]
112         adc     \$0,%rdx
113         mov     %rax,$lo0
114         mov     %rdx,$hi0
115
116         imulq   $n0,%rax                # tp[0]*n0
117         mov     %rax,$m1
118
119         mulq    ($np,$j,8)              # np[0]*m1
120         add     $lo0,%rax               # discarded
121         adc     \$0,%rdx
122         mov     %rdx,$hi1
123
124         lea     1($j),$j                # j++
125 .align  4
126 .Linner:
127         mov     ($ap,$j,8),%rax
128         mulq    $m0                     # ap[j]*bp[i]
129         add     $hi0,%rax
130         adc     \$0,%rdx
131         add     (%rsp,$j,8),%rax        # ap[j]*bp[i]+tp[j]
132         adc     \$0,%rdx
133         mov     %rax,$lo0
134         mov     %rdx,$hi0
135
136         mov     ($np,$j,8),%rax
137         mulq    $m1                     # np[j]*m1
138         add     $hi1,%rax
139         adc     \$0,%rdx
140         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[i]+tp[j]
141         adc     \$0,%rdx
142         mov     %rax,-8(%rsp,$j,8)      # tp[j-1]
143         mov     %rdx,$hi1
144
145         lea     1($j),$j                # j++
146         cmp     $num,$j
147         jl      .Linner
148
149         xor     %rdx,%rdx
150         add     $hi0,$hi1
151         adc     \$0,%rdx
152         add     (%rsp,$num,8),$hi1      # pull upmost overflow bit
153         adc     \$0,%rdx
154         mov     $hi1,-8(%rsp,$num,8)
155         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
156
157         lea     1($i),$i                # i++
158         cmp     $num,$i
159         jl      .Louter
160
161         xor     $i,$i                   # i=0
162         lea     -1($num),$j             # j=num-1
163         cmp     \$0,%rdx                # %rdx still holds upmost overflow bit
164         jnz     .Lsub                   # CF is cleared by compare with 0
165         mov     (%rsp,$j,8),%rax
166         cmp     ($np,$j,8),%rax         # tp[num-1]-np[num-1]
167         jae     .Lsub                   # if taken CF was cleared by above cmp
168 .align  4
169 .Lcopy:
170         mov     (%rsp,$j,8),%rax
171         mov     %rax,($rp,$j,8)         # rp[i]=tp[i]
172         mov     $i,(%rsp,$j,8)          # zap temporary vector
173         dec     $j
174         jge     .Lcopy
175 .align  4
176 .Lexit:
177         mov     8(%rsp,$num,8),%rsp     # restore %rsp
178         mov     \$1,%rax
179         pop     %r15
180         pop     %r14
181         pop     %r13
182         pop     %r12
183         pop     %rbp
184         pop     %rbx
185         ret
186
187 .align  16
188 .Lsub:  mov     (%rsp,$i,8),%rax
189         sbb     ($np,$i,8),%rax
190         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[j]
191         lea     1($i),$i                # i++
192         dec     $j                      # doesn't affect CF!
193         jge     .Lsub
194         lea     -1($num),$j             # j=num-1
195         sbb     \$0,%rdx
196         jc      .Lcopy                  # tp was less than np
197 .align  4
198 .Lzap:  mov     $i,(%rsp,$j,8)          # zap temporary vector
199         dec     $j
200         jge     .Lzap
201         jmp     .Lexit
202 .size   bn_mul_mont,.-bn_mul_mont
203 ___
204
205 print $code;
206 close STDOUT;