Author: Dann Corbit
Date: 23:40:15 06/14/01
Suppose that you have a chessboard represented as 64 characters, and you want to
make a hash from it. This works well, if you make a 64 bit hash by hashing the
first 32 characters and then the second 32 characters to make two 32 bit chunks.
It was quite a bit faster than Zobrist hashing. On the other hand, it cannot
be used to do incremental updates, so you might be sorry you used it if you
decide to go that route.
/*
--------------------------------------------------------------------
fhash.h, originally by Bob Jenkins, December 1996
hash2() and mix() are externally useful functions.
You can use this free for any purpose. It has no warranty.
Dann Corbit messed around with this suff. It has been changed for
hashing fixed sizes using a single technique.
--------------------------------------------------------------------
*/
/*
--------------------------------------------------------------------
mix -- mix 3 32-bit values reversibly.
For every delta with one or two bit set, and the deltas of all three
high bits or all three low bits, whether the original value of a,b,c
is almost all zero or is uniformly distributed,
* If mix() is run forward or backward, at least 32 bits in a,b,c
have at least 1/4 probability of changing.
* If mix() is run forward, every bit of c will change between 1/3 and
2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
mix() was built out of 36 single-cycle latency instructions in a
structure that could supported 2x parallelism, like so:
a -= b;
a -= c; x = (c>>13);
b -= c; a ^= x;
b -= a; x = (a<<8);
c -= a; b ^= x;
c -= b; x = (b>>13);
...
Unfortunately, superscalar Pentiums and Sparcs can't take advantage
of that parallelism. They've also turned some of those single-cycle
latency instructions into multi-cycle latency instructions. Still,
this is the fastest good hash I could find. There were about 2^^68
to choose from. I only looked at a billion or so.
--------------------------------------------------------------------
*/
#define mix(a,b,c) \
{ \
a -= b; a -= c; a ^= (c>>13); \
b -= c; b -= a; b ^= (a<<8); \
c -= a; c -= b; c ^= (b>>13); \
a -= b; a -= c; a ^= (c>>12); \
b -= c; b -= a; b ^= (a<<16); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>3); \
b -= c; b -= a; b ^= (a<<10); \
c -= a; c -= b; c ^= (b>>15); \
}
/*
--------------------------------------------------------------------
This works on all machines, is identical to hash() on little-endian
machines, and it is much faster than hash(), but it requires
-- that the key be an array of unsigned long's,
-- that all your machines have the same endianness (to share hashes)
--------------------------------------------------------------------
*/
unsigned long hash2(unsigned long register *k)
{
unsigned long register
a,
b,
c;
/* Set up the internal state */
a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
a += k[0];
b += k[1];
c = k[2];
mix(a, b, c);
a += k[3];
b += k[4];
c += k[5];
mix(a, b, c);
c += 8;
b += k[6];
a += k[7];
mix(a, b, c);
return c;
}
This page took 0 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.