Author: Dieter Buerssner
Date: 12:49:05 05/28/04
Go up one level in this thread
On May 28, 2004 at 13:22:05, Gerd Isenberg wrote:
>You are almost right, but one additional "and" 0x0f0f0f0f is necessary ;-)
Yes. Sorry, I forgot to mention it (actually I was too lazy, to think about it,
in the code I gave in the URL it is there).
Your trick with the maj() and odd() can make my head spin ...
Can you easily compare it to my try pc_10bb() (population count of 10
bitboards). It seems to work at least. Code follows.
Cheers,
Dieter
#include <stdio.h>
#include <stdlib.h>
typedef unsigned __int64 BitBoard;
__forceinline
unsigned int low (BitBoard x) {return (unsigned int) x;}
__forceinline
unsigned int high(BitBoard x) {return (unsigned int) (x>>32);}
int popCount(BitBoard bb)
{
unsigned int l = low(bb);
unsigned int h = high(bb);
l -= (l >> 1) & 0x55555555; // count 2-bit groups
h -= (h >> 1) & 0x55555555; // count 2-bit groups
l = (l & 0x33333333) + ((l >> 2) & 0x33333333); // count 4-bit groups
h = (h & 0x33333333) + ((h >> 2) & 0x33333333); // count 4-bit groups
l = (l + (l >> 4)) & 0x0f0f0f0f; // count 8-bits groups
h = (h + (h >> 4)) & 0x0f0f0f0f; // count 8-bits groups
return ((h+l) * 0x01010101) >> 24; // sum 8-bit results
}
int pc_10bb(BitBoard x[])
{
unsigned int a, b, c, d, i;
unsigned int *xw = (unsigned int *)x; // Of course not really portable
unsigned int aa[7], *aap=aa;
/* Process first 18 words, do it in triples, because after the
2nd stage, we can combine 3 words without overflow */
i = 6;
do
{
a = *xw++;
a = a - ((a>>1) & 0x55555555);
b = *xw++;
b = b - ((b>>1) & 0x55555555);
c = *xw++;
c = c - ((c>>1) & 0x55555555);
a = (a & 0x33333333) + ((a>>2) & 0x33333333);
b = (b & 0x33333333) + ((b>>2) & 0x33333333);
c = (c & 0x33333333) + ((c>>2) & 0x33333333);
*aap++ = a+b+c;
/* Now we have 4 bit counters with max 12 */
}
while (--i);
/* And the remaining 2 words */
a = *xw++;
a = a - ((a>>1) & 0x55555555);
b = *xw++;
b = b - ((b>>1) & 0x55555555);
a = (a & 0x33333333) + ((a>>2) & 0x33333333);
b = (b & 0x33333333) + ((b>>2) & 0x33333333);
aa[6] = a+b;
/* process the 4 bit counters in aa[] */
a = aa[0];
b = aa[1];
c = aa[2];
d = aa[3];
a = (a & 0x0f0f0f0f) + ((a>>4) & 0x0f0f0f0f);
b = (b & 0x0f0f0f0f) + ((b>>4) & 0x0f0f0f0f);
c = (c & 0x0f0f0f0f) + ((c>>4) & 0x0f0f0f0f);
d = (d & 0x0f0f0f0f) + ((d>>4) & 0x0f0f0f0f);
/* 8-bit counters now have a max of 24. We can add 8 such counters together */
d += a+b+c;
a = aa[4];
b = aa[5];
c = aa[6];
a = (a & 0x0f0f0f0f) + ((a>>4) & 0x0f0f0f0f);
b = (b & 0x0f0f0f0f) + ((b>>4) & 0x0f0f0f0f);
c = (c & 0x0f0f0f0f) + ((c>>4) & 0x0f0f0f0f);
d+=a+b+c;
/* Maybe, it is possible to save some masks in the last 2 steps
but it won't really matter */
d = (d & 0x00ff00ff) + ((d>>8) & 0x00ff00ff);
d = (d & 0x0000ffff) + ((d>>16) & 0x0000ffff);
return d;
}
// some random attack boards
// #define rand() 0xffff
void initDisjointAttacks(BitBoard disjointAtta[10])
{
int i;
srand(0);
for (i = 0; i < 10; i++)
{
disjointAtta[i] = rand();
disjointAtta[i] <<= 16;
disjointAtta[i] |= rand();
disjointAtta[i] <<= 16;
disjointAtta[i] |= rand();
disjointAtta[i] <<= 16;
disjointAtta[i] |= rand();
}
}
__forceinline
BitBoard odd(BitBoard x, BitBoard y, BitBoard z) {
return x^y^z;}
__forceinline
BitBoard maj(BitBoard x, BitBoard y, BitBoard z) {
return ((x^y)&z)|(x&y);}
void determineAttackCounts(BitBoard c[4], const BitBoard a[10])
{
BitBoard t1,t2,u1,u2,v1,v2,w1,w2,x2,y2,y4,z4;
t1 = odd( a[0], a[1], a[2]);
t2 = maj( a[0], a[1], a[2]);
u1 = odd( a[3], a[4], a[5]);
u2 = maj( a[3], a[4], a[5]);
v1 = odd( a[6], a[7], a[8]);
v2 = maj( a[6], a[7], a[8]);
w1 = odd( a[9], t1, u1);
w2 = maj( a[9], t1, u1);
c[0] = odd(v1, w1, 0); // all odds
x2 = maj(v1, w1, 0);
y2 = odd(t2, u2, v2);
y4 = maj(t2, u2, v2);
c[1] = odd(w2, x2, y2);
z4 = maj(w2, x2, y2);
c[2] = odd(y4, z4, 0);
c[3] = maj(y4, z4, 0);
}
int main(void)
{
BitBoard disjointAtta[10]; // up to 15
BitBoard attackCounts[4];
int i, pc1 = 0, pc2 = 0;
initDisjointAttacks(disjointAtta);
determineAttackCounts(attackCounts, disjointAtta);
for (i = 0; i < 10; ++i)
{
pc1 += popCount(disjointAtta[i]);
printf("disjointAtta[%d] 0x%08X%08X\n", i,
high(disjointAtta[i]), low(disjointAtta[i]));
}
printf("==================================\n");
for (i = 0; i < 4; ++i)
{
pc2 += popCount(attackCounts[i]) * (1<<i);
printf("attackCounts[%d] 0x%08X%08X\n", i,
high(attackCounts[i]), low(attackCounts[i]));
}
printf("pc1=%d, pc2=%d pc3=%d\n", pc1, pc2, pc_10bb(disjointAtta));
getchar();
return 0;
}
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.