[Cryptography] Exotic Operations in Primitive Construction

[Jerry Leichter]

>> As another followup (and I'm not trying to turn this into a C forum), but 
>> can anyone think of a way to flip an n-bit word around i.e. LSB becomes 
>> MSB etc?
>> 
> 
> Generally as follows. For simplicity's sake I've removed the container
> type you need to store an arbitrary sized number. You should see the
> size of the type as a potential parameter.
> 
> uint16_t reverse(uint16_t v) {
> 	uint16_t r = 0;
> 	for (int i = 0; i < 16; i++) {
> 		r |= (((1 << i) & v) >> i) << (15 - i);
> 	}
> 	return r;
> }
This is highly inefficient.  There's a classic trick:  To reverse an n-bit value, split it into two n/2-bit values; reverse each; and swap.  Repeat the recursion until you have a "small enough" remaining value, then look up the reversed value in a table.  A table mapping every 8-bit byte to its reverse is only 256 bytes long and will certainly fit in the cache of any modern CPU.  So:

uint8_t reverseByte[256] = {0x00, 0x80, 0x40, ...};

uint16_t reverse(uint16_t v) {
  uint8_t left = (v >> 8) & 0xFF;
  uint8_t right = v & 0xFF;
  return (reverseByte[left] << 16) | reverseByte[right];
}

The win is obvious even for 16 bits, and (assuming you open-code it, rather than writing a loop or doing a recursion) is even greater as you deal with longer words:  The loop is linear in the bit size; this is logarithmic.

If you want to deal with really long bit strings, they won't be represented as C primitive types - they'll be arrays of uintX_t's.  Most of the cost in this algorithm is splitting the uint16_t into its constituent bytes.  If the input is an array, most of the work is already done for you.

This will need to deal with bit strings that are not a power of two in length, the code gets more involved, but the same idea applies.

                                                        -- Jerry