Bit permutation tables in C

Question

Is there a pattern for, or a standard way to permute bits according to a permutation table that specifies for each bit position of the result - which position is taken from the source.

I.e. table 0322 would create result 0011 from 0010

My current strategy has been to read each entry of the table - create a bitmask and then perform a binary AND of the mask and the source, OR`ing that with a cumulative result.

so to process the first table entry:

result |= ( ( (int) pow(2,table[0]) & source)

This just seems expensive and repetitive and homebrewed. Am I missing some obvious standard easier way?

Answer 1

It's really expensive to use the pow function for this. The repetitive and home-brewed parts are unavoidable. A better way

result = 0;
for ( i = 0; i < table_size; i++ )
{ 
    result <<= 1;
    if ( source & (1 << table[i]) )
        result |= 1;
}

Answer 2

One possible use for this kind of coding is implementing an encryption algorithm. I've used this in DES and S-boxes, although it was a while ago. The key point is that performance matters. You need something fast.

My recommendation is to precompute the masks and unroll the loop. For your 4 bit example:

int bits[4] = { 1, 2, 4, 8 };
result = (bits[table[0]] & source)
       | (bits[table[1]] & source)
       | (bits[table[2]] & source)
       | (bits[table[3]] & source);

[I don't think this is the right algorithm, but it matches the question.]

But I would check the generated code. A good enough optimising compiler could convert your code into exactly this!