diff options
| -rw-r--r-- | Makefile | 12 | ||||
| -rw-r--r-- | murmurhash.c | 73 | ||||
| -rw-r--r-- | murmurhash.h | 18 | ||||
| -rw-r--r-- | package.json | 9 | ||||
| -rw-r--r-- | test.c | 57 |
5 files changed, 169 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..5a87aa9 --- /dev/null +++ b/Makefile @@ -0,0 +1,12 @@ + +SRC = murmurhash.c +CFLAGS += -std=c99 -Wall -I. + +clean: + rm -f test + +test: + $(CC) test.c $(SRC) $(CFLAGS) -o test + ./test + +.PHONY: test diff --git a/murmurhash.c b/murmurhash.c new file mode 100644 index 0000000..427b3d2 --- /dev/null +++ b/murmurhash.c @@ -0,0 +1,73 @@ + +/** + * `murmurhash.h' - murmurhash + * + * copyright (c) 2014 joseph werle <joseph.werle@gmail.com> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <murmurhash.h> + +uint32_t +murmurhash (const char *key, uint32_t len, uint32_t seed) { + uint32_t c1 = 0xcc9e2d51; + uint32_t c2 = 0x1b873593; + uint32_t r1 = 15; + uint32_t r2 = 13; + uint32_t m = 5; + uint32_t n = 0xe6546b64; + uint32_t h = 0; + uint32_t k = 0; + uint8_t *d = (uint8_t *) key; // 32 bit extract from `key' + const uint32_t *chunks = 0; + const uint8_t *tail = 0; // tail - last 8 bytes + int i = 0; + int l = len / 4; // chunk length + + h = seed; + + chunks = (const uint32_t *) (d + l * 4); // body + tail = (const uint8_t *) (d + l * 4); // last 8 byte chunk of `key' + + // for each 4 byte chunk of `key' + for (i = -l; i != 0; ++i) { + // next 4 byte chunk of `key' + k = chunks[i]; + + // encode next 4 byte chunk of `key' + k *= c1; + k = (k << r1) | (k >> (32 - r1)); + k *= c2; + + // append to hash + h ^= k; + h = (h << r2) | (h >> (32 - r2)); + h = h * m + n; + } + + k = 0; + + // remainder + switch (len & 3) { // `len % 4' + case 3: k ^= (tail[2] << 16); + case 2: k ^= (tail[1] << 8); + + case 1: + k ^= tail[0]; + k *= c1; + k = (k << r1) | (k >> (32 - r1)); + k *= c2; + h ^= k; + } + + h ^= len; + + h ^= (h >> 16); + h *= 0x85ebca6b; + h ^= (h >> 13); + h *= 0xc2b2ae35; + h ^= (h >> 16); + + return h; +} diff --git a/murmurhash.h b/murmurhash.h new file mode 100644 index 0000000..48d39bf --- /dev/null +++ b/murmurhash.h @@ -0,0 +1,18 @@ + +/** + * `murmurhash.h' - murmurhash + * + * copyright (c) 2014 joseph werle <joseph.werle@gmail.com> + */ + +#ifndef MURMURHASH_H +#define MURMURHASH_H 1 + +/** + * + */ + +uint32_t +murmurhash (const char *, uint32_t, uint32_t); + +#endif diff --git a/package.json b/package.json new file mode 100644 index 0000000..940797c --- /dev/null +++ b/package.json @@ -0,0 +1,9 @@ +{ + "name": "murmurhash", + "version": "0.0.1", + "repo": "jwerle/murmurhash.c", + "description": "MurmurHash3 general hash bashed lookup function implementation", + "keywords": ["murmur", "hash", "murmurhash"], + "license": "MIT", + "src": [ "murmurhash.h", "murmurhash.c" ] +} @@ -0,0 +1,57 @@ + +/** + * `test.c' - murmurhash + * + * copyright (c) 2014 joseph werle <joseph.werle@gmail.com> + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <inttypes.h> +#include <assert.h> +#include <murmurhash.h> + +int +main (void) { + uint32_t hash = 0; + uint32_t seed = 0; + +#define t(str, seed, expected) { \ + uint32_t len = (uint32_t) strlen(str); \ + hash = murmurhash(str, len, seed); \ + printf( \ + "['%s'] '%" PRIu32 "' = '%" PRIu32 "'", \ + str, (uint32_t) expected, hash); \ + assert((uint32_t) expected == hash); \ + printf(" ...ok\n"); \ +} + + seed = 0; + t("", seed, 0x00000000); + t("0", seed, 0xd271c07f); + t("01", seed, 0x61ec6600); + t("012", seed, 0xec6cff8c); + t("0123", seed, 0xd41994a0); + t("01234", seed, 0x19d02170); + t("2", seed, 0x0129e217); + t("88", seed, 0x7a0040a5); + + t("asdfqwer", seed, 0xa46b5209); + t("asdfqwerty", seed, 0xa3cfe04b); + t("asd", seed, 0x14570c6f); + + t("Hello", seed, 0x12da77c8); + t("Hello1", seed, 0x6357e0a6); + t("Hello2", seed, 0xe5ce223e); + + t("hey", seed, 0x12f94418); + t("dude", seed, 0xef0487f3); + t("test", seed, 0xba6bd213); + + + seed = 1; + t("", seed, 0x514e28b7); + + return 0; +} |