Difference between revisions of "Fill by Subtraction"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Fill by Subtraction''' Performing the Subtracting a Rook from a blocking Piec...")
 
m
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 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]].
+
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]].
 
[[include page="MappingHint"]]
 
[[include page="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.

Revision as of 15:42, 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. include page="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.

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

Up one Level