11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the License 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or implied. See the License for the specific language governing permissions and limitations under 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 157dd252788645e940eada959bdde927426e2531c9Paul Duffin/* 167dd252788645e940eada959bdde927426e2531c9Paul Duffin * MurmurHash3 was written by Austin Appleby, and is placed in the public 177dd252788645e940eada959bdde927426e2531c9Paul Duffin * domain. The author hereby disclaims copyright to this source code. 187dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 197dd252788645e940eada959bdde927426e2531c9Paul Duffin 207dd252788645e940eada959bdde927426e2531c9Paul Duffin/* 217dd252788645e940eada959bdde927426e2531c9Paul Duffin * Source: 227dd252788645e940eada959bdde927426e2531c9Paul Duffin * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp 237dd252788645e940eada959bdde927426e2531c9Paul Duffin * (Modified to adapt to Guava coding conventions and to use the HashFunction interface) 247dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 257dd252788645e940eada959bdde927426e2531c9Paul Duffin 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.hash; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.primitives.UnsignedBytes.toInt; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.Serializable; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.nio.ByteBuffer; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.nio.ByteOrder; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 340888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport javax.annotation.Nullable; 350888a09821a98ac0680fad765217302858e70fa4Paul Duffin 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * MurmurHash3_x64_128 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 407dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Austin Appleby 417dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Dimitris Andreou 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertfinal class Murmur3_128HashFunction extends AbstractStreamingHashFunction implements Serializable { 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(user): when the shortcuts are implemented, update BloomFilterStrategies 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final int seed; 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Murmur3_128HashFunction(int seed) { 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.seed = seed; 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 510888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int bits() { 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 128; 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 550888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Hasher newHasher() { 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Murmur3_128Hasher(seed); 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 597dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 607dd252788645e940eada959bdde927426e2531c9Paul Duffin public String toString() { 617dd252788645e940eada959bdde927426e2531c9Paul Duffin return "Hashing.murmur3_128(" + seed + ")"; 627dd252788645e940eada959bdde927426e2531c9Paul Duffin } 637dd252788645e940eada959bdde927426e2531c9Paul Duffin 640888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin public boolean equals(@Nullable Object object) { 660888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (object instanceof Murmur3_128HashFunction) { 670888a09821a98ac0680fad765217302858e70fa4Paul Duffin Murmur3_128HashFunction other = (Murmur3_128HashFunction) object; 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin return seed == other.seed; 690888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 700888a09821a98ac0680fad765217302858e70fa4Paul Duffin return false; 710888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin 730888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 740888a09821a98ac0680fad765217302858e70fa4Paul Duffin public int hashCode() { 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin return getClass().hashCode() ^ seed; 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final class Murmur3_128Hasher extends AbstractStreamingHasher { 797dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final int CHUNK_SIZE = 16; 807dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final long C1 = 0x87c37b91114253d5L; 817dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final long C2 = 0x4cf5ad432745937fL; 827dd252788645e940eada959bdde927426e2531c9Paul Duffin private long h1; 837dd252788645e940eada959bdde927426e2531c9Paul Duffin private long h2; 847dd252788645e940eada959bdde927426e2531c9Paul Duffin private int length; 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Murmur3_128Hasher(int seed) { 877dd252788645e940eada959bdde927426e2531c9Paul Duffin super(CHUNK_SIZE); 887dd252788645e940eada959bdde927426e2531c9Paul Duffin this.h1 = seed; 897dd252788645e940eada959bdde927426e2531c9Paul Duffin this.h2 = seed; 907dd252788645e940eada959bdde927426e2531c9Paul Duffin this.length = 0; 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected void process(ByteBuffer bb) { 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long k1 = bb.getLong(); 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long k2 = bb.getLong(); 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert bmix64(k1, k2); 977dd252788645e940eada959bdde927426e2531c9Paul Duffin length += CHUNK_SIZE; 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private void bmix64(long k1, long k2) { 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin h1 ^= mixK1(k1); 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h1 = Long.rotateLeft(h1, 27); 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h1 += h2; 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h1 = h1 * 5 + 0x52dce729; 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin h2 ^= mixK2(k2); 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h2 = Long.rotateLeft(h2, 31); 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h2 += h1; 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h2 = h2 * 5 + 0x38495ab5; 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected void processRemaining(ByteBuffer bb) { 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long k1 = 0; 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long k2 = 0; 1177dd252788645e940eada959bdde927426e2531c9Paul Duffin length += bb.remaining(); 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (bb.remaining()) { 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 15: 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k2 ^= (long) toInt(bb.get(14)) << 48; // fall through 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 14: 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k2 ^= (long) toInt(bb.get(13)) << 40; // fall through 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 13: 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k2 ^= (long) toInt(bb.get(12)) << 32; // fall through 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 12: 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k2 ^= (long) toInt(bb.get(11)) << 24; // fall through 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 11: 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k2 ^= (long) toInt(bb.get(10)) << 16; // fall through 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 10: 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k2 ^= (long) toInt(bb.get(9)) << 8; // fall through 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 9: 1320888a09821a98ac0680fad765217302858e70fa4Paul Duffin k2 ^= (long) toInt(bb.get(8)); // fall through 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 8: 1347dd252788645e940eada959bdde927426e2531c9Paul Duffin k1 ^= bb.getLong(); 1357dd252788645e940eada959bdde927426e2531c9Paul Duffin break; 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 7: 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k1 ^= (long) toInt(bb.get(6)) << 48; // fall through 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 6: 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k1 ^= (long) toInt(bb.get(5)) << 40; // fall through 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 5: 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k1 ^= (long) toInt(bb.get(4)) << 32; // fall through 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 4: 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k1 ^= (long) toInt(bb.get(3)) << 24; // fall through 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 3: 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k1 ^= (long) toInt(bb.get(2)) << 16; // fall through 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 2: 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k1 ^= (long) toInt(bb.get(1)) << 8; // fall through 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert case 1: 1490888a09821a98ac0680fad765217302858e70fa4Paul Duffin k1 ^= (long) toInt(bb.get(0)); 1507dd252788645e940eada959bdde927426e2531c9Paul Duffin break; 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert default: 1527dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new AssertionError("Should never get here."); 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1547dd252788645e940eada959bdde927426e2531c9Paul Duffin h1 ^= mixK1(k1); 1557dd252788645e940eada959bdde927426e2531c9Paul Duffin h2 ^= mixK2(k2); 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public HashCode makeHash() { 1597dd252788645e940eada959bdde927426e2531c9Paul Duffin h1 ^= length; 1607dd252788645e940eada959bdde927426e2531c9Paul Duffin h2 ^= length; 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h1 += h2; 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h2 += h1; 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h1 = fmix64(h1); 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h2 = fmix64(h2); 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h1 += h2; 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert h2 += h1; 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1710888a09821a98ac0680fad765217302858e70fa4Paul Duffin return HashCode.fromBytesNoCopy(ByteBuffer 1720888a09821a98ac0680fad765217302858e70fa4Paul Duffin .wrap(new byte[CHUNK_SIZE]) 1730888a09821a98ac0680fad765217302858e70fa4Paul Duffin .order(ByteOrder.LITTLE_ENDIAN) 1740888a09821a98ac0680fad765217302858e70fa4Paul Duffin .putLong(h1) 1750888a09821a98ac0680fad765217302858e70fa4Paul Duffin .putLong(h2) 1760888a09821a98ac0680fad765217302858e70fa4Paul Duffin .array()); 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1797dd252788645e940eada959bdde927426e2531c9Paul Duffin private static long fmix64(long k) { 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k ^= k >>> 33; 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k *= 0xff51afd7ed558ccdL; 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k ^= k >>> 33; 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k *= 0xc4ceb9fe1a85ec53L; 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert k ^= k >>> 33; 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return k; 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1877dd252788645e940eada959bdde927426e2531c9Paul Duffin 1887dd252788645e940eada959bdde927426e2531c9Paul Duffin private static long mixK1(long k1) { 1897dd252788645e940eada959bdde927426e2531c9Paul Duffin k1 *= C1; 1907dd252788645e940eada959bdde927426e2531c9Paul Duffin k1 = Long.rotateLeft(k1, 31); 1917dd252788645e940eada959bdde927426e2531c9Paul Duffin k1 *= C2; 1927dd252788645e940eada959bdde927426e2531c9Paul Duffin return k1; 1937dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1947dd252788645e940eada959bdde927426e2531c9Paul Duffin 1957dd252788645e940eada959bdde927426e2531c9Paul Duffin private static long mixK2(long k2) { 1967dd252788645e940eada959bdde927426e2531c9Paul Duffin k2 *= C2; 1977dd252788645e940eada959bdde927426e2531c9Paul Duffin k2 = Long.rotateLeft(k2, 33); 1987dd252788645e940eada959bdde927426e2531c9Paul Duffin k2 *= C1; 1997dd252788645e940eada959bdde927426e2531c9Paul Duffin return k2; 2007dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 0L; 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 205