From 2b280891fb53250056cf3d333a8f53b92303ee55 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 27 Feb 2009 16:54:38 -0800 Subject: [PATCH] hash: Make hash function pieces available to other modules. This way, modules that want to implement hash functions on their own terms, for performance (e.g. the classifier), do not have to duplicate the code. --- lib/hash.c | 33 ++++----------------------------- lib/hash.h | 26 ++++++++++++++++++++++++++ 2 files changed, 30 insertions(+), 29 deletions(-) diff --git a/lib/hash.c b/lib/hash.c index 104ce224..ebf3d534 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -34,31 +34,6 @@ #include "hash.h" #include -/* 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' 32-bit words at 'p', starting from 'basis'. * 'p' must be properly aligned. */ uint32_t @@ -72,7 +47,7 @@ hash_words(const uint32_t *p, size_t n, uint32_t basis) a += p[0]; b += p[1]; c += p[2]; - mix(a, b, c); + HASH_MIX(a, b, c); n -= 3; p += 3; } @@ -86,7 +61,7 @@ hash_words(const uint32_t *p, size_t n, uint32_t basis) /* fall through */ case 1: a += p[0]; - final(a, b, c); + HASH_FINAL(a, b, c); /* fall through */ case 0: break; @@ -109,7 +84,7 @@ hash_bytes(const void *p_, size_t n, uint32_t basis) a += tmp[0]; b += tmp[1]; c += tmp[2]; - mix(a, b, c); + HASH_MIX(a, b, c); n -= sizeof tmp; p += sizeof tmp; } @@ -120,7 +95,7 @@ hash_bytes(const void *p_, size_t n, uint32_t basis) a += tmp[0]; b += tmp[1]; c += tmp[2]; - final(a, b, c); + HASH_FINAL(a, b, c); } return c; diff --git a/lib/hash.h b/lib/hash.h index a52d8ca7..e1393ddf 100644 --- a/lib/hash.h +++ b/lib/hash.h @@ -36,6 +36,32 @@ #include #include +/* This is the public domain lookup3 hash by Bob Jenkins from + * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */ + +#define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) + +#define HASH_MIX(a, b, c) \ + do { \ + a -= c; a ^= HASH_ROT(c, 4); c += b; \ + b -= a; b ^= HASH_ROT(a, 6); a += c; \ + c -= b; c ^= HASH_ROT(b, 8); b += a; \ + a -= c; a ^= HASH_ROT(c, 16); c += b; \ + b -= a; b ^= HASH_ROT(a, 19); a += c; \ + c -= b; c ^= HASH_ROT(b, 4); b += a; \ + } while (0) + +#define HASH_FINAL(a, b, c) \ + do { \ + c ^= b; c -= HASH_ROT(b, 14); \ + a ^= c; a -= HASH_ROT(c, 11); \ + b ^= a; b -= HASH_ROT(a, 25); \ + c ^= b; c -= HASH_ROT(b, 16); \ + a ^= c; a -= HASH_ROT(c, 4); \ + b ^= a; b -= HASH_ROT(a, 14); \ + c ^= b; c -= HASH_ROT(b, 24); \ + } while (0) + uint32_t hash_words(const uint32_t *, size_t n_word, uint32_t basis); uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis); -- 2.30.2