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, .ident keywords, and lint(1B) guards.
74 #
75 # 3. Changed function name from RC4() to arcfour_crypt() 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 code to use CPUID
83 # instruction subfunction EAX=0 to determine if we're running on "GenuineIntel"
84 # or not. The result decides whether to use a
85 # * 1-byte key array (label .LRC4_CHAR, optimal on Intel EM64T) or a
86 # * 4-byte key array (Labels .Lloop1 and .Lloop8, optimal on AMD64).
87 #
88 # 5. Removed x86_64-xlate.pl script (not needed for as(1) or gas(1) assemblers).
89 #
90 # 6. Removed Lcloop8 code (slower than Lcloop1 on EM64T and not used on AMD64).
91 #
92
93 use strict;
94 my ($code, $dat, $inp, $out, $len, $idx, $ido, $i, @XX, @TX, $YY, $TY);
95 my $output = shift;
96 open STDOUT,">$output";
97
98 #
99 # Parameters
100 #
101
102 # OpenSSL:
103 # void RC4(RC4_KEY *key, unsigned long len, const unsigned char *indata,
104 # unsigned char *outdata);
105 #$dat="%rdi"; # arg1
106 #$len="%rsi"; # arg2
107 #$inp="%rdx"; # arg3
108 #$out="%rcx"; # arg4
109
110 # OpenSolaris:
111 # void arcfour_crypt(ARCFour_key *key, uchar_t *in, uchar_t *out, size_t len);
112 $dat="%rdi"; # arg1
113 $inp="%rsi"; # arg2
114 $out="%rdx"; # arg3
115 $len="%rcx"; # arg4
116
117 #
118 # Register variables
119 #
120 # $XX[0] is key->i (aka key->x), $XX[1] is a temporary.
121 # $TX[0] and $TX[1] are temporaries.
122 # $YY is key->j (aka key->y).
123 # $TY is a temporary.
124 #
125 @XX=("%r8","%r10");
126 @TX=("%r9","%r11");
127 $YY="%r12";
128 $TY="%r13";
129
130 $code=<<___;
131 #if !defined(lint) && !defined(__lint)
132
133 .ident "@(#)arcfour-x86_64.pl 1.1 08/03/20 SMI"
134
135 #include <sys/asm_linkage.h>
136
137
138 ENTRY_NP(arcfour_crypt)
139 /* EXPORT DELETE START */
140
141 or $len,$len # If (len == 0) return
142 jne .Lentry
143 ret
144 .Lentry:
145 push %r12
146 push %r13
147
148 / Set $dat to beginning of array, key->arr[0]
149 add \$8,$dat
150 / Get key->j
151 movl -8($dat),$XX[0]#d
152 / Get key->i
153 movl -4($dat),$YY#d
154
155 /
156 / Use a 1-byte data array, on Intel P4 EM64T,
157 / which is more efficient there,
158 / or a 4-byte data array (for AMD AMD64).
159 /
160
161 / If RC4_CHAR flag set (Intel EM64T), then use 1-byte array
162 cmpl \$-1,256($dat)
163 je .LRC4_CHAR
164 / otherwise use 4-byte integer array (AMD64)
165 inc $XX[0]#b
166 movl ($dat,$XX[0],4),$TX[0]#d
167 test \$-8,$len
168 jz .Lloop1
169 jmp .Lloop8
170
171 .align 16
172 .Lloop8:
173 /
174 / This code is for use with a 4-byte integer data array, which is
175 / more efficient on AMD64 Athlon and Opteron-class processors.
176 /
177 ___
178 for ($i=0;$i<8;$i++) {
179 $code.=<<___;
180 add $TX[0]#b,$YY#b
181 mov $XX[0],$XX[1]
182 movl ($dat,$YY,4),$TY#d
183 ror \$8,%rax # ror is redundant when $i=0
184 inc $XX[1]#b
185 movl ($dat,$XX[1],4),$TX[1]#d
186 cmp $XX[1],$YY
187 movl $TX[0]#d,($dat,$YY,4)
188 cmove $TX[0],$TX[1]
189 movl $TY#d,($dat,$XX[0],4)
190 add $TX[0]#b,$TY#b
191 movb ($dat,$TY,4),%al
192 ___
193 push(@TX,shift(@TX)); push(@XX,shift(@XX)); # "rotate" registers
194 }
195 $code.=<<___;
196 ror \$8,%rax
197 sub \$8,$len
198
199 xor ($inp),%rax
200 add \$8,$inp
201 mov %rax,($out)
202 add \$8,$out
203
204 test \$-8,$len
205 jnz .Lloop8
206 cmp \$0,$len
207 jne .Lloop1
208 ___
209 $code.=<<___;
210 .Lexit:
211 /
212 / Cleanup and exit code
213 /
214 / --i to undo ++i done at entry
215 sub \$1,$XX[0]#b
216 / set key->i
217 movl $XX[0]#d,-8($dat)
218 / set key->j
219 movl $YY#d,-4($dat)
220
221 pop %r13
222 pop %r12
223 ret
224 .align 16
225 .Lloop1:
226 add $TX[0]#b,$YY#b
227 movl ($dat,$YY,4),$TY#d
228 movl $TX[0]#d,($dat,$YY,4)
229 movl $TY#d,($dat,$XX[0],4)
230 add $TY#b,$TX[0]#b
231 inc $XX[0]#b
232 movl ($dat,$TX[0],4),$TY#d
233 movl ($dat,$XX[0],4),$TX[0]#d
234 xorb ($inp),$TY#b
235 inc $inp
236 movb $TY#b,($out)
237 inc $out
238 dec $len
239 jnz .Lloop1
240 jmp .Lexit
241
242
243 .align 16
244 .LRC4_CHAR:
245 /
246 / This code is for use with a 1-byte integer data array, which is
247 / more efficient on Intel P4 EM64T-class processors.
248 /
249 add \$1,$XX[0]#b
250 movzb ($dat,$XX[0]),$TX[0]#d
251 jmp .Lcloop1
252
253 .align 16
254 .Lcloop1:
255 add $TX[0]#b,$YY#b
256 movzb ($dat,$YY),$TY#d
257 movb $TX[0]#b,($dat,$YY)
258 movb $TY#b,($dat,$XX[0])
259 add $TX[0]#b,$TY#b
260 add \$1,$XX[0]#b
261 / Intel Optimization (preload $TY and $XX[0]):
262 movzb $TY#b,$TY#d
263 movzb $XX[0]#b,$XX[0]#d
264 movzb ($dat,$TY),$TY#d
265 movzb ($dat,$XX[0]),$TX[0]#d
266 xorb ($inp),$TY#b
267 lea 1($inp),$inp
268 movb $TY#b,($out)
269 lea 1($out),$out
270 sub \$1,$len
271 jnz .Lcloop1
272 jmp .Lexit
273
274 /* EXPORT DELETE END */
275 ret
276 SET_SIZE(arcfour_crypt)
277 ___
278
279
280 #
281 # Parameters
282 #
283
284 # OpenSSL:
285 # void RC4_set_key(RC4_KEY *key, int len, const unsigned char *data);
286 #$dat="%rdi"; # arg1
287 #$len="%rsi"; # arg2
288 #$inp="%rdx"; # arg3
289
290 # OpenSolaris:
291 # void arcfour_key_init(ARCFour_key *key, uchar_t *keyval, int keyvallen);
292 $dat="%rdi"; # arg1
293 $inp="%rsi"; # arg2
294 $len="%rdx"; # arg3
295
296 # Temporaries
297 $idx="%r8";
298 $ido="%r9";
299
300 $code.=<<___;
301 / int arcfour_crypt_on_intel(void);
302 .extern arcfour_crypt_on_intel
303
304 ENTRY_NP(arcfour_key_init)
305 /* EXPORT DELETE START */
306
307 / Find out if we're running on Intel or something else (e.g., AMD64).
308 / This sets %eax to 1 for Intel, otherwise 0.
309 push %rdi / Save arg1
310 push %rsi / Save arg2
311 push %rdx / Save arg3
312 call arcfour_crypt_on_intel
313 pop %rdx / Restore arg3
314 pop %rsi / Restore arg2
315 pop %rdi / Restore arg1
316
317 / Set $dat to beginning of array, key->arr[0]
318 lea 8($dat),$dat
319 lea ($inp,$len),$inp
320 neg $len
321 mov $len,%rcx
322 / Zeroed below, as %eax contains a flag from arcfour_crypt_on_intel():
323 /xor %eax,%eax
324 xor $ido,$ido
325 xor %r10,%r10
326 xor %r11,%r11
327
328 /
329 / Use a 1-byte data array, on Intel P4 EM64T,
330 / which is more efficient there,
331 / or a 4-byte data array (for AMD AMD64).
332 /
333 cmp \$1,%eax / Test if Intel
334 mov \$0,%eax / Zero eax without modifying flags
335 je .Lc1stloop / If Intel then use a 1-byte array,
336 jmp .Lw1stloop / otherwise use a 4-byte array.
337
338 .align 16
339 .Lw1stloop:
340 / AMD64 (4-byte array)
341 mov %eax,($dat,%rax,4)
342 add \$1,%al
343 jnc .Lw1stloop
344
345 xor $ido,$ido
346 xor $idx,$idx
347 .align 16
348 .Lw2ndloop:
349 mov ($dat,$ido,4),%r10d
350 add ($inp,$len,1),$idx#b
351 add %r10b,$idx#b
352 add \$1,$len
353 mov ($dat,$idx,4),%r11d
354 cmovz %rcx,$len
355 mov %r10d,($dat,$idx,4)
356 mov %r11d,($dat,$ido,4)
357 add \$1,$ido#b
358 jnc .Lw2ndloop
359 jmp .Lexit_key
360
361 .align 16
362 .Lc1stloop:
363 / Intel EM64T (1-byte array)
364 mov %al,($dat,%rax)
365 add \$1,%al
366 jnc .Lc1stloop
367
368 xor $ido,$ido
369 xor $idx,$idx
370 .align 16
371 .Lc2ndloop:
372 mov ($dat,$ido),%r10b
373 add ($inp,$len),$idx#b
374 add %r10b,$idx#b
375 add \$1,$len
376 mov ($dat,$idx),%r11b
377 jnz .Lcnowrap
378 mov %rcx,$len
379 .Lcnowrap:
380 mov %r10b,($dat,$idx)
381 mov %r11b,($dat,$ido)
382 add \$1,$ido#b
383 jnc .Lc2ndloop
384 movl \$-1,256($dat)
385
386 .align 16
387 .Lexit_key:
388 xor %eax,%eax
389 mov %eax,-8($dat)
390 mov %eax,-4($dat)
391
392 /* EXPORT DELETE END */
393 ret
394 SET_SIZE(arcfour_key_init)
395 .asciz "RC4 for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
396
397 #else
398 /* LINTED */
399 /* Nothing to be linted in this file--it's pure assembly source. */
400 #endif /* !lint && !__lint */
401 ___
402
403 $code =~ s/#([bwd])/$1/gm;
404
405 print $code;
406
407 close STDOUT;