Author: Gerd Isenberg
Date: 07:39:03 09/15/02
Hi all,
Stimulated by all the nice flood fill routines posted by Stefan Westcott,
http://www.talkchess.com/forums/1/message.html?252020
http://www.talkchess.com/forums/1/message.html?252066
i am currently thinking about using flood fill to generate attacks for sliding
pieces, simply by doing seven floods unconditionally in each direction, without
possible expensive memory access.
The mmx code for rooks is 320 Bytes long, which is about as twice as the
table-lookup code (OK with hammer it's a bit more). But no need for lookup
tables and no need for rotated bitboards anymore!
At least two direction floods may processed simultaniously due to the two
mmx-integer pipes, and no need to save any (32-bit) register in calling
function!
The routine may generate attacks for multiple rooks (or straight attacks from
queens) simultaniously, therefore the BitBoard rooks parameter!
I think the "Kogge-Stone parallel prefix algorithm" is not possible here. May be
it can be combined with the x ^= (x-2) trick for ranks.
Worth to try?
Cheers,
Gerd
similar c-code:
BitBoard getRookAttacks(BitBoard freeSquares, BitBoard rooks)
{
BitBoard attck = 0;
// 1. straight fill
BitBoard left = ShiftLeft(rooks);
BitBoard right = ShiftRight(rooks);
BitBoard up = ShiftUp(rooks);
BitBoard down = ShiftDown(rooks);
attck |= left|right|up|down;
// 2. straight fill
left = ShiftLeft(left&freeSquares);
right = ShiftRight(left&freeSquares);
up = ShiftUp(up&freeSquares);
down = ShiftDown(down&freeSquares);
attck |= left|right|up|down;
// 3..6. straight fill
// repeat 2.fill code 4 times
// ...............
// 7. straight fill
return attck
| ShiftLeft(left&freeSquares)
| ShiftRight(left&freeSquares)
| ShiftUp(up&freeSquares)
| ShiftDown(down&freeSquares);
}
prefered mmx code:
BitBoard getRookAttacksMMX(BitBoard freeSquares, BitBoard rooks)
{
static const BitBoard eight = 8;
static const BitBoard notH = 0x7f7f7f7f7f7f7f7f;
__asm
{
movd mm6, [freeSquares]
punpckldq mm6, [freeSquares+4]
movd mm1, [rooks]
punpckldq mm1, [rooks+4]
pxor mm0, mm0 ; rookAttacks := 0
movq mm5, [eight]; saves some bytes in unrolled loop
movq mm7, [notH] ; saves some bytes in unrolled loop
movq mm2, mm1 ; left
movq mm3, mm1 ; up
movq mm4, mm1 ; down
// 1. straight fill in each direction
paddb mm1, mm1 ; right
psrlq mm2, 1 ; left
psllq mm3, mm5 ; up
por mm0, mm1 ; rookAttacks |= right
pand mm2, mm7 ; clear left h-file wraps
pand mm1, mm6 ; clear right occupied
por mm0, mm3 ; rookAttacks |= up
psrlq mm4, mm5 ; down
por mm0, mm2 ; rookAttacks |= left
pand mm3, mm6 ; clear up occupied
por mm0, mm4 ; rookAttacks |= down
pand mm2, mm6 ; clear left occupied
pand mm4, mm6 ; clear down occupied
// 2-6. straight fill in each direction
// repeat above fill code 5 times
// .........
// 7. straight fill in each direction
paddb mm1, mm1 ; right
psrlq mm2, 1 ; left
psllq mm3, mm5 ; up
por mm0, mm1 ; rookAttacks |= right
pand mm2, mm7 ; clear left h-file wraps
por mm0, mm3 ; rookAttacks |= up
psrlq mm4, mm5 ; down
por mm0, mm2 ; rookAttacks |= left
por mm0, mm4 ; rookAttacks |= down
pswapd mm1, mm0 ; highboard athlon only
movd eax, mm0 ; return low board in eax
movd edx, mm1 ; high board in edx
}
}
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.