1/* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15package com.google.common.hash; 16 17import static com.google.common.primitives.UnsignedBytes.toInt; 18 19import java.io.Serializable; 20import java.nio.ByteBuffer; 21import java.nio.ByteOrder; 22 23/** 24 * See http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp 25 * MurmurHash3_x64_128 26 * 27 * @author aappleby@google.com (Austin Appleby) 28 * @author andreou@google.com (Dimitris Andreou) 29 */ 30final class Murmur3_128HashFunction extends AbstractStreamingHashFunction implements Serializable { 31 // TODO(user): when the shortcuts are implemented, update BloomFilterStrategies 32 private final int seed; 33 34 Murmur3_128HashFunction(int seed) { 35 this.seed = seed; 36 } 37 38 @Override public int bits() { 39 return 128; 40 } 41 42 @Override public Hasher newHasher() { 43 return new Murmur3_128Hasher(seed); 44 } 45 46 private static final class Murmur3_128Hasher extends AbstractStreamingHasher { 47 long h1; 48 long h2; 49 long c1 = 0x87c37b91114253d5L; 50 long c2 = 0x4cf5ad432745937fL; 51 int len; 52 53 Murmur3_128Hasher(int seed) { 54 super(16); 55 h1 = seed; 56 h2 = seed; 57 } 58 59 @Override protected void process(ByteBuffer bb) { 60 long k1 = bb.getLong(); 61 long k2 = bb.getLong(); 62 len += 16; 63 bmix64(k1, k2); 64 } 65 66 private void bmix64(long k1, long k2) { 67 k1 *= c1; 68 k1 = Long.rotateLeft(k1, 31); 69 k1 *= c2; 70 h1 ^= k1; 71 72 h1 = Long.rotateLeft(h1, 27); 73 h1 += h2; 74 h1 = h1 * 5 + 0x52dce729; 75 76 k2 *= c2; 77 k2 = Long.rotateLeft(k2, 33); 78 k2 *= c1; 79 h2 ^= k2; 80 81 h2 = Long.rotateLeft(h2, 31); 82 h2 += h1; 83 h2 = h2 * 5 + 0x38495ab5; 84 } 85 86 @Override protected void processRemaining(ByteBuffer bb) { 87 long k1 = 0; 88 long k2 = 0; 89 len += bb.remaining(); 90 switch (bb.remaining()) { 91 case 15: 92 k2 ^= (long) toInt(bb.get(14)) << 48; // fall through 93 case 14: 94 k2 ^= (long) toInt(bb.get(13)) << 40; // fall through 95 case 13: 96 k2 ^= (long) toInt(bb.get(12)) << 32; // fall through 97 case 12: 98 k2 ^= (long) toInt(bb.get(11)) << 24; // fall through 99 case 11: 100 k2 ^= (long) toInt(bb.get(10)) << 16; // fall through 101 case 10: 102 k2 ^= (long) toInt(bb.get(9)) << 8; // fall through 103 case 9: 104 k2 ^= (long) toInt(bb.get(8)) << 0; 105 k2 *= c2; 106 k2 = Long.rotateLeft(k2, 33); 107 k2 *= c1; 108 h2 ^= k2; 109 // fall through 110 case 8: 111 k1 ^= (long) toInt(bb.get(7)) << 56; // fall through 112 case 7: 113 k1 ^= (long) toInt(bb.get(6)) << 48; // fall through 114 case 6: 115 k1 ^= (long) toInt(bb.get(5)) << 40; // fall through 116 case 5: 117 k1 ^= (long) toInt(bb.get(4)) << 32; // fall through 118 case 4: 119 k1 ^= (long) toInt(bb.get(3)) << 24; // fall through 120 case 3: 121 k1 ^= (long) toInt(bb.get(2)) << 16; // fall through 122 case 2: 123 k1 ^= (long) toInt(bb.get(1)) << 8; // fall through 124 case 1: 125 k1 ^= (long) toInt(bb.get(0)) << 0; 126 k1 *= c1; 127 k1 = Long.rotateLeft(k1, 31); 128 k1 *= c2; 129 h1 ^= k1; 130 // fall through 131 default: 132 } 133 } 134 135 @Override public HashCode makeHash() { 136 h1 ^= len; 137 h2 ^= len; 138 139 h1 += h2; 140 h2 += h1; 141 142 h1 = fmix64(h1); 143 h2 = fmix64(h2); 144 145 h1 += h2; 146 h2 += h1; 147 148 ByteBuffer bb = ByteBuffer.wrap(new byte[16]).order(ByteOrder.LITTLE_ENDIAN); 149 bb.putLong(h1); 150 bb.putLong(h2); 151 return HashCodes.fromBytes(bb.array()); 152 } 153 154 private long fmix64(long k) { 155 k ^= k >>> 33; 156 k *= 0xff51afd7ed558ccdL; 157 k ^= k >>> 33; 158 k *= 0xc4ceb9fe1a85ec53L; 159 k ^= k >>> 33; 160 return k; 161 } 162 } 163 164 private static final long serialVersionUID = 0L; 165} 166