Author: Walter Faxon
Date: 03:31:10 01/10/03
Go up one level in this thread
Hi, Matt.
I just looked back at my yabs() code and noticed that I had written it for
isolating the LSB before computing LSB-1. That's an additional statement over
my original scheme in LSB_64(). So here is a "final" version of the 32-bit
table bitscanner, only slightly less pedantic.
-- Walter
Code follows: <snip> when responding.
// ---------------------------------------------------------------------------
typedef unsigned long long u64_t;
typedef unsigned long u32_t;
typedef unsigned char u8_t;
extern const u8_t LSB_32_table[134];
#define LSB_32_magic ( (u32_t)0x05407DB7 )
// ---------------------------------------------------------------------------
// Find, remove, report index of least-significant set bit of 64-bit
// "bitboard". Low-order bit reported as 0, high-order as 63.
// Argument must be non-null (or can branch where marked "*****").
// Extra-pedantic code for late x86 32-bit architecture; uses 3 GPRs.
// Written by Walter Faxon, Jan 2003. No copyright. No warranty.
//
inline
int bitscan_64( u64_t *p_bitboard )
{
u32_t *p_bb, lowHalf, highHalf, index;
union
{
u32_t dword;
struct {
u8_t low, high;
} bytes;
} fold; // aid folding in place
union
{
u32_t dword;
u8_t low;
} indexb; // aid adding to low byte of index in place
// read 64 bits
p_bb = (u32_t *)p_bitboard; // rename, no code
lowHalf = p_bb[0];
highHalf = p_bb[1];
// put active half in lowHalf; compute its index {0,1}
index = (lowHalf == 0) ? 1 : 0; // zero, test, setcc
if (lowHalf == 0) lowHalf = highHalf; // cmove; no branch
// remove LSB from lowHalf; put LSB-1 in highHalf
highHalf = lowHalf - 1;
// ***** Here, carry flag set implies null input.
lowHalf &= highHalf;
highHalf ^= lowHalf;
// ***** Here, sign flag set (highHalf < 0) implies null input.
// ***** Omit the next line if you don't want the argument updated:
p_bb[index] = lowHalf;
// convert {0,1} ==> {0,32}
index <<= 5;
// fold LSB-1 into table index
fold.dword = highHalf; // rename, no code
fold.dword ^= LSB_32_magic;
fold.dword += fold.dword >> 16;
fold.bytes.low -= fold.bytes.high;
fold.dword &= (u32_t)0x000000FF;
// add 32-bit index from table to bitboard half index
indexb.dword = index; // rename, no code
indexb.low += LSB_32_table[fold.dword]; // {0,32} + {0..31} ==> {0..63}
// done
return (int)indexb.dword;
}
// ---------------------------------------------------------------------------
// Table reports number of low-order bit of 32 as 0, high-order as 31.
// (Numbering can be reversed by changing this table.)
// Important: arrange storage so that this table is kept in the cache.
const u8_t LSB_32_table[134] =
{
#define __ -1
23,16,17,__,18,10, 8, 9,19,11, 31,__,__,__,__,__,20,12,__,__,
__,__,__,__,__,__,__,__,__,__, __,__,21,13,__,__,__,__,__,__,
__,__,__,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,__,__,
__,__,__,__,22,14,__,__,__,__, 6,__,__,__,30,__,__,__,__,__,
__,__,__,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,__,__,
__,__, 5,__,__,__,29,__,__,__, 3,__,__,__, 2,__, 1, 0, 4,__,
__,__,28,__,__,__,26,24,25,15, 27,__,__, 7
#undef __
};
// 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.