Author: Gerd Isenberg
Date: 10:14:28 06/18/02
Go up one level in this thread
On June 18, 2002 at 12:15:09, Adriano Bedeschi de Souza wrote:
>Could someone help me with LSB (MSB) and POPCOUNT optimization?
>
>thx,
>Bedeschi
some sample source code for msc6 with sone inline asm:
PopCount / BitCount :
#ifdef _M_IX86
__forceinline int _fastcall BitCount (BitBoard bb)
{
__asm
{
mov ecx, dword ptr bb
xor eax, eax
test ecx, ecx
jz l1
l0: lea edx, [ecx-1]
inc eax
and ecx, edx
jnz l0
l1: mov ecx, dword ptr bb+4
test ecx, ecx
jz l3
l2: lea edx, [ecx-1]
inc eax
and ecx, edx
jnz l2
l3:
}
}
#else
__forceinline int _fastcall BitCount (BitBoard bb)
{
static const UINT32 m1 = 0x55555555;
static const UINT32 m2 = 0x33333333;
static const UINT32 m3 = 0x0f0f0f0f;
UINT32 l = LOWBOARD(bb);
UINT32 h = HIGHBOARD(bb);
l = l - ((l>>1) & m1);
h = h - ((h>>1) & m1);
l = (l & m2) + ((l>>2) & m2);
h = (h & m2) + ((h>>2) & m2);
l = (l & m3) + ((l>>4) & m3);
h = (h & m3) + ((h>>4) & m3);
l = (l & 0x0ffff) + (l>>16);
h = (h & 0x0ffff) + (h>>16);
return ((l & 0x0ff) + (l>>8) + (h & 0x0ff) + (h>>8));
}
#endif
LSB / BitSearch / BitScan:
// precondition: bb not null
__forceinline unsigned int BitSearch(BitBoard bb)
{
#ifdef _M_IX86
__asm
{
bsf eax,[bb+4]
xor eax, 32
bsf eax,[bb]
}
#else
BitBoard lsbb = bb & (-(__int64)bb);
UINT32 lsb = LOWBOARD(lsbb) | HIGHBOARD(lsbb);
return ((((((((((HIGHBOARD(lsbb)!=0) <<1)
+((lsb & 0xffff0000)!=0))<<1)
+((lsb & 0xff00ff00)!=0))<<1)
+((lsb & 0xf0f0f0f0)!=0))<<1)
+((lsb & 0xcccccccc)!=0))<<1)
+((lsb & 0xaaaaaaaa)!=0);
#endif
}
LSB with reset found bit:
// precondition: bb not null
__forceinline unsigned int BitSearchAndReset(BitBoard &bb)
{
#ifdef _M_IX86
__asm
{
mov edx, [bb]
bsf eax, [edx+4]
xor eax, 32
bsf eax, [edx]
btr [edx],eax
}
#else
BitBoard lsbb = bb & (-(__int64)bb);
bb ^= lsbb;
UINT32 lsb = LOWBOARD(lsbb) | HIGHBOARD(lsbb);
return ((((((((((HIGHBOARD(lsbb)!=0) <<1)
+((lsb & 0xffff0000)!=0))<<1)
+((lsb & 0xff00ff00)!=0))<<1)
+((lsb & 0xf0f0f0f0)!=0))<<1)
+((lsb & 0xcccccccc)!=0))<<1)
+((lsb & 0xaaaaaaaa)!=0);
#endif
}
to traverse BitBoards:
while (bb)
{
unsigned int sq = BitSearchAndReset(bb);
....
}
// msb in with inline asm
#ifdef _M_IX86
__forceinline unsigned int BitSearchReverse(BitBoard bb)
{
__asm
{
bsr eax,[bb]
bsr eax,[bb+4]
setnz dl
shl dl, 5
add al, dl
}
}
#endif
regards,
Gerd
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.