Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 96 | pmbaty | 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 |