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;