2 # Copyright 2011-2016 The OpenSSL Project Authors. All Rights Reserved.
4 # Licensed under the Apache License 2.0 (the "License"). You may not use
5 # this file except in compliance with the License. You can obtain a copy
6 # in the file LICENSE in the source distribution or at
7 # https://www.openssl.org/source/license.html
10 # ====================================================================
11 # Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
12 # project. The module is, however, dual licensed under OpenSSL and
13 # CRYPTOGAMS licenses depending on where you obtain it. For further
14 # details see http://www.openssl.org/~appro/cryptogams/.
15 # ====================================================================
19 # This is RC4+MD5 "stitch" implementation. The idea, as spelled in
20 # http://download.intel.com/design/intarch/papers/323686.pdf, is that
21 # since both algorithms exhibit instruction-level parallelism, ILP,
22 # below theoretical maximum, interleaving them would allow to utilize
23 # processor resources better and achieve better performance. RC4
24 # instruction sequence is virtually identical to rc4-x86_64.pl, which
25 # is heavily based on submission by Maxim Perminov, Maxim Locktyukhin
26 # and Jim Guilford of Intel. MD5 is fresh implementation aiming to
27 # minimize register usage, which was used as "main thread" with RC4
28 # weaved into it, one RC4 round per one MD5 round. In addition to the
29 # stiched subroutine the script can generate standalone replacement
30 # md5_block_asm_data_order and RC4. Below are performance numbers in
31 # cycles per processed byte, less is better, for these the standalone
32 # subroutines, sum of them, and stitched one:
34 # RC4 MD5 RC4+MD5 stitch gain
35 # Opteron 6.5(*) 5.4 11.9 7.0 +70%(*)
36 # Core2 6.5 5.8 12.3 7.7 +60%
37 # Westmere 4.3 5.2 9.5 7.0 +36%
38 # Sandy Bridge 4.2 5.5 9.7 6.8 +43%
39 # Ivy Bridge 4.1 5.2 9.3 6.0 +54%
40 # Haswell 4.0 5.0 9.0 5.7 +60%
41 # Skylake 6.3(**) 5.0 11.3 5.3 +110%
42 # Atom 9.3 6.5 15.8 11.1 +42%
43 # VIA Nano 6.3 5.4 11.7 8.6 +37%
44 # Bulldozer 4.5 5.4 9.9 7.7 +29%
46 # (*) rc4-x86_64.pl delivers 5.3 on Opteron, so real improvement
48 # (**) unidentified anomaly;
50 my ($rc4,$md5)=(1,1); # what to generate?
51 my $D="#" if (!$md5); # if set to "#", MD5 is stitched into RC4(),
52 # but its result is discarded. Idea here is
53 # to be able to use 'openssl speed rc4' for
54 # benchmarking the stitched subroutine...
56 # $output is the last argument if it looks like a file (it has an extension)
57 # $flavour is the first argument if it doesn't look like a file
58 my $output = $#ARGV >= 0 && $ARGV[$#ARGV] =~ m|\.\w+$| ? pop : undef;
59 my $flavour = $#ARGV >= 0 && $ARGV[0] !~ m|\.| ? shift : undef;
61 my $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
63 $0 =~ m/(.*[\/\\])[^\/\\]+$/; my $dir=$1; my $xlate;
64 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
65 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
66 die "can't locate x86_64-xlate.pl";
68 open OUT,"| \"$^X\" \"$xlate\" $flavour \"$output\""
69 or die "can't call $xlate: $!";
72 my ($dat,$in0,$out,$ctx,$inp,$len, $func,$nargs);
75 ($dat,$len,$in0,$out) = ("%rdi","%rsi","%rdx","%rcx");
76 $func="RC4"; $nargs=4;
77 } elsif ($md5 && !$rc4) {
78 ($ctx,$inp,$len) = ("%rdi","%rsi","%rdx");
79 $func="md5_block_asm_data_order"; $nargs=3;
81 ($dat,$in0,$out,$ctx,$inp,$len) = ("%rdi","%rsi","%rdx","%rcx","%r8","%r9");
82 $func="rc4_md5_enc"; $nargs=6;
85 # const void *in0, # RC4 input
86 # void *out, # RC4 output
88 # const void *inp, # MD5 input
89 # size_t len); # number of 64-byte blocks
92 my @K=( 0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
93 0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,
94 0x698098d8,0x8b44f7af,0xffff5bb1,0x895cd7be,
95 0x6b901122,0xfd987193,0xa679438e,0x49b40821,
97 0xf61e2562,0xc040b340,0x265e5a51,0xe9b6c7aa,
98 0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
99 0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,
100 0xa9e3e905,0xfcefa3f8,0x676f02d9,0x8d2a4c8a,
102 0xfffa3942,0x8771f681,0x6d9d6122,0xfde5380c,
103 0xa4beea44,0x4bdecfa9,0xf6bb4b60,0xbebfbc70,
104 0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
105 0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,
107 0xf4292244,0x432aff97,0xab9423a7,0xfc93a039,
108 0x655b59c3,0x8f0ccc92,0xffeff47d,0x85845dd1,
109 0x6fa87e4f,0xfe2ce6e0,0xa3014314,0x4e0811a1,
110 0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391 );
112 my @V=("%r8d","%r9d","%r10d","%r11d"); # MD5 registers
115 my @XX=("%rbp","%rsi"); # RC4 registers
116 my @TX=("%rax","%rbx");
120 my $MOD=32; # 16, 32 or 64
127 .type $func,\@function,$nargs
145 .cfi_adjust_cfa_offset 40
150 $D#md5# mov $ctx,%r11 # reassign arguments
154 $D#md5# mov $inp,%r15
156 $ctx="%r11" if ($md5); # reassign arguments
160 $inp="%r15" if ($md5);
161 $inp=$in0 if (!$md5);
167 mov -8($dat),$XX[0]#b
172 movl ($dat,$XX[0],4),$TX[0]#d
174 $code.=<<___ if (!$md5);
179 and \$`$MOD-1`,$TX[1]
180 jz .Loop${MOD}_is_hot
184 movl ($dat,$YY,4),$TY#d
185 movl $TX[0]#d,($dat,$YY,4)
186 movl $TY#d,($dat,$XX[0],4)
189 movl ($dat,$TX[0],4),$TY#d
190 movl ($dat,$XX[0],4),$TX[0]#d
192 movb $TY#b,($out,$in0)
195 jnz .Loop${MOD}_warmup
202 mov $len,32(%rsp) # save original $len
203 shr \$6,$len # number of 64-byte blocks
205 if ($D && !$md5) { # stitch in dummy MD5
216 #rc4# add $TX[0]#b,$YY#b
217 #rc4# lea ($dat,$XX[0],4),$XX[1]
219 add $inp,$len # pointer to the end of input
222 #md5# mov $ctx,24(%rsp) # save pointer to MD5_CTX
223 #md5# mov 0*4($ctx),$V[0] # load current hash value from MD5_CTX
224 #md5# mov 1*4($ctx),$V[1]
225 #md5# mov 2*4($ctx),$V[2]
226 #md5# mov 3*4($ctx),$V[3]
231 #md5# mov $V[0],0*4(%rsp) # put aside current hash value
232 #md5# mov $V[1],1*4(%rsp)
233 #md5# mov $V[2],2*4(%rsp)
234 #md5# mov $V[3],$tmp # forward reference
235 #md5# mov $V[3],3*4(%rsp)
239 my ($i,$a,$b,$c,$d)=@_;
240 my @rot0=(7,12,17,22);
243 my $xmm="%xmm".($j&1);
244 $code.=" movdqu ($in0),%xmm2\n" if ($rc4 && $j==15);
245 $code.=" add \$$MOD,$XX[0]#b\n" if ($rc4 && $j==15 && $k==$MOD-1);
246 $code.=" pxor $xmm,$xmm\n" if ($rc4 && $j<=1);
248 #rc4# movl ($dat,$YY,4),$TY#d
250 #rc4# movl $TX[0]#d,($dat,$YY,4)
252 #md5# add 4*`$j`($inp),$a
253 #rc4# add $TY#b,$TX[0]#b
254 #rc4# movl `4*(($k+1)%$MOD)`(`$k==$MOD-1?"$dat,$XX[0],4":"$XX[1]"`),$TX[1]#d
255 #md5# add \$$K[$i],$a
257 #rc4# movz $TX[0]#b,$TX[0]#d
258 #rc4# movl $TY#d,4*$k($XX[1])
260 #rc4# add $TX[1]#b,$YY#b
261 #md5# rol \$$rot0[$j%4],$a
262 #md5# mov `$j==15?"$b":"$c"`,$tmp # forward reference
263 #rc4# pinsrw \$`($j>>1)&7`,($dat,$TX[0],4),$xmm\n
266 $code.=<<___ if ($rc4 && $j==15 && $k==$MOD-1);
268 xor $YY,$YY # keyword to partial register
270 lea ($dat,$XX[0],4),$XX[1]
272 $code.=<<___ if ($rc4 && $j==15);
279 my ($i,$a,$b,$c,$d)=@_;
280 my @rot1=(5,9,14,20);
283 my $xmm="%xmm".($j&1);
284 $code.=" movdqu 16($in0),%xmm3\n" if ($rc4 && $j==15);
285 $code.=" add \$$MOD,$XX[0]#b\n" if ($rc4 && $j==15 && $k==$MOD-1);
286 $code.=" pxor $xmm,$xmm\n" if ($rc4 && $j<=1);
288 #rc4# movl ($dat,$YY,4),$TY#d
290 #rc4# movl $TX[0]#d,($dat,$YY,4)
292 #md5# add 4*`((1+5*$j)%16)`($inp),$a
293 #rc4# add $TY#b,$TX[0]#b
294 #rc4# movl `4*(($k+1)%$MOD)`(`$k==$MOD-1?"$dat,$XX[0],4":"$XX[1]"`),$TX[1]#d
295 #md5# add \$$K[$i],$a
297 #rc4# movz $TX[0]#b,$TX[0]#d
298 #rc4# movl $TY#d,4*$k($XX[1])
300 #rc4# add $TX[1]#b,$YY#b
301 #md5# rol \$$rot1[$j%4],$a
302 #md5# mov `$j==15?"$c":"$b"`,$tmp # forward reference
303 #rc4# pinsrw \$`($j>>1)&7`,($dat,$TX[0],4),$xmm\n
306 $code.=<<___ if ($rc4 && $j==15 && $k==$MOD-1);
308 xor $YY,$YY # keyword to partial register
310 lea ($dat,$XX[0],4),$XX[1]
312 $code.=<<___ if ($rc4 && $j==15);
319 my ($i,$a,$b,$c,$d)=@_;
320 my @rot2=(4,11,16,23);
323 my $xmm="%xmm".($j&1);
324 $code.=" movdqu 32($in0),%xmm4\n" if ($rc4 && $j==15);
325 $code.=" add \$$MOD,$XX[0]#b\n" if ($rc4 && $j==15 && $k==$MOD-1);
326 $code.=" pxor $xmm,$xmm\n" if ($rc4 && $j<=1);
328 #rc4# movl ($dat,$YY,4),$TY#d
330 #rc4# movl $TX[0]#d,($dat,$YY,4)
332 #md5# add 4*`((5+3*$j)%16)`($inp),$a
333 #rc4# add $TY#b,$TX[0]#b
334 #rc4# movl `4*(($k+1)%$MOD)`(`$k==$MOD-1?"$dat,$XX[0],4":"$XX[1]"`),$TX[1]#d
335 #md5# add \$$K[$i],$a
336 #rc4# movz $TX[0]#b,$TX[0]#d
338 #rc4# movl $TY#d,4*$k($XX[1])
339 #rc4# add $TX[1]#b,$YY#b
340 #md5# rol \$$rot2[$j%4],$a
341 #md5# mov `$j==15?"\\\$-1":"$c"`,$tmp # forward reference
342 #rc4# pinsrw \$`($j>>1)&7`,($dat,$TX[0],4),$xmm\n
345 $code.=<<___ if ($rc4 && $j==15 && $k==$MOD-1);
347 xor $YY,$YY # keyword to partial register
349 lea ($dat,$XX[0],4),$XX[1]
351 $code.=<<___ if ($rc4 && $j==15);
358 my ($i,$a,$b,$c,$d)=@_;
359 my @rot3=(6,10,15,21);
362 my $xmm="%xmm".($j&1);
363 $code.=" movdqu 48($in0),%xmm5\n" if ($rc4 && $j==15);
364 $code.=" add \$$MOD,$XX[0]#b\n" if ($rc4 && $j==15 && $k==$MOD-1);
365 $code.=" pxor $xmm,$xmm\n" if ($rc4 && $j<=1);
367 #rc4# movl ($dat,$YY,4),$TY#d
369 #rc4# movl $TX[0]#d,($dat,$YY,4)
371 #md5# add 4*`((7*$j)%16)`($inp),$a
372 #rc4# add $TY#b,$TX[0]#b
373 #rc4# movl `4*(($k+1)%$MOD)`(`$k==$MOD-1?"$dat,$XX[0],4":"$XX[1]"`),$TX[1]#d
374 #md5# add \$$K[$i],$a
375 #rc4# movz $TX[0]#b,$TX[0]#d
377 #rc4# movl $TY#d,4*$k($XX[1])
379 #rc4# add $TX[1]#b,$YY#b
380 #md5# rol \$$rot3[$j%4],$a
381 #md5# mov \$-1,$tmp # forward reference
382 #rc4# pinsrw \$`($j>>1)&7`,($dat,$TX[0],4),$xmm\n
385 $code.=<<___ if ($rc4 && $j==15);
387 xor $XX[0],$XX[0] # keyword to partial register
388 mov $XX[1]#b,$XX[0]#b
390 xor $YY,$YY # keyword to partial register
392 lea ($dat,$XX[0],4),$XX[1]
400 for(;$i<16;$i++) { R0($i,@V); unshift(@V,pop(@V)); push(@TX,shift(@TX)); }
401 for(;$i<32;$i++) { R1($i,@V); unshift(@V,pop(@V)); push(@TX,shift(@TX)); }
402 for(;$i<48;$i++) { R2($i,@V); unshift(@V,pop(@V)); push(@TX,shift(@TX)); }
403 for(;$i<64;$i++) { R3($i,@V); unshift(@V,pop(@V)); push(@TX,shift(@TX)); }
406 #md5# add 0*4(%rsp),$V[0] # accumulate hash value
407 #md5# add 1*4(%rsp),$V[1]
408 #md5# add 2*4(%rsp),$V[2]
409 #md5# add 3*4(%rsp),$V[3]
411 #rc4# movdqu %xmm2,($out,$in0) # write RC4 output
412 #rc4# movdqu %xmm3,16($out,$in0)
413 #rc4# movdqu %xmm4,32($out,$in0)
414 #rc4# movdqu %xmm5,48($out,$in0)
415 #md5# lea 64($inp),$inp
416 #rc4# lea 64($in0),$in0
417 cmp 16(%rsp),$inp # are we done?
420 #md5# mov 24(%rsp),$len # restore pointer to MD5_CTX
421 #rc4# sub $TX[0]#b,$YY#b # correct $YY
422 #md5# mov $V[0],0*4($len) # write MD5_CTX
423 #md5# mov $V[1],1*4($len)
424 #md5# mov $V[2],2*4($len)
425 #md5# mov $V[3],3*4($len)
427 $code.=<<___ if ($rc4 && (!$md5 || $D));
428 mov 32(%rsp),$len # restore original $len
429 and \$63,$len # remaining bytes
436 movl ($dat,$YY,4),$TY#d
437 movl $TX[0]#d,($dat,$YY,4)
438 movl $TY#d,($dat,$XX[0],4)
441 movl ($dat,$TX[0],4),$TY#d
442 movl ($dat,$XX[0],4),$TX[0]#d
444 movb $TY#b,($out,$in0)
452 #rc4# sub \$1,$XX[0]#b
453 #rc4# movl $XX[0]#d,-8($dat)
454 #rc4# movl $YY#d,-4($dat)
469 .cfi_adjust_cfa_offset -88
477 if ($rc4 && $D) { # sole purpose of this section is to provide
478 # option to use the generated module as drop-in
479 # replacement for rc4-x86_64.pl for debugging
480 # and testing purposes...
481 my ($idx,$ido)=("%r8","%r9");
482 my ($dat,$len,$inp)=("%rdi","%rsi","%rdx");
486 .type RC4_set_key,\@function,3
502 mov %eax,($dat,%rax,4)
510 mov ($dat,$ido,4),%r10d
511 add ($inp,$len,1),$idx#b
514 mov ($dat,$idx,4),%r11d
516 mov %r10d,($dat,$idx,4)
517 mov %r11d,($dat,$ido,4)
526 .size RC4_set_key,.-RC4_set_key
529 .type RC4_options,\@abi-omnipotent
532 lea .Lopts(%rip),%rax
536 .asciz "rc4(64x,int)"
538 .size RC4_options,.-RC4_options
541 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
542 # CONTEXT *context,DISPATCHER_CONTEXT *disp)
550 .extern __imp_RtlVirtualUnwind
551 .type se_handler,\@abi-omnipotent
565 mov 120($context),%rax # pull context->Rax
566 mov 248($context),%rbx # pull context->Rip
568 lea .Lbody(%rip),%r10
569 cmp %r10,%rbx # context->Rip<.Lbody
572 mov 152($context),%rax # pull context->Rsp
574 lea .Lepilogue(%rip),%r10
575 cmp %r10,%rbx # context->Rip>=.Lepilogue
586 mov %rbx,144($context) # restore context->Rbx
587 mov %rbp,160($context) # restore context->Rbp
588 mov %r12,216($context) # restore context->R12
589 mov %r13,224($context) # restore context->R12
590 mov %r14,232($context) # restore context->R14
591 mov %r15,240($context) # restore context->R15
596 mov %rax,152($context) # restore context->Rsp
597 mov %rsi,168($context) # restore context->Rsi
598 mov %rdi,176($context) # restore context->Rdi
600 mov 40($disp),%rdi # disp->ContextRecord
601 mov $context,%rsi # context
602 mov \$154,%ecx # sizeof(CONTEXT)
603 .long 0xa548f3fc # cld; rep movsq
606 xor %rcx,%rcx # arg1, UNW_FLAG_NHANDLER
607 mov 8(%rsi),%rdx # arg2, disp->ImageBase
608 mov 0(%rsi),%r8 # arg3, disp->ControlPc
609 mov 16(%rsi),%r9 # arg4, disp->FunctionEntry
610 mov 40(%rsi),%r10 # disp->ContextRecord
611 lea 56(%rsi),%r11 # &disp->HandlerData
612 lea 24(%rsi),%r12 # &disp->EstablisherFrame
613 mov %r10,32(%rsp) # arg5
614 mov %r11,40(%rsp) # arg6
615 mov %r12,48(%rsp) # arg7
616 mov %rcx,56(%rsp) # arg8, (NULL)
617 call *__imp_RtlVirtualUnwind(%rip)
619 mov \$1,%eax # ExceptionContinueSearch
631 .size se_handler,.-se_handler
635 .rva .LSEH_begin_$func
637 .rva .LSEH_info_$func
649 if ($reg =~ /%r[0-9]+/) { $reg .= $conv; }
650 elsif ($conv eq "b") { $reg =~ s/%[er]([^x]+)x?/%$1l/; }
651 elsif ($conv eq "w") { $reg =~ s/%[er](.+)/%$1/; }
652 elsif ($conv eq "d") { $reg =~ s/%[er](.+)/%e$1/; }
656 $code =~ s/(%[a-z0-9]+)#([bwd])/reg_part($1,$2)/gem;
657 $code =~ s/\`([^\`]*)\`/eval $1/gem;
658 $code =~ s/pinsrw\s+\$0,/movd /gm;
660 $code =~ s/#md5#//gm if ($md5);
661 $code =~ s/#rc4#//gm if ($rc4);
665 close STDOUT or die "error closing STDOUT";