hash: Introduce an implementation of murmurhash.

Murmurhash is generally superior to the Jenkins lookup3 hash according to
the available figures.  Perhaps we should generally replace our current
hashes by murmurhash.

For now, I'm introducing a parallel implementation to allow it to be used
in cases where an incremental one-word-at-a-time hash is desirable.  The
first user will be added in an upcoming commit.

Signed-off-by: Ben Pfaff <blp@nicira.com>
Acked-by: Ethan Jackson <ethan@nicira.com>

1 files changed, 15 insertions, 0 deletions

diff --git a/lib/hash.c b/lib/hash.c
index f7aa91633..41ad1bf2f 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -102,3 +102,18 @@ hash_bytes(const void *p_, size_t n, uint32_t basis)
 
     return c;
 }
+
+/* Returns the hash of the 'n' 32-bit words at 'p', starting from 'basis'.
+ * 'p' must be properly aligned. */
+uint32_t
+mhash_words(const uint32_t p[], size_t n_words, uint32_t basis)
+{
+    uint32_t hash;
+    size_t i;
+
+    hash = basis;
+    for (i = 0; i < n_words; i++) {
+        hash = mhash_add(hash, p[i]);
+    }
+    return mhash_finish(hash, n_words);
+}