A way around the rotational issue

By | 27 April 2005

Haha! My roommate pointed out on Saturday that a bit-wise rotation is just like shifting a value X bits, and or-ing it with the same value shifted the opposite direction (word size)-X bits. For example: A = (A << 7) | (a >> 25) for a 32-bit variable. This means I can, in fact, perform really big variable shifting using a source array and a temporary holding variable for the first entry. See the following for an example of rotating a 96-bit value 3 bits left (3 32-bit entries): h = A[0]; A[0] = (A[0] << 3) | (A[1] >> 29); A[1] = (A[1] << 3) | (A[2] >> 29); A[2] = (A[2 << 3) | (h >> 29).

It’s a bit confusing at first blush, but it works, and it’s extensible to any size chunks you want to rotate. And it doesn’t have the overhead of an additional 2(N-bit) operations to expand and compress the value into a ‘real’ array first.

This means that I can also code my Wolf0 algorithm, the first one I’d come up with, without realizing too much of a performance hit.