From 3376c68f4bb83dc9fd874eb9d710dab09609ae54 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Thu, 21 May 2009 15:29:28 +0200 Subject: [PATCH] Introduce bitcount.h It will be used for POPCNT intrinsics. For now no bianry and functional change. Signed-off-by: Marco Costalba --- src/bitboard.cpp | 3 +- src/bitboard.h | 65 ------------------- src/bitcount.h | 162 +++++++++++++++++++++++++++++++++++++++++++++++ src/endgame.cpp | 3 +- src/evaluate.cpp | 37 +++++------ src/main.cpp | 2 +- src/pawns.cpp | 5 +- src/position.cpp | 5 +- 8 files changed, 192 insertions(+), 90 deletions(-) create mode 100644 src/bitcount.h diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 474e321c..f7a6ba27 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -35,6 +35,7 @@ #include #include "bitboard.h" +#include "bitcount.h" #include "direction.h" @@ -460,7 +461,7 @@ namespace { Bitboard index_to_bitboard(int index, Bitboard mask) { - int i, j, bits = count_1s(mask); + int i, j, bits = count_1s(mask); Bitboard result = 0ULL; for(i = 0; i < bits; i++) { j = pop_1st_bit(&mask); diff --git a/src/bitboard.h b/src/bitboard.h index d3a4ae53..54ed5053 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -22,7 +22,6 @@ #if !defined(BITBOARD_H_INCLUDED) #define BITBOARD_H_INCLUDED - //// //// Defines //// @@ -47,15 +46,10 @@ //#define USE_32BIT_ATTACKS #define USE_FOLDED_BITSCAN -#define BITCOUNT_SWAR_64 -//#define BITCOUNT_SWAR_32 -//#define BITCOUNT_LOOP - #else #define USE_32BIT_ATTACKS #define USE_FOLDED_BITSCAN -#define BITCOUNT_SWAR_32 #endif @@ -429,65 +423,6 @@ inline Bitboard isolated_pawn_mask(Square s) { } -/// count_1s() counts the number of nonzero bits in a bitboard. - -#if defined(BITCOUNT_LOOP) - -inline int count_1s(Bitboard b) { - int r; - for(r = 0; b; r++, b &= b - 1); - return r; -} - -inline int count_1s_max_15(Bitboard b) { - return count_1s(b); -} - -#elif defined(BITCOUNT_SWAR_32) - -inline int count_1s(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) & 0x0F0F0F0F; // 0-8 in 8 bits - v += (((w >> 4) + w) & 0x0F0F0F0F); // 0-16 in 8 bits - v *= 0x01010101; // mul is fast on amd procs - return int(v >> 24); -} - -inline int count_1s_max_15(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 += w; // 0-8 in 4 bits - v *= 0x11111111; - return int(v >> 28); -} - -#elif defined(BITCOUNT_SWAR_64) - -inline int count_1s(Bitboard b) { - b -= ((b>>1) & 0x5555555555555555ULL); - b = ((b>>2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL); - b = ((b>>4) + b) & 0x0F0F0F0F0F0F0F0FULL; - b *= 0x0101010101010101ULL; - return int(b >> 56); -} - -inline int count_1s_max_15(Bitboard b) { - b -= (b>>1) & 0x5555555555555555ULL; - b = ((b>>2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL); - b *= 0x1111111111111111ULL; - return int(b >> 60); -} - -#endif // BITCOUNT - - //// //// Prototypes //// diff --git a/src/bitcount.h b/src/bitcount.h new file mode 100644 index 00000000..12826a9f --- /dev/null +++ b/src/bitcount.h @@ -0,0 +1,162 @@ +/* + Stockfish, a UCI chess playing engine derived from Glaurung 2.1 + Copyright (C) 2004-2008 Tord Romstad (Glaurung author) + Copyright (C) 2008-2009 Marco Costalba + + 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 . +*/ + + +#if !defined(BITCOUNT_H_INCLUDED) +#define BITCOUNT_H_INCLUDED + +#include "bitboard.h" + + +// Select type of software bit count function to use + +#if !defined(AUTO_CONFIGURATION) || defined(IS_64BIT) + +//#define USE_COMPACT_ROOK_ATTACKS +//#define USE_32BIT_ATTACKS +#define USE_FOLDED_BITSCAN + +#define BITCOUNT_SWAR_64 +//#define BITCOUNT_SWAR_32 +//#define BITCOUNT_LOOP + +#else + +#define USE_32BIT_ATTACKS +#define USE_FOLDED_BITSCAN +#define BITCOUNT_SWAR_32 + +#endif + + +// Select type of intrinsic bit count instruction to use + +#if defined(_MSC_VER) // Microsoft compiler + +#include + +inline bool cpu_has_popcnt() { + + int CPUInfo[4] = {-1}; + __cpuid(CPUInfo, 0x00000001); + return (CPUInfo[2] >> 23) & 1; +} + +#define POPCNT_INTRINSIC(x) __popcnt64(x) + +#elif defined(__INTEL_COMPILER) && (defined(__x86_64) || defined(_M_X64)) // Intel compiler + +#include + +inline bool cpu_has_popcnt() { + + int CPUInfo[4] = {-1}; + __cpuid(CPUInfo, 0x00000001); + return (CPUInfo[2] >> 23) & 1; +} + +#define POPCNT_INTRINSIC(x) _mm_popcnt_u64(x) + +#else // Safe fallback for unsupported compilers + +inline bool cpu_has_popcnt() { return false; } + +#define POPCNT_INTRINSIC(x) sw_count_1s(x) + +#endif + + +/// Software implementation of bit count functions + +#if defined(BITCOUNT_LOOP) + +inline int sw_count_1s(Bitboard b) { + int r; + for(r = 0; b; r++, b &= b - 1); + return r; +} + +inline int sw_count_1s_max_15(Bitboard b) { + return count_1s(b); +} + +#elif defined(BITCOUNT_SWAR_32) + +inline int sw_count_1s(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) & 0x0F0F0F0F; // 0-8 in 8 bits + v += (((w >> 4) + w) & 0x0F0F0F0F); // 0-16 in 8 bits + v *= 0x01010101; // mul is fast on amd procs + return int(v >> 24); +} + +inline int sw_count_1s_max_15(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 += w; // 0-8 in 4 bits + v *= 0x11111111; + return int(v >> 28); +} + +#elif defined(BITCOUNT_SWAR_64) + +inline int sw_count_1s(Bitboard b) { + b -= ((b>>1) & 0x5555555555555555ULL); + b = ((b>>2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL); + b = ((b>>4) + b) & 0x0F0F0F0F0F0F0F0FULL; + b *= 0x0101010101010101ULL; + return int(b >> 56); +} + +inline int sw_count_1s_max_15(Bitboard b) { + b -= (b>>1) & 0x5555555555555555ULL; + b = ((b>>2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL); + b *= 0x1111111111111111ULL; + return int(b >> 60); +} + +#endif // BITCOUNT + + +/// count_1s() counts the number of nonzero bits in a bitboard. +/// If template parameter is true an intrinsic is called, otherwise +/// we fallback on a software implementation. + +template +inline int count_1s(Bitboard b) { + + return UseIntrinsic ? POPCNT_INTRINSIC(b) : sw_count_1s(b); +} + +template +inline int count_1s_max_15(Bitboard b) { + + return UseIntrinsic ? POPCNT_INTRINSIC(b) : sw_count_1s_max_15(b); +} + + +#endif // !defined(BITCOUNT_H_INCLUDED) diff --git a/src/endgame.cpp b/src/endgame.cpp index 3f3bdcce..90898e83 100644 --- a/src/endgame.cpp +++ b/src/endgame.cpp @@ -25,6 +25,7 @@ #include #include "bitbase.h" +#include "bitcount.h" #include "endgame.h" @@ -377,7 +378,7 @@ Value EvaluationFunction::apply(const Position& pos) { result += Value(square_distance(bksq, nsq) * 32); // Bonus for restricting the knight's mobility - result += Value((8 - count_1s_max_15(pos.piece_attacks(nsq))) * 8); + result += Value((8 - count_1s_max_15(pos.piece_attacks(nsq))) * 8); return (strongerSide == pos.side_to_move() ? result : -result); } diff --git a/src/evaluate.cpp b/src/evaluate.cpp index c0b4866b..35922281 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -25,6 +25,7 @@ #include #include +#include "bitcount.h" #include "evaluate.h" #include "material.h" #include "pawns.h" @@ -339,8 +340,8 @@ Value evaluate(const Position &pos, EvalInfo &ei, int threadID) { // Initialize pawn attack bitboards for both sides ei.attackedBy[WHITE][PAWN] = ((pos.pawns(WHITE) << 9) & ~FileABB) | ((pos.pawns(WHITE) << 7) & ~FileHBB); ei.attackedBy[BLACK][PAWN] = ((pos.pawns(BLACK) >> 7) & ~FileABB) | ((pos.pawns(BLACK) >> 9) & ~FileHBB); - ei.kingAttackersCount[WHITE] = count_1s_max_15(ei.attackedBy[WHITE][PAWN] & ei.attackedBy[BLACK][KING])/2; - ei.kingAttackersCount[BLACK] = count_1s_max_15(ei.attackedBy[BLACK][PAWN] & ei.attackedBy[WHITE][KING])/2; + ei.kingAttackersCount[WHITE] = count_1s_max_15(ei.attackedBy[WHITE][PAWN] & ei.attackedBy[BLACK][KING])/2; + ei.kingAttackersCount[BLACK] = count_1s_max_15(ei.attackedBy[BLACK][PAWN] & ei.attackedBy[WHITE][KING])/2; // Evaluate pieces for (Color c = WHITE; c <= BLACK; c++) @@ -481,8 +482,8 @@ void init_eval(int threads) { for (Bitboard b = 0ULL; b < 256ULL; b++) { - assert(count_1s(b) == int(uint8_t(count_1s(b)))); - BitCount8Bit[b] = (uint8_t)count_1s(b); + assert(count_1s(b) == int(uint8_t(count_1s(b)))); + BitCount8Bit[b] = (uint8_t)count_1s(b); } } @@ -547,15 +548,15 @@ namespace { ei.kingAttackersWeight[us] += AttackWeight[Piece]; Bitboard bb = (b & ei.attackedBy[them][KING]); if (bb) - ei.kingAdjacentZoneAttacksCount[us] += count_1s_max_15(bb); + ei.kingAdjacentZoneAttacksCount[us] += count_1s_max_15(bb); } // Remove squares protected by enemy pawns Bitboard bb = (b & ~ei.attackedBy[them][PAWN]); // Mobility - int mob = (Piece != QUEEN ? count_1s_max_15(bb & ~p.pieces_of_color(us)) - : count_1s(bb & ~p.pieces_of_color(us))); + int mob = (Piece != QUEEN ? count_1s_max_15(bb & ~p.pieces_of_color(us)) + : count_1s(bb & ~p.pieces_of_color(us))); ei.mgMobility += Sign[us] * MgBonus[Piece][mob]; ei.egMobility += Sign[us] * EgBonus[Piece][mob]; @@ -744,7 +745,7 @@ namespace { // quality of the pawn shelter. int attackUnits = Min((ei.kingAttackersCount[them] * ei.kingAttackersWeight[them]) / 2, 25) - + (ei.kingAdjacentZoneAttacksCount[them] + count_1s_max_15(undefended)) * 3 + + (ei.kingAdjacentZoneAttacksCount[them] + count_1s_max_15(undefended)) * 3 + InitKingDanger[relative_square(us, s)] - (shelter >> 5); // Analyse safe queen contact checks @@ -760,7 +761,7 @@ namespace { { // The bitboard b now contains the squares available for safe queen // contact checks. - int count = count_1s_max_15(b); + int count = count_1s_max_15(b); attackUnits += QueenContactCheckBonus * count * (sente ? 2 : 1); // Is there a mate threat? @@ -800,12 +801,12 @@ namespace { // Queen checks b2 = b & ei.attacked_by(them, QUEEN); if( b2) - attackUnits += QueenCheckBonus * count_1s_max_15(b2); + attackUnits += QueenCheckBonus * count_1s_max_15(b2); // Rook checks b2 = b & ei.attacked_by(them, ROOK); if (b2) - attackUnits += RookCheckBonus * count_1s_max_15(b2); + attackUnits += RookCheckBonus * count_1s_max_15(b2); } if (QueenCheckBonus > 0 || BishopCheckBonus > 0) { @@ -814,12 +815,12 @@ namespace { // Queen checks b2 = b & ei.attacked_by(them, QUEEN); if (b2) - attackUnits += QueenCheckBonus * count_1s_max_15(b2); + attackUnits += QueenCheckBonus * count_1s_max_15(b2); // Bishop checks b2 = b & ei.attacked_by(them, BISHOP); if (b2) - attackUnits += BishopCheckBonus * count_1s_max_15(b2); + attackUnits += BishopCheckBonus * count_1s_max_15(b2); } if (KnightCheckBonus > 0) { @@ -828,7 +829,7 @@ namespace { // Knight checks b2 = b & ei.attacked_by(them, KNIGHT); if (b2) - attackUnits += KnightCheckBonus * count_1s_max_15(b2); + attackUnits += KnightCheckBonus * count_1s_max_15(b2); } // Analyse discovered checks (only for non-pawns right now, consider @@ -837,7 +838,7 @@ namespace { { b = p.discovered_check_candidates(them) & ~p.pawns(); if (b) - attackUnits += DiscoveredCheckBonus * count_1s_max_15(b) * (sente? 2 : 1); + attackUnits += DiscoveredCheckBonus * count_1s_max_15(b) * (sente? 2 : 1); } // Has a mate threat been found? We don't do anything here if the @@ -972,7 +973,7 @@ namespace { if (d < 0) { int mtg = RANK_8 - relative_rank(us, s); - int blockerCount = count_1s_max_15(squares_in_front_of(us,s) & pos.occupied_squares()); + int blockerCount = count_1s_max_15(squares_in_front_of(us,s) & pos.occupied_squares()); mtg += blockerCount; d += blockerCount; if (d < 0) @@ -1133,8 +1134,8 @@ namespace { behindFriendlyPawns |= (behindFriendlyPawns << 16); } - int space = count_1s_max_15(safeSquares) - + count_1s_max_15(behindFriendlyPawns & safeSquares); + int space = count_1s_max_15(safeSquares) + + count_1s_max_15(behindFriendlyPawns & safeSquares); ei.mgValue += Sign[us] * apply_weight(Value(space * ei.mi->space_weight()), WeightSpace); } diff --git a/src/main.cpp b/src/main.cpp index e009fd96..91986206 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -18,7 +18,7 @@ */ // To profile with callgrind uncomment following line -//#define USE_CALLGRIND +#define USE_CALLGRIND //// diff --git a/src/pawns.cpp b/src/pawns.cpp index 3cfe3750..08b0e7ba 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -25,6 +25,7 @@ #include #include +#include "bitcount.h" #include "pawns.h" #include "position.h" @@ -329,8 +330,8 @@ PawnInfo *PawnInfoTable::get_pawn_info(const Position &pos) { // Test for candidate passed pawn candidate = !passed && pos.file_is_half_open(them, f) - && ( count_1s_max_15(neighboring_files_bb(f) & (behind_bb(us, r) | rank_bb(r)) & ourPawns) - - count_1s_max_15(neighboring_files_bb(f) & in_front_bb(us, r) & theirPawns) + && ( count_1s_max_15(neighboring_files_bb(f) & (behind_bb(us, r) | rank_bb(r)) & ourPawns) + - count_1s_max_15(neighboring_files_bb(f) & in_front_bb(us, r) & theirPawns) >= 0); // In order to prevent doubled passed pawns from receiving a too big diff --git a/src/position.cpp b/src/position.cpp index f4752c5e..6e6bf38b 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -27,6 +27,7 @@ #include #include +#include "bitcount.h" #include "mersenne.h" #include "movegen.h" #include "movepick.h" @@ -2090,7 +2091,7 @@ bool Position::is_ok(int* failedStep) const { // Is there more than 2 checkers? if (failedStep) (*failedStep)++; - if (debugCheckerCount && count_1s(st->checkersBB) > 2) + if (debugCheckerCount && count_1s(st->checkersBB) > 2) return false; // Bitboards OK? @@ -2165,7 +2166,7 @@ bool Position::is_ok(int* failedStep) const { if (debugPieceCounts) for (Color c = WHITE; c <= BLACK; c++) for (PieceType pt = PAWN; pt <= KING; pt++) - if (pieceCount[c][pt] != count_1s(pieces_of_color_and_type(c, pt))) + if (pieceCount[c][pt] != count_1s(pieces_of_color_and_type(c, pt))) return false; if (failedStep) (*failedStep)++; -- 2.39.2