From: Marco Costalba <mcostalba@gmail.com>
Date: Tue, 14 Jun 2011 17:40:52 +0000 (+0100)
Subject: Use Carry-Rippler trick to speed up magics
X-Git-Url: https://git.sesse.net/?p=stockfish;a=commitdiff_plain;h=4c9d570e43b19119354e1c1643653ff85981f976;hp=fc519ca74a110a0ceea3c710c88da096fa850c65

Use Carry-Rippler trick to speed up magics

Nice trick discovered on:

http://chessprogramming.wikispaces.com/Traversing+Subsets+of+a+Set

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
---

diff --git a/src/bitboard.cpp b/src/bitboard.cpp
index 2fd0cada..67f211a4 100644
--- a/src/bitboard.cpp
+++ b/src/bitboard.cpp
@@ -252,25 +252,6 @@ void init_bitboards() {
 
 namespace {
 
-  Bitboard submask(Bitboard mask, int key) {
-
-    Bitboard b, subMask = 0;
-    int bitProbe = 1;
-
-    // Extract an unique submask out of a mask according to the given key
-    while (mask)
-    {
-        b = mask & -mask;
-        mask ^= b;
-
-        if (key & bitProbe)
-            subMask |= b;
-
-        bitProbe <<= 1;
-    }
-    return subMask;
-  }
-
   Bitboard sliding_attacks(Square sq, Bitboard occupied, Square delta[], Bitboard excluded) {
 
     Bitboard attacks = 0;
@@ -321,7 +302,7 @@ namespace {
     const int  MagicBoosters[][8] = { { 3191, 2184, 1310, 3618, 2091, 1308, 2452, 3996 },
                                       { 1059, 3608,  605, 3234, 3326,   38, 2029, 3043 } };
     RKISS rk;
-    Bitboard occupancy[4096], reference[4096], excluded;
+    Bitboard occupancy[4096], reference[4096], excluded, b;
     int key, maxKey, index, booster, offset = 0;
 
     for (Square s = SQ_A1; s <= SQ_H8; s++)
@@ -332,17 +313,17 @@ namespace {
         mask[s]   = sliding_attacks(s, EmptyBoardBB, delta, excluded);
         shift[s]  = (CpuIs64Bit ? 64 : 32) - count_1s<CNT32_MAX15>(mask[s]);
 
-        maxKey = 1 << count_1s<CNT32_MAX15>(mask[s]);
+        // Use Carry-Rippler trick to enumerate all subsets of mask[s]
+        b = maxKey = 0;
+        do {
+            occupancy[maxKey] = b;
+            reference[maxKey++] = sliding_attacks(s, b, delta, EmptyBoardBB);
+            b = (b - mask[s]) & mask[s];
+        } while (b);
+
         offset += maxKey;
         booster = MagicBoosters[CpuIs64Bit][square_rank(s)];
 
-        // First compute occupancy and attacks for square 's'
-        for (key = 0; key < maxKey; key++)
-        {
-            occupancy[key] = submask(mask[s], key);
-            reference[key] = sliding_attacks(s, occupancy[key], delta, EmptyBoardBB);
-        }
-
         // Then find a possible magic and the corresponding attacks
         do {
             magic[s] = pick_magic(mask[s], rk, booster);