TalkChess.com

Zach Wegner wrote:... At the end we have the highest existing priority 0<=p<=63 in result, which we use in a reverse lookup table.

steffan wrote:

Zach Wegner wrote:... At the end we have the highest existing priority 0<=p<=63 in result, which we use in a reverse lookup table.

Why do the lookup? By the end of your code, isn't the answer in the variable bb? If so, you dont need the 'result' variable at all.

Cheers,
Steffan

mcostalba wrote:Just a very quick idea, probably could be further optimized. It compiles, but I have no time now for a complete test.

Code: Select all

int bitScanReverse(uint64_t b) {

    const uint64_t P32 = 0xFFFFFFFF00000000UL;
    const uint64_t P16 = 0xFFFF0000FFFF0000UL;
    const uint64_t P08 = 0xFF00FF00FF00FF00UL;
    const uint64_t P04 = 0xF0F0F0F0F0F0F0F0UL;
    const uint64_t P02 = 0xCCCCCCCCCCCCCCCCUL;
    const uint64_t P01 = 0x8888888888888888UL;

    const uint64_t M32[2] = { P32, ~P32 };
    const uint64_t M16[2] = { P16, ~P16 };
    const uint64_t M08[2] = { P08, ~P08 };
    const uint64_t M04[2] = { P04, ~P04 };
    const uint64_t M02[2] = { P02, ~P02 };

    uint64_t mask;
    int ret, n;

    ret = n = b > P32;
    mask = M32[n];

    n = b > (P16 & mask);
    mask &= M16[n];
    ret = &#40;ret << 1&#41; + n;

    n = b > &#40;P08 & mask&#41;;
    mask &= M08&#91;n&#93;;
    ret = &#40;ret << 1&#41; + n;

    n = b > &#40;P04 & mask&#41;;
    mask &= M04&#91;n&#93;;
    ret = &#40;ret << 1&#41; + n;

    n = b > &#40;P02 & mask&#41;;
    mask &= M02&#91;n&#93;;
    ret = &#40;ret << 1&#41; + n;

    return &#40;ret << 1&#41; + &#40;b > &#40;P01 & mask&#41;);
&#125;

Gerd Isenberg wrote:I don't actually understand what "arbitrary bitscan order" means ;-(
Is it file/rank order related? F.i. to implement a "symmetrical" white versus black bitscan?

Code: Select all

int symmetricalBsf (U64 bb, enumColor color) {
    if ( color == ECWhite )
       return bsf(bb);          // from a1..h1, a2..., h8
    return bsf(bswap(bb)) ^ 56; // from a8..h8, a7..., h1
}

int table[] = {
  56, 57, 58, 59, 60, 61, 62, 63,
  48, 49, 50, 51, 52, 53, 54, 55,
  ...
  0, 1, 2, 3, 4, 5, 6, 7
};

Zach Wegner wrote: Yes, that could be one possible order. The priority table in this case, for black and a1=0, would be:

Code: Select all

int table[] = {
  56, 57, 58, 59, 60, 61, 62, 63,
  48, 49, 50, 51, 52, 53, 54, 55,
  ...
  0, 1, 2, 3, 4, 5, 6, 7
};

Think about it like quad bitboards--the 4 bitboards there vertically encode a piece code 0-16 (I guess I should have said "vertical" originally instead of "horizontally"). Here 6 bitboards vertically encode a priority value 0-63 for each square. The priority is just the order the bits should be pulled off in. If you pass in -1 as a bitboard, it would first pull off the bit with priority 63, then 62...0.

As Aleks says, this could be used to order in a piece-square order. For kings you'd prioritize the back rank, with the two wings being preferable to the center (maybe with a penalty for d1/f1 though). Knights go to the center first, etc.

Zach Wegner wrote:I think this should work, but with an inversion of the P* masks. Testing for a bit in the top 32 bits is equivalent to > 0xffffffff. I think the (bb&mask)!=0 and bb>~mask should be the same speed though, a test and setnz in the first case and a cmp and seta in the second. I like your array idea though, perhaps it could be faster than a calculated mask.

Also, just scrapping the mask and doing b &= M*[n] should be faster.

int bitScanReverse(uint64_t b) {

    const uint64_t P32 = 0xFFFFFFFF00000000UL;
    const uint64_t P16 = 0xFFFF0000FFFF0000UL;
    const uint64_t P08 = 0xFF00FF00FF00FF00UL;
    const uint64_t P04 = 0xF0F0F0F0F0F0F0F0UL;
    const uint64_t P02 = 0xCCCCCCCCCCCCCCCCUL;
    const uint64_t P01 = 0x8888888888888888UL;

    const uint64_t M32[2] = { ~P32, P32 };
    const uint64_t M16[2] = { ~P16, P16 };
    const uint64_t M08[2] = { ~P08, P08 };
    const uint64_t M04[2] = { ~P04, P04 };
    const uint64_t M02[2] = { ~P02, P02 };

    int ret, n;

    ret = n = (b & P32) != 0;
    b &= M32[n];

    n = (b & P16) != 0;
    b &= M16[n];
    ret = &#40;ret << 1&#41; + n;

    n = &#40;b & P08&#41; != 0;
    b &= M08&#91;n&#93;;
    ret = &#40;ret << 1&#41; + n;

    n = &#40;b & P04&#41; != 0;
    b &= M04&#91;n&#93;;
    ret = &#40;ret << 1&#41; + n;

    n = &#40;b & P02&#41; != 0;
    b &= M02&#91;n&#93;;
    ret = &#40;ret << 1&#41; + n;

    return &#40;ret << 1&#41; + (&#40;b & P01&#41; != 0&#41;;
&#125;