Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Matt Taylor's magic de Bruijn Constant

Author: Gerd Isenberg

Date: 12:05:26 07/14/03

Go up one level in this thread


On July 14, 2003 at 09:54:39, Walter Faxon wrote:

>On July 13, 2003 at 12:51:45, Gerd Isenberg wrote (after snipping):
>
>>Hi Bas,
>>
>>Nice constants, but they map 32-bit to a range of 64 or 60 - about the double
>>space as necessary ;-) Ahh, you use signed char for table, may be a additional
>>and 0xff or movsx instead of mov. Why not using de Bruijn constants, that map to
>>a range of 32?
>>
>>Regards,
>>Gerd
>
>
>Hi, Gerd; Bas.
>
>Here's one with a 32-byte array, and (hopefully) use of conditional-move instead
>of a branch, which reduces the code size as well.  Again, this version doesn't
>remove the bit.  An unsigned byte table is ok if we can 'or' the byte into a
>byte-addressable register, I think.
>
>A smaller table doesn't solve the cache problem, but still, smaller should be
>better.  There's got to be some way to disable replacement of some cache lines.
>
>-- Walter
>
>
>// ---------------------------------------------------------------------------
>// Should we use a union to force better alignment of this table?
>const unsigned char MT32table [32] = {
>    0,  9,  1, 10, 13, 21,  2, 29, 11, 14, 16, 18, 22, 25,  3, 30,
>    8, 12, 20, 28, 15, 17, 24,  7, 19, 27, 23,  6, 26,  5,  4, 31 };
>
>// Constant, table reference and inline function below, all in header file.
>// There are 1024 such constants possible.
>
>#define MT32magic  (130329821UL)
>extern const unsigned char MT32table [32];
>
>/*  Return index of least-significant bit of 64; argument must be non-zero.
>    "Magic" indexing algorithm by Matt Taylor.
>    Version for 32-bit architecture by WF.
>    No warranty.
>*/
>__forceinline int leastSigBit64( unsigned __int64 bb )
>{
>    unsigned long bb0, bb1;
>    int bbHalf;
>
>    bb0 = ((unsigned long*)&bb)[0];
>    bb1 = ((unsigned long*)&bb)[1];     // if bb in registers, no code
>    bbHalf = (bb0 == 0);
>    if (bbHalf) bb0 = bb1;              // will code as cmov (ideally)
>    bb0 ^= bb0 - 1;
>    bb0 *= MT32magic;
>    return (bbHalf << 5) | MT32table[bb0 >> 27];
>        // if bbHalf in byte-addressable register, bitwise-or
>        // preferred to avoid int+char type/sizing conflict
>}
>
>//eof


Hi Walter,

that's what i meant. Unfortunately no cmov with MSVC 6 :-(
Therefore i would prefere the unconditional one with the 0x78291ACF with
64-Byte lookup table.

Regards,
Gerd


My small De Bruijn Test of 130329821:

0x07C4ACDD
00000111110001001010110011011101B
bit 31 - bit 27   00000  0
bit 30 - bit 26   00001  1
bit 29 - bit 25   00011  3
bit 28 - bit 24   00111  7
bit 27 - bit 23   01111 15
bit 26 - bit 22   11111 31
bit 25 - bit 21   11110 30
bit 24 - bit 20   11100 28
bit 23 - bit 19   11000 24
bit 22 - bit 18   10001 17
bit 21 - bit 17   00010  2
bit 20 - bit 16   00100  4
bit 19 - bit 15   01001  9
bit 18 - bit 14   10010 18
bit 17 - bit 13   00101  5
bit 16 - bit 12   01010 10
bit 15 - bit 11   10101 21
bit 14 - bit 10   01011 11
bit 13 - bit  9   10110 22
bit 12 - bit  8   01100 12
bit 11 - bit  7   11001 25
bit 10 - bit  6   10011 19
bit  9 - bit  5   00110  6
bit  8 - bit  4   01101 13
bit  7 - bit  3   11011 27
bit  6 - bit  2   10111 23
bit  5 - bit  1   01110 14
bit  4 - bit  0   11101 29
0x07C4ACDD is 5bit de Bruin Sequence




This page took 0.03 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.