Computer Chess Club Archives


Search

Terms

Messages

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

Author: Walter Faxon

Date: 06:54:39 07/14/03

Go up one level in this thread


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



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