Reordering magic data
authormstembera <MissingEmail@email>
Tue, 6 Jun 2017 17:20:43 +0000 (10:20 -0700)
committerJoona Kiiski <joona@zoox.com>
Tue, 6 Jun 2017 17:22:12 +0000 (10:22 -0700)
Gather all magic relevant data into a struct.

This changes memory layout putting everything necessary for processing a single square
in the same memory location thus speeding up access.

Original patch by @snicolet

No functional change.

Closes #1127
Closes #1128

src/bitboard.cpp
src/bitboard.h

index 1f6dab9df64de1394d6784b6d84983cd378d5ead..99070ef2c0a6f9e606781517af9a4a213c91cb35 100644 (file)
 uint8_t PopCnt16[1 << 16];
 int SquareDistance[SQUARE_NB][SQUARE_NB];
 
-Bitboard  RookMasks  [SQUARE_NB];
-Bitboard  RookMagics [SQUARE_NB];
-Bitboard* RookAttacks[SQUARE_NB];
-unsigned  RookShifts [SQUARE_NB];
-
-Bitboard  BishopMasks  [SQUARE_NB];
-Bitboard  BishopMagics [SQUARE_NB];
-Bitboard* BishopAttacks[SQUARE_NB];
-unsigned  BishopShifts [SQUARE_NB];
+Magic RookMagics[SQUARE_NB];
+Magic BishopMagics[SQUARE_NB];
 
 Bitboard SquareBB[SQUARE_NB];
 Bitboard FileBB[FILE_NB];
@@ -63,8 +56,7 @@ namespace {
 
   typedef unsigned (Fn)(Square, Bitboard);
 
-  void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[],
-                   Bitboard masks[], unsigned shifts[], Square deltas[], Fn index);
+  void init_magics(Bitboard table[], Magic magics[], Square deltas[], Fn index);
 
   // bsf_index() returns the index into BSFTable[] to look up the bitscan. Uses
   // Matt Taylor's folding for 32 bit case, extended to 64 bit by Kim Walisch.
@@ -212,8 +204,8 @@ void Bitboards::init() {
   Square RookDeltas[] = { NORTH,  EAST,  SOUTH,  WEST };
   Square BishopDeltas[] = { NORTH_EAST, SOUTH_EAST, SOUTH_WEST, NORTH_WEST };
 
-  init_magics(RookTable, RookAttacks, RookMagics, RookMasks, RookShifts, RookDeltas, magic_index<ROOK>);
-  init_magics(BishopTable, BishopAttacks, BishopMagics, BishopMasks, BishopShifts, BishopDeltas, magic_index<BISHOP>);
+  init_magics(RookTable, RookMagics, RookDeltas, magic_index<ROOK>);
+  init_magics(BishopTable, BishopMagics, BishopDeltas, magic_index<BISHOP>);
 
   for (Square s1 = SQ_A1; s1 <= SQ_H8; ++s1)
   {
@@ -259,8 +251,7 @@ namespace {
   // chessprogramming.wikispaces.com/Magic+Bitboards. In particular, here we
   // use the so called "fancy" approach.
 
-  void init_magics(Bitboard table[], Bitboard* attacks[], Bitboard magics[],
-                   Bitboard masks[], unsigned shifts[], Square deltas[], Fn index) {
+  void init_magics(Bitboard table[], Magic magics[], Square deltas[], Fn index) {
 
     int seeds[][RANK_NB] = { { 8977, 44560, 54343, 38998,  5731, 95205, 104912, 17020 },
                              {  728, 10316, 55013, 32803, 12281, 15100,  16645,   255 } };
@@ -269,7 +260,7 @@ namespace {
     int age[4096] = {0}, current = 0, i, size;
 
     // attacks[s] is a pointer to the beginning of the attacks table for square 's'
-    attacks[SQ_A1] = table;
+    magics[SQ_A1].attacks = table;
 
     for (Square s = SQ_A1; s <= SQ_H8; ++s)
     {
@@ -281,8 +272,8 @@ namespace {
         // all the attacks for each possible subset of the mask and so is 2 power
         // the number of 1s of the mask. Hence we deduce the size of the shift to
         // apply to the 64 or 32 bits word to get the index.
-        masks[s]  = sliding_attack(deltas, s, 0) & ~edges;
-        shifts[s] = (Is64Bit ? 64 : 32) - popcount(masks[s]);
+        magics[s].mask  = sliding_attack(deltas, s, 0) & ~edges;
+        magics[s].shift = (Is64Bit ? 64 : 32) - popcount(magics[s].mask);
 
         // Use Carry-Rippler trick to enumerate all subsets of masks[s] and
         // store the corresponding sliding attack bitboard in reference[].
@@ -292,16 +283,16 @@ namespace {
             reference[size] = sliding_attack(deltas, s, b);
 
             if (HasPext)
-                attacks[s][pext(b, masks[s])] = reference[size];
+                magics[s].attacks[pext(b, magics[s].mask)] = reference[size];
 
             size++;
-            b = (b - masks[s]) & masks[s];
+            b = (b - magics[s].mask) & magics[s].mask;
         } while (b);
 
         // Set the offset for the table of the next square. We have individual
         // table sizes for each square with "Fancy Magic Bitboards".
         if (s < SQ_H8)
-            attacks[s + 1] = attacks[s] + size;
+            magics[s + 1].attacks = magics[s].attacks + size;
 
         if (HasPext)
             continue;
@@ -312,8 +303,8 @@ namespace {
         // until we find the one that passes the verification test.
         do {
             do
-                magics[s] = rng.sparse_rand<Bitboard>();
-            while (popcount((magics[s] * masks[s]) >> 56) < 6);
+                magics[s].magic = rng.sparse_rand<Bitboard>();
+            while (popcount((magics[s].magic * magics[s].mask) >> 56) < 6);
 
             // A good magic must map every possible occupancy to an index that
             // looks up the correct sliding attack in the attacks[s] database.
@@ -326,9 +317,9 @@ namespace {
                 if (age[idx] < current)
                 {
                     age[idx] = current;
-                    attacks[s][idx] = reference[i];
+                    magics[s].attacks[idx] = reference[i];
                 }
-                else if (attacks[s][idx] != reference[i])
+                else if (magics[s].attacks[idx] != reference[i])
                     break;
             }
         } while (i < size);
index c957a40fe23d61296a0e094bf36bd44581cda5d6..3ea92bdf2e56400b273cafaf4f1689bc12a5de7e 100644 (file)
@@ -209,41 +209,47 @@ template<> inline int distance<File>(Square x, Square y) { return distance(file_
 template<> inline int distance<Rank>(Square x, Square y) { return distance(rank_of(x), rank_of(y)); }
 
 
+/// Magic holds all magic relevant data for a single square
+struct Magic {
+
+    Bitboard  mask;
+    Bitboard  magic;
+    Bitboard* attacks;
+    unsigned  shift;
+};
+
 /// attacks_bb() returns a bitboard representing all the squares attacked by a
 /// piece of type Pt (bishop or rook) placed on 's'. The helper magic_index()
 /// looks up the index using the 'magic bitboards' approach.
 template<PieceType Pt>
 inline unsigned magic_index(Square s, Bitboard occupied) {
 
-  extern Bitboard RookMasks[SQUARE_NB];
-  extern Bitboard RookMagics[SQUARE_NB];
-  extern unsigned RookShifts[SQUARE_NB];
-  extern Bitboard BishopMasks[SQUARE_NB];
-  extern Bitboard BishopMagics[SQUARE_NB];
-  extern unsigned BishopShifts[SQUARE_NB];
+  extern Magic RookMagics[SQUARE_NB];
+  extern Magic BishopMagics[SQUARE_NB];
 
-  Bitboard* const Masks  = Pt == ROOK ? RookMasks  : BishopMasks;
-  Bitboard* const Magics = Pt == ROOK ? RookMagics : BishopMagics;
-  unsigned* const Shifts = Pt == ROOK ? RookShifts : BishopShifts;
+  const Magic* Magics = Pt == ROOK ? RookMagics : BishopMagics;
+  Bitboard mask  = Magics[s].mask;
+  Bitboard magic = Magics[s].magic;
+  unsigned shift = Magics[s].shift;
 
   if (HasPext)
-      return unsigned(pext(occupied, Masks[s]));
+      return unsigned(pext(occupied, mask));
 
   if (Is64Bit)
-      return unsigned(((occupied & Masks[s]) * Magics[s]) >> Shifts[s]);
+      return unsigned(((occupied & mask) * magic) >> shift);
 
-  unsigned lo = unsigned(occupied) & unsigned(Masks[s]);
-  unsigned hi = unsigned(occupied >> 32) & unsigned(Masks[s] >> 32);
-  return (lo * unsigned(Magics[s]) ^ hi * unsigned(Magics[s] >> 32)) >> Shifts[s];
+  unsigned lo = unsigned(occupied) & unsigned(mask);
+  unsigned hi = unsigned(occupied >> 32) & unsigned(mask >> 32);
+  return  (lo * unsigned(magic) ^ hi * unsigned(magic >> 32)) >> shift;
 }
 
 template<PieceType Pt>
 inline Bitboard attacks_bb(Square s, Bitboard occupied) {
 
-  extern Bitboard* RookAttacks[SQUARE_NB];
-  extern Bitboard* BishopAttacks[SQUARE_NB];
+    extern Magic RookMagics[SQUARE_NB];
+    extern Magic BishopMagics[SQUARE_NB];
 
-  return (Pt == ROOK ? RookAttacks : BishopAttacks)[s][magic_index<Pt>(s, occupied)];
+    return (Pt == ROOK ? RookMagics : BishopMagics)[s].attacks[magic_index<Pt>(s, occupied)];
 }
 
 inline Bitboard attacks_bb(PieceType pt, Square s, Bitboard occupied) {