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 #
  62 # OpenSolaris OS modifications
  63 #
  64 # Sun elects to use this software under the BSD license.
  65 #
  66 # This source originates from OpenSSL file rc4-x86_64.pl at
  67 # ftp://ftp.openssl.org/snapshot/openssl-0.9.8-stable-SNAP-20080131.tar.gz
  68 # (presumably for future OpenSSL release 0.9.8h), with these changes:
  69 #
  70 # 1. Added some comments, "use strict", and declared all variables.
  71 #
  72 # 2. Added OpenSolaris ENTRY_NP/SET_SIZE macros from
  73 # /usr/include/sys/asm_linkage.h.
  74 #
  75 # 3. Changed function name from RC4() to arcfour_crypt_asm() and RC4_set_key()
  76 # to arcfour_key_init(), and changed the parameter order for both to that
  77 # used by OpenSolaris.
  78 #
  79 # 4. The current method of using cpuid feature bits 20 (NX) or 28 (HTT) from
  80 # function OPENSSL_ia32_cpuid() to distinguish Intel/AMD does not work for
  81 # some newer AMD64 processors, as these bits are set on both Intel EM64T
  82 # processors and newer AMD64 processors.  I replaced this with C code
  83 # (function arcfour_crypt_on_intel()) to call cpuid_getvendor()
  84 # when executing in the kernel and getisax() when executing in userland.
  85 #
  86 # 5. Set a new field in the key structure, key->flag to 0 for AMD AMD64
  87 # and 1 for Intel EM64T.  This is to select the most-efficient arcfour_crypt()
  88 # function to use.
  89 #
  90 # 6. Removed x86_64-xlate.pl script (not needed for as(1) or gas(1) assemblers).
  91 #
  92 # 7. Removed unused RC4_CHAR, Lcloop1, and Lcloop8 code.
  93 #
  94 # 8. Added C function definitions for use by lint(1B).
  95 #
  96 
  97 use strict;
  98 my ($code, $dat, $inp, $out, $len, $idx, $ido, $i, @XX, @TX, $YY, $TY);
  99 my $output = shift;
 100 open STDOUT,">$output";
 101 
 102 #
 103 # Parameters
 104 #
 105 
 106 # OpenSSL:
 107 # void RC4(RC4_KEY *key, unsigned long len, const unsigned char *indata,
 108 #       unsigned char *outdata);
 109 #$dat="%rdi";       # arg1
 110 #$len="%rsi";       # arg2
 111 #$inp="%rdx";       # arg3
 112 #$out="%rcx";       # arg4
 113 
 114 # OpenSolaris:
 115 # void arcfour_crypt_asm(ARCFour_key *key, uchar_t *in, uchar_t *out,
 116 #       size_t len);
 117 $dat="%rdi";        # arg1
 118 $inp="%rsi";        # arg2
 119 $out="%rdx";        # arg3
 120 $len="%rcx";        # arg4
 121 
 122 #
 123 # Register variables
 124 #
 125 # $XX[0] is key->i (aka key->x), $XX[1] is a temporary.
 126 # $TX[0] and $TX[1] are temporaries.
 127 # $YY is key->j (aka key->y).
 128 # $TY is a temporary.
 129 #
 130 @XX=("%r8","%r10");
 131 @TX=("%r9","%r11");
 132 $YY="%r12";
 133 $TY="%r13";
 134 
 135 $code=<<___;
 136 #if defined(lint) || defined(__lint)
 137 
 138 #include "arcfour.h"
 139 
 140 /* ARGSUSED */
 141 void
 142 arcfour_crypt_asm(ARCFour_key *key, uchar_t *in, uchar_t *out, size_t len)
 143 {}
 144 
 145 /* ARGSUSED */
 146 void
 147 arcfour_key_init(ARCFour_key *key, uchar_t *keyval, int keyvallen)
 148 {}
 149 
 150 #else
 151 #include <sys/asm_linkage.h>
 152 
 153 ENTRY_NP(arcfour_crypt_asm)
 154         or      $len,$len # If (len == 0) return
 155         jne     .Lentry
 156         ret
 157 .Lentry:
 158         push    %r12
 159         push    %r13
 160 
 161         / Set $dat to beginning of array, key->arr[0]
 162         add     \$8,$dat
 163         / Get key->j
 164         movl    -8($dat),$XX[0]#d
 165         / Get key->i
 166         movl    -4($dat),$YY#d
 167 
 168         /
 169         / Use a 4-byte key schedule element array
 170         /
 171         inc     $XX[0]#b
 172         movl    ($dat,$XX[0],4),$TX[0]#d
 173         test    \$-8,$len
 174         jz      .Lloop1
 175         jmp     .Lloop8
 176 
 177 .align  16
 178 .Lloop8:
 179 ___
 180 for ($i=0;$i<8;$i++) {
 181 $code.=<<___;
 182         add     $TX[0]#b,$YY#b
 183         mov     $XX[0],$XX[1]
 184         movl    ($dat,$YY,4),$TY#d
 185         ror     \$8,%rax                        # ror is redundant when $i=0
 186         inc     $XX[1]#b
 187         movl    ($dat,$XX[1],4),$TX[1]#d
 188         cmp     $XX[1],$YY
 189         movl    $TX[0]#d,($dat,$YY,4)
 190         cmove   $TX[0],$TX[1]
 191         movl    $TY#d,($dat,$XX[0],4)
 192         add     $TX[0]#b,$TY#b
 193         movb    ($dat,$TY,4),%al
 194 ___
 195 push(@TX,shift(@TX)); push(@XX,shift(@XX));     # "rotate" registers
 196 }
 197 $code.=<<___;
 198         ror     \$8,%rax
 199         sub     \$8,$len
 200 
 201         xor     ($inp),%rax
 202         add     \$8,$inp
 203         mov     %rax,($out)
 204         add     \$8,$out
 205 
 206         test    \$-8,$len
 207         jnz     .Lloop8
 208         cmp     \$0,$len
 209         jne     .Lloop1
 210 
 211 .Lexit:
 212         /
 213         / Cleanup and exit code
 214         /
 215         / --i to undo ++i done at entry
 216         sub     \$1,$XX[0]#b
 217         / set key->i
 218         movl    $XX[0]#d,-8($dat)
 219         / set key->j
 220         movl    $YY#d,-4($dat)
 221 
 222         pop     %r13
 223         pop     %r12
 224         ret
 225 
 226 .align  16
 227 .Lloop1:
 228         add     $TX[0]#b,$YY#b
 229         movl    ($dat,$YY,4),$TY#d
 230         movl    $TX[0]#d,($dat,$YY,4)
 231         movl    $TY#d,($dat,$XX[0],4)
 232         add     $TY#b,$TX[0]#b
 233         inc     $XX[0]#b
 234         movl    ($dat,$TX[0],4),$TY#d
 235         movl    ($dat,$XX[0],4),$TX[0]#d
 236         xorb    ($inp),$TY#b
 237         inc     $inp
 238         movb    $TY#b,($out)
 239         inc     $out
 240         dec     $len
 241         jnz     .Lloop1
 242         jmp     .Lexit
 243 
 244         ret
 245 SET_SIZE(arcfour_crypt_asm)
 246 ___
 247 
 248 
 249 #
 250 # Parameters
 251 #
 252 
 253 # OpenSSL:
 254 # void RC4_set_key(RC4_KEY *key, int len, const unsigned char *data);
 255 #$dat="%rdi";       # arg1
 256 #$len="%rsi";       # arg2
 257 #$inp="%rdx";       # arg3
 258 
 259 # OpenSolaris:
 260 # void arcfour_key_init(ARCFour_key *key, uchar_t *keyval, int keyvallen);
 261 $dat="%rdi";        # arg1
 262 $inp="%rsi";        # arg2
 263 $len="%rdx";        # arg3
 264 
 265 # Temporaries
 266 $idx="%r8";
 267 $ido="%r9";
 268 
 269 $code.=<<___;
 270         / int arcfour_crypt_on_intel(void);
 271 .extern arcfour_crypt_on_intel
 272 
 273 ENTRY_NP(arcfour_key_init)
 274         / Find out if we're running on Intel or something else (e.g., AMD64).
 275         / This sets %eax to 1 for Intel, otherwise 0.
 276         push    %rdi            / Save arg1
 277         push    %rsi            / Save arg2
 278         push    %rdx            / Save arg3
 279         call    arcfour_crypt_on_intel
 280         pop     %rdx            / Restore arg3
 281         pop     %rsi            / Restore arg2
 282         pop     %rdi            / Restore arg1
 283         / Save return value in key->flag (1=Intel, 0=AMD)
 284         movl    %eax,1032($dat)
 285 
 286         / Set $dat to beginning of array, key->arr[0]
 287         lea     8($dat),$dat
 288         lea     ($inp,$len),$inp
 289         neg     $len
 290         mov     $len,%rcx
 291 
 292         xor     %eax,%eax
 293         xor     $ido,$ido
 294         xor     %r10,%r10
 295         xor     %r11,%r11
 296 
 297         / Use a 4-byte data array
 298         jmp     .Lw1stloop
 299 
 300 .align  16
 301 .Lw1stloop:
 302         / AMD64 (4-byte array)
 303         mov     %eax,($dat,%rax,4)
 304         add     \$1,%al
 305         jnc     .Lw1stloop
 306 
 307         xor     $ido,$ido
 308         xor     $idx,$idx
 309 
 310 .align  16
 311 .Lw2ndloop:
 312         mov     ($dat,$ido,4),%r10d
 313         add     ($inp,$len,1),$idx#b
 314         add     %r10b,$idx#b
 315         add     \$1,$len
 316         mov     ($dat,$idx,4),%r11d
 317         cmovz   %rcx,$len
 318         mov     %r10d,($dat,$idx,4)
 319         mov     %r11d,($dat,$ido,4)
 320         add     \$1,$ido#b
 321         jnc     .Lw2ndloop
 322 
 323         / Exit code
 324         xor     %eax,%eax
 325         mov     %eax,-8($dat)
 326         mov     %eax,-4($dat)
 327 
 328         ret
 329 SET_SIZE(arcfour_key_init)
 330 .asciz  "RC4 for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
 331 #endif /* !lint && !__lint */
 332 ___
 333 
 334 $code =~ s/#([bwd])/$1/gm;
 335 
 336 print $code;
 337 
 338 close STDOUT;