diff options
Diffstat (limited to 'common/hash.c')
-rw-r--r-- | common/hash.c | 126 |
1 files changed, 126 insertions, 0 deletions
diff --git a/common/hash.c b/common/hash.c index 59548fa..2041f1f 100644 --- a/common/hash.c +++ b/common/hash.c @@ -540,3 +540,129 @@ p11_hash_md5 (unsigned char *hash, md5_final (&md5, hash); md5_invalidate (&md5); } + +/* + * MurmurHash.c + * MYUtilities + * + * This file created by Jens Alfke on 3/17/08. + * Algorithm & source code by Austin Appleby, released to public domain. + * <http://murmurhash.googlepages.com/> + * Downloaded 3/16/2008. + * Modified slightly by Jens Alfke (use standard uint32_t and size_t types; + * change 'm' and 'r' to #defines for better C compatibility.) + * + */ + +/*----------------------------------------------------------------------------- + * MurmurHash2, by Austin Appleby + * + * Note - This code makes a few assumptions about how your machine behaves - + * + * 1. We can read a 4-byte value from any address without crashing + * 2. sizeof(int) == 4 **Jens: I fixed this by changing 'unsigned int' to 'uint32_t'** + * + * And it has a few limitations - + * + * 1. It will not work incrementally. + * 2. It will not produce the same results on little-endian and big-endian + * machines. + */ + +void +p11_hash_murmur2 (void *hash, + const void *input, + size_t len, + ...) +{ + /* + * 'm' and 'r' are mixing constants generated offline. + * They're not really 'magic', they just happen to work well. + * seed is arbitrarily chosen + */ + + #define m 0x5bd1e995 + #define r 24 + #define seed 42 + + const unsigned char * data = input; + unsigned char overflow[4]; + va_list va; + uint32_t h; + + /* Initialize the hash based on the length */ + va_start (va, len); + h = len; + while (va_arg (va, const void *)) + h += va_arg (va, size_t); + h ^= seed; + va_end (va); + + /* Mix 4 bytes at a time into the hash */ + va_start (va, len); + for (;;) { + uint32_t k; + + if (len >= 4) { + k = *(uint32_t *)data; + data += 4; + len -= 4; + + } else { + size_t num = len; + memcpy (overflow, data, len); + + while (num < 4) { + size_t part; + + data = va_arg (va, const void *); + if (!data) + break; + + /* Combine uint32 from old and new */ + len = va_arg (va, size_t); + part = 4 - num; + if (part > len) + part = len; + memcpy (overflow + num, data, part); + data += part; + len -= part; + num += part; + } + + if (num < 4) { + len = num; + break; + } + + k = *(uint32_t *)overflow; + } + + k *= m; + k ^= k >> r; + k *= m; + + h *= m; + h ^= k; + } + va_end (va); + + /* Handle the last few bytes of the input array */ + switch(len) { + case 3: h ^= overflow[2] << 16; + case 2: h ^= overflow[1] << 8; + case 1: h ^= overflow[0]; + h *= m; + }; + + /* + * Do a few final mixes of the hash to ensure the last few + * bytes are well-incorporated. + */ + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + assert (sizeof (h) == P11_HASH_MURMUR2_LEN); + memcpy (hash, &h, sizeof (h)); +} |