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")
}],