    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 java.nio.charset.Charset;
    021import java.nio.charset.StandardCharsets;
    022
    023import org.apache.commons.codec.binary.StringUtils;
    024
    025/**
    026 * Implementation of the MurmurHash3 32-bit and 128-bit hash functions.
    027 *
    028 * <p>
    029 * MurmurHash is a non-cryptographic hash function suitable for general hash-based lookup. The name comes from two basic
    030 * operations, multiply (MU) and rotate (R), used in its inner loop. Unlike cryptographic hash functions, it is not
    031 * specifically designed to be difficult to reverse by an adversary, making it unsuitable for cryptographic purposes.
    032 * </p>
    033 *
    034 * <p>
    035 * This contains a Java port of the 32-bit hash function {@code MurmurHash3_x86_32} and the 128-bit hash function
    036 * {@code MurmurHash3_x64_128} from Austin Applyby's original {@code c++} code in SMHasher.
    037 * </p>
    038 *
    039 * <p>
    040 * This is public domain code with no copyrights. From home page of
    041 * <a href="https://github.com/aappleby/smhasher">SMHasher</a>:
    042 * </p>
    043 *
    044 * <blockquote> "All MurmurHash versions are public domain software, and the author disclaims all copyright to their
    045 * code." </blockquote>
    046 *
    047 * <p>
    048 * Original adaption from Apache Hive. That adaption contains a {@code hash64} method that is not part of the original
    049 * MurmurHash3 code. It is not recommended to use these methods. They will be removed in a future release. To obtain a
    050 * 64-bit hash use half of the bits from the {@code hash128x64} methods using the input data converted to bytes.
    051 * <p>
    052 *
    053 * @see <a href="https://en.wikipedia.org/wiki/MurmurHash">MurmurHash</a>
    054 * @see <a href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp"> Original MurmurHash3 c++
    055 *      code</a>
    056 * @see <a href=
    057 *      "https://github.com/apache/hive/blob/master/storage-api/src/java/org/apache/hive/common/util/Murmur3.java">
    058 *      Apache Hive Murmer3</a>
    059 * @since 1.13
    060 */
    061public final class MurmurHash3 {
    062
    063    /**
    064     * A random number to use for a hash code.
    065     *
    066     * @deprecated This is not used internally and will be removed in a future release.
    067     */
    068    @Deprecated
    069    public static final long NULL_HASHCODE = 2862933555777941757L;
    070
    071    /**
    072     * A default seed to use for the murmur hash algorithm.
    073     * Has the value {@code 104729}.
    074     */
    075    public static final int DEFAULT_SEED = 104729;
    076
    077    /** TODO Replace on Java 8 with Long.BYTES. */
    078    static final int LONG_BYTES = Long.SIZE / Byte.SIZE;
    079
    080    /** TODO Replace on Java 8 with Integer.BYTES. */
    081    static final int INTEGER_BYTES = Integer.SIZE / Byte.SIZE;
    082
    083    /** TODO Replace on Java 8 with Short.BYTES. */
    084    static final int SHORT_BYTES = Short.SIZE / Byte.SIZE;
    085
    086    // Constants for 32-bit variant
    087    private static final int C1_32 = 0xcc9e2d51;
    088    private static final int C2_32 = 0x1b873593;
    089    private static final int R1_32 = 15;
    090    private static final int R2_32 = 13;
    091    private static final int M_32 = 5;
    092    private static final int N_32 = 0xe6546b64;
    093
    094    // Constants for 128-bit variant
    095    private static final long C1 = 0x87c37b91114253d5L;
    096    private static final long C2 = 0x4cf5ad432745937fL;
    097    private static final int R1 = 31;
    098    private static final int R2 = 27;
    099    private static final int R3 = 33;
    100    private static final int M = 5;
    101    private static final int N1 = 0x52dce729;
    102    private static final int N2 = 0x38495ab5;
    103
    104    /** No instance methods. */
    105    private MurmurHash3() {
    106    }
    107
    108    /**
    109     * Generates 32-bit hash from two longs with a default seed value.
    110     * This is a helper method that will produce the same result as:
    111     *
    112     * <pre>
    113     * int offset = 0;
    114     * int seed = 104729;
    115     * int hash = MurmurHash3.hash32x86(ByteBuffer.allocate(16)
    116     *                                            .putLong(data1)
    117     *                                            .putLong(data2)
    118     *                                            .array(), offset, 16, seed);
    119     * </pre>
    120     *
    121     * @param data1 The first long to hash
    122     * @param data2 The second long to hash
    123     * @return The 32-bit hash
    124     * @see #hash32x86(byte[], int, int, int)
    125     */
    126    public static int hash32(final long data1, final long data2) {
    127        return hash32(data1, data2, DEFAULT_SEED);
    128    }
    129
    130    /**
    131     * Generates 32-bit hash from two longs with the given seed.
    132     * This is a helper method that will produce the same result as:
    133     *
    134     * <pre>
    135     * int offset = 0;
    136     * int hash = MurmurHash3.hash32x86(ByteBuffer.allocate(16)
    137     *                                            .putLong(data1)
    138     *                                            .putLong(data2)
    139     *                                            .array(), offset, 16, seed);
    140     * </pre>
    141     *
    142     * @param data1 The first long to hash
    143     * @param data2 The second long to hash
    144     * @param seed The initial seed value
    145     * @return The 32-bit hash
    146     * @see #hash32x86(byte[], int, int, int)
    147     */
    148    public static int hash32(final long data1, final long data2, final int seed) {
    149        int hash = seed;
    150        final long r0 = Long.reverseBytes(data1);
    151        final long r1 = Long.reverseBytes(data2);
    152
    153        hash = mix32((int) r0, hash);
    154        hash = mix32((int) (r0 >>> 32), hash);
    155        hash = mix32((int) (r1), hash);
    156        hash = mix32((int) (r1 >>> 32), hash);
    157
    158        hash ^= LONG_BYTES * 2;
    159        return fmix32(hash);
    160    }
    161
    162    /**
    163     * Generates 32-bit hash from a long with a default seed value.
    164     * This is a helper method that will produce the same result as:
    165     *
    166     * <pre>
    167     * int offset = 0;
    168     * int seed = 104729;
    169     * int hash = MurmurHash3.hash32x86(ByteBuffer.allocate(8)
    170     *                                            .putLong(data)
    171     *                                            .array(), offset, 8, seed);
    172     * </pre>
    173     *
    174     * @param data The long to hash
    175     * @return The 32-bit hash
    176     * @see #hash32x86(byte[], int, int, int)
    177     */
    178    public static int hash32(final long data) {
    179        return hash32(data, DEFAULT_SEED);
    180    }
    181
    182    /**
    183     * Generates 32-bit hash from a long with the given seed.
    184     * This is a helper method that will produce the same result as:
    185     *
    186     * <pre>
    187     * int offset = 0;
    188     * int hash = MurmurHash3.hash32x86(ByteBuffer.allocate(8)
    189     *                                            .putLong(data)
    190     *                                            .array(), offset, 8, seed);
    191     * </pre>
    192     *
    193     * @param data The long to hash
    194     * @param seed The initial seed value
    195     * @return The 32-bit hash
    196     * @see #hash32x86(byte[], int, int, int)
    197     */
    198    public static int hash32(final long data, final int seed) {
    199        int hash = seed;
    200        final long r0 = Long.reverseBytes(data);
    201
    202        hash = mix32((int) r0, hash);
    203        hash = mix32((int) (r0 >>> 32), hash);
    204
    205        hash ^= LONG_BYTES;
    206        return fmix32(hash);
    207    }
    208
    209    /**
    210     * Generates 32-bit hash from the byte array with a default seed.
    211     * This is a helper method that will produce the same result as:
    212     *
    213     * <pre>
    214     * int offset = 0;
    215     * int seed = 104729;
    216     * int hash = MurmurHash3.hash32(data, offset, data.length, seed);
    217     * </pre>
    218     *
    219     * <p>This implementation contains a sign-extension bug in the finalization step of
    220     * any bytes left over from dividing the length by 4. This manifests if any of these
    221     * bytes are negative.<p>
    222     *
    223     * @param data The input byte array
    224     * @return The 32-bit hash
    225     * @see #hash32(byte[], int, int, int)
    226     * @deprecated Use {@link #hash32x86(byte[], int, int, int)}. This corrects the processing of trailing bytes.
    227     */
    228    @Deprecated
    229    public static int hash32(final byte[] data) {
    230        return hash32(data, 0, data.length, DEFAULT_SEED);
    231    }
    232
    233    /**
    234     * Generates 32-bit hash from a string with a default seed.
    235     * <p>
    236     * Before 1.14 the string was converted using default encoding.
    237     * Since 1.14 the string is converted to bytes using UTF-8 encoding.
    238     * </p>
    239     * This is a helper method that will produce the same result as:
    240     *
    241     * <pre>
    242     * int offset = 0;
    243     * int seed = 104729;
    244     * byte[] bytes = data.getBytes(StandardCharsets.UTF_8);
    245     * int hash = MurmurHash3.hash32(bytes, offset, bytes.length, seed);
    246     * </pre>
    247     *
    248     * <p>This implementation contains a sign-extension bug in the finalization step of
    249     * any bytes left over from dividing the length by 4. This manifests if any of these
    250     * bytes are negative.<p>
    251     *
    252     * @param data The input string
    253     * @return The 32-bit hash
    254     * @see #hash32(byte[], int, int, int)
    255     * @deprecated Use {@link #hash32x86(byte[], int, int, int)} with the bytes returned from
    256     * {@link String#getBytes(java.nio.charset.Charset)}. This corrects the processing of trailing bytes.
    257     */
    258    @Deprecated
    259    public static int hash32(final String data) {
    260        final byte[] bytes = StringUtils.getBytesUtf8(data);
    261        return hash32(bytes, 0, bytes.length, DEFAULT_SEED);
    262    }
    263
    264    /**
    265     * Generates 32-bit hash from the byte array with the given length and a default seed.
    266     * This is a helper method that will produce the same result as:
    267     *
    268     * <pre>
    269     * int offset = 0;
    270     * int seed = 104729;
    271     * int hash = MurmurHash3.hash32(data, offset, length, seed);
    272     * </pre>
    273     *
    274     * <p>This implementation contains a sign-extension bug in the finalization step of
    275     * any bytes left over from dividing the length by 4. This manifests if any of these
    276     * bytes are negative.<p>
    277     *
    278     * @param data The input byte array
    279     * @param length The length of array
    280     * @return The 32-bit hash
    281     * @see #hash32(byte[], int, int, int)
    282     * @deprecated Use {@link #hash32x86(byte[], int, int, int)}. This corrects the processing of trailing bytes.
    283     */
    284    @Deprecated
    285    public static int hash32(final byte[] data, final int length) {
    286        return hash32(data, length, DEFAULT_SEED);
    287    }
    288
    289    /**
    290     * Generates 32-bit hash from the byte array with the given length and seed. This is a
    291     * helper method that will produce the same result as:
    292     *
    293     * <pre>
    294     * int offset = 0;
    295     * int hash = MurmurHash3.hash32(data, offset, length, seed);
    296     * </pre>
    297     *
    298     * <p>This implementation contains a sign-extension bug in the finalization step of
    299     * any bytes left over from dividing the length by 4. This manifests if any of these
    300     * bytes are negative.<p>
    301     *
    302     * @param data The input byte array
    303     * @param length The length of array
    304     * @param seed The initial seed value
    305     * @return The 32-bit hash
    306     * @see #hash32(byte[], int, int, int)
    307     * @deprecated Use {@link #hash32x86(byte[], int, int, int)}. This corrects the processing of trailing bytes.
    308     */
    309    @Deprecated
    310    public static int hash32(final byte[] data, final int length, final int seed) {
    311        return hash32(data, 0, length, seed);
    312    }
    313
    314    /**
    315     * Generates 32-bit hash from the byte array with the given offset, length and seed.
    316     *
    317     * <p>This is an implementation of the 32-bit hash function {@code MurmurHash3_x86_32}
    318     * from from Austin Applyby's original MurmurHash3 {@code c++} code in SMHasher.</p>
    319     *
    320     * <p>This implementation contains a sign-extension bug in the finalization step of
    321     * any bytes left over from dividing the length by 4. This manifests if any of these
    322     * bytes are negative.<p>
    323     *
    324     * @param data The input byte array
    325     * @param offset The offset of data
    326     * @param length The length of array
    327     * @param seed The initial seed value
    328     * @return The 32-bit hash
    329     * @deprecated Use {@link #hash32x86(byte[], int, int, int)}. This corrects the processing of trailing bytes.
    330     */
    331    @Deprecated
    332    public static int hash32(final byte[] data, final int offset, final int length, final int seed) {
    333        int hash = seed;
    334        final int nblocks = length >> 2;
    335
    336        // body
    337        for (int i = 0; i < nblocks; i++) {
    338            final int index = offset + (i << 2);
    339            final int k = getLittleEndianInt(data, index);
    340            hash = mix32(k, hash);
    341        }
    342
    343        // tail
    344        // ************
    345        // Note: This fails to apply masking using 0xff to the 3 remaining bytes.
    346        // ************
    347        final int index = offset + (nblocks << 2);
    348        int k1 = 0;
    349        switch (offset + length - index) {
    350        case 3:
    351            k1 ^= data[index + 2] << 16;
    352        case 2:
    353            k1 ^= data[index + 1] << 8;
    354        case 1:
    355            k1 ^= data[index];
    356
    357            // mix functions
    358            k1 *= C1_32;
    359            k1 = Integer.rotateLeft(k1, R1_32);
    360            k1 *= C2_32;
    361            hash ^= k1;
    362        }
    363
    364        hash ^= length;
    365        return fmix32(hash);
    366    }
    367
    368    /**
    369     * Generates 32-bit hash from the byte array with a seed of zero.
    370     * This is a helper method that will produce the same result as:
    371     *
    372     * <pre>
    373     * int offset = 0;
    374     * int seed = 0;
    375     * int hash = MurmurHash3.hash32x86(data, offset, data.length, seed);
    376     * </pre>
    377     *
    378     * @param data The input byte array
    379     * @return The 32-bit hash
    380     * @see #hash32x86(byte[], int, int, int)
    381     * @since 1.14
    382     */
    383    public static int hash32x86(final byte[] data) {
    384        return hash32x86(data, 0, data.length, 0);
    385    }
    386
    387    /**
    388     * Generates 32-bit hash from the byte array with the given offset, length and seed.
    389     *
    390     * <p>This is an implementation of the 32-bit hash function {@code MurmurHash3_x86_32}
    391     * from from Austin Applyby's original MurmurHash3 {@code c++} code in SMHasher.</p>
    392     *
    393     * @param data The input byte array
    394     * @param offset The offset of data
    395     * @param length The length of array
    396     * @param seed The initial seed value
    397     * @return The 32-bit hash
    398     * @since 1.14
    399     */
    400    public static int hash32x86(final byte[] data, final int offset, final int length, final int seed) {
    401        int hash = seed;
    402        final int nblocks = length >> 2;
    403
    404        // body
    405        for (int i = 0; i < nblocks; i++) {
    406            final int index = offset + (i << 2);
    407            final int k = getLittleEndianInt(data, index);
    408            hash = mix32(k, hash);
    409        }
    410
    411        // tail
    412        final int index = offset + (nblocks << 2);
    413        int k1 = 0;
    414        switch (offset + length - index) {
    415        case 3:
    416            k1 ^= (data[index + 2] & 0xff) << 16;
    417        case 2:
    418            k1 ^= (data[index + 1] & 0xff) << 8;
    419        case 1:
    420            k1 ^= (data[index] & 0xff);
    421
    422            // mix functions
    423            k1 *= C1_32;
    424            k1 = Integer.rotateLeft(k1, R1_32);
    425            k1 *= C2_32;
    426            hash ^= k1;
    427        }
    428
    429        hash ^= length;
    430        return fmix32(hash);
    431    }
    432
    433    /**
    434     * Generates 64-bit hash from a long with a default seed.
    435     *
    436     * <p><strong>This is not part of the original MurmurHash3 {@code c++} implementation.</strong></p>
    437     *
    438     * <p>This is a Murmur3-like 64-bit variant.
    439     * The method does not produce the same result as either half of the hash bytes from
    440     * {@linkplain #hash128x64(byte[])} with the same byte data from the {@code long}.
    441     * This method will be removed in a future release.</p>
    442     *
    443     * <p>Note: The sign extension bug in {@link #hash64(byte[], int, int, int)} does not effect
    444     * this result as the default seed is positive.</p>
    445     *
    446     * <p>This is a helper method that will produce the same result as:</p>
    447     *
    448     * <pre>
    449     * int offset = 0;
    450     * int seed = 104729;
    451     * long hash = MurmurHash3.hash64(ByteBuffer.allocate(8)
    452     *                                          .putLong(data)
    453     *                                          .array(), offset, 8, seed);
    454     * </pre>
    455     *
    456     * @param data The long to hash
    457     * @return The 64-bit hash
    458     * @see #hash64(byte[], int, int, int)
    459     * @deprecated Not part of the MurmurHash3 implementation.
    460     * Use half of the hash bytes from {@link #hash128x64(byte[])} with the bytes from the {@code long}.
    461     */
    462    @Deprecated
    463    public static long hash64(final long data) {
    464        long hash = DEFAULT_SEED;
    465        long k = Long.reverseBytes(data);
    466        final int length = LONG_BYTES;
    467        // mix functions
    468        k *= C1;
    469        k = Long.rotateLeft(k, R1);
    470        k *= C2;
    471        hash ^= k;
    472        hash = Long.rotateLeft(hash, R2) * M + N1;
    473        // finalization
    474        hash ^= length;
    475        hash = fmix64(hash);
    476        return hash;
    477    }
    478
    479    /**
    480     * Generates 64-bit hash from an int with a default seed.
    481     *
    482     * <p><strong>This is not part of the original MurmurHash3 {@code c++} implementation.</strong></p>
    483     *
    484     * <p>This is a Murmur3-like 64-bit variant.
    485     * The method does not produce the same result as either half of the hash bytes from
    486     * {@linkplain #hash128x64(byte[])} with the same byte data from the {@code int}.
    487     * This method will be removed in a future release.</p>
    488     *
    489     * <p>Note: The sign extension bug in {@link #hash64(byte[], int, int, int)} does not effect
    490     * this result as the default seed is positive.</p>
    491     *
    492     * <p>This is a helper method that will produce the same result as:</p>
    493     *
    494     * <pre>
    495     * int offset = 0;
    496     * int seed = 104729;
    497     * long hash = MurmurHash3.hash64(ByteBuffer.allocate(4)
    498     *                                          .putInt(data)
    499     *                                          .array(), offset, 4, seed);
    500     * </pre>
    501     *
    502     * @param data The int to hash
    503     * @return The 64-bit hash
    504     * @see #hash64(byte[], int, int, int)
    505     * @deprecated Not part of the MurmurHash3 implementation.
    506     * Use half of the hash bytes from {@link #hash128x64(byte[])} with the bytes from the {@code int}.
    507     */
    508    @Deprecated
    509    public static long hash64(final int data) {
    510        long k1 = Integer.reverseBytes(data) & (-1L >>> 32);
    511        final int length = INTEGER_BYTES;
    512        long hash = DEFAULT_SEED;
    513        k1 *= C1;
    514        k1 = Long.rotateLeft(k1, R1);
    515        k1 *= C2;
    516        hash ^= k1;
    517        // finalization
    518        hash ^= length;
    519        hash = fmix64(hash);
    520        return hash;
    521    }
    522
    523    /**
    524     * Generates 64-bit hash from a short with a default seed.
    525     *
    526     * <p><strong>This is not part of the original MurmurHash3 {@code c++} implementation.</strong></p>
    527     *
    528     * <p>This is a Murmur3-like 64-bit variant.
    529     * The method does not produce the same result as either half of the hash bytes from
    530     * {@linkplain #hash128x64(byte[])} with the same byte data from the {@code short}.
    531     * This method will be removed in a future release.</p>
    532     *
    533     * <p>Note: The sign extension bug in {@link #hash64(byte[], int, int, int)} does not effect
    534     * this result as the default seed is positive.</p>
    535     *
    536     * <p>This is a helper method that will produce the same result as:</p>
    537     *
    538     * <pre>
    539     * int offset = 0;
    540     * int seed = 104729;
    541     * long hash = MurmurHash3.hash64(ByteBuffer.allocate(2)
    542     *                                          .putShort(data)
    543     *                                          .array(), offset, 2, seed);
    544     * </pre>
    545     *
    546     * @param data The short to hash
    547     * @return The 64-bit hash
    548     * @see #hash64(byte[], int, int, int)
    549     * @deprecated Not part of the MurmurHash3 implementation.
    550     * Use half of the hash bytes from {@link #hash128x64(byte[])} with the bytes from the {@code short}.
    551     */
    552    @Deprecated
    553    public static long hash64(final short data) {
    554        long hash = DEFAULT_SEED;
    555        long k1 = 0;
    556        k1 ^= ((long) data & 0xff) << 8;
    557        k1 ^= ((long) ((data & 0xFF00) >> 8) & 0xff);
    558        k1 *= C1;
    559        k1 = Long.rotateLeft(k1, R1);
    560        k1 *= C2;
    561        hash ^= k1;
    562
    563        // finalization
    564        hash ^= SHORT_BYTES;
    565        hash = fmix64(hash);
    566        return hash;
    567    }
    568
    569    /**
    570     * Generates 64-bit hash from a byte array with a default seed.
    571     *
    572     * <p><strong>This is not part of the original MurmurHash3 {@code c++} implementation.</strong></p>
    573     *
    574     * <p>This is a Murmur3-like 64-bit variant.
    575     * The method does not produce the same result as either half of the hash bytes from
    576     * {@linkplain #hash128x64(byte[])} with the same byte data.
    577     * This method will be removed in a future release.</p>
    578     *
    579     * <p>Note: The sign extension bug in {@link #hash64(byte[], int, int, int)} does not effect
    580     * this result as the default seed is positive.</p>
    581     *
    582     * <p>This is a helper method that will produce the same result as:</p>
    583     *
    584     * <pre>
    585     * int offset = 0;
    586     * int seed = 104729;
    587     * long hash = MurmurHash3.hash64(data, offset, data.length, seed);
    588     * </pre>
    589     *
    590     * @param data The input byte array
    591     * @return The 64-bit hash
    592     * @see #hash64(byte[], int, int, int)
    593     * @deprecated Not part of the MurmurHash3 implementation.
    594     * Use half of the hash bytes from {@link #hash128x64(byte[])}.
    595     */
    596    @Deprecated
    597    public static long hash64(final byte[] data) {
    598        return hash64(data, 0, data.length, DEFAULT_SEED);
    599    }
    600
    601    /**
    602     * Generates 64-bit hash from a byte array with the given offset and length and a default seed.
    603     *
    604     * <p><strong>This is not part of the original MurmurHash3 {@code c++} implementation.</strong></p>
    605     *
    606     * <p>This is a Murmur3-like 64-bit variant.
    607     * The method does not produce the same result as either half of the hash bytes from
    608     * {@linkplain #hash128x64(byte[])} with the same byte data.
    609     * This method will be removed in a future release.</p>
    610     *
    611     * <p>Note: The sign extension bug in {@link #hash64(byte[], int, int, int)} does not effect
    612     * this result as the default seed is positive.</p>
    613     *
    614     * <p>This is a helper method that will produce the same result as:</p>
    615     *
    616     * <pre>
    617     * int seed = 104729;
    618     * long hash = MurmurHash3.hash64(data, offset, length, seed);
    619     * </pre>
    620     *
    621     * @param data The input byte array
    622     * @param offset The offset of data
    623     * @param length The length of array
    624     * @return The 64-bit hash
    625     * @see #hash64(byte[], int, int, int)
    626     * @deprecated Not part of the MurmurHash3 implementation.
    627     * Use half of the hash bytes from {@link #hash128x64(byte[], int, int, int)}.
    628     */
    629    @Deprecated
    630    public static long hash64(final byte[] data, final int offset, final int length) {
    631        return hash64(data, offset, length, DEFAULT_SEED);
    632    }
    633
    634    /**
    635     * Generates 64-bit hash from a byte array with the given offset, length and seed.
    636     *
    637     * <p><strong>This is not part of the original MurmurHash3 {@code c++} implementation.</strong></p>
    638     *
    639     * <p>This is a Murmur3-like 64-bit variant.
    640     * This method will be removed in a future release.</p>
    641     *
    642     * <p>This implementation contains a sign-extension bug in the seed initialization.
    643     * This manifests if the seed is negative.</p>
    644     *
    645     * <p>This algorithm processes 8 bytes chunks of data in a manner similar to the 16 byte chunks
    646     * of data processed in the MurmurHash3 {@code MurmurHash3_x64_128} method. However the hash
    647     * is not mixed with a hash chunk from the next 8 bytes of data. The method will not return
    648     * the same value as the first or second 64-bits of the function
    649     * {@link #hash128(byte[], int, int, int)}.</p>
    650     *
    651     * <p>Use of this method is not advised. Use the first long returned from
    652     * {@link #hash128x64(byte[], int, int, int)}.<p>
    653     *
    654     * @param data The input byte array
    655     * @param offset The offset of data
    656     * @param length The length of array
    657     * @param seed The initial seed value
    658     * @return The 64-bit hash
    659     * @deprecated Not part of the MurmurHash3 implementation.
    660     * Use half of the hash bytes from {@link #hash128x64(byte[], int, int, int)}.
    661     */
    662    @Deprecated
    663    public static long hash64(final byte[] data, final int offset, final int length, final int seed) {
    664        // ************
    665        // Note: This fails to apply masking using 0xffffffffL to the seed.
    666        // ************
    667        long hash = seed;
    668        final int nblocks = length >> 3;
    669
    670        // body
    671        for (int i = 0; i < nblocks; i++) {
    672            final int index = offset + (i << 3);
    673            long k = getLittleEndianLong(data, index);
    674
    675            // mix functions
    676            k *= C1;
    677            k = Long.rotateLeft(k, R1);
    678            k *= C2;
    679            hash ^= k;
    680            hash = Long.rotateLeft(hash, R2) * M + N1;
    681        }
    682
    683        // tail
    684        long k1 = 0;
    685        final int index = offset + (nblocks << 3);
    686        switch (offset + length - index) {
    687        case 7:
    688            k1 ^= ((long) data[index + 6] & 0xff) << 48;
    689        case 6:
    690            k1 ^= ((long) data[index + 5] & 0xff) << 40;
    691        case 5:
    692            k1 ^= ((long) data[index + 4] & 0xff) << 32;
    693        case 4:
    694            k1 ^= ((long) data[index + 3] & 0xff) << 24;
    695        case 3:
    696            k1 ^= ((long) data[index + 2] & 0xff) << 16;
    697        case 2:
    698            k1 ^= ((long) data[index + 1] & 0xff) << 8;
    699        case 1:
    700            k1 ^= ((long) data[index] & 0xff);
    701            k1 *= C1;
    702            k1 = Long.rotateLeft(k1, R1);
    703            k1 *= C2;
    704            hash ^= k1;
    705        }
    706
    707        // finalization
    708        hash ^= length;
    709        hash = fmix64(hash);
    710
    711        return hash;
    712    }
    713
    714    /**
    715     * Generates 128-bit hash from the byte array with a default seed.
    716     * This is a helper method that will produce the same result as:
    717     *
    718     * <pre>
    719     * int offset = 0;
    720     * int seed = 104729;
    721     * int hash = MurmurHash3.hash128(data, offset, data.length, seed);
    722     * </pre>
    723     *
    724     * <p>Note: The sign extension bug in {@link #hash128(byte[], int, int, int)} does not effect
    725     * this result as the default seed is positive.</p>
    726     *
    727     * @param data The input byte array
    728     * @return The 128-bit hash (2 longs)
    729     * @see #hash128(byte[], int, int, int)
    730     */
    731    public static long[] hash128(final byte[] data) {
    732        return hash128(data, 0, data.length, DEFAULT_SEED);
    733    }
    734
    735    /**
    736     * Generates 128-bit hash from the byte array with a seed of zero.
    737     * This is a helper method that will produce the same result as:
    738     *
    739     * <pre>
    740     * int offset = 0;
    741     * int seed = 0;
    742     * int hash = MurmurHash3.hash128x64(data, offset, data.length, seed);
    743     * </pre>
    744     *
    745     * @param data The input byte array
    746     * @return The 128-bit hash (2 longs)
    747     * @see #hash128x64(byte[], int, int, int)
    748     * @since 1.14
    749     */
    750    public static long[] hash128x64(final byte[] data) {
    751        return hash128x64(data, 0, data.length, 0);
    752    }
    753
    754    /**
    755     * Generates 128-bit hash from a string with a default seed.
    756     * <p>
    757     * Before 1.14 the string was converted using default encoding.
    758     * Since 1.14 the string is converted to bytes using UTF-8 encoding.
    759     * </p>
    760     * This is a helper method that will produce the same result as:
    761     *
    762     * <pre>
    763     * int offset = 0;
    764     * int seed = 104729;
    765     * byte[] bytes = data.getBytes(StandardCharsets.UTF_8);
    766     * int hash = MurmurHash3.hash128(bytes, offset, bytes.length, seed);
    767     * </pre>
    768     *
    769     * <p>Note: The sign extension bug in {@link #hash128(byte[], int, int, int)} does not effect
    770     * this result as the default seed is positive.</p>
    771     *
    772     * @param data The input String
    773     * @return The 128-bit hash (2 longs)
    774     * @see #hash128(byte[], int, int, int)
    775     * @deprecated Use {@link #hash128x64(byte[])} using the bytes returned from
    776     * {@link String#getBytes(java.nio.charset.Charset)}.
    777     */
    778    @Deprecated
    779    public static long[] hash128(final String data) {
    780        final byte[] bytes = StringUtils.getBytesUtf8(data);
    781        return hash128(bytes, 0, bytes.length, DEFAULT_SEED);
    782    }
    783
    784    /**
    785     * Generates 128-bit hash from the byte array with the given offset, length and seed.
    786     *
    787     * <p>This is an implementation of the 128-bit hash function {@code MurmurHash3_x64_128}
    788     * from from Austin Applyby's original MurmurHash3 {@code c++} code in SMHasher.</p>
    789     *
    790     * <p>This implementation contains a sign-extension bug in the seed initialization.
    791     * This manifests if the seed is negative.<p>
    792     *
    793     * @param data The input byte array
    794     * @param offset The first element of array
    795     * @param length The length of array
    796     * @param seed The initial seed value
    797     * @return The 128-bit hash (2 longs)
    798     * @deprecated Use {@link #hash128x64(byte[], int, int, int)}. This corrects the seed initialization.
    799     */
    800    @Deprecated
    801    public static long[] hash128(final byte[] data, final int offset, final int length, final int seed) {
    802        // ************
    803        // Note: This fails to apply masking using 0xffffffffL to the seed.
    804        // ************
    805        return hash128x64(data, offset, length, seed);
    806    }
    807
    808    /**
    809     * Generates 128-bit hash from the byte array with the given offset, length and seed.
    810     *
    811     * <p>This is an implementation of the 128-bit hash function {@code MurmurHash3_x64_128}
    812     * from from Austin Applyby's original MurmurHash3 {@code c++} code in SMHasher.</p>
    813     *
    814     * @param data The input byte array
    815     * @param offset The first element of array
    816     * @param length The length of array
    817     * @param seed The initial seed value
    818     * @return The 128-bit hash (2 longs)
    819     * @since 1.14
    820     */
    821    public static long[] hash128x64(final byte[] data, final int offset, final int length, final int seed) {
    822        // Use an unsigned 32-bit integer as the seed
    823        return hash128x64(data, offset, length, seed & 0xffffffffL);
    824    }
    825
    826    /**
    827     * Generates 128-bit hash from the byte array with the given offset, length and seed.
    828     *
    829     * <p>This is an implementation of the 128-bit hash function {@code MurmurHash3_x64_128}
    830     * from from Austin Applyby's original MurmurHash3 {@code c++} code in SMHasher.</p>
    831     *
    832     * @param data The input byte array
    833     * @param offset The first element of array
    834     * @param length The length of array
    835     * @param seed The initial seed value
    836     * @return The 128-bit hash (2 longs)
    837     */
    838    private static long[] hash128x64(final byte[] data, final int offset, final int length, final long seed) {
    839        long h1 = seed;
    840        long h2 = seed;
    841        final int nblocks = length >> 4;
    842
    843        // body
    844        for (int i = 0; i < nblocks; i++) {
    845            final int index = offset + (i << 4);
    846            long k1 = getLittleEndianLong(data, index);
    847            long k2 = getLittleEndianLong(data, index + 8);
    848
    849            // mix functions for k1
    850            k1 *= C1;
    851            k1 = Long.rotateLeft(k1, R1);
    852            k1 *= C2;
    853            h1 ^= k1;
    854            h1 = Long.rotateLeft(h1, R2);
    855            h1 += h2;
    856            h1 = h1 * M + N1;
    857
    858            // mix functions for k2
    859            k2 *= C2;
    860            k2 = Long.rotateLeft(k2, R3);
    861            k2 *= C1;
    862            h2 ^= k2;
    863            h2 = Long.rotateLeft(h2, R1);
    864            h2 += h1;
    865            h2 = h2 * M + N2;
    866        }
    867
    868        // tail
    869        long k1 = 0;
    870        long k2 = 0;
    871        final int index = offset + (nblocks << 4);
    872        switch (offset + length - index) {
    873        case 15:
    874            k2 ^= ((long) data[index + 14] & 0xff) << 48;
    875        case 14:
    876            k2 ^= ((long) data[index + 13] & 0xff) << 40;
    877        case 13:
    878            k2 ^= ((long) data[index + 12] & 0xff) << 32;
    879        case 12:
    880            k2 ^= ((long) data[index + 11] & 0xff) << 24;
    881        case 11:
    882            k2 ^= ((long) data[index + 10] & 0xff) << 16;
    883        case 10:
    884            k2 ^= ((long) data[index + 9] & 0xff) << 8;
    885        case 9:
    886            k2 ^= data[index + 8] & 0xff;
    887            k2 *= C2;
    888            k2 = Long.rotateLeft(k2, R3);
    889            k2 *= C1;
    890            h2 ^= k2;
    891
    892        case 8:
    893            k1 ^= ((long) data[index + 7] & 0xff) << 56;
    894        case 7:
    895            k1 ^= ((long) data[index + 6] & 0xff) << 48;
    896        case 6:
    897            k1 ^= ((long) data[index + 5] & 0xff) << 40;
    898        case 5:
    899            k1 ^= ((long) data[index + 4] & 0xff) << 32;
    900        case 4:
    901            k1 ^= ((long) data[index + 3] & 0xff) << 24;
    902        case 3:
    903            k1 ^= ((long) data[index + 2] & 0xff) << 16;
    904        case 2:
    905            k1 ^= ((long) data[index + 1] & 0xff) << 8;
    906        case 1:
    907            k1 ^= data[index] & 0xff;
    908            k1 *= C1;
    909            k1 = Long.rotateLeft(k1, R1);
    910            k1 *= C2;
    911            h1 ^= k1;
    912        }
    913
    914        // finalization
    915        h1 ^= length;
    916        h2 ^= length;
    917
    918        h1 += h2;
    919        h2 += h1;
    920
    921        h1 = fmix64(h1);
    922        h2 = fmix64(h2);
    923
    924        h1 += h2;
    925        h2 += h1;
    926
    927        return new long[] { h1, h2 };
    928    }
    929
    930    /**
    931     * Gets the little-endian long from 8 bytes starting at the specified index.
    932     *
    933     * @param data The data
    934     * @param index The index
    935     * @return The little-endian long
    936     */
    937    private static long getLittleEndianLong(final byte[] data, final int index) {
    938        return (((long) data[index    ] & 0xff)      ) |
    939               (((long) data[index + 1] & 0xff) <<  8) |
    940               (((long) data[index + 2] & 0xff) << 16) |
    941               (((long) data[index + 3] & 0xff) << 24) |
    942               (((long) data[index + 4] & 0xff) << 32) |
    943               (((long) data[index + 5] & 0xff) << 40) |
    944               (((long) data[index + 6] & 0xff) << 48) |
    945               (((long) data[index + 7] & 0xff) << 56);
    946    }
    947
    948    /**
    949     * Gets the little-endian int from 4 bytes starting at the specified index.
    950     *
    951     * @param data The data
    952     * @param index The index
    953     * @return The little-endian int
    954     */
    955    private static int getLittleEndianInt(final byte[] data, final int index) {
    956        return ((data[index    ] & 0xff)      ) |
    957               ((data[index + 1] & 0xff) <<  8) |
    958               ((data[index + 2] & 0xff) << 16) |
    959               ((data[index + 3] & 0xff) << 24);
    960    }
    961
    962    /**
    963     * Performs the intermediate mix step of the 32-bit hash function {@code MurmurHash3_x86_32}.
    964     *
    965     * @param k The data to add to the hash
    966     * @param hash The current hash
    967     * @return The new hash
    968     */
    969    private static int mix32(int k, int hash) {
    970        k *= C1_32;
    971        k = Integer.rotateLeft(k, R1_32);
    972        k *= C2_32;
    973        hash ^= k;
    974        return Integer.rotateLeft(hash, R2_32) * M_32 + N_32;
    975    }
    976
    977    /**
    978     * Performs the final avalanche mix step of the 32-bit hash function {@code MurmurHash3_x86_32}.
    979     *
    980     * @param hash The current hash
    981     * @return The final hash
    982     */
    983    private static int fmix32(int hash) {
    984        hash ^= (hash >>> 16);
    985        hash *= 0x85ebca6b;
    986        hash ^= (hash >>> 13);
    987        hash *= 0xc2b2ae35;
    988        hash ^= (hash >>> 16);
    989        return hash;
    990    }
    991
    992    /**
    993     * Performs the final avalanche mix step of the 64-bit hash function {@code MurmurHash3_x64_128}.
    994     *
    995     * @param hash The current hash
    996     * @return The final hash
    997     */
    998    private static long fmix64(long hash) {
    999        hash ^= (hash >>> 33);
    1000        hash *= 0xff51afd7ed558ccdL;
    1001        hash ^= (hash >>> 33);
    1002        hash *= 0xc4ceb9fe1a85ec53L;
    1003        hash ^= (hash >>> 33);
    1004        return hash;
    1005    }
    1006
    1007    /**
    1008     * Generates 32-bit hash from input bytes. Bytes can be added incrementally and the new
    1009     * hash computed.
    1010     *
    1011     * <p>This is an implementation of the 32-bit hash function {@code MurmurHash3_x86_32}
    1012     * from from Austin Applyby's original MurmurHash3 {@code c++} code in SMHasher.</p>
    1013     *
    1014     * @since 1.14
    1015     */
    1016    public static class IncrementalHash32x86 {
    1017
    1018        /** The size of byte blocks that are processed together. */
    1019        private static final int BLOCK_SIZE = 4;
    1020
    1021        /** Up to 3 unprocessed bytes from input data. */
    1022        private final byte[] unprocessed = new byte[3];
    1023
    1024        /** The number of unprocessed bytes in the tail data. */
    1025        private int unprocessedLength;
    1026
    1027        /** The total number of input bytes added since the start. */
    1028        private int totalLen;
    1029
    1030        /**
    1031         * The current running hash.
    1032         * This must be finalised to generate the 32-bit hash value.
    1033         */
    1034        private int hash;
    1035
    1036        /**
    1037         * Starts a new incremental hash.
    1038         *
    1039         * @param seed The initial seed value
    1040         */
    1041        public final void start(final int seed) {
    1042            // Reset
    1043            unprocessedLength = totalLen = 0;
    1044            this.hash = seed;
    1045        }
    1046
    1047        /**
    1048         * Adds the byte array to the current incremental hash.
    1049         *
    1050         * @param data The input byte array
    1051         * @param offset The offset of data
    1052         * @param length The length of array
    1053         */
    1054        public final void add(final byte[] data, final int offset, final int length) {
    1055            if (length <= 0) {
    1056                // Nothing to add
    1057                return;
    1058            }
    1059            totalLen += length;
    1060
    1061            // Process the bytes in blocks of 4.
    1062            // New bytes must be added to any current unprocessed bytes,
    1063            // then processed in blocks of 4 and the remaining bytes saved:
    1064            //
    1065            //    |--|---------------------------|--|
    1066            // unprocessed
    1067            //                main block
    1068            //                                remaining
    1069
    1070            // Check if the unprocessed bytes and new bytes can fill a block of 4.
    1071            // Make this overflow safe in the event that length is Integer.MAX_VALUE.
    1072            // Equivalent to: (unprocessedLength + length < BLOCK_SIZE)
    1073            if (unprocessedLength + length - BLOCK_SIZE < 0) {
    1074                // Not enough so add to the unprocessed bytes
    1075                System.arraycopy(data, offset, unprocessed, unprocessedLength, length);
    1076                unprocessedLength += length;
    1077                return;
    1078            }
    1079
    1080            // Combine unprocessed bytes with new bytes.
    1081            int newOffset;
    1082            int newLength;
    1083            if (unprocessedLength > 0) {
    1084                int k = -1;
    1085                switch (unprocessedLength) {
    1086                case 1:
    1087                    k = orBytes(unprocessed[0], data[offset], data[offset + 1], data[offset + 2]);
    1088                    break;
    1089                case 2:
    1090                    k = orBytes(unprocessed[0], unprocessed[1], data[offset], data[offset + 1]);
    1091                    break;
    1092                case 3:
    1093                    k = orBytes(unprocessed[0], unprocessed[1], unprocessed[2], data[offset]);
    1094                    break;
    1095                default:
    1096                    throw new IllegalStateException("Unprocessed length should be 1, 2, or 3: " + unprocessedLength);
    1097                }
    1098                hash = mix32(k, hash);
    1099                // Update the offset and length
    1100                final int consumed = BLOCK_SIZE - unprocessedLength;
    1101                newOffset = offset + consumed;
    1102                newLength = length - consumed;
    1103            } else {
    1104                newOffset = offset;
    1105                newLength = length;
    1106            }
    1107
    1108            // Main processing of blocks of 4 bytes
    1109            final int nblocks = newLength >> 2;
    1110
    1111            for (int i = 0; i < nblocks; i++) {
    1112                final int index = newOffset + (i << 2);
    1113                final int k = getLittleEndianInt(data, index);
    1114                hash = mix32(k, hash);
    1115            }
    1116
    1117            // Save left-over unprocessed bytes
    1118            final int consumed = (nblocks << 2);
    1119            unprocessedLength = newLength - consumed;
    1120            if (unprocessedLength != 0) {
    1121                System.arraycopy(data, newOffset + consumed, unprocessed, 0, unprocessedLength);
    1122            }
    1123        }
    1124
    1125        /**
    1126         * Generate the 32-bit hash value. Repeat calls to this method with no additional data
    1127         * will generate the same hash value.
    1128         *
    1129         * @return The 32-bit hash
    1130         */
    1131        public final int end() {
    1132            // Allow calling end() again after adding no data to return the same result.
    1133            return finalise(hash, unprocessedLength, unprocessed, totalLen);
    1134        }
    1135
    1136        /**
    1137         * Finalize the running hash to the output 32-bit hash by processing remaining bytes
    1138         * and performing final mixing.
    1139         *
    1140         * @param hash The running hash
    1141         * @param unprocessedLength The number of unprocessed bytes in the tail data.
    1142         * @param unprocessed Up to 3 unprocessed bytes from input data.
    1143         * @param totalLen The total number of input bytes added since the start.
    1144         * @return The 32-bit hash
    1145         */
    1146        int finalise(final int hash, final int unprocessedLength, final byte[] unprocessed, final int totalLen) {
    1147            int result = hash;
    1148            int k1 = 0;
    1149            switch (unprocessedLength) {
    1150            case 3:
    1151                k1 ^= (unprocessed[2] & 0xff) << 16;
    1152            case 2:
    1153                k1 ^= (unprocessed[1] & 0xff) << 8;
    1154            case 1:
    1155                k1 ^= (unprocessed[0] & 0xff);
    1156
    1157                // mix functions
    1158                k1 *= C1_32;
    1159                k1 = Integer.rotateLeft(k1, R1_32);
    1160                k1 *= C2_32;
    1161                result ^= k1;
    1162            }
    1163
    1164            // finalization
    1165            result ^= totalLen;
    1166            return fmix32(result);
    1167        }
    1168
    1169        /**
    1170         * Combines the bytes using an Or operation ({@code | } in a little-endian representation
    1171         * of a 32-bit integer; byte 1 will be the least significant byte, byte 4 the most
    1172         * significant.
    1173         *
    1174         * @param b1 The first byte
    1175         * @param b2 The second byte
    1176         * @param b3 The third byte
    1177         * @param b4 The fourth byte
    1178         * @return The 32-bit integer
    1179         */
    1180        private static int orBytes(final byte b1, final byte b2, final byte b3, final byte b4) {
    1181            return (b1 & 0xff) | ((b2 & 0xff) << 8) | ((b3 & 0xff) << 16) | ((b4 & 0xff) << 24);
    1182        }
    1183    }
    1184
    1185    /**
    1186     * Generates 32-bit hash from input bytes. Bytes can be added incrementally and the new
    1187     * hash computed.
    1188     *
    1189     * <p>This is an implementation of the 32-bit hash function {@code MurmurHash3_x86_32}
    1190     * from from Austin Applyby's original MurmurHash3 {@code c++} code in SMHasher.</p>
    1191     *
    1192     * <p>This implementation contains a sign-extension bug in the finalization step of
    1193     * any bytes left over from dividing the length by 4. This manifests if any of these
    1194     * bytes are negative.<p>
    1195     *
    1196     * @deprecated Use IncrementalHash32x86. This corrects the processing of trailing bytes.
    1197     */
    1198    @Deprecated
    1199    public static class IncrementalHash32 extends IncrementalHash32x86 {
    1200
    1201        /**
    1202         * {@inheritDoc}
    1203         *
    1204         * <p>This implementation contains a sign-extension bug in the finalization step of
    1205         * any bytes left over from dividing the length by 4. This manifests if any of these
    1206         * bytes are negative.<p>
    1207         *
    1208         * @deprecated Use IncrementalHash32x86. This corrects the processing of trailing bytes.
    1209         */
    1210        @Override
    1211        @Deprecated
    1212        int finalise(final int hash, final int unprocessedLength, final byte[] unprocessed, final int totalLen) {
    1213            int result = hash;
    1214            // ************
    1215            // Note: This fails to apply masking using 0xff to the 3 remaining bytes.
    1216            // ************
    1217            int k1 = 0;
    1218            switch (unprocessedLength) {
    1219            case 3:
    1220                k1 ^= unprocessed[2] << 16;
    1221            case 2:
    1222                k1 ^= unprocessed[1] << 8;
    1223            case 1:
    1224                k1 ^= unprocessed[0];
    1225
    1226                // mix functions
    1227                k1 *= C1_32;
    1228                k1 = Integer.rotateLeft(k1, R1_32);
    1229                k1 *= C2_32;
    1230                result ^= k1;
    1231            }
    1232
    1233            // finalization
    1234            result ^= totalLen;
    1235            return fmix32(result);
    1236        }
    1237    }
    1238}