-
Notifications
You must be signed in to change notification settings - Fork 1
/
murmur3.go
92 lines (77 loc) · 1.42 KB
/
murmur3.go
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
package murmur3
import (
"math/bits"
"github.com/glojurelang/glojure/internal/seq"
)
const (
seed = 0
c1 = 0xcc9e2d51
c2 = 0x1b873593
)
func HashInt(input int32) uint32 {
if input == 0 {
return 0
}
k1 := mixK1(uint32(input))
h1 := mixH1(seed, k1)
return fmix(h1, 4)
}
func HashLong(input int64) uint32 {
if input == 0 {
return 0
}
low := uint32(input)
high := uint32((input >> 32) & 0xffffffff)
k1 := mixK1(low)
h1 := mixH1(seed, k1)
k1 = mixK1(high)
h1 = mixH1(h1, k1)
return fmix(h1, 8)
}
func HashOrdered(xs seq.Seq, elHash func(any) uint32) uint32 {
var n uint32
var hash uint32 = 1
for ; xs != nil; xs = xs.Next() {
eh := elHash(xs.First())
hash = 31*hash + eh
n++
}
return MixCollHash(hash, n)
}
func HashUnordered(xs seq.Seq, elHash func(any) uint32) uint32 {
var n uint32
var hash uint32
for ; xs != nil; xs = xs.Next() {
eh := elHash(xs.First())
hash += eh
n++
}
return MixCollHash(hash, n)
}
func MixCollHash(hash, count uint32) uint32 {
h1 := uint32(seed)
k1 := mixK1(hash)
h1 = mixH1(h1, k1)
return fmix(h1, count)
}
func mixK1(k1 uint32) uint32 {
k1 *= c1
k1 = bits.RotateLeft32(k1, 15)
k1 *= c2
return k1
}
func mixH1(h1, k1 uint32) uint32 {
h1 ^= k1
h1 = bits.RotateLeft32(h1, 13)
h1 = h1*5 + 0xe6546b64
return h1
}
func fmix(h1, length uint32) uint32 {
h1 ^= length
h1 ^= h1 >> 16
h1 *= 0x85ebca6b
h1 ^= h1 >> 13
h1 *= 0xc2b2ae35
h1 ^= h1 >> 16
return h1
}