Murmur3_128HashFunction.java revision 1d580d0f6ee4f21eb309ba7b509d2c6d671c4044 
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