Date: Thu, 22 Mar 2012 21:35:44 +0400 From: Solar Designer <solar@...nwall.com> To: john-dev@...ts.openwall.com Subject: Re: Research ideas. On Thu, Mar 22, 2012 at 09:09:42AM -0700, Alain Espinosa wrote: > I was trying to implement and S-box assembly code generator. The new > s-box are amazing but there is other optimization as well. Solar > counts gates Why, I actually count instructions as well. Please take a look at those cryptic comments before each S-box in nonstd.c and sboxes-s.c. > but in s-box functions ~30% of code are implementation > specific, like mov instructions. The s-box can be represented by a > directed acyclic graph and develop an algotithm to generate code with > the less instructions. I have done this manually i get ~20% better > than Microsoft C compiler for SSE2 assembly and i think and automatic > way speed up things more. How does your code compare (e.g., in terms of instruction count) to what's found in x86-64.S and x86-sse.S? These were generated with my Perl scripts, then hand-edited a bit. For x86-64, gcc 4.3.x (only these versions) generate very decent code as well (maybe even slightly better than mine due to instruction scheduling across S-box boundaries), but for 32-bit x86's SSE2 and MMX so far the Perl-generated and hand-edited code is the best I have seen. > There is also the fact that roman generate > various possibles variants of each s-box. There were thousands. Sometimes tens of thousands even. Roman and I ran them through the Perl scripts I mentioned and picked those producing better code - separately for different criteria: gate count, instruction count on 2-op archs, register count, estimated stall counts on an abstract single-issue CPU with different instruction latencies (2, 3, 4, 5, 6 cycles). The latter also approximates multi-issue CPUs. Since there were multiple criteria, several versions of many of the S-boxes were left in the released C files. > > Another related project would be producing a bitslice implementation of > > the Lotus5 hashing... > > Is possible a bit-slice implementation of AES? I think is possible. Yes. You can find papers on that. Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.