Source code

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 *      https://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 * Implements the MurmurHash2 32-bit and 64-bit hash functions.
024 *
025 * <p>
026 * MurmurHash is a non-cryptographic hash function suitable for general
027 * hash-based lookup. The name comes from two basic operations, multiply (MU)
028 * and rotate (R), used in its inner loop. Unlike cryptographic hash functions,
029 * it is not specifically designed to be difficult to reverse by an adversary,
030 * making it unsuitable for cryptographic purposes.
031 * </p>
032 *
033 * <p>
034 * This contains a Java port of the 32-bit hash function {@code MurmurHash2}
035 * and the 64-bit hash function {@code MurmurHash64A} from Austin Appleby's
036 * original {@code c++} code in SMHasher.
037 * </p>
038 *
039 * <p>
040 * This is a re-implementation of the original C code plus some additional
041 * features.
042 * </p>
043 *
044 * <p>
045 * This is public domain code with no copyrights. From home page of
046 * <a href="https://github.com/aappleby/smhasher">SMHasher</a>:
047 * </p>
048 *
049 * <blockquote>
050 * "All MurmurHash versions are public domain software, and the author
051 * disclaims all copyright to their code."
052 * </blockquote>
053 *
054 * @see <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>
055 * @see <a href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash2.cpp">
056 *   Original MurmurHash2 c++ code</a>
057 * @since 1.13
058 */
059public final class MurmurHash2 {
060
061    // Constants for 32-bit variant
062    private static final int M32 = 0x5bd1e995;
063    private static final int R32 = 24;
064
065    // Constants for 64-bit variant
066    private static final long M64 = 0xc6a4a7935bd1e995L;
067    private static final int R64 = 47;
068
069    /**
070     * Generates a 32-bit hash from byte array with the given length and a default seed value.
071     * This is a helper method that will produce the same result as:
072     *
073     * <pre>
074     * int seed = 0x9747b28c;
075     * int hash = MurmurHash2.hash32(data, length, seed);
076     * </pre>
077     *
078     * @param data The input byte array.
079     * @param length The length of the array.
080     * @return The 32-bit hash.
081     * @see #hash32(byte[], int, int)
082     */
083    public static int hash32(final byte[] data, final int length) {
084        return hash32(data, length, 0x9747b28c);
085    }
086
087    /**
088     * Generates a 32-bit hash from byte array with the given length and seed.
089     *
090     * @param data The input byte array.
091     * @param length The length of the array.
092     * @param seed The initial seed value.
093     * @return The 32-bit hash.
094     */
095    public static int hash32(final byte[] data, final int length, final int seed) {
096        // Initialize the hash to a random value
097        int h = seed ^ length;
098        // Mix 4 bytes at a time into the hash
099        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}