src/main/java/org/apache/datasketches/hash/MurmurHash3.java - datasketches-java - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *   http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing,
  * software distributed under the License is distributed on an
  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  * KIND, either express or implied.  See the License for the
  * specific language governing permissions and limitations
  * under the License.
  */

 package org.apache.datasketches.hash;

 import java.io.Serializable;
 import java.nio.ByteBuffer;
 import java.nio.ByteOrder;


 /**
  * <p>
  * The MurmurHash3 is a fast, non-cryptographic, 128-bit hash function that has
  * excellent avalanche and 2-way bit independence properties.
  * </p>
  *
  * <p>
  * Austin Appleby's C++
  * <a href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp">
  * MurmurHash3_x64_128(...), final revision 150</a>,
  * which is in the Public Domain, was the inspiration for this implementation in Java.
  * </p>
  *
  * <p>
  * This java implementation pays close attention to the C++ algorithms in order to
  * maintain bit-wise compatibility, but the design is quite different. This implementation has also
  * been extended to include processing of arrays of longs, char or ints, which was not part of the
  * original C++ implementation. This implementation produces the same exact output hash bits as
  * the above C++ method given the same input.</p>
  *
  * <p>In addition, with this implementation, the hash of byte[], char[], int[], or long[] will
  * produce the same hash result if, and only if, all the arrays have the same exact length in
  * bytes, and if the contents of the values in the arrays have the same byte endianness and
  * overall order. There is a unit test for this class that demonstrates this.</p>
  *
  * <p>
  * The structure of this implementation also reflects a separation of code that is dependent on the
  * input structure (in this case byte[], int[] or long[]) from code that is independent of the input
  * structure. This also makes the code more readable and suitable for future extensions.
  * </p>
  *
  * @author Lee Rhodes
  */
 public final class MurmurHash3 implements Serializable {
   private static final long serialVersionUID = 0L;

   private MurmurHash3() {}

   //--Hash of long[]----------------------------------------------------
   /**
    * Returns a long array of size 2, which is a 128-bit hash of the input.
    *
    * @param key The input long[] array. Must be non-null and non-empty.
    * @param seed A long valued seed.
    * @return the hash.
    */
   public static long[] hash(final long[] key, final long seed) {
     final HashState hashState = new HashState(seed, seed);
     final int longs = key.length; //in longs

     // Number of full 128-bit blocks of 2 longs (the body).
     // Possible exclusion of a remainder of 1 long.
     final int nblocks = longs >>> 1; //longs / 2

     // Process the 128-bit blocks (the body) into the hash
     for (int i = 0; i < nblocks; i++ ) {
       final long k1 = key[i << 1]; //0, 2, 4, ...
       final long k2 = key[(i << 1) + 1]; //1, 3, 5, ...
       hashState.blockMix128(k1, k2);
     }

     // Get the tail index, remainder length
     final int tail = nblocks << 1; // 2 longs / block
     final int rem = longs - tail; // remainder longs: 0,1

     // Get the tail
     final long k1 = (rem == 0) ? 0 : key[tail]; //k2 -> 0
     // Mix the tail into the hash and return
     return hashState.finalMix128(k1, 0, longs << 3); //convert to bytes
   }

   //--Hash of int[]----------------------------------------------------
   /**
    * Returns a long array of size 2, which is a 128-bit hash of the input.
    *
    * @param key The input int[] array. Must be non-null and non-empty.
    * @param seed A long valued seed.
    * @return the hash.
    */
   public static long[] hash(final int[] key, final long seed) {
     final HashState hashState = new HashState(seed, seed);
     final int ints = key.length; //in ints

     // Number of full 128-bit blocks of 4 ints.
     // Possible exclusion of a remainder of up to 3 ints.
     final int nblocks = ints >>> 2; //ints / 4

     // Process the 128-bit blocks (the body) into the hash
     for (int i = 0; i < nblocks; i++ ) { //4 ints per block
       final long k1 = getLong(key, i << 2, 2); //0, 4, 8, ...
       final long k2 = getLong(key, (i << 2) + 2, 2); //2, 6, 10, ...
       hashState.blockMix128(k1, k2);
     }

     // Get the tail index, remainder length
     final int tail = nblocks << 2; // 4 ints per block
     final int rem = ints - tail; // remainder ints: 0,1,2,3

     // Get the tail
     final long k1;
     final long k2;
     if (rem > 2) { //k1 -> whole; k2 -> partial
       k1 = getLong(key, tail, 2);
       k2 = getLong(key, tail + 2, rem - 2);
     }
     else { //k1 -> whole, partial or 0; k2 == 0
       k1 = (rem == 0) ? 0 : getLong(key, tail, rem);
       k2 = 0;
     }
     // Mix the tail into the hash and return
     return hashState.finalMix128(k1, k2, ints << 2); //convert to bytes
   }

   //--Hash of char[]----------------------------------------------------
   /**
    * Returns a long array of size 2, which is a 128-bit hash of the input.
    *
    * @param key The input char[] array. Must be non-null and non-empty.
    * @param seed A long valued seed.
    * @return the hash.
    */
   public static long[] hash(final char[] key, final long seed) {
     final HashState hashState = new HashState(seed, seed);
     final int chars = key.length; //in chars

     // Number of full 128-bit blocks of 8 chars.
     // Possible exclusion of a remainder of up to 7 chars.
     final int nblocks = chars >>> 3; //chars / 8

     // Process the 128-bit blocks (the body) into the hash
     for (int i = 0; i < nblocks; i++ ) { //8 chars per block
       final long k1 = getLong(key, i << 3, 4); //0, 8, 16, ...
       final long k2 = getLong(key, (i << 3) + 4, 4); //4, 12, 20, ...
       hashState.blockMix128(k1, k2);
     }

     // Get the tail index, remainder length
     final int tail = nblocks << 3; // 8 chars per block
     final int rem = chars - tail; // remainder chars: 0,1,2,3,4,5,6,7

     // Get the tail
     final long k1;
     final long k2;
     if (rem > 4) { //k1 -> whole; k2 -> partial
       k1 = getLong(key, tail, 4);
       k2 = getLong(key, tail + 4, rem - 4);
     }
     else { //k1 -> whole, partial or 0; k2 == 0
       k1 = (rem == 0) ? 0 : getLong(key, tail, rem);
       k2 = 0;
     }
     // Mix the tail into the hash and return
     return hashState.finalMix128(k1, k2, chars << 1); //convert to bytes
   }

   //--Hash of ByteBuffer------------------------------------------------
   /**
    * Returns a long array of size 2, which is a 128-bit hash of the input.
    *
    * @param buf The input byte buffer. Must be non-null and non-empty.
    * @param seed A long valued seed.
    * @return the hash.
    */
   public static long[] hash(final ByteBuffer buf, final long seed) {
     final HashState hashState = new HashState(seed, seed);
     final ByteBuffer littleEndianBuf;

     if (buf.order() == ByteOrder.LITTLE_ENDIAN) {
       littleEndianBuf = buf;
     } else {
       littleEndianBuf = buf.duplicate().order(ByteOrder.LITTLE_ENDIAN);
     }

     final int bytes = littleEndianBuf.remaining(); //in bytes
     final int offset = littleEndianBuf.position();

     // Number of full 128-bit blocks of 16 bytes.
     // Possible exclusion of a remainder of up to 15 bytes.
     final int nblocks = bytes >>> 4; //bytes / 16

     // Process the 128-bit blocks (the body) into the hash
     for (int i = 0; i < nblocks; i++ ) { //16 bytes per block
       final long k1 = getLong(littleEndianBuf, offset + (i << 4), 8); //0, 16, 32, ...
       final long k2 = getLong(littleEndianBuf, offset + (i << 4) + 8, 8); //8, 24, 40, ...
       hashState.blockMix128(k1, k2);
     }

     // Get the tail index, remainder length
     final int tail = nblocks << 4; //16 bytes per block
     final int rem = bytes - tail; // remainder bytes: 0,1,...,15

     // Get the tail
     final long k1;
     final long k2;
     if (rem > 8) { //k1 -> whole; k2 -> partial
       k1 = getLong(littleEndianBuf, offset + tail, 8);
       k2 = getLong(littleEndianBuf, offset + tail + 8, rem - 8);
     }
     else { //k1 -> whole, partial or 0; k2 == 0
       k1 = (rem == 0) ? 0 : getLong(littleEndianBuf, offset + tail, rem);
       k2 = 0;
     }
     // Mix the tail into the hash and return
     return hashState.finalMix128(k1, k2, bytes);
   }

   //--Hash of byte[]----------------------------------------------------
   /**
    * Returns a long array of size 2, which is a 128-bit hash of the input.
    *
    * @param key The input byte[] array. Must be non-null and non-empty.
    * @param seed A long valued seed.
    * @return the hash.
    */
   public static long[] hash(final byte[] key, final long seed) {
     final HashState hashState = new HashState(seed, seed);
     final int bytes = key.length; //in bytes

     // Number of full 128-bit blocks of 16 bytes.
     // Possible exclusion of a remainder of up to 15 bytes.
     final int nblocks = bytes >>> 4; //bytes / 16

     // Process the 128-bit blocks (the body) into the hash
     for (int i = 0; i < nblocks; i++ ) { //16 bytes per block
       final long k1 = getLong(key, i << 4, 8); //0, 16, 32, ...
       final long k2 = getLong(key, (i << 4) + 8, 8); //8, 24, 40, ...
       hashState.blockMix128(k1, k2);
     }

     // Get the tail index, remainder length
     final int tail = nblocks << 4; //16 bytes per block
     final int rem = bytes - tail; // remainder bytes: 0,1,...,15

     // Get the tail
     final long k1;
     final long k2;
     if (rem > 8) { //k1 -> whole; k2 -> partial
       k1 = getLong(key, tail, 8);
       k2 = getLong(key, tail + 8, rem - 8);
     }
     else { //k1 -> whole, partial or 0; k2 == 0
       k1 = (rem == 0) ? 0 : getLong(key, tail, rem);
       k2 = 0;
     }
     // Mix the tail into the hash and return
     return hashState.finalMix128(k1, k2, bytes);
   }

   //--HashState class---------------------------------------------------
   /**
    * Common processing of the 128-bit hash state independent of input type.
    */
   private static final class HashState {
     private static final long C1 = 0x87c37b91114253d5L;
     private static final long C2 = 0x4cf5ad432745937fL;
     private long h1;
     private long h2;

     HashState(final long h1, final long h2) {
       this.h1 = h1;
       this.h2 = h2;
     }

     /**
      * Block mix (128-bit block) of input key to internal hash state.
      *
      * @param k1 intermediate mix value
      * @param k2 intermediate mix value
      */
     void blockMix128(final long k1, final long k2) {
       h1 ^= mixK1(k1);
       h1 = Long.rotateLeft(h1, 27);
       h1 += h2;
       h1 = (h1 * 5) + 0x52dce729;

       h2 ^= mixK2(k2);
       h2 = Long.rotateLeft(h2, 31);
       h2 += h1;
       h2 = (h2 * 5) + 0x38495ab5;
     }

     long[] finalMix128(final long k1, final long k2, final long inputLengthBytes) {
       h1 ^= mixK1(k1);
       h2 ^= mixK2(k2);
       h1 ^= inputLengthBytes;
       h2 ^= inputLengthBytes;
       h1 += h2;
       h2 += h1;
       h1 = finalMix64(h1);
       h2 = finalMix64(h2);
       h1 += h2;
       h2 += h1;
       return new long[] { h1, h2 };
     }

     /**
      * Final self mix of h*.
      *
      * @param h input to final mix
      * @return mix
      */
     private static long finalMix64(long h) {
       h ^= h >>> 33;
       h *= 0xff51afd7ed558ccdL;
       h ^= h >>> 33;
       h *= 0xc4ceb9fe1a85ec53L;
       h ^= h >>> 33;
       return h;
     }

     /**
      * Self mix of k1
      *
      * @param k1 input argument
      * @return mix
      */
     private static long mixK1(long k1) {
       k1 *= C1;
       k1 = Long.rotateLeft(k1, 31);
       k1 *= C2;
       return k1;
     }

     /**
      * Self mix of k2
      *
      * @param k2 input argument
      * @return mix
      */
     private static long mixK2(long k2) {
       k2 *= C2;
       k2 = Long.rotateLeft(k2, 33);
       k2 *= C1;
       return k2;
     }
   }

   //--Helper methods----------------------------------------------------
   /**
    * Gets a long from the given byte buffer starting at the given position index and continuing for
    * remainder (rem) bytes. The buffer must be in little-endian order. The bytes are extracted in
    * little-endian order. The buffer endianness and limit are not checked.
    *
    * @param buf The given input byte buffer.
    * @param index Zero-based index from the start of the byte array.
    * @param rem Remainder bytes. An integer in the range [1,8].
    * @return long
    */
   private static long getLong(final ByteBuffer buf, final int index, final int rem) {
     long out = 0L;

     switch (rem) {
       case 8:
         out = buf.getLong(index);
         break;
       case 7:
         out ^= (buf.get(index + 6) & 0xFFL) << 48;
       case 6:
         out ^= (buf.get(index + 5) & 0xFFL) << 40;
       case 5:
         out ^= (buf.get(index + 4) & 0xFFL) << 32;
       case 4:
         out ^= (buf.get(index + 3) & 0xFFL) << 24;
       case 3:
         out ^= (buf.get(index + 2) & 0xFFL) << 16;
       case 2:
         out ^= (buf.get(index + 1) & 0xFFL) << 8;
       case 1:
         out ^= buf.get(index) & 0xFFL;
     }

     return out;
   }

   //--Helper methods----------------------------------------------------
   /**
    * Gets a long from the given byte array starting at the given byte array index and continuing for
    * remainder (rem) bytes. The bytes are extracted in little-endian order. There is no limit
    * checking.
    *
    * @param bArr The given input byte array.
    * @param index Zero-based index from the start of the byte array.
    * @param rem Remainder bytes. An integer in the range [1,8].
    * @return long
    */
   private static long getLong(final byte[] bArr, final int index, final int rem) {
     long out = 0L;
     for (int i = rem; i-- > 0;) { //i= 7,6,5,4,3,2,1,0
       final byte b = bArr[index + i];
       out ^= (b & 0xFFL) << (i * 8); //equivalent to |=
     }
     return out;
   }

   /**
    * Gets a long from the given char array starting at the given char array index and continuing for
    * remainder (rem) chars. The chars are extracted in little-endian order. There is no limit
    * checking.
    *
    * @param charArr The given input char array.
    * @param index Zero-based index from the start of the char array.
    * @param rem Remainder chars. An integer in the range [1,4].
    * @return long
    */
   private static long getLong(final char[] charArr, final int index, final int rem) {
     long out = 0L;
     for (int i = rem; i-- > 0;) { //i= 3,2,1,0
       final char c = charArr[index + i];
       out ^= (c & 0xFFFFL) << (i * 16); //equivalent to |=
     }
     return out;
   }

   /**
    * Gets a long from the given int array starting at the given int array index and continuing for
    * remainder (rem) integers. The integers are extracted in little-endian order. There is no limit
    * checking.
    *
    * @param intArr The given input int array.
    * @param index Zero-based index from the start of the int array.
    * @param rem Remainder integers. An integer in the range [1,2].
    * @return long
    */
   private static long getLong(final int[] intArr, final int index, final int rem) {
     long out = 0L;
     for (int i = rem; i-- > 0;) { //i= 1,0
       final int v = intArr[index + i];
       out ^= (v & 0xFFFFFFFFL) << (i * 32); //equivalent to |=
     }
     return out;
   }

 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing,
	* software distributed under the License is distributed on an
	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	* KIND, either express or implied. See the License for the
	* specific language governing permissions and limitations
	* under the License.
	*/

	package org.apache.datasketches.hash;

	import java.io.Serializable;
	import java.nio.ByteBuffer;
	import java.nio.ByteOrder;


	/**
	* <p>
	* The MurmurHash3 is a fast, non-cryptographic, 128-bit hash function that has
	* excellent avalanche and 2-way bit independence properties.
	* </p>
	*
	* <p>
	* Austin Appleby's C++
	* <a href="https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp">
	* MurmurHash3_x64_128(...), final revision 150</a>,
	* which is in the Public Domain, was the inspiration for this implementation in Java.
	* </p>
	*
	* <p>
	* This java implementation pays close attention to the C++ algorithms in order to
	* maintain bit-wise compatibility, but the design is quite different. This implementation has also
	* been extended to include processing of arrays of longs, char or ints, which was not part of the
	* original C++ implementation. This implementation produces the same exact output hash bits as
	* the above C++ method given the same input.</p>
	*
	* <p>In addition, with this implementation, the hash of byte[], char[], int[], or long[] will
	* produce the same hash result if, and only if, all the arrays have the same exact length in
	* bytes, and if the contents of the values in the arrays have the same byte endianness and
	* overall order. There is a unit test for this class that demonstrates this.</p>
	*
	* <p>
	* The structure of this implementation also reflects a separation of code that is dependent on the
	* input structure (in this case byte[], int[] or long[]) from code that is independent of the input
	* structure. This also makes the code more readable and suitable for future extensions.
	* </p>
	*
	* @author Lee Rhodes
	*/
	public final class MurmurHash3 implements Serializable {
	private static final long serialVersionUID = 0L;

	private MurmurHash3() {}

	//--Hash of long[]----------------------------------------------------
	/**
	* Returns a long array of size 2, which is a 128-bit hash of the input.
	*
	* @param key The input long[] array. Must be non-null and non-empty.
	* @param seed A long valued seed.
	* @return the hash.
	*/
	public static long[] hash(final long[] key, final long seed) {
	final HashState hashState = new HashState(seed, seed);
	final int longs = key.length; //in longs

	// Number of full 128-bit blocks of 2 longs (the body).
	// Possible exclusion of a remainder of 1 long.
	final int nblocks = longs >>> 1; //longs / 2

	// Process the 128-bit blocks (the body) into the hash
	for (int i = 0; i < nblocks; i++ ) {
	final long k1 = key[i << 1]; //0, 2, 4, ...
	final long k2 = key[(i << 1) + 1]; //1, 3, 5, ...
	hashState.blockMix128(k1, k2);
	}

	// Get the tail index, remainder length
	final int tail = nblocks << 1; // 2 longs / block
	final int rem = longs - tail; // remainder longs: 0,1

	// Get the tail
	final long k1 = (rem == 0) ? 0 : key[tail]; //k2 -> 0
	// Mix the tail into the hash and return
	return hashState.finalMix128(k1, 0, longs << 3); //convert to bytes
	}

	//--Hash of int[]----------------------------------------------------
	/**
	* Returns a long array of size 2, which is a 128-bit hash of the input.
	*
	* @param key The input int[] array. Must be non-null and non-empty.
	* @param seed A long valued seed.
	* @return the hash.
	*/
	public static long[] hash(final int[] key, final long seed) {
	final HashState hashState = new HashState(seed, seed);
	final int ints = key.length; //in ints

	// Number of full 128-bit blocks of 4 ints.
	// Possible exclusion of a remainder of up to 3 ints.
	final int nblocks = ints >>> 2; //ints / 4

	// Process the 128-bit blocks (the body) into the hash
	for (int i = 0; i < nblocks; i++ ) { //4 ints per block
	final long k1 = getLong(key, i << 2, 2); //0, 4, 8, ...
	final long k2 = getLong(key, (i << 2) + 2, 2); //2, 6, 10, ...
	hashState.blockMix128(k1, k2);
	}

	// Get the tail index, remainder length
	final int tail = nblocks << 2; // 4 ints per block
	final int rem = ints - tail; // remainder ints: 0,1,2,3

	// Get the tail
	final long k1;
	final long k2;
	if (rem > 2) { //k1 -> whole; k2 -> partial
	k1 = getLong(key, tail, 2);
	k2 = getLong(key, tail + 2, rem - 2);
	}
	else { //k1 -> whole, partial or 0; k2 == 0
	k1 = (rem == 0) ? 0 : getLong(key, tail, rem);
	k2 = 0;
	}
	// Mix the tail into the hash and return
	return hashState.finalMix128(k1, k2, ints << 2); //convert to bytes
	}

	//--Hash of char[]----------------------------------------------------
	/**
	* Returns a long array of size 2, which is a 128-bit hash of the input.
	*
	* @param key The input char[] array. Must be non-null and non-empty.
	* @param seed A long valued seed.
	* @return the hash.
	*/
	public static long[] hash(final char[] key, final long seed) {
	final HashState hashState = new HashState(seed, seed);
	final int chars = key.length; //in chars

	// Number of full 128-bit blocks of 8 chars.
	// Possible exclusion of a remainder of up to 7 chars.
	final int nblocks = chars >>> 3; //chars / 8

	// Process the 128-bit blocks (the body) into the hash
	for (int i = 0; i < nblocks; i++ ) { //8 chars per block
	final long k1 = getLong(key, i << 3, 4); //0, 8, 16, ...
	final long k2 = getLong(key, (i << 3) + 4, 4); //4, 12, 20, ...
	hashState.blockMix128(k1, k2);
	}

	// Get the tail index, remainder length
	final int tail = nblocks << 3; // 8 chars per block
	final int rem = chars - tail; // remainder chars: 0,1,2,3,4,5,6,7

	// Get the tail
	final long k1;
	final long k2;
	if (rem > 4) { //k1 -> whole; k2 -> partial
	k1 = getLong(key, tail, 4);
	k2 = getLong(key, tail + 4, rem - 4);
	}
	else { //k1 -> whole, partial or 0; k2 == 0
	k1 = (rem == 0) ? 0 : getLong(key, tail, rem);
	k2 = 0;
	}
	// Mix the tail into the hash and return
	return hashState.finalMix128(k1, k2, chars << 1); //convert to bytes
	}

	//--Hash of ByteBuffer------------------------------------------------
	/**
	* Returns a long array of size 2, which is a 128-bit hash of the input.
	*
	* @param buf The input byte buffer. Must be non-null and non-empty.
	* @param seed A long valued seed.
	* @return the hash.
	*/
	public static long[] hash(final ByteBuffer buf, final long seed) {
	final HashState hashState = new HashState(seed, seed);
	final ByteBuffer littleEndianBuf;

	if (buf.order() == ByteOrder.LITTLE_ENDIAN) {
	littleEndianBuf = buf;
	} else {
	littleEndianBuf = buf.duplicate().order(ByteOrder.LITTLE_ENDIAN);
	}

	final int bytes = littleEndianBuf.remaining(); //in bytes
	final int offset = littleEndianBuf.position();

	// Number of full 128-bit blocks of 16 bytes.
	// Possible exclusion of a remainder of up to 15 bytes.
	final int nblocks = bytes >>> 4; //bytes / 16

	// Process the 128-bit blocks (the body) into the hash
	for (int i = 0; i < nblocks; i++ ) { //16 bytes per block
	final long k1 = getLong(littleEndianBuf, offset + (i << 4), 8); //0, 16, 32, ...
	final long k2 = getLong(littleEndianBuf, offset + (i << 4) + 8, 8); //8, 24, 40, ...
	hashState.blockMix128(k1, k2);
	}

	// Get the tail index, remainder length
	final int tail = nblocks << 4; //16 bytes per block
	final int rem = bytes - tail; // remainder bytes: 0,1,...,15

	// Get the tail
	final long k1;
	final long k2;
	if (rem > 8) { //k1 -> whole; k2 -> partial
	k1 = getLong(littleEndianBuf, offset + tail, 8);
	k2 = getLong(littleEndianBuf, offset + tail + 8, rem - 8);
	}
	else { //k1 -> whole, partial or 0; k2 == 0
	k1 = (rem == 0) ? 0 : getLong(littleEndianBuf, offset + tail, rem);
	k2 = 0;
	}
	// Mix the tail into the hash and return
	return hashState.finalMix128(k1, k2, bytes);
	}

	//--Hash of byte[]----------------------------------------------------
	/**
	* Returns a long array of size 2, which is a 128-bit hash of the input.
	*
	* @param key The input byte[] array. Must be non-null and non-empty.
	* @param seed A long valued seed.
	* @return the hash.
	*/
	public static long[] hash(final byte[] key, final long seed) {
	final HashState hashState = new HashState(seed, seed);
	final int bytes = key.length; //in bytes

	// Number of full 128-bit blocks of 16 bytes.
	// Possible exclusion of a remainder of up to 15 bytes.
	final int nblocks = bytes >>> 4; //bytes / 16

	// Process the 128-bit blocks (the body) into the hash
	for (int i = 0; i < nblocks; i++ ) { //16 bytes per block
	final long k1 = getLong(key, i << 4, 8); //0, 16, 32, ...
	final long k2 = getLong(key, (i << 4) + 8, 8); //8, 24, 40, ...
	hashState.blockMix128(k1, k2);
	}

	// Get the tail index, remainder length
	final int tail = nblocks << 4; //16 bytes per block
	final int rem = bytes - tail; // remainder bytes: 0,1,...,15

	// Get the tail
	final long k1;
	final long k2;
	if (rem > 8) { //k1 -> whole; k2 -> partial
	k1 = getLong(key, tail, 8);
	k2 = getLong(key, tail + 8, rem - 8);
	}
	else { //k1 -> whole, partial or 0; k2 == 0
	k1 = (rem == 0) ? 0 : getLong(key, tail, rem);
	k2 = 0;
	}
	// Mix the tail into the hash and return
	return hashState.finalMix128(k1, k2, bytes);
	}

	//--HashState class---------------------------------------------------
	/**
	* Common processing of the 128-bit hash state independent of input type.
	*/
	private static final class HashState {
	private static final long C1 = 0x87c37b91114253d5L;
	private static final long C2 = 0x4cf5ad432745937fL;
	private long h1;
	private long h2;

	HashState(final long h1, final long h2) {
	this.h1 = h1;
	this.h2 = h2;
	}

	/**
	* Block mix (128-bit block) of input key to internal hash state.
	*
	* @param k1 intermediate mix value
	* @param k2 intermediate mix value
	*/
	void blockMix128(final long k1, final long k2) {
	h1 ^= mixK1(k1);
	h1 = Long.rotateLeft(h1, 27);
	h1 += h2;
	h1 = (h1 * 5) + 0x52dce729;

	h2 ^= mixK2(k2);
	h2 = Long.rotateLeft(h2, 31);
	h2 += h1;
	h2 = (h2 * 5) + 0x38495ab5;
	}

	long[] finalMix128(final long k1, final long k2, final long inputLengthBytes) {
	h1 ^= mixK1(k1);
	h2 ^= mixK2(k2);
	h1 ^= inputLengthBytes;
	h2 ^= inputLengthBytes;
	h1 += h2;
	h2 += h1;
	h1 = finalMix64(h1);
	h2 = finalMix64(h2);
	h1 += h2;
	h2 += h1;
	return new long[] { h1, h2 };
	}

	/**
	* Final self mix of h*.
	*
	* @param h input to final mix
	* @return mix
	*/
	private static long finalMix64(long h) {
	h ^= h >>> 33;
	h *= 0xff51afd7ed558ccdL;
	h ^= h >>> 33;
	h *= 0xc4ceb9fe1a85ec53L;
	h ^= h >>> 33;
	return h;
	}

	/**
	* Self mix of k1
	*
	* @param k1 input argument
	* @return mix
	*/
	private static long mixK1(long k1) {
	k1 *= C1;
	k1 = Long.rotateLeft(k1, 31);
	k1 *= C2;
	return k1;
	}

	/**
	* Self mix of k2
	*
	* @param k2 input argument
	* @return mix
	*/
	private static long mixK2(long k2) {
	k2 *= C2;
	k2 = Long.rotateLeft(k2, 33);
	k2 *= C1;
	return k2;
	}
	}

	//--Helper methods----------------------------------------------------
	/**
	* Gets a long from the given byte buffer starting at the given position index and continuing for
	* remainder (rem) bytes. The buffer must be in little-endian order. The bytes are extracted in
	* little-endian order. The buffer endianness and limit are not checked.
	*
	* @param buf The given input byte buffer.
	* @param index Zero-based index from the start of the byte array.
	* @param rem Remainder bytes. An integer in the range [1,8].
	* @return long
	*/
	private static long getLong(final ByteBuffer buf, final int index, final int rem) {
	long out = 0L;

	switch (rem) {
	case 8:
	out = buf.getLong(index);
	break;
	case 7:
	out ^= (buf.get(index + 6) & 0xFFL) << 48;
	case 6:
	out ^= (buf.get(index + 5) & 0xFFL) << 40;
	case 5:
	out ^= (buf.get(index + 4) & 0xFFL) << 32;
	case 4:
	out ^= (buf.get(index + 3) & 0xFFL) << 24;
	case 3:
	out ^= (buf.get(index + 2) & 0xFFL) << 16;
	case 2:
	out ^= (buf.get(index + 1) & 0xFFL) << 8;
	case 1:
	out ^= buf.get(index) & 0xFFL;
	}

	return out;
	}

	//--Helper methods----------------------------------------------------
	/**
	* Gets a long from the given byte array starting at the given byte array index and continuing for
	* remainder (rem) bytes. The bytes are extracted in little-endian order. There is no limit
	* checking.
	*
	* @param bArr The given input byte array.
	* @param index Zero-based index from the start of the byte array.
	* @param rem Remainder bytes. An integer in the range [1,8].
	* @return long
	*/
	private static long getLong(final byte[] bArr, final int index, final int rem) {
	long out = 0L;
	for (int i = rem; i-- > 0;) { //i= 7,6,5,4,3,2,1,0
	final byte b = bArr[index + i];
	out ^= (b & 0xFFL) << (i * 8); //equivalent to \|=
	}
	return out;
	}

	/**
	* Gets a long from the given char array starting at the given char array index and continuing for
	* remainder (rem) chars. The chars are extracted in little-endian order. There is no limit
	* checking.
	*
	* @param charArr The given input char array.
	* @param index Zero-based index from the start of the char array.
	* @param rem Remainder chars. An integer in the range [1,4].
	* @return long
	*/
	private static long getLong(final char[] charArr, final int index, final int rem) {
	long out = 0L;
	for (int i = rem; i-- > 0;) { //i= 3,2,1,0
	final char c = charArr[index + i];
	out ^= (c & 0xFFFFL) << (i * 16); //equivalent to \|=
	}
	return out;
	}

	/**
	* Gets a long from the given int array starting at the given int array index and continuing for
	* remainder (rem) integers. The integers are extracted in little-endian order. There is no limit
	* checking.
	*
	* @param intArr The given input int array.
	* @param index Zero-based index from the start of the int array.
	* @param rem Remainder integers. An integer in the range [1,2].
	* @return long
	*/
	private static long getLong(final int[] intArr, final int index, final int rem) {
	long out = 0L;
	for (int i = rem; i-- > 0;) { //i= 1,0
	final int v = intArr[index + i];
	out ^= (v & 0xFFFFFFFFL) << (i * 32); //equivalent to \|=
	}
	return out;
	}

	}