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