shithub: mc

Download patch

ref: 778aadfc5a73c80a9046250b00a085e074a1870f
parent: 336413341a83ffd0294b16e2debe1ec5132fa19b
author: Ori Bernstein <[email protected]>
date: Tue May 24 21:58:52 EDT 2016 

Improve hash functions.


--- a/test/runtest.sh
+++ b/test/runtest.sh
@@ -10,6 +10,7 @@
 
 function build {
 	rm -f $1 $1.o $1.s $1.use
+	echo mbld -b $1 -C../6/6m -M../muse/muse -I../lib/std -I../lib/sys -r../rt/_myrrt.o $1.myr
 	mbld -b $1 -C../6/6m -M../muse/muse -I../lib/std -I../lib/sys -r../rt/_myrrt.o $1.myr
 }
 
--- a/util/htab.c
+++ b/util/htab.c
@@ -9,7 +9,10 @@
 #include "util.h"
 
 #define Initsz 16
+#define Seed 2928213749
 
+ulong murmurhash2(void *key, size_t len);
+
 /* Creates a new empty hash table, using 'hash' as the
  * hash funciton, and 'cmp' to verify that there are no
  * hash collisions. */
@@ -210,20 +213,11 @@
 ulong strhash(void *_s)
 {
 	char *s;
-	ulong h;
-	ulong g;
 
 	s = _s;
-	h = 0;
-	while (s && *s) {
-		h = ((h << 4) + *s++);
-
-		if ((g = (h & 0xF0000000)))
-			h ^= (g >> 24);
-
-		h &= ~g;
-	}
-	return h;
+	if (!s)
+		return Seed;
+	return murmurhash2(_s, strlen(_s));
 }
 
 int streq(void *a, void *b)
@@ -238,19 +232,11 @@
 ulong strlithash(void *_s)
 {
 	Str *s;
-	ulong h, g, i;
 
 	s = _s;
-	h = 0;
-	for (i = 0; i < s->len; i++) {
-		h = ((h << 4) + s->buf[i]);
-
-		if ((g = (h & 0xF0000000)))
-			h ^= (g >> 24);
-
-		h &= ~g;
-	}
-	return h;
+	if (!s)
+		return Seed;
+	return murmurhash2(s->buf, s->len);
 }
 
 int strliteq(void *_a, void *_b)
@@ -272,17 +258,58 @@
 
 ulong inthash(uint64_t key)
 {
-	uintptr_t h;
+	return murmurhash2(&key, sizeof key);
+}
 
-	h = (uintptr_t)key;
-	h *= 357913941;
-	h ^= h << 24;
-	h += ~357913941;
-	h ^= h >> 31;
-	h ^= h << 31;
-	return h;
+int inteq(uint64_t a, uint64_t b)
+{
+	return a == b;
 }
 
-int inteq(uint64_t a, uint64_t b) { return a == b; }
+int ptreq(void *a, void *b)
+{
+	return a == b;
+}
 
-int ptreq(void *a, void *b) { return a == b; }
+ulong murmurhash2 (void *ptr, size_t len)
+{
+	uint32_t m = 0x5bd1e995;
+	uint32_t r = 24;
+	uint32_t h, k;
+	uint32_t *data;
+	char *buf;
+	
+	buf = ptr;
+	data = (uint32_t*)buf;
+	h = Seed ^ len;
+	while (len >= 4) {
+		k = *data;
+
+		k *= m;
+		k ^= k >> r;
+		k *= m;
+
+		h *= m;
+		h ^= k;
+		data++;
+		len -= sizeof(*data);
+	}
+
+	switch (len) {
+	case 3:
+		h ^= buf[2] << 16;
+	case 2:
+		h ^= buf[1] << 8;
+	case 1:
+		h ^= buf[0] << 0;
+	default:
+		break;
+	};
+	h *= m;
+
+	h ^= h >> 13;
+	h *= m;
+	h ^= h >> 15;
+
+	return h;
+}