summaryrefslogtreecommitdiff
path: root/libstd/hashfuncs.myr
blob: 00c44c447fe5b1c00742d3f400c132e29f9188e2 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
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
}