## Terra Help and Information

### Kogge-Stone algorithm

a post in ICC

Subject: Kogge-Stone C-routines

Posted by Gerd Isenberg   on June 02, 2003 at 14:08:16:

In Reply to: Re: A doomed bishop  posted by Steve Maughan  on June 02, 2003 at 08:43:05:

Kogge-Stone-Parallel-Prefix-Fill-Algorithm for slide attack generation.

C-routines by Steffan Westcott:

The set g (generator) are the sliding pieces to generates attacks for, the set p

(propagator) is the free square bitboard (~occupied) - they may be precalculated

for every direction.

Rook right attacks may be computed faster with bytewise arithmetic (MMX psubb):

occupied ^ ( occupied - 2*rooks)

Gerd

------------------------------------------------------------------------------

BitBoard RookUpAttacks(BitBoard rooks, BitBoard freeSquares)

{

return FillUpOccluded(rooks, freeSquares) << 8;

}

....

BitBoard FillUpOccluded(BitBoard g, BitBoard p)

{

g |= p & (g <<  8);

p &=     (p <<  8);

g |= p & (g << 16);

p &=     (p << 16);

return g |= p & (g << 32);

}

BitBoard FillDownOccluded(BitBoard g, BitBoard p)

{

g |= p & (g >>  8);

p &=     (p >>  8);

g |= p & (g >> 16);

p &=     (p >> 16);

return g |= p & (g >> 32);

}

BitBoard FillRightOccluded(BitBoard g, BitBoard p)

{

p &= 0xfefefefefefefefe;

g |= p & (g << 1);

p &=     (p << 1);

g |= p & (g << 2);

p &=     (p << 2);

return g |= p & (g << 4);

}

BitBoard FillLeftOccluded(BitBoard g, BitBoard p)

{

p &= 0x7f7f7f7f7f7f7f7f;

g |= p & (g >> 1);

p &=     (p >> 1);

g |= p & (g >> 2);

p &=     (p >> 2);

return g |= p & (g >> 4);

}