#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,
#else // if !defined(IS_64BIT)
+const uint32_t DeBruijnMagic = 0x783A9B23;
+
const uint64_t BMult[64] = {
0x54142844C6A22981ULL, 0x710358A6EA25C19EULL, 0x704F746D63A4A8DCULL,
0xBFED1A0B80F838C5ULL, 0x90561D5631E62110ULL, 0x2804260376E60944ULL,
#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[]);
}
#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
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;
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);
- }
- }
-
}
projects / stockfish / blobdiff