How to do really fast bit permutations with few operations

If you look at the specs of algorithms such as the now semi defunct DES, you are often required to do permutations of bits, i.e. changing the order of bits in a bit field.

One typical example is bit reversal, which comes handy even if you need to switch from little endian to big endian.

But let’s suppose you just need to shuffle bits in a predetermined order. There are lots of WRONG ways of doing this, there are lots of wrong solutions, which will make your program a lot slower than it could be.

Examples of painful slow solutions: use bit masking, use logical AND / OR, bring result into Carry flag, shifts.

If your instruction set allows for direct bit addressing ( e.g.: modern x86 architecture starting with 386 in protected mode), you can gain an about 5x speedup, but that’s not the intelligent way of doing permutations.

The right way:

at compile time:

1) Divide your bit fields in bytes or similar n convenient chunks.

2) build n tables, each of n elements, each element long as the entire bitfield.

3) for each table, each element at the row corresponding to the value of the “chunk” considered as a displacement, should contain “1″ in the permuted destination bits, if the corresponding bits in the original chunk  are themselves set to “1″ and pad to zero everything else.

at run time:

1) divide your bitfields in chunks, for each chunk read the row corresponding to its value in the corresponding table.

2) just OR together the results of the individual array reads.

i.e.: instead of m bit operations, if you need to permute 64 bits you just need 8 indexed reads and 7 OR operations.

That’s a lot better than trying 64 bit masks and shifting results around. Even if you have direct bit addressing, this solution will be 8-10 times faster.