From 75df3785587ab6e7168dd43ccfb3891848e56f59 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Tue, 23 Dec 2008 15:01:25 -0800 Subject: [PATCH] Add faster and better-quality hash function hash_lookup3(). --- lib/hash.c | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/hash.h | 1 + 2 files changed, 63 insertions(+) diff --git a/lib/hash.c b/lib/hash.c index 8e87216b..22caa923 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -44,3 +44,65 @@ hash_fnv(const void *p_, size_t n, uint32_t basis) } return hash; } + +/* This is the public domain lookup3 hash by Bob Jenkins from + * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */ +#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) + +#define mix(a, b, c) \ + do { \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c, 16); c += b; \ + b -= a; b ^= rot(a, 19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ + } while (0) + +#define final(a, b, c) \ + do { \ + c ^= b; c -= rot(b, 14); \ + a ^= c; a -= rot(c, 11); \ + b ^= a; b -= rot(a, 25); \ + c ^= b; c -= rot(b, 16); \ + a ^= c; a -= rot(c, 4); \ + b ^= a; b -= rot(a, 14); \ + c ^= b; c -= rot(b, 24); \ + } while (0) + +/* Returns the hash of the 'n' uint32_t values at 'p', starting from 'basis'. + * Note especially that 'n' is a count of 32-bit words, not bytes, and that + * 'p' must be properly aligned. */ +uint32_t +hash_lookup3(const uint32_t *p, size_t n, uint32_t basis) +{ + uint32_t a, b, c; + + a = b = c = 0xdeadbeef + (((uint32_t) n) << 2) + basis; + + while (n > 3) { + a += p[0]; + b += p[1]; + c += p[2]; + mix(a, b, c); + n -= 3; + p += 3; + } + + switch (n) { + case 3: + c += p[2]; + /* fall through */ + case 2: + b += p[1]; + /* fall through */ + case 1: + a += p[0]; + final(a, b, c); + /* fall through */ + case 0: + break; + } + return c; +} + diff --git a/lib/hash.h b/lib/hash.h index 6fce3471..44d7b054 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -40,5 +40,6 @@ #define HASH_FNV_PRIME UINT32_C(16777619) uint32_t hash_fnv(const void *, size_t, uint32_t basis); +uint32_t hash_lookup3(const uint32_t *, size_t n, uint32_t basis); #endif /* hash.h */ -- 2.30.2