1 package xxh3
2
3 import (
4 "math/bits"
5 )
6
7
8 func Hash128(b []byte) Uint128 {
9 return hashAny128(*(*str)(ptr(&b)))
10 }
11
12
13 func HashString128(s string) Uint128 {
14 return hashAny128(*(*str)(ptr(&s)))
15 }
16
17 func hashAny128(s str) (acc u128) {
18 p, l := s.p, s.l
19
20 switch {
21 case l <= 16:
22 switch {
23 case l > 8:
24 const bitflipl = key64_032 ^ key64_040
25 const bitfliph = key64_048 ^ key64_056
26
27 input_lo := readU64(p, 0)
28 input_hi := readU64(p, ui(l)-8)
29
30 m128_h, m128_l := bits.Mul64(input_lo^input_hi^bitflipl, prime64_1)
31
32 m128_l += uint64(l-1) << 54
33 input_hi ^= bitfliph
34
35 m128_h += input_hi + uint64(uint32(input_hi))*(prime32_2-1)
36
37 m128_l ^= bits.ReverseBytes64(m128_h)
38
39 acc.Hi, acc.Lo = bits.Mul64(m128_l, prime64_2)
40 acc.Hi += m128_h * prime64_2
41
42 acc.Lo = xxh3Avalanche(acc.Lo)
43 acc.Hi = xxh3Avalanche(acc.Hi)
44
45 return acc
46
47 case l > 3:
48 const bitflip = key64_016 ^ key64_024
49
50 input_lo := readU32(p, 0)
51 input_hi := readU32(p, ui(l)-4)
52 input_64 := u64(input_lo) + u64(input_hi)<<32
53 keyed := input_64 ^ bitflip
54
55 acc.Hi, acc.Lo = bits.Mul64(keyed, prime64_1+(uint64(l)<<2))
56
57 acc.Hi += acc.Lo << 1
58 acc.Lo ^= acc.Hi >> 3
59
60 acc.Lo ^= acc.Lo >> 35
61 acc.Lo *= 0x9fb21c651e98df25
62 acc.Lo ^= acc.Lo >> 28
63 acc.Hi = xxh3Avalanche(acc.Hi)
64
65 return acc
66
67 case l == 3:
68 c12 := u64(readU16(p, 0))
69 c3 := u64(readU8(p, 2))
70 acc.Lo = c12<<16 + c3 + 3<<8
71
72 case l > 1:
73 c12 := u64(readU16(p, 0))
74 acc.Lo = c12*(1<<24+1)>>8 + 2<<8
75
76 case l == 1:
77 c1 := u64(readU8(p, 0))
78 acc.Lo = c1*(1<<24+1<<16+1) + 1<<8
79
80 default:
81 return u128{0x99aa06d3014798d8, 0x6001c324468d497f}
82 }
83
84 acc.Hi = uint64(bits.RotateLeft32(bits.ReverseBytes32(uint32(acc.Lo)), 13))
85 acc.Lo ^= uint64(key32_000 ^ key32_004)
86 acc.Hi ^= uint64(key32_008 ^ key32_012)
87
88 acc.Lo = xxh64AvalancheSmall(acc.Lo)
89 acc.Hi = xxh64AvalancheSmall(acc.Hi)
90
91 return acc
92
93 case l <= 128:
94 acc.Lo = u64(l) * prime64_1
95
96 if l > 32 {
97 if l > 64 {
98 if l > 96 {
99 in8, in7 := readU64(p, ui(l)-8*8), readU64(p, ui(l)-7*8)
100 i6, i7 := readU64(p, 6*8), readU64(p, 7*8)
101
102 acc.Hi += mulFold64(in8^key64_112, in7^key64_120)
103 acc.Hi ^= i6 + i7
104 acc.Lo += mulFold64(i6^key64_096, i7^key64_104)
105 acc.Lo ^= in8 + in7
106
107 }
108
109 in6, in5 := readU64(p, ui(l)-6*8), readU64(p, ui(l)-5*8)
110 i4, i5 := readU64(p, 4*8), readU64(p, 5*8)
111
112 acc.Hi += mulFold64(in6^key64_080, in5^key64_088)
113 acc.Hi ^= i4 + i5
114 acc.Lo += mulFold64(i4^key64_064, i5^key64_072)
115 acc.Lo ^= in6 + in5
116
117 }
118
119 in4, in3 := readU64(p, ui(l)-4*8), readU64(p, ui(l)-3*8)
120 i2, i3 := readU64(p, 2*8), readU64(p, 3*8)
121
122 acc.Hi += mulFold64(in4^key64_048, in3^key64_056)
123 acc.Hi ^= i2 + i3
124 acc.Lo += mulFold64(i2^key64_032, i3^key64_040)
125 acc.Lo ^= in4 + in3
126
127 }
128
129 in2, in1 := readU64(p, ui(l)-2*8), readU64(p, ui(l)-1*8)
130 i0, i1 := readU64(p, 0*8), readU64(p, 1*8)
131
132 acc.Hi += mulFold64(in2^key64_016, in1^key64_024)
133 acc.Hi ^= i0 + i1
134 acc.Lo += mulFold64(i0^key64_000, i1^key64_008)
135 acc.Lo ^= in2 + in1
136
137 acc.Hi, acc.Lo = (acc.Lo*prime64_1)+(acc.Hi*prime64_4)+(u64(l)*prime64_2), acc.Hi+acc.Lo
138
139 acc.Hi = -xxh3Avalanche(acc.Hi)
140 acc.Lo = xxh3Avalanche(acc.Lo)
141
142 return acc
143
144 case l <= 240:
145 acc.Lo = u64(l) * prime64_1
146
147 {
148 i0, i1, i2, i3 := readU64(p, 0*8), readU64(p, 1*8), readU64(p, 2*8), readU64(p, 3*8)
149
150 acc.Hi += mulFold64(i2^key64_016, i3^key64_024)
151 acc.Hi ^= i0 + i1
152 acc.Lo += mulFold64(i0^key64_000, i1^key64_008)
153 acc.Lo ^= i2 + i3
154 }
155
156 {
157 i0, i1, i2, i3 := readU64(p, 4*8), readU64(p, 5*8), readU64(p, 6*8), readU64(p, 7*8)
158
159 acc.Hi += mulFold64(i2^key64_048, i3^key64_056)
160 acc.Hi ^= i0 + i1
161 acc.Lo += mulFold64(i0^key64_032, i1^key64_040)
162 acc.Lo ^= i2 + i3
163 }
164
165 {
166 i0, i1, i2, i3 := readU64(p, 8*8), readU64(p, 9*8), readU64(p, 10*8), readU64(p, 11*8)
167
168 acc.Hi += mulFold64(i2^key64_080, i3^key64_088)
169 acc.Hi ^= i0 + i1
170 acc.Lo += mulFold64(i0^key64_064, i1^key64_072)
171 acc.Lo ^= i2 + i3
172 }
173
174 {
175 i0, i1, i2, i3 := readU64(p, 12*8), readU64(p, 13*8), readU64(p, 14*8), readU64(p, 15*8)
176
177 acc.Hi += mulFold64(i2^key64_112, i3^key64_120)
178 acc.Hi ^= i0 + i1
179 acc.Lo += mulFold64(i0^key64_096, i1^key64_104)
180 acc.Lo ^= i2 + i3
181 }
182
183
184 acc.Hi = xxh3Avalanche(acc.Hi)
185 acc.Lo = xxh3Avalanche(acc.Lo)
186
187
188 top := ui(l) &^ 31
189 for i := ui(4 * 32); i < top; i += 32 {
190 i0, i1, i2, i3 := readU64(p, i+0), readU64(p, i+8), readU64(p, i+16), readU64(p, i+24)
191 k0, k1, k2, k3 := readU64(key, i-125), readU64(key, i-117), readU64(key, i-109), readU64(key, i-101)
192
193 acc.Hi += mulFold64(i2^k2, i3^k3)
194 acc.Hi ^= i0 + i1
195 acc.Lo += mulFold64(i0^k0, i1^k1)
196 acc.Lo ^= i2 + i3
197 }
198
199
200 {
201 i0, i1, i2, i3 := readU64(p, ui(l)-32), readU64(p, ui(l)-24), readU64(p, ui(l)-16), readU64(p, ui(l)-8)
202
203 acc.Hi += mulFold64(i0^key64_119, i1^key64_127)
204 acc.Hi ^= i2 + i3
205 acc.Lo += mulFold64(i2^key64_103, i3^key64_111)
206 acc.Lo ^= i0 + i1
207 }
208
209 acc.Hi, acc.Lo = (acc.Lo*prime64_1)+(acc.Hi*prime64_4)+(u64(l)*prime64_2), acc.Hi+acc.Lo
210
211 acc.Hi = -xxh3Avalanche(acc.Hi)
212 acc.Lo = xxh3Avalanche(acc.Lo)
213
214 return acc
215
216 default:
217 acc.Lo = u64(l) * prime64_1
218 acc.Hi = ^(u64(l) * prime64_2)
219
220 accs := [8]u64{
221 prime32_3, prime64_1, prime64_2, prime64_3,
222 prime64_4, prime32_2, prime64_5, prime32_1,
223 }
224
225 if hasAVX512 && l >= avx512Switch {
226 accumAVX512(&accs, p, key, u64(l))
227 } else if hasAVX2 {
228 accumAVX2(&accs, p, key, u64(l))
229 } else if hasSSE2 {
230 accumSSE(&accs, p, key, u64(l))
231 } else {
232 accumScalar(&accs, p, key, u64(l))
233 }
234
235
236 acc.Lo += mulFold64(accs[0]^key64_011, accs[1]^key64_019)
237 acc.Hi += mulFold64(accs[0]^key64_117, accs[1]^key64_125)
238
239 acc.Lo += mulFold64(accs[2]^key64_027, accs[3]^key64_035)
240 acc.Hi += mulFold64(accs[2]^key64_133, accs[3]^key64_141)
241
242 acc.Lo += mulFold64(accs[4]^key64_043, accs[5]^key64_051)
243 acc.Hi += mulFold64(accs[4]^key64_149, accs[5]^key64_157)
244
245 acc.Lo += mulFold64(accs[6]^key64_059, accs[7]^key64_067)
246 acc.Hi += mulFold64(accs[6]^key64_165, accs[7]^key64_173)
247
248 acc.Lo = xxh3Avalanche(acc.Lo)
249 acc.Hi = xxh3Avalanche(acc.Hi)
250
251 return acc
252 }
253 }
254
View as plain text