Dumb7Fill - the obvious, straight forward flood-fill approach works set-wise - seven times one fill-cycle by one step only in one of eight directions. We rely on the compass rose to identify ray-directions.
noWe nort noEa
+7 +8 +9
\ | /
west -1 <- 0 -> +1 east
/ | \
-9 -8 -7
soWe sout soEa
An occluded fill includes the flood generating sliding pieces, but excludes the blocker. It is base of attack fills. One additional direction shift excludes the sliders but includes the blocker.
Seven Fill Cycles
The sliding pieces generate the flood. They were shifted one step in the desired direction and intersected with the set of empty squares, the propagator. The flood aggregates the intersection and the cycle repeats six further times to cover the maximum distance on the chessboard. A blocker, not member of propagator, stops the flood in that particular ray-direction for one sliding piece. Therefor occluded fill contains the initial generator but excludes any blocker.
U64 soutOccl(U64 gen, U64 pro){for(int cycle =0; cycle <7; cycle++)
gen |= pro &(gen >>8);return gen;}
Fill Loop
Alternatively one may save move-instructions by introducing an explicit flood accumulator, and to probably terminate the loop early if the flood stops:
To combine the dumb7fill as attack getter, we also can take advantage of outer square occupancy doesn't affect the attack set. We need one fill cycle less, before the final shift. That takes 19 operations. In anticipation to parallel prefix, a Kogge-Stone approach takes 14 instructions, 5 less. Kogge-Stone needs more move-instructions and a temporary register to compute generator as well as propagator, while dumb7fill uses a const propagator:
Horizontal fills need to consider wraps from H-file to A-file and vice versa. Fortunately this can be combined by intersection of ~A-file or ~H-file with the propagator:
Since rotate works like a generalized shift with positive or negative shift amount - since it internally applies a modulo 64 and makes -i = 64-i. We need to clear either the lower or upper bits by intersection with a mask, which might be combined with the wrap-ands for one step. It might be applied to get attacks for both sides with a direction parameter and small lookups for shift amount and wrap-ands - instead of multiple code for eight directions. Of course generalized shift will be a bit slower due to lookups and using cl as the shift amount register.
Loop Version
This is the loop-version:
U64 occludedFill (U64 gen, U64 pro, int dir8){
U64 flood =0;if(gen){int r = shift[dir8];// {+-1,7,8,9}
pro &= avoidWrap[dir8];do{
flood |= gen;
gen = rotateLeft(gen, r)& pro;}while(gen);}return flood;}
U64 shiftOne (U64 b, int dir8){int r = shift[dir8];// {+-1,7,8,9}return rotateLeft(b, r)& avoidWrap[dir8];}
U64 slidingAttacks (U64 sliders, U64 empty, int dir8){
U64 fill = occludedFill(slider, empty, dir8)return shiftOne(fill, dir8);}// positve left, negative right shiftsint shift[8]={9, 1,-7,-8,-9,-1, 7, 8};
U64 avoidWrap[8]={0xfefefefefefefe00,
0xfefefefefefefefe,
0x00fefefefefefefe,
0x00ffffffffffffff,
0x007f7f7f7f7f7f7f,
0x7f7f7f7f7f7f7f7f,
0x7f7f7f7f7f7f7f00,
0xffffffffffffff00,
};
The avoidWrap masks by some arbitrary dir8 enumeration and shift amount:
Table of Contents
Dumb7Fill - the obvious, straight forward flood-fill approach works set-wise - seven times one fill-cycle by one step only in one of eight directions. We rely on the compass rose to identify ray-directions.
noWe nort noEa +7 +8 +9 \ | / west -1 <- 0 -> +1 east / | \ -9 -8 -7 soWe sout soEaOccluded Fill
An occluded fill includes the flood generating sliding pieces, but excludes the blocker. It is base of attack fills. One additional direction shift excludes the sliders but includes the blocker.Seven Fill Cycles
The sliding pieces generate the flood. They were shifted one step in the desired direction and intersected with the set of empty squares, the propagator. The flood aggregates the intersection and the cycle repeats six further times to cover the maximum distance on the chessboard. A blocker, not member of propagator, stops the flood in that particular ray-direction for one sliding piece. Therefor occluded fill contains the initial generator but excludes any blocker.Fill Loop
Alternatively one may save move-instructions by introducing an explicit flood accumulator, and to probably terminate the loop early if the flood stops:Unrolled Loop
To avoid conditional branches and to schedule several directions in parallel, the "real" dumb7fill unrolls the loop:Some south fill cycles in slow motion:
The flood already stopped, the final 7th fill cycles don't change anything.
Attack Fill
To get attacks, one additional direction shift of the occluded fill is necessary to exclude the rooks/queen and include the blocker:Comparison with Kogge-Stone
To combine the dumb7fill as attack getter, we also can take advantage of outer square occupancy doesn't affect the attack set. We need one fill cycle less, before the final shift. That takes 19 operations. In anticipation to parallel prefix, a Kogge-Stone approach takes 14 instructions, 5 less. Kogge-Stone needs more move-instructions and a temporary register to compute generator as well as propagator, while dumb7fill uses a const propagator:Thus, dumb7fill is not that bad, specially if processing several directions in parallel, like south and north, all east and all west attacks.
All Directions
Horizontal fills need to consider wraps from H-file to A-file and vice versa. Fortunately this can be combined by intersection of ~A-file or ~H-file with the propagator:Generalized Rays
Since rotate works like a generalized shift with positive or negative shift amount - since it internally applies a modulo 64 and makes -i = 64-i. We need to clear either the lower or upper bits by intersection with a mask, which might be combined with the wrap-ands for one step. It might be applied to get attacks for both sides with a direction parameter and small lookups for shift amount and wrap-ands - instead of multiple code for eight directions. Of course generalized shift will be a bit slower due to lookups and using cl as the shift amount register.
Loop Version
This is the loop-version:The avoidWrap masks by some arbitrary dir8 enumeration and shift amount:
Unrolled Attacks
The generalized unrolled sliding attack getter:See also
External Links
Joe Zawinul, Wayne Shorter, Miroslav Vitouš, Alphonse Mouzon, Dom Um Romão
What links here?
Up one Level