[codereview] 3d bitboard rotation

[luser droog]

https://codereview.stackexchange.com/questions/181267/rotating-3d-bit-board-in-c

Interesting question came up on codereview about the best
way to do a 90-degree rotation of a 3d bit array stored
in a 64-bit unsigned long long.

I got as far as trying to mirror on the three axes.


static inline
unsigned long long bit( int x, int y, int x ){
return 1 << z*16 + y*4 + x;
}

static inline
unsigned long long mirror_x( unsigned long long b ){
return
(b&0x1111111111111111) << 3
| (b&0x2222222222222222) << 1
| (b&0x4444444444444444) >> 1
| (b&0x8888888888888888) >> 3;
}

static inline
unsigned long long mirror_y( unsigned long long b ){
return
(b&0x000f000f000f000f) << 12
| (b&0x00f000f000f000f0) << 4
| (b&0x0f000f000f000f00) >> 4
| (b&0xf000f000f000f000) >> 12;
}

static inline
unsigned long long mirror_z( unsigned long long b ){
return
(b&0x000000000000ffff) << 48
| (b&0x00000000ffff0000) << 16
| (b&0x0000ffff00000000) >> 16
| (b&0xffff000000000000) >> 48;
}

[zaca...@gmail.com]

If you're still interested, I think we've found the most efficient implementation by using delta swaps, a most intriguing technique, and it's all quite well documented, thanks to user Quuxplusone.
In terms of instructions, or clock cycles I should say, we're down to less than 30, which I think is rather impressive.
The only thing I'm not quite content with is the fact that normal mirroring, like your mirror_z() function, can be done just as efficiently using delta swaps, but I suppose it's a matter of compilers being rather good at optimization these days.
On ly thing I can think of is some obscure byte swap instruction, which as the name suggests reverses the order of the bytes. I've so far been unable to find any useful information on it, but it could possibly be useful.

That being said I'm quite content with what I've got. For my purposes it doesn't actually need to at all efficient, it was more of an exercise.


Best regards.