Author: Dann Corbit
Date: 13:40:33 05/10/02
Go up one level in this thread
On May 10, 2002 at 04:53:45, Tim Foden wrote:
>On May 09, 2002 at 22:56:05, Dann Corbit wrote:
>
>>On May 09, 2002 at 22:17:24, Vincent Diepeveen wrote:
>>>On May 09, 2002 at 20:04:40, Dann Corbit wrote:
>>>
>>>please freshen up our mind what you can do with
>>>the top_bit function?
>>>
>>>i completely forgot. something like finding all moves from here to
>>>a certain square or so?
>>>
>>>that is... ...in a bitmap
>>
>>Nice to pick out pieces from a list of bits, if you are using it as a piece
>>list. Just a handy way to get the first piece from a list. It has the same
>>function as FirstOne(BITBOARD a) in Crafty's code.
>
>I would have thought it was similar to LastOne() :)
>
>Of course, it only returns a bitmap. To get a bit index (which is what
>FirstOne() and LastOne() return) you would need something like this:
>
>static int map[67] =
>{
> -1, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,
> 4, 0, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55, 47,
> 5, 32, 0, 38, 14, 22, 11, 58, 18, 53, 63, 9, 61, 27, 29, 50,
> 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56, 7, 48, 35,
> 6, 34, 33,
>};
>
>/* Returns bit index of top bit of x, or -1 if x = 0. */
>static INLINE int LastOne( uint64 x )
>{
> x |= x >> 1;
> x |= x >> 2;
> x |= x >> 4;
> x |= x >> 8;
> x |= x >> 16;
> x |= x >> 32;
> x ^= x >> 1;
> return map[x % 67];
>}
>
>// and of course you can do first one too...
>static INLINE int FirstOne( uint64 x )
>{
> x &= ~(x - 1)
> return map[x % 67];
>}
In the same newsgroup, Terje Mathisen (terje.mathisen@hda.hydro.com) had this
interesting follow-up:
Here's the inner loop of that Pentomino solver, it should be immediately
obvious that by inverting the meaning of 1 and 0 bits, the BSR part can
get rid of two instructions and the same number of cycles. This would
however make it much harder to test for a fitting piece further down, so
it is better to keep it the way it is.
// Start of inner (64-bit) function
aTry64:
pushad
lea edx,[ebp-1] // Start with the last entry
dec ebp
#ifdef USE_BSR // This is faster!!!
mov eax,-1
xor eax,edi
mov ecx,31
bsr eax,eax
sub ecx,eax
shld edi,ebx,cl
shl ebx,cl
#else
next_bit64:
add ebx,ebx
adc edi,edi
js next_bit64 // Search for a leading zero bit
#endif
start_64:
try_p64:
mov ecx,bPieces[edx*4] // Load current
mov esi,bPieces[ebp*4] // and last entry
mov bPieces[edx*4],esi // Put last entry into table
mov esi,ecx // and remember current
mov eax,[ecx] // Load first permutation
add ecx,4
try_perm64:
test edi,eax // Does it fit?
jnz next_perm64
or edi,eax // Yes, so update the board and
mov bsoltab[ebp*4],eax // remember the current piece
test ebp,ebp // Was this the last piece?
jz have_solution // If so, save/display this solution
call aTry64 // Recursive search for the next piece
xor edi,eax // Remove the piece from the board!
next_perm64:
mov eax,[ecx] // Load next perm of current piece
add ecx,4
test eax,eax // Sentinel value?
jnz try_perm64
mov bPieces[edx*4],esi // Restore the current piece
dec edx
jns try_p64 // More pieces to try?
popad
ret
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.