summaryrefslogtreecommitdiff
path: root/lib/std/hashfuncs.myr
blob: fa72f90477953ad2b199c6698c35906a98d474aa (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
107
use "alloc"
use "chartype"
use "die"
use "getint"
use "sleq"
use "slpush"
use "traits"
use "types"
use "utf"

pkg std =
	const siphash24	: (data : byte[:], seed : byte[16] -> uint64)

	impl comparable @a[:] =
		cmp = {a, b
			-> sleq(a, b)
		}
	;;

	impl hashable @a[:] =
		hash = {a
			-> siphash24((a : byte#)[:a.len * sizeof(@a)], Seed)
		}
	;;

	impl comparable @a::(integral,numeric) =
		cmp = {a, b
			-> a == b
		}
	;;

	impl hashable @a::(integral,numeric) =
		hash = {a
			-> siphash24((&a : byte#)[:sizeof(@a)], Seed)
		}
	;;

	impl comparable @a# =
		cmp = {a, b
			-> a == b
		}
	;;

	impl hashable @a# =
		hash = {a
			-> hash((a : intptr))
		}
	;;
;;

const Seed : byte[16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

const sipround = {v0, v1, v2, v3 -> (uint64, uint64, uint64, uint64)
	v0 += v1
	v1 = (v1 << 13) | (v1 >> 51)
	v1 ^= v0
	v0 = (v0 << 32) | (v0 >> 32)
	v2 += v3
	v3 = (v3 << 16) | (v3 >> 48)
	v3 ^= v2

	v2 += v1
	v1 = (v1 << 17) | (v1 >> 47)
	v1 ^= v2
	v2 = (v2 << 32) | (v2 >> 32)
	v0 += v3
	v3 = (v3 << 21) | (v3 >> 43)
	v3 ^= v0

	-> (v0, v1, v2, v3)
}

const siphash24 = {data, seed
	var k0, k1, m, v0, v1, v2, v3, w
	var tail : byte[8] = [0, 0, 0, 0, 0, 0, 0, 0]

	k0 = std.getle64(seed[0:8])
	k1 = std.getle64(seed[8:16])
	v0 = k0 ^ 0x736f6d6570736575
	v1 = k1 ^ 0x646f72616e646f6d
	v2 = k0 ^ 0x6c7967656e657261
	v3 = k1 ^ 0x7465646279746573
	w = (data.len + 8) / 8 - 1
	for var i = 0; i < w; i++
		m = std.getle64(data[8 * i:8 * (i + 1)])
		v3 ^= m
		(v0, v1, v2, v3) = sipround(v0, v1, v2, v3)
		(v0, v1, v2, v3) = sipround(v0, v1, v2, v3)
		v0 ^= m
	;;
	for var i = 0; i < data.len % 8; i++
		tail[i] = data[8 * w + i]
	;;
	tail[7] = (data.len % 256 : byte)
	m = std.getle64(tail[:])
	v3 ^= m
	(v0, v1, v2, v3) = sipround(v0, v1, v2, v3)
	(v0, v1, v2, v3) = sipround(v0, v1, v2, v3)
	v0 ^= m

	v2 ^= 0xff
	(v0, v1, v2, v3) = sipround(v0, v1, v2, v3)
	(v0, v1, v2, v3) = sipround(v0, v1, v2, v3)
	(v0, v1, v2, v3) = sipround(v0, v1, v2, v3)
	(v0, v1, v2, v3) = sipround(v0, v1, v2, v3)
	-> v0 ^ v1 ^ v2 ^ v3
}