Computer Chess Club Archives


Search

Terms

Messages

Subject: Matt Taylor's magic de Bruijn Constant

Author: Gerd Isenberg

Date: 03:03:00 07/13/03


Hi all,

Matt Taylor's invention of the super magic de Bruijn Constant 0x78291ACF is of
course usefull for yet another, but fast and portable _firstOne_ Bitscan routine
with only one 32bit multiplication!


int firstOneKey(BitBoard bb)
{
	BitBoard lsb = bb ^ (bb - 1);
	unsigned int foldedLSB = ((int) lsb) ^ ((int)(lsb>>32));
	return (foldedLSB * 0x78291ACF) >> (32-6); // range is 0..63
       // to get the bit index, a table lookup is required
}


Because i'am still looking for a fast key-fuction for two single populated move
bitboards, i tried the obvious approach to use Matt's routine twice. It works
like firstOneKey(from)*64 + firtsOneKey(to) and therefore maps to a 64*64-range.

int getMoveKey(BitBoard frbit, BitBoard tobit)
{
	frbit -= 1; tobit -= 1;
	unsigned int foldedfr = ((int) frbit)  ^ ((int)(frbit>>32));
	unsigned int foldedto = ((int) tobit)  ^ ((int)(tobit>>32));
	return ((foldedfr*0x78291ACF) ^ ((foldedto*0x78291ACF) >> 6)) >> 20;
}

x86 assembler output of this routine:

00401435 83 C6 FF             add         esi,0FFFFFFFFh
00401438 83 D1 FF             adc         ecx,0FFFFFFFFh
0040143B 83 C2 FF             add         edx,0FFFFFFFFh
0040143E 83 D0 FF             adc         eax,0FFFFFFFFh
00401441 33 CE                xor         ecx,esi
00401443 33 C2                xor         eax,edx
00401445 69 C9 CF 1A 29 78    imul        ecx,ecx,78291ACFh
0040144B 69 C0 CF 1A 29 78    imul        eax,eax,78291ACFh
00401451 C1 E8 06             shr         eax,6
00401454 33 C1                xor         eax,ecx
00401456 C1 E8 14             shr         eax,14h

only 36 Bytes - but two 32-bit multiplications.

Two questions:
Any ideas to it better, eg. only by one multiplication?
Why are the unsigned multiplications translated to "imul" by the compiler?

Thanks in advance,
Gerd




This page took 0.44 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.