From: Marco Costalba Date: Sat, 3 Jan 2015 15:39:17 +0000 (+0100) Subject: Retire one implementation of pop_lsb() X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=3fda064a669c2bcecfa31d66c661efa7408499de Retire one implementation of pop_lsb() We have two implementations that are equivalent, so retire one. Plus usual tidy up of comments and code reshuffle. No functional change. --- diff --git a/src/bitbase.cpp b/src/bitbase.cpp index e7638cd8..57fc5016 100644 --- a/src/bitbase.cpp +++ b/src/bitbase.cpp @@ -71,7 +71,7 @@ namespace { } // namespace -bool Bitbases::probe_kpk(Square wksq, Square wpsq, Square bksq, Color us) { +bool Bitbases::probe(Square wksq, Square wpsq, Square bksq, Color us) { assert(file_of(wpsq) <= FILE_D); @@ -80,7 +80,7 @@ bool Bitbases::probe_kpk(Square wksq, Square wpsq, Square bksq, Color us) { } -void Bitbases::init_kpk() { +void Bitbases::init() { unsigned idx, repeat = 1; std::vector db; diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 4771e677..6ab90124 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -24,15 +24,17 @@ #include "bitcount.h" #include "misc.h" -Bitboard RookMasks[SQUARE_NB]; -Bitboard RookMagics[SQUARE_NB]; +int SquareDistance[SQUARE_NB][SQUARE_NB]; + +Bitboard RookMasks [SQUARE_NB]; +Bitboard RookMagics [SQUARE_NB]; Bitboard* RookAttacks[SQUARE_NB]; -unsigned RookShifts[SQUARE_NB]; +unsigned RookShifts [SQUARE_NB]; -Bitboard BishopMasks[SQUARE_NB]; -Bitboard BishopMagics[SQUARE_NB]; +Bitboard BishopMasks [SQUARE_NB]; +Bitboard BishopMagics [SQUARE_NB]; Bitboard* BishopAttacks[SQUARE_NB]; -unsigned BishopShifts[SQUARE_NB]; +unsigned BishopShifts [SQUARE_NB]; Bitboard SquareBB[SQUARE_NB]; Bitboard FileBB[FILE_NB]; @@ -42,51 +44,44 @@ Bitboard InFrontBB[COLOR_NB][RANK_NB]; Bitboard StepAttacksBB[PIECE_NB][SQUARE_NB]; Bitboard BetweenBB[SQUARE_NB][SQUARE_NB]; Bitboard LineBB[SQUARE_NB][SQUARE_NB]; -Bitboard DistanceRingsBB[SQUARE_NB][8]; +Bitboard DistanceRingBB[SQUARE_NB][8]; Bitboard ForwardBB[COLOR_NB][SQUARE_NB]; Bitboard PassedPawnMask[COLOR_NB][SQUARE_NB]; Bitboard PawnAttackSpan[COLOR_NB][SQUARE_NB]; Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; -int SquareDistance[SQUARE_NB][SQUARE_NB]; - namespace { // De Bruijn sequences. See chessprogramming.wikispaces.com/BitScan - const uint64_t DeBruijn_64 = 0x3F79D71B4CB0A89ULL; - const uint32_t DeBruijn_32 = 0x783A9B23; + const uint64_t DeBruijn64 = 0x3F79D71B4CB0A89ULL; + const uint32_t DeBruijn32 = 0x783A9B23; - int MS1BTable[256]; - Square BSFTable[SQUARE_NB]; - Bitboard RookTable[0x19000]; // Storage space for rook attacks - Bitboard BishopTable[0x1480]; // Storage space for bishop attacks + int MS1BTable[256]; // To implement software msb() + Square BSFTable[SQUARE_NB]; // To implement software bitscan + Bitboard RookTable[0x19000]; // To store rook attacks + Bitboard BishopTable[0x1480]; // To store bishop attacks typedef unsigned (Fn)(Square, Bitboard); void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[], Bitboard masks[], unsigned shifts[], Square deltas[], Fn index); - FORCE_INLINE unsigned bsf_index(Bitboard b) { + // bsf_index() returns the index into BSFTable[] to look up the bitscan. Uses + // Matt Taylor's folding for 32 bit case, extended to 64 bit by Kim Walisch. - // Matt Taylor's folding for 32 bit systems, extended to 64 bits by Kim Walisch - b ^= (b - 1); - return Is64Bit ? (b * DeBruijn_64) >> 58 - : ((unsigned(b) ^ unsigned(b >> 32)) * DeBruijn_32) >> 26; + FORCE_INLINE unsigned bsf_index(Bitboard b) { + b ^= b - 1; + return Is64Bit ? (b * DeBruijn64) >> 58 + : ((unsigned(b) ^ unsigned(b >> 32)) * DeBruijn32) >> 26; } } -/// lsb()/msb() finds the least/most significant bit in a non-zero bitboard. -/// pop_lsb() finds and clears the least significant bit in a non-zero bitboard. - #ifndef USE_BSFQ -Square lsb(Bitboard b) { return BSFTable[bsf_index(b)]; } - -Square pop_lsb(Bitboard* b) { +/// Software fall-back of lsb() and msb() for CPU lacking hardware support - Bitboard bb = *b; - *b = bb & (bb - 1); - return BSFTable[bsf_index(bb)]; +Square lsb(Bitboard b) { + return BSFTable[bsf_index(b)]; } Square msb(Bitboard b) { @@ -120,8 +115,8 @@ Square msb(Bitboard b) { #endif // ifndef USE_BSFQ -/// Bitboards::pretty() returns an ASCII representation of a bitboard to be -/// printed to standard output. This is sometimes useful for debugging. +/// Bitboards::pretty() returns an ASCII representation of a bitboard suitable +/// to be printed to standard output. Useful for debugging. const std::string Bitboards::pretty(Bitboard b) { @@ -178,7 +173,7 @@ void Bitboards::init() { if (s1 != s2) { SquareDistance[s1][s2] = std::max(distance(s1, s2), distance(s1, s2)); - DistanceRingsBB[s1][SquareDistance[s1][s2] - 1] |= s2; + DistanceRingBB[s1][SquareDistance[s1][s2] - 1] |= s2; } int steps[][9] = { {}, { 7, 9 }, { 17, 15, 10, 6, -6, -10, -15, -17 }, diff --git a/src/bitboard.h b/src/bitboard.h index f361658a..b38fa55b 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -25,20 +25,22 @@ #include "types.h" -namespace Bitboards { +namespace Bitbases { void init(); -const std::string pretty(Bitboard b); +bool probe(Square wksq, Square wpsq, Square bksq, Color us); } -namespace Bitbases { +namespace Bitboards { -void init_kpk(); -bool probe_kpk(Square wksq, Square wpsq, Square bksq, Color us); +void init(); +const std::string pretty(Bitboard b); } +const Bitboard DarkSquares = 0xAA55AA55AA55AA55ULL; + const Bitboard FileABB = 0x0101010101010101ULL; const Bitboard FileBBB = FileABB << 1; const Bitboard FileCBB = FileABB << 2; @@ -57,15 +59,17 @@ const Bitboard Rank6BB = Rank1BB << (8 * 5); const Bitboard Rank7BB = Rank1BB << (8 * 6); const Bitboard Rank8BB = Rank1BB << (8 * 7); -extern Bitboard RookMasks[SQUARE_NB]; -extern Bitboard RookMagics[SQUARE_NB]; +extern int SquareDistance[SQUARE_NB][SQUARE_NB]; + +extern Bitboard RookMasks [SQUARE_NB]; +extern Bitboard RookMagics [SQUARE_NB]; extern Bitboard* RookAttacks[SQUARE_NB]; -extern unsigned RookShifts[SQUARE_NB]; +extern unsigned RookShifts [SQUARE_NB]; -extern Bitboard BishopMasks[SQUARE_NB]; -extern Bitboard BishopMagics[SQUARE_NB]; +extern Bitboard BishopMasks [SQUARE_NB]; +extern Bitboard BishopMagics [SQUARE_NB]; extern Bitboard* BishopAttacks[SQUARE_NB]; -extern unsigned BishopShifts[SQUARE_NB]; +extern unsigned BishopShifts [SQUARE_NB]; extern Bitboard SquareBB[SQUARE_NB]; extern Bitboard FileBB[FILE_NB]; @@ -75,15 +79,12 @@ extern Bitboard InFrontBB[COLOR_NB][RANK_NB]; extern Bitboard StepAttacksBB[PIECE_NB][SQUARE_NB]; extern Bitboard BetweenBB[SQUARE_NB][SQUARE_NB]; extern Bitboard LineBB[SQUARE_NB][SQUARE_NB]; -extern Bitboard DistanceRingsBB[SQUARE_NB][8]; +extern Bitboard DistanceRingBB[SQUARE_NB][8]; extern Bitboard ForwardBB[COLOR_NB][SQUARE_NB]; extern Bitboard PassedPawnMask[COLOR_NB][SQUARE_NB]; extern Bitboard PawnAttackSpan[COLOR_NB][SQUARE_NB]; extern Bitboard PseudoAttacks[PIECE_TYPE_NB][SQUARE_NB]; -extern int SquareDistance[SQUARE_NB][SQUARE_NB]; - -const Bitboard DarkSquares = 0xAA55AA55AA55AA55ULL; /// Overloads of bitwise operators between a Bitboard and a Square for testing /// whether a given bit is set in a bitboard, and for setting and clearing bits. @@ -92,14 +93,6 @@ inline Bitboard operator&(Bitboard b, Square s) { return b & SquareBB[s]; } -inline Bitboard& operator|=(Bitboard& b, Square s) { - return b |= SquareBB[s]; -} - -inline Bitboard& operator^=(Bitboard& b, Square s) { - return b ^= SquareBB[s]; -} - inline Bitboard operator|(Bitboard b, Square s) { return b | SquareBB[s]; } @@ -108,32 +101,21 @@ inline Bitboard operator^(Bitboard b, Square s) { return b ^ SquareBB[s]; } -inline bool more_than_one(Bitboard b) { - return b & (b - 1); +inline Bitboard& operator|=(Bitboard& b, Square s) { + return b |= SquareBB[s]; } -template inline int distance(T x, T y) { return x < y ? y - x : x - y; } -template<> inline int distance(Square x, Square y) { return SquareDistance[x][y]; } - -template inline int distance(T2 x, T2 y); -template<> inline int distance(Square x, Square y) { return distance(file_of(x), file_of(y)); } -template<> inline int distance(Square x, Square y) { return distance(rank_of(x), rank_of(y)); } - - -/// shift_bb() moves bitboard one step along direction Delta. Mainly for pawns. - -template -inline Bitboard shift_bb(Bitboard b) { +inline Bitboard& operator^=(Bitboard& b, Square s) { + return b ^= SquareBB[s]; +} - return Delta == DELTA_N ? b << 8 : Delta == DELTA_S ? b >> 8 - : Delta == DELTA_NE ? (b & ~FileHBB) << 9 : Delta == DELTA_SE ? (b & ~FileHBB) >> 7 - : Delta == DELTA_NW ? (b & ~FileABB) << 7 : Delta == DELTA_SW ? (b & ~FileABB) >> 9 - : 0; +inline bool more_than_one(Bitboard b) { + return b & (b - 1); } -/// rank_bb() and file_bb() take a file or a square as input and return -/// a bitboard representing all squares on the given file or rank. +/// rank_bb() and file_bb() return a bitboard representing all the squares on +/// the given file or rank. inline Bitboard rank_bb(Rank r) { return RankBB[r]; @@ -152,83 +134,102 @@ inline Bitboard file_bb(Square s) { } -/// adjacent_files_bb() takes a file as input and returns a bitboard representing -/// all squares on the adjacent files. +/// shift_bb() moves a bitboard one step along direction Delta. Mainly for pawns -inline Bitboard adjacent_files_bb(File f) { - return AdjacentFilesBB[f]; +template +inline Bitboard shift_bb(Bitboard b) { + return Delta == DELTA_N ? b << 8 : Delta == DELTA_S ? b >> 8 + : Delta == DELTA_NE ? (b & ~FileHBB) << 9 : Delta == DELTA_SE ? (b & ~FileHBB) >> 7 + : Delta == DELTA_NW ? (b & ~FileABB) << 7 : Delta == DELTA_SW ? (b & ~FileABB) >> 9 + : 0; } -/// in_front_bb() takes a color and a rank as input, and returns a bitboard -/// representing all the squares on all ranks in front of the rank, from the -/// given color's point of view. For instance, in_front_bb(BLACK, RANK_3) will -/// give all squares on ranks 1 and 2. +/// adjacent_files_bb() returns a bitboard representing all the squares on the +/// adjacent files of the given one. -inline Bitboard in_front_bb(Color c, Rank r) { - return InFrontBB[c][r]; +inline Bitboard adjacent_files_bb(File f) { + return AdjacentFilesBB[f]; } -/// between_bb() returns a bitboard representing all squares between two squares. -/// For instance, between_bb(SQ_C4, SQ_F7) returns a bitboard with the bits for -/// square d5 and e6 set. If s1 and s2 are not on the same rank, file or diagonal, -/// 0 is returned. +/// between_bb() returns a bitboard representing all the squares between the two +/// given ones. For instance, between_bb(SQ_C4, SQ_F7) returns a bitboard with +/// the bits for square d5 and e6 set. If s1 and s2 are not on the same rank, file +/// or diagonal, 0 is returned. inline Bitboard between_bb(Square s1, Square s2) { return BetweenBB[s1][s2]; } -/// forward_bb() takes a color and a square as input, and returns a bitboard -/// representing all squares along the line in front of the square, from the -/// point of view of the given color. Definition of the table is: -/// ForwardBB[c][s] = in_front_bb(c, s) & file_bb(s) +/// in_front_bb() returns a bitboard representing all the squares on all the ranks +/// in front of the given one, from the point of view of the given color. For +/// instance, in_front_bb(BLACK, RANK_3) will return the squares on ranks 1 and 2. + +inline Bitboard in_front_bb(Color c, Rank r) { + return InFrontBB[c][r]; +} + + +/// forward_bb() returns a bitboard representing all the squares along the line +/// in front of the given one, from the point of view of the given color: +/// ForwardBB[c][s] = in_front_bb(c, s) & file_bb(s) inline Bitboard forward_bb(Color c, Square s) { return ForwardBB[c][s]; } -/// pawn_attack_span() takes a color and a square as input, and returns a bitboard -/// representing all squares that can be attacked by a pawn of the given color -/// when it moves along its file starting from the given square. Definition is: -/// PawnAttackSpan[c][s] = in_front_bb(c, s) & adjacent_files_bb(s); +/// pawn_attack_span() returns a bitboard representing all the squares that can be +/// attacked by a pawn of the given color when it moves along its file, starting +/// from the given square: +/// PawnAttackSpan[c][s] = in_front_bb(c, s) & adjacent_files_bb(s); inline Bitboard pawn_attack_span(Color c, Square s) { return PawnAttackSpan[c][s]; } -/// passed_pawn_mask() takes a color and a square as input, and returns a -/// bitboard mask which can be used to test if a pawn of the given color on -/// the given square is a passed pawn. Definition of the table is: -/// PassedPawnMask[c][s] = pawn_attack_span(c, s) | forward_bb(c, s) +/// passed_pawn_mask() returns a bitboard mask which can be used to test if a +/// pawn of the given color and on the given square is a passed pawn: +/// PassedPawnMask[c][s] = pawn_attack_span(c, s) | forward_bb(c, s) inline Bitboard passed_pawn_mask(Color c, Square s) { return PassedPawnMask[c][s]; } -/// squares_of_color() returns a bitboard representing all squares with the same -/// color of the given square. +/// squares_of_color() returns a bitboard representing all the squares of the +/// same color of the given one. inline Bitboard squares_of_color(Square s) { return DarkSquares & s ? DarkSquares : ~DarkSquares; } -/// aligned() returns true if the squares s1, s2 and s3 are aligned -/// either on a straight or on a diagonal line. +/// aligned() returns true if the squares s1, s2 and s3 are aligned either on a +/// straight or on a diagonal line. inline bool aligned(Square s1, Square s2, Square s3) { return LineBB[s1][s2] & s3; } -/// Functions for computing sliding attack bitboards. Function attacks_bb() takes -/// a square and a bitboard of occupied squares as input, and returns a bitboard -/// representing all squares attacked by Pt (bishop or rook) on the given square. +/// distance() functions return the distance between x and y, defined as the +/// number of steps for a king in x to reach y. Works with squares, ranks, files. + +template inline int distance(T x, T y) { return x < y ? y - x : x - y; } +template<> inline int distance(Square x, Square y) { return SquareDistance[x][y]; } + +template inline int distance(T2 x, T2 y); +template<> inline int distance(Square x, Square y) { return distance(file_of(x), file_of(y)); } +template<> inline int distance(Square x, Square y) { return distance(rank_of(x), rank_of(y)); } + + +/// attacks_bb() returns a bitboard representing all the squares attacked by a +/// piece of type Pt (bishop or rook) placed on 's'. The helper magic_index() +/// looks up the index using the 'magic bitboards' approach. template FORCE_INLINE unsigned magic_index(Square s, Bitboard occupied) { @@ -263,8 +264,8 @@ inline Bitboard attacks_bb(Piece pc, Square s, Bitboard occupied) { } } -/// lsb()/msb() finds the least/most significant bit in a non-zero bitboard. -/// pop_lsb() finds and clears the least significant bit in a non-zero bitboard. + +/// lsb() and msb() return the least/most significant bit in a non-zero bitboard #ifdef USE_BSFQ @@ -297,7 +298,7 @@ FORCE_INLINE Square lsb(Bitboard b) { return (Square) (uint32_t(b) ? lsb32(uint32_t(b)) : 32 + lsb32(uint32_t(b >> 32))); } -# else +# else // Assumed gcc or compatible compiler FORCE_INLINE Square lsb(Bitboard b) { // Assembly code by Heinz van Saanen Bitboard idx; @@ -313,21 +314,24 @@ FORCE_INLINE Square msb(Bitboard b) { # endif +#else // ifdef(USE_BSFQ) + +Square lsb(Bitboard b); +Square msb(Bitboard b); + +#endif + + +/// pop_lsb() finds and clears the least significant bit in a non-zero bitboard + FORCE_INLINE Square pop_lsb(Bitboard* b) { const Square s = lsb(*b); *b &= *b - 1; return s; } -#else // if defined(USE_BSFQ) - -extern Square msb(Bitboard b); -extern Square lsb(Bitboard b); -extern Square pop_lsb(Bitboard* b); - -#endif -/// frontmost_sq() and backmost_sq() find the square corresponding to the +/// frontmost_sq() and backmost_sq() return the square corresponding to the /// most/least advanced bit relative to the given color. inline Square frontmost_sq(Color c, Bitboard b) { return c == WHITE ? msb(b) : lsb(b); } diff --git a/src/endgame.cpp b/src/endgame.cpp index 9cc0c372..fd4c92f7 100644 --- a/src/endgame.cpp +++ b/src/endgame.cpp @@ -217,7 +217,7 @@ Value Endgame::operator()(const Position& pos) const { Color us = strongSide == pos.side_to_move() ? WHITE : BLACK; - if (!Bitbases::probe_kpk(wksq, psq, bksq, us)) + if (!Bitbases::probe(wksq, psq, bksq, us)) return VALUE_DRAW; Value result = VALUE_KNOWN_WIN + PawnValueEg + Value(rank_of(psq)); @@ -852,5 +852,5 @@ ScaleFactor Endgame::operator()(const Position& pos) const { // Probe the KPK bitbase with the weakest side's pawn removed. If it's a draw, // it's probably at least a draw even with the pawn. - return Bitbases::probe_kpk(wksq, psq, bksq, us) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW; + return Bitbases::probe(wksq, psq, bksq, us) ? SCALE_FACTOR_NONE : SCALE_FACTOR_DRAW; } diff --git a/src/main.cpp b/src/main.cpp index d34fb974..95400ce1 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -35,7 +35,7 @@ int main(int argc, char* argv[]) { UCI::init(Options); Bitboards::init(); Position::init(); - Bitbases::init_kpk(); + Bitbases::init(); Search::init(); Eval::init(); Pawns::init(); diff --git a/src/pawns.cpp b/src/pawns.cpp index 6ec718ff..0a227567 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -288,7 +288,7 @@ Score Entry::do_king_safety(const Position& pos, Square ksq) { Bitboard pawns = pos.pieces(Us, PAWN); if (pawns) - while (!(DistanceRingsBB[ksq][minKingPawnDistance[Us]++] & pawns)) {} + while (!(DistanceRingBB[ksq][minKingPawnDistance[Us]++] & pawns)) {} if (relative_rank(Us, ksq) > RANK_4) return make_score(0, -16 * minKingPawnDistance[Us]);