summaryrefslogtreecommitdiff
path: root/lib/std/hashfuncs.myr
diff options
context:
space:
mode:
Diffstat (limited to 'lib/std/hashfuncs.myr')
-rw-r--r--lib/std/hashfuncs.myr106
1 files changed, 106 insertions, 0 deletions
diff --git a/lib/std/hashfuncs.myr b/lib/std/hashfuncs.myr
new file mode 100644
index 0000000..00c44c4
--- /dev/null
+++ b/lib/std/hashfuncs.myr
@@ -0,0 +1,106 @@
+use "die.use"
+use "sleq.use"
+use "types.use"
+
+pkg std =
+ const strhash : (s : byte[:] -> uint32)
+ const streq : (a : byte[:], b : byte[:] -> bool)
+
+ generic ptrhash : (p : @a# -> uint32)
+ generic ptreq : (a : @a#, b : @a# -> bool)
+
+ generic inthash : (v : @a::(integral,numeric) -> uint32)
+ generic inteq : (a : @a::(integral,numeric), b : @a::(integral,numeric) -> bool)
+
+ const murmurhash2 : (data : byte[:], seed : uint32 -> uint32)
+
+ generic slhash : (sl : @a[:] -> uint32)
+ generic tobytes : (sl : @a[:] -> byte[:])
+;;
+
+const Seed = 1234
+
+generic slhash = {data : @a[:]
+ -> strhash(slbytes(data))
+}
+
+generic slbytes = {data : @a[:]
+ var n
+
+ n = data.len * sizeof(@a)
+ -> (data castto(byte#))[:n]
+}
+
+/* Supremely simple djb hash. */
+const strhash = {s
+ -> murmurhash2(s, Seed)
+}
+
+const streq = {a, b
+ -> sleq(a, b)
+}
+
+generic ptrhash = {p : @a#
+ var x
+
+ x = &p castto(byte#)
+ -> murmurhash2(x[0:sizeof(@a)], Seed)
+}
+
+generic ptreq = {a, b
+ -> a == b
+}
+
+generic inthash = {v : @a::(integral,numeric)
+ var p
+
+ p = &v castto(byte#)
+ -> murmurhash2(p[0:sizeof(@a)], Seed)
+}
+
+generic inteq = {a, b
+ -> a == b
+}
+
+const murmurhash2 = {data, seed
+ const m = 0x5bd1e995;
+ const r = 24
+ var h, k
+
+ h = seed ^ data.len
+ while data.len >= 4
+ k = (data[0] castto(uint32))
+ k |= (data[1] castto(uint32)) << 8
+ k |= (data[2] castto(uint32)) << 16
+ k |= (data[3] castto(uint32)) << 24
+
+ k *= m
+ k ^= k >> r
+ k *= m
+
+ h *= m
+ h ^= k
+ data = data[4:]
+ ;;
+
+ match data.len
+ | 3:
+ h ^= (data[2] castto(uint32)) << 16
+ h ^= (data[1] castto(uint32)) <<8
+ h ^= (data[0] castto(uint32))
+ | 2:
+ h ^= (data[1] castto(uint32)) <<8
+ h ^= (data[0] castto(uint32))
+ | 1:
+ h ^= (data[0] castto(uint32))
+ | 0: /* nothing */
+ | _: die("0 < len < 4 must be true")
+ ;;
+ h *= m
+
+ h ^= h >> 13
+ h *= m
+ h ^= h >> 15
+
+ -> h
+}