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 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.