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. Rights for redistribution and usage in source and binary
   6 # forms are granted according to the OpenSSL license.
   7 # ====================================================================
   8 #
   9 # 2.22x RC4 tune-up:-) It should be noted though that my hand [as in
  10 # "hand-coded assembler"] doesn't stand for the whole improvement
  11 # coefficient. It turned out that eliminating RC4_CHAR from config
  12 # line results in ~40% improvement (yes, even for C implementation).
  13 # Presumably it has everything to do with AMD cache architecture and
  14 # RAW or whatever penalties. Once again! The module *requires* config
  15 # line *without* RC4_CHAR! As for coding "secret," I bet on partial
  16 # register arithmetics. For example instead of 'inc %r8; and $255,%r8'
  17 # I simply 'inc %r8b'. Even though optimization manual discourages
  18 # to operate on partial registers, it turned out to be the best bet.
  19 # At least for AMD... How IA32E would perform remains to be seen...
  20
  21 # As was shown by Marc Bevand reordering of couple of load operations
  22 # results in even higher performance gain of 3.3x:-) At least on
  23 # Opteron... For reference, 1x in this case is RC4_CHAR C-code
  24 # compiled with gcc 3.3.2, which performs at ~54MBps per 1GHz clock.
  25 # Latter means that if you want to *estimate* what to expect from
  26 # *your* Opteron, then multiply 54 by 3.3 and clock frequency in GHz.
  27
  28 # Intel P4 EM64T core was found to run the AMD64 code really slow...
  29 # The only way to achieve comparable performance on P4 was to keep
  30 # RC4_CHAR. Kind of ironic, huh? As it's apparently impossible to
  31 # compose blended code, which would perform even within 30% marginal
  32 # on either AMD and Intel platforms, I implement both cases. See
  33 # rc4_skey.c for further details...
  34
  35 # P4 EM64T core appears to be "allergic" to 64-bit inc/dec. Replacing
  36 # those with add/sub results in 50% performance improvement of folded
  37 # loop...
  38
  39 # As was shown by Zou Nanhai loop unrolling can improve Intel EM64T
  40 # performance by >30% [unlike P4 32-bit case that is]. But this is
  41 # provided that loads are reordered even more aggressively! Both code
  42 # pathes, AMD64 and EM64T, reorder loads in essentially same manner
  43 # as my IA-64 implementation. On Opteron this resulted in modest 5%
  44 # improvement [I had to test it], while final Intel P4 performance
  45 # achieves respectful 432MBps on 2.8GHz processor now. For reference.
  46 # If executed on Xeon, current RC4_CHAR code-path is 2.7x faster than
  47 # RC4_INT code-path. While if executed on Opteron, it's only 25%
  48 # slower than the RC4_INT one [meaning that if CPU µ-arch detection
  49 # is not implemented, then this final RC4_CHAR code-path should be
  50 # preferred, as it provides better *all-round* performance].
  51
  52 # Intel Core2 was observed to perform poorly on both code paths:-( It
  53 # apparently suffers from some kind of partial register stall, which
  54 # occurs in 64-bit mode only [as virtually identical 32-bit loop was
  55 # observed to outperform 64-bit one by almost 50%]. Adding two movzb to
  56 # cloop1 boosts its performance by 80%! This loop appears to be optimal
  57 # fit for Core2 and therefore the code was modified to skip cloop8 on
  58 # this CPU.
  59
  60 $output=shift;
  61 open STDOUT,"| $^X ../perlasm/x86_64-xlate.pl $output";
  62
  63 $dat="%rdi";        # arg1
  64 $len="%rsi";        # arg2
  65 $inp="%rdx";        # arg3
  66 $out="%rcx";        # arg4
  67
  68 @XX=("%r8","%r10");
  69 @TX=("%r9","%r11");
  70 $YY="%r12";
  71 $TY="%r13";
  72
  73 $code=<<___;
  74 .text
  75
  76 .globl  RC4
  77 .type   RC4,\@function,4
  78 .align  16
  79 RC4:    or      $len,$len
  80         jne     .Lentry
  81         ret
  82 .Lentry:
  83         push    %r12
  84         push    %r13
  85
  86         add     \$8,$dat
  87         movl    -8($dat),$XX[0]#d
  88         movl    -4($dat),$YY#d
  89         cmpl    \$-1,256($dat)
  90         je      .LRC4_CHAR
  91         inc     $XX[0]#b
  92         movl    ($dat,$XX[0],4),$TX[0]#d
  93         test    \$-8,$len
  94         jz      .Lloop1
  95         jmp     .Lloop8
  96 .align  16
  97 .Lloop8:
  98 ___
  99 for ($i=0;$i<8;$i++) {
 100 $code.=<<___;
 101         add     $TX[0]#b,$YY#b
 102         mov     $XX[0],$XX[1]
 103         movl    ($dat,$YY,4),$TY#d
 104         ror     \$8,%rax                        # ror is redundant when $i=0
 105         inc     $XX[1]#b
 106         movl    ($dat,$XX[1],4),$TX[1]#d
 107         cmp     $XX[1],$YY
 108         movl    $TX[0]#d,($dat,$YY,4)
 109         cmove   $TX[0],$TX[1]
 110         movl    $TY#d,($dat,$XX[0],4)
 111         add     $TX[0]#b,$TY#b
 112         movb    ($dat,$TY,4),%al
 113 ___
 114 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
 115 }
 116 $code.=<<___;
 117         ror     \$8,%rax
 118         sub     \$8,$len
 119
 120         xor     ($inp),%rax
 121         add     \$8,$inp
 122         mov     %rax,($out)
 123         add     \$8,$out
 124
 125         test    \$-8,$len
 126         jnz     .Lloop8
 127         cmp     \$0,$len
 128         jne     .Lloop1
 129 ___
 130 $code.=<<___;
 131 .Lexit:
 132         sub     \$1,$XX[0]#b
 133         movl    $XX[0]#d,-8($dat)
 134         movl    $YY#d,-4($dat)
 135
 136         pop     %r13
 137         pop     %r12
 138         ret
 139 .align  16
 140 .Lloop1:
 141         add     $TX[0]#b,$YY#b
 142         movl    ($dat,$YY,4),$TY#d
 143         movl    $TX[0]#d,($dat,$YY,4)
 144         movl    $TY#d,($dat,$XX[0],4)
 145         add     $TY#b,$TX[0]#b
 146         inc     $XX[0]#b
 147         movl    ($dat,$TX[0],4),$TY#d
 148         movl    ($dat,$XX[0],4),$TX[0]#d
 149         xorb    ($inp),$TY#b
 150         inc     $inp
 151         movb    $TY#b,($out)
 152         inc     $out
 153         dec     $len
 154         jnz     .Lloop1
 155         jmp     .Lexit
 156
 157 .align  16
 158 .LRC4_CHAR:
 159         add     \$1,$XX[0]#b
 160         movzb   ($dat,$XX[0]),$TX[0]#d
 161         test    \$-8,$len
 162         jz      .Lcloop1
 163         cmp     \$0,260($dat)
 164         jnz     .Lcloop1
 165         push    %rbx
 166         jmp     .Lcloop8
 167 .align  16
 168 .Lcloop8:
 169         mov     ($inp),%eax
 170         mov     4($inp),%ebx
 171 ___
 172 # unroll 2x4-wise, because 64-bit rotates kill Intel P4...
 173 for ($i=0;$i<4;$i++) {
 174 $code.=<<___;
 175         add     $TX[0]#b,$YY#b
 176         lea     1($XX[0]),$XX[1]
 177         movzb   ($dat,$YY),$TY#d
 178         movzb   $XX[1]#b,$XX[1]#d
 179         movzb   ($dat,$XX[1]),$TX[1]#d
 180         movb    $TX[0]#b,($dat,$YY)
 181         cmp     $XX[1],$YY
 182         movb    $TY#b,($dat,$XX[0])
 183         jne     .Lcmov$i                        # Intel cmov is sloooow...
 184         mov     $TX[0],$TX[1]
 185 .Lcmov$i:
 186         add     $TX[0]#b,$TY#b
 187         xor     ($dat,$TY),%al
 188         ror     \$8,%eax
 189 ___
 190 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
 191 }
 192 for ($i=4;$i<8;$i++) {
 193 $code.=<<___;
 194         add     $TX[0]#b,$YY#b
 195         lea     1($XX[0]),$XX[1]
 196         movzb   ($dat,$YY),$TY#d
 197         movzb   $XX[1]#b,$XX[1]#d
 198         movzb   ($dat,$XX[1]),$TX[1]#d
 199         movb    $TX[0]#b,($dat,$YY)
 200         cmp     $XX[1],$YY
 201         movb    $TY#b,($dat,$XX[0])
 202         jne     .Lcmov$i                        # Intel cmov is sloooow...
 203         mov     $TX[0],$TX[1]
 204 .Lcmov$i:
 205         add     $TX[0]#b,$TY#b
 206         xor     ($dat,$TY),%bl
 207         ror     \$8,%ebx
 208 ___
 209 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
 210 }
 211 $code.=<<___;
 212         lea     -8($len),$len
 213         mov     %eax,($out)
 214         lea     8($inp),$inp
 215         mov     %ebx,4($out)
 216         lea     8($out),$out
 217
 218         test    \$-8,$len
 219         jnz     .Lcloop8
 220         pop     %rbx
 221         cmp     \$0,$len
 222         jne     .Lcloop1
 223         jmp     .Lexit
 224 ___
 225 $code.=<<___;
 226 .align  16
 227 .Lcloop1:
 228         add     $TX[0]#b,$YY#b
 229         movzb   ($dat,$YY),$TY#d
 230         movb    $TX[0]#b,($dat,$YY)
 231         movb    $TY#b,($dat,$XX[0])
 232         add     $TX[0]#b,$TY#b
 233         add     \$1,$XX[0]#b
 234         movzb   $TY#b,$TY#d
 235         movzb   $XX[0]#b,$XX[0]#d
 236         movzb   ($dat,$TY),$TY#d
 237         movzb   ($dat,$XX[0]),$TX[0]#d
 238         xorb    ($inp),$TY#b
 239         lea     1($inp),$inp
 240         movb    $TY#b,($out)
 241         lea     1($out),$out
 242         sub     \$1,$len
 243         jnz     .Lcloop1
 244         jmp     .Lexit
 245 .size   RC4,.-RC4
 246 ___
 247
 248 $idx="%r8";
 249 $ido="%r9";
 250
 251 $code.=<<___;
 252 .extern OPENSSL_ia32cap_P
 253 .globl  RC4_set_key
 254 .type   RC4_set_key,\@function,3
 255 .align  16
 256 RC4_set_key:
 257         lea     8($dat),$dat
 258         lea     ($inp,$len),$inp
 259         neg     $len
 260         mov     $len,%rcx
 261         xor     %eax,%eax
 262         xor     $ido,$ido
 263         xor     %r10,%r10
 264         xor     %r11,%r11
 265
 266         mov     OPENSSL_ia32cap_P(%rip),$idx#d
 267         bt      \$20,$idx#d
 268         jnc     .Lw1stloop
 269         bt      \$30,$idx#d
 270         setc    $ido#b
 271         mov     $ido#d,260($dat)
 272         jmp     .Lc1stloop
 273
 274 .align  16
 275 .Lw1stloop:
 276         mov     %eax,($dat,%rax,4)
 277         add     \$1,%al
 278         jnc     .Lw1stloop
 279
 280         xor     $ido,$ido
 281         xor     $idx,$idx
 282 .align  16
 283 .Lw2ndloop:
 284         mov     ($dat,$ido,4),%r10d
 285         add     ($inp,$len,1),$idx#b
 286         add     %r10b,$idx#b
 287         add     \$1,$len
 288         mov     ($dat,$idx,4),%r11d
 289         cmovz   %rcx,$len
 290         mov     %r10d,($dat,$idx,4)
 291         mov     %r11d,($dat,$ido,4)
 292         add     \$1,$ido#b
 293         jnc     .Lw2ndloop
 294         jmp     .Lexit_key
 295
 296 .align  16
 297 .Lc1stloop:
 298         mov     %al,($dat,%rax)
 299         add     \$1,%al
 300         jnc     .Lc1stloop
 301
 302         xor     $ido,$ido
 303         xor     $idx,$idx
 304 .align  16
 305 .Lc2ndloop:
 306         mov     ($dat,$ido),%r10b
 307         add     ($inp,$len),$idx#b
 308         add     %r10b,$idx#b
 309         add     \$1,$len
 310         mov     ($dat,$idx),%r11b
 311         jnz     .Lcnowrap
 312         mov     %rcx,$len
 313 .Lcnowrap:
 314         mov     %r10b,($dat,$idx)
 315         mov     %r11b,($dat,$ido)
 316         add     \$1,$ido#b
 317         jnc     .Lc2ndloop
 318         movl    \$-1,256($dat)
 319
 320 .align  16
 321 .Lexit_key:
 322         xor     %eax,%eax
 323         mov     %eax,-8($dat)
 324         mov     %eax,-4($dat)
 325         ret
 326 .size   RC4_set_key,.-RC4_set_key
 327
 328 .globl  RC4_options
 329 .type   RC4_options,\@function,0
 330 .align  16
 331 RC4_options:
 332         .picmeup %rax
 333         lea     .Lopts-.(%rax),%rax
 334         mov     OPENSSL_ia32cap_P(%rip),%edx
 335         bt      \$20,%edx
 336         jnc     .Ldone
 337         add     \$12,%rax
 338         bt      \$30,%edx
 339         jnc     .Ldone
 340         add     \$13,%rax
 341 .Ldone:
 342         ret
 343 .align  64
 344 .Lopts:
 345 .asciz  "rc4(8x,int)"
 346 .asciz  "rc4(8x,char)"
 347 .asciz  "rc4(1x,char)"
 348 .asciz  "RC4 for x86_64, OpenSSL project"
 349 .align  64
 350 .size   RC4_options,.-RC4_options
 351 ___
 352
 353 $code =~ s/#([bwd])/$1/gm;
 354
 355 print $code;
 356
 357 close STDOUT;