1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
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 ([email protected]) 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);
}
|
