Author: Walter Faxon
Date: 01:53:06 12/22/02
Go up one level in this thread
On December 21, 2002 at 12:20:19, Matt Taylor wrote:
>On December 21, 2002 at 05:16:18, Walter Faxon wrote:
<snip>
>>Question: would using a pure-C routine to remove/report a bit in a 32-bit word
>>just be better? It would require an additional loop, so at least one additional
>>variable, so I thought it best to skip it. But you wouldn't have to update both
>>halves each run through. That'd save some time and registers, at a premium
>>here. I can post the 32-bit code and table if you like.
>>
>>Or maybe we're just flogging this one little function to death... :)
>>
>>-- Walter
>
>No, please do post the 32-bit version! I would expect it to be faster on our
>existing chips. On a 64-bit chip, your 64-bit version routine will probably be
>fastest.
>
>-Matt
Ok, Matt. Here is some sample code to loop over all set bits, using a C 32-bit
bit-scan routine, LSB_32(). It's really not very neat.
By the way, regarding another of your posts, it was Sune Fischer who remarked
(on December 04, 2002 at 04:39:05) that we might consider exploring a larger
class of solutions by trying to find "any bit" rather than specifically the LSB
or MSB.
-- Walter
IMPORTANT: A lot of code here; please <snip> when responding.
Code follows:
// ---------------------------------------------------------------------------
typedef unsigned long long u64; // nonstandard
typedef unsigned long u32;
typedef unsigned char u8;
extern const u8 LSB_32_table[134]; // bit number table
#define LSB_32_magic ( (u32)0x05407DB7 ) // magic constant
// ---------------------------------------------------------------------------
// LSB_32() -- find, remove, report least-significant bit of 32.
// The value referenced by the argument 'bp' must be non-null
// (except see the note). Method: fold then table lookup.
// Written by Walter Faxon, 2002. No copyright. No warranty.
//
inline // inline declaration may differ by compiler
int LSB_32( u32* bp )
{
u32 t32;
u8 t8;
t32 = *bp - 1;
//
// NOTE: at this point, normal assembly code would leave the
// carry flag set when the input (*bp == 0). If a "break" or
// "goto" on that flag is possible, one could for example, loop
// without any leading test for (*bp != 0).
//
*bp &= t32;
t32 ^= *bp;
t32 ^= LSB_32_magic;
t32 += t32 >> 16;
t8 = (u8)t32 - (u8)(t32 >> 8); // regs addressable by byte
return LSB_32_table[t8];
}
// ---------------------------------------------------------------------------
// Table reports number of low-order bit 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 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 __
};
// ===========================================================================
// LSB32tst.c -- use LSB_32() for full bitboard bit extraction
// Written by Walter Faxon, December 2002. No copyright. No warranty.
#include <stdio.h>
// global for test only
char marked[64] = { 0 };
// ---------------------------------------------------------------------------
// Example code to loop over all squares in bitboard using LSB_32().
// Form for low-order bit numbered 0, high-order numbered 63.
// Too-clever code examines top half of bitboard first,
// but from its low-order bit.
// Form to see u64 as u32*.
#define u64_to_u32p(bb) ( (u32*)&(bb) )
void loop_over_bitboard( u64 bb )
{
u32* bp = &u64_to_u32p(bb)[1]; // no further direct reference to bb
int base = 32; // base of top half of bitboard
int sq;
for (;;)
{
for (;;)
{
// better to break on carry-set inside LSB_32()
if (*bp == 0) break;
sq = LSB_32(bp) + base;
// ==> Here, do something with sq. <==
// This test just checks and marks a global array.
if (sq < 0 || sq > 63 || marked[sq])
{
printf("ERROR 1\n");
exit(0);
}
marked[sq] = sq + 1;
}
bp--;
if ((base -= 32) < 0) break;
}
return;
}
int main( void )
{
u64 bb = ~(u64)0; // all 1's
int sq;
loop_over_bitboard(bb);
for (sq=0; sq<64; sq++)
if (marked[sq] != sq + 1)
{
printf("ERROR 2\n");
exit(0);
}
printf("DONE\n");
return 0;
}
// LSB32tst.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.