Simplify popcnt

[stockfish] / src / bitboard.cpp

diff --git a/src/bitboard.cpp b/src/bitboard.cpp
index e0533bc9cc286280c61432c455adf41ee3695ebe..334ea879eabe6011eca8933780ce9d5763880306 100644 (file)
--- a/src/bitboard.cpp
+++ b/src/bitboard.cpp
@@ -2,6 +2,7 @@
   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
@@ -18,12 +19,11 @@
 */
 
 #include <algorithm>
-#include <cstring>   // For std::memset
 
 #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,18 +74,30 @@ 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;
+  }
 }
 
-#ifndef USE_BSFQ
+#ifdef NO_BSF
 
 /// Software fall-back of lsb() and msb() for CPU lacking hardware support
 
 Square lsb(Bitboard b) {
+  assert(b);
   return BSFTable[bsf_index(b)];
 }
 
 Square msb(Bitboard b) {
 
+  assert(b);
   unsigned b32;
   int result = 0;
 
@@ -112,7 +124,7 @@ Square msb(Bitboard b) {
   return Square(result + MSBTable[b32]);
 }
 
-#endif // ifndef USE_BSFQ
+#endif // ifdef NO_BSF
 
 
 /// Bitboards::pretty() returns an ASCII representation of a bitboard suitable
@@ -139,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;
@@ -247,9 +262,7 @@ namespace {
                              {  728, 10316, 55013, 32803, 12281, 15100,  16645,   255 } };
 
     Bitboard occupancy[4096], reference[4096], edges, b;
-    int age[4096], current = 0, i, size;
-
-    std::memset(age, 0, sizeof(age));
+    int age[4096] = {0}, current = 0, i, size;
 
     // attacks[s] is a pointer to the beginning of the attacks table for square 's'
     attacks[SQ_A1] = table;
@@ -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<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[].
@@ -296,7 +309,7 @@ namespace {
         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.