Rotating 3D bit board in C

Question

I've got a 64 bit bitboard, but instead of interpreting as an 8 by 8 binary matrix, as is usually the case, I've taken it to the third dimension, so to speak.

Now mirroring and even rotating by 180 degrees on any individual axis is, if I'm not mistaken, fairly simple, but rotating by 90 degrees, which is what I actually need, has given me a nasty headache.

I have of course come up with a solution, but I would like to ensure that there isn't a better way, because frankly it's a bit much.

Anyway, here an example function, rotating, I suppose, clockwise on the Y axis:

unsigned long long rotateLeft( unsigned long long bs )
{
     return ( ( bs & 0x0000000000001111 ) << 48 ) |
            ( ( bs & 0x0000000000002222 ) << 31 ) |
            ( ( bs & 0x0000000000004444 ) << 14 ) |
            ( ( bs & 0x0000000000008888 ) >>  3 ) |
            ( ( bs & 0x0000000011110000 ) << 33 ) |
            ( ( bs & 0x0000000022220000 ) << 16 ) |
            ( ( bs & 0x0000000044440000 ) >>  1 ) |
            ( ( bs & 0x0000000088880000 ) >> 18 ) |
            ( ( bs & 0x0000111100000000 ) << 18 ) |
            ( ( bs & 0x0000222200000000 ) <<  1 ) |
            ( ( bs & 0x0000444400000000 ) >> 16 ) |
            ( ( bs & 0x0000888800000000 ) >> 33 ) |
            ( ( bs & 0x1111000000000000 ) <<  3 ) |
            ( ( bs & 0x2222000000000000 ) >> 14 ) |
            ( ( bs & 0x4444000000000000 ) >> 31 ) |
            ( ( bs & 0x8888000000000000 ) >> 48 );
}

I suppose 16 shifts, 16 ANDs and 15 ORs is not actually that bad, but I cannot believe that this is the best option.

So is there another/better way? I need both direction for the X and Y axis, but I suppose the solution will be somewhat similar for all of them, assuming of course that there is a better way.

Come to think of it you could do something like:

unsigned long long rotateLeft( unsigned long long bs )
{
    //mirror in diagonal plane (x=z?)
    bs =   ( ( bs & 0x0000000000008888 ) << 45 ) | ( ( bs & 0x1111000000000000 ) >> 45 ) |
           ( ( bs & 0x0000000088884444 ) << 30 ) | ( ( bs & 0x2222111100000000 ) >> 30 ) |
           ( ( bs & 0x0000888844442222 ) << 15 ) | ( ( bs & 0x4444222211110000 ) >> 15 ) |
             ( bs & 0x8888444422221111 );
    //mirror in vertical plane (xy?)
    //I do apologize  for not knowing the correct terminology.
    bs =   ( ( bs & 0x00000000ffffffff ) << 32 ) | ( ( bs & 0xffffffff00000000 ) >> 32 );
    return ( ( bs & 0x0000ffff0000ffff ) << 16 ) | ( ( bs & 0xffff0000ffff0000 ) >> 16 ) |
}

I would even think that could be improved a bit without too much effort. Still, I'd be interested in any suggestions.

edit: I've been informed that clarification is needed, so I'll do my best. Firstly, structurally I'm talking about a 4 by 4 by 4 cube. Line 1 of layer 1 consist of bits 0 through 3 Line 2 of layer 2 of bits 20 through 23 layer 3 of bits 32 through 47 and so on. for each layer lsb is at the top left and msb is bottom right, counting line wise.

and example of rotating left could be: layer 1-4:

1000 0000 0000 0000
0100 0000 0000 0000
0010 0000 0000 0000
0001 0000 0000 0000

to

0000 0000 0000 1000
0000 0000 1000 0000
0000 1000 0000 0000
1000 0000 0000 0000

or

0x0000 0000 0000 8421

to

0x1000 0100 0010 0001

I hope this clarifies matters a bit.

edit 2: as request, here the implementation:

uint64_t board_with_exactly_one_bit_set(int x, int y, int z)
{
    return 1 << ( z*16 +y*4 +x );
}

Could you explain which bit corresponds to which (x,y,z) position? It isn't obvious from your code. — JS1, Commented Nov 25, 2017 at 2:05
+1 to JS1's comment. I'm not even sure if I'm guessing correctly that your board is 4x4x4! You can answer this question easily by providing the implementation of the function uint64_t board_with_exactly_one_bit_set(int x, int y, int z). Given that function, everyone should be able to deduce exactly the same interpretation of operations such as "rotate 90 degrees RHRward around the Y axis." — Quuxplusone, Commented Nov 25, 2017 at 5:27
I guess I wasn't particular clear, just figure it would be obvious. Anyway, we count from the top left as always, line by line and then layer by layer, thus line 1 of layer 1 is bit 0-3, layer 1 is bit 0-15, layer 2 16-31, and so on, and yes, it is of course 4 by 4 by 4. So, if we have and actual value of 0x81, well end up with by rotation one of four directions. up: 0x0001000800000000 left: 0x0001000000000010 down: 0x0000000080001000 right: 0x0080000000000008 If I'm not much mistaken. I'll try to edit the post for more clarity. — Zacariaz, Commented Nov 25, 2017 at 12:22
@Zacariaz: You must have missed my comment where I explained how to unambiguously communicate the answer. It's currently right above your last comment on this question (which is right above the comment I am now typing). — Quuxplusone, Commented Nov 26, 2017 at 18:01
I don't think I can make it any clearer than I already have. Orientation and direction is not really relevant, the general method is. In any case, I've thought a lot about the issue, and I rather doubt it can be done any more effectively, except perhaps on the one axis I don't need to rotate on. As for the implementation requested, which I did rather mis the point of the first time around, I'll add it now. — Zacariaz, Commented Nov 26, 2017 at 21:28

Quuxplusone · Accepted Answer · 2017-11-29 19:02:18Z

Update to my previous answer!

The original questioner (@Zacariaz) reported that "I'm currently looking into so-called delta swaps." I don't know how Zacariaz got turned onto them, but they are indeed amazingly efficient at doing bit-permutations. (So I can at least feel good that I identified the root problem here as "bit-permutation," even if I didn't know the best solution.)

The online generator, written by Jasper Neumann, comes with C++ source code; click the link to calcperm.* at the bottom of that page.

Using Jasper Neumann's generator, I found the best rotation code so far. It uses this primitive:

inline constexpr uint64_t delta_swap(uint64_t a, int delta, uint64_t mask)
{
    if (((mask >> delta) ^ mask) == 0xFFFF'FFFF'FFFF'FFFF) {
        return ((a << delta) & mask) | ((a & mask) >> delta);
    } else {
        uint64_t b = (a ^ (a << delta)) & mask;
        return a ^ b ^ (b >> delta);
    }
}

Notice that we will only ever use this function with integer-literal delta and mask arguments, so the if is testing a compile-time-known value and will be optimized away by the compiler. On the other hand, neither Clang nor GCC seems smart enough to figure out that the math in the "else" branch is equivalent to the math in the "if" branch; so by providing the optimized "if" branch explicitly, we're helping Clang and GCC save a couple of instructions.

Here's the "x" rotation:

uint64_t rotate_right_around_x_axis(uint64_t o)
{
    uint64_t r = o;
    r = delta_swap(r, 32, 0xffffffff00000000);
    r = delta_swap(r, 16, 0xffff0000ffff0000);
    r = delta_swap(r, 24, 0x00ff00ff00000000);
    r = delta_swap(r, 12, 0x0f0f00000f0f0000);
    return r;
}

A cool thing about delta swaps — besides how efficient they are — is that to get the inverse permutation (a.k.a. "rotate left around x axis"), all you have to do is invert the order of the swaps! (Swaps that don't interact with each other don't have to be inverted. I found it aesthetically pleasing to keep such swaps in decreasing order of shift value.)

uint64_t rotate_left_around_x_axis(uint64_t o)
{
    uint64_t r = o;
    r = delta_swap(r, 24, 0x00ff00ff00000000);
    r = delta_swap(r, 12, 0x0f0f00000f0f0000);
    r = delta_swap(r, 32, 0xffffffff00000000);
    r = delta_swap(r, 16, 0xffff0000ffff0000);
    return r;
}

And the rest of the rotations:

uint64_t rotate_right_around_y_axis(uint64_t o)
{
    uint64_t r = o;
    r = delta_swap(r, 32, 0xffffffff00000000);
    r = delta_swap(r, 16, 0xffff0000ffff0000);
    r = delta_swap(r, 34, 0xcccccccc00000000);
    r = delta_swap(r, 17, 0xaaaa0000aaaa0000);
    return r;
}
uint64_t rotate_left_around_y_axis(uint64_t o)
{
    uint64_t r = o;
    r = delta_swap(r, 34, 0xcccccccc00000000);
    r = delta_swap(r, 17, 0xaaaa0000aaaa0000);
    r = delta_swap(r, 32, 0xffffffff00000000);
    r = delta_swap(r, 16, 0xffff0000ffff0000);
    return r;
}
uint64_t rotate_right_around_z_axis(uint64_t o)
{
    uint64_t r = o;
    r = delta_swap(r, 8, 0xff00ff00ff00ff00);
    r = delta_swap(r, 4, 0xf0f0f0f0f0f0f0f0);
    r = delta_swap(r, 6, 0x3300330033003300);
    r = delta_swap(r, 3, 0x5050505050505050);
    return r;
}
uint64_t rotate_left_around_z_axis(uint64_t o)
{
    uint64_t r = o;
    r = delta_swap(r, 6, 0x3300330033003300);
    r = delta_swap(r, 3, 0x5050505050505050);
    r = delta_swap(r, 8, 0xff00ff00ff00ff00);
    r = delta_swap(r, 4, 0xf0f0f0f0f0f0f0f0);
    return r;
}

Notice that they are all very similar in flow: the four shift counts are always "power-of-two, half-that-number; non-power-of-two, half-that-number" for right rotations. This is unsurprising in retrospect because our cube-rotations are naturally isomorphic in terms of how many sets of bits are switching places. The only difference is which indexes are contained in those sets of bits.

Notice that the 32-16 swap that shows up in the "x" and "y" rotations is a "reverse-words-in-the-qword" operation, and the 8-4 swap in the "z" rotations is a "reverse-nybbles-in-each-word" operation. The x86-64 processor has a built-in "reverse-bytes-in-the-qword" operation (bswapq) but does not have any faster way to do the 32-16 or 8-4 swaps as far as I know. (We do the former in 9 instructions and the latter in 17.)

The code for these rotations, and (non-exhaustive) test cases for them, is now located on my GitHub at https://github.com/Quuxplusone/rot4x4x4.

You can investigate the assembly code for these rotations on Matt Godbolt's Compiler Explorer: https://godbolt.org/g/DJrM6i

I honestly didn't think it could be improved, but apparently I was wrong. While your example is no more efficient in terms of instructions than what I posted, if you 32 bit delta swaps for a simple (b>>32)|(b<<32), you will, as far as I can figure, save a couple of instructions as it can be done very efficiently. This won't work for the z-axis, but since I don't need that, it's all good. ;) I'll see if I can change my pick of answer because you certainly earned it. — Zacariaz, Commented Nov 29, 2017 at 20:44
As it were, with you moving the order around, employing my previous suggestion, we're apparently down to 22 instruction. I guess I'll just have to test them all now. — Zacariaz, Commented Nov 29, 2017 at 21:07
Okay, so that's why we do test. Using the previously mentioned trick, right on X got down to an amazing 22 instruction, but the same does not work for left on Y. I'm sitting staring at the assembly, trying to figure it out, but there must be some special case of optimization on the first case. — Zacariaz, Commented Nov 29, 2017 at 21:21
@Zacariaz, can you clarify what you mean by "my previous suggestion / previously mentioned trick"? I have found that we can save a movabsq on GCC (but not on Clang) by rewriting ((a << delta) & mask) | ((a & mask) >> delta) into (~(~a | mask) << delta) | ((a & mask) >> delta), but that still leaves me at 26 instructions, not 22. (The swap with shift=32 already compiles down to a single instruction: rorx.) — Quuxplusone, Commented Nov 29, 2017 at 21:45
I see now what the purpose of that if statement was, I've been such an idiot. Never mind my rambling. Furthermore, while trying to recreate the situation I mentioned, I can't. I checked the case thoroughly for mistakes, but I get there must have been one. — Zacariaz, Commented Nov 29, 2017 at 21:50

Quuxplusone · Accepted Answer · 2017-11-26 22:17:47Z

First of all, it might help to explain the problem domain; you might have an XY problem here. The first application for "4x4x4 bitboards" that pops into my head is that you're dealing with Rubik's Revenge... but representing cubelets by single bits is not of obvious utility to me, and rotating the entire cube by 90 degrees is even less useful.

Next, this does seem like the sort of thing that has a known solution somewhere, so I'd definitely recommend doing a thorough Google search. (Asking StackOverflow might also be appropriate; but that's just offloading the Google search onto somebody else. It would be polite to do some searching yourself first, and report the results.) I didn't do any searching myself other than a quick fruitless skim through HAKMEM; but if you find out "the" answer, I'd be mildly interested to hear about it.

Okay, so, let's assume that we've got a 4x4x4 bitboard that looks like this:

uint64_t board_with_one_bit_set(int x, int y, int z)
{
    int index = (x + 4*y + 16*z);
    return 1uLL << index;
}

Notice that "rotating a bitboard" is a special case of "permuting the bits in a word." That is, we expect our result to have the same parity as the input — and in fact the same bits, just in a different order. So mathematically it might make more sense to think of this as a permutation of a 64-element sequence, rather than as a bunch of imperative shifts and masks.

To avoid brain farts, I decided to write a little Python script to generate the bit-shifting code from the permutation. Here's the input:

original = [
    63, 62, 61, 60,
    59, 58, 57, 56,
    55, 54, 53, 52,
    51, 50, 49, 48,
                   47, 46, 45, 44,
                   43, 42, 41, 40,
                   39, 38, 37, 36,
                   35, 34, 33, 32,
                                  31, 30, 29, 28,
                                  27, 26, 25, 24,
                                  23, 22, 21, 20,
                                  19, 18, 17, 16,
                                                 15, 14, 13, 12,
                                                 11, 10, 9,  8,
                                                 7,  6,  5,  4,
                                                 3,  2,  1,  0,
]
rotated_right_around_x_axis = [
    51, 50, 49, 48,
    35, 34, 33, 32,
    19, 18, 17, 16,
    3,  2,  1,  0,
                   55, 54, 53, 52,
                   39, 38, 37, 36,
                   23, 22, 21, 20,
                   7,  6,  5,  4,
                                  59, 58, 57, 56,
                                  43, 42, 41, 40,
                                  27, 26, 25, 24,
                                  11, 10, 9,  8,
                                                 63, 62, 61, 60,
                                                 47, 46, 45, 44,
                                                 31, 30, 29, 28,
                                                 15, 14, 13, 12,
]

(I think this is right. "Rotating right around the x axis" means pointing your right thumb in the direction of increasing x, which I think of as "to the left", and curling your fingers in the direction of the rotation, which I think of as "top-moves-away". However, even with this much effort to avoid brain farts, I might have messed it up.)

Here's the Python code for converting the input into a C++ function body:

def to_cpp11_hex(mask):
    return "0x%04X'%04X'%04X'%04X" % (
        ((mask >> 48) & 0xFFFF),
        ((mask >> 32) & 0xFFFF),
        ((mask >> 16) & 0xFFFF),
        ((mask >> 0) & 0xFFFF),
    )

def print_function_body(original, rotated):
    bits_by_rotation = {}
    for b in xrange(64):
        o = original.index(b)
        r = rotated.index(b)
        rotl_amount = ((o - r) + 64) % 64
        bits_by_rotation.setdefault(rotl_amount, []).append(r)
    print '    uint64_t r = 0;'
    for amount, bits in sorted(bits_by_rotation.iteritems()):
        mask = sum(1 << b for b in bits)
        print '    r |= rotl(o, %d) & %s;' % (amount, to_cpp11_hex(mask))
    print '    return r;'

print_function_body(original, rotated_right_around_x_axis)

This script generates functions like the following:

inline constexpr uint64_t rotl(uint64_t x, int k)
{
    return (x << k) | (x >> (64-k));
}

uint64_t rotate_left_around_x_axis(uint64_t o)
{
    uint64_t r = 0;
    r |= rotl(o, 4) & 0x0000'00F0'0000'0000;
    r |= rotl(o, 8) & 0x0000'0000'0000'0F00;
    r |= rotl(o, 12) & 0x000F'0000'0000'0000;
    r |= rotl(o, 16) & 0xF000'0000'00F0'0000;
    r |= rotl(o, 24) & 0x0000'000F'0000'0000;
    r |= rotl(o, 28) & 0x0000'F000'0000'00F0;
    r |= rotl(o, 36) & 0x0F00'0000'000F'0000;
    r |= rotl(o, 40) & 0x0000'0000'F000'0000;
    r |= rotl(o, 48) & 0x0000'0F00'0000'000F;
    r |= rotl(o, 52) & 0x0000'0000'0000'F000;
    r |= rotl(o, 56) & 0x00F0'0000'0000'0000;
    r |= rotl(o, 60) & 0x0000'0000'0F00'0000;
    return r;
}

uint64_t rotate_right_around_x_axis(uint64_t o)
{
    uint64_t r = 0;
    r |= rotl(o, 4) & 0x0000'0000'00F0'0000;
    r |= rotl(o, 8) & 0x0000'F000'0000'0000;
    r |= rotl(o, 12) & 0x0000'0000'0000'000F;
    r |= rotl(o, 16) & 0x000F'0000'0F00'0000;
    r |= rotl(o, 24) & 0x0000'0000'0000'00F0;
    r |= rotl(o, 28) & 0x00F0'0000'F000'0000;
    r |= rotl(o, 36) & 0x0000'000F'0000'0F00;
    r |= rotl(o, 40) & 0x0F00'0000'0000'0000;
    r |= rotl(o, 48) & 0x0000'00F0'0000'F000;
    r |= rotl(o, 52) & 0xF000'0000'0000'0000;
    r |= rotl(o, 56) & 0x0000'0000'000F'0000;
    r |= rotl(o, 60) & 0x0000'0F00'0000'0000;
    return r;
}

I don't immediately see any improvements. I had various ideas, such as trying to incrementally rotate o by repetitions of

    r |= (o = rotl(o, 4-or-8)) & MASK;

or limiting all the masks to 32 bits for x86-64-friendliness

def print_function_body_32bit(original, rotated):
    bits_by_rotation = {}
    for b in xrange(32, 64):
        o = original.index(b)
        r = rotated.index(b)
        rotl_amount = ((o - r) + 64) % 64
        bits_by_rotation.setdefault(rotl_amount, []).append(r)
    print '    uint64_t r = 0;'
    for amount, bits in sorted(bits_by_rotation.iteritems()):
        mask = sum(1 << b for b in bits)
        print '    r |= rotl(o, %d) & %s;' % ((amount + 32) % 64, to_cpp11_hex((mask >> 32) & 0xFFFFFFFF))
    print '    r <<= 32;'
    bits_by_rotation = {}
    for b in xrange(0, 32):
        o = original.index(b)
        r = rotated.index(b)
        rotl_amount = ((o - r) + 64) % 64
        bits_by_rotation.setdefault(rotl_amount, []).append(r)
    for amount, bits in sorted(bits_by_rotation.iteritems()):
        mask = sum(1 << b for b in bits)
        print '    r |= rotl(o, %d) & %s;' % (amount, to_cpp11_hex(mask & 0xFFFFFFFF))
    print '    return r;'

which generates function bodies like

uint64_t rotate_right_around_x_axis(uint64_t o)
{
    uint64_t r = 0;
    r |= rotl(o, 36) & 0x0000'0000'0000'0000;
    r |= rotl(o, 44) & 0x0000'0000'0000'0000;
    r |= rotl(o, 48) & 0x0000'0000'000F'0000;
    r |= rotl(o, 56) & 0x0000'0000'0000'0000;
    r |= rotl(o, 60) & 0x0000'0000'00F0'0000;
    r |= rotl(o, 4) & 0x0000'0000'0000'000F;
    r |= rotl(o, 16) & 0x0000'0000'0000'00F0;
    r |= rotl(o, 24) & 0x0000'0000'0000'0000;
    r <<= 32;
    r |= rotl(o, 8) & 0x0000'0000'0000'0000;
    r |= rotl(o, 16) & 0x0000'0000'0F00'0000;
    r |= rotl(o, 28) & 0x0000'0000'F000'0000;
    r |= rotl(o, 36) & 0x0000'0000'0000'0F00;
    r |= rotl(o, 40) & 0x0000'0000'0000'0000;
    r |= rotl(o, 48) & 0x0000'0000'0000'F000;
    r |= rotl(o, 52) & 0x0000'0000'0000'0000;
    r |= rotl(o, 60) & 0x0000'0000'0000'0000;
    return r;
}

which are nevertheless longer (in terms of number of assembly instructions) than the more "naïve" 64-bit version.

Writing an appropriate benchmark for the various possibilities, and writing out the permutation matrices for rotated_right_around_y_axis and rotated_right_around_z_axis, are left as exercises for the interested reader.

It would also be supremely interesting to feed these "rotation-permutation" functions to a superoptimizer and see what it produces. However, my wild-ass guess is that the optimal instruction sequence is in excess of 40 instructions, which would (I think) make it intractable for the current state-of-the-art in superoptimizers. But I could be wrong. Anyway, if you find out, it would be interesting to post the results here.

Firstly, thank for the great effort. I'll read it more thuroughly later. That being said, I would like to point out that I have in fact done rather a lot of google searching on this particular problem, not only the last few days, but on various occasions over the last years. However, all I've been able to find ahs to do with 2D boards. This information does have some aplications, but not for this particular issue I think. Last, how many instructions would you guestimate my second function to be? Seems to me no more than 32, but perhaps I'm mistaken. — Zacariaz, Commented Nov 27, 2017 at 9:49
Oh yes, just to clarify, I would very much like to avoid doing these rotation, but for my particular use case, the alternative would likely be impractical. In any case, it's an interesting question, so there's that. — Zacariaz, Commented Nov 27, 2017 at 9:56
@Zacariaz: You can check the assembly of any C++ function on godbolt. Your second function has a typo on the return line, but if I replace the | with a ;, it's 41 instructions. — Quuxplusone, Commented Nov 27, 2017 at 20:39
I have already checked the assembly, and I must admit I'm was a bit confused about the result, but then again, I don't really know much about assembly. Regardless, your flags seem to have cleaned it all up nicely. I'll make sure to fix the typo. I also tried your second rotate_right_around_x_axis(), which is far superior in terms of lines of assembly, but it doesn't seem to work either and I can't exactly claim to understand the implementation. Anyway, thanks again. — Zacariaz, Commented Nov 27, 2017 at 22:00
@Zacariaz: I noticed that my rotate functions and yours didn't match up. I took an hour just now and fixed my Python-script approach to match yours, and added some unit tests. Here's the result on GitHub: github.com/Quuxplusone/rot4x4x4/blob/master/rotations.h — Quuxplusone, Commented Nov 28, 2017 at 0:16

Zacariaz · Accepted Answer · 2017-11-29 19:14:01Z

I've finished what I believe to be the final solution. It's both pretty and efficient:

static inline uint64_t delta_swap( uint64_t b, int delta, uint64_t mask )
{
    uint64_t t = ( b ^ ( b << delta ) ) & mask;
    return b ^ t ^ ( t >> delta );
}
uint64_t rotate_left_around_y_axis( uint64_t b ) // Right
{
    b = delta_swap( b, 34, 0xcccccccc00000000 );
    b = delta_swap( b, 17, 0xaaaa0000aaaa0000 );
    b = delta_swap( b, 16, 0xffff0000ffff0000 );
    return ( b >> 32 ) | ( b << 32 );
}
uint64_t rotate_right_around_y_axis( uint64_t b ) // Left
{
    b = delta_swap( b, 30, 0x3333333300000000 );
    b = delta_swap( b, 15, 0x5555000055550000 );
    b = delta_swap( b, 16, 0xffff0000ffff0000 );
    return ( b >> 32 ) | ( b << 32 );
}
uint64_t rotate_right_around_x_axis( uint64_t b ) // Up
{
    b = delta_swap( b, 24, 0x00ff00ff00000000 );
    b = delta_swap( b, 12, 0x0f0f00000f0f0000 );
    b = delta_swap( b, 16, 0xffff0000ffff0000 );
    return ( b >> 32 ) | ( b << 32 );
}
uint64_t rotate_left_around_x_axis( uint64_t b ) // Down
{
    b = delta_swap( b, 40, 0xff00ff0000000000 );
    b = delta_swap( b, 20, 0xf0f00000f0f00000 );
    b = delta_swap( b, 16, 0xffff0000ffff0000 );
    return ( b >> 32 ) | ( b << 32 );
}

Rotating around the Z axis is left as an exercise, as it's actually the easiest to do and I don't need it. Beware though that the ladder 2 lines of code in the functions for Z will have to be changed slightly and that they will be slightly less efficient than the functions for X and Y.

To understand the code you'll need of course to understand the basics of working with bitwise operator and bitboards, but more importantly you'll need to understand Delta Swaps. A couple of resources are: https://reflectionsonsecurity.wordpress.com/2014/05/11/efficient-bit-permutation-using-delta-swaps/ https://chessprogramming.wikispaces.com/General+Setwise+Operations#DeltaSwap

The comment section of Quuxplusone's answer should also prove enlightening.

I'm going to accept my own answer, for the sake of documentation you might say, but no small amount of credit should go to Quuxplusone.

Best regards.

Zacariaz · Accepted Answer · 2017-12-05 14:40:18Z

For the sake of completion and because, "why not?", I make a complete, and I do mean complete list of function in 1, 2, 3 and 6, yes I said 6 dimension. Note that I've split up the operations, so that if you want to for example rotate around the X axis in 3 dimension (whatever direction) you will need the Flip AND Flip Diag function. Furthermore, since I couldn't figure out what to call the axis of the higher dimensions, all axis are now labeled X0 through X5, instead of x, y, z, w/t, etc. Please note that while I do believe that the functions for 6 dimensions are correct, I offer no guarantee. That being said, whatever dimension you want to work in, this list of functions should allow you to reach all rotations and symmetries, 2 for 1d, 8 for 2d, 48 for 3d and I do believe 240 for 6d, but I suppose that is irrelevant. Also, I've "reversed" the deltaSwap function for no other reason than I think somehow it's more correct this way, so do beware that using the deltaSwap function from earlier examples will yield an incorrect result. The naming scheme can be somewhat confusing, at least I had a hard time coming up with one, but here's an explanations as fa as I can explain it.

FlipX0_2D() result in what we would consider a "mirrored" image or patter, thus it "flips" the pattern in the direction of the vector (I think that's the right terminology) that is X0, or just plain x if you prefer. FlipDiagX0_X1_2D() and FlpDiagX1_X0_2D() is slightly more confusing, but basically ascending order means ascending order means it flippes in the direction perpendicular to the diagonal "vector" going through 0,0, and descending of course means the reverse. I should've changed the order I suppose, but this make more sense to me for some reason. If in doubt, test in 2D. The same principles of course goes for higher dimensions. Lastly I'd very much like to hear if anyone finds an application for this, and I'd also appreciate suggestions as to how I can improve my somewhat confusing explanation.

Best regards.

#include <stdint.h>

static inline uint64_t deltaSwap( uint64_t b, int delta, uint64_t mask )
{
    if( ( ( mask<<delta )^mask ) == 0xffffffffffffffff )
        return ( ( b>>delta )&mask )|( ( b&mask )<<delta );
    uint64_t t = ( b^( b >> delta ) )&mask;
    return b^t^( t << delta );
}

//1D

uint64_t brFlip_X0_1D( uint64_t b )
{
    b = deltaSwap( b, 32, 0x00000000ffffffff );
    b = deltaSwap( b, 16, 0x0000ffff0000ffff );
    b = deltaSwap( b,  8, 0x00ff00ff00ff00ff );
    b = deltaSwap( b,  4, 0x0f0f0f0f0f0f0f0f );
    b = deltaSwap( b,  2, 0x3333333333333333 );
    b = deltaSwap( b,  1, 0x5555555555555555 );
    return b;
}

//2D

uint64_t brFlip_X1_2D( uint64_t b )
{
    b = deltaSwap( b, 32, 0x00000000ffffffff );
    b = deltaSwap( b, 16, 0x0000ffff0000ffff );
    b = deltaSwap( b,  8, 0x00ff00ff00ff00ff );
    return b;
}

uint64_t brFlip_X0_2D( uint64_t b )
{
    b = deltaSwap( b,  4, 0x0f0f0f0f0f0f0f0f );
    b = deltaSwap( b,  2, 0x3333333333333333 );
    b = deltaSwap( b,  1, 0x5555555555555555 );
    return b;
}

uint64_t brFlipDiag_X0_X12D( uint64_t b )
{
    b = deltaSwap( b, 28, 0x00000000f0f0f0f0 );
    b = deltaSwap( b, 14, 0x0000cccc0000cccc );
    b = deltaSwap( b,  7, 0x00aa00aa00aa00aa );
    return b;
}

uint64_t brFlipDiag_X1_X0_2D( uint64_t b )
{
    b = deltaSwap( b, 36, 0x000000000f0f0f0f );
    b = deltaSwap( b, 18, 0x0000333300003333 );
    b = deltaSwap( b,  9, 0x0055005500550055 );
    return b;
}

//3D

uint64_t brFlipX2_3D( uint64_t b )
{
    b = deltaSwap( b, 32, 0x00000000ffffffff );
    b = deltaSwap( b, 16, 0x0000ffff0000ffff );
    return b;
}

uint64_t brFlipX1_3D( uint64_t b )
{
    b = deltaSwap( b,  8, 0x00ff00ff00ff00ff );
    b = deltaSwap( b,  4, 0x0f0f0f0f0f0f0f0f );
    return b;
}

uint64_t brFlipX0_3D( uint64_t b )
{
    b = deltaSwap( b,  2, 0x3333333333333333 );
    b = deltaSwap( b,  1, 0x5555555555555555 );
    return b;
}

uint64_t brFlipDiagX0_X1_3D( uint64_t b )
{
    b = deltaSwap( b,  6, 0x00cc00cc00cc00cc );
    b = deltaSwap( b,  3, 0x0a0a0a0a0a0a0a0a );
    return b;
}

uint64_t brFlipDiagX1_X0_3D( uint64_t b )
{
    b = deltaSwap( b, 10, 0x0033003300330033 );
    b = deltaSwap( b,  5, 0x0505050505050505 );
    return b;
}

uint64_t brFlipDiagX0_X2_3D( uint64_t b )
{
    b = deltaSwap( b, 30, 0x00000000cccccccc );
    b = deltaSwap( b, 15, 0x0000aaaa0000aaaa );
    return b;
}

uint64_t brFlipDiagX2_X0_3D( uint64_t b )
{
    b = deltaSwap( b, 34, 0x0000000033333333 );
    b = deltaSwap( b, 17, 0x0000555500005555 );
    return b;
}

uint64_t brFlipDiagX1_X2_3D( uint64_t b )//16,4
{
    b = deltaSwap( b, 24, 0x00000000ff00ff00 );
    b = deltaSwap( b, 12, 0x0000f0f00000f0f0 );
    return b;
}

uint64_t brFlipDiagX2_X1_3D( uint64_t b )
{
    b = deltaSwap( b, 40, 0x0000000000ff00ff );
    b = deltaSwap( b, 20, 0x00000f0f00000f0f );
    return b;
}

//6D

uint64_t brFlipX5_6D( uint64_t b )
{
    b = deltaSwap( b, 32, 0x00000000ffffffff );
    return b;
}
uint64_t brFlipX4_6D( uint64_t b )
{
    b = deltaSwap( b, 16, 0x0000ffff0000ffff );
    return b;
}
uint64_t brFlipX3_6D( uint64_t b )
{
    b = deltaSwap( b,  8, 0x00ff00ff00ff00ff );
    return b;
}
uint64_t brFlipX2_6D( uint64_t b )
{
    b = deltaSwap( b,  4, 0x0f0f0f0f0f0f0f0f );
    return b;
}
uint64_t brFlipX1_6D( uint64_t b )
{
    b = deltaSwap( b,  2, 0x3333333333333333 );
    return b;
}
uint64_t brFlipX0_6D( uint64_t b )
{
    b = deltaSwap( b,  1, 0x5555555555555555 );
    return b;
}

uint64_t brFlipDiagX5_X4_6D( uint64_t b )
{
    b = deltaSwap( b,48, 0x000000000000ffff );
    return b;
}
uint64_t brFlipDiagX4_X5_6D( uint64_t b )
{
    b = deltaSwap( b,16, 0x00000000ffff0000 );
    return b;
}
uint64_t brFlipDiagX5_X3_6D( uint64_t b )
{
    b = deltaSwap( b,40, 0x0000000000ff00ff );
    return b;
}
uint64_t brFlipDiagX3_X5_6D( uint64_t b )
{
    b = deltaSwap( b,24, 0x00000000ff00ff00 );
    return b;
}
uint64_t brFlipDiagX5_X2_6D( uint64_t b )
{
    b = deltaSwap( b,36, 0x000000000f0f0f0f );
    return b;
}
uint64_t brFlipDiagX2_X5_6D( uint64_t b )
{
    b = deltaSwap( b,28, 0x00000000f0f0f0f0 );
    return b;
}
uint64_t brFlipDiagX5_X1_6D( uint64_t b )
{
    b = deltaSwap( b,34, 0x0000000033333333 );
    return b;
}
uint64_t brFlipDiagX1_X5_6D( uint64_t b )
{
    b = deltaSwap( b,30, 0x00000000cccccccc );
    return b;
}
uint64_t brFlipDiagX5_X0_6D( uint64_t b )
{
    b = deltaSwap( b,33, 0x0000000055555555 );
    return b;
}
uint64_t brFlipDiagX0_X5_6D( uint64_t b )
{
    b = deltaSwap( b,31, 0x00000000aaaaaaaa );
    return b;
}
uint64_t brFlipDiagX4_X3_6D( uint64_t b )
{
    b = deltaSwap( b,24, 0x000000ff000000ff );
    return b;
}
uint64_t brFlipDiagX3_X4_6D( uint64_t b )
{
    b = deltaSwap( b, 8, 0x0000ff000000ff00 );
    return b;
}
uint64_t brFlipDiagX4_X2_6D( uint64_t b )
{
    b = deltaSwap( b,20, 0x00000f0f00000f0f );
    return b;
}
uint64_t brFlipDiagX2_X4_6D( uint64_t b )
{
    b = deltaSwap( b,12, 0x0000f0f00000f0f0 );
    return b;
}
uint64_t brFlipDiagX4_X1_6D( uint64_t b )
{
    b = deltaSwap( b,18, 0x0000333300003333 );
    return b;
}
uint64_t brFlipDiagX1_X4_6D( uint64_t b )
{
    b = deltaSwap( b,14, 0x0000cccc0000cccc );
    return b;
}
uint64_t brFlipDiagX4_X0_6D( uint64_t b )
{
    b = deltaSwap( b,17, 0x0000555500005555 );
    return b;
}
uint64_t brFlipDiagX0_X4_6D( uint64_t b )
{
    b = deltaSwap( b,15, 0x0000aaaa0000aaaa );
    return b;
}
uint64_t brFlipDiagX3_X2_6D( uint64_t b )
{
    b = deltaSwap( b,12, 0x000f000f000f000f );
    return b;
}
uint64_t brFlipDiagX2_X3_6D( uint64_t b )
{
    b = deltaSwap( b, 4, 0x00f000f000f000f0 );
    return b;
}
uint64_t brFlipDiagX3_X1_6D( uint64_t b )
{
    b = deltaSwap( b,10, 0x0033003300330033 );
    return b;
}
uint64_t brFlipDiagX1_X3_6D( uint64_t b )
{
    b = deltaSwap( b, 6, 0x00cc00cc00cc00cc );
    return b;
}
uint64_t brFlipDiagX3_X0_6D( uint64_t b )
{
    b = deltaSwap( b, 9, 0x0055005500550055 );
    return b;
}
uint64_t brFlipDiagX0_X3_6D( uint64_t b )
{
    b = deltaSwap( b, 7, 0x00aa00aa00aa00aa );
    return b;
}
uint64_t brFlipDiagX2_X1_6D( uint64_t b )
{
    b = deltaSwap( b, 6, 0x0303030303030303 );
    return b;
}
uint64_t brFlipDiagX1_X2_6D( uint64_t b )
{
    b = deltaSwap( b, 2, 0x0c0c0c0c0c0c0c0c );
    return b;
}
uint64_t brFlipDiagX2_X0_6D( uint64_t b )
{
    b = deltaSwap( b, 5, 0x0505050505050505 );
    return b;
}
uint64_t brFlipDiagX0_X2_6D( uint64_t b )
{
    b = deltaSwap( b, 3, 0x0a0a0a0a0a0a0a0a );
    return b;
}
uint64_t brFlipDiagX1_X0_6D( uint64_t b )
{
    b = deltaSwap( b, 3, 0x1111111111111111 );
    return b;
}
uint64_t brFlipDiagX0_X1_6D( uint64_t b )
{
    b = deltaSwap( b, 1, 0x2222222222222222 );
    return b;
}

luser droog · Accepted Answer · 2019-06-21 23:03:02Z

It can be done simply with 8 ANDs, 8 SHIFTs, and 6 ORs.

A naive counting of the delta-swap's operations is 1 AND, 2 SHIFTs and 3 XORs which if called 4 times yields 4 ANDs, 8 SHIFTs, and 12 XORs for the whole rotation. So the optimum may well depend upon the particular instructions' speeds on a particular hardware implementation. More ANDs and less (X)ORs or vice versa?

uint64_t
rotateXY_CW( uint64_t b ){
    uint64_t c =
            (b & 0x0033003300330033) << 2 |
            (b & 0x00cc00cc00cc00cc) << 8 |
            (b & 0xcc00cc00cc00cc00) >> 2 |
            (b & 0x3300330033003300) >> 8
            ;
    uint64_t d =
            (c & 0x0505050505050505) << 1 |
            (c & 0x0a0a0a0a0a0a0a0a) << 4 |
            (c & 0xa0a0a0a0a0a0a0a0) >> 1 |
            (c & 0x5050505050505050) >> 4
            ;
    return  d;
}

There is 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] (https://archive.org/details/byte-magazine-1981-08) on page 188.

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.

More details

So, assume for simplicity that we have a 4x4 bitmap to rotate, mapped into 16 bits.

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
  | (x & 0x00cc) << 8
  | (x & 0xcc00) >> 2
  | (x & 0x3300) >> 8;
x = (x & 0x0505) << 1
  | (x & 0x0a0a) << 4
  | (x & 0xa0a0) >> 1
  | (x & 0x5050) >> 4;

Notice that in the second step, operations parallelize over all sub-quadrants by selecting more pieces with the mask.

   0 1  2 3
                   >>         >    >
0  0 0  1 0     0 1  0 0     1 0V 1 0V   1 0  1 0
1  1 1  0 0     1 0  1 1    ^0<1 ^1<0    0 1  1 0
              ^^        VV    
2  0 1  0 0     0 0  1 0     0>0V 0>1V   0 0  0 1
3  1 0  0 0     0 0  0 0    ^0 0 ^0 0    0 0  0 0
                   <<         <    <

Masks for each quadrant:

1100          0011          0000          0000
1100          0011          0000          0000
0000          0000          0011          1100
0000 = 0033   0000 = 00cc   0011 = cc00   1100 = 3300

Shifting each mask yields the next mask

0033 << 2 == 00cc
00cc << 8 == cc00
cc00 >> 2 == 3300
3300 >> 8 == 0033

Masks for each sub-quadrant

1010          0101          0000          0000
0000          0000          0101          1010
1010          0101          0000          0000
0000 = 0505   0000 = 0a0a   0101 = a0a0   1010 = 5050

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
  | (x & 0x00cc00cc) << 8
  | (x & 0xcc00cc00) >> 2
  | (x & 0x33003300) >> 8;
x = (x & 0x05050505) << 1
  | (x & 0x0a0a0a0a) << 4
  | (x & 0xa0a0a0a0) >> 1
  | (x & 0x50505050) >> 4;

The number of operations doesn't increase! only the lengths of the masks increase.

And by replicating the mask from the 4x4 code 4 times it applies to a 4x4x4 cube.

Reversing the direction

Rotating in the other direction can be done by changing the directions of all the shifts.

uint64_t
rotateXY_CCW( uint64_t b ){
    uint64_t c =
            (b & 0x0033003300330033) << 8 |
            (b & 0x3300330033003300) << 2 |
            (b & 0xcc00cc00cc00cc00) >> 8 |
            (b & 0x00cc00cc00cc00cc) >> 2 |
            ;
    uint64_t d =
            (c & 0x0505050505050505) << 4 |
            (c & 0x5050505050505050) << 1 |
            (c & 0xa0a0a0a0a0a0a0a0) >> 4 |
            (c & 0x0a0a0a0a0a0a0a0a) >> 1
            ;
    return  d;
}

Rotating on a different axis

uint64_t
rotateXZ_CW( uint64_t b ){
    uint64_t c =
            (b & 0x0000000033333333) <<  2 |
            (b & 0x00000000cccccccc) << 32 |
            (b & 0xcccccccc00000000) >>  2 |
            (b & 0x3333333300000000) >> 32
            ;
    uint64_t d =
            (b & 0x0000555500005555) <<  1 |
            (b & 0x0000aaaa0000aaaa) << 16 |
            (b & 0xaaaa0000aaaa0000) >>  1 |
            (b & 0x5555000055550000) >> 16
            ;
    return  d;
}

uint64_t
rotateXZ_CCW( uint64_t b ){
    uint64_t c =
            (b & 0x0000000033333333) << 32 |
            (b & 0x3333333300000000) <<  2 |
            (b & 0xcccccccc00000000) >> 32 |
            (b & 0x00000000cccccccc) >>  2
            ;
    uint64_t d =
            (b & 0x0000555500005555) << 16 |
            (b & 0x5555000055550000) <<  1 |
            (b & 0xaaaa0000aaaa0000) >> 16 |
            (b & 0x0000aaaa0000aaaa) >>  1
            ;
    return  d;
}


quadrant masks
    1100 1100 0000 0000   
    1100 1100 0000 0000
    1100 1100 0000 0000
    1100 1100 0000 0000

    0011 0011 0000 0000
    ...

    0000 0000 0011 0011
    ...

    0000 0000 1100 1100
    ...

subquadrant masks
    1010 0000 1010 0000
    0101 0000 0101 0000
    0000 0101 0000 0101
    0000 1010 0000 1010

Rotating on the other, other axis

This one was harder for me to wrap my head around, but my ascii art of the masks seems to make sense.

uint64_t
rotateYZ_CW( uint64_t b ){
    uint64_t c =
            (b & 0x0000000000ff00ff) << 32 |
            (b & 0x00ff00ff00000000) <<  8 |
            (b & 0xff00ff0000000000) >> 32 |
            (b & 0x00000000ff00ff00) >>  8
            ;
    uint64_t d =
            (c & 0x00000f0f00000f0f) << 16 |
            (c & 0x0f0f00000f0f0000) <<  4 |
            (c & 0xf0f00000f0f00000) >> 16 |
            (c & 0x0000f0f00000f0f0) >>  4
            ;
    return  d;
}

uint64_t
rotateYZ_CCW( uint64_t b ){
    uint64_t c =
            (b & 0x0000000000ff00ff) <<  8 |
            (b & 0x00000000ff00ff00) << 32 |
            (b & 0xff00ff0000000000) >>  8 |
            (b & 0x00ff00ff00000000) >> 32
            ;
    uint64_t d =
            (c & 0x00000f0f00000f0f) <<  4 |
            (c & 0x0000f0f00000f0f0) << 16 |
            (c & 0xf0f00000f0f00000) >>  4 |
            (c & 0x0f0f00000f0f0000) >> 16
            ;
    return  d;
}

YZ quadrant masks
    1111 1111 0000 0000
    1111 1111 0000 0000
    0000 0000 0000 0000
    0000 0000 0000 0000

    0000 0000 1111 1111
    0000 0000 1111 1111
    0000 0000 0000 0000
    0000 0000 0000 0000

    0000 0000 0000 0000
    0000 0000 0000 0000
    0000 0000 1111 1111
    0000 0000 1111 1111

    0000 0000 0000 0000
    0000 0000 0000 0000
    1111 1111 0000 0000
    1111 1111 0000 0000

subquadrant masks
    1111 0000 1111 0000
    0000 0000 0000 0000
    1111 0000 1111 0000
    0000 0000 0000 0000

    0000 1111 0000 1111
    0000 0000 0000 0000
    0000 1111 0000 1111
    0000 0000 0000 0000

    0000 0000 0000 0000
    0000 1111 0000 1111
    0000 0000 0000 0000
    0000 1111 0000 1111

    0000 0000 0000 0000
    1111 0000 1111 0000
    0000 0000 0000 0000
    1111 0000 1111 0000

Stack Exchange Network

Rotating 3D bit board in C

5 Answers 5

More details

Reversing the direction

Rotating on a different axis

Rotating on the other, other axis

Your Answer

Not the answer you're looking for? Browse other questions tagged
c
bitwise
or ask your own question.

Linked

Hot Network Questions

Rotating 3D bit board in C

5 Answers 5

More details

Reversing the direction

Rotating on a different axis

Rotating on the other, other axis

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged cbitwise or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c
bitwise
or ask your own question.