There is much literature on this subject but it may not be immediately obvious that the results are applicable here. A bit-cube can be considered as a stack of bit-planes. And rotation of a bitmap is a topic that underwent much study at Xerox PARC when they invented WIMP and GUI. An algorithm is presented in the Byte Magazine 1981 SmallTalk Issue on page 188. So, assume for simplicity that we have a 4x4 bitmap to rotate, mapped into 16 bits.
0 1 2 3
0 0 0 1 0
1 1 1 0 0
2 0 1 0 0
3 1 0 0 0
As the image at the bottom of that page illustrates, the steps of the algorithm are to:
- rotate the quadrants
- rotate the quadrants of the quadrants
- rotate the quadrants of the quadrants of the quadrants
- ..... until the quadrants just moved were pixel-sized, then we're done.
With 4 bits in a row, we only need 2 steps of taking quadrants before we're down to pixels.
uint16_t x = 0x1234;
x = (x & 0x0033) << 2 // upper left quadrant
| (x & 0x00cc) << 8 // upper right quadrant
| (x & 0xcc00) >> 2 // lower right quadrant
| (x & 0x3300) >> 8; // lower left quadrant
x = (x & 0x0505) << 1 // upper left bits of all quadrants!
| (x & 0x0a0a) << 4 // upper right bits
| (x & 0xa0a0) >> 1 // lower right bits
| (x & 0x5050) >> 4; // lower left bits
Notice that in the "recursive" second step, operations parallelize over all sub-quadrants by selecting more pieces with the mask.
Now watch what happens if we extend this to a stack of 2 bit-planes. 2 4x4 bitmaps in 32 bits.
uint32_t x = 0x00001234;
x = (x & 0x00330033) << 2 // upper left quadrants of both planes!
| (x & 0x00cc00cc) << 8 // upper right quadrants
| (x & 0xcc00cc00) >> 2 // lower right quadrants
| (x & 0x33003300) >> 8; // lower left quadrants
x = (x & 0x05050505) << 1 // upper left bits of all quadrants of all planes!
| (x & 0x0a0a0a0a) << 4 // upper right bits
| (x & 0xa0a0a0a0) >> 1 // lower right bits
| (x & 0x50505050) >> 4; // lower left bits
The number of operations doesn't increase! only the lengths of the masks increase.
Extension to 4x4x4 is left as a (trivial) exercise.