Skip to contentSkip to conversation

RC4 optimized for AMD64

rc4-amd64 Marc Bevand 4 participants 9 messages Nov 1, 2004 – Nov 3, 2004 1 message not in the archive

lore
Share & tools
lore
#0 lore raw

I have just published a small paper about optimizing RC4 for AMD64 (x86-64). A working implementation is also provided:

http://epita.fr/~bevand_m/papers/rc4-amd64.html

Kernel people may be interested given the fact that Linux already implements RC4.

Signature · 2 lines
Marc Bevand                          http://www.epita.fr/~bevand_m
Computer Science School EPITA - System, Network and Security Dept.
#1 lore raw
Quoted 7 lines · Marc Bevand

I have just published a small paper about optimizing RC4 for AMD64 (x86-64). A working implementation is also provided:

http://epita.fr/~bevand_m/papers/rc4-amd64.html

Kernel people may be interested given the fact that Linux already implements RC4.

Only problem is that the setkey code is released under a GPL incompatible license. Although it's probably not difficult to make the kernel's existing C setkey code to work with the new asm code.

- James

Signature · 2 lines
James Morris
<[email protected]>
#2 lore raw

On 2004-11-01, James Morris <[email protected]> wrote:

| 
|  Only problem is that the setkey code is released under a GPL incompatible
|  license.  Although it's probably not difficult to make the kernel's
|  existing C setkey code to work with the new asm code.

Yes, it would be very easy to do. This patch (completetly untested) is probably all that is necessary to make Linux arc4_set_key() work with rc4-amd64:

--- 8< -----------------------------------------------------------------

arc4.c 2004-11-01 13:18:16.799924112 +0100 renamed from arc4.c.orig 2004-11-01 13:16:41.739375512 +0100 +2 -2
@@ -20,8 +20,8 @@
 #define ARC4_BLOCK_SIZE                1
 
 struct arc4_ctx {
-       u8 S[256];
-       u8 x, y;
+       u64 x, y;
+       u64 S[256];
 };
 
 static int arc4_set_key(void *ctx_arg, const u8 *in_key, unsigned int key_len, u32 *flags)

--- 8< -----------------------------------------------------------------

Signature · 2 lines
Marc Bevand                          http://www.epita.fr/~bevand_m
Computer Science School EPITA - System, Network and Security Dept.
#4 lore raw
In reply to dean gaudet
Quoted 12 lines · dean gaudet
Quoted 7 lines · Marc Bevand

I have just published a small paper about optimizing RC4 for AMD64 (x86-64). A working implementation is also provided:

http://epita.fr/~bevand_m/papers/rc4-amd64.html

Kernel people may be interested given the fact that Linux already implements RC4.

you've made a non-portable flags assumption:

Quoted 7 lines
Quoted 3 lines

dec %r11b
ror $8, %r8 # (ror does not change ZF)
jnz 1b

the contents of ZF are undefined after a rotation... most importantly they differ between p4 (ZF is set according to result) and k8 (ZF unchanged).

ack... it's too early on a monday morning -- i misread the documentation. this ZF assumption is actually defined and portable... still kind of ugly. how much benefit do you see?

-dean

#5 lore raw

dean gaudet wrote:

| 
| [...]
| ack... it's too early on a monday morning -- i misread the documentation.
| this ZF assumption is actually defined and portable... still kind of ugly.
| how much benefit do you see?

When "dec" is placed before "ror", throughput goes up by about 5% on my test system (Opteron 244 rev C0). I don't find it "ugly" because the optimization no intrusive at all (only 1 moved instruction).

Concerning the "dec / sub $1" case, it makes absolutely no difference on the Opteron, I just used "dec" because the opcode is 3 bytes length instead of 4.

Signature · 2 lines
Marc Bevand                          http://www.epita.fr/~bevand_m
Computer Science School EPITA - System, Network and Security Dept.
#3 lore raw
In reply to Marc Bevand
Quoted 7 lines · Marc Bevand

I have just published a small paper about optimizing RC4 for AMD64 (x86-64). A working implementation is also provided:

http://epita.fr/~bevand_m/papers/rc4-amd64.html

Kernel people may be interested given the fact that Linux already implements RC4.

you've made a non-portable flags assumption:

Quoted 3 lines

dec %r11b
ror $8, %r8 # (ror does not change ZF)
jnz 1b

the contents of ZF are undefined after a rotation... most importantly they differ between p4 (ZF is set according to result) and k8 (ZF unchanged).

do you really measure a perf improvement from this assumption? note that p4 would prefer "sub $1, %r11b" here instead of dec... but the difference is likely minimal.

-dean

#7 lore raw
In reply to a message not in the archive
Quoted 7 lines · Denis Vlasenko
Quoted 3 lines · dean gaudet

note that
p4 would prefer "sub $1, %r11b" here instead of dec... but the difference is likely minimal.

p4 is not the only x86 CPU on the planet. Why should I use longer instruction then?

you're asking about spending one byte? one byte extra for code which could perform better on more CPUs?

i could equally well say "k8 is not the only x86-64 cpu on the planet".

i really don't care whether this change is made or not, i only mentioned a general perf rule.

go ahead and use -Os for the rest of the kernel if you're worried about size, it'll likely go faster. but spending 1 byte in code which is perf critical is nothing.

-dean

#8 lore raw
Quoted 7 lines · dean gaudet
Quoted 5 lines · Denis Vlasenko
Quoted 3 lines · dean gaudet

note that
p4 would prefer "sub $1, %r11b" here instead of dec... but the difference is likely minimal.

Quoted 5 lines
Quoted 2 lines

p4 is not the only x86 CPU on the planet. Why should I use longer instruction then?

you're asking about spending one byte? one byte extra for code which could perform better on more CPUs?

You're asking about speedup by 1 cycle on a CPU which will be outdated 6 months from now?
--
vda

#9 lore raw
In reply to dean gaudet

dean gaudet wrote:

| 
| [...]
| you're asking about spending one byte?  one byte extra for code which 
| could perform better on more CPUs?

Guys, this does not matter _for now_, because AFAIK nobody has benchmarked this code on an EM64T P4 CPU.

Obviously, if 'sub $1,X' is proved to be faster than 'dec' on the Intel CPU, then I will change the code (since both instructions are equivalent on AMD CPUs).

Signature · 2 lines
Marc Bevand                          http://www.epita.fr/~bevand_m
Computer Science School EPITA - System, Network and Security Dept.