From d9d3c714351b82cfd387fc6f83d89591909312a2 Mon Sep 17 00:00:00 2001 From: Jo-Philipp Wich Date: Thu, 9 Jul 2009 15:04:27 +0000 Subject: libs: introduce lmo - Lua Machine Objects, an implementation of binary hash tables --- libs/lmo/src/lmo_hash.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) create mode 100644 libs/lmo/src/lmo_hash.c (limited to 'libs/lmo/src/lmo_hash.c') diff --git a/libs/lmo/src/lmo_hash.c b/libs/lmo/src/lmo_hash.c new file mode 100644 index 0000000000..bc8e6fe4ed --- /dev/null +++ b/libs/lmo/src/lmo_hash.c @@ -0,0 +1,53 @@ +/* + * Hash function from http://www.azillionmonkeys.com/qed/hash.html + * Copyright (C) 2004-2008 by Paul Hsieh + */ + +#include "lmo.h" + +uint32_t sfh_hash(const char * data, int len) +{ + uint32_t hash = len, tmp; + int rem; + + if (len <= 0 || data == NULL) return 0; + + rem = len & 3; + len >>= 2; + + /* Main loop */ + for (;len > 0; len--) { + hash += sfh_get16(data); + tmp = (sfh_get16(data+2) << 11) ^ hash; + hash = (hash << 16) ^ tmp; + data += 2*sizeof(uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) { + case 3: hash += sfh_get16(data); + hash ^= hash << 16; + hash ^= data[sizeof(uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: hash += sfh_get16(data); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: hash += *data; + hash ^= hash << 10; + hash += hash >> 1; + } + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return hash; +} + -- cgit v1.2.3