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    
021    package 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    * Copyright (C) 2011 The Guava Authors
032    *
033    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
034    * in compliance with the License. You may obtain a copy of the License at
035    *
036    * http://www.apache.org/licenses/LICENSE-2.0
037    *
038    * Unless required by applicable law or agreed to in writing, software distributed under the License
039    * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
040    * or implied. See the License for the specific language governing permissions and limitations under
041    * the License.
042    */
043    /*
044    * MurmurHash3 was written by Austin Appleby, and is placed in the public
045    * domain. The author hereby disclaims copyright to this source code.
046    */
047    /*
048    * Source:
049    * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
050    * (Modified to adapt to Guava coding conventions and to use the HashFunction interface)
051    */
052    public class Murmur3
053      {
054      private static final int C1 = 0xcc9e2d51;
055      private static final int C2 = 0x1b873593;
056      public static final int SEED = 0x9747b28c;
057    
058      /**
059       * Applies murmur3 to the given input.
060       *
061       * @param input The int to hash.
062       * @return a murmur3 hash.
063       */
064      public static int hashInt( int input )
065        {
066        int k1 = mixK1( input );
067        int h1 = mixH1( SEED, k1 );
068        return fmix( h1, 4 );
069        }
070    
071      public static int mixK1( int k1 )
072        {
073        k1 *= C1;
074        k1 = Integer.rotateLeft( k1, 15 );
075        k1 *= C2;
076        return k1;
077        }
078    
079      public static int mixH1( int h1, int k1 )
080        {
081        h1 ^= k1;
082        h1 = Integer.rotateLeft( h1, 13 );
083        h1 = h1 * 5 + 0xe6546b64;
084        return h1;
085        }
086    
087      // Finalization mix - force all bits of a hash block to avalanche
088      public static int fmix( int h1, int length )
089        {
090        h1 ^= length;
091        h1 ^= h1 >>> 16;
092        h1 *= 0x85ebca6b;
093        h1 ^= h1 >>> 13;
094        h1 *= 0xc2b2ae35;
095        h1 ^= h1 >>> 16;
096        return h1;
097        }
098      }