From 3fd43cd5fcb22bb65bf2a92a25d95d801b11c9e0 Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Wed, 1 Jun 2016 18:58:58 -0700 Subject: Initial checkin for typhoon chess engine. --- src/bitboard.c | 398 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 398 insertions(+) create mode 100755 src/bitboard.c (limited to 'src/bitboard.c') diff --git a/src/bitboard.c b/src/bitboard.c new file mode 100755 index 0000000..0478fc1 --- /dev/null +++ b/src/bitboard.c @@ -0,0 +1,398 @@ +/** + +Copyright (c) Scott Gasch + +Module Name: + + bitboard.c + +Abstract: + + Routines dealing with bitboards. If you build with the + testbitboard.c code enabled it will give you a rough benchmark of + these routines' speeds. Here are some typical results (from a + 1.5ghz Athlon): + + SLOWCOOR_TO_BB: 10 cycles/op + COOR_TO_BB: 5 cycles/op + SlowCountBits: 82 cycles/op + CountBits: 2 cycles/op + SlowLastBit: 158 cycles/op + LastBit: 2 cycles/op + SlowFirstBit: 22 cycles/op + FirstBit: 2 cycles/op + + As you can see the inline assembly language code is quite a bit + faster so use it if you can. And if, on the off chance, you are + porting this code to another hardware platform, it might be worth + your time to research what your instruction set has in the way of + bit twiddling opcodes. + +Author: + + Scott Gasch (scott.gasch@gmail.com) 19 Jun 2004 + +Revision History: + + $Id: bitboard.c 345 2007-12-02 22:56:42Z scott $ + +**/ + +#include "chess.h" + + +// +// Mapping from square -> bit +// +BITBOARD BBSQUARE[64] = +{ + 0x1ULL, // 1 + 0x2ULL, // 2 + 0x4ULL, // 3 + 0x8ULL, // 4 + 0x10ULL, // 5 + 0x20ULL, // 6 + 0x40ULL, // 7 + 0x80ULL, // 8 + 0x100ULL, // 9 + 0x200ULL, // 10 + 0x400ULL, // 11 + 0x800ULL, // 12 + 0x1000ULL, // 13 + 0x2000ULL, // 14 + 0x4000ULL, // 15 + 0x8000ULL, // 16 + 0x10000ULL, // 17 + 0x20000ULL, // 18 + 0x40000ULL, // 19 + 0x80000ULL, // 20 + 0x100000ULL, // 21 + 0x200000ULL, // 22 + 0x400000ULL, // 23 + 0x800000ULL, // 24 + 0x1000000ULL, // 25 + 0x2000000ULL, // 26 + 0x4000000ULL, // 27 + 0x8000000ULL, // 28 + 0x10000000ULL, // 29 + 0x20000000ULL, // 30 + 0x40000000ULL, // 31 + 0x80000000ULL, // 32 +//-------------------------------------------------- + 0x100000000ULL, // 33 + 0x200000000ULL, // 34 + 0x400000000ULL, // 35 + 0x800000000ULL, // 36 + 0x1000000000ULL, // 37 + 0x2000000000ULL, // 38 + 0x4000000000ULL, // 39 + 0x8000000000ULL, // 40 + 0x10000000000ULL, // 41 + 0x20000000000ULL, // 42 + 0x40000000000ULL, // 43 + 0x80000000000ULL, // 44 + 0x100000000000ULL, // 45 + 0x200000000000ULL, // 46 + 0x400000000000ULL, // 47 + 0x800000000000ULL, // 48 + 0x1000000000000ULL, // 49 + 0x2000000000000ULL, // 50 + 0x4000000000000ULL, // 51 + 0x8000000000000ULL, // 52 + 0x10000000000000ULL, // 53 + 0x20000000000000ULL, // 54 + 0x40000000000000ULL, // 55 + 0x80000000000000ULL, // 56 + 0x100000000000000ULL, // 57 + 0x200000000000000ULL, // 58 + 0x400000000000000ULL, // 59 + 0x800000000000000ULL, // 60 + 0x1000000000000000ULL, // 61 + 0x2000000000000000ULL, // 62 + 0x4000000000000000ULL, // 63 + 0x8000000000000000ULL, // 64 +}; + + + +// +// The white colored squares on the board +// +BITBOARD BBWHITESQ = ( + SLOWCOOR_TO_BB(A2) | SLOWCOOR_TO_BB(A4) | SLOWCOOR_TO_BB(A6) | + SLOWCOOR_TO_BB(A8) | SLOWCOOR_TO_BB(B1) | SLOWCOOR_TO_BB(B3) | + SLOWCOOR_TO_BB(B5) | SLOWCOOR_TO_BB(B7) | SLOWCOOR_TO_BB(C2) | + SLOWCOOR_TO_BB(C4) | SLOWCOOR_TO_BB(C6) | SLOWCOOR_TO_BB(C8) | + SLOWCOOR_TO_BB(D1) | SLOWCOOR_TO_BB(D3) | SLOWCOOR_TO_BB(D5) | + SLOWCOOR_TO_BB(D7) | SLOWCOOR_TO_BB(E2) | SLOWCOOR_TO_BB(E4) | + SLOWCOOR_TO_BB(E6) | SLOWCOOR_TO_BB(E8) | SLOWCOOR_TO_BB(F1) | + SLOWCOOR_TO_BB(F3) | SLOWCOOR_TO_BB(F5) | SLOWCOOR_TO_BB(F7) | + SLOWCOOR_TO_BB(G2) | SLOWCOOR_TO_BB(G4) | SLOWCOOR_TO_BB(G6) | + SLOWCOOR_TO_BB(G8) | SLOWCOOR_TO_BB(H1) | SLOWCOOR_TO_BB(H3) | + SLOWCOOR_TO_BB(H5) | SLOWCOOR_TO_BB(H7) + ); + +// +// The black colored squares on the board +// +BITBOARD BBBLACKSQ = ~( + SLOWCOOR_TO_BB(A2) | SLOWCOOR_TO_BB(A4) | SLOWCOOR_TO_BB(A6) | + SLOWCOOR_TO_BB(A8) | SLOWCOOR_TO_BB(B1) | SLOWCOOR_TO_BB(B3) | + SLOWCOOR_TO_BB(B5) | SLOWCOOR_TO_BB(B7) | SLOWCOOR_TO_BB(C2) | + SLOWCOOR_TO_BB(C4) | SLOWCOOR_TO_BB(C6) | SLOWCOOR_TO_BB(C8) | + SLOWCOOR_TO_BB(D1) | SLOWCOOR_TO_BB(D3) | SLOWCOOR_TO_BB(D5) | + SLOWCOOR_TO_BB(D7) | SLOWCOOR_TO_BB(E2) | SLOWCOOR_TO_BB(E4) | + SLOWCOOR_TO_BB(E6) | SLOWCOOR_TO_BB(E8) | SLOWCOOR_TO_BB(F1) | + SLOWCOOR_TO_BB(F3) | SLOWCOOR_TO_BB(F5) | SLOWCOOR_TO_BB(F7) | + SLOWCOOR_TO_BB(G2) | SLOWCOOR_TO_BB(G4) | SLOWCOOR_TO_BB(G6) | + SLOWCOOR_TO_BB(G8) | SLOWCOOR_TO_BB(H1) | SLOWCOOR_TO_BB(H3) | + SLOWCOOR_TO_BB(H5) | SLOWCOOR_TO_BB(H7) + ); + + +// +// A way to select one file +// +BITBOARD BBFILE[8] = { + BBFILEA, + BBFILEB, + BBFILEC, + BBFILED, + BBFILEE, + BBFILEF, + BBFILEG, + BBFILEH +}; + +// +// A way to select one rank +// +BITBOARD BBRANK[9] = { + 0, + BBRANK11, + BBRANK22, + BBRANK33, + BBRANK44, + BBRANK55, + BBRANK66, + BBRANK77, + BBRANK88 +}; + +// +// Two files: A and H +// +BITBOARD BBROOK_PAWNS = BBFILEA | BBFILEH; + + +ULONG CDECL +SlowCountBits(BITBOARD bb) +/** + +Routine description: + + Strictly-C implementation of bit counting. How many bits are + asserted in a particular bitboard? + +Parameters: + + BITBOARD bb : the bitboard to count + +Return value: + + ULONG : number of bits set in bb + +**/ +{ + ULONG uCount = 0; + while(bb) + { + uCount++; + bb &= (bb - 1); + } + return(uCount); +} + + +static const int foldedTable[] = { + 63,30, 3,32,59,14,11,33, + 60,24,50, 9,55,19,21,34, + 61,29, 2,53,51,23,41,18, + 56,28, 1,43,46,27, 0,35, + 62,31,58, 4, 5,49,54, 6, + 15,52,12,40, 7,42,45,16, + 25,57,48,13,10,39, 8,44, + 20,47,38,22,17,37,36,26, +}; + +ULONG CDECL +DeBruijnFirstBit(BITBOARD bb) +{ + int folded; + if (bb == 0ULL) return(0); + bb ^= (bb - 1); + folded = ((int)bb) ^ ((int)(bb >> 32)); + return foldedTable[(folded * 0x78291ACF) >> 26] + 1; +} + +ULONG CDECL +SlowFirstBit(BITBOARD bb) +/** + +Routine description: + + Strictly-C implementation of "find the number of the first (lowest + order) asserted bit in the bitboard". + +Parameters: + + BITBOARD bb : the bitboard to test + +Return value: + + ULONG : the number of the first bit from the low order side of the + bb that is asserted. The lowest order bit is #1. + +**/ +{ + static ULONG uTable[16] = + { // 0000 0001 0010 0011 0100 0101 0110 0111 + 0, 1, 2, 1, 3, 1, 2, 1, + // 1000 1001 1010 1011 1100 1101 1110 1111 + 4, 1, 2, 1, 3, 1, 2, 1 }; + ULONG uShifts = 0; + ULONG u; + + while(bb) + { + u = (ULONG)bb & 0xF; + if (0 != u) + { + return(uTable[u] + (uShifts * 4)); + } + bb >>= 4; + uShifts++; + } + return(0); +} + + +ULONG CDECL +SlowLastBit(BITBOARD bb) +/** + +Routine description: + + Strictly-C implementation of "find the number of the last (highest + order) bit asserted in the bitboard". + + Note: On every system benchmarked this code sucked. Using the x86 + bsr instruction is way faster on modern x86 family processors. + +Parameters: + + BITBOARD bb : the bitboard to test + +Return value: + + ULONG : the number of the first bit from the high order side of bb + that is asserted. The highest order bit is #64. + +**/ +{ + static ULONG uTable[16] = + { // 0000 0001 0010 0011 0100 0101 0110 0111 + 0, 1, 2, 2, 3, 3, 3, 3, + // 1000 1001 1010 1011 1100 1101 1110 1111 + 4, 4, 4, 4, 4, 4, 4, 4 }; + ULONG uShifts = 15; + ULONG u; + + while(bb) + { + u = (ULONG)((bb & 0xF000000000000000ULL) >> 60); + if (0 != u) + { + return(uTable[u] + (uShifts * 4)); + } + bb <<= 4; + uShifts--; + ASSERT(uShifts < 15); + } + return(0); +} + +COOR +CoorFromBitBoardRank8ToRank1(BITBOARD *pbb) +/** + +Routine description: + + Return the square cooresponding to the first asserted bit in the + bitboard or ILLEGAL_COOR if there are no bits asserted in the + bitboard. If a valid COOR is returned, clear that bit in the + bitboard. + +Parameters: + + BITBOARD *pbb + +Return value: + + COOR + +**/ +{ + COOR c = ILLEGAL_COOR; + ULONG uFirstBit = FirstBit(*pbb); + + ASSERT(uFirstBit == SlowFirstBit(*pbb)); + if (0 != uFirstBit) + { + uFirstBit--; // bit 1 is 1 << 0 + c = BIT_NUMBER_TO_COOR(uFirstBit); + ASSERT(c == SLOW_BIT_NUMBER_TO_COOR(uFirstBit)); + ASSERT(IS_ON_BOARD(c)); + *pbb &= (*pbb - 1); + } + return(c); +} + + +COOR +CoorFromBitBoardRank1ToRank8(BITBOARD *pbb) +/** + +Routine description: + + Return the square cooresponding to the last asserted bit in the + bitboard or ILLEGAL_COOR if there are no bits asserted in the + bitboard. If a valid COOR is returned, clear that bit in the + bitboard. + +Parameters: + + BITBOARD *pbb + +Return value: + + COOR + +**/ +{ + COOR c; + ULONG uLastBit = LastBit(*pbb); + ASSERT(SlowLastBit(*pbb) == uLastBit); + + c = ILLEGAL_COOR; + if (0 != uLastBit) + { + ASSERT(*pbb); + uLastBit--; + *pbb &= (*pbb - 1); + c = BIT_NUMBER_TO_COOR(uLastBit); + ASSERT(c == SLOW_BIT_NUMBER_TO_COOR(uLastBit)); + ASSERT(IS_ON_BOARD(c)); + } + return(c); +} -- cgit v1.3