murmurhash3 java_MurMurHash3

packageutil.hash;/*** The MurmurHash3 algorithm was created by Austin Appleby and placed in the public domain.

* This java port was authored by Yonik Seeley and also placed into the public domain.

* The author hereby disclaims copyright to this source code.

*

* This produces exactly the same hash values as the final C++

* version of MurmurHash3 and is thus suitable for producing the same hash values across

* platforms.

*

* The 32 bit x86 version of this hash should be the fastest variant for relatively short keys like ids.

* murmurhash3_x64_128 is a good choice for longer strings or if you need more than 32 bits of hash.

*

* Note – The x86 and x64 versions do _not_ produce the same results, as the

* algorithms are optimized for their respective platforms.

*

* Seehttp://github.com/yonik/java_utilfor future updates to this file.*/

public final classMurmurHash3 {/**128 bits of state*/

public static final classLongPair {public longval1;public longval2;

}public static final int fmix32(inth) {

h^= h >>> 16;

h*= 0x85ebca6b;

h^= h >>> 13;

h*= 0xc2b2ae35;

h^= h >>> 16;returnh;

}public static final long fmix64(longk) {

k^= k >>> 33;

k*= 0xff51afd7ed558ccdL;

k^= k >>> 33;

k*= 0xc4ceb9fe1a85ec53L;

k^= k >>> 33;returnk;

}/**Gets a long from a byte buffer in little endian byte order.*/

public static final long getLongLittleEndian(byte[] buf, intoffset) {return ((long)buf[offset+7] << 56) //no mask needed

| ((buf[offset+6] & 0xffL) << 48)| ((buf[offset+5] & 0xffL) << 40)| ((buf[offset+4] & 0xffL) << 32)| ((buf[offset+3] & 0xffL) << 24)| ((buf[offset+2] & 0xffL) << 16)| ((buf[offset+1] & 0xffL) << 8)| ((buf[offset ] & 0xffL)); //no shift needed

}/**Returns the MurmurHash3_x86_32 hash.*/

public static int murmurhash3_x86_32(byte[] data, int offset, int len, intseed) {final int c1 = 0xcc9e2d51;final int c2 = 0x1b873593;int h1 =seed;int roundedEnd = offset + (len & 0xfffffffc); //round down to 4 byte block

for (int i=offset; i

int k1 = (data[i] & 0xff) | ((data[i+1] & 0xff) << 8) | ((data[i+2] & 0xff) << 16) | (data[i+3] << 24);

k1*=c1;

k1= (k1 << 15) | (k1 >>> 17); //ROTL32(k1,15);

k1 *=c2;

h1^=k1;

h1= (h1 << 13) | (h1 >>> 19); //ROTL32(h1,13);

h1 = h1*5+0xe6546b64;

}//tail

int k1 = 0;switch(len & 0x03) {case 3:

k1= (data[roundedEnd + 2] & 0xff) << 16;//fallthrough

case 2:

k1|= (data[roundedEnd + 1] & 0xff) << 8;//fallthrough

case 1:

k1|= (data[roundedEnd] & 0xff);

k1*=c1;

k1= (k1 << 15) | (k1 >>> 17); //ROTL32(k1,15);

k1 *=c2;

h1^=k1;

}//finalization

h1 ^=len;//fmix(h1);

h1 ^= h1 >>> 16;

h1*= 0x85ebca6b;

h1^= h1 >>> 13;

h1*= 0xc2b2ae35;

h1^= h1 >>> 16;returnh1;

}/**Returns the MurmurHash3_x86_32 hash of the UTF-8 bytes of the String without actually encoding

* the string to a temporary buffer. This is more than 2x faster than hashing the result

* of String.getBytes().*/

public static int murmurhash3_x86_32(CharSequence data, int offset, int len, intseed) {final int c1 = 0xcc9e2d51;final int c2 = 0x1b873593;int h1 =seed;int pos =offset;int end = offset +len;int k1 = 0;int k2 = 0;int shift = 0;int bits = 0;int nBytes = 0; //length in UTF8 bytes

while (pos

k2=code;

bits= 8;/***

// optimized ascii implementation (currently slower!!! code size?)

if (shift == 24) {

k1 = k1 | (code << 24);

k1 *= c1;

k1 = (k1 << 15) | (k1 >>> 17); // ROTL32(k1,15);

k1 *= c2;

h1 ^= k1;

h1 = (h1 << 13) | (h1 >>> 19); // ROTL32(h1,13);

h1 = h1*5+0xe6546b64;

shift = 0;

nBytes += 4;

k1 = 0;

} else {

k1 |= code << shift;

shift += 8;

}

continue;

***/}else if (code < 0x800) {

k2= (0xC0 | (code >> 6))| ((0x80 | (code & 0x3F)) << 8);

bits= 16;

}else if (code < 0xD800 || code > 0xDFFF || pos>=end) {//we check for pos>=end to encode an unpaired surrogate as 3 bytes.

k2 = (0xE0 | (code >> 12))| ((0x80 | ((code >> 6) & 0x3F)) << 8)| ((0x80 | (code & 0x3F)) << 16);

bits= 24;

}else{//surrogate pair//int utf32 = pos < end ? (int) data.charAt(pos++) : 0;

int utf32 = (int) data.charAt(pos++);

utf32= ((code – 0xD7C0) << 10) + (utf32 & 0x3FF);

k2= (0xff & (0xF0 | (utf32 >> 18)))| ((0x80 | ((utf32 >> 12) & 0x3F))) << 8

| ((0x80 | ((utf32 >> 6) & 0x3F))) << 16

| (0x80 | (utf32 & 0x3F)) << 24;

bits= 32;

}

k1|= k2 <

shift+=bits;if (shift >= 32) {//mix after we have a complete word

k1*=c1;

k1= (k1 << 15) | (k1 >>> 17); //ROTL32(k1,15);

k1 *=c2;

h1^=k1;

h1= (h1 << 13) | (h1 >>> 19); //ROTL32(h1,13);

h1 = h1*5+0xe6546b64;

shift-= 32;//unfortunately, java won‘t let you shift 32 bits off, so we need to check for 0

if (shift != 0) {

k1= k2 >>> (bits-shift); //bits used == bits – newshift

} else{

k1= 0;

}

nBytes+= 4;

}

}//inner//handle tail

if (shift > 0) {

nBytes+= shift >> 3;

k1*=c1;

k1= (k1 << 15) | (k1 >>> 17); //ROTL32(k1,15);

k1 *=c2;

h1^=k1;

}//finalization

h1 ^=nBytes;//fmix(h1);

h1 ^= h1 >>> 16;

h1*= 0x85ebca6b;

h1^= h1 >>> 13;

h1*= 0xc2b2ae35;

h1^= h1 >>> 16;returnh1;

}/**Returns the MurmurHash3_x64_128 hash, placing the result in “out”.*/

public static void murmurhash3_x64_128(byte[] key, int offset, int len, intseed, LongPair out) {//The original algorithm does have a 32 bit unsigned seed.//We have to mask to match the behavior of the unsigned types and prevent sign extension.

long h1 = seed & 0x00000000FFFFFFFFL;long h2 = seed & 0x00000000FFFFFFFFL;final long c1 = 0x87c37b91114253d5L;final long c2 = 0x4cf5ad432745937fL;int roundedEnd = offset + (len & 0xFFFFFFF0); //round down to 16 byte block

for (int i=offset; i

k1*= c1; k1 = Long.rotateLeft(k1,31); k1 *= c2; h1 ^=k1;

h1= Long.rotateLeft(h1,27); h1 += h2; h1 = h1*5+0x52dce729;

k2*= c2; k2 = Long.rotateLeft(k2,33); k2 *= c1; h2 ^=k2;

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

}long k1 = 0;long k2 = 0;switch (len & 15) {case 15: k2 = (key[roundedEnd+14] & 0xffL) << 48;case 14: k2 |= (key[roundedEnd+13] & 0xffL) << 40;case 13: k2 |= (key[roundedEnd+12] & 0xffL) << 32;case 12: k2 |= (key[roundedEnd+11] & 0xffL) << 24;case 11: k2 |= (key[roundedEnd+10] & 0xffL) << 16;case 10: k2 |= (key[roundedEnd+ 9] & 0xffL) << 8;case 9: k2 |= (key[roundedEnd+ 8] & 0xffL);

k2*= c2; k2 = Long.rotateLeft(k2, 33); k2 *= c1; h2 ^=k2;case 8: k1 = ((long)key[roundedEnd+7]) << 56;case 7: k1 |= (key[roundedEnd+6] & 0xffL) << 48;case 6: k1 |= (key[roundedEnd+5] & 0xffL) << 40;case 5: k1 |= (key[roundedEnd+4] & 0xffL) << 32;case 4: k1 |= (key[roundedEnd+3] & 0xffL) << 24;case 3: k1 |= (key[roundedEnd+2] & 0xffL) << 16;case 2: k1 |= (key[roundedEnd+1] & 0xffL) << 8;case 1: k1 |= (key[roundedEnd ] & 0xffL);

k1*= c1; k1 = Long.rotateLeft(k1,31); k1 *= c2; h1 ^=k1;

}//———-//finalization

h1^= len; h2 ^=len;

h1+=h2;

h2+=h1;

h1=fmix64(h1);

h2=fmix64(h2);

h1+=h2;

h2+=h1;

out.val1=h1;

out.val2=h2;

}

}