001/*
002 * Copyright (c) 2007-2015 Concurrent, Inc. All Rights Reserved.
003 *
004 * Project and contact information: http://www.cascading.org/
005 *
006 * This file is part of the Cascading project.
007 *
008 * Licensed under the Apache License, Version 2.0 (the "License");
009 * you may not use this file except in compliance with the License.
010 * You may obtain a copy of the License at
011 *
012 *     http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing, software
015 * distributed under the License is distributed on an "AS IS" BASIS,
016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017 * See the License for the specific language governing permissions and
018 * limitations under the License.
019 */
020
021package cascading.util;
022
023/**
024 * Murmur3 is a fast non cryptographic hash algorithm. This class implements the 32bit version of Murmur 3.
025 * <p/>
026 * The code has been taken from the guava project:
027 * https://github.com/google/guava/blob/v18.0/guava/src/com/google/common/hash/Murmur3_32HashFunction.java
028 */
029
030/*
031* Source:
032* http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
033* (Modified to adapt to Guava coding conventions and to use the HashFunction interface)
034*/
035public class Murmur3
036  {
037  private static final int C1 = 0xcc9e2d51;
038  private static final int C2 = 0x1b873593;
039  public static final int SEED = 0x9747b28c;
040
041  /**
042   * Applies murmur3 to the given input.
043   *
044   * @param input The int to hash.
045   * @return a murmur3 hash.
046   */
047  public static int hashInt( int input )
048    {
049    int k1 = mixK1( input );
050    int h1 = mixH1( SEED, k1 );
051    return fmix( h1, 4 );
052    }
053
054  public static int mixK1( int k1 )
055    {
056    k1 *= C1;
057    k1 = Integer.rotateLeft( k1, 15 );
058    k1 *= C2;
059    return k1;
060    }
061
062  public static int mixH1( int h1, int k1 )
063    {
064    h1 ^= k1;
065    h1 = Integer.rotateLeft( h1, 13 );
066    h1 = h1 * 5 + 0xe6546b64;
067    return h1;
068    }
069
070  // Finalization mix - force all bits of a hash block to avalanche
071  public static int fmix( int h1, int length )
072    {
073    h1 ^= length;
074    h1 ^= h1 >>> 16;
075    h1 *= 0x85ebca6b;
076    h1 ^= h1 >>> 13;
077    h1 *= 0xc2b2ae35;
078    h1 ^= h1 >>> 16;
079    return h1;
080    }
081  }