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; }

- Re: A fast hash -- assuming you are not planning to do incremental updates
**martin fierz***02:09:35 06/15/01*- Re: A fast hash -- assuming you are not planning to do incremental updates
**Dann Corbit***02:19:42 06/15/01*- Re: A fast hash -- assuming you are not planning to do incremental updates
**martin fierz***03:00:23 06/15/01*

- Re: A fast hash -- assuming you are not planning to do incremental updates

- Re: A fast hash -- assuming you are not planning to do incremental updates

This page took 0.04 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.