From: Marco Costalba Date: Sun, 8 Jul 2012 07:30:37 +0000 (+0100) Subject: Rename first_1 / last_1 in lsb / msb X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=6b5322ce000d6a8a6f845beda2d7e149e1baea0c Rename first_1 / last_1 in lsb / msb It seems more accurate: lsb is clear while 'first bit' depends from where you look at the bitboard. And fix compile in case of 64 bits platforms that do not use BSFQ intrinsics. No functional change. Signed-off-by: Marco Costalba --- diff --git a/src/bitbase.cpp b/src/bitbase.cpp index 9322e537..9d2cde03 100644 --- a/src/bitbase.cpp +++ b/src/bitbase.cpp @@ -196,8 +196,8 @@ namespace { while (b) { - r |= Us == WHITE ? db[index(pop_1st_bit(&b), bksq, psq, BLACK)] - : db[index(wksq, pop_1st_bit(&b), psq, WHITE)]; + r |= Us == WHITE ? db[index(pop_lsb(&b), bksq, psq, BLACK)] + : db[index(wksq, pop_lsb(&b), psq, WHITE)]; if (Us == WHITE && (r & WIN)) return WIN; diff --git a/src/bitboard.cpp b/src/bitboard.cpp index 08b43ad8..945169c3 100644 --- a/src/bitboard.cpp +++ b/src/bitboard.cpp @@ -69,40 +69,35 @@ namespace { Bitboard masks[], unsigned shifts[], Square deltas[], Fn index); } -/// 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. +/// lsb()/msb() finds the least/most significant bit in a nonzero bitboard. +/// pop_lsb() finds and clears the least significant bit in a nonzero bitboard. -#if defined(IS_64BIT) && !defined(USE_BSFQ) +#if !defined(USE_BSFQ) -Square first_1(Bitboard b) { - return Square(BSFTable[((b & -b) * 0x218A392CD3D5DBFULL) >> 58]); -} - -Square pop_1st_bit(Bitboard* b) { - Bitboard bb = *b; - *b &= (*b - 1); - return Square(BSFTable[((bb & -bb) * 0x218A392CD3D5DBFULL) >> 58]); -} +Square lsb(Bitboard b) { -#elif !defined(USE_BSFQ) + if (Is64Bit) + return Square(BSFTable[((b & -b) * 0x218A392CD3D5DBFULL) >> 58]); -Square first_1(Bitboard b) { b ^= (b - 1); uint32_t fold = unsigned(b) ^ unsigned(b >> 32); return Square(BSFTable[(fold * 0x783A9B23) >> 26]); } -Square pop_1st_bit(Bitboard* b) { +Square pop_lsb(Bitboard* b) { Bitboard bb = *b; *b = bb & (bb - 1); + + if (Is64Bit) + return Square(BSFTable[((bb & -bb) * 0x218A392CD3D5DBFULL) >> 58]); + bb ^= (bb - 1); uint32_t fold = unsigned(bb) ^ unsigned(bb >> 32); return Square(BSFTable[(fold * 0x783A9B23) >> 26]); } -Square last_1(Bitboard b) { +Square msb(Bitboard b) { unsigned b32; int result = 0; diff --git a/src/bitboard.h b/src/bitboard.h index d187102f..2c4a0ea2 100644 --- a/src/bitboard.h +++ b/src/bitboard.h @@ -221,51 +221,52 @@ inline Bitboard attacks_bb(Square s, Bitboard occ) { } -/// 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. +/// lsb()/msb() finds the least/most significant bit in a nonzero bitboard. +/// pop_lsb() finds and clears the least significant bit in a nonzero bitboard. #if defined(USE_BSFQ) -#if defined(_MSC_VER) && !defined(__INTEL_COMPILER) +# if defined(_MSC_VER) && !defined(__INTEL_COMPILER) -FORCE_INLINE Square first_1(Bitboard b) { +FORCE_INLINE Square lsb(Bitboard b) { unsigned long index; _BitScanForward64(&index, b); return (Square) index; } -FORCE_INLINE Square last_1(Bitboard b) { +FORCE_INLINE Square msb(Bitboard b) { unsigned long index; _BitScanReverse64(&index, b); return (Square) index; } -#else -FORCE_INLINE Square first_1(Bitboard b) { // Assembly code by Heinz van Saanen - Bitboard dummy; - __asm__("bsfq %1, %0": "=r"(dummy): "rm"(b) ); - return (Square) dummy; +# else + +FORCE_INLINE Square lsb(Bitboard b) { // Assembly code by Heinz van Saanen + Bitboard index; + __asm__("bsfq %1, %0": "=r"(index): "rm"(b) ); + return (Square) index; } -FORCE_INLINE Square last_1(Bitboard b) { - Bitboard dummy; - __asm__("bsrq %1, %0": "=r"(dummy): "rm"(b) ); - return (Square) dummy; +FORCE_INLINE Square msb(Bitboard b) { + Bitboard index; + __asm__("bsrq %1, %0": "=r"(index): "rm"(b) ); + return (Square) index; } -#endif -FORCE_INLINE Square pop_1st_bit(Bitboard* b) { - const Square s = first_1(*b); - *b &= ~(1ULL<(Bitboard b) { #if !defined(USE_POPCNT) assert(false); - return int(b != 0); // Avoid 'b not used' warning + return b != 0; // Avoid 'b not used' warning #elif defined(_MSC_VER) && defined(__INTEL_COMPILER) diff --git a/src/book.cpp b/src/book.cpp index 8624dfbf..e14de415 100644 --- a/src/book.cpp +++ b/src/book.cpp @@ -316,7 +316,7 @@ namespace { { // Piece offset is at 64 * polyPiece where polyPiece is defined as: // BP = 0, WP = 1, BN = 2, WN = 3, ... BK = 10, WK = 11 - Square s = pop_1st_bit(&b); + Square s = pop_lsb(&b); Piece p = pos.piece_on(s); int polyPiece = 2 * (type_of(p) - 1) + (color_of(p) == WHITE); key ^= ZobPiece[64 * polyPiece + s]; @@ -325,7 +325,7 @@ namespace { b = pos.can_castle(ALL_CASTLES); while (b) - key ^= ZobCastle[pop_1st_bit(&b)]; + key ^= ZobCastle[pop_lsb(&b)]; if (pos.ep_square() != SQ_NONE) key ^= ZobEnPassant[file_of(pos.ep_square())]; diff --git a/src/evaluate.cpp b/src/evaluate.cpp index 02ca6d35..3b70a950 100644 --- a/src/evaluate.cpp +++ b/src/evaluate.cpp @@ -582,7 +582,7 @@ Value do_evaluate(const Position& pos, Value& margin) { assert(b); if (!more_than_one(b) && (b & pos.pieces(Them))) - score += ThreatBonus[Piece][type_of(pos.piece_on(first_1(b)))]; + score += ThreatBonus[Piece][type_of(pos.piece_on(lsb(b)))]; } // Decrease score if we are attacked by an enemy pawn. Remaining part @@ -870,7 +870,7 @@ Value do_evaluate(const Position& pos, Value& margin) { return SCORE_ZERO; do { - Square s = pop_1st_bit(&b); + Square s = pop_lsb(&b); assert(pos.pawn_is_passed(Us, s)); @@ -976,7 +976,7 @@ Value do_evaluate(const Position& pos, Value& margin) { while (b) { - s = pop_1st_bit(&b); + s = pop_lsb(&b); queeningSquare = relative_square(c, file_of(s) | RANK_8); queeningPath = forward_bb(c, s); @@ -1017,7 +1017,7 @@ Value do_evaluate(const Position& pos, Value& margin) { while (b) { - s = pop_1st_bit(&b); + s = pop_lsb(&b); // Compute plies from queening queeningSquare = relative_square(loserSide, file_of(s) | RANK_8); @@ -1039,7 +1039,7 @@ Value do_evaluate(const Position& pos, Value& margin) { while (b) { - s = pop_1st_bit(&b); + s = pop_lsb(&b); sacptg = blockersCount = 0; minKingDist = kingptg = 256; @@ -1058,7 +1058,7 @@ Value do_evaluate(const Position& pos, Value& margin) { // How many plies does it take to remove all the blocking pawns? while (blockers) { - blockSq = pop_1st_bit(&blockers); + blockSq = pop_lsb(&blockers); movesToGo = 256; // Check pawns that can give support to overcome obstacle, for instance @@ -1069,7 +1069,7 @@ Value do_evaluate(const Position& pos, Value& margin) { while (b2) // This while-loop could be replaced with LSB/MSB (depending on color) { - d = square_distance(blockSq, pop_1st_bit(&b2)) - 2; + d = square_distance(blockSq, pop_lsb(&b2)) - 2; movesToGo = std::min(movesToGo, d); } } @@ -1079,7 +1079,7 @@ Value do_evaluate(const Position& pos, Value& margin) { while (b2) // This while-loop could be replaced with LSB/MSB (depending on color) { - d = square_distance(blockSq, pop_1st_bit(&b2)) - 2; + d = square_distance(blockSq, pop_lsb(&b2)) - 2; movesToGo = std::min(movesToGo, d); } diff --git a/src/movegen.cpp b/src/movegen.cpp index 4ae16b4b..c275109d 100644 --- a/src/movegen.cpp +++ b/src/movegen.cpp @@ -25,10 +25,10 @@ /// Simple macro to wrap a very common while loop, no facny, no flexibility, /// hardcoded names 'mlist' and 'from'. -#define SERIALIZE(b) while (b) (*mlist++).move = make_move(from, pop_1st_bit(&b)) +#define SERIALIZE(b) while (b) (*mlist++).move = make_move(from, pop_lsb(&b)) /// Version used for pawns, where the 'from' square is given as a delta from the 'to' square -#define SERIALIZE_PAWNS(b, d) while (b) { Square to = pop_1st_bit(&b); \ +#define SERIALIZE_PAWNS(b, d) while (b) { Square to = pop_lsb(&b); \ (*mlist++).move = make_move(to - (d), to); } namespace { @@ -87,7 +87,7 @@ namespace { while (b) { - Square to = pop_1st_bit(&b); + Square to = pop_lsb(&b); if (Type == CAPTURES || Type == EVASIONS || Type == NON_EVASIONS) (*mlist++).move = make(to - Delta, to, QUEEN); @@ -207,7 +207,7 @@ namespace { assert(b1); while (b1) - (*mlist++).move = make(pop_1st_bit(&b1), pos.ep_square()); + (*mlist++).move = make(pop_lsb(&b1), pos.ep_square()); } } @@ -343,7 +343,7 @@ MoveStack* generate(const Position& pos, MoveStack* mlist) { while (dc) { - Square from = pop_1st_bit(&dc); + Square from = pop_lsb(&dc); PieceType pt = type_of(pos.piece_on(from)); if (pt == PAWN) @@ -398,7 +398,7 @@ MoveStack* generate(const Position& pos, MoveStack* mlist) { do { checkersCnt++; - checksq = pop_1st_bit(&b); + checksq = pop_lsb(&b); assert(color_of(pos.piece_on(checksq)) == ~us); diff --git a/src/notation.cpp b/src/notation.cpp index 69a44d95..89b00c55 100644 --- a/src/notation.cpp +++ b/src/notation.cpp @@ -108,7 +108,7 @@ const string move_to_san(Position& pos, Move m) { while (attackers) { - Square sq = pop_1st_bit(&attackers); + Square sq = pop_lsb(&attackers); // Pinned pieces are not included in the possible sub-set if (!pos.pl_move_is_legal(make_move(sq, to), pos.pinned_pieces())) diff --git a/src/pawns.cpp b/src/pawns.cpp index 73a9b904..069c8d94 100644 --- a/src/pawns.cpp +++ b/src/pawns.cpp @@ -240,12 +240,12 @@ Value PawnEntry::shelter_storm(const Position& pos, Square ksq) { { // Shelter penalty is higher for the pawn in front of the king b = ourPawns & FileBB[f]; - rkUs = b ? rank_of(Us == WHITE ? first_1(b) : ~last_1(b)) : RANK_1; + rkUs = b ? rank_of(Us == WHITE ? lsb(b) : ~msb(b)) : RANK_1; safety -= ShelterWeakness[f != kf][rkUs]; // Storm danger is smaller if enemy pawn is blocked b = theirPawns & FileBB[f]; - rkThem = b ? rank_of(Us == WHITE ? first_1(b) : ~last_1(b)) : RANK_1; + rkThem = b ? rank_of(Us == WHITE ? lsb(b) : ~msb(b)) : RANK_1; safety -= StormDanger[rkThem == rkUs + 1][rkThem]; } diff --git a/src/position.cpp b/src/position.cpp index a425b59c..244a2580 100644 --- a/src/position.cpp +++ b/src/position.cpp @@ -359,7 +359,7 @@ Bitboard Position::hidden_checkers() const { while (pinners) { - b = between_bb(ksq, pop_1st_bit(&pinners)) & pieces(); + b = between_bb(ksq, pop_lsb(&pinners)) & pieces(); if (b && !more_than_one(b) && (b & pieces(sideToMove))) result |= b; @@ -597,7 +597,7 @@ bool Position::is_pseudo_legal(const Move m) const { if (type_of(pc) != KING) { Bitboard b = checkers(); - Square checksq = pop_1st_bit(&b); + Square checksq = pop_lsb(&b); if (b) // double check ? In this case a king move is required return false; @@ -1323,7 +1323,7 @@ Key Position::compute_key() const { for (Bitboard b = pieces(); b; ) { - Square s = pop_1st_bit(&b); + Square s = pop_lsb(&b); k ^= zobrist[color_of(piece_on(s))][type_of(piece_on(s))][s]; } @@ -1349,7 +1349,7 @@ Key Position::compute_pawn_key() const { for (Bitboard b = pieces(PAWN); b; ) { - Square s = pop_1st_bit(&b); + Square s = pop_lsb(&b); k ^= zobrist[color_of(piece_on(s))][PAWN][s]; } @@ -1386,7 +1386,7 @@ Score Position::compute_psq_score() const { for (Bitboard b = pieces(); b; ) { - Square s = pop_1st_bit(&b); + Square s = pop_lsb(&b); score += pieceSquareTable[piece_on(s)][s]; } @@ -1477,7 +1477,7 @@ void Position::init() { Bitboard b = cr; while (b) { - Key k = zobCastle[1ULL << pop_1st_bit(&b)]; + Key k = zobCastle[1ULL << pop_lsb(&b)]; zobCastle[cr] ^= k ? k : rk.rand(); } } diff --git a/src/search.cpp b/src/search.cpp index 72ab9a12..9478ef17 100644 --- a/src/search.cpp +++ b/src/search.cpp @@ -1354,7 +1354,7 @@ split_point_start: // At split points actual search starts from here while (b) { // Note that here we generate illegal "double move"! - if (futilityBase + PieceValueEndgame[pos.piece_on(pop_1st_bit(&b))] >= beta) + if (futilityBase + PieceValueEndgame[pos.piece_on(pop_lsb(&b))] >= beta) return true; } diff --git a/src/tt.cpp b/src/tt.cpp index 72952257..9dbfcb5a 100644 --- a/src/tt.cpp +++ b/src/tt.cpp @@ -44,7 +44,7 @@ TranspositionTable::~TranspositionTable() { void TranspositionTable::set_size(size_t mbSize) { - size_t newSize = 1ULL << last_1((mbSize << 20) / sizeof(TTCluster)); + size_t newSize = 1ULL << msb((mbSize << 20) / sizeof(TTCluster)); if (newSize == size) return; @@ -60,7 +60,7 @@ void TranspositionTable::set_size(size_t mbSize) { exit(EXIT_FAILURE); } - clear(); // operator new is not guaranteed to initialize memory to zero + clear(); // Operator new is not guaranteed to initialize memory to zero }