Rename first_1 / last_1 in lsb / msb
authorMarco Costalba <mcostalba@gmail.com>
Sun, 8 Jul 2012 07:30:37 +0000 (08:30 +0100)
committerMarco Costalba <mcostalba@gmail.com>
Sun, 8 Jul 2012 08:36:40 +0000 (09:36 +0100)
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 <mcostalba@gmail.com>
12 files changed:
src/bitbase.cpp
src/bitboard.cpp
src/bitboard.h
src/bitcount.h
src/book.cpp
src/evaluate.cpp
src/movegen.cpp
src/notation.cpp
src/pawns.cpp
src/position.cpp
src/search.cpp
src/tt.cpp

index 9322e53..9d2cde0 100644 (file)
@@ -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;
index 08b43ad..945169c 100644 (file)
@@ -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;
index d187102..2c4a0ea 100644 (file)
@@ -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<<s);
+#  endif
+
+FORCE_INLINE Square pop_lsb(Bitboard* b) {
+  const Square s = lsb(*b);
+  *b &= ~(1ULL << s);
   return s;
 }
 
 #else // if !defined(USE_BSFQ)
 
-extern Square first_1(Bitboard b);
-extern Square last_1(Bitboard b);
-extern Square pop_1st_bit(Bitboard* b);
+extern Square msb(Bitboard b);
+extern Square lsb(Bitboard b);
+extern Square pop_lsb(Bitboard* b);
 
 #endif
 
index 9d25a5e..ce2a69a 100644 (file)
@@ -90,7 +90,7 @@ inline int popcount<CNT_HW_POPCNT>(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)
 
index 8624dfb..e14de41 100644 (file)
@@ -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())];
index 02ca6d3..3b70a95 100644 (file)
@@ -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);
             }
 
index 4ae16b4..c275109 100644 (file)
 
 /// 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<PROMOTION>(to - Delta, to, QUEEN);
@@ -207,7 +207,7 @@ namespace {
             assert(b1);
 
             while (b1)
-                (*mlist++).move = make<ENPASSANT>(pop_1st_bit(&b1), pos.ep_square());
+                (*mlist++).move = make<ENPASSANT>(pop_lsb(&b1), pos.ep_square());
         }
     }
 
@@ -343,7 +343,7 @@ MoveStack* generate<QUIET_CHECKS>(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<EVASIONS>(const Position& pos, MoveStack* mlist) {
   do
   {
       checkersCnt++;
-      checksq = pop_1st_bit(&b);
+      checksq = pop_lsb(&b);
 
       assert(color_of(pos.piece_on(checksq)) == ~us);
 
index 69a44d9..89b00c5 100644 (file)
@@ -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()))
index 73a9b90..069c8d9 100644 (file)
@@ -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];
   }
 
index a425b59..244a258 100644 (file)
@@ -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<Key>();
       }
   }
index 72ab9a1..9478ef1 100644 (file)
@@ -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;
     }
 
index 7295225..9dbfcb5 100644 (file)
@@ -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
 }