shithub: mc

Download patch

ref: 63b175e2da14c72d77f329f05385402104ef0fc7
parent: e5b424be893e7f771456a548ab66e1bcb7ed50d3
author: Lucas Gabriel Vuotto <[email protected]>
date: Thu Sep 7 21:19:42 EDT 2017

Replace murmurhash with siphash

Signed-off-by: Lucas Gabriel Vuotto <[email protected]>

--- a/lib/std/bitset.myr
+++ b/lib/std/bitset.myr
@@ -30,7 +30,7 @@
 	const bsunion	: (a : bitset#, b : bitset# -> void)
 	const bseq	: (a : bitset#, b : bitset# -> bool)
 	const bsissubset	: (a : bitset#, b : bitset# -> bool)
-	const bshash	: (a : bitset# -> uint32)
+	const bshash	: (a : bitset# -> uint64)
 
 	type bsiter = struct
 		idx	: size
--- a/lib/std/hashfuncs.myr
+++ b/lib/std/hashfuncs.myr
@@ -8,25 +8,25 @@
 use "utf"
 
 pkg std =
-	const strhash	: (s : byte[:]	-> uint32)
+	const strhash	: (s : byte[:]	-> uint64)
 	const streq	: (a : byte[:], b : byte[:]	-> bool)
 
-	const strcasehash	: (s : byte[:]	-> uint32)
+	const strcasehash	: (s : byte[:]	-> uint64)
 	const strcaseeq	: (a : byte[:], b : byte[:]	-> bool)
 
-	generic ptrhash	: (p : @a#	-> uint32)
+	generic ptrhash	: (p : @a#	-> uint64)
 	generic ptreq	: (a : @a#, b : @a#	-> bool)
 
-	generic inthash	: (v : @a::(integral,numeric)	-> uint32)
+	generic inthash	: (v : @a::(integral,numeric)	-> uint64)
 	generic inteq	: (a : @a::(integral,numeric), b : @a::(integral,numeric) -> bool)
 
 	const murmurhash2	: (data : byte[:], seed : uint32 -> uint32)
 	const siphash24	: (data : byte[:], seed : byte[16] -> uint64)
 
-	generic slhash	: (sl : @a[:] -> uint32)
+	generic slhash	: (sl : @a[:] -> uint64)
 ;;
 
-const Seed = 1234
+const Seed : byte[16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
 
 generic slhash = {data : @a[:]
 	-> strhash(slbytes(data))
@@ -40,7 +40,7 @@
 }
 
 const strhash = {s
-	-> murmurhash2(s, Seed)
+	-> siphash24(s, Seed)
 }
 
 const strcaseeq = {a, b
@@ -68,7 +68,7 @@
 		(c, s) = std.strstep(s)
 		std.slpush(&chars, std.tolower(c))
 	;;
-	h = murmurhash2(slbytes(chars), Seed)
+	h = siphash24(slbytes(chars), Seed)
 	slfree(chars)
 	-> h
 }
@@ -81,7 +81,7 @@
 	var x
 
 	x = (&p : byte#)
-	-> murmurhash2(x[0:sizeof(@a#)], Seed)
+	-> siphash24(x[0:sizeof(@a#)], Seed)
 }
 
 generic ptreq = {a, b
@@ -92,7 +92,7 @@
 	var p
 
 	p = (&v : byte#)
-	-> murmurhash2(p[0:sizeof(@a)], Seed)
+	-> siphash24(p[0:sizeof(@a)], Seed)
 }
 
 generic inteq = {a, b
--- a/lib/std/htab.myr
+++ b/lib/std/htab.myr
@@ -6,7 +6,7 @@
 
 pkg std =
 	type htab(@k, @v) = struct
-		hash	: (k : @k	-> uint32)
+		hash	: (k : @k	-> uint64)
 		eq	: (a : @k, b : @k -> bool)
 
 		nelt	: size
@@ -13,12 +13,12 @@
 		ndead	: size
 		keys	: @k[:]
 		vals	: @v[:]
-		hashes	: uint32[:]
+		hashes	: uint64[:]
 		dead	: bool[:]
 	;;
 
-	generic mkht	: (h : (k : @k -> uint32), eq : (a : @k, b : @k -> bool) -> htab(@k, @v)#)
-	generic htinit	: (ht : htab(@k, @v)#, h : (k : @k -> uint32), eq : (a : @k, b : @k -> bool) -> void)
+	generic mkht	: (h : (k : @k -> uint64), eq : (a : @k, b : @k -> bool) -> htab(@k, @v)#)
+	generic htinit	: (ht : htab(@k, @v)#, h : (k : @k -> uint64), eq : (a : @k, b : @k -> bool) -> void)
 	generic htfree	: (ht : htab(@k, @v)# -> void)
 	generic htput	: (ht : htab(@k, @v)#, k : @k, v : @v -> void)
 	generic htdel	: (ht : htab(@k, @v)#, k : @k -> void)
--- a/lib/std/test/bitset.myr
+++ b/lib/std/test/bitset.myr
@@ -49,11 +49,11 @@
 		}],
 		[.name="hash", .fn={ctx
 			var bs = mkset([][:])
-			testr.check(ctx, std.bshash(bs) == 2580988821, "wrong hash, got {}", std.bshash(bs))
+			testr.check(ctx, std.bshash(bs) == 0x726fdb47dd0e0e31, "wrong hash, got {}", std.bshash(bs))
 			std.bsput(bs, 123456)
-			testr.check(ctx, std.bshash(bs) == 2020624217, "wrong hash, got {}", std.bshash(bs))
+			testr.check(ctx, std.bshash(bs) == 0x778abc1d7706143b, "wrong hash, got {}", std.bshash(bs))
 			std.bsdel(bs, 123456)
-			testr.check(ctx, std.bshash(bs) == 2580988821, "wrong hash, got {}", std.bshash(bs))
+			testr.check(ctx, std.bshash(bs) == 0x726fdb47dd0e0e31, "wrong hash, got {}", std.bshash(bs))
 			std.bsfree(bs)
 		}]
 	][:])
--- a/lib/std/test/hashfuncs.myr
+++ b/lib/std/test/hashfuncs.myr
@@ -4,7 +4,7 @@
 const main = {
 	testr.run([
 		[.name="string hash and equality", .fn={ctx
-			testr.check(ctx, std.strhash("abc") == 1241861192, "wrong hash\n")
+			testr.check(ctx, std.strhash("abc") == 0x5dbcfa53aa2007a5, "wrong hash\n")
 			testr.check(ctx, std.streq("abc\0def", "abc\0def"), "equal strings not equal\n")
 			testr.check(ctx, !std.streq("abc\0def", "abcdef"), "unequal strings are equal\n")
 		}],
@@ -20,7 +20,7 @@
 			testr.check(ctx, !std.ptreq(&x, &y), "unequal pointers are equal")
 		}],
 		[.name="int hash and equality", .fn={ctx
-			testr.check(ctx, std.inthash(123) == 3497506805, "wrong int hash")
+			testr.check(ctx, std.inthash(123) == 0x5671db246859d5b6, "wrong int hash")
 			testr.check(ctx, std.inteq(123, 123), "equal integers not equal")
 			testr.check(ctx, !std.inteq(123, 456), "unequal integers are equal")
 		}],