Subversion Repositories Games.Chess Giants

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.   Stockfish, a UCI chess playing engine derived from Glaurung 2.1
  3.   Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
  4.   Copyright (C) 2008-2015 Marco Costalba, Joona Kiiski, Tord Romstad
  5.   Copyright (C) 2015-2016 Marco Costalba, Joona Kiiski, Gary Linscott, Tord Romstad
  6.  
  7.   Stockfish is free software: you can redistribute it and/or modify
  8.   it under the terms of the GNU General Public License as published by
  9.   the Free Software Foundation, either version 3 of the License, or
  10.   (at your option) any later version.
  11.  
  12.   Stockfish is distributed in the hope that it will be useful,
  13.   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.   GNU General Public License for more details.
  16.  
  17.   You should have received a copy of the GNU General Public License
  18.   along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19. */
  20.  
  21. #ifndef BITCOUNT_H_INCLUDED
  22. #define BITCOUNT_H_INCLUDED
  23.  
  24. #include <cassert>
  25.  
  26. #include "types.h"
  27.  
  28. enum BitCountType {
  29.   CNT_64,
  30.   CNT_64_MAX15,
  31.   CNT_32,
  32.   CNT_32_MAX15,
  33.   CNT_HW_POPCNT
  34. };
  35.  
  36. /// Determine at compile time the best popcount<> specialization according to
  37. /// whether the platform is 32 or 64 bit, the maximum number of non-zero
  38. /// bits to count and if the hardware popcnt instruction is available.
  39. const BitCountType Full  = HasPopCnt ? CNT_HW_POPCNT : Is64Bit ? CNT_64       : CNT_32;
  40. const BitCountType Max15 = HasPopCnt ? CNT_HW_POPCNT : Is64Bit ? CNT_64_MAX15 : CNT_32_MAX15;
  41.  
  42.  
  43. /// popcount() counts the number of non-zero bits in a bitboard
  44. template<BitCountType> inline int popcount(Bitboard);
  45.  
  46. template<>
  47. inline int popcount<CNT_64>(Bitboard b) {
  48.   b -=  (b >> 1) & 0x5555555555555555ULL;
  49.   b  = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);
  50.   b  = ((b >> 4) + b) & 0x0F0F0F0F0F0F0F0FULL;
  51.   return (b * 0x0101010101010101ULL) >> 56;
  52. }
  53.  
  54. template<>
  55. inline int popcount<CNT_64_MAX15>(Bitboard b) {
  56.   b -=  (b >> 1) & 0x5555555555555555ULL;
  57.   b  = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);
  58.   return (b * 0x1111111111111111ULL) >> 60;
  59. }
  60.  
  61. template<>
  62. inline int popcount<CNT_32>(Bitboard b) {
  63.   unsigned w = unsigned(b >> 32), v = unsigned(b);
  64.   v -=  (v >> 1) & 0x55555555; // 0-2 in 2 bits
  65.   w -=  (w >> 1) & 0x55555555;
  66.   v  = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits
  67.   w  = ((w >> 2) & 0x33333333) + (w & 0x33333333);
  68.   v  = ((v >> 4) + v + (w >> 4) + w) & 0x0F0F0F0F;
  69.   return (v * 0x01010101) >> 24;
  70. }
  71.  
  72. template<>
  73. inline int popcount<CNT_32_MAX15>(Bitboard b) {
  74.   unsigned w = unsigned(b >> 32), v = unsigned(b);
  75.   v -=  (v >> 1) & 0x55555555; // 0-2 in 2 bits
  76.   w -=  (w >> 1) & 0x55555555;
  77.   v  = ((v >> 2) & 0x33333333) + (v & 0x33333333); // 0-4 in 4 bits
  78.   w  = ((w >> 2) & 0x33333333) + (w & 0x33333333);
  79.   return ((v + w) * 0x11111111) >> 28;
  80. }
  81.  
  82. template<>
  83. inline int popcount<CNT_HW_POPCNT>(Bitboard b) {
  84.  
  85. #ifndef USE_POPCNT
  86.  
  87.   assert(false);
  88.   return b != 0; // Avoid 'b not used' warning
  89.  
  90. #elif defined(_MSC_VER) && defined(__INTEL_COMPILER)
  91.  
  92.   return _mm_popcnt_u64(b);
  93.  
  94. #elif defined(_MSC_VER)
  95.  
  96.   return (int)__popcnt64(b);
  97.  
  98. #else // Assumed gcc or compatible compiler
  99.  
  100.   return __builtin_popcountll(b);
  101.  
  102. #endif
  103. }
  104.  
  105. #endif // #ifndef BITCOUNT_H_INCLUDED
  106.