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