Neat x86 trick

While these days it's becoming more and more of a forgotten art, bit wizardry and size coding is a fascinating subject. Many such tricks are known, and published over the decades in venues ranging from HAKMEM, to several books, to the venerable Art of Computer Programming.

In this post I show one such trick I didn't find anywhere else (although I didn't look that hard). Suppose you want to increment and decrement integers with a defined floor and ceiling; let us call those f and c. We can avoid branching by doing

sub eax, c

adc eax, c

to increment, and

sub eax, f+1

adc eax, f

to decrement. You can see that, by making clever use of the carry flag, one avoids both extra registers (as with, e.g., cmov) and branching.

Having fun with C++ metaprogramming

C++ is not a simple language. Sometimes that sucks. Sometimes we can use it to our advantange (or at least convenience).

Inspired by a recent article on compile-time string encryption, I decided to up the ante by implementing actual encryption: AES-128.

As most of you will know, the AES is composed by 4 main subroutines, which are repeated 10 times to complete the encryption of a single 16-byte block: AddRoundKey, SubBytes, ShiftRows, MixColumns.

The AddRoundKey, ShiftRows, and MixColumns subroutines mostly just shuffle and xor bytes together, thus not being any real challenge to implement. The SubBytes transformation is the trickiest to achieve, and its main component, the S-box, can be performed in two ways. The first involves specializing each template argument to the S-box for each of the 256 possible positions. The second uses the algebraic representation of the Sbox, as

S(a) = M (a^-1) + b,

where the field is F_2[x]/(x^8 + x^4 + x^3 + x + 1), M is a 8x8 F_2 matrix, and b can be represented by the 0x63 hexadecimal integers.

Once the S-box is done, it's just a matter of putting everything together and using standard looping techniques for C++ metaprogramming (feel free to read some literature, if you're not familiar).


Without further ado, here's the proof-of-concept code implementing the AES:
AES Implementation


If you're interested in more C++ metaprogramming code, check the Boost or Blitz projects; they ought to keep you busy for a while.