Fastest bitboard compress routine when you can't use ASM
Posted: Thu May 31, 2007 7:22 pm
One of the problems with bitboard move generators is how to efficiently determine which bits are "on" in a 64 bit move map in order to generate the target squares for a piece when constructing move lists.
Those of you who can drop into assembler can of course use the BSF and BSR opcodes to do this, but I thought you might nonetheless be interested in a technique based on number theory that I have used in ermintrude (which is written in java and so can't use any asm code) that is faster than any other non-assembler technique I've tried. Its so good its almost like magic. Moreover it operates in linear time - no processing huge numbers of zero-bits just to find the one-bits
The idea is to extract each bit field in turn from the 64 bit value, fold it into a 32 bit value, and multiply it by a "magic" number. The top 5 bits of the result is then used as an index into a small lookup table, whose value indicates the bit index (0 - 63) of the bit value - and hence the target square for the move.
Here's the code I use in ermintrude:
The multiplication is probably the slowest parts of the algorithm, as the lookup table itself is small enough to reside in cache memory. I haven't tried factorising the magic number into a sequence of shifts and adds - this might speed it up slightly.
Anyway its' just one of the tricks I've had to resort to in order to get java to perform respectably
Vince
Those of you who can drop into assembler can of course use the BSF and BSR opcodes to do this, but I thought you might nonetheless be interested in a technique based on number theory that I have used in ermintrude (which is written in java and so can't use any asm code) that is faster than any other non-assembler technique I've tried. Its so good its almost like magic. Moreover it operates in linear time - no processing huge numbers of zero-bits just to find the one-bits
The idea is to extract each bit field in turn from the 64 bit value, fold it into a 32 bit value, and multiply it by a "magic" number. The top 5 bits of the result is then used as an index into a small lookup table, whose value indicates the bit index (0 - 63) of the bit value - and hence the target square for the move.
Here's the code I use in ermintrude:
Code: Select all
public static final int tzc64[] = {
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
};
public static int compress(long bb, int[] loc) {
int lo, high;
long v;
int j = 0;
while (bb != 0) {
v = bb ^ (bb-1);
bb &= (bb - 1);
lo = (int)(v >> 32);
high = (int) v;
loc[j++] = tzc64[(0x3f & ((lo ^ high) * 0x78291ACF) >> 26)];
}
loc[j] = -1;
return j;
}
Anyway its' just one of the tricks I've had to resort to in order to get java to perform respectably
Vince