From: mstembera Date: Fri, 8 Apr 2016 17:52:15 +0000 (+0100) Subject: Simplify popcnt X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=8fb45caadef67fb2ccc27857c15ade987d9f5e2f Simplify popcnt Also a speedup(about 1%) on 64-bit w/o hardware popcnt Retire Max15 and Full template parameters (Contributed by Marco Costalba) Now that we have just SW and HW versions, use template default parameter to get rid of explicit template parameters. Retire bitcount.h and move the only defined function to bitboard.h No functional change Resolves #620 --- diff --git a/src/bitboard.cpp b/src/bitboard.cpp index ba1af2f2..334ea879 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -21,9 +21,9 @@ #include #include "bitboard.h" -#include "bitcount.h" #include "misc.h" +uint8_t PopCnt16[1 << 16]; int SquareDistance[SQUARE_NB][SQUARE_NB]; Bitboard RookMasks [SQUARE_NB]; @@ -74,6 +74,16 @@ namespace { return Is64Bit ? (b * DeBruijn64) >> 58 : ((unsigned(b) ^ unsigned(b >> 32)) * DeBruijn32) >> 26; } + + + // popcount16() counts the non-zero bits using SWAR-Popcount algorithm + + uint8_t popcount16(uint16_t u) { + u -= (u >> 1) & 0x5555U; + u = ((u >> 2) & 0x3333U) + (u & 0x3333U); + u = ((u >> 4) + u) & 0x0F0FU; + return (u * 0x0101U) >> 8; + } } #ifdef NO_BSF @@ -141,6 +151,9 @@ const std::string Bitboards::pretty(Bitboard b) { void Bitboards::init() { + for (unsigned i = 0; i < (1 << 16); ++i) + PopCnt16[i] = popcount16(i); + for (Square s = SQ_A1; s <= SQ_H8; ++s) { SquareBB[s] = 1ULL << s; @@ -265,7 +278,7 @@ namespace { // the number of 1s of the mask. Hence we deduce the size of the shift to // apply to the 64 or 32 bits word to get the index. masks[s] = sliding_attack(deltas, s, 0) & ~edges; - shifts[s] = (Is64Bit ? 64 : 32) - popcount(masks[s]); + shifts[s] = (Is64Bit ? 64 : 32) - popcount(masks[s]); // Use Carry-Rippler trick to enumerate all subsets of masks[s] and // store the corresponding sliding attack bitboard in reference[]. @@ -296,7 +309,7 @@ namespace { do { do magics[s] = rng.sparse_rand(); - while (popcount((magics[s] * masks[s]) >> 56) < 6); + while (popcount((magics[s] * masks[s]) >> 56) < 6); // A good magic must map every possible occupancy to an index that // looks up the correct sliding attack in the attacks[s] database. diff --git a/src/bitboard.h b/src/bitboard.h index 77a824ba..21dc6e44 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -257,6 +257,32 @@ inline Bitboard attacks_bb(Piece pc, Square s, Bitboard occupied) { } +/// popcount() counts the number of non-zero bits in a bitboard + +inline int popcount(Bitboard b) { + +#ifndef USE_POPCNT + + extern uint8_t PopCnt16[1 << 16]; + union { Bitboard bb; uint16_t u[4]; } v = { b }; + return PopCnt16[v.u[0]] + PopCnt16[v.u[1]] + PopCnt16[v.u[2]] + PopCnt16[v.u[3]]; + +#elif defined(_MSC_VER) && defined(__INTEL_COMPILER) + + return _mm_popcnt_u64(b); + +#elif defined(_MSC_VER) + + return (int)__popcnt64(b); + +#else // Assumed gcc or compatible compiler + + return __builtin_popcountll(b); + +#endif +} + + /// lsb() and msb() return the least/most significant bit in a non-zero bitboard #if defined(__GNUC__) diff --git a/src/bitcount.h b/src/bitcount.h deleted file mode 100644 index 7609da40..00000000 --- a/src/bitcount.h +++ /dev/null @@ -1,105 +0,0 @@ -/* - Stockfish, a UCI chess playing engine derived from Glaurung 2.1 - Copyright (C) 2004-2008 Tord Romstad (Glaurung author) - Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad - Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad - - Stockfish is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - Stockfish is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see . -*/ - -#ifndef BITCOUNT_H_INCLUDED -#define BITCOUNT_H_INCLUDED - -#include - -#include "types.h" - -enum BitCountType { - CNT_64, - CNT_64_MAX15, - CNT_32, - CNT_32_MAX15, - CNT_HW_POPCNT -}; - -/// Determine at compile time the best popcount<> specialization according to -/// whether the platform is 32 or 64 bit, the maximum number of non-zero -/// bits to count and if the hardware popcnt instruction is available. -const BitCountType Full = HasPopCnt ? CNT_HW_POPCNT : Is64Bit ? CNT_64 : CNT_32; -const BitCountType Max15 = HasPopCnt ? CNT_HW_POPCNT : Is64Bit ? CNT_64_MAX15 : CNT_32_MAX15; - - -/// popcount() counts the number of non-zero bits in a bitboard -template inline int popcount(Bitboard); - -template<> -inline int popcount(Bitboard b) { - b -= (b >> 1) & 0x5555555555555555ULL; - b = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL); - b = ((b >> 4) + b) & 0x0F0F0F0F0F0F0F0FULL; - return (b * 0x0101010101010101ULL) >> 56; -} - -template<> -inline int popcount(Bitboard b) { - b -= (b >> 1) & 0x5555555555555555ULL; - b = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL); - return (b * 0x1111111111111111ULL) >> 60; -} - -template<> -inline int popcount(Bitboard b) { - unsigned w = unsigned(b >> 32), v = unsigned(b); - v -= (v >> 1) & 0x55555555; // 0-2 in 2 bits - w -= (w >> 1) & 0x55555555; - v = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits - w = ((w >> 2) & 0x33333333) + (w & 0x33333333); - v = ((v >> 4) + v + (w >> 4) + w) & 0x0F0F0F0F; - return (v * 0x01010101) >> 24; -} - -template<> -inline int popcount(Bitboard b) { - unsigned w = unsigned(b >> 32), v = unsigned(b); - v -= (v >> 1) & 0x55555555; // 0-2 in 2 bits - w -= (w >> 1) & 0x55555555; - v = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits - w = ((w >> 2) & 0x33333333) + (w & 0x33333333); - return ((v + w) * 0x11111111) >> 28; -} - -template<> -inline int popcount(Bitboard b) { - -#ifndef USE_POPCNT - - assert(false); - return b != 0; // Avoid 'b not used' warning - -#elif defined(_MSC_VER) && defined(__INTEL_COMPILER) - - return _mm_popcnt_u64(b); - -#elif defined(_MSC_VER) - - return (int)__popcnt64(b); - -#else // Assumed gcc or compatible compiler - - return __builtin_popcountll(b); - -#endif -} - -#endif // #ifndef BITCOUNT_H_INCLUDED diff --git a/src/endgame.cpp b/src/endgame.cpp index 30826dd7..cc663043 100644 --- a/src/endgame.cpp +++ b/src/endgame.cpp @@ -22,7 +22,6 @@ #include #include "bitboard.h" -#include "bitcount.h" #include "endgame.h" #include "movegen.h" diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 6b329bb0..da4b9c30 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -24,7 +24,7 @@ #include #include -#include "bitcount.h" +#include "bitboard.h" #include "evaluate.h" #include "material.h" #include "pawns.h" @@ -234,7 +234,7 @@ namespace { { ei.kingRing[Them] = b | shift_bb(b); b &= ei.attackedBy[Us][PAWN]; - ei.kingAttackersCount[Us] = b ? popcount(b) : 0; + ei.kingAttackersCount[Us] = b ? popcount(b) : 0; ei.kingAdjacentZoneAttacksCount[Us] = ei.kingAttackersWeight[Us] = 0; } else @@ -278,7 +278,7 @@ namespace { ei.kingAttackersWeight[Us] += KingAttackWeights[Pt]; bb = b & ei.attackedBy[Them][KING]; if (bb) - ei.kingAdjacentZoneAttacksCount[Us] += popcount(bb); + ei.kingAdjacentZoneAttacksCount[Us] += popcount(bb); } if (Pt == QUEEN) @@ -286,7 +286,7 @@ namespace { | ei.attackedBy[Them][BISHOP] | ei.attackedBy[Them][ROOK]); - int mob = popcount(b & mobilityArea[Us]); + int mob = popcount(b & mobilityArea[Us]); mobility[Us] += MobilityBonus[Pt][mob]; @@ -334,7 +334,7 @@ namespace { { Bitboard alignedPawns = pos.pieces(Them, PAWN) & PseudoAttacks[ROOK][s]; if (alignedPawns) - score += RookOnPawn * popcount(alignedPawns); + score += RookOnPawn * popcount(alignedPawns); } // Bonus when on an open or semi-open file @@ -399,7 +399,7 @@ namespace { // the pawn shelter (current 'score' value). attackUnits = std::min(72, ei.kingAttackersCount[Them] * ei.kingAttackersWeight[Them]) + 9 * ei.kingAdjacentZoneAttacksCount[Them] - + 27 * popcount(undefended) + + 27 * popcount(undefended) + 11 * !!ei.pinnedPieces[Us] - 64 * !pos.count(Them) - mg_value(score) / 8; @@ -415,7 +415,7 @@ namespace { | ei.attackedBy[Them][KING]; if (b) - attackUnits += QueenContactCheck * popcount(b); + attackUnits += QueenContactCheck * popcount(b); } // Analyse the enemy's safe distance checks for sliders and knights @@ -513,7 +513,7 @@ namespace { b = weak & ~ei.attackedBy[Them][ALL_PIECES]; if (b) - score += Hanging * popcount(b); + score += Hanging * popcount(b); b = weak & ei.attackedBy[Us][KING]; if (b) @@ -533,7 +533,7 @@ namespace { & ~ei.attackedBy[Us][PAWN]; if (b) - score += ThreatByPawnPush * popcount(b); + score += ThreatByPawnPush * popcount(b); if (DoTrace) Trace::add(THREAT, Us, score); @@ -656,7 +656,7 @@ namespace { assert(unsigned(safe >> (Us == WHITE ? 32 : 0)) == 0); // ...count safe + (behind & safe) with a single popcount - int bonus = popcount((Us == WHITE ? safe << 32 : safe >> 32) | (behind & safe)); + int bonus = popcount((Us == WHITE ? safe << 32 : safe >> 32) | (behind & safe)); int weight = pos.count(Us) + pos.count(Us) + pos.count(Them) + pos.count(Them); diff --git a/src/pawns.cpp b/src/pawns.cpp index 9239bfac..5bf0e82e 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -22,7 +22,6 @@ #include #include "bitboard.h" -#include "bitcount.h" #include "pawns.h" #include "position.h" #include "thread.h" @@ -114,7 +113,7 @@ namespace { e->kingSquares[Us] = SQ_NONE; e->semiopenFiles[Us] = 0xFF; e->pawnAttacks[Us] = shift_bb(ourPawns) | shift_bb(ourPawns); - e->pawnsOnSquares[Us][BLACK] = popcount(ourPawns & DarkSquares); + e->pawnsOnSquares[Us][BLACK] = popcount(ourPawns & DarkSquares); e->pawnsOnSquares[Us][WHITE] = pos.count(Us) - e->pawnsOnSquares[Us][BLACK]; // Loop through all pawns of the current color and score each pawn @@ -233,7 +232,7 @@ Entry* probe(const Position& pos) { e->key = key; e->score = evaluate(pos, e) - evaluate(pos, e); - e->asymmetry = popcount(e->semiopenFiles[WHITE] ^ e->semiopenFiles[BLACK]); + e->asymmetry = popcount(e->semiopenFiles[WHITE] ^ e->semiopenFiles[BLACK]); return e; } diff --git a/src/position.cpp b/src/position.cpp index 0d563481..9b5ab923 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -24,7 +24,7 @@ #include #include -#include "bitcount.h" +#include "bitboard.h" #include "misc.h" #include "movegen.h" #include "position.h" @@ -1170,7 +1170,7 @@ bool Position::pos_is_ok(int* failedStep) const { for (Color c = WHITE; c <= BLACK; ++c) for (PieceType pt = PAWN; pt <= KING; ++pt) { - if (pieceCount[c][pt] != popcount(pieces(c, pt))) + if (pieceCount[c][pt] != popcount(pieces(c, pt))) return false; for (int i = 0; i < pieceCount[c][pt]; ++i) diff --git a/src/syzygy/tbprobe.cpp b/src/syzygy/tbprobe.cpp index 7bce67ea..14d34e79 100644 --- a/src/syzygy/tbprobe.cpp +++ b/src/syzygy/tbprobe.cpp @@ -15,7 +15,6 @@ #include "../movegen.h" #include "../bitboard.h" #include "../search.h" -#include "../bitcount.h" #include "tbprobe.h" #include "tbcore.h" @@ -39,12 +38,12 @@ static void prt_str(Position& pos, char *str, int mirror) color = !mirror ? WHITE : BLACK; for (pt = KING; pt >= PAWN; --pt) - for (i = popcount(pos.pieces(color, pt)); i > 0; i--) + for (i = popcount(pos.pieces(color, pt)); i > 0; i--) *str++ = pchr[6 - pt]; *str++ = 'v'; color = ~color; for (pt = KING; pt >= PAWN; --pt) - for (i = popcount(pos.pieces(color, pt)); i > 0; i--) + for (i = popcount(pos.pieces(color, pt)); i > 0; i--) *str++ = pchr[6 - pt]; *str++ = 0; } @@ -60,11 +59,11 @@ static uint64 calc_key(Position& pos, int mirror) color = !mirror ? WHITE : BLACK; for (pt = PAWN; pt <= KING; ++pt) - for (i = popcount(pos.pieces(color, pt)); i > 0; i--) + for (i = popcount(pos.pieces(color, pt)); i > 0; i--) key ^= Zobrist::psq[WHITE][pt][i - 1]; color = ~color; for (pt = PAWN; pt <= KING; ++pt) - for (i = popcount(pos.pieces(color, pt)); i > 0; i--) + for (i = popcount(pos.pieces(color, pt)); i > 0; i--) key ^= Zobrist::psq[BLACK][pt][i - 1]; return key;