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