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 com.google.common.primitives.Chars; 31 import com.google.common.primitives.Ints; 32 import com.google.common.primitives.Longs; 33 34 import java.io.Serializable; 35 import java.nio.ByteBuffer; 36 37 import javax.annotation.Nullable; 38 39 /** 40 * See http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp 41 * MurmurHash3_x86_32 42 * 43 * @author Austin Appleby 44 * @author Dimitris Andreou 45 * @author Kurt Alfred Kluever 46 */ 47 final class Murmur3_32HashFunction extends AbstractStreamingHashFunction implements Serializable { 48 private static final int C1 = 0xcc9e2d51; 49 private static final int C2 = 0x1b873593; 50 51 private final int seed; 52 53 Murmur3_32HashFunction(int seed) { 54 this.seed = seed; 55 } 56 57 @Override public int bits() { 58 return 32; 59 } 60 61 @Override public Hasher newHasher() { 62 return new Murmur3_32Hasher(seed); 63 } 64 65 @Override 66 public String toString() { 67 return "Hashing.murmur3_32(" + seed + ")"; 68 } 69 70 @Override 71 public boolean equals(@Nullable Object object) { 72 if (object instanceof Murmur3_32HashFunction) { 73 Murmur3_32HashFunction other = (Murmur3_32HashFunction) 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 @Override public HashCode hashInt(int input) { 85 int k1 = mixK1(input); 86 int h1 = mixH1(seed, k1); 87 88 return fmix(h1, Ints.BYTES); 89 } 90 91 @Override public HashCode hashLong(long input) { 92 int low = (int) input; 93 int high = (int) (input >>> 32); 94 95 int k1 = mixK1(low); 96 int h1 = mixH1(seed, k1); 97 98 k1 = mixK1(high); 99 h1 = mixH1(h1, k1); 100 101 return fmix(h1, Longs.BYTES); 102 } 103 104 // TODO(user): Maybe implement #hashBytes instead? 105 @Override public HashCode hashUnencodedChars(CharSequence input) { 106 int h1 = seed; 107 108 // step through the CharSequence 2 chars at a time 109 for (int i = 1; i < input.length(); i += 2) { 110 int k1 = input.charAt(i - 1) | (input.charAt(i) << 16); 111 k1 = mixK1(k1); 112 h1 = mixH1(h1, k1); 113 } 114 115 // deal with any remaining characters 116 if ((input.length() & 1) == 1) { 117 int k1 = input.charAt(input.length() - 1); 118 k1 = mixK1(k1); 119 h1 ^= k1; 120 } 121 122 return fmix(h1, Chars.BYTES * input.length()); 123 } 124 125 private static int mixK1(int k1) { 126 k1 *= C1; 127 k1 = Integer.rotateLeft(k1, 15); 128 k1 *= C2; 129 return k1; 130 } 131 132 private static int mixH1(int h1, int k1) { 133 h1 ^= k1; 134 h1 = Integer.rotateLeft(h1, 13); 135 h1 = h1 * 5 + 0xe6546b64; 136 return h1; 137 } 138 139 // Finalization mix - force all bits of a hash block to avalanche 140 private static HashCode fmix(int h1, int length) { 141 h1 ^= length; 142 h1 ^= h1 >>> 16; 143 h1 *= 0x85ebca6b; 144 h1 ^= h1 >>> 13; 145 h1 *= 0xc2b2ae35; 146 h1 ^= h1 >>> 16; 147 return HashCode.fromInt(h1); 148 } 149 150 private static final class Murmur3_32Hasher extends AbstractStreamingHasher { 151 private static final int CHUNK_SIZE = 4; 152 private int h1; 153 private int length; 154 155 Murmur3_32Hasher(int seed) { 156 super(CHUNK_SIZE); 157 this.h1 = seed; 158 this.length = 0; 159 } 160 161 @Override protected void process(ByteBuffer bb) { 162 int k1 = Murmur3_32HashFunction.mixK1(bb.getInt()); 163 h1 = Murmur3_32HashFunction.mixH1(h1, k1); 164 length += CHUNK_SIZE; 165 } 166 167 @Override protected void processRemaining(ByteBuffer bb) { 168 length += bb.remaining(); 169 int k1 = 0; 170 for (int i = 0; bb.hasRemaining(); i += 8) { 171 k1 ^= toInt(bb.get()) << i; 172 } 173 h1 ^= Murmur3_32HashFunction.mixK1(k1); 174 } 175 176 @Override public HashCode makeHash() { 177 return Murmur3_32HashFunction.fmix(h1, length); 178 } 179 } 180 181 private static final long serialVersionUID = 0L; 182 } 183
