lib/libcrypto/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 # July 2004
  11 #
  12 # 2.22x RC4 tune-up:-) It should be noted though that my hand [as in
  13 # "hand-coded assembler"] doesn't stand for the whole improvement
  14 # coefficient. It turned out that eliminating RC4_CHAR from config
  15 # line results in ~40% improvement (yes, even for C implementation).
  16 # Presumably it has everything to do with AMD cache architecture and
  17 # RAW or whatever penalties. Once again! The module *requires* config
  18 # line *without* RC4_CHAR! As for coding "secret," I bet on partial
  19 # register arithmetics. For example instead of 'inc %r8; and $255,%r8'
  20 # I simply 'inc %r8b'. Even though optimization manual discourages
  21 # to operate on partial registers, it turned out to be the best bet.
  22 # At least for AMD... How IA32E would perform remains to be seen...
  23
  24 # November 2004
  25 #
  26 # As was shown by Marc Bevand reordering of couple of load operations
  27 # results in even higher performance gain of 3.3x:-) At least on
  28 # Opteron... For reference, 1x in this case is RC4_CHAR C-code
  29 # compiled with gcc 3.3.2, which performs at ~54MBps per 1GHz clock.
  30 # Latter means that if you want to *estimate* what to expect from
  31 # *your* Opteron, then multiply 54 by 3.3 and clock frequency in GHz.
  32
  33 # November 2004
  34 #
  35 # Intel P4 EM64T core was found to run the AMD64 code really slow...
  36 # The only way to achieve comparable performance on P4 was to keep
  37 # RC4_CHAR. Kind of ironic, huh? As it's apparently impossible to
  38 # compose blended code, which would perform even within 30% marginal
  39 # on either AMD and Intel platforms, I implement both cases. See
  40 # rc4_skey.c for further details...
  41
  42 # April 2005
  43 #
  44 # P4 EM64T core appears to be "allergic" to 64-bit inc/dec. Replacing
  45 # those with add/sub results in 50% performance improvement of folded
  46 # loop...
  47
  48 # May 2005
  49 #
  50 # As was shown by Zou Nanhai loop unrolling can improve Intel EM64T
  51 # performance by >30% [unlike P4 32-bit case that is]. But this is
  52 # provided that loads are reordered even more aggressively! Both code
  53 # pathes, AMD64 and EM64T, reorder loads in essentially same manner
  54 # as my IA-64 implementation. On Opteron this resulted in modest 5%
  55 # improvement [I had to test it], while final Intel P4 performance
  56 # achieves respectful 432MBps on 2.8GHz processor now. For reference.
  57 # If executed on Xeon, current RC4_CHAR code-path is 2.7x faster than
  58 # RC4_INT code-path. While if executed on Opteron, it's only 25%
  59 # slower than the RC4_INT one [meaning that if CPU µ-arch detection
  60 # is not implemented, then this final RC4_CHAR code-path should be
  61 # preferred, as it provides better *all-round* performance].
  62
  63 # March 2007
  64 #
  65 # Intel Core2 was observed to perform poorly on both code paths:-( It
  66 # apparently suffers from some kind of partial register stall, which
  67 # occurs in 64-bit mode only [as virtually identical 32-bit loop was
  68 # observed to outperform 64-bit one by almost 50%]. Adding two movzb to
  69 # cloop1 boosts its performance by 80%! This loop appears to be optimal
  70 # fit for Core2 and therefore the code was modified to skip cloop8 on
  71 # this CPU.
  72
  73 # May 2010
  74 #
  75 # Intel Westmere was observed to perform suboptimally. Adding yet
  76 # another movzb to cloop1 improved performance by almost 50%! Core2
  77 # performance is improved too, but nominally...
  78
  79 # May 2011
  80 #
  81 # The only code path that was not modified is P4-specific one. Non-P4
  82 # Intel code path optimization is heavily based on submission by Maxim
  83 # Perminov, Maxim Locktyukhin and Jim Guilford of Intel. I've used
  84 # some of the ideas even in attempt to optmize the original RC4_INT
  85 # code path... Current performance in cycles per processed byte (less
  86 # is better) and improvement coefficients relative to previous
  87 # version of this module are:
  88 #
  89 # Opteron       5.3/+0%(*)
  90 # P4            6.5
  91 # Core2         6.2/+15%(**)
  92 # Westmere      4.2/+60%
  93 # Sandy Bridge  4.2/+120%
  94 # Atom          9.3/+80%
  95 #
  96 # (*)   But corresponding loop has less instructions, which should have
  97 #       positive effect on upcoming Bulldozer, which has one less ALU.
  98 #       For reference, Intel code runs at 6.8 cpb rate on Opteron.
  99 # (**)  Note that Core2 result is ~15% lower than corresponding result
 100 #       for 32-bit code, meaning that it's possible to improve it,
 101 #       but more than likely at the cost of the others (see rc4-586.pl
 102 #       to get the idea)...
 103
 104 $flavour = shift;
 105 $output  = shift;
 106 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
 107
 108 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
 109 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
 110 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
 111 die "can't locate x86_64-xlate.pl";
 112
 113 open OUT,"| \"$^X\" $xlate $flavour $output";
 114 *STDOUT=*OUT;
 115
 116 $dat="%rdi";        # arg1
 117 $len="%rsi";        # arg2
 118 $inp="%rdx";        # arg3
 119 $out="%rcx";        # arg4
 120
 121 {
 122 $code=<<___;
 123 .text
 124 .extern OPENSSL_ia32cap_P
 125 .hidden OPENSSL_ia32cap_P
 126
 127 .globl  RC4
 128 .type   RC4,\@function,4
 129 .align  16
 130 RC4:    or      $len,$len
 131         jne     .Lentry
 132         ret
 133 .Lentry:
 134         push    %rbx
 135         push    %r12
 136         push    %r13
 137 .Lprologue:
 138         mov     $len,%r11
 139         mov     $inp,%r12
 140         mov     $out,%r13
 141 ___
 142 my $len="%r11";         # reassign input arguments
 143 my $inp="%r12";
 144 my $out="%r13";
 145
 146 my @XX=("%r10","%rsi");
 147 my @TX=("%rax","%rbx");
 148 my $YY="%rcx";
 149 my $TY="%rdx";
 150
 151 $code.=<<___;
 152         xor     $XX[0],$XX[0]
 153         xor     $YY,$YY
 154
 155         lea     8($dat),$dat
 156         mov     -8($dat),$XX[0]#b
 157         mov     -4($dat),$YY#b
 158         cmpl    \$-1,256($dat)
 159         je      .LRC4_CHAR
 160         mov     OPENSSL_ia32cap_P(%rip),%r8d
 161         xor     $TX[1],$TX[1]
 162         inc     $XX[0]#b
 163         sub     $XX[0],$TX[1]
 164         sub     $inp,$out
 165         movl    ($dat,$XX[0],4),$TX[0]#d
 166         test    \$-16,$len
 167         jz      .Lloop1
 168         bt      \$IA32CAP_BIT0_INTEL,%r8d       # Intel CPU?
 169         jc      .Lintel
 170         and     \$7,$TX[1]
 171         lea     1($XX[0]),$XX[1]
 172         jz      .Loop8
 173         sub     $TX[1],$len
 174 .Loop8_warmup:
 175         add     $TX[0]#b,$YY#b
 176         movl    ($dat,$YY,4),$TY#d
 177         movl    $TX[0]#d,($dat,$YY,4)
 178         movl    $TY#d,($dat,$XX[0],4)
 179         add     $TY#b,$TX[0]#b
 180         inc     $XX[0]#b
 181         movl    ($dat,$TX[0],4),$TY#d
 182         movl    ($dat,$XX[0],4),$TX[0]#d
 183         xorb    ($inp),$TY#b
 184         movb    $TY#b,($out,$inp)
 185         lea     1($inp),$inp
 186         dec     $TX[1]
 187         jnz     .Loop8_warmup
 188
 189         lea     1($XX[0]),$XX[1]
 190         jmp     .Loop8
 191 .align  16
 192 .Loop8:
 193 ___
 194 for ($i=0;$i<8;$i++) {
 195 $code.=<<___ if ($i==7);
 196         add     \$8,$XX[1]#b
 197 ___
 198 $code.=<<___;
 199         add     $TX[0]#b,$YY#b
 200         movl    ($dat,$YY,4),$TY#d
 201         movl    $TX[0]#d,($dat,$YY,4)
 202         movl    `4*($i==7?-1:$i)`($dat,$XX[1],4),$TX[1]#d
 203         ror     \$8,%r8                         # ror is redundant when $i=0
 204         movl    $TY#d,4*$i($dat,$XX[0],4)
 205         add     $TX[0]#b,$TY#b
 206         movb    ($dat,$TY,4),%r8b
 207 ___
 208 push(@TX,shift(@TX)); #push(@XX,shift(@XX));    # "rotate" registers
 209 }
 210 $code.=<<___;
 211         add     \$8,$XX[0]#b
 212         ror     \$8,%r8
 213         sub     \$8,$len
 214
 215         xor     ($inp),%r8
 216         mov     %r8,($out,$inp)
 217         lea     8($inp),$inp
 218
 219         test    \$-8,$len
 220         jnz     .Loop8
 221         cmp     \$0,$len
 222         jne     .Lloop1
 223         jmp     .Lexit
 224
 225 .align  16
 226 .Lintel:
 227         test    \$-32,$len
 228         jz      .Lloop1
 229         and     \$15,$TX[1]
 230         jz      .Loop16_is_hot
 231         sub     $TX[1],$len
 232 .Loop16_warmup:
 233         add     $TX[0]#b,$YY#b
 234         movl    ($dat,$YY,4),$TY#d
 235         movl    $TX[0]#d,($dat,$YY,4)
 236         movl    $TY#d,($dat,$XX[0],4)
 237         add     $TY#b,$TX[0]#b
 238         inc     $XX[0]#b
 239         movl    ($dat,$TX[0],4),$TY#d
 240         movl    ($dat,$XX[0],4),$TX[0]#d
 241         xorb    ($inp),$TY#b
 242         movb    $TY#b,($out,$inp)
 243         lea     1($inp),$inp
 244         dec     $TX[1]
 245         jnz     .Loop16_warmup
 246
 247         mov     $YY,$TX[1]
 248         xor     $YY,$YY
 249         mov     $TX[1]#b,$YY#b
 250
 251 .Loop16_is_hot:
 252         lea     ($dat,$XX[0],4),$XX[1]
 253 ___
 254 sub RC4_loop {
 255   my $i=shift;
 256   my $j=$i<0?0:$i;
 257   my $xmm="%xmm".($j&1);
 258
 259     $code.="    add     \$16,$XX[0]#b\n"                if ($i==15);
 260     $code.="    movdqu  ($inp),%xmm2\n"                 if ($i==15);
 261     $code.="    add     $TX[0]#b,$YY#b\n"               if ($i<=0);
 262     $code.="    movl    ($dat,$YY,4),$TY#d\n";
 263     $code.="    pxor    %xmm0,%xmm2\n"                  if ($i==0);
 264     $code.="    psllq   \$8,%xmm1\n"                    if ($i==0);
 265     $code.="    pxor    $xmm,$xmm\n"                    if ($i<=1);
 266     $code.="    movl    $TX[0]#d,($dat,$YY,4)\n";
 267     $code.="    add     $TY#b,$TX[0]#b\n";
 268     $code.="    movl    `4*($j+1)`($XX[1]),$TX[1]#d\n"  if ($i<15);
 269     $code.="    movz    $TX[0]#b,$TX[0]#d\n";
 270     $code.="    movl    $TY#d,4*$j($XX[1])\n";
 271     $code.="    pxor    %xmm1,%xmm2\n"                  if ($i==0);
 272     $code.="    lea     ($dat,$XX[0],4),$XX[1]\n"       if ($i==15);
 273     $code.="    add     $TX[1]#b,$YY#b\n"               if ($i<15);
 274     $code.="    pinsrw  \$`($j>>1)&7`,($dat,$TX[0],4),$xmm\n";
 275     $code.="    movdqu  %xmm2,($out,$inp)\n"            if ($i==0);
 276     $code.="    lea     16($inp),$inp\n"                if ($i==0);
 277     $code.="    movl    ($XX[1]),$TX[1]#d\n"            if ($i==15);
 278 }
 279         RC4_loop(-1);
 280 $code.=<<___;
 281         jmp     .Loop16_enter
 282 .align  16
 283 .Loop16:
 284 ___
 285
 286 for ($i=0;$i<16;$i++) {
 287     $code.=".Loop16_enter:\n"           if ($i==1);
 288         RC4_loop($i);
 289         push(@TX,shift(@TX));           # "rotate" registers
 290 }
 291 $code.=<<___;
 292         mov     $YY,$TX[1]
 293         xor     $YY,$YY                 # keyword to partial register
 294         sub     \$16,$len
 295         mov     $TX[1]#b,$YY#b
 296         test    \$-16,$len
 297         jnz     .Loop16
 298
 299         psllq   \$8,%xmm1
 300         pxor    %xmm0,%xmm2
 301         pxor    %xmm1,%xmm2
 302         movdqu  %xmm2,($out,$inp)
 303         lea     16($inp),$inp
 304
 305         cmp     \$0,$len
 306         jne     .Lloop1
 307         jmp     .Lexit
 308
 309 .align  16
 310 .Lloop1:
 311         add     $TX[0]#b,$YY#b
 312         movl    ($dat,$YY,4),$TY#d
 313         movl    $TX[0]#d,($dat,$YY,4)
 314         movl    $TY#d,($dat,$XX[0],4)
 315         add     $TY#b,$TX[0]#b
 316         inc     $XX[0]#b
 317         movl    ($dat,$TX[0],4),$TY#d
 318         movl    ($dat,$XX[0],4),$TX[0]#d
 319         xorb    ($inp),$TY#b
 320         movb    $TY#b,($out,$inp)
 321         lea     1($inp),$inp
 322         dec     $len
 323         jnz     .Lloop1
 324         jmp     .Lexit
 325
 326 .align  16
 327 .LRC4_CHAR:
 328         add     \$1,$XX[0]#b
 329         movzb   ($dat,$XX[0]),$TX[0]#d
 330         test    \$-8,$len
 331         jz      .Lcloop1
 332         jmp     .Lcloop8
 333 .align  16
 334 .Lcloop8:
 335         mov     ($inp),%r8d
 336         mov     4($inp),%r9d
 337 ___
 338 # unroll 2x4-wise, because 64-bit rotates kill Intel P4...
 339 for ($i=0;$i<4;$i++) {
 340 $code.=<<___;
 341         add     $TX[0]#b,$YY#b
 342         lea     1($XX[0]),$XX[1]
 343         movzb   ($dat,$YY),$TY#d
 344         movzb   $XX[1]#b,$XX[1]#d
 345         movzb   ($dat,$XX[1]),$TX[1]#d
 346         movb    $TX[0]#b,($dat,$YY)
 347         cmp     $XX[1],$YY
 348         movb    $TY#b,($dat,$XX[0])
 349         jne     .Lcmov$i                        # Intel cmov is sloooow...
 350         mov     $TX[0],$TX[1]
 351 .Lcmov$i:
 352         add     $TX[0]#b,$TY#b
 353         xor     ($dat,$TY),%r8b
 354         ror     \$8,%r8d
 355 ___
 356 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
 357 }
 358 for ($i=4;$i<8;$i++) {
 359 $code.=<<___;
 360         add     $TX[0]#b,$YY#b
 361         lea     1($XX[0]),$XX[1]
 362         movzb   ($dat,$YY),$TY#d
 363         movzb   $XX[1]#b,$XX[1]#d
 364         movzb   ($dat,$XX[1]),$TX[1]#d
 365         movb    $TX[0]#b,($dat,$YY)
 366         cmp     $XX[1],$YY
 367         movb    $TY#b,($dat,$XX[0])
 368         jne     .Lcmov$i                        # Intel cmov is sloooow...
 369         mov     $TX[0],$TX[1]
 370 .Lcmov$i:
 371         add     $TX[0]#b,$TY#b
 372         xor     ($dat,$TY),%r9b
 373         ror     \$8,%r9d
 374 ___
 375 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
 376 }
 377 $code.=<<___;
 378         lea     -8($len),$len
 379         mov     %r8d,($out)
 380         lea     8($inp),$inp
 381         mov     %r9d,4($out)
 382         lea     8($out),$out
 383
 384         test    \$-8,$len
 385         jnz     .Lcloop8
 386         cmp     \$0,$len
 387         jne     .Lcloop1
 388         jmp     .Lexit
 389 ___
 390 $code.=<<___;
 391 .align  16
 392 .Lcloop1:
 393         add     $TX[0]#b,$YY#b
 394         movzb   $YY#b,$YY#d
 395         movzb   ($dat,$YY),$TY#d
 396         movb    $TX[0]#b,($dat,$YY)
 397         movb    $TY#b,($dat,$XX[0])
 398         add     $TX[0]#b,$TY#b
 399         add     \$1,$XX[0]#b
 400         movzb   $TY#b,$TY#d
 401         movzb   $XX[0]#b,$XX[0]#d
 402         movzb   ($dat,$TY),$TY#d
 403         movzb   ($dat,$XX[0]),$TX[0]#d
 404         xorb    ($inp),$TY#b
 405         lea     1($inp),$inp
 406         movb    $TY#b,($out)
 407         lea     1($out),$out
 408         sub     \$1,$len
 409         jnz     .Lcloop1
 410         jmp     .Lexit
 411
 412 .align  16
 413 .Lexit:
 414         sub     \$1,$XX[0]#b
 415         movl    $XX[0]#d,-8($dat)
 416         movl    $YY#d,-4($dat)
 417
 418         mov     (%rsp),%r13
 419         mov     8(%rsp),%r12
 420         mov     16(%rsp),%rbx
 421         add     \$24,%rsp
 422 .Lepilogue:
 423         ret
 424 .size   RC4,.-RC4
 425 ___
 426 }
 427
 428 $idx="%r8";
 429 $ido="%r9";
 430
 431 $code.=<<___;
 432 .globl  RC4_set_key
 433 .type   RC4_set_key,\@function,3
 434 .align  16
 435 RC4_set_key:
 436         lea     8($dat),$dat
 437         lea     ($inp,$len),$inp
 438         neg     $len
 439         mov     $len,%rcx
 440         xor     %eax,%eax
 441         xor     $ido,$ido
 442         xor     %r10,%r10
 443         xor     %r11,%r11
 444
 445         mov     OPENSSL_ia32cap_P(%rip),$idx#d
 446         bt      \$IA32CAP_BIT0_INTELP4,$idx#d   # RC4_CHAR?
 447         jc      .Lc1stloop
 448         jmp     .Lw1stloop
 449
 450 .align  16
 451 .Lw1stloop:
 452         mov     %eax,($dat,%rax,4)
 453         add     \$1,%al
 454         jnc     .Lw1stloop
 455
 456         xor     $ido,$ido
 457         xor     $idx,$idx
 458 .align  16
 459 .Lw2ndloop:
 460         mov     ($dat,$ido,4),%r10d
 461         add     ($inp,$len,1),$idx#b
 462         add     %r10b,$idx#b
 463         add     \$1,$len
 464         mov     ($dat,$idx,4),%r11d
 465         cmovz   %rcx,$len
 466         mov     %r10d,($dat,$idx,4)
 467         mov     %r11d,($dat,$ido,4)
 468         add     \$1,$ido#b
 469         jnc     .Lw2ndloop
 470         jmp     .Lexit_key
 471
 472 .align  16
 473 .Lc1stloop:
 474         mov     %al,($dat,%rax)
 475         add     \$1,%al
 476         jnc     .Lc1stloop
 477
 478         xor     $ido,$ido
 479         xor     $idx,$idx
 480 .align  16
 481 .Lc2ndloop:
 482         mov     ($dat,$ido),%r10b
 483         add     ($inp,$len),$idx#b
 484         add     %r10b,$idx#b
 485         add     \$1,$len
 486         mov     ($dat,$idx),%r11b
 487         jnz     .Lcnowrap
 488         mov     %rcx,$len
 489 .Lcnowrap:
 490         mov     %r10b,($dat,$idx)
 491         mov     %r11b,($dat,$ido)
 492         add     \$1,$ido#b
 493         jnc     .Lc2ndloop
 494         movl    \$-1,256($dat)
 495
 496 .align  16
 497 .Lexit_key:
 498         xor     %eax,%eax
 499         mov     %eax,-8($dat)
 500         mov     %eax,-4($dat)
 501         ret
 502 .size   RC4_set_key,.-RC4_set_key
 503
 504 .globl  RC4_options
 505 .type   RC4_options,\@abi-omnipotent
 506 .align  16
 507 RC4_options:
 508         lea     .Lopts(%rip),%rax
 509         mov     OPENSSL_ia32cap_P(%rip),%edx
 510         bt      \$IA32CAP_BIT0_INTELP4,%edx
 511         jc      .L8xchar
 512         bt      \$IA32CAP_BIT0_INTEL,%edx
 513         jnc     .Ldone
 514         add     \$25,%rax
 515         ret
 516 .L8xchar:
 517         add     \$12,%rax
 518 .Ldone:
 519         ret
 520 .align  64
 521 .Lopts:
 522 .asciz  "rc4(8x,int)"
 523 .asciz  "rc4(8x,char)"
 524 .asciz  "rc4(16x,int)"
 525 .asciz  "RC4 for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
 526 .align  64
 527 .size   RC4_options,.-RC4_options
 528 ___
 529
 530 sub reg_part {
 531 my ($reg,$conv)=@_;
 532     if ($reg =~ /%r[0-9]+/)     { $reg .= $conv; }
 533     elsif ($conv eq "b")        { $reg =~ s/%[er]([^x]+)x?/%$1l/;       }
 534     elsif ($conv eq "w")        { $reg =~ s/%[er](.+)/%$1/;             }
 535     elsif ($conv eq "d")        { $reg =~ s/%[er](.+)/%e$1/;            }
 536     return $reg;
 537 }
 538
 539 $code =~ s/(%[a-z0-9]+)#([bwd])/reg_part($1,$2)/gem;
 540 $code =~ s/\`([^\`]*)\`/eval $1/gem;
 541
 542 print $code;
 543
 544 close STDOUT;