Debian Codegraph @

src/main/java/io/airlift/slice/Murmur3Hash128.java

raw
1 /*
2 * Licensed under the Apache License, Version 2.0 (the "License");
3 * you may not use this file except in compliance with the License.
4 * You may obtain a copy of the License at
5 *
6 * http://www.apache.org/licenses/LICENSE-2.0
7 *
8 * Unless required by applicable law or agreed to in writing, software
9 * distributed under the License is distributed on an "AS IS" BASIS,
10 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 * See the License for the specific language governing permissions and
12 * limitations under the License.
13 */
14 package io.airlift.slice;
15
16 public class Murmur3Hash128
17 {
18 private static final long C1 = 0x87c37b91114253d5L;
19 private static final long C2 = 0x4cf5ad432745937fL;
20
21 private final static long DEFAULT_SEED = 0;
22
23 public static Slice hash(Slice data)
24 {
25 return hash(data, 0, data.length());
26 }
27
28 public static Slice hash(Slice data, int offset, int length)
29 {
30 return hash(DEFAULT_SEED, data, offset, length);
31 }
32
33 public static Slice hash(long seed, Slice data, int offset, int length)
34 {
35 final int fastLimit = offset + length - (2 * SizeOf.SIZE_OF_LONG) + 1;
36
37 long h1 = seed;
38 long h2 = seed;
39
40 int current = offset;
41 while (current < fastLimit) {
42 long k1 = data.getLong(current);
43 current += SizeOf.SIZE_OF_LONG;
44
45 long k2 = data.getLong(current);
46 current += SizeOf.SIZE_OF_LONG;
47
48 k1 *= C1;
49 k1 = Long.rotateLeft(k1, 31);
50 k1 *= C2;
51 h1 ^= k1;
52
53 h1 = Long.rotateLeft(h1, 27);
54 h1 += h2;
55 h1 = h1 * 5 + 0x52dce729L;
56
57 k2 *= C2;
58 k2 = Long.rotateLeft(k2, 33);
59 k2 *= C1;
60 h2 ^= k2;
61
62 h2 = Long.rotateLeft(h2, 31);
63 h2 += h1;
64 h2 = h2 * 5 + 0x38495ab5L;
65 }
66
67 long k1 = 0;
68 long k2 = 0;
69
70 switch (length & 15) {
71 case 15:
72 k2 ^= ((long) data.getUnsignedByte(current + 14)) << 48;
73 case 14:
74 k2 ^= ((long) data.getUnsignedByte(current + 13)) << 40;
75 case 13:
76 k2 ^= ((long) data.getUnsignedByte(current + 12)) << 32;
77 case 12:
78 k2 ^= ((long) data.getUnsignedByte(current + 11)) << 24;
79 case 11:
80 k2 ^= ((long) data.getUnsignedByte(current + 10)) << 16;
81 case 10:
82 k2 ^= ((long) data.getUnsignedByte(current + 9)) << 8;
83 case 9:
84 k2 ^= ((long) data.getUnsignedByte(current + 8)) << 0;
85
86 k2 *= C2;
87 k2 = Long.rotateLeft(k2, 33);
88 k2 *= C1;
89 h2 ^= k2;
90
91 case 8:
92 k1 ^= ((long) data.getUnsignedByte(current + 7)) << 56;
93 case 7:
94 k1 ^= ((long) data.getUnsignedByte(current + 6)) << 48;
95 case 6:
96 k1 ^= ((long) data.getUnsignedByte(current + 5)) << 40;
97 case 5:
98 k1 ^= ((long) data.getUnsignedByte(current + 4)) << 32;
99 case 4:
100 k1 ^= ((long) data.getUnsignedByte(current + 3)) << 24;
101 case 3:
102 k1 ^= ((long) data.getUnsignedByte(current + 2)) << 16;
103 case 2:
104 k1 ^= ((long) data.getUnsignedByte(current + 1)) << 8;
105 case 1:
106 k1 ^= ((long) data.getUnsignedByte(current + 0)) << 0;
107
108 k1 *= C1;
109 k1 = Long.rotateLeft(k1, 31);
110 k1 *= C2;
111 h1 ^= k1;
112 }
113
114 h1 ^= length;
115 h2 ^= length;
116
117 h1 += h2;
118 h2 += h1;
119
120 h1 = mix64(h1);
121 h2 = mix64(h2);
122
123 h1 += h2;
124 h2 += h1;
125
126 Slice result = Slices.allocate(16);
127 result.setLong(0, h1);
128 result.setLong(8, h2);
129
130 return result;
131 }
132
133 /**
134 * Returns the 64 most significant bits of the Murmur128 hash of the provided value
135 */
136 public static long hash64(Slice data)
137 {
138 return hash64(data, 0, data.length());
139 }
140
141 public static long hash64(Slice data, int offset, int length)
142 {
143 return hash64(DEFAULT_SEED, data, offset, length);
144 }
145
146 public static long hash64(long seed, Slice data, int offset, int length)
147 {
148 final int fastLimit = offset + length - (2 * SizeOf.SIZE_OF_LONG) + 1;
149
150 long h1 = seed;
151 long h2 = seed;
152
153 int current = offset;
154 while (current < fastLimit) {
155 long k1 = data.getLong(current);
156 current += SizeOf.SIZE_OF_LONG;
157
158 long k2 = data.getLong(current);
159 current += SizeOf.SIZE_OF_LONG;
160
161 k1 *= C1;
162 k1 = Long.rotateLeft(k1, 31);
163 k1 *= C2;
164 h1 ^= k1;
165
166 h1 = Long.rotateLeft(h1, 27);
167 h1 += h2;
168 h1 = h1 * 5 + 0x52dce729L;
169
170 k2 *= C2;
171 k2 = Long.rotateLeft(k2, 33);
172 k2 *= C1;
173 h2 ^= k2;
174
175 h2 = Long.rotateLeft(h2, 31);
176 h2 += h1;
177 h2 = h2 * 5 + 0x38495ab5L;
178 }
179
180 long k1 = 0;
181 long k2 = 0;
182
183 switch (length & 15) {
184 case 15:
185 k2 ^= ((long) data.getUnsignedByte(current + 14)) << 48;
186 case 14:
187 k2 ^= ((long) data.getUnsignedByte(current + 13)) << 40;
188 case 13:
189 k2 ^= ((long) data.getUnsignedByte(current + 12)) << 32;
190 case 12:
191 k2 ^= ((long) data.getUnsignedByte(current + 11)) << 24;
192 case 11:
193 k2 ^= ((long) data.getUnsignedByte(current + 10)) << 16;
194 case 10:
195 k2 ^= ((long) data.getUnsignedByte(current + 9)) << 8;
196 case 9:
197 k2 ^= ((long) data.getUnsignedByte(current + 8)) << 0;
198
199 k2 *= C2;
200 k2 = Long.rotateLeft(k2, 33);
201 k2 *= C1;
202 h2 ^= k2;
203
204 case 8:
205 k1 ^= ((long) data.getUnsignedByte(current + 7)) << 56;
206 case 7:
207 k1 ^= ((long) data.getUnsignedByte(current + 6)) << 48;
208 case 6:
209 k1 ^= ((long) data.getUnsignedByte(current + 5)) << 40;
210 case 5:
211 k1 ^= ((long) data.getUnsignedByte(current + 4)) << 32;
212 case 4:
213 k1 ^= ((long) data.getUnsignedByte(current + 3)) << 24;
214 case 3:
215 k1 ^= ((long) data.getUnsignedByte(current + 2)) << 16;
216 case 2:
217 k1 ^= ((long) data.getUnsignedByte(current + 1)) << 8;
218 case 1:
219 k1 ^= ((long) data.getUnsignedByte(current + 0)) << 0;
220
221 k1 *= C1;
222 k1 = Long.rotateLeft(k1, 31);
223 k1 *= C2;
224 h1 ^= k1;
225 }
226
227 h1 ^= length;
228 h2 ^= length;
229
230 h1 += h2;
231 h2 += h1;
232
233 h1 = mix64(h1);
234 h2 = mix64(h2);
235
236 return h1 + h2;
237 }
238
239 /**
240 * Special-purpose version for hashing a single long value. Value is treated as little-endian
241 */
242 public static long hash64(long value)
243 {
244 long h2 = DEFAULT_SEED ^ SizeOf.SIZE_OF_LONG;
245 long h1 = h2 + (h2 ^ (Long.rotateLeft(value * C1, 31) * C2));
246
247 return mix64(h1) + mix64(h1 + h2);
248 }
249
250 private static long mix64(long k)
251 {
252 k ^= k >>> 33;
253 k *= 0xff51afd7ed558ccdL;
254 k ^= k >>> 33;
255 k *= 0xc4ceb9fe1a85ec53L;
256 k ^= k >>> 33;
257
258 return k;
259 }
260 }