Author: Eugene Nalimov
Date: 10:24:57 06/18/02
Go up one level in this thread
Your version of popcnt use behaviour that is not guaranteed to work on the
future CPUs. (Actually there is no guarantee that it works even on the current
CPUs)
Thanks,
Eugene
On June 18, 2002 at 13:14:28, Gerd Isenberg wrote:
>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.