Debian Codegraph @

src/main/java/io/airlift/slice/XxHash64.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 import static io.airlift.slice.JvmUtils.unsafe;
17 import static io.airlift.slice.Preconditions.checkPositionIndexes;
18 import static java.lang.Long.rotateLeft;
19
20 public class XxHash64
21 {
22 private final static long PRIME64_1 = 0x9E3779B185EBCA87L;
23 private final static long PRIME64_2 = 0xC2B2AE3D27D4EB4FL;
24 private final static long PRIME64_3 = 0x165667B19E3779F9L;
25 private final static long PRIME64_4 = 0x85EBCA77C2b2AE63L;
26 private final static long PRIME64_5 = 0x27D4EB2F165667C5L;
27
28 private final static long DEFAULT_SEED = 0;
29
30 public static long hash(long value)
31 {
32 long hash = DEFAULT_SEED + PRIME64_5 + SizeOf.SIZE_OF_LONG;
33 hash = updateTail(hash, value);
34 hash = finalShuffle(hash);
35
36 return hash;
37 }
38
39 public static long hash(Slice data)
40 {
41 return hash(data, 0, data.length());
42 }
43
44 public static long hash(long seed, Slice data)
45 {
46 return hash(seed, data, 0, data.length());
47 }
48
49 public static long hash(Slice data, int offset, int length)
50 {
51 return hash(DEFAULT_SEED, data, offset, length);
52 }
53
54 public static long hash(long seed, Slice data, int offset, int length)
55 {
56 checkPositionIndexes(0, offset + length, data.length());
57
58 Object base = data.getBase();
59 final long address = data.getAddress() + offset;
60
61 long hash;
62 if (length >= 32) {
63 hash = updateBody(seed, base, address, length - 32);
64 }
65 else {
66 hash = seed + PRIME64_5;
67 }
68
69 hash += length;
70
71 // round to the closest 32 byte boundary
72 // this is the point up to which {@see #updateBody} processed
73 int index = length & 0xFFFFFF70;
74
75 while (index <= length - 8) {
76 hash = updateTail(hash, unsafe.getLong(base, address + index));
77 index += 8;
78 }
79
80 if (index <= length - 4) {
81 hash = updateTail(hash, unsafe.getInt(base, address + index));
82 index += 4;
83 }
84
85 while (index < length) {
86 hash = updateTail(hash, unsafe.getByte(base, address + index));
87 index++;
88 }
89
90 hash = finalShuffle(hash);
91
92 return hash;
93 }
94
95 private static long updateBody(long seed, Object base, long address, int length)
96 {
97 long v1 = seed + PRIME64_1 + PRIME64_2;
98 long v2 = seed + PRIME64_2;
99 long v3 = seed + 0;
100 long v4 = seed - PRIME64_1;
101
102 for (int index = 0; index <= length; index += 32) {
103 v1 = mix(v1, unsafe.getLong(base, address));
104 v2 = mix(v2, unsafe.getLong(base, address + 8));
105 v3 = mix(v3, unsafe.getLong(base, address + 16));
106 v4 = mix(v4, unsafe.getLong(base, address + 24));
107
108 address += 32;
109 }
110
111 long hash = rotateLeft(v1, 1) + rotateLeft(v2, 7) + rotateLeft(v3, 12) + rotateLeft(v4, 18);
112
113 hash = update(hash, v1);
114 hash = update(hash, v2);
115 hash = update(hash, v3);
116 hash = update(hash, v4);
117
118 return hash;
119 }
120
121 private static long mix(long current, long value)
122 {
123 return rotateLeft(current + value * PRIME64_2, 31) * PRIME64_1;
124 }
125
126 private static long update(long hash, long value)
127 {
128 long temp = hash ^ mix(0, value);
129 return temp * PRIME64_1 + PRIME64_4;
130 }
131
132 private static long updateTail(long hash, long value)
133 {
134 long temp = hash ^ mix(0, value);
135 return rotateLeft(temp, 27) * PRIME64_1 + PRIME64_4;
136 }
137
138 private static long updateTail(long hash, int value)
139 {
140 long unsigned = value & 0xFFFF_FFFFL;
141 long temp = hash ^ (unsigned * PRIME64_1);
142 return rotateLeft(temp, 23) * PRIME64_2 + PRIME64_3;
143 }
144
145 private static long updateTail(long hash, byte value)
146 {
147 int unsigned = value & 0xFF;
148 long temp = hash ^ (unsigned * PRIME64_5);
149 return rotateLeft(temp, 11) * PRIME64_1;
150 }
151
152 private static long finalShuffle(long hash)
153 {
154 hash ^= hash >>> 33;
155 hash *= PRIME64_2;
156 hash ^= hash >>> 29;
157 hash *= PRIME64_3;
158 hash ^= hash >>> 32;
159 return hash;
160 }
161 }