Magic Knight- and King-Move Generation

[Gerd Isenberg]

The idea is to mul/shift/lookup a move(capture)-target bitboards, to do a almost branchless move-generation with precalculated moves inside movelists:

Code: Select all

moveTarget = KingAttacks[sq] & ~(ownPieces | attackedSquares);
idx = (moveTarget * kingMagic[sq]) >> kingShift[sq]);
movelists = kingMoveLists[sq];
movelist  = movelists[idx];
moveCpy(target, movelist, movelist->n);


A king in a corner may have up to three moves.
Thus there are 2**3 == 8 possible movelists, eg. for a king on a1 (number of moves: vector of moves):

Code: Select all

0:{empty}
1:{a1-b1}
1:{a1-a2}
1:{a1-b2}
2:{a1-b1,a1-a2}
2:{a1-b1,a1-b2}
2:{a1-a2,a1-b2}
3:{a1-b1,a1-a2,a1-b2}


Kings on edges have 5 potential target squares, thus there are 32 possible movelists. All other kings have 8 all the 8 neightboars with up to 256 movelists. Similar movelist enumeration is possible with knights and ...

I was rather surprised that all possible move-target subsets of kings and knights for all 64 from-squares are perfectly hashable with a magic factor of only four one-bits set - 10016 possible king-movelists and 5520 knight-movelists:

Code: Select all

find Magics with 4 one bits for King-Moves, bits 3
magic/shift[ 0]   8 movelists: 0x1040000000000003 61
magic/shift[ 7]   8 movelists: 0x0081000000000003 61
magic/shift[56]   8 movelists: 0x0000000000002043 61
magic/shift[63]   8 movelists: 0x000000000000008e 61
4 magics found so far with 32 entries

find Magics with 4 one bits for King-Moves, bits 5
magic/shift[ 1]  32 movelists: 0x0c20000000000001 59
magic/shift[ 2]  32 movelists: 0x0610000000000001 59
magic/shift[ 3]  32 movelists: 0x0308000000000001 59
magic/shift[ 4]  32 movelists: 0x0184000000000001 59
magic/shift[ 5]  32 movelists: 0x00c2000000000001 59
magic/shift[ 6]  32 movelists: 0x0061000000000001 59
magic/shift[ 8]  32 movelists: 0x0810400000000001 59
magic/shift[15]  32 movelists: 0x0020810000000001 59
magic/shift[16]  32 movelists: 0x0008104000000001 59
magic/shift[23]  32 movelists: 0x0000208100000001 59
magic/shift[24]  32 movelists: 0x0000081040000001 59
magic/shift[31]  32 movelists: 0x0000002081000001 59
magic/shift[32]  32 movelists: 0x0000000810400001 59
magic/shift[39]  32 movelists: 0x0000000020810001 59
magic/shift[40]  32 movelists: 0x0000000008104001 59
magic/shift[47]  32 movelists: 0x0000000000208101 59
magic/shift[48]  32 movelists: 0x0000000000081041 59
magic/shift[55]  32 movelists: 0x0000000000002083 59
magic/shift[57]  32 movelists: 0x0000000000002013 59
magic/shift[58]  32 movelists: 0x000000000000100b 59
magic/shift[59]  32 movelists: 0x0000000000000807 59
magic/shift[60]  32 movelists: 0x000000000000088c 59
magic/shift[61]  32 movelists: 0x0000000000000446 59
magic/shift[62]  32 movelists: 0x0000000000000223 59
28 magics found so far with 800 entries

find Magics with 4 one bits for King-Moves, bits 8
magic/shift[ 9] 256 movelists: 0x0402600000000000 56
magic/shift[10] 256 movelists: 0x0201300000000000 56
magic/shift[11] 256 movelists: 0x0100980000000000 56
magic/shift[12] 256 movelists: 0x00804c0000000000 56
magic/shift[13] 256 movelists: 0x0040260000000000 56
magic/shift[14] 256 movelists: 0x0020130000000000 56
magic/shift[17] 256 movelists: 0x0004026000000000 56
magic/shift[18] 256 movelists: 0x0002013000000000 56
magic/shift[19] 256 movelists: 0x0001009800000000 56
magic/shift[20] 256 movelists: 0x0000804c00000000 56
magic/shift[21] 256 movelists: 0x0000402600000000 56
magic/shift[22] 256 movelists: 0x0000201300000000 56
magic/shift[25] 256 movelists: 0x0000040260000000 56
magic/shift[26] 256 movelists: 0x0000020130000000 56
magic/shift[27] 256 movelists: 0x0000010098000000 56
magic/shift[28] 256 movelists: 0x000000804c000000 56
magic/shift[29] 256 movelists: 0x0000004026000000 56
magic/shift[30] 256 movelists: 0x0000002013000000 56
magic/shift[33] 256 movelists: 0x0000000402600000 56
magic/shift[34] 256 movelists: 0x0000000201300000 56
magic/shift[35] 256 movelists: 0x0000000100980000 56
magic/shift[36] 256 movelists: 0x00000000804c0000 56
magic/shift[37] 256 movelists: 0x0000000040260000 56
magic/shift[38] 256 movelists: 0x0000000020130000 56
magic/shift[41] 256 movelists: 0x0000000004026000 56
magic/shift[42] 256 movelists: 0x0000000002013000 56
magic/shift[43] 256 movelists: 0x0000000001009800 56
magic/shift[44] 256 movelists: 0x0000000000804c00 56
magic/shift[45] 256 movelists: 0x0000000000402600 56
magic/shift[46] 256 movelists: 0x0000000000201300 56
magic/shift[49] 256 movelists: 0x0000000000040260 56
magic/shift[50] 256 movelists: 0x0000000000020130 56
magic/shift[51] 256 movelists: 0x0000000000010098 56
magic/shift[52] 256 movelists: 0x000000000000804c 56
magic/shift[53] 256 movelists: 0x0000000000004026 56
magic/shift[54] 256 movelists: 0x0000000000002013 56
64 magics found so far with 10016 entries


find Magics with 4 one bits for Knight-Moves, bits 2
magic/shift[ 0]   4 movelists: 0x0010400000000003 62
magic/shift[ 7]   4 movelists: 0x0002020000000003 62
magic/shift[56]   4 movelists: 0x0000000000202003 62
magic/shift[63]   4 movelists: 0x0000000000010403 62
4 magics found so far with 16 entries

find Magics with 4 one bits for Knight-Moves, bits 3
magic/shift[ 1]   8 movelists: 0x0004900000000001 61
magic/shift[ 6]   8 movelists: 0x0002048000000001 61
magic/shift[ 8]   8 movelists: 0x0800104000000001 61
magic/shift[15]   8 movelists: 0x0100020200000001 61
magic/shift[48]   8 movelists: 0x0000000010100021 61
magic/shift[55]   8 movelists: 0x000000000082000c 61
magic/shift[57]   8 movelists: 0x0000000000200803 61
magic/shift[62]   8 movelists: 0x0000000000010403 61
12 magics found so far with 80 entries

find Magics with 4 one bits for Knight-Moves, bits 4
magic/shift[ 2]  16 movelists: 0x0014100000000001 60
magic/shift[ 3]  16 movelists: 0x000a080000000001 60
magic/shift[ 4]  16 movelists: 0x0005040000000001 60
magic/shift[ 5]  16 movelists: 0x0002820000000001 60
magic/shift[ 9]  16 movelists: 0x0200082000000001 60
magic/shift[14]  16 movelists: 0x0100040100000001 60
magic/shift[16]  16 movelists: 0x0808001040000000 60
magic/shift[23]  16 movelists: 0x0041000202000000 60
magic/shift[24]  16 movelists: 0x0008080010400000 60
magic/shift[31]  16 movelists: 0x0000410002020000 60
magic/shift[32]  16 movelists: 0x0000080800104000 60
magic/shift[39]  16 movelists: 0x0000004100020200 60
magic/shift[40]  16 movelists: 0x0000000808001040 60
magic/shift[47]  16 movelists: 0x0000000041000202 60
magic/shift[49]  16 movelists: 0x0000000010040011 60
magic/shift[54]  16 movelists: 0x0000000000820018 60
magic/shift[58]  16 movelists: 0x0000000000082801 60
magic/shift[59]  16 movelists: 0x0000000000041401 60
magic/shift[60]  16 movelists: 0x0000000000020a01 60
magic/shift[61]  16 movelists: 0x0000000000010501 60
32 magics found so far with 400 entries

find Magics with 4 one bits for Knight-Moves, bits 6
magic/shift[10]  64 movelists: 0x0400091000000000 58
magic/shift[11]  64 movelists: 0x0200048800000000 58
magic/shift[12]  64 movelists: 0x0100024400000000 58
magic/shift[13]  64 movelists: 0x0080012200000000 58
magic/shift[17]  64 movelists: 0x0401000820000000 58
magic/shift[22]  64 movelists: 0x0020800401000000 58
magic/shift[25]  64 movelists: 0x0004010008200000 58
magic/shift[30]  64 movelists: 0x0000208004010000 58
magic/shift[33]  64 movelists: 0x0000040100082000 58
magic/shift[38]  64 movelists: 0x0000002080040100 58
magic/shift[41]  64 movelists: 0x0000000401000820 58
magic/shift[46]  64 movelists: 0x0000000020800401 58
magic/shift[50]  64 movelists: 0x0000000002080042 58
magic/shift[51]  64 movelists: 0x0000000001040021 58
magic/shift[52]  64 movelists: 0x0000000002018002 58
magic/shift[53]  64 movelists: 0x000000000100c001 58
48 magics found so far with 1424 entries

find Magics with 4 one bits for Knight-Moves, bits 8
magic/shift[18] 256 movelists: 0x0082000808000000 56
magic/shift[19] 256 movelists: 0x0041000404000000 56
magic/shift[20] 256 movelists: 0x0020800202000000 56
magic/shift[21] 256 movelists: 0x0010400101000000 56
magic/shift[26] 256 movelists: 0x0000820008080000 56
magic/shift[27] 256 movelists: 0x0000410004040000 56
magic/shift[28] 256 movelists: 0x0000208002020000 56
magic/shift[29] 256 movelists: 0x0000104001010000 56
magic/shift[34] 256 movelists: 0x0000008200080800 56
magic/shift[35] 256 movelists: 0x0000004100040400 56
magic/shift[36] 256 movelists: 0x0000002080020200 56
magic/shift[37] 256 movelists: 0x0000001040010100 56
magic/shift[42] 256 movelists: 0x0000000082000808 56
magic/shift[43] 256 movelists: 0x0000000041000404 56
magic/shift[44] 256 movelists: 0x0000000020800202 56
magic/shift[45] 256 movelists: 0x0000000010400101 56
64 magics found so far with 5520 entries


The small test framework if you may try to search magics by yourself:

Code: Select all

#include <stdio.h>
typedef __int64 i64;
typedef unsigned __int64 u64;
typedef unsigned int u32;


#define MAXBITS 16
#define LOCKSIZE (1<<(MAXBITS-5))

u32 gLockArray[LOCKSIZE];


__forceinline
void clearLock()
{
   for (int i = 0; i < LOCKSIZE; i++)
      gLockArray[i] = 0;
}

__forceinline
bool testAndSet(u32 idx)
{
   u32 bit = 1 << (idx & 31);
   idx >>= 5; // 32 bits per u32
   bool res = (gLockArray[idx] & bit) != 0;
   gLockArray[idx] |= bit;
   return res;
}

int tryMagic4knightMoves(u64 magic, u32 shift, u32 square)
{
   u64 a0, a1, b, a = 1;
   u32 idx, count = 0;

   clearLock();
   a <<= square;
   a0 = (a  << 1) & 0xFEFEFEFEFEFEFEFE;
   a1 = (a  >> 1) & 0x7F7F7F7F7F7F7F7F;
   a  = (a0|a1) >> 16;
   a |= (a0|a1) << 16;
   a0 = (a0 << 1) & 0xFEFEFEFEFEFEFEFE;
   a1 = (a1 >> 1) & 0x7F7F7F7F7F7F7F7F;
   a |= (a0|a1) >> 8;
   a |= (a0|a1) << 8;
   b  = 0; // first subset
   do { // traverse all subsets
      idx = (u32)((b*magic)>>shift);
      if ( testAndSet(idx))
         return 0; // collision
      count++;
      b = (b - a) & a;
   } while (b);
   return count;
}

int tryMagic4kingMoves(u64 magic, u32 shift, u32 square)
{
   u64 a0, a1, b, a = 1;
   u32 idx, count = 0;

   clearLock();
   a <<= square;
   a0 = (a << 1) & 0xFEFEFEFEFEFEFEFE;
   a1 = (a >> 1) & 0x7F7F7F7F7F7F7F7F;
   a0|= a1;
   a0|= (a0 >> 8) | (a0 << 8);
   a  = (a  >> 8) | (a  << 8) | a0;
   b  = 0; // first subset
   do { // traverse all subsets
      idx = (u32)((b*magic)>>shift);
      if ( testAndSet(idx))
         return 0; // collision
      count++;
      b = (b - a) & a;
   } while (b);
   return count;
}

// search next higher word with same number of one bits
u64 snoob (u64 x) {
   static const unsigned int deBruijnLookup[64] =
   {
      0,  1, 48,  2, 57, 49, 28,  3,
     61, 58, 50, 42, 38, 29, 17,  4,
     62, 55, 59, 36, 53, 51, 43, 22,
     45, 39, 33, 30, 24, 18, 12,  5,
     63, 47, 56, 27, 60, 41, 37, 16,
     54, 35, 52, 21, 44, 32, 23, 11,
     46, 26, 40, 15, 34, 20, 31, 10,
     25, 14, 19,  9, 13,  8,  7,  6,
   };
   static const u64 deBruijn = 0x03f79d71b4cb0a89;
   u64 smallest, ripple, ones;

   smallest = x & -(i64)x;
   ripple   = x + smallest;
   ones     = x ^ ripple;
   ones     = (ones >> 2) >> deBruijnLookup[(smallest*deBruijn) >> 58];
   return ripple | ones;
}

int findMagic(u32 sq, int nOneBits4Magic, int bits, int (*pTryFunc)(u64, u32, u32))
{
   u64 x, y, first = 1;
   u32 count;

   first = (first << nOneBits4Magic)-1;
   for (x = first; (y = snoob(x)) > x; x = y) {
      count = pTryFunc(y, 64-bits, sq);
      if ( count > 0 ) {
         printf("magic/shift[%2d] %3d movelists: 0x%08x%08x %2d\n",
                 sq, count, (u32)(y>>32), (u32)y, 64-bits);
         return 1; // found
      }
   }
   return 0;
}


void findMagics(int n1Bits4Magic, int width, int (*pTryFunc)(u64, u32, u32), const char* str)
{
   u64 sqbb, set = 0;
   u32 sq, bits;
   int count = 0, total = 0;

   for (bits = width; bits <= MAXBITS; bits++) {
      printf("find Magics with %d one bits for %s, bits %d\n", n1Bits4Magic, str, bits);
      for (sq=0, sqbb=1; sq < 64; sq++, sqbb+=sqbb) {
         if ( (set & sqbb) == 0 && findMagic(sq, n1Bits4Magic, bits, pTryFunc) ) {
            set |= sqbb;
            count++;
            total += (1<<bits);
         }
         printf("%d magics found so far with %d entries\n", count, total);
         if ( count == 64 )
        return;
      }
   }
}

int main(int argc, char* argv[])
{
   findMagics(4, 2, tryMagic4knightMoves, "Knight-Moves");
   findMagics(4, 3, tryMagic4kingMoves, "King-Moves");
   return 0;
}


Cheers,
Gerd

[Grant Osborne]

Great post Gerd.
Congratulations.

In my engine, 32-bit magics proved to be faster for bishops/rooks. So maybe it will also be faster for king/knights

Code: Select all

U64 moveTarget = KingAttacks[sq] & ~(ownPieces | attackedSquares);
unsigned int lo = ((int)(moveTarget) * (int)(kingMagic[sq]));
unsigned int hi = ((int)(moveTarget >> 32) * (int)(kingMagic[sq] >> 32));
idx = (lo ^ hi) >> kingShift[sq];
movelist  = movelists[idx];
moveCpy(target, movelist, movelist->n);

Magic pawns anyone?

Grant

[H.G.Muller]

Interesting idea. In principle, you could map the attacks set (well, actually just legal-move set in this case) onto the same bits of the bitboard by a simple shift. (You are not buggered by different patterns of the occupied bits, like files vs ranks for the Rooks.) A shift would not make the bits contiguous, though, and you might need a shift in either direction to get it in a standard place. You could remedy that by not shifting the bits in place, but using a rotate instruction. (Alas not accessible from C; too bad that they did not supply a '<>' operator for this. Now you would have to do it through cumbersome notations like A<<N|A>>64-N, of which it is doubtful that the compiler will recognize them as a rotate.)

Rotating the moveTarget by a square-dependent amount such that a King would map to B2 and a Knight to C3 (assuming that A1 is LSB) you could use a fixed multiplier and shift to pack them into a universal 8-bit index, that you could use to access a single 256-entry table of move vectors, to which you would only have to add the from-square to get the to-square.

You might even rotate the moveTarget to the MSBs (K to G7, N to F6), do the multiply with the universal magic, and use the high-order word of the product, without the need for any shifting after the multiply:

Code: Select all

moveTarget = moveTarget<<KingRot[sq] | moveTarget>>64-KingRot[sq]; // one instruction!
idx = moveTarget*KingMagic >> 64;  // no shift, just take high word!
steplist = KingStepList[idx];
addCpy(target, steplist, steplist->n, sq);


Actually, there is nothing against rotating the King to the same position as the Knight (F6), so that they use the same Rotate table, just a different Magic and StepList. This automatically avoids the sign bit, so that you don't have to worry about the magic muliply to be signed or unsigned.

As for the 32-bit issue: simply fold the board by ORing or ADDing low and high 32-bits. This will never cause collisions (for the King due to limited range, for the Knight due to color-boundness). Then do the whole thing as above with 32-bit integers.

[Gerd Isenberg]

Interesting idea. In principle, you could map the attacks set (well, actually just legal-move set in this case) onto the same bits of the bitboard by a simple shift. (You are not buggered by different patterns of the occupied bits, like files vs ranks for the Rooks.) A shift would not make the bits contiguous, though, and you might need a shift in either direction to get it in a standard place. You could remedy that by not shifting the bits in place, but using a rotate instruction. (Alas not accessible from C; too bad that they did not supply a '<>' operator for this. Now you would have to do it through cumbersome notations like A<<N|A>>64-N, of which it is doubtful that the compiler will recognize them as a rotate.)

Rotating the moveTarget by a square-dependent amount such that a King would map to B2 and a Knight to C3 (assuming that A1 is LSB) you could use a fixed multiplier and shift to pack them into a universal 8-bit index, that you could use to access a single 256-entry table of move vectors, to which you would only have to add the from-square to get the to-square.

You might even rotate the moveTarget to the MSBs (K to G7, N to F6), do the multiply with the universal magic, and use the high-order word of the product, without the need for any shifting after the multiply:

Code: Select all

moveTarget = moveTarget<<KingRot[sq] | moveTarget>>64-KingRot[sq]; // one instruction!
idx = moveTarget*KingMagic >> 64;  // no shift, just take high word!
steplist = KingStepList[idx];
addCpy(target, steplist, steplist->n, sq);


Actually, there is nothing against rotating the King to the same position as the Knight (F6), so that they use the same Rotate table, just a different Magic and StepList. This automatically avoids the sign bit, so that you don't have to worry about the magic muliply to be signed or unsigned.

As for the 32-bit issue: simply fold the board by ORing or ADDing low and high 32-bits. This will never cause collisions (for the King due to limited range, for the Knight due to color-boundness). Then do the whole thing as above with 32-bit integers.

Yes, good point to go with only 256-lists for one "normalized" square and to do some vector-arithmetic e.g. with sse2. Aren't the _rotr64, _rotl64 x86/64-intrinsics available for recent 64-bit compiler? At least vc2005 has them, but i think intel c and gcc as well.

I'm not sure whether this whole magic stuff for movelist pays off - since bitscan is so fast (again) in Core 2...

[H.G.Muller]

I was not aware of those intrinsics, so thanks!

It should be slightly faster than the normal way, I think, because you would still have to do the DeBruin magic & hashing there, on a per move basis, no matter how fast bsf is.

And, like you say, adding the vectors is quite cheap, you could make a 64-table that just packs the indexing square many times in a long data-type, and add it to the vector sets you retrieve from the table, to get all to-squares (or even complete 16-bit moves) at once.

[Gerd Isenberg]

[edit] Not so obvious as i first thought, since "e" (square 35 with knight on 45 or f6) and "d" (55 or h7) share the same target square 63 or h8 after shifting left by 28 resp. 8. Nevertheless there are 256 unique indices. Final bit 63 becomes ~"d" if "e" is set. "e" is mapped to square 57 anyway.[/edit]

After some thinking, it is quite obvious why four-bit factors are neccessary to map all knight and king target squares to the most significant byte - lets take the knight on f6 (square 45), with eight attack squares called a-h:

Code: Select all

magic/shift[45] 256 movelists: 0x0000000010400101 56

 . . . . a . b .                 g e h c a f b d 
 . . . c . . . d                 x x x x x x x x
 . . . . . n . .                 x x x x x x x x
 . . . e . . . f  * 0x10400101 = . . . e x x x f   
 . . . . g . h .                 . . . . g . h .
 . . . . . . . .                 . . . . . . . .
 . . . . . . . .                 . . . . . . . .
 . . . . . . . .                 . . . . . . . .


So a-b is already fine, c-d are shifted one up, e-f three up and two right (board left with my mapping) and g-four up and four right. Adding or oring all together leaves the 8-bit index, which we can shift right by 64-8.

We may use four shifts (or rotates) and three and/or instead of the multiplication, eg c3:

Code: Select all

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . a . b . . . .
 c . . . d . . .
 . . n . . . . .
 e . . . f . . .
 . g . h . . . .

_rotr64(0,8,22,28) & 255 :=> e g c h f a d b


It might be possible to combine the four rotates already with the square normalization rotate, but i guess rot,mul,shift will be faster on K8 or P6.

Code: Select all

setX = _rotl64(setX, sq-18);
idx  = (char)  setX;
idx += (char) _rotr64(setX, 8);
idx += (char) _rotr64(setX,22);
idx += (char) _rotr64(setX,28);


Code: Select all

// f6 normalization, because of the low 32-bit factor
idx  = (_rotr64(setX,sq-45) * 0x10400101) >> 56;


The nice thing is rotate is generalized, the processor masks the upper two bits of cl to zero, so that -1 becomes 63 again.

Code: Select all

_rotl64(setX, a) == _rotr64(setX, -a)


[Gerd Isenberg]

In my engine, 32-bit magics proved to be faster for bishops/rooks. So maybe it will also be faster for king/knights

Yes, the stuff with king or knight moves looks rather 32-bit friendly.

Magic pawns anyone?

Hashing pawn move-sets of targets of multiple pawns looks hard. I tried 3^8 = 6561 possible pawn pushes on two ranks - but it only maps with 16-bit indices to a 64K-range. Hashing pawn-pushes, double-pushes and left-right captures per rank with up to 256 combinations each looks rather expensive, looking for up to six ranks - compared to bitscan loops or even simple board traversal.

Gerd

[Gerd Isenberg]

As for the 32-bit issue: simply fold the board by ORing or ADDing low and high 32-bits. This will never cause collisions (for the King due to limited range, for the Knight due to color-boundness). Then do the whole thing as above with 32-bit integers.

That does not work for knights, both halfs of the board have same color mapping, a1 and a4 are both black squares. Thus one additional 32-bit bswap or rot8 seems necessary.

[H.G.Muller]

Oops, you are right... For some reason I was indeed imagining true folding of a board, where the white and black squares interleave.

Then it doesn't work at all, for Knights on different squares distribute their target squares differently over the two half boards, so the folded pattern wouldn't be universal. I guess even for King you would need square-dependent magics, because in cases where the moves stradle the boundary, they make an essentially different pattern.

Well, stick to 64-bit then.

[Gerd Isenberg]

Oops, you are right... For some reason I was indeed imagining true folding of a board, where the white and black squares interleave.

Then it doesn't work at all, for Knights on different squares distribute their target squares differently over the two half boards, so the folded pattern wouldn't be universal. I guess even for King you would need square-dependent magics, because in cases where the moves stradle the boundary, they make an essentially different pattern.

Well, stick to 64-bit then.

Yes, seems the rotate to f6(c3)has to be 64-bitwise.
But then you can perform two independent 32-bit operations before oring them together and shift right 24. Since magic has only three bits set there is even an exact 1:1 square mapping - e and d don't share bit 63 anymore since there is no shl 28:

Code: Select all

 . . . . a . b .                 . e . c a f b d
 . . . c . . . d                 x x x x x x x x
 . . . . . n . .                 x x x x x x x x
 . . . e . . . f  * 0x00400101 = . . . e x x x f   
 
 . . . . g . h .                 g . h . . . . .
 . . . . . . . .                 . . . . . . . .
 . . . . . . . .  >> 4           . . . . . . . .
 . . . . . . . .                 . . . . . . . .


_rotl64, _rotr64 are available in 32 bit mode as well, double shift, shift.