rc4-x86_64.pl: "Westmere" optimization.
[openssl.git] / crypto / rc4 / asm / rc4-x86_64.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 # 2.22x RC4 tune-up:-) It should be noted though that my hand [as in
11 # "hand-coded assembler"] doesn't stand for the whole improvement
12 # coefficient. It turned out that eliminating RC4_CHAR from config
13 # line results in ~40% improvement (yes, even for C implementation).
14 # Presumably it has everything to do with AMD cache architecture and
15 # RAW or whatever penalties. Once again! The module *requires* config
16 # line *without* RC4_CHAR! As for coding "secret," I bet on partial
17 # register arithmetics. For example instead of 'inc %r8; and $255,%r8'
18 # I simply 'inc %r8b'. Even though optimization manual discourages
19 # to operate on partial registers, it turned out to be the best bet.
20 # At least for AMD... How IA32E would perform remains to be seen...
21
22 # As was shown by Marc Bevand reordering of couple of load operations
23 # results in even higher performance gain of 3.3x:-) At least on
24 # Opteron... For reference, 1x in this case is RC4_CHAR C-code
25 # compiled with gcc 3.3.2, which performs at ~54MBps per 1GHz clock.
26 # Latter means that if you want to *estimate* what to expect from
27 # *your* Opteron, then multiply 54 by 3.3 and clock frequency in GHz.
28
29 # Intel P4 EM64T core was found to run the AMD64 code really slow...
30 # The only way to achieve comparable performance on P4 was to keep
31 # RC4_CHAR. Kind of ironic, huh? As it's apparently impossible to
32 # compose blended code, which would perform even within 30% marginal
33 # on either AMD and Intel platforms, I implement both cases. See
34 # rc4_skey.c for further details...
35
36 # P4 EM64T core appears to be "allergic" to 64-bit inc/dec. Replacing 
37 # those with add/sub results in 50% performance improvement of folded
38 # loop...
39
40 # As was shown by Zou Nanhai loop unrolling can improve Intel EM64T
41 # performance by >30% [unlike P4 32-bit case that is]. But this is
42 # provided that loads are reordered even more aggressively! Both code
43 # pathes, AMD64 and EM64T, reorder loads in essentially same manner
44 # as my IA-64 implementation. On Opteron this resulted in modest 5%
45 # improvement [I had to test it], while final Intel P4 performance
46 # achieves respectful 432MBps on 2.8GHz processor now. For reference.
47 # If executed on Xeon, current RC4_CHAR code-path is 2.7x faster than
48 # RC4_INT code-path. While if executed on Opteron, it's only 25%
49 # slower than the RC4_INT one [meaning that if CPU ยต-arch detection
50 # is not implemented, then this final RC4_CHAR code-path should be
51 # preferred, as it provides better *all-round* performance].
52
53 # Intel Core2 was observed to perform poorly on both code paths:-( It
54 # apparently suffers from some kind of partial register stall, which
55 # occurs in 64-bit mode only [as virtually identical 32-bit loop was
56 # observed to outperform 64-bit one by almost 50%]. Adding two movzb to
57 # cloop1 boosts its performance by 80%! This loop appears to be optimal
58 # fit for Core2 and therefore the code was modified to skip cloop8 on
59 # this CPU.
60
61 # Intel Westmere was observed to perform suboptimally. Adding yet
62 # another movzb to cloop1 improved performance by almost 50%! Core2
63 # performance is improved too, but nominally...
64
65 $flavour = shift;
66 $output  = shift;
67 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
68
69 $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
70
71 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
72 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
73 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
74 die "can't locate x86_64-xlate.pl";
75
76 open STDOUT,"| $^X $xlate $flavour $output";
77
78 $dat="%rdi";        # arg1
79 $len="%rsi";        # arg2
80 $inp="%rdx";        # arg3
81 $out="%rcx";        # arg4
82
83 @XX=("%r8","%r10");
84 @TX=("%r9","%r11");
85 $YY="%r12";
86 $TY="%r13";
87
88 $code=<<___;
89 .text
90
91 .globl  RC4
92 .type   RC4,\@function,4
93 .align  16
94 RC4:    or      $len,$len
95         jne     .Lentry
96         ret
97 .Lentry:
98         push    %rbx
99         push    %r12
100         push    %r13
101 .Lprologue:
102
103         add     \$8,$dat
104         movl    -8($dat),$XX[0]#d
105         movl    -4($dat),$YY#d
106         cmpl    \$-1,256($dat)
107         je      .LRC4_CHAR
108         inc     $XX[0]#b
109         movl    ($dat,$XX[0],4),$TX[0]#d
110         test    \$-8,$len
111         jz      .Lloop1
112         jmp     .Lloop8
113 .align  16
114 .Lloop8:
115 ___
116 for ($i=0;$i<8;$i++) {
117 $code.=<<___;
118         add     $TX[0]#b,$YY#b
119         mov     $XX[0],$XX[1]
120         movl    ($dat,$YY,4),$TY#d
121         ror     \$8,%rax                        # ror is redundant when $i=0
122         inc     $XX[1]#b
123         movl    ($dat,$XX[1],4),$TX[1]#d
124         cmp     $XX[1],$YY
125         movl    $TX[0]#d,($dat,$YY,4)
126         cmove   $TX[0],$TX[1]
127         movl    $TY#d,($dat,$XX[0],4)
128         add     $TX[0]#b,$TY#b
129         movb    ($dat,$TY,4),%al
130 ___
131 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
132 }
133 $code.=<<___;
134         ror     \$8,%rax
135         sub     \$8,$len
136
137         xor     ($inp),%rax
138         add     \$8,$inp
139         mov     %rax,($out)
140         add     \$8,$out
141
142         test    \$-8,$len
143         jnz     .Lloop8
144         cmp     \$0,$len
145         jne     .Lloop1
146         jmp     .Lexit
147
148 .align  16
149 .Lloop1:
150         add     $TX[0]#b,$YY#b
151         movl    ($dat,$YY,4),$TY#d
152         movl    $TX[0]#d,($dat,$YY,4)
153         movl    $TY#d,($dat,$XX[0],4)
154         add     $TY#b,$TX[0]#b
155         inc     $XX[0]#b
156         movl    ($dat,$TX[0],4),$TY#d
157         movl    ($dat,$XX[0],4),$TX[0]#d
158         xorb    ($inp),$TY#b
159         inc     $inp
160         movb    $TY#b,($out)
161         inc     $out
162         dec     $len
163         jnz     .Lloop1
164         jmp     .Lexit
165
166 .align  16
167 .LRC4_CHAR:
168         add     \$1,$XX[0]#b
169         movzb   ($dat,$XX[0]),$TX[0]#d
170         test    \$-8,$len
171         jz      .Lcloop1
172         cmpl    \$0,260($dat)
173         jnz     .Lcloop1
174         jmp     .Lcloop8
175 .align  16
176 .Lcloop8:
177         mov     ($inp),%eax
178         mov     4($inp),%ebx
179 ___
180 # unroll 2x4-wise, because 64-bit rotates kill Intel P4...
181 for ($i=0;$i<4;$i++) {
182 $code.=<<___;
183         add     $TX[0]#b,$YY#b
184         lea     1($XX[0]),$XX[1]
185         movzb   ($dat,$YY),$TY#d
186         movzb   $XX[1]#b,$XX[1]#d
187         movzb   ($dat,$XX[1]),$TX[1]#d
188         movb    $TX[0]#b,($dat,$YY)
189         cmp     $XX[1],$YY
190         movb    $TY#b,($dat,$XX[0])
191         jne     .Lcmov$i                        # Intel cmov is sloooow...
192         mov     $TX[0],$TX[1]
193 .Lcmov$i:
194         add     $TX[0]#b,$TY#b
195         xor     ($dat,$TY),%al
196         ror     \$8,%eax
197 ___
198 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
199 }
200 for ($i=4;$i<8;$i++) {
201 $code.=<<___;
202         add     $TX[0]#b,$YY#b
203         lea     1($XX[0]),$XX[1]
204         movzb   ($dat,$YY),$TY#d
205         movzb   $XX[1]#b,$XX[1]#d
206         movzb   ($dat,$XX[1]),$TX[1]#d
207         movb    $TX[0]#b,($dat,$YY)
208         cmp     $XX[1],$YY
209         movb    $TY#b,($dat,$XX[0])
210         jne     .Lcmov$i                        # Intel cmov is sloooow...
211         mov     $TX[0],$TX[1]
212 .Lcmov$i:
213         add     $TX[0]#b,$TY#b
214         xor     ($dat,$TY),%bl
215         ror     \$8,%ebx
216 ___
217 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
218 }
219 $code.=<<___;
220         lea     -8($len),$len
221         mov     %eax,($out)
222         lea     8($inp),$inp
223         mov     %ebx,4($out)
224         lea     8($out),$out
225
226         test    \$-8,$len
227         jnz     .Lcloop8
228         cmp     \$0,$len
229         jne     .Lcloop1
230         jmp     .Lexit
231 ___
232 $code.=<<___;
233 .align  16
234 .Lcloop1:
235         add     $TX[0]#b,$YY#b
236         movzb   $YY#b,$YY#d
237         movzb   ($dat,$YY),$TY#d
238         movb    $TX[0]#b,($dat,$YY)
239         movb    $TY#b,($dat,$XX[0])
240         add     $TX[0]#b,$TY#b
241         add     \$1,$XX[0]#b
242         movzb   $TY#b,$TY#d
243         movzb   $XX[0]#b,$XX[0]#d
244         movzb   ($dat,$TY),$TY#d
245         movzb   ($dat,$XX[0]),$TX[0]#d
246         xorb    ($inp),$TY#b
247         lea     1($inp),$inp
248         movb    $TY#b,($out)
249         lea     1($out),$out
250         sub     \$1,$len
251         jnz     .Lcloop1
252         jmp     .Lexit
253
254 .align  16
255 .Lexit:
256         sub     \$1,$XX[0]#b
257         movl    $XX[0]#d,-8($dat)
258         movl    $YY#d,-4($dat)
259
260         mov     (%rsp),%r13
261         mov     8(%rsp),%r12
262         mov     16(%rsp),%rbx
263         add     \$24,%rsp
264 .Lepilogue:
265         ret
266 .size   RC4,.-RC4
267 ___
268
269 $idx="%r8";
270 $ido="%r9";
271
272 $code.=<<___;
273 .extern OPENSSL_ia32cap_P
274 .globl  RC4_set_key
275 .type   RC4_set_key,\@function,3
276 .align  16
277 RC4_set_key:
278         lea     8($dat),$dat
279         lea     ($inp,$len),$inp
280         neg     $len
281         mov     $len,%rcx
282         xor     %eax,%eax
283         xor     $ido,$ido
284         xor     %r10,%r10
285         xor     %r11,%r11
286
287         mov     OPENSSL_ia32cap_P(%rip),$idx#d
288         bt      \$20,$idx#d
289         jnc     .Lw1stloop
290         bt      \$30,$idx#d
291         setc    $ido#b
292         mov     $ido#d,260($dat)
293         jmp     .Lc1stloop
294
295 .align  16
296 .Lw1stloop:
297         mov     %eax,($dat,%rax,4)
298         add     \$1,%al
299         jnc     .Lw1stloop
300
301         xor     $ido,$ido
302         xor     $idx,$idx
303 .align  16
304 .Lw2ndloop:
305         mov     ($dat,$ido,4),%r10d
306         add     ($inp,$len,1),$idx#b
307         add     %r10b,$idx#b
308         add     \$1,$len
309         mov     ($dat,$idx,4),%r11d
310         cmovz   %rcx,$len
311         mov     %r10d,($dat,$idx,4)
312         mov     %r11d,($dat,$ido,4)
313         add     \$1,$ido#b
314         jnc     .Lw2ndloop
315         jmp     .Lexit_key
316
317 .align  16
318 .Lc1stloop:
319         mov     %al,($dat,%rax)
320         add     \$1,%al
321         jnc     .Lc1stloop
322
323         xor     $ido,$ido
324         xor     $idx,$idx
325 .align  16
326 .Lc2ndloop:
327         mov     ($dat,$ido),%r10b
328         add     ($inp,$len),$idx#b
329         add     %r10b,$idx#b
330         add     \$1,$len
331         mov     ($dat,$idx),%r11b
332         jnz     .Lcnowrap
333         mov     %rcx,$len
334 .Lcnowrap:
335         mov     %r10b,($dat,$idx)
336         mov     %r11b,($dat,$ido)
337         add     \$1,$ido#b
338         jnc     .Lc2ndloop
339         movl    \$-1,256($dat)
340
341 .align  16
342 .Lexit_key:
343         xor     %eax,%eax
344         mov     %eax,-8($dat)
345         mov     %eax,-4($dat)
346         ret
347 .size   RC4_set_key,.-RC4_set_key
348
349 .globl  RC4_options
350 .type   RC4_options,\@abi-omnipotent
351 .align  16
352 RC4_options:
353         lea     .Lopts(%rip),%rax
354         mov     OPENSSL_ia32cap_P(%rip),%edx
355         bt      \$20,%edx
356         jnc     .Ldone
357         add     \$12,%rax
358         bt      \$30,%edx
359         jnc     .Ldone
360         add     \$13,%rax
361 .Ldone:
362         ret
363 .align  64
364 .Lopts:
365 .asciz  "rc4(8x,int)"
366 .asciz  "rc4(8x,char)"
367 .asciz  "rc4(1x,char)"
368 .asciz  "RC4 for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
369 .align  64
370 .size   RC4_options,.-RC4_options
371 ___
372
373 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
374 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
375 if ($win64) {
376 $rec="%rcx";
377 $frame="%rdx";
378 $context="%r8";
379 $disp="%r9";
380
381 $code.=<<___;
382 .extern __imp_RtlVirtualUnwind
383 .type   stream_se_handler,\@abi-omnipotent
384 .align  16
385 stream_se_handler:
386         push    %rsi
387         push    %rdi
388         push    %rbx
389         push    %rbp
390         push    %r12
391         push    %r13
392         push    %r14
393         push    %r15
394         pushfq
395         sub     \$64,%rsp
396
397         mov     120($context),%rax      # pull context->Rax
398         mov     248($context),%rbx      # pull context->Rip
399
400         lea     .Lprologue(%rip),%r10
401         cmp     %r10,%rbx               # context->Rip<prologue label
402         jb      .Lin_prologue
403
404         mov     152($context),%rax      # pull context->Rsp
405
406         lea     .Lepilogue(%rip),%r10
407         cmp     %r10,%rbx               # context->Rip>=epilogue label
408         jae     .Lin_prologue
409
410         lea     24(%rax),%rax
411
412         mov     -8(%rax),%rbx
413         mov     -16(%rax),%r12
414         mov     -24(%rax),%r13
415         mov     %rbx,144($context)      # restore context->Rbx
416         mov     %r12,216($context)      # restore context->R12
417         mov     %r13,224($context)      # restore context->R13
418
419 .Lin_prologue:
420         mov     8(%rax),%rdi
421         mov     16(%rax),%rsi
422         mov     %rax,152($context)      # restore context->Rsp
423         mov     %rsi,168($context)      # restore context->Rsi
424         mov     %rdi,176($context)      # restore context->Rdi
425
426         jmp     .Lcommon_seh_exit
427 .size   stream_se_handler,.-stream_se_handler
428
429 .type   key_se_handler,\@abi-omnipotent
430 .align  16
431 key_se_handler:
432         push    %rsi
433         push    %rdi
434         push    %rbx
435         push    %rbp
436         push    %r12
437         push    %r13
438         push    %r14
439         push    %r15
440         pushfq
441         sub     \$64,%rsp
442
443         mov     152($context),%rax      # pull context->Rsp
444         mov     8(%rax),%rdi
445         mov     16(%rax),%rsi
446         mov     %rsi,168($context)      # restore context->Rsi
447         mov     %rdi,176($context)      # restore context->Rdi
448
449 .Lcommon_seh_exit:
450
451         mov     40($disp),%rdi          # disp->ContextRecord
452         mov     $context,%rsi           # context
453         mov     \$154,%ecx              # sizeof(CONTEXT)
454         .long   0xa548f3fc              # cld; rep movsq
455
456         mov     $disp,%rsi
457         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
458         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
459         mov     0(%rsi),%r8             # arg3, disp->ControlPc
460         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
461         mov     40(%rsi),%r10           # disp->ContextRecord
462         lea     56(%rsi),%r11           # &disp->HandlerData
463         lea     24(%rsi),%r12           # &disp->EstablisherFrame
464         mov     %r10,32(%rsp)           # arg5
465         mov     %r11,40(%rsp)           # arg6
466         mov     %r12,48(%rsp)           # arg7
467         mov     %rcx,56(%rsp)           # arg8, (NULL)
468         call    *__imp_RtlVirtualUnwind(%rip)
469
470         mov     \$1,%eax                # ExceptionContinueSearch
471         add     \$64,%rsp
472         popfq
473         pop     %r15
474         pop     %r14
475         pop     %r13
476         pop     %r12
477         pop     %rbp
478         pop     %rbx
479         pop     %rdi
480         pop     %rsi
481         ret
482 .size   key_se_handler,.-key_se_handler
483
484 .section        .pdata
485 .align  4
486         .rva    .LSEH_begin_RC4
487         .rva    .LSEH_end_RC4
488         .rva    .LSEH_info_RC4
489
490         .rva    .LSEH_begin_RC4_set_key
491         .rva    .LSEH_end_RC4_set_key
492         .rva    .LSEH_info_RC4_set_key
493
494 .section        .xdata
495 .align  8
496 .LSEH_info_RC4:
497         .byte   9,0,0,0
498         .rva    stream_se_handler
499 .LSEH_info_RC4_set_key:
500         .byte   9,0,0,0
501         .rva    key_se_handler
502 ___
503 }
504
505 $code =~ s/#([bwd])/$1/gm;
506
507 print $code;
508
509 close STDOUT;