X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fbitboard.cpp;h=b1bf4d91e583b3f07f1ac53cb669dce2a4522eb0;hp=54cc94fa7d04525390ff3e66094fff51b2adff69;hb=3092f0c6460c831e666d54389710394c52a86ed9;hpb=a617b038759f6abd1b33f71ef6d1938fa3588c3d

diff --git a/src/bitboard.cpp b/src/bitboard.cpp
index 54cc94fa..b1bf4d91 100644
--- a/src/bitboard.cpp
+++ b/src/bitboard.cpp
@@ -22,8 +22,41 @@
 #include "bitboard.h"
 #include "bitcount.h"
 
+// Global bitboards definitions with static storage duration are
+// automatically set to zero before enter main().
+Bitboard RAttacks[0x19000];
+Bitboard BAttacks[0x1480];
+
+Magics RMagics[64];
+Magics BMagics[64];
+
+Bitboard SetMaskBB[65];
+Bitboard ClearMaskBB[65];
+
+Bitboard SquaresByColorBB[2];
+Bitboard FileBB[8];
+Bitboard RankBB[8];
+Bitboard NeighboringFilesBB[8];
+Bitboard ThisAndNeighboringFilesBB[8];
+Bitboard InFrontBB[2][8];
+Bitboard StepAttacksBB[16][64];
+Bitboard BetweenBB[64][64];
+Bitboard SquaresInFrontMask[2][64];
+Bitboard PassedPawnMask[2][64];
+Bitboard AttackSpanMask[2][64];
+
+Bitboard BishopPseudoAttacks[64];
+Bitboard RookPseudoAttacks[64];
+Bitboard QueenPseudoAttacks[64];
+
+uint8_t BitCount8Bit[256];
+
+namespace {
+
 #if defined(IS_64BIT)
 
+const uint64_t DeBruijnMagic = 0x218A392CD3D5DBFULL;
+
 const uint64_t BMult[64] = {
   0x0440049104032280ULL, 0x1021023C82008040ULL, 0x0404040082000048ULL,
   0x48C4440084048090ULL, 0x2801104026490000ULL, 0x4100880442040800ULL,
@@ -90,6 +123,8 @@ const int RShift[64] = {
 
 #else // if !defined(IS_64BIT)
 
+const uint32_t DeBruijnMagic = 0x783A9B23;
+
 const uint64_t BMult[64] = {
   0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL,
   0xBFED1A0B80F838C5ULL, 0x90561D5631E62110ULL, 0x2804260376E60944ULL,
@@ -156,49 +191,10 @@ const int RShift[64] = {
 
 #endif // defined(IS_64BIT)
 
-// Global bitboards definitions with static storage duration are
-// automatically set to zero before enter main().
-Bitboard RMask[64];
-int RAttackIndex[64];
-Bitboard RAttacks[0x19000];
-
-Bitboard BMask[64];
-int BAttackIndex[64];
-Bitboard BAttacks[0x1480];
-
-Bitboard SetMaskBB[65];
-Bitboard ClearMaskBB[65];
-
-Bitboard SquaresByColorBB[2];
-Bitboard FileBB[8];
-Bitboard RankBB[8];
-Bitboard NeighboringFilesBB[8];
-Bitboard ThisAndNeighboringFilesBB[8];
-Bitboard InFrontBB[2][8];
-Bitboard NonSlidingAttacksBB[16][64];
-Bitboard BetweenBB[64][64];
-Bitboard SquaresInFrontMask[2][64];
-Bitboard PassedPawnMask[2][64];
-Bitboard AttackSpanMask[2][64];
-
-Bitboard BishopPseudoAttacks[64];
-Bitboard RookPseudoAttacks[64];
-Bitboard QueenPseudoAttacks[64];
-
-uint8_t BitCount8Bit[256];
-
+  CACHE_LINE_ALIGNMENT int BSFTable[64];
 
-namespace {
-
-  void init_masks();
-  void init_non_sliding_attacks();
-  void init_pseudo_attacks();
-  void init_between_bitboards();
-  Bitboard index_to_bitboard(int index, Bitboard mask);
-  Bitboard sliding_attacks(int sq, Bitboard occupied, int deltas[][2],
-                           int fmin, int fmax, int rmin, int rmax);
-  void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
-                            const int shift[], const Bitboard mult[], int deltas[][2]);
+  void init_sliding_attacks(Bitboard attacks[], Magics m[], const int shift[],
+                            const Bitboard mult[], Square deltas[]);
 }
 
 
@@ -225,39 +221,22 @@ void print_bitboard(Bitboard b) {
 
 #if defined(IS_64BIT) && !defined(USE_BSFQ)
 
-static CACHE_LINE_ALIGNMENT
-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]);
+  return Square(BSFTable[((b & -b) * DeBruijnMagic) >> 58]);
 }
 
 Square pop_1st_bit(Bitboard* b) {
   Bitboard bb = *b;
   *b &= (*b - 1);
-  return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
+  return Square(BSFTable[((bb & -bb) * DeBruijnMagic) >> 58]);
 }
 
 #elif !defined(USE_BSFQ)
 
-static CACHE_LINE_ALIGNMENT
-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]);
+  uint32_t fold = unsigned(b) ^ unsigned(b >> 32);
+  return Square(BSFTable[(fold * DeBruijnMagic) >> 26]);
 }
 
 // Use type-punning
@@ -284,12 +263,12 @@ Square pop_1st_bit(Bitboard* bb) {
 
    if (u.dw.l)
    {
-       ret = Square(BitTable[((u.dw.l ^ (u.dw.l - 1)) * 0x783a9b23) >> 26]);
+       ret = Square(BSFTable[((u.dw.l ^ (u.dw.l - 1)) * DeBruijnMagic) >> 26]);
        u.dw.l &= (u.dw.l - 1);
        *bb = u.b;
        return ret;
    }
-   ret = Square(BitTable[((~(u.dw.h ^ (u.dw.h - 1))) * 0x783a9b23) >> 26]);
+   ret = Square(BSFTable[((~(u.dw.h ^ (u.dw.h - 1))) * DeBruijnMagic) >> 26]);
    u.dw.h &= (u.dw.h - 1);
    *bb = u.b;
    return ret;
@@ -303,184 +282,166 @@ Square pop_1st_bit(Bitboard* bb) {
 
 void init_bitboards() {
 
-  int rookDeltas[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
-  int bishopDeltas[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
+  SquaresByColorBB[DARK]  =  0xAA55AA55AA55AA55ULL;
+  SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK];
 
-  init_masks();
-  init_non_sliding_attacks();
-  init_sliding_attacks(RAttacks, RAttackIndex, RMask, RShift, RMult, rookDeltas);
-  init_sliding_attacks(BAttacks, BAttackIndex, BMask, BShift, BMult, bishopDeltas);
-  init_pseudo_attacks();
-  init_between_bitboards();
-}
-
-namespace {
+  for (Square s = SQ_A1; s <= SQ_H8; s++)
+  {
+      SetMaskBB[s] = (1ULL << s);
+      ClearMaskBB[s] = ~SetMaskBB[s];
+  }
 
-  // All functions below are used to precompute various bitboards during
-  // program initialization.  Some of the functions may be difficult to
-  // understand, but they all seem to work correctly, and it should never
-  // be necessary to touch any of them.
+  ClearMaskBB[SQ_NONE] = ~EmptyBoardBB;
 
-  void init_masks() {
+  FileBB[FILE_A] = FileABB;
+  RankBB[RANK_1] = Rank1BB;
 
-    SquaresByColorBB[DARK]  =  0xAA55AA55AA55AA55ULL;
-    SquaresByColorBB[LIGHT] = ~SquaresByColorBB[DARK];
+  for (int f = FILE_B; f <= FILE_H; f++)
+  {
+      FileBB[f] = FileBB[f - 1] << 1;
+      RankBB[f] = RankBB[f - 1] << 8;
+  }
 
-    FileBB[FILE_A] = FileABB;
-    RankBB[RANK_1] = Rank1BB;
+  for (int f = FILE_A; f <= FILE_H; f++)
+  {
+      NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
+      ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f];
+  }
 
-    for (File f = FILE_B; f <= FILE_H; f++)
-    {
-        FileBB[f] = FileBB[f - 1] << 1;
-        RankBB[f] = RankBB[f - 1] << 8;
-    }
+  for (int rw = RANK_7, rb = RANK_2; rw >= RANK_1; rw--, rb++)
+  {
+      InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1];
+      InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1];
+  }
 
-    for (File f = FILE_A; f <= FILE_H; f++)
-    {
-        NeighboringFilesBB[f] = (f > FILE_A ? FileBB[f - 1] : 0) | (f < FILE_H ? FileBB[f + 1] : 0);
-        ThisAndNeighboringFilesBB[f] = FileBB[f] | NeighboringFilesBB[f];
-    }
+  for (Color c = WHITE; c <= BLACK; c++)
+      for (Square s = SQ_A1; s <= SQ_H8; s++)
+      {
+          SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
+          PassedPawnMask[c][s]     = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
+          AttackSpanMask[c][s]     = in_front_bb(c, s) & neighboring_files_bb(s);
+      }
+
+  for (Bitboard b = 0; b < 256; b++)
+      BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
+
+  for (int i = 1; i < 64; i++)
+      if (!CpuIs64Bit) // Matt Taylor's folding trick for 32 bit systems
+      {
+          Bitboard b = 1ULL << i;
+          b ^= b - 1;
+          b ^= b >> 32;
+          BSFTable[uint32_t(b * DeBruijnMagic) >> 26] = i;
+      }
+      else
+          BSFTable[((1ULL << i) * DeBruijnMagic) >> 58] = i;
+
+  int steps[][9] = {
+    {0}, {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0}, {9,7,-7,-9,8,1,-1,-8,0}
+  };
+
+  for (Color c = WHITE; c <= BLACK; c++)
+      for (Square s = SQ_A1; s <= SQ_H8; s++)
+          for (PieceType pt = PAWN; pt <= KING; pt++)
+              for (int k = 0; steps[pt][k]; k++)
+              {
+                  Square to = s + Square(c == WHITE ? steps[pt][k] : -steps[pt][k]);
+
+                  if (square_is_ok(to) && square_distance(s, to) < 3)
+                      set_bit(&StepAttacksBB[make_piece(c, pt)][s], to);
+              }
+
+  Square RDeltas[] = { DELTA_N,  DELTA_E,  DELTA_S,  DELTA_W  };
+  Square BDeltas[] = { DELTA_NE, DELTA_SE, DELTA_SW, DELTA_NW };
+
+  init_sliding_attacks(RAttacks, RMagics, RShift, RMult, RDeltas);
+  init_sliding_attacks(BAttacks, BMagics, BShift, BMult, BDeltas);
+
+  for (Square s = SQ_A1; s <= SQ_H8; s++)
+  {
+      BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
+      RookPseudoAttacks[s]   = rook_attacks_bb(s, EmptyBoardBB);
+      QueenPseudoAttacks[s]  = queen_attacks_bb(s, EmptyBoardBB);
+  }
 
-    for (Rank rw = RANK_7, rb = RANK_1; rw >= RANK_1; rw--, rb++)
-    {
-        InFrontBB[WHITE][rw] = InFrontBB[WHITE][rw + 1] | RankBB[rw + 1];
-        InFrontBB[BLACK][rb] = InFrontBB[BLACK][rb - 1] | RankBB[rb - 1];
-    }
+  for (Square s1 = SQ_A1; s1 <= SQ_H8; s1++)
+      for (Square s2 = SQ_A1; s2 <= SQ_H8; s2++)
+          if (bit_is_set(QueenPseudoAttacks[s1], s2))
+          {
+              int f = file_distance(s1, s2);
+              int r = rank_distance(s1, s2);
 
-    SetMaskBB[SQ_NONE] = EmptyBoardBB;
-    ClearMaskBB[SQ_NONE] = ~SetMaskBB[SQ_NONE];
+              Square d = (s2 - s1) / Max(f, r);
 
-    for (Square s = SQ_A1; s <= SQ_H8; s++)
-    {
-        SetMaskBB[s] = (1ULL << s);
-        ClearMaskBB[s] = ~SetMaskBB[s];
-    }
+              for (Square s3 = s1 + d; s3 != s2; s3 += d)
+                  set_bit(&BetweenBB[s1][s2], s3);
+          }
+}
 
-    for (Color c = WHITE; c <= BLACK; c++)
-        for (Square s = SQ_A1; s <= SQ_H8; s++)
-        {
-            SquaresInFrontMask[c][s] = in_front_bb(c, s) & file_bb(s);
-            PassedPawnMask[c][s] = in_front_bb(c, s) & this_and_neighboring_files_bb(s);
-            AttackSpanMask[c][s] = in_front_bb(c, s) & neighboring_files_bb(s);
-        }
 
-    for (Bitboard b = 0; b < 256; b++)
-        BitCount8Bit[b] = (uint8_t)count_1s<CNT32>(b);
-  }
+namespace {
 
-  void init_non_sliding_attacks() {
+  Bitboard submask(Bitboard mask, int key) {
 
-    const int step[][9] =  {
-      {0},
-      {7,9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0},
-      {9,7,-7,-9,8,1,-1,-8,0}, {0}, {0},
-      {-7,-9,0}, {17,15,10,6,-6,-10,-15,-17,0}, {0}, {0}, {0},
-      {9,7,-7,-9,8,1,-1,-8,0}
-    };
+    Bitboard subMask = 0;
+    int bitNum = -1;
 
+    // Extract an unique submask out of a mask according to the given key
     for (Square s = SQ_A1; s <= SQ_H8; s++)
-        for (Piece pc = WP; pc <= BK; pc++)
-            for (int k = 0; step[pc][k] != 0; k++)
-            {
-                Square to = s + Square(step[pc][k]);
-
-                if (square_is_ok(to) && square_distance(s, to) < 3)
-                    set_bit(&NonSlidingAttacksBB[pc][s], to);
-           }
+        if (bit_is_set(mask, s) && bit_is_set(key, Square(++bitNum)))
+            set_bit(&subMask, s);
+
+    return subMask;
   }
 
-  Bitboard sliding_attacks(int sq, Bitboard occupied, int deltas[][2],
-                           int fmin, int fmax, int rmin, int rmax) {
-    int dx, dy, f, r;
-    int rk = sq / 8;
-    int fl = sq % 8;
-    Bitboard attacks = EmptyBoardBB;
+  Bitboard sliding_attacks(Square sq, Bitboard occupied, Square deltas[], bool skipLast) {
+
+    Bitboard attacks = 0;
 
     for (int i = 0; i < 4; i++)
     {
-        dx = deltas[i][0];
-        dy = deltas[i][1];
-        f = fl + dx;
-        r = rk + dy;
+        Square s = sq + deltas[i];
 
-        while (   (dx == 0 || (f >= fmin && f <= fmax))
-               && (dy == 0 || (r >= rmin && r <= rmax)))
+        while (    square_is_ok(s)
+               &&  square_distance(s, s - deltas[i]) == 1
+               && (!skipLast || !file_distance(s, sq) || (square_file(s) != FILE_A && square_file(s) != FILE_H))
+               && (!skipLast || !rank_distance(s, sq) || (square_rank(s) != RANK_1 && square_rank(s) != RANK_8)))
         {
-            attacks |= (1ULL << (f + r * 8));
+            attacks |= 1ULL << s;
 
-            if (occupied & (1ULL << (f + r * 8)))
+            if (occupied & (1ULL << s))
                 break;
 
-            f += dx;
-            r += dy;
+            s += deltas[i];
         }
     }
     return attacks;
   }
 
-  Bitboard index_to_bitboard(int index, Bitboard mask) {
-
-    Bitboard result = EmptyBoardBB;
-    int sq, cnt = 0;
+  void init_sliding_attacks(Bitboard attacks[], Magics m[], const int shift[],
+                            const Bitboard mult[], Square deltas[]) {
+    Bitboard occupancy, index;
+    int maxKey, offset = 0;
 
-    while (mask)
+    for (Square s = SQ_A1; s <= SQ_H8; s++)
     {
-        sq = pop_1st_bit(&mask);
-
-        if (index & (1 << cnt++))
-            result |= (1ULL << sq);
-    }
-    return result;
-  }
-
-  void init_sliding_attacks(Bitboard attacks[], int attackIndex[], Bitboard mask[],
-                            const int shift[], const Bitboard mult[], int deltas[][2]) {
-    Bitboard b, v;
-    int i, j, index;
+        m[s].offset = offset;
+        m[s].mult   = mult[s];
+        m[s].shift  = shift[s];
+        m[s].mask   = sliding_attacks(s, EmptyBoardBB, deltas, true);
 
-    for (i = index = 0; i < 64; i++)
-    {
-        attackIndex[i] = index;
-        mask[i] = sliding_attacks(i, 0, deltas, 1, 6, 1, 6);
-        j = 1 << ((CpuIs64Bit ? 64 : 32) - shift[i]);
+        maxKey = 1 << (CpuIs64Bit ? 64 - shift[s] : 32 - shift[s]);
 
-        for (int k = 0; k < j; k++)
+        for (int key = 0; key < maxKey; key++)
         {
-            b = index_to_bitboard(k, mask[i]);
-            v = CpuIs64Bit ? b * mult[i] : unsigned(b * mult[i] ^ (b >> 32) * (mult[i] >> 32));
-            attacks[index + (v >> shift[i])] = sliding_attacks(i, b, deltas, 0, 7, 0, 7);
-        }
-        index += j;
-    }
-  }
+            occupancy = submask(m[s].mask, key);
 
-  void init_pseudo_attacks() {
+            index = CpuIs64Bit ? occupancy * mult[s]
+                               : unsigned(occupancy * mult[s] ^ (occupancy >> 32) * (mult[s] >> 32));
 
-    for (Square s = SQ_A1; s <= SQ_H8; s++)
-    {
-        BishopPseudoAttacks[s] = bishop_attacks_bb(s, EmptyBoardBB);
-        RookPseudoAttacks[s]   = rook_attacks_bb(s, EmptyBoardBB);
-        QueenPseudoAttacks[s]  = queen_attacks_bb(s, EmptyBoardBB);
+            attacks[offset + (index >> shift[s])] = sliding_attacks(s, occupancy, deltas, false);
+        }
+        offset += maxKey;
     }
   }
-
-  void init_between_bitboards() {
-
-    Square s1, s2, s3, d;
-    int f, r;
-
-    for (s1 = SQ_A1; s1 <= SQ_H8; s1++)
-        for (s2 = SQ_A1; s2 <= SQ_H8; s2++)
-            if (bit_is_set(QueenPseudoAttacks[s1], s2))
-            {
-                f = file_distance(s1, s2);
-                r = rank_distance(s1, s2);
-
-                d = (s2 - s1) / Max(f, r);
-
-                for (s3 = s1 + d; s3 != s2; s3 += d)
-                    set_bit(&(BetweenBB[s1][s2]), s3);
-            }
-  }
-
 }