Author: Walter Faxon
Date: 02:47:00 01/16/03
Hi, bitboarders.
As per Crafty's LastOne() function, this routine simply reports the bit number
of the lowest set bit in a bitboard, with the most-significant bit reported as
number 0, the least-significant as number 63, and null input as number 64. This
version is mostly for the AMD x86, to replace code using its otherwise slow bsf
instruction. Also note: since VC7 supposedly doesn't generate conditional
move instructions, and some compilers won't recognize the structures as being
in-register, the asm output will likely have to be tweaked a bit by hand for
good performance. (It's not an ideal world.)
-- Walter
Code follows. <snip> if responding.
// ===========================================================================
// LastOne.c -- duplicate Crafty LastOne() functionality using table.
// ---------------------------------------------------------------------------
typedef unsigned long long u64_t;
typedef unsigned long u32_t;
typedef unsigned char u8_t;
extern const u8_t LSB_32_table[139];
#define LSB_32_magic ( (u32_t)0x05407DB7 )
// ---------------------------------------------------------------------------
// Find and report index of lsb in 64-bit "bitboard".
// High-order bit reported as 0, low-order as 63, null input as 64.
// Extra-pedantic code for late x86 32-bit architecture; uses 3 GPRs.
// Best asm code may require hand fixes; see comments.
// Written by Walter Faxon, Jan 2003. No copyright. No warranty.
//
inline
int LastOne( u64_t bitboard )
{
u32_t 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
lowHalf = (u32_t)bitboard;
highHalf = (u32_t)(bitboard >> 32);
// active half into lowHalf
index = (lowHalf != 0); // zero, test, setcc
if (lowHalf == 0) lowHalf = highHalf; // cmove; no branch
index <<= 5;
// compute lsb-1 in highHalf
highHalf = lowHalf - 1; // possible LEA
lowHalf &= highHalf;
highHalf ^= lowHalf;
// fold lsb-1 into byte
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;
// look up 32-bit index; add to half
indexb.dword = index; // rename; no code
indexb.low += LSB_32_table[fold.dword];
return (int)indexb.dword;
}
// ---------------------------------------------------------------------------
// Table reports number of high-order bit of 32 as 0, low-order as 31,
// no set bit as 64.
// Important: arrange storage so that this table is kept in the cache.
// Version for Crafty LastOne() function.
const u8_t LSB_32_table[139] =
{
#define __ -1
8,15,14,__,13,21,23,22,12,20, 0,__,__,__,__,__,11,19,__,__,
__,__,__,__,__,__,__,__,__,__, __,__,10,18,__,__,__,__,__,__,
__,__,__,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,__,__,
__,__,__,__, 9,17,__,__,__,__, 25,__,__,__, 1,__,__,__,__,__,
__,__,__,__,__,__,__,__,__,__, __,__,__,__,__,__,__,__,__,__,
__,__,26,__,__,__, 2,__,__,__, 28,__,__,__,29,__,30,31,27,__,
__,__, 3,__,__,__, 5, 7, 6,16, 4,__,__,24,__,__,__,__,64
#undef __
};
// ---------------------------------------------------------------------------
// test driver
#include <stdio.h>
int main( void )
{
u64_t bb = ~(u64_t)0;
int tstsq = 64;
for (;;)
{
int sq = LastOne(bb);
// printf("sq=%d\n", sq);
if (--tstsq < 0)
if (sq == 64) break;
else
{
printf("error2");
return 1;
}
if (sq != tstsq)
{
printf("error1");
return 1;
}
bb ^= ((u64_t)1 << 63) >> sq;
}
printf("done");
return 0;
}
// LastOne.c end
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.