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 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 34 import 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 */ 43 final 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
