Slider attack mask generation without table lookup - Part 2

[vittyvirus]

Let's jump straight to the code:

Code: Select all

// ThisAndNextSq&#91;sq&#93; == 3ULL << sq
// PrevSquares&#91;sq&#93; == &#40;1ULL << sq&#41; - 1
inline bitboard_t rank_attacks&#40;square_t sq, bitboard_t occ&#41;
  &#123;
    static const bitboard_t OuterSquares&#91;Square&#58;&#58;SQ_NB&#93; = &#123;
      0x0000000000000081ULL, 0x0000000000000081ULL, 0x0000000000000081ULL,
      0x0000000000000081ULL, 0x0000000000000081ULL, 0x0000000000000081ULL,
      0x0000000000000081ULL, 0x0000000000000001ULL, 0x0000000000008000ULL,
      0x0000000000008100ULL, 0x0000000000008100ULL, 0x0000000000008100ULL,
      0x0000000000008100ULL, 0x0000000000008100ULL, 0x0000000000008100ULL,
      0x0000000000000100ULL, 0x0000000000800000ULL, 0x0000000000810000ULL,
      0x0000000000810000ULL, 0x0000000000810000ULL, 0x0000000000810000ULL,
      0x0000000000810000ULL, 0x0000000000810000ULL, 0x0000000000010000ULL,
      0x0000000080000000ULL, 0x0000000081000000ULL, 0x0000000081000000ULL,
      0x0000000081000000ULL, 0x0000000081000000ULL, 0x0000000081000000ULL,
      0x0000000081000000ULL, 0x0000000001000000ULL, 0x0000008000000000ULL,
      0x0000008100000000ULL, 0x0000008100000000ULL, 0x0000008100000000ULL,
      0x0000008100000000ULL, 0x0000008100000000ULL, 0x0000008100000000ULL,
      0x0000000100000000ULL, 0x0000800000000000ULL, 0x0000810000000000ULL,
      0x0000810000000000ULL, 0x0000810000000000ULL, 0x0000810000000000ULL,
      0x0000810000000000ULL, 0x0000810000000000ULL, 0x0000010000000000ULL,
      0x0080000000000000ULL, 0x0081000000000000ULL, 0x0081000000000000ULL,
      0x0081000000000000ULL, 0x0081000000000000ULL, 0x0081000000000000ULL,
      0x0081000000000000ULL, 0x0001000000000000ULL, 0x8000000000000000ULL,
      0x8100000000000000ULL, 0x8100000000000000ULL, 0x8100000000000000ULL,
      0x8100000000000000ULL, 0x8100000000000000ULL, 0x8100000000000000ULL,
      0x0100000000000000ULL,
    &#125;;
    occ = &#40;occ & RankMaskEx&#91;sq&#93;) | OuterSquares&#91;sq&#93;;
    return (&#40;occ - &#40;ThisAndNextSq&#91;msb&#40;occ & PrevSquares&#91;sq&#93;)&#93;)) ^ occ&#41;
      & RankMaskEx&#91;sq&#93;;
  &#125;
  inline bitboard_t file_attacks&#40;square_t sq, bitboard_t occ&#41;
  &#123;
    static const bitboard_t OuterSquares&#91;Square&#58;&#58;SQ_NB&#93; = &#123;
      0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL,
      0x0800000000000000ULL, 0x1000000000000000ULL, 0x2000000000000000ULL,
      0x4000000000000000ULL, 0x8000000000000000ULL, 0x0100000000000001ULL,
      0x0200000000000002ULL, 0x0400000000000004ULL, 0x0800000000000008ULL,
      0x1000000000000010ULL, 0x2000000000000020ULL, 0x4000000000000040ULL,
      0x8000000000000080ULL, 0x0100000000000001ULL, 0x0200000000000002ULL,
      0x0400000000000004ULL, 0x0800000000000008ULL, 0x1000000000000010ULL,
      0x2000000000000020ULL, 0x4000000000000040ULL, 0x8000000000000080ULL,
      0x0100000000000001ULL, 0x0200000000000002ULL, 0x0400000000000004ULL,
      0x0800000000000008ULL, 0x1000000000000010ULL, 0x2000000000000020ULL,
      0x4000000000000040ULL, 0x8000000000000080ULL, 0x0100000000000001ULL,
      0x0200000000000002ULL, 0x0400000000000004ULL, 0x0800000000000008ULL,
      0x1000000000000010ULL, 0x2000000000000020ULL, 0x4000000000000040ULL,
      0x8000000000000080ULL, 0x0100000000000001ULL, 0x0200000000000002ULL,
      0x0400000000000004ULL, 0x0800000000000008ULL, 0x1000000000000010ULL,
      0x2000000000000020ULL, 0x4000000000000040ULL, 0x8000000000000080ULL,
      0x0100000000000001ULL, 0x0200000000000002ULL, 0x0400000000000004ULL,
      0x0800000000000008ULL, 0x1000000000000010ULL, 0x2000000000000020ULL,
      0x4000000000000040ULL, 0x8000000000000080ULL, 0x0000000000000001ULL,
      0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
      0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL,
      0x0000000000000080ULL,
    &#125;;
    occ = &#40;occ & FileMaskEx&#91;sq&#93;) | OuterSquares&#91;sq&#93;;
    return (&#40;occ - ThisAndNextSq&#91;msb&#40;occ & PrevSquares&#91;sq&#93;)&#93;) ^ occ&#41; & FileMaskEx&#91;sq&#93;;
  &#125;

This code avoids two operations(compared to the previous one I proposed). This should be at least as fast as Hyperbola Quintessence, if not faster. I haven't tried, but it is possible to use the same idea for Diagonals. This gives a tough competition to magic bitboards on 64-bits. Also, I think coding SSE version of this code is also possible, which would work for all four directions in one go.

[Aleks Peshkov]

"Slider attack mask generation without table lookup" with 10 table lookups?

[vittyvirus]

"Slider attack mask generation without table lookup" with 10 table lookups?

Well, I'll have to agree that the name is not fully correct. I guess a correct name would be: "Slider attack mask generation by direct calculation".
By table lookup, I mean the attack masks are not pre-stored inside an array (which is the case with magic bitboards, kindergarten bitboards etc.)