From 5d79af9e0d466572217dc47f5c307f6fd382a646 Mon Sep 17 00:00:00 2001 From: Marco Costalba Date: Fri, 3 Jul 2009 08:40:41 +0100 Subject: [PATCH] Restore correct 64 bit version of pop_1st_bit() Was erroneusly changed with the 32bit in recent patch "Retire USE_COMPACT_ROOK_ATTACKS...". Also another clean up of define magics. Move compiler specific definitions in types.h and remove redundant cruft. Now this macro ugly mess seems more reasonable. No functional change. Signed-off-by: Marco Costalba --- src/bitboard.cpp | 30 ++++++++++++++++++++--- src/bitboard.h | 40 +------------------------------ src/bitcount.h | 62 +++++++++++------------------------------------- src/types.h | 24 ++++++++++++++++++- 4 files changed, 65 insertions(+), 91 deletions(-) diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 0bdb9d3a..4a7a0af2 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -242,20 +242,44 @@ void init_bitboards() { } +/// first_1() finds the least significant nonzero bit in a nonzero bitboard. /// pop_1st_bit() finds and clears the least significant nonzero bit in a /// nonzero bitboard. #if defined(IS_64BIT) && !defined(USE_BSFQ) +static const int BitTable[64] = { + 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, + 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, + 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, + 51, 60, 42, 59, 58 +}; + +Square first_1(Bitboard b) { + return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]); +} + Square pop_1st_bit(Bitboard* b) { - Bitboard bb = *b ^ (*b - 1); - uint32_t fold = int(bb) ^ int(bb >> 32); + Bitboard bb = *b; *b &= (*b - 1); - return Square(BitTable[(fold * 0x783a9b23) >> 26]); + return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]); } #elif !defined(USE_BSFQ) +static const int BitTable[64] = { + 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2, + 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52, + 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28, + 58, 20, 37, 17, 36, 8 +}; + +Square first_1(Bitboard b) { + b ^= (b - 1); + uint32_t fold = int(b) ^ int(b >> 32); + return Square(BitTable[(fold * 0x783a9b23) >> 26]); +} + // Use type-punning union b_union { diff --git a/src/bitboard.h b/src/bitboard.h index d5c16a91..0064fb26 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -22,25 +22,6 @@ #if !defined(BITBOARD_H_INCLUDED) #define BITBOARD_H_INCLUDED -//// -//// Defines -//// - -// Quiet a warning on Intel compiler -#if !defined(__SIZEOF_INT__ ) -#define __SIZEOF_INT__ 0 -#endif - -// Check for 64 bits for different compilers: Intel, MSVC and gcc -#if defined(__x86_64) || defined(_WIN64) || (__SIZEOF_INT__ > 4) -#define IS_64BIT -#endif - -#if defined(IS_64BIT) && (defined(__GNUC__) || defined(__INTEL_COMPILER)) -#define USE_BSFQ -#endif - - //// //// Includes //// @@ -51,13 +32,6 @@ #include "types.h" -//// -//// Types -//// - -typedef uint64_t Bitboard; - - //// //// Constants and variables //// @@ -132,13 +106,6 @@ const Bitboard InFrontBB[2][8] = { } }; -const int BitTable[64] = { - 63, 30, 3, 32, 25, 41, 22, 33, 15, 50, 42, 13, 11, 53, 19, 34, 61, 29, 2, - 51, 21, 43, 45, 10, 18, 47, 1, 54, 9, 57, 0, 35, 62, 31, 40, 4, 49, 5, 52, - 26, 60, 6, 23, 44, 46, 27, 56, 16, 7, 39, 48, 24, 59, 14, 12, 55, 38, 28, - 58, 20, 37, 17, 36, 8 -}; - extern Bitboard SetMaskBB[65]; extern Bitboard ClearMaskBB[65]; @@ -407,12 +374,7 @@ inline Square __attribute__((always_inline)) pop_1st_bit(Bitboard* b) { #else // if !defined(USE_BSFQ) -inline Square first_1(Bitboard b) { - b ^= (b - 1); - uint32_t fold = int(b) ^ int(b >> 32); - return Square(BitTable[(fold * 0x783a9b23) >> 26]); -} - +extern Square first_1(Bitboard b); extern Square pop_1st_bit(Bitboard* b); #endif diff --git a/src/bitcount.h b/src/bitcount.h index d57b3f40..4747afc6 100644 --- a/src/bitcount.h +++ b/src/bitcount.h @@ -28,29 +28,7 @@ //#define DISABLE_POPCNT_SUPPORT -#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 - +#include "types.h" // Select type of intrinsic bit count instruction to use @@ -86,24 +64,29 @@ inline bool cpu_has_popcnt() { return false; } #define POPCNT_INTRINSIC(x) count_1s(x) -#endif +#endif // cpu_has_popcnt() selection /// Software implementation of bit count functions -#if defined(BITCOUNT_LOOP) +#if defined(IS_64BIT) inline int count_1s(Bitboard b) { - int r; - for(r = 0; b; r++, b &= b - 1); - return r; + 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) { - return count_1s(b); + b -= (b>>1) & 0x5555555555555555ULL; + b = ((b>>2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL); + b *= 0x1111111111111111ULL; + return int(b >> 60); } -#elif defined(BITCOUNT_SWAR_32) +#else // if !defined(IS_64BIT) inline int count_1s(Bitboard b) { unsigned w = unsigned(b >> 32), v = unsigned(b); @@ -128,23 +111,6 @@ inline int count_1s_max_15(Bitboard b) { 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 @@ -177,7 +143,7 @@ const bool CpuHasPOPCNT = cpu_has_popcnt(); // Global variable used to print info about the use of 64 optimized // functions to verify that a 64bit compile has been correctly built. -#if defined(BITCOUNT_SWAR_64) +#if defined(IS_64BIT) const bool CpuHas64BitPath = true; #else const bool CpuHas64BitPath = false; diff --git a/src/types.h b/src/types.h index 396942cd..577f97d7 100644 --- a/src/types.h +++ b/src/types.h @@ -41,7 +41,29 @@ typedef __int64 int64_t; #endif // !defined(_MSC_VER) -// Hash keys: +// Hash keys typedef uint64_t Key; +// Bitboard type +typedef uint64_t Bitboard; + + +//// +//// Compiler specific defines +//// + +// Quiet a warning on Intel compiler +#if !defined(__SIZEOF_INT__ ) +#define __SIZEOF_INT__ 0 +#endif + +// Check for 64 bits for different compilers: Intel, MSVC and gcc +#if defined(__x86_64) || defined(_WIN64) || (__SIZEOF_INT__ > 4) +#define IS_64BIT +#endif + +#if defined(IS_64BIT) && (defined(__GNUC__) || defined(__INTEL_COMPILER)) +#define USE_BSFQ +#endif + #endif // !defined(TYPES_H_INCLUDED) -- 2.39.2