1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.codec.digest;
19
20 import org.apache.commons.codec.binary.StringUtils;
21
22 /**
23 * Implements the MurmurHash2 32-bit and 64-bit hash functions.
24 *
25 * <p>
26 * MurmurHash is a non-cryptographic hash function suitable for general
27 * hash-based lookup. The name comes from two basic operations, multiply (MU)
28 * and rotate (R), used in its inner loop. Unlike cryptographic hash functions,
29 * it is not specifically designed to be difficult to reverse by an adversary,
30 * making it unsuitable for cryptographic purposes.
31 * </p>
32 *
33 * <p>
34 * This contains a Java port of the 32-bit hash function {@code MurmurHash2}
35 * and the 64-bit hash function {@code MurmurHash64A} from Austin Appleby's
36 * original {@code c++} code in SMHasher.
37 * </p>
38 *
39 * <p>
40 * This is a re-implementation of the original C code plus some additional
41 * features.
42 * </p>
43 *
44 * <p>
45 * This is public domain code with no copyrights. From home page of
46 * <a href="https://github.com/aappleby/smhasher">SMHasher</a>:
47 * </p>
48 *
49 * <blockquote>
50 * "All MurmurHash versions are public domain software, and the author
51 * disclaims all copyright to their code."
52 * </blockquote>
53 *
54 * @see <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>
55 * @see <a href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash2.cpp">
56 * Original MurmurHash2 c++ code</a>
57 * @since 1.13
58 */
59 public final class MurmurHash2 {
60
61 // Constants for 32-bit variant
62 private static final int M32 = 0x5bd1e995;
63 private static final int R32 = 24;
64
65 // Constants for 64-bit variant
66 private static final long M64 = 0xc6a4a7935bd1e995L;
67 private static final int R64 = 47;
68
69 /**
70 * Generates a 32-bit hash from byte array with the given length and a default seed value.
71 * This is a helper method that will produce the same result as:
72 *
73 * <pre>
74 * int seed = 0x9747b28c;
75 * int hash = MurmurHash2.hash32(data, length, seed);
76 * </pre>
77 *
78 * @param data The input byte array.
79 * @param length The length of the array.
80 * @return The 32-bit hash.
81 * @see #hash32(byte[], int, int)
82 */
83 public static int hash32(final byte[] data, final int length) {
84 return hash32(data, length, 0x9747b28c);
85 }
86
87 /**
88 * Generates a 32-bit hash from byte array with the given length and seed.
89 *
90 * @param data The input byte array.
91 * @param length The length of the array.
92 * @param seed The initial seed value.
93 * @return The 32-bit hash.
94 */
95 public static int hash32(final byte[] data, final int length, final int seed) {
96 // Initialize the hash to a random value
97 int h = seed ^ length;
98 // Mix 4 bytes at a time into the hash
99 final int nblocks = length >> 2;
100 // body
101 for (int i = 0; i < nblocks; i++) {
102 final int index = i << 2;
103 int k = MurmurHash.getLittleEndianInt(data, index);
104 k *= M32;
105 k ^= k >>> R32;
106 k *= M32;
107 h *= M32;
108 h ^= k;
109 }
110 // Handle the last few bytes of the input array
111 final int index = nblocks << 2;
112 switch (length - index) {
113 case 3:
114 h ^= (data[index + 2] & 0xff) << 16;
115 // falls-through
116 case 2:
117 h ^= (data[index + 1] & 0xff) << 8;
118 // falls-through
119 case 1:
120 h ^= data[index] & 0xff;
121 h *= M32;
122 }
123 // Do a few final mixes of the hash to ensure the last few
124 // bytes are well-incorporated.
125 h ^= h >>> 13;
126 h *= M32;
127 h ^= h >>> 15;
128 return h;
129 }
130
131 /**
132 * Generates a 32-bit hash from a string with a default seed.
133 * <p>
134 * Before 1.14 the string was converted using default encoding.
135 * Since 1.14 the string is converted to bytes using UTF-8 encoding.
136 * </p>
137 * This is a helper method that will produce the same result as:
138 *
139 * <pre>
140 * int seed = 0x9747b28c;
141 * byte[] bytes = data.getBytes(StandardCharsets.UTF_8);
142 * int hash = MurmurHash2.hash32(bytes, bytes.length, seed);
143 * </pre>
144 *
145 * @param text The input string.
146 * @return The 32-bit hash.
147 * @see #hash32(byte[], int, int)
148 */
149 public static int hash32(final String text) {
150 final byte[] bytes = StringUtils.getBytesUtf8(text);
151 return hash32(bytes, bytes.length);
152 }
153
154 /**
155 * Generates a 32-bit hash from a substring with a default seed value.
156 * The string is converted to bytes using the default encoding.
157 * This is a helper method that will produce the same result as:
158 *
159 * <pre>
160 * int seed = 0x9747b28c;
161 * byte[] bytes = text.substring(from, from + length).getBytes(StandardCharsets.UTF_8);
162 * int hash = MurmurHash2.hash32(bytes, bytes.length, seed);
163 * </pre>
164 *
165 * @param text The input string.
166 * @param from The starting index.
167 * @param length The length of the substring.
168 * @return The 32-bit hash.
169 * @see #hash32(byte[], int, int)
170 */
171 public static int hash32(final String text, final int from, final int length) {
172 return hash32(text.substring(from, from + length));
173 }
174
175 /**
176 * Generates a 64-bit hash from byte array with given length and a default seed value.
177 * This is a helper method that will produce the same result as:
178 *
179 * <pre>
180 * int seed = 0xe17a1465;
181 * int hash = MurmurHash2.hash64(data, length, seed);
182 * </pre>
183 *
184 * @param data The input byte array.
185 * @param length The length of the array.
186 * @return The 64-bit hash.
187 * @see #hash64(byte[], int, int)
188 */
189 public static long hash64(final byte[] data, final int length) {
190 return hash64(data, length, 0xe17a1465);
191 }
192
193 /**
194 * Generates a 64-bit hash from byte array of the given length and seed.
195 *
196 * @param data The input byte array.
197 * @param length The length of the array.
198 * @param seed The initial seed value.
199 * @return The 64-bit hash of the given array.
200 */
201 public static long hash64(final byte[] data, final int length, final int seed) {
202 long h = seed & 0xffffffffL ^ length * M64;
203 final int nblocks = length >> 3;
204 // body
205 for (int i = 0; i < nblocks; i++) {
206 final int index = i << 3;
207 long k = MurmurHash.getLittleEndianLong(data, index);
208
209 k *= M64;
210 k ^= k >>> R64;
211 k *= M64;
212
213 h ^= k;
214 h *= M64;
215 }
216 final int index = nblocks << 3;
217 switch (length - index) {
218 case 7:
219 h ^= ((long) data[index + 6] & 0xff) << 48;
220 // falls-through
221 case 6:
222 h ^= ((long) data[index + 5] & 0xff) << 40;
223 // falls-through
224 case 5:
225 h ^= ((long) data[index + 4] & 0xff) << 32;
226 // falls-through
227 case 4:
228 h ^= ((long) data[index + 3] & 0xff) << 24;
229 // falls-through
230 case 3:
231 h ^= ((long) data[index + 2] & 0xff) << 16;
232 // falls-through
233 case 2:
234 h ^= ((long) data[index + 1] & 0xff) << 8;
235 // falls-through
236 case 1:
237 h ^= (long) data[index] & 0xff;
238 h *= M64;
239 }
240 h ^= h >>> R64;
241 h *= M64;
242 h ^= h >>> R64;
243 return h;
244 }
245
246 /**
247 * Generates a 64-bit hash from a string with a default seed.
248 * <p>
249 * Before 1.14 the string was converted using default encoding.
250 * Since 1.14 the string is converted to bytes using UTF-8 encoding.
251 * </p>
252 * <p>
253 * This is a helper method that will produce the same result as:
254 * </p>
255 *
256 * <pre>
257 * int seed = 0xe17a1465;
258 * byte[] bytes = data.getBytes(StandardCharsets.UTF_8);
259 * int hash = MurmurHash2.hash64(bytes, bytes.length, seed);
260 * </pre>
261 *
262 * @param text The input string.
263 * @return The 64-bit hash.
264 * @see #hash64(byte[], int, int)
265 */
266 public static long hash64(final String text) {
267 final byte[] bytes = StringUtils.getBytesUtf8(text);
268 return hash64(bytes, bytes.length);
269 }
270
271 /**
272 * Generates a 64-bit hash from a substring with a default seed value.
273 * The string is converted to bytes using the default encoding.
274 * This is a helper method that will produce the same result as:
275 *
276 * <pre>
277 * int seed = 0xe17a1465;
278 * byte[] bytes = text.substring(from, from + length).getBytes(StandardCharsets.UTF_8);
279 * int hash = MurmurHash2.hash64(bytes, bytes.length, seed);
280 * </pre>
281 *
282 * @param text The input string.
283 * @param from The starting index.
284 * @param length The length of the substring.
285 * @return The 64-bit hash.
286 * @see #hash64(byte[], int, int)
287 */
288 public static long hash64(final String text, final int from, final int length) {
289 return hash64(text.substring(from, from + length));
290 }
291
292 /** No instance methods. */
293 private MurmurHash2() {
294 }
295 }