X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbitboard.cpp;h=dd8023e9bd5770eef292f87301750dc55b1ccbcf;hp=ba03d66ef85669cfe4d9f3c8ddf3fa19e272d99c;hb=a0005ba45f7d5c97a096b79065c0b83ae3d81afa;hpb=063e2441b17b8260de443b3d580f49b3d65d03c7 diff --git a/src/bitboard.cpp b/src/bitboard.cpp index ba03d66e..dd8023e9 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -161,8 +161,55 @@ const int RShift[64] = { 21, 22, 22, 22, 22, 22, 22, 21, 20, 21, 21, 21, 21, 21, 21, 20 }; -#endif +#endif // defined(IS_64BIT) + +const Bitboard SquaresByColorBB[2] = { BlackSquaresBB, WhiteSquaresBB }; + +const Bitboard FileBB[8] = { + FileABB, FileBBB, FileCBB, FileDBB, FileEBB, FileFBB, FileGBB, FileHBB +}; + +const Bitboard NeighboringFilesBB[8] = { + FileBBB, FileABB|FileCBB, FileBBB|FileDBB, FileCBB|FileEBB, + FileDBB|FileFBB, FileEBB|FileGBB, FileFBB|FileHBB, FileGBB +}; +const Bitboard ThisAndNeighboringFilesBB[8] = { + FileABB|FileBBB, FileABB|FileBBB|FileCBB, + FileBBB|FileCBB|FileDBB, FileCBB|FileDBB|FileEBB, + FileDBB|FileEBB|FileFBB, FileEBB|FileFBB|FileGBB, + FileFBB|FileGBB|FileHBB, FileGBB|FileHBB +}; + +const Bitboard RankBB[8] = { + Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB +}; + +const Bitboard RelativeRankBB[2][8] = { + { Rank1BB, Rank2BB, Rank3BB, Rank4BB, Rank5BB, Rank6BB, Rank7BB, Rank8BB }, + { Rank8BB, Rank7BB, Rank6BB, Rank5BB, Rank4BB, Rank3BB, Rank2BB, Rank1BB } +}; + +const Bitboard InFrontBB[2][8] = { + { Rank2BB | Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, + Rank3BB | Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, + Rank4BB | Rank5BB | Rank6BB | Rank7BB | Rank8BB, + Rank5BB | Rank6BB | Rank7BB | Rank8BB, + Rank6BB | Rank7BB | Rank8BB, + Rank7BB | Rank8BB, + Rank8BB, + EmptyBoardBB + }, + { EmptyBoardBB, + Rank1BB, + Rank2BB | Rank1BB, + Rank3BB | Rank2BB | Rank1BB, + Rank4BB | Rank3BB | Rank2BB | Rank1BB, + Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB, + Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB, + Rank7BB | Rank6BB | Rank5BB | Rank4BB | Rank3BB | Rank2BB | Rank1BB + } +}; Bitboard RMask[64]; int RAttackIndex[64]; @@ -186,6 +233,8 @@ Bitboard BishopPseudoAttacks[64]; Bitboard RookPseudoAttacks[64]; Bitboard QueenPseudoAttacks[64]; +uint8_t BitCount8Bit[256]; + //// //// Local definitions @@ -242,55 +291,117 @@ void init_bitboards() { } +/// first_1() finds the least significant nonzero bit in a nonzero bitboard. /// pop_1st_bit() finds and clears the least significant nonzero bit in a /// nonzero bitboard. -#if defined(IS_64BIT) +#if defined(IS_64BIT) && !defined(USE_BSFQ) + +static CACHE_LINE_ALIGNMENT +const int BitTable[64] = { + 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, + 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, + 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, + 51, 60, 42, 59, 58 +}; + +Square first_1(Bitboard b) { + return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]); +} -Square pop_1st_bit(Bitboard *b) { - Bitboard bb = *b ^ (*b - 1); - uint32_t fold = int(bb) ^ int(bb >> 32); +Square pop_1st_bit(Bitboard* b) { + Bitboard bb = *b; *b &= (*b - 1); - return Square(BitTable[(fold * 0x783a9b23) >> 26]); + return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]); } -#else +#elif !defined(USE_BSFQ) + +static CACHE_LINE_ALIGNMENT +const int BitTable[64] = { + 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2, + 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52, + 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28, + 58, 20, 37, 17, 36, 8 +}; + +Square first_1(Bitboard b) { + b ^= (b - 1); + uint32_t fold = int(b) ^ int(b >> 32); + return Square(BitTable[(fold * 0x783a9b23) >> 26]); +} // Use type-punning union b_union { Bitboard b; struct { +#if defined (BIGENDIAN) + uint32_t h; + uint32_t l; +#else uint32_t l; uint32_t h; +#endif } dw; }; -// WARNING: Needs -fno-strict-aliasing compiler option -Square pop_1st_bit(Bitboard *bb) { +Square pop_1st_bit(Bitboard* bb) { - b_union u; - uint32_t b; + b_union u; + Square ret; - u.b = *bb; + u.b = *bb; - if (u.dw.l) - { - b = u.dw.l; - *((uint32_t*)bb) = b & (b - 1); - b ^= (b - 1); - } - else - { - b = u.dw.h; - *((uint32_t*)bb+1) = b & (b - 1); // Little endian only? - b = ~(b ^ (b - 1)); - } - return Square(BitTable[(b * 0x783a9b23) >> 26]); + if (u.dw.l) + { + ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 26]); + u.dw.l &= (u.dw.l - 1); + *bb = u.b; + return ret; + } + ret = Square(BitTable[((~(u.dw.h ^ (u.dw.h - 1))) * 0x783a9b23) >> 26]); + u.dw.h &= (u.dw.h - 1); + *bb = u.b; + return ret; } #endif +// Optimized bitScanReverse32() implementation by Pascal Georges. Note +// that first bit is 1, this allow to differentiate between 0 and 1. +static CACHE_LINE_ALIGNMENT +const char MsbTable[256] = { + 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 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, 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, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 +}; + +int bitScanReverse32(uint32_t b) +{ + int result = 0; + + if (b > 0xFFFF) + { + b >>= 16; + result += 16; + } + if (b > 0xFF) + { + b >>= 8; + result += 8; + } + return result + MsbTable[b]; +} + namespace { // All functions below are used to precompute various bitboards during @@ -311,6 +422,9 @@ namespace { in_front_bb(c, s) & this_and_neighboring_files_bb(s); OutpostMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s); } + + for (Bitboard b = 0ULL; b < 256ULL; b++) + BitCount8Bit[b] = (uint8_t)count_1s(b); }