1package murmur
2
3const (
4	c1    int64 = -8663945395140668459 // 0x87c37b91114253d5
5	c2    int64 = 5545529020109919103  // 0x4cf5ad432745937f
6	fmix1 int64 = -49064778989728563   // 0xff51afd7ed558ccd
7	fmix2 int64 = -4265267296055464877 // 0xc4ceb9fe1a85ec53
8)
9
10func fmix(n int64) int64 {
11	// cast to unsigned for logical right bitshift (to match C* MM3 implementation)
12	n ^= int64(uint64(n) >> 33)
13	n *= fmix1
14	n ^= int64(uint64(n) >> 33)
15	n *= fmix2
16	n ^= int64(uint64(n) >> 33)
17
18	return n
19}
20
21func block(p byte) int64 {
22	return int64(int8(p))
23}
24
25func rotl(x int64, r uint8) int64 {
26	// cast to unsigned for logical right bitshift (to match C* MM3 implementation)
27	return (x << r) | (int64)((uint64(x) >> (64 - r)))
28}
29
30func Murmur3H1(data []byte) int64 {
31	length := len(data)
32
33	var h1, h2, k1, k2 int64
34
35	// body
36	nBlocks := length / 16
37	for i := 0; i < nBlocks; i++ {
38		k1, k2 = getBlock(data, i)
39
40		k1 *= c1
41		k1 = rotl(k1, 31)
42		k1 *= c2
43		h1 ^= k1
44
45		h1 = rotl(h1, 27)
46		h1 += h2
47		h1 = h1*5 + 0x52dce729
48
49		k2 *= c2
50		k2 = rotl(k2, 33)
51		k2 *= c1
52		h2 ^= k2
53
54		h2 = rotl(h2, 31)
55		h2 += h1
56		h2 = h2*5 + 0x38495ab5
57	}
58
59	// tail
60	tail := data[nBlocks*16:]
61	k1 = 0
62	k2 = 0
63	switch length & 15 {
64	case 15:
65		k2 ^= block(tail[14]) << 48
66		fallthrough
67	case 14:
68		k2 ^= block(tail[13]) << 40
69		fallthrough
70	case 13:
71		k2 ^= block(tail[12]) << 32
72		fallthrough
73	case 12:
74		k2 ^= block(tail[11]) << 24
75		fallthrough
76	case 11:
77		k2 ^= block(tail[10]) << 16
78		fallthrough
79	case 10:
80		k2 ^= block(tail[9]) << 8
81		fallthrough
82	case 9:
83		k2 ^= block(tail[8])
84
85		k2 *= c2
86		k2 = rotl(k2, 33)
87		k2 *= c1
88		h2 ^= k2
89
90		fallthrough
91	case 8:
92		k1 ^= block(tail[7]) << 56
93		fallthrough
94	case 7:
95		k1 ^= block(tail[6]) << 48
96		fallthrough
97	case 6:
98		k1 ^= block(tail[5]) << 40
99		fallthrough
100	case 5:
101		k1 ^= block(tail[4]) << 32
102		fallthrough
103	case 4:
104		k1 ^= block(tail[3]) << 24
105		fallthrough
106	case 3:
107		k1 ^= block(tail[2]) << 16
108		fallthrough
109	case 2:
110		k1 ^= block(tail[1]) << 8
111		fallthrough
112	case 1:
113		k1 ^= block(tail[0])
114
115		k1 *= c1
116		k1 = rotl(k1, 31)
117		k1 *= c2
118		h1 ^= k1
119	}
120
121	h1 ^= int64(length)
122	h2 ^= int64(length)
123
124	h1 += h2
125	h2 += h1
126
127	h1 = fmix(h1)
128	h2 = fmix(h2)
129
130	h1 += h2
131	// the following is extraneous since h2 is discarded
132	// h2 += h1
133
134	return h1
135}
136