Fill by Subtraction

Home * Board Representation * Bitboards * Sliding Piece Attacks * Fill by Subtraction

Performing the o^(o-2r) - trick in a SWAR-wise fashion with bytes (ranks), saves some instructions compared to Kogge-Stone.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

Unfortunately it only works in positive horizontal direction, so the possible savings are marginal, despite even less generalization of handling one out of eight cases with a different code pattern.

Source Code

U64 eastAttacks(U64 rooks, U64 empty) {
   const U64 H     =  0x8080808080808080;
   U64 occInclRook =  rooks | ~empty | H;
   U64 occExclRook = (rooks   &=      ~H)  ^ occInclRook;
   U64 rookAttacks = (occExclRook - rooks) ^ occInclRook;
   return rookAttacks;
}

Even more with vectors of two bitboards and SSE2-instructions.

Comparison with Kogge-Stone

For comparison the Kogge-Stone attack-getter. It gives an idea how to implement a Kogge-Stone Adder with bitwise operations only.

U64 eastAttacks(U64 rooks, U64 empty) {
   empty &= notAFile;
   rooks |= empty & (rooks << 1);
   empty &=         (empty << 1);
   rooks |= empty & (rooks << 2);
   empty &=         (empty << 2);
   rooks |= empty & (rooks << 4);
   return notAFile& (rooks << 1);
}

See also

• Add/Sub versus Attacks from Parallel Prefix Algorithms
• Fill Algorithms
• Fill by Subtraction with SSE2-instructions
• Kogge-Stone Algorithm
• Pieces versus Directions
• SIMD and SWAR Techniques
• Subtracting a Rook from a Blocking Piece

Up one Level