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
97use strict;
98my ($code, $dat, $inp, $out, $len, $idx, $ido, $i, @XX, @TX, $YY, $TY);
99my $output = shift;
100open 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 */
141void
142arcfour_crypt_asm(ARCFour_key *key, uchar_t *in, uchar_t *out, size_t len)
143{}
144
145/* ARGSUSED */
146void
147arcfour_key_init(ARCFour_key *key, uchar_t *keyval, int keyvallen)
148{}
149
150#else
151#include <sys/asm_linkage.h>
152
153ENTRY_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___
180for ($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___
195push(@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
245SET_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
273ENTRY_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
329SET_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
336print $code;
337
338close STDOUT;
339