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