Terra Help and Information

bullet1 Theories

bullet2 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);

}


    Please give your comments in WinBoard Forum or email me. This document was updated 2004-08-02.