Difference between revisions of "Fill by Subtraction"
GerdIsenberg (talk | contribs) (Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Fill by Subtraction''' Performing the Subtracting a Rook from a blocking Piec...") |
GerdIsenberg (talk | contribs) m |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Fill by Subtraction''' | '''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Fill by Subtraction''' | ||
− | Performing the [[Subtracting a Rook from a | + | Performing the [[Subtracting a Rook from a Blocking Piece|o^(o-2r) - trick ]] in a [[SIMD and SWAR Techniques|SWAR-wise]] fashion with bytes (ranks), saves some instructions compared to [[Kogge-Stone Algorithm|Kogge-Stone]]. |
− | + | {{MappingHint}} | |
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. | 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. | ||
Line 39: | Line 39: | ||
* [[Pieces versus Directions]] | * [[Pieces versus Directions]] | ||
* [[SIMD and SWAR Techniques]] | * [[SIMD and SWAR Techniques]] | ||
− | * [[Subtracting a Rook from a | + | * [[Subtracting a Rook from a Blocking Piece]] |
'''[[Sliding Piece Attacks|Up one Level]]''' | '''[[Sliding Piece Attacks|Up one Level]]''' |
Latest revision as of 16:43, 18 May 2018
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); }