Home | History | Annotate | Download | only in hash 
      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 package com.google.common.hash;
     16 
     17 import static com.google.common.primitives.UnsignedBytes.toInt;
     18 
     19 import java.io.Serializable;
     20 import java.nio.ByteBuffer;
     21 import java.nio.ByteOrder;
     22 
     23 /**
     24  * See http://smhasher.googlecode.com/svn/trunk/MurmurHash3.cpp
     25  * MurmurHash3_x64_128
     26  *
     27  * @author aappleby (at) google.com (Austin Appleby)
     28  * @author andreou (at) google.com (Dimitris Andreou)
     29  */
     30 final 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