Code: Select all
#define SIZE (1<<27)
long long int Zob[12*64];
int lock[SIZE];
int cnt;
test(int d, int n, long long int k)
{
int i, j, m;
if(d==0)
{
i = k & SIZE-1; // Ignore 5 bits of index part of key
j = k >> 32 | 0x3FF; // Ignore 10 bits of signature part
// (effective key length = 49 bits)
while(lock[i])
{
if(lock[i] == j)
{ printf("%3d. collission %llx\n", cnt++, k);
break;
} else i = i+1 & SIZE-1;
}
lock[i] = j;
return;
}
for(i=n; i<12*64; i++)
{
test(d-1, i+1, k^Zob[i]);
}
}
main()
{
int i, j, k, cnt=0;
// initialize Zobrist key table
for(i=0; i<64*12; i++)
Zob[i] = ((long long int) rand()) << 33 ^
((long long int) rand()) << 22 ^
((long long int) rand()) << 11 ^
((long long int) rand()) ^
((long long int) rand()) >> 11;
Zob[32] = Zob[31] ^ 0x100000; // try to make bad one
// Screen all permutations of 3 keys for duplicates
// (equivalent to screening all permutations of 6 keys for zero)
test(3, 0, 0);
}
To make it interesting, I shortened the key length to 49 bits. (With a 64-bit key one would expect only collisions with combinations of 9 or more keys, and to test that would take much too long).
I took a Zobrist table of 12*64 = 768 randoms. his give (768*767*766)/6 ~75 million combinations of 3. The probability that any two of these combinations are the same (in the 49 bits I consider) is 1/2^49 (=1.77e-15). There are 75M^2/2 (=2.8e15) pairs of combinations, though. S the number of expected collisions is 5.
In practice I find 6, which is in good ageement.
Now I try to spoil the set by intentionally including two keys (nr 31 and 32) with a very small Hamming distance, only 1 bit different. The result is 7 collisions, the old 6 (which apparently did not involve key #32), and a single new one. Not significantly different. If I would make #32 by XORing #31 by 0x200000 in stead of 0x100000, the number of collisions remains 6.
So indeed, Hamming distance seems irrelevant. Unless it is zero, of course, where it is just a complicated way of saying that two keys are equal.
