[Mesa-dev] [PATCH 7/8] util: Add murmur3 hashing function

[Thomas Helland]

Copy-pasta from the wikipedia article.

Results from oprofile on a shader-db run:
mesa_hash_data	        3.25 ---> 3.11
hash_table_insert       2.52 ---> 2.52
hash_table_search       2.64 ---> 2.64
set_add	                1.65 ---> 1.74
set_search              2.07 ---> 2.08
runtime	                160  ---> 160
---
 src/util/hash_table.c |  5 ++---
 src/util/hash_table.h | 54 +++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 56 insertions(+), 3 deletions(-)

diff --git a/src/util/hash_table.c b/src/util/hash_table.c
index 8216869..f2b8cf6 100644
--- a/src/util/hash_table.c
+++ b/src/util/hash_table.c
@@ -436,8 +436,7 @@ _mesa_hash_table_random_entry(struct hash_table *ht,
 uint32_t
 _mesa_hash_data(const void *data, size_t size)
 {
-   return _mesa_fnv32_1a_accumulate_block(_mesa_fnv32_1a_offset_bias,
-                                          data, size);
+   return murmur3_32(data, size, _mesa_fnv32_1a_offset_bias);
 }
 
 /** FNV-1a string hash implementation */
@@ -447,7 +446,7 @@ _mesa_hash_string(const char *key)
    uint32_t hash = _mesa_fnv32_1a_offset_bias;
 
    while (*key != 0) {
-      hash = _mesa_fnv32_1a_accumulate(hash, *key);
+      hash = _mesa_murmur3_32(hash, *key);
       key++;
    }
 
diff --git a/src/util/hash_table.h b/src/util/hash_table.h
index 6d41338..288e205 100644
--- a/src/util/hash_table.h
+++ b/src/util/hash_table.h
@@ -119,6 +119,60 @@ _mesa_fnv32_1a_accumulate_block(uint32_t hash, const void *data, size_t size)
 #define _mesa_fnv32_1a_accumulate(hash, expr) \
    _mesa_fnv32_1a_accumulate_block(hash, &(expr), sizeof(expr))
 
+#define _mesa_murmur3_32(hash, expr) \
+   murmur3_32(&(expr), sizeof(expr), hash)
+
+static inline
+uint32_t murmur3_32(const char *key, uint32_t len, uint32_t seed) {
+   static const uint32_t c1 = 0xcc9e2d51;
+   static const uint32_t c2 = 0x1b873593;
+   static const uint32_t r1 = 15;
+   static const uint32_t r2 = 13;
+   static const uint32_t m = 5;
+   static const uint32_t n = 0xe6546b64;
+
+   uint32_t hash = seed;
+
+   const int nblocks = len / 4;
+   const uint32_t *blocks = (const uint32_t *) key;
+   int i;
+   for (i = 0; i < nblocks; i++) {
+      uint32_t k = blocks[i];
+      k *= c1;
+      k = (k << r1) | (k >> (32 - r1));
+      k *= c2;
+
+      hash ^= k;
+      hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
+   }
+
+   const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);
+   uint32_t k1 = 0;
+
+   switch (len & 3) {
+   case 3:
+      k1 ^= tail[2] << 16;
+   case 2:
+      k1 ^= tail[1] << 8;
+   case 1:
+      k1 ^= tail[0];
+
+      k1 *= c1;
+      k1 = (k1 << r1) | (k1 >> (32 - r1));
+      k1 *= c2;
+      hash ^= k1;
+   }
+
+   hash ^= len;
+   hash ^= (hash >> 16);
+   hash *= 0x85ebca6b;
+   hash ^= (hash >> 13);
+   hash *= 0xc2b2ae35;
+   hash ^= (hash >> 16);
+
+   return hash;
+}
+
 /**
  * This foreach function is safe against deletion (which just replaces
  * an entry's data with the deleted marker), but not against insertion
-- 
2.2.1