src/bitboard.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     bitboard.c
   8
   9 Abstract:
  10
  11     Routines dealing with bitboards.  If you build with the
  12     testbitboard.c code enabled it will give you a rough benchmark of
  13     these routines' speeds.  Here are some typical results (from a
  14     1.5ghz Athlon):
  15
  16         SLOWCOOR_TO_BB: 10 cycles/op
  17         COOR_TO_BB:     5 cycles/op
  18         SlowCountBits:  82 cycles/op
  19         CountBits:      2 cycles/op
  20         SlowLastBit:    158 cycles/op
  21         LastBit:        2 cycles/op
  22         SlowFirstBit:   22 cycles/op
  23         FirstBit:       2 cycles/op
  24
  25     As you can see the inline assembly language code is quite a bit
  26     faster so use it if you can.  And if, on the off chance, you are
  27     porting this code to another hardware platform, it might be worth
  28     your time to research what your instruction set has in the way of
  29     bit twiddling opcodes.
  30
  31 Author:
  32
  33     Scott Gasch ([email protected]) 19 Jun 2004
  34
  35 Revision History:
  36
  37     $Id: bitboard.c 345 2007-12-02 22:56:42Z scott $
  38
  39 **/
  40
  41 #include "chess.h"
  42
  43
  44 //
  45 // Mapping from square -> bit
  46 //
  47 BITBOARD BBSQUARE[64] =
  48 {
  49     0x1ULL,                                   // 1
  50     0x2ULL,                                   // 2
  51     0x4ULL,                                   // 3
  52     0x8ULL,                                   // 4
  53     0x10ULL,                                  // 5
  54     0x20ULL,                                  // 6
  55     0x40ULL,                                  // 7
  56     0x80ULL,                                  // 8
  57     0x100ULL,                                 // 9
  58     0x200ULL,                                 // 10
  59     0x400ULL,                                 // 11
  60     0x800ULL,                                 // 12
  61     0x1000ULL,                                // 13
  62     0x2000ULL,                                // 14
  63     0x4000ULL,                                // 15
  64     0x8000ULL,                                // 16
  65     0x10000ULL,                               // 17
  66     0x20000ULL,                               // 18
  67     0x40000ULL,                               // 19
  68     0x80000ULL,                               // 20
  69     0x100000ULL,                              // 21
  70     0x200000ULL,                              // 22
  71     0x400000ULL,                              // 23
  72     0x800000ULL,                              // 24
  73     0x1000000ULL,                             // 25
  74     0x2000000ULL,                             // 26
  75     0x4000000ULL,                             // 27
  76     0x8000000ULL,                             // 28
  77     0x10000000ULL,                            // 29
  78     0x20000000ULL,                            // 30
  79     0x40000000ULL,                            // 31
  80     0x80000000ULL,                            // 32
  81 //--------------------------------------------------
  82     0x100000000ULL,                           // 33
  83     0x200000000ULL,                           // 34
  84     0x400000000ULL,                           // 35
  85     0x800000000ULL,                           // 36
  86     0x1000000000ULL,                          // 37
  87     0x2000000000ULL,                          // 38
  88     0x4000000000ULL,                          // 39
  89     0x8000000000ULL,                          // 40
  90     0x10000000000ULL,                         // 41
  91     0x20000000000ULL,                         // 42
  92     0x40000000000ULL,                         // 43
  93     0x80000000000ULL,                         // 44
  94     0x100000000000ULL,                        // 45
  95     0x200000000000ULL,                        // 46
  96     0x400000000000ULL,                        // 47
  97     0x800000000000ULL,                        // 48
  98     0x1000000000000ULL,                       // 49
  99     0x2000000000000ULL,                       // 50
 100     0x4000000000000ULL,                       // 51
 101     0x8000000000000ULL,                       // 52
 102     0x10000000000000ULL,                      // 53
 103     0x20000000000000ULL,                      // 54
 104     0x40000000000000ULL,                      // 55
 105     0x80000000000000ULL,                      // 56
 106     0x100000000000000ULL,                     // 57
 107     0x200000000000000ULL,                     // 58
 108     0x400000000000000ULL,                     // 59
 109     0x800000000000000ULL,                     // 60
 110     0x1000000000000000ULL,                    // 61
 111     0x2000000000000000ULL,                    // 62
 112     0x4000000000000000ULL,                    // 63
 113     0x8000000000000000ULL,                    // 64
 114 };
 115
 116
 117
 118 //
 119 // The white colored squares on the board
 120 //
 121 BITBOARD BBWHITESQ = (
 122     SLOWCOOR_TO_BB(A2) | SLOWCOOR_TO_BB(A4) | SLOWCOOR_TO_BB(A6) |
 123     SLOWCOOR_TO_BB(A8) | SLOWCOOR_TO_BB(B1) | SLOWCOOR_TO_BB(B3) |
 124     SLOWCOOR_TO_BB(B5) | SLOWCOOR_TO_BB(B7) | SLOWCOOR_TO_BB(C2) |
 125     SLOWCOOR_TO_BB(C4) | SLOWCOOR_TO_BB(C6) | SLOWCOOR_TO_BB(C8) |
 126     SLOWCOOR_TO_BB(D1) | SLOWCOOR_TO_BB(D3) | SLOWCOOR_TO_BB(D5) |
 127     SLOWCOOR_TO_BB(D7) | SLOWCOOR_TO_BB(E2) | SLOWCOOR_TO_BB(E4) |
 128     SLOWCOOR_TO_BB(E6) | SLOWCOOR_TO_BB(E8) | SLOWCOOR_TO_BB(F1) |
 129     SLOWCOOR_TO_BB(F3) | SLOWCOOR_TO_BB(F5) | SLOWCOOR_TO_BB(F7) |
 130     SLOWCOOR_TO_BB(G2) | SLOWCOOR_TO_BB(G4) | SLOWCOOR_TO_BB(G6) |
 131     SLOWCOOR_TO_BB(G8) | SLOWCOOR_TO_BB(H1) | SLOWCOOR_TO_BB(H3) |
 132     SLOWCOOR_TO_BB(H5) | SLOWCOOR_TO_BB(H7)
 133     );
 134
 135 //
 136 // The black colored squares on the board
 137 //
 138 BITBOARD BBBLACKSQ = ~(
 139     SLOWCOOR_TO_BB(A2) | SLOWCOOR_TO_BB(A4) | SLOWCOOR_TO_BB(A6) |
 140     SLOWCOOR_TO_BB(A8) | SLOWCOOR_TO_BB(B1) | SLOWCOOR_TO_BB(B3) |
 141     SLOWCOOR_TO_BB(B5) | SLOWCOOR_TO_BB(B7) | SLOWCOOR_TO_BB(C2) |
 142     SLOWCOOR_TO_BB(C4) | SLOWCOOR_TO_BB(C6) | SLOWCOOR_TO_BB(C8) |
 143     SLOWCOOR_TO_BB(D1) | SLOWCOOR_TO_BB(D3) | SLOWCOOR_TO_BB(D5) |
 144     SLOWCOOR_TO_BB(D7) | SLOWCOOR_TO_BB(E2) | SLOWCOOR_TO_BB(E4) |
 145     SLOWCOOR_TO_BB(E6) | SLOWCOOR_TO_BB(E8) | SLOWCOOR_TO_BB(F1) |
 146     SLOWCOOR_TO_BB(F3) | SLOWCOOR_TO_BB(F5) | SLOWCOOR_TO_BB(F7) |
 147     SLOWCOOR_TO_BB(G2) | SLOWCOOR_TO_BB(G4) | SLOWCOOR_TO_BB(G6) |
 148     SLOWCOOR_TO_BB(G8) | SLOWCOOR_TO_BB(H1) | SLOWCOOR_TO_BB(H3) |
 149     SLOWCOOR_TO_BB(H5) | SLOWCOOR_TO_BB(H7)
 150     );
 151
 152
 153 //
 154 // A way to select one file
 155 //
 156 BITBOARD BBFILE[8] = {
 157     BBFILEA,
 158     BBFILEB,
 159     BBFILEC,
 160     BBFILED,
 161     BBFILEE,
 162     BBFILEF,
 163     BBFILEG,
 164     BBFILEH
 165 };
 166
 167 //
 168 // A way to select one rank
 169 //
 170 BITBOARD BBRANK[9] = {
 171     0,
 172     BBRANK11,
 173     BBRANK22,
 174     BBRANK33,
 175     BBRANK44,
 176     BBRANK55,
 177     BBRANK66,
 178     BBRANK77,
 179     BBRANK88
 180 };
 181
 182 //
 183 // Two files: A and H
 184 //
 185 BITBOARD BBROOK_PAWNS = BBFILEA | BBFILEH;
 186
 187
 188 ULONG CDECL
 189 SlowCountBits(BITBOARD bb)
 190 /**
 191
 192 Routine description:
 193
 194     Strictly-C implementation of bit counting.  How many bits are
 195     asserted in a particular bitboard?
 196
 197 Parameters:
 198
 199     BITBOARD bb : the bitboard to count
 200
 201 Return value:
 202
 203     ULONG : number of bits set in bb
 204
 205 **/
 206 {
 207     ULONG uCount = 0;
 208     while(bb)
 209     {
 210         uCount++;
 211         bb &= (bb - 1);
 212     }
 213     return(uCount);
 214 }
 215
 216
 217 static const int foldedTable[] = {
 218     63,30, 3,32,59,14,11,33,
 219     60,24,50, 9,55,19,21,34,
 220     61,29, 2,53,51,23,41,18,
 221     56,28, 1,43,46,27, 0,35,
 222     62,31,58, 4, 5,49,54, 6,
 223     15,52,12,40, 7,42,45,16,
 224     25,57,48,13,10,39, 8,44,
 225     20,47,38,22,17,37,36,26,
 226 };
 227
 228 ULONG CDECL
 229 DeBruijnFirstBit(BITBOARD bb)
 230 {
 231         int folded;
 232     if (bb == 0ULL) return(0);
 233     bb ^= (bb - 1);
 234     folded = ((int)bb) ^ ((int)(bb >> 32));
 235     return foldedTable[(folded * 0x78291ACF) >> 26] + 1;
 236 }
 237
 238 ULONG CDECL
 239 SlowFirstBit(BITBOARD bb)
 240 /**
 241
 242 Routine description:
 243
 244     Strictly-C implementation of "find the number of the first (lowest
 245     order) asserted bit in the bitboard".
 246
 247 Parameters:
 248
 249     BITBOARD bb : the bitboard to test
 250
 251 Return value:
 252
 253     ULONG : the number of the first bit from the low order side of the
 254             bb that is asserted.  The lowest order bit is #1.
 255
 256 **/
 257 {
 258     static ULONG uTable[16] =
 259     { // 0000  0001  0010  0011  0100  0101  0110  0111
 260          0,    1,    2,    1,    3,    1,    2,    1,
 261       // 1000  1001  1010  1011  1100  1101  1110  1111
 262          4,    1,    2,    1,    3,    1,    2,    1 };
 263     ULONG uShifts = 0;
 264     ULONG u;
 265
 266     while(bb)
 267     {
 268         u = (ULONG)bb & 0xF;
 269         if (0 != u)
 270         {
 271             return(uTable[u] + (uShifts * 4));
 272         }
 273         bb >>= 4;
 274         uShifts++;
 275     }
 276     return(0);
 277 }
 278
 279
 280 ULONG CDECL
 281 SlowLastBit(BITBOARD bb)
 282 /**
 283
 284 Routine description:
 285
 286     Strictly-C implementation of "find the number of the last (highest
 287     order) bit asserted in the bitboard".
 288
 289     Note: On every system benchmarked this code sucked.  Using the x86
 290     bsr instruction is way faster on modern x86 family processors.
 291
 292 Parameters:
 293
 294     BITBOARD bb : the bitboard to test
 295
 296 Return value:
 297
 298     ULONG : the number of the first bit from the high order side of bb
 299             that is asserted.  The highest order bit is #64.
 300
 301 **/
 302 {
 303     static ULONG uTable[16] =
 304     { // 0000  0001  0010  0011  0100  0101  0110  0111
 305             0,    1,    2,    2,    3,    3,    3,    3,
 306       // 1000  1001  1010  1011  1100  1101  1110  1111
 307             4,    4,    4,    4,    4,    4,    4,    4 };
 308     ULONG uShifts = 15;
 309     ULONG u;
 310
 311     while(bb)
 312     {
 313         u = (ULONG)((bb & 0xF000000000000000ULL) >> 60);
 314         if (0 != u)
 315         {
 316             return(uTable[u] + (uShifts * 4));
 317         }
 318         bb <<= 4;
 319         uShifts--;
 320         ASSERT(uShifts < 15);
 321     }
 322     return(0);
 323 }
 324
 325 COOR
 326 CoorFromBitBoardRank8ToRank1(BITBOARD *pbb)
 327 /**
 328
 329 Routine description:
 330
 331     Return the square cooresponding to the first asserted bit in the
 332     bitboard or ILLEGAL_COOR if there are no bits asserted in the
 333     bitboard.  If a valid COOR is returned, clear that bit in the
 334     bitboard.
 335
 336 Parameters:
 337
 338     BITBOARD *pbb
 339
 340 Return value:
 341
 342     COOR
 343
 344 **/
 345 {
 346     COOR c = ILLEGAL_COOR;
 347     ULONG uFirstBit = FirstBit(*pbb);
 348
 349     ASSERT(uFirstBit == SlowFirstBit(*pbb));
 350     if (0 != uFirstBit)
 351     {
 352         uFirstBit--; // bit 1 is 1 << 0
 353         c = BIT_NUMBER_TO_COOR(uFirstBit);
 354         ASSERT(c == SLOW_BIT_NUMBER_TO_COOR(uFirstBit));
 355         ASSERT(IS_ON_BOARD(c));
 356         *pbb &= (*pbb - 1);
 357     }
 358     return(c);
 359 }
 360
 361
 362 COOR
 363 CoorFromBitBoardRank1ToRank8(BITBOARD *pbb)
 364 /**
 365
 366 Routine description:
 367
 368     Return the square cooresponding to the last asserted bit in the
 369     bitboard or ILLEGAL_COOR if there are no bits asserted in the
 370     bitboard.  If a valid COOR is returned, clear that bit in the
 371     bitboard.
 372
 373 Parameters:
 374
 375     BITBOARD *pbb
 376
 377 Return value:
 378
 379     COOR
 380
 381 **/
 382 {
 383     COOR c;
 384     ULONG uLastBit = LastBit(*pbb);
 385     ASSERT(SlowLastBit(*pbb) == uLastBit);
 386
 387     c = ILLEGAL_COOR;
 388     if (0 != uLastBit)
 389     {
 390         ASSERT(*pbb);
 391         uLastBit--;
 392         *pbb &= (*pbb - 1);
 393         c = BIT_NUMBER_TO_COOR(uLastBit);
 394         ASSERT(c == SLOW_BIT_NUMBER_TO_COOR(uLastBit));
 395         ASSERT(IS_ON_BOARD(c));
 396     }
 397     return(c);
 398 }