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
15 /*
16 * MurmurHash3 was written by Austin Appleby, and is placed in the public
17 * domain. The author hereby disclaims copyright to this source code.
18 */
19
20 /*
21 * Source:
22 * https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
23 * (Modified to adapt to Guava coding conventions and to use the HashFunction interface)
24 */
25
26 package com.google.common.hash;
27
28 import static com.google.common.primitives.UnsignedBytes.toInt;
29
30 import com.google.errorprone.annotations.Immutable;
31 import java.io.Serializable;
32 import java.nio.ByteBuffer;
33 import java.nio.ByteOrder;
34 import javax.annotation.CheckForNull;
35
36 /**
37 * See MurmurHash3_x64_128 in <a href="http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp">the
38 * C++ implementation</a>.
39 *
40 * @author Austin Appleby
41 * @author Dimitris Andreou
42 */
43 @Immutable
44 @ElementTypesAreNonnullByDefault
45 final class Murmur3_128HashFunction extends AbstractHashFunction implements Serializable {
46 static final HashFunction MURMUR3_128 = new Murmur3_128HashFunction(0);
47
48 static final HashFunction GOOD_FAST_HASH_128 =
49 new Murmur3_128HashFunction(Hashing.GOOD_FAST_HASH_SEED);
50
51 // TODO(user): when the shortcuts are implemented, update BloomFilterStrategies
52 private final int seed;
53
54 Murmur3_128HashFunction(int seed) {
55 this.seed = seed;
56 }
57
58 @Override
59 public int bits() {
60 return 128;
61 }
62
63 @Override
64 public Hasher newHasher() {
65 return new Murmur3_128Hasher(seed);
66 }
67
68 @Override
69 public String toString() {
70 return "Hashing.murmur3_128(" + seed + ")";
71 }
72
73 @Override
74 public boolean equals(@CheckForNull Object object) {
75 if (object instanceof Murmur3_128HashFunction) {
76 Murmur3_128HashFunction other = (Murmur3_128HashFunction) object;
77 return seed == other.seed;
78 }
79 return false;
80 }
81
82 @Override
83 public int hashCode() {
84 return getClass().hashCode() ^ seed;
85 }
86
87 private static final class Murmur3_128Hasher extends AbstractStreamingHasher {
88 private static final int CHUNK_SIZE = 16;
89 private static final long C1 = 0x87c37b91114253d5L;
90 private static final long C2 = 0x4cf5ad432745937fL;
91 private long h1;
92 private long h2;
93 private int length;
94
95 Murmur3_128Hasher(int seed) {
96 super(CHUNK_SIZE);
97 this.h1 = seed;
98 this.h2 = seed;
99 this.length = 0;
100 }
101
102 @Override
103 protected void process(ByteBuffer bb) {
104 long k1 = bb.getLong();
105 long k2 = bb.getLong();
106 bmix64(k1, k2);
107 length += CHUNK_SIZE;
108 }
109
110 private void bmix64(long k1, long k2) {
111 h1 ^= mixK1(k1);
112
113 h1 = Long.rotateLeft(h1, 27);
114 h1 += h2;
115 h1 = h1 * 5 + 0x52dce729;
116
117 h2 ^= mixK2(k2);
118
119 h2 = Long.rotateLeft(h2, 31);
120 h2 += h1;
121 h2 = h2 * 5 + 0x38495ab5;
122 }
123
124 @Override
125 protected void processRemaining(ByteBuffer bb) {
126 long k1 = 0;
127 long k2 = 0;
128 length += bb.remaining();
129 switch (bb.remaining()) {
130 case 15:
131 k2 ^= (long) toInt(bb.get(14)) << 48; // fall through
132 case 14:
133 k2 ^= (long) toInt(bb.get(13)) << 40; // fall through
134 case 13:
135 k2 ^= (long) toInt(bb.get(12)) << 32; // fall through
136 case 12:
137 k2 ^= (long) toInt(bb.get(11)) << 24; // fall through
138 case 11:
139 k2 ^= (long) toInt(bb.get(10)) << 16; // fall through
140 case 10:
141 k2 ^= (long) toInt(bb.get(9)) << 8; // fall through
142 case 9:
143 k2 ^= (long) toInt(bb.get(8)); // fall through
144 case 8:
145 k1 ^= bb.getLong();
146 break;
147 case 7:
148 k1 ^= (long) toInt(bb.get(6)) << 48; // fall through
149 case 6:
150 k1 ^= (long) toInt(bb.get(5)) << 40; // fall through
151 case 5:
152 k1 ^= (long) toInt(bb.get(4)) << 32; // fall through
153 case 4:
154 k1 ^= (long) toInt(bb.get(3)) << 24; // fall through
155 case 3:
156 k1 ^= (long) toInt(bb.get(2)) << 16; // fall through
157 case 2:
158 k1 ^= (long) toInt(bb.get(1)) << 8; // fall through
159 case 1:
160 k1 ^= (long) toInt(bb.get(0));
161 break;
162 default:
163 throw new AssertionError("Should never get here.");
164 }
165 h1 ^= mixK1(k1);
166 h2 ^= mixK2(k2);
167 }
168
169 @Override
170 protected HashCode makeHash() {
171 h1 ^= length;
172 h2 ^= length;
173
174 h1 += h2;
175 h2 += h1;
176
177 h1 = fmix64(h1);
178 h2 = fmix64(h2);
179
180 h1 += h2;
181 h2 += h1;
182
183 return HashCode.fromBytesNoCopy(
184 ByteBuffer.wrap(new byte[CHUNK_SIZE])
185 .order(ByteOrder.LITTLE_ENDIAN)
186 .putLong(h1)
187 .putLong(h2)
188 .array());
189 }
190
191 private static long fmix64(long k) {
192 k ^= k >>> 33;
193 k *= 0xff51afd7ed558ccdL;
194 k ^= k >>> 33;
195 k *= 0xc4ceb9fe1a85ec53L;
196 k ^= k >>> 33;
197 return k;
198 }
199
200 private static long mixK1(long k1) {
201 k1 *= C1;
202 k1 = Long.rotateLeft(k1, 31);
203 k1 *= C2;
204 return k1;
205 }
206
207 private static long mixK2(long k2) {
208 k2 *= C2;
209 k2 = Long.rotateLeft(k2, 33);
210 k2 *= C1;
211 return k2;
212 }
213 }
214
215 private static final long serialVersionUID = 0L;
216 }