001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.codec.digest;
019
020import org.apache.commons.codec.binary.StringUtils;
021
022/**
023 * Implementation of the MurmurHash2 32-bit and 64-bit hash functions.
024 *
025 * <p>MurmurHash is a non-cryptographic hash function suitable for general
026 * hash-based lookup. The name comes from two basic operations, multiply (MU)
027 * and rotate (R), used in its inner loop. Unlike cryptographic hash functions,
028 * it is not specifically designed to be difficult to reverse by an adversary,
029 * making it unsuitable for cryptographic purposes.</p>
030 *
031 * <p>This contains a Java port of the 32-bit hash function {@code MurmurHash2}
032 * and the 64-bit hash function {@code MurmurHash64A} from Austin Appleby's
033 * original {@code c++} code in SMHasher.</p>
034 *
035 * <p>This is a re-implementation of the original C code plus some additional
036 * features.</p>
037 *
038 * <p>This is public domain code with no copyrights. From home page of
039 * <a href="https://github.com/aappleby/smhasher">SMHasher</a>:</p>
040 *
041 * <blockquote>
042 * "All MurmurHash versions are public domain software, and the author
043 * disclaims all copyright to their code."
044 * </blockquote>
045 *
046 * @see <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>
047 * @see <a href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash2.cpp">
048 *   Original MurmurHash2 c++ code</a>
049 * @since 1.13
050 */
051public final class MurmurHash2 {
052
053    // Constants for 32-bit variant
054    private static final int M32 = 0x5bd1e995;
055    private static final int R32 = 24;
056
057    // Constants for 64-bit variant
058    private static final long M64 = 0xc6a4a7935bd1e995L;
059    private static final int R64 = 47;
060
061    /**
062     * Gets the little-endian int from 4 bytes starting at the specified index.
063     *
064     * @param data The data
065     * @param index The index
066     * @return The little-endian int
067     */
068    private static int getLittleEndianInt(final byte[] data, final int index) {
069        return data[index    ] & 0xff |
070               (data[index + 1] & 0xff) <<  8 |
071               (data[index + 2] & 0xff) << 16 |
072               (data[index + 3] & 0xff) << 24;
073    }
074
075    /**
076     * Gets the little-endian long from 8 bytes starting at the specified index.
077     *
078     * @param data The data
079     * @param index The index
080     * @return The little-endian long
081     */
082    private static long getLittleEndianLong(final byte[] data, final int index) {
083        return (long) data[index    ] & 0xff |
084               ((long) data[index + 1] & 0xff) <<  8 |
085               ((long) data[index + 2] & 0xff) << 16 |
086               ((long) data[index + 3] & 0xff) << 24 |
087               ((long) data[index + 4] & 0xff) << 32 |
088               ((long) data[index + 5] & 0xff) << 40 |
089               ((long) data[index + 6] & 0xff) << 48 |
090               ((long) data[index + 7] & 0xff) << 56;
091    }
092
093    /**
094     * Generates a 32-bit hash from byte array with the given length and a default seed value.
095     * This is a helper method that will produce the same result as:
096     *
097     * <pre>
098     * int seed = 0x9747b28c;
099     * int hash = MurmurHash2.hash32(data, length, seed);
100     * </pre>
101     *
102     * @param data The input byte array
103     * @param length The length of the array
104     * @return The 32-bit hash
105     * @see #hash32(byte[], int, int)
106     */
107    public static int hash32(final byte[] data, final int length) {
108        return hash32(data, length, 0x9747b28c);
109    }
110
111    /**
112     * Generates a 32-bit hash from byte array with the given length and seed.
113     *
114     * @param data The input byte array
115     * @param length The length of the array
116     * @param seed The initial seed value
117     * @return The 32-bit hash
118     */
119    public static int hash32(final byte[] data, final int length, final int seed) {
120        // Initialize the hash to a random value
121        int h = seed ^ length;
122
123        // Mix 4 bytes at a time into the hash
124        final int nblocks = length >> 2;
125
126        // body
127        for (int i = 0; i < nblocks; i++) {
128            final int index = i << 2;
129            int k = getLittleEndianInt(data, index);
130            k *= M32;
131            k ^= k >>> R32;
132            k *= M32;
133            h *= M32;
134            h ^= k;
135        }
136
137        // Handle the last few bytes of the input array
138        final int index = nblocks << 2;
139        switch (length - index) {
140        case 3:
141            h ^= (data[index + 2] & 0xff) << 16;
142        case 2:
143            h ^= (data[index + 1] & 0xff) << 8;
144        case 1:
145            h ^= data[index] & 0xff;
146            h *= M32;
147        }
148
149        // Do a few final mixes of the hash to ensure the last few
150        // bytes are well-incorporated.
151        h ^= h >>> 13;
152        h *= M32;
153        h ^= h >>> 15;
154
155        return h;
156    }
157
158    /**
159     * Generates a 32-bit hash from a string with a default seed.
160     * <p>
161     * Before 1.14 the string was converted using default encoding.
162     * Since 1.14 the string is converted to bytes using UTF-8 encoding.
163     * </p>
164     * This is a helper method that will produce the same result as:
165     *
166     * <pre>
167     * int seed = 0x9747b28c;
168     * byte[] bytes = data.getBytes(StandardCharsets.UTF_8);
169     * int hash = MurmurHash2.hash32(bytes, bytes.length, seed);
170     * </pre>
171     *
172     * @param text The input string
173     * @return The 32-bit hash
174     * @see #hash32(byte[], int, int)
175     */
176    public static int hash32(final String text) {
177        final byte[] bytes = StringUtils.getBytesUtf8(text);
178        return hash32(bytes, bytes.length);
179    }
180
181    /**
182     * Generates a 32-bit hash from a substring with a default seed value.
183     * The string is converted to bytes using the default encoding.
184     * This is a helper method that will produce the same result as:
185     *
186     * <pre>
187     * int seed = 0x9747b28c;
188     * byte[] bytes = text.substring(from, from + length).getBytes(StandardCharsets.UTF_8);
189     * int hash = MurmurHash2.hash32(bytes, bytes.length, seed);
190     * </pre>
191     *
192     * @param text The input string
193     * @param from The starting index
194     * @param length The length of the substring
195     * @return The 32-bit hash
196     * @see #hash32(byte[], int, int)
197     */
198    public static int hash32(final String text, final int from, final int length) {
199        return hash32(text.substring(from, from + length));
200    }
201
202    /**
203     * Generates a 64-bit hash from byte array with given length and a default seed value.
204     * This is a helper method that will produce the same result as:
205     *
206     * <pre>
207     * int seed = 0xe17a1465;
208     * int hash = MurmurHash2.hash64(data, length, seed);
209     * </pre>
210     *
211     * @param data The input byte array
212     * @param length The length of the array
213     * @return The 64-bit hash
214     * @see #hash64(byte[], int, int)
215     */
216    public static long hash64(final byte[] data, final int length) {
217        return hash64(data, length, 0xe17a1465);
218    }
219
220    /**
221     * Generates a 64-bit hash from byte array of the given length and seed.
222     *
223     * @param data The input byte array
224     * @param length The length of the array
225     * @param seed The initial seed value
226     * @return The 64-bit hash of the given array
227     */
228    public static long hash64(final byte[] data, final int length, final int seed) {
229        long h = seed & 0xffffffffL ^ length * M64;
230
231        final int nblocks = length >> 3;
232
233        // body
234        for (int i = 0; i < nblocks; i++) {
235            final int index = i << 3;
236            long k = getLittleEndianLong(data, index);
237
238            k *= M64;
239            k ^= k >>> R64;
240            k *= M64;
241
242            h ^= k;
243            h *= M64;
244        }
245
246        final int index = nblocks << 3;
247        switch (length - index) {
248        case 7:
249            h ^= ((long) data[index + 6] & 0xff) << 48;
250        case 6:
251            h ^= ((long) data[index + 5] & 0xff) << 40;
252        case 5:
253            h ^= ((long) data[index + 4] & 0xff) << 32;
254        case 4:
255            h ^= ((long) data[index + 3] & 0xff) << 24;
256        case 3:
257            h ^= ((long) data[index + 2] & 0xff) << 16;
258        case 2:
259            h ^= ((long) data[index + 1] & 0xff) << 8;
260        case 1:
261            h ^= (long) data[index] & 0xff;
262            h *= M64;
263        }
264
265        h ^= h >>> R64;
266        h *= M64;
267        h ^= h >>> R64;
268
269        return h;
270    }
271
272    /**
273     * Generates a 64-bit hash from a string with a default seed.
274     * <p>
275     * Before 1.14 the string was converted using default encoding.
276     * Since 1.14 the string is converted to bytes using UTF-8 encoding.
277     * </p>
278     * <p>
279     * This is a helper method that will produce the same result as:
280     * </p>
281     *
282     * <pre>
283     * int seed = 0xe17a1465;
284     * byte[] bytes = data.getBytes(StandardCharsets.UTF_8);
285     * int hash = MurmurHash2.hash64(bytes, bytes.length, seed);
286     * </pre>
287     *
288     * @param text The input string
289     * @return The 64-bit hash
290     * @see #hash64(byte[], int, int)
291     */
292    public static long hash64(final String text) {
293        final byte[] bytes = StringUtils.getBytesUtf8(text);
294        return hash64(bytes, bytes.length);
295    }
296
297    /**
298     * Generates a 64-bit hash from a substring with a default seed value.
299     * The string is converted to bytes using the default encoding.
300     * This is a helper method that will produce the same result as:
301     *
302     * <pre>
303     * int seed = 0xe17a1465;
304     * byte[] bytes = text.substring(from, from + length).getBytes(StandardCharsets.UTF_8);
305     * int hash = MurmurHash2.hash64(bytes, bytes.length, seed);
306     * </pre>
307     *
308     * @param text The input string
309     * @param from The starting index
310     * @param length The length of the substring
311     * @return The 64-bit hash
312     * @see #hash64(byte[], int, int)
313     */
314    public static long hash64(final String text, final int from, final int length) {
315        return hash64(text.substring(from, from + length));
316    }
317
318    /** No instance methods. */
319    private MurmurHash2() {
320    }
321}