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 ba1af2f2865f28865791178206add9752a392889..334ea879eabe6011eca8933780ce9d5763880306 100644 (file)
--- a/src/bitboard.cpp
+++ b/src/bitboard.cpp
@@ -21,9 +21,9 @@
 #include <algorithm>
 
 #include "bitboard.h"
 #include <algorithm>
 
 #include "bitboard.h"

-#include "bitcount.h"

 #include "misc.h"
 
 #include "misc.h"
 

+uint8_t PopCnt16[1 << 16];

 int SquareDistance[SQUARE_NB][SQUARE_NB];
 
 Bitboard  RookMasks  [SQUARE_NB];
 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;
   }
     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
 }
 
 #ifdef NO_BSF


@@ -141,6 +151,9 @@ const std::string Bitboards::pretty(Bitboard b) {
 
 void Bitboards::init() {
 
 
 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;
   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;
         // 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<Max15>(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[].
 
         // 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<Bitboard>();
         do {
             do
                 magics[s] = rng.sparse_rand<Bitboard>();

-            while (popcount<Max15>((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.
 
             // 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 77a824ba62106965ba9513803a19c650c092bb4c..21dc6e44087a36e5c527d0d9a15b78119aa48463 100644 (file)
--- 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__)
 /// 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 (file)
index 7609da4..0000000
--- 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 <http://www.gnu.org/licenses/>.
-*/
-
-#ifndef BITCOUNT_H_INCLUDED
-#define BITCOUNT_H_INCLUDED
-
-#include <cassert>
-
-#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<BitCountType> inline int popcount(Bitboard);
-
-template<>
-inline int popcount<CNT_64>(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<CNT_64_MAX15>(Bitboard b) {
-  b -=  (b >> 1) & 0x5555555555555555ULL;
-  b  = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);
-  return (b * 0x1111111111111111ULL) >> 60;
-}
-
-template<>
-inline int popcount<CNT_32>(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<CNT_32_MAX15>(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<CNT_HW_POPCNT>(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 30826dd786557ed5d546ba7b6d8d85ad09153db4..cc6630439cdfdd743a905563b43a9c720835a852 100644 (file)
--- a/src/endgame.cpp
+++ b/src/endgame.cpp
@@ -22,7 +22,6 @@
 #include <cassert>
 
 #include "bitboard.h"
 #include <cassert>
 
 #include "bitboard.h"

-#include "bitcount.h"

 #include "endgame.h"
 #include "movegen.h"
 
 #include "endgame.h"
 #include "movegen.h"
 

diff --git a/src/evaluate.cpp b/src/evaluate.cpp
index 6b329bb0def455471fcf6302f6ce5722de69215a..da4b9c30b41c3e9d3f4ac17641e7a8fcb3f28233 100644 (file)
--- a/src/evaluate.cpp
+++ b/src/evaluate.cpp
@@ -24,7 +24,7 @@
 #include <iomanip>
 #include <sstream>
 
 #include <iomanip>
 #include <sstream>
 

-#include "bitcount.h"
+#include "bitboard.h"

 #include "evaluate.h"
 #include "material.h"
 #include "pawns.h"
 #include "evaluate.h"
 #include "material.h"
 #include "pawns.h"


@@ -234,7 +234,7 @@ namespace {
     {
         ei.kingRing[Them] = b | shift_bb<Down>(b);
         b &= ei.attackedBy[Us][PAWN];
     {
         ei.kingRing[Them] = b | shift_bb<Down>(b);
         b &= ei.attackedBy[Us][PAWN];

-        ei.kingAttackersCount[Us] = b ? popcount<Max15>(b) : 0;
+        ei.kingAttackersCount[Us] = b ? popcount(b) : 0;

         ei.kingAdjacentZoneAttacksCount[Us] = ei.kingAttackersWeight[Us] = 0;
     }
     else
         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.kingAttackersWeight[Us] += KingAttackWeights[Pt];
             bb = b & ei.attackedBy[Them][KING];
             if (bb)

-                ei.kingAdjacentZoneAttacksCount[Us] += popcount<Max15>(bb);
+                ei.kingAdjacentZoneAttacksCount[Us] += popcount(bb);

         }
 
         if (Pt == QUEEN)
         }
 
         if (Pt == QUEEN)


@@ -286,7 +286,7 @@ namespace {
                    | ei.attackedBy[Them][BISHOP]
                    | ei.attackedBy[Them][ROOK]);
 
                    | ei.attackedBy[Them][BISHOP]
                    | ei.attackedBy[Them][ROOK]);
 

-        int mob = popcount<Pt == QUEEN ? Full : Max15>(b & mobilityArea[Us]);
+        int mob = popcount(b & mobilityArea[Us]);

 
         mobility[Us] += MobilityBonus[Pt][mob];
 
 
         mobility[Us] += MobilityBonus[Pt][mob];
 


@@ -334,7 +334,7 @@ namespace {
             {
                 Bitboard alignedPawns = pos.pieces(Them, PAWN) & PseudoAttacks[ROOK][s];
                 if (alignedPawns)
             {
                 Bitboard alignedPawns = pos.pieces(Them, PAWN) & PseudoAttacks[ROOK][s];
                 if (alignedPawns)

-                    score += RookOnPawn * popcount<Max15>(alignedPawns);
+                    score += RookOnPawn * popcount(alignedPawns);

             }
 
             // Bonus when on an open or semi-open file
             }
 
             // 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]
         // the pawn shelter (current 'score' value).
         attackUnits =  std::min(72, ei.kingAttackersCount[Them] * ei.kingAttackersWeight[Them])
                      +  9 * ei.kingAdjacentZoneAttacksCount[Them]

-                     + 27 * popcount<Max15>(undefended)
+                     + 27 * popcount(undefended)

                      + 11 * !!ei.pinnedPieces[Us]
                      - 64 * !pos.count<QUEEN>(Them)
                      - mg_value(score) / 8;
                      + 11 * !!ei.pinnedPieces[Us]
                      - 64 * !pos.count<QUEEN>(Them)
                      - mg_value(score) / 8;


@@ -415,7 +415,7 @@ namespace {
                 | ei.attackedBy[Them][KING];
 
             if (b)
                 | ei.attackedBy[Them][KING];
 
             if (b)

-                attackUnits += QueenContactCheck * popcount<Max15>(b);
+                attackUnits += QueenContactCheck * popcount(b);

         }
 
         // Analyse the enemy's safe distance checks for sliders and knights
         }
 
         // 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)
 
         b = weak & ~ei.attackedBy[Them][ALL_PIECES];
         if (b)

-            score += Hanging * popcount<Max15>(b);
+            score += Hanging * popcount(b);

 
         b = weak & ei.attackedBy[Us][KING];
         if (b)
 
         b = weak & ei.attackedBy[Us][KING];
         if (b)


@@ -533,7 +533,7 @@ namespace {
        & ~ei.attackedBy[Us][PAWN];
 
     if (b)
        & ~ei.attackedBy[Us][PAWN];
 
     if (b)

-        score += ThreatByPawnPush * popcount<Max15>(b);
+        score += ThreatByPawnPush * popcount(b);

 
     if (DoTrace)
         Trace::add(THREAT, Us, score);
 
     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
     assert(unsigned(safe >> (Us == WHITE ? 32 : 0)) == 0);
 
     // ...count safe + (behind & safe) with a single popcount

-    int bonus = popcount<Full>((Us == WHITE ? safe << 32 : safe >> 32) | (behind & safe));
+    int bonus = popcount((Us == WHITE ? safe << 32 : safe >> 32) | (behind & safe));

     int weight =  pos.count<KNIGHT>(Us) + pos.count<BISHOP>(Us)
                 + pos.count<KNIGHT>(Them) + pos.count<BISHOP>(Them);
 
     int weight =  pos.count<KNIGHT>(Us) + pos.count<BISHOP>(Us)
                 + pos.count<KNIGHT>(Them) + pos.count<BISHOP>(Them);
 

diff --git a/src/pawns.cpp b/src/pawns.cpp
index 9239bface2e06c163b6daa521e9ba8fe3f6a9bd5..5bf0e82ea98434aee57b171d5604b9ddf3055781 100644 (file)
--- a/src/pawns.cpp
+++ b/src/pawns.cpp
@@ -22,7 +22,6 @@
 #include <cassert>
 
 #include "bitboard.h"
 #include <cassert>
 
 #include "bitboard.h"

-#include "bitcount.h"

 #include "pawns.h"
 #include "position.h"
 #include "thread.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<Right>(ourPawns) | shift_bb<Left>(ourPawns);
     e->kingSquares[Us] = SQ_NONE;
     e->semiopenFiles[Us] = 0xFF;
     e->pawnAttacks[Us] = shift_bb<Right>(ourPawns) | shift_bb<Left>(ourPawns);

-    e->pawnsOnSquares[Us][BLACK] = popcount<Max15>(ourPawns & DarkSquares);
+    e->pawnsOnSquares[Us][BLACK] = popcount(ourPawns & DarkSquares);

     e->pawnsOnSquares[Us][WHITE] = pos.count<PAWN>(Us) - e->pawnsOnSquares[Us][BLACK];
 
     // Loop through all pawns of the current color and score each pawn
     e->pawnsOnSquares[Us][WHITE] = pos.count<PAWN>(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<WHITE>(pos, e) - evaluate<BLACK>(pos, e);
 
   e->key = key;
   e->score = evaluate<WHITE>(pos, e) - evaluate<BLACK>(pos, e);

-  e->asymmetry = popcount<Max15>(e->semiopenFiles[WHITE] ^ e->semiopenFiles[BLACK]);
+  e->asymmetry = popcount(e->semiopenFiles[WHITE] ^ e->semiopenFiles[BLACK]);

   return e;
 }
 
   return e;
 }
 

diff --git a/src/position.cpp b/src/position.cpp
index 0d563481c671529dee1474c765172f31fa97a1fc..9b5ab9234e8c506eb1e50446ba32faead5e37e7e 100644 (file)
--- a/src/position.cpp
+++ b/src/position.cpp
@@ -24,7 +24,7 @@
 #include <iomanip>
 #include <sstream>
 
 #include <iomanip>
 #include <sstream>
 

-#include "bitcount.h"
+#include "bitboard.h"

 #include "misc.h"
 #include "movegen.h"
 #include "position.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)
               {
           for (Color c = WHITE; c <= BLACK; ++c)
               for (PieceType pt = PAWN; pt <= KING; ++pt)
               {

-                  if (pieceCount[c][pt] != popcount<Full>(pieces(c, pt)))
+                  if (pieceCount[c][pt] != popcount(pieces(c, pt)))

                       return false;
 
                   for (int i = 0; i < pieceCount[c][pt];  ++i)
                       return false;
 
                   for (int i = 0; i < pieceCount[c][pt];  ++i)

diff --git a/src/syzygy/tbprobe.cpp b/src/syzygy/tbprobe.cpp
index 7bce67eabea8d1cb5e9d1632ae31de46b688bd5b..14d34e79b097af0ac406d822f5dbe1006e245ff3 100644 (file)
--- a/src/syzygy/tbprobe.cpp
+++ b/src/syzygy/tbprobe.cpp
@@ -15,7 +15,6 @@
 #include "../movegen.h"
 #include "../bitboard.h"
 #include "../search.h"
 #include "../movegen.h"
 #include "../bitboard.h"
 #include "../search.h"

-#include "../bitcount.h"

 
 #include "tbprobe.h"
 #include "tbcore.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)
 
   color = !mirror ? WHITE : BLACK;
   for (pt = KING; pt >= PAWN; --pt)

-    for (i = popcount<Max15>(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)
       *str++ = pchr[6 - pt];
   *str++ = 'v';
   color = ~color;
   for (pt = KING; pt >= PAWN; --pt)

-    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)
+    for (i = popcount(pos.pieces(color, pt)); i > 0; i--)

       *str++ = pchr[6 - pt];
   *str++ = 0;
 }
       *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)
 
   color = !mirror ? WHITE : BLACK;
   for (pt = PAWN; pt <= KING; ++pt)

-    for (i = popcount<Max15>(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)
       key ^= Zobrist::psq[WHITE][pt][i - 1];
   color = ~color;
   for (pt = PAWN; pt <= KING; ++pt)

-    for (i = popcount<Max15>(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;
       key ^= Zobrist::psq[BLACK][pt][i - 1];
 
   return key;