Looking for an CPU Instruction or a Function Which Can ...

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, Dann Corbit, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
nkg114mc
Posts: 68
Joined: Sat Dec 18, 2010 4:19 pm
Location: Tianjin, China

Looking for an CPU Instruction or a Function Which Can ...

Post by nkg114mc » Fri Oct 19, 2012 8:59 am

Hi all,

I come cross a problem on operating the bitboard. I am looking a CPU instruction or a function implemented by asm language or C language. The input of this function is a 64-bit unsigned integer N and a bit number k (0 <= k <= 64). The return value is also a 64-bit unsigned integer R. Suppose the first non-zero bit on left side of bit k is bit k1, and the first non-zero bit on the right side of k is bit k2. Then R is such a 64-bit unsigned integer that all bits from k1 to k2 (including k1 and k2) are 1, but all other bits are 0.

For example:

Code: Select all

                    High bit                                                 Low bit

        input&#58;  N = 0001000000001000100000000000000000000100000000000100000000010000 &#40;64-bit binary integer&#41;
                                    ^     ^              ^
                                    k1    k              k2
                k =                       41
        output&#58; R = 0000000000000000111111111111111111111100000000000000000000000000 &#40;64-bit binary integer&#41;
Another example:

Code: Select all

        input&#58;  N = 0001000000001000100000000000000000000100000000000100000000010000 &#40;64-bit binary integer&#41;
                       ^  ^     ^
                       k1 k     k2
                k =       57
        output&#58; R = 0001111111111000000000000000000000000000000000000000000000000000 &#40;64-bit binary integer&#41;
Is there any CPU instruction which can finish such a task, or a good implementation of function which can generate such a 64-bit unsigned integer effciently (do not need to go through each bit one by one from bit k1 to bit k2)?

Thanks a lot!

mar
Posts: 2220
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Looking for an CPU Instruction or a Function Which Can .

Post by mar » Fri Oct 19, 2012 11:04 am

Hi,

What do you want then? R? Then you can try this:
((1 << (k1+1))-1) ^ ((1<<(k2+1))-1)

(I hope it's not total BS however)

You can also use a lookup table for that.

If you want a bb mask for squares between two endsquares then you probably want something else than what you described.

Martin

Harald
Posts: 279
Joined: Thu Mar 09, 2006 12:07 am

Re: Looking for an CPU Instruction or a Function Which Can .

Post by Harald » Fri Oct 19, 2012 11:42 am

Hi

If you already know k1 and k2 you could use Martin's formula (slightly changed):
((1 << (k1+1))-1) ^ ((1<<(k2))-1)

If your bits k1, k and k2 are on one rank of a chess board and you know the
rank (0..7) then you can shift it down first, (N >> rank) and look up the
result in a table indexed by the lowest 8 bit of the shifted N.
That would to a degree also work with more bits for the range. But the
lookup index must be very big when you don't know where k is inside that
range. The index would have twice the number of bits than the maxium range.

If you don't know the position of k1 and k2 you could use something like this:

Code: Select all

while ( copyOfN )
&#123;
    int sq = msb_nr&#40; copyOfN ); // most significant bit
    ...
    copyOfN &= ~&#40;1 << sq&#41;;
&#125;
You can find k2 as the biggest sq below k and k1 as the smalles sq over k.

with:

Code: Select all

// Most significant bit number.
// Get the position of the most significant bit &#40;0-63&#41;. 
// \return 0-63 and NoSquare for an empty bitboard.
// (== log2&#41;
// &#40;Version with big table&#41;
SquareType msb_nr_big_table&#40; BB bb )
&#123;
    static const byte log2table&#91;256&#93; =
    &#123;
       64, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 
        4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
        5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
        7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
    &#125;;
    if ( bb & C&#40;0xffffffff00000000&#41; )
    &#123;
        if ( bb & C&#40;0xffff000000000000&#41; )
        &#123;
            if ( bb & C&#40;0xff00000000000000&#41; )
                return log2table&#91;bb >> 56&#93; + 56;
            return log2table&#91;bb >> 48&#93; + 48;
        &#125;
        else
        &#123;
            if ( bb & C&#40;0x0000ff0000000000&#41; )
                return log2table&#91;bb >> 40&#93; + 40;
            return log2table&#91;bb >> 32&#93; + 32;
        &#125;
    &#125;
    else
    &#123;
        if ( bb & 0xffff0000 )
        &#123;
            if ( bb & 0xff000000 )
                return log2table&#91;bb >> 24&#93; + 24;
            return log2table&#91;bb >> 16&#93; + 16;
        &#125;
        else
        &#123;
            if ( bb & 0x0000ff00 )
                return log2table&#91;bb >> 8&#93; + 8;
            else if ( bb & 0x000000ff )
                return log2table&#91;bb&#93;;
            else
                return NoSquare;
        &#125;
    &#125;
&#125;


#ifdef _MSC_VER
// Most significant bit number.
// Get the position of the most significant bit &#40;0-63&#41;. 
// \return 0-63 and NoSquare for an empty bitboard.
// (== log2&#41;
// &#40;Version with bsr = bit scan reverse )
SquareType msb_nr_bsr&#40; BB bb )
&#123;
    static const unsigned long zero_value = NoSquare;
    __asm
    &#123;
        mov eax, &#91;DWORD PTR bb + 4&#93;
        bsr eax, eax
        jne Upper
        mov eax, &#91;DWORD PTR bb + 0&#93;
        bsr eax, eax
        cmove eax, &#91;zero_value&#93;
        jmp Done
      Upper&#58;
        add eax, 32
      Done&#58;
    &#125;;
&#125;
#endif


// Most significant bit number.
// Get the position of the most significant bit &#40;0-63&#41;. 
// \return 0-63 and NoSquare for an empty bitboard.
// &#40;best version&#41;
SquareType msb_nr&#40; BB bb )
&#123;
#ifdef _MSC_VER
    return msb_nr_bsr&#40;bb&#41;;
#else
    return msb_nr_big_table&#40;bb&#41;;
#endif
&#125;
There are more algorithms for msb numbers or lsb numbers.
See the chessprogramming wiki or the other side of a Google search.

Harald

User avatar
lucasart
Posts: 3168
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Looking for an CPU Instruction or a Function Which Can .

Post by lucasart » Fri Oct 19, 2012 11:46 am

I haven't coded n assembly since the days of the 80386, so I'm really not an expert in modern assembly. But the operation you describe seems far too specific for someone to have designed an operation in assembly for it. Besides, you need to think about portability.

Here's how I would do it, in C:

Code: Select all

/*
 * left&#91;k&#93; has bits 0..k-1 set, others null
 * right&#91;k&#93; has bits k+1..63 set, others null
 * obviously if k-1<0 or k+1>63, then these are null bitboards
 * I let you write the code to precompute these
*/
uint64_t left&#91;64&#93;, right&#91;64&#93;;

/*
 * bit_segment&#91;k1&#93;&#91;k2&#93; has bits k1..k2 set others null
 * you can assume k1 < k2, and zero fill the rest
*/
uint64_t bit_segment&#91;64&#93;&#91;64&#93;;

uint64_t your_function&#40;uint64_t x, unsigned k&#41;
&#123;
  unsigned k1 = msb&#40;x & left&#91;k&#93;);
  unsigned k2 = lsb&#40;x & right&#91;k&#93;);
  /* you need to decide what you do if x & left&#91;k&#93; == 0, or x & right&#91;k&#93; == 0, not described in your spec. what if x = 0 for example ? */
  return bit_segment&#91;k1&#93;&#91;k2&#93;;
&#125;
For lsb and msb, you can have a look at Stockfish. It has all the state of the art stuff.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
lucasart
Posts: 3168
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Looking for an CPU Instruction or a Function Which Can .

Post by lucasart » Fri Oct 19, 2012 11:49 am

mar wrote:Hi,

What do you want then? R? Then you can try this:
((1 << (k1+1))-1) ^ ((1<<(k2+1))-1)

(I hope it's not total BS however)

You can also use a lookup table for that.

If you want a bb mask for squares between two endsquares then you probably want something else than what you described.

Martin
I think you missed the point. The only difficult part is to compute k1 and k2.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

bob
Posts: 20920
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Looking for an CPU Instruction or a Function Which Can .

Post by bob » Fri Oct 19, 2012 1:25 pm

nkg114mc wrote:Hi all,

I come cross a problem on operating the bitboard. I am looking a CPU instruction or a function implemented by asm language or C language. The input of this function is a 64-bit unsigned integer N and a bit number k (0 <= k <= 64). The return value is also a 64-bit unsigned integer R. Suppose the first non-zero bit on left side of bit k is bit k1, and the first non-zero bit on the right side of k is bit k2. Then R is such a 64-bit unsigned integer that all bits from k1 to k2 (including k1 and k2) are 1, but all other bits are 0.

For example:

Code: Select all

                    High bit                                                 Low bit

        input&#58;  N = 0001000000001000100000000000000000000100000000000100000000010000 &#40;64-bit binary integer&#41;
                                    ^     ^              ^
                                    k1    k              k2
                k =                       41
        output&#58; R = 0000000000000000111111111111111111111100000000000000000000000000 &#40;64-bit binary integer&#41;
Another example:

Code: Select all

        input&#58;  N = 0001000000001000100000000000000000000100000000000100000000010000 &#40;64-bit binary integer&#41;
                       ^  ^     ^
                       k1 k     k2
                k =       57
        output&#58; R = 0001111111111000000000000000000000000000000000000000000000000000 &#40;64-bit binary integer&#41;
Is there any CPU instruction which can finish such a task, or a good implementation of function which can generate such a 64-bit unsigned integer effciently (do not need to go through each bit one by one from bit k1 to bit k2)?

Thanks a lot!
On the Cray, you can do this. On X86, no. Will take a few programming tricks...

One simple approach is to locate the two 1 bits in question, say k1 and k2.

Create an array that has one bits set from each bit in the word all the way through the end. set[0] has ones everywhere, set[1] has bits from bit 1 thru 63 set, etc.

create another array that has 1 bits everywhere, except on the "other side" of a bit. For example, unset[8] would have 1 bits on bits 0-8, and 0 bits on 9-63.

given the two bits you have, k1 and k2, you use

mask = set[k1] & unset[k2];

Used to do this kind of thing in bitboards before moving on to rotated and then magics.

mar
Posts: 2220
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Looking for an CPU Instruction or a Function Which Can .

Post by mar » Fri Oct 19, 2012 1:41 pm

lucasart wrote:I think you missed the point. The only difficult part is to compute k1 and k2.
C'est parce que j'approuve Windaube et je n'y connaisse rien ;)

User avatar
JuLieN
Posts: 2948
Joined: Mon May 05, 2008 10:16 am
Location: Nantes (France)
Contact:

Re: Looking for an CPU Instruction or a Function Which Can .

Post by JuLieN » Fri Oct 19, 2012 1:43 pm

mar wrote:
lucasart wrote:I think you missed the point. The only difficult part is to compute k1 and k2.
C'est parce que j'approuve Windaube et je n'y connaisse rien ;)
:lol: :lol: :lol:
"The only good bug is a dead bug." (Don Dailey)
Image [Blog: http://tinyurl.com/predateur ] [Facebook: http://tinyurl.com/fbpredateur ] [MacEngines: http://tinyurl.com/macengines ]

bob
Posts: 20920
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Looking for an CPU Instruction or a Function Which Can .

Post by bob » Fri Oct 19, 2012 1:58 pm

lucasart wrote:
mar wrote:Hi,

What do you want then? R? Then you can try this:
((1 << (k1+1))-1) ^ ((1<<(k2+1))-1)

(I hope it's not total BS however)

You can also use a lookup table for that.

If you want a bb mask for squares between two endsquares then you probably want something else than what you described.

Martin
I think you missed the point. The only difficult part is to compute k1 and k2.
I don't think that part is hard. To find the first 1 to the right of bit k, you simply clear all bits to the left of K and bit K itself, then use a BSR. To find the first 1 to the left, clear all bits to the right of K and K itself, and use a BSF.

clearing the bits is an AND with a simple table lookup into 64 values...

User avatar
Desperado
Posts: 647
Joined: Mon Dec 15, 2008 10:45 am

Re: Looking for an CPU Instruction or a Function Which Can .

Post by Desperado » Fri Oct 19, 2012 3:12 pm

heres just another idea. I hope i read carefully enough and
its doing what you want...

(2*k2-k1) & (2*k2-k1)

Michael

Post Reply