Branch data     Line data    Source code

       1                 :            : //-----------------------------------------------------------------------------
       2                 :            : // MurmurHash2 was written by Austin Appleby, and is placed in the public
       3                 :            : // domain. The author hereby disclaims copyright to this source code.
       4                 :            : 
       5                 :            : // Note - This code makes a few assumptions about how your machine behaves -
       6                 :            : 
       7                 :            : // 1. We can read a 4-byte value from any address without crashing
       8                 :            : // 2. sizeof(int) == 4
       9                 :            : 
      10                 :            : // And it has a few limitations -
      11                 :            : 
      12                 :            : // 1. It will not work incrementally.
      13                 :            : // 2. It will not produce the same results on little-endian and big-endian
      14                 :            : //    machines.
      15                 :            : 
      16                 :            : #include "MurmurHash2.h"
      17                 :            : 
      18                 :            : #if __GNUC__ >= 7
      19                 :            : _Pragma("GCC diagnostic ignored \"-Wimplicit-fallthrough\"")
      20                 :            : #endif
      21                 :            : 
      22                 :            : //-----------------------------------------------------------------------------
      23                 :            : // Platform-specific functions and macros
      24                 :            : 
      25                 :            : // Microsoft Visual Studio
      26                 :            : 
      27                 :            : #if defined(_MSC_VER)
      28                 :            : 
      29                 :            : #define BIG_CONSTANT(x) (x)
      30                 :            : 
      31                 :            : // Other compilers
      32                 :            : 
      33                 :            : #else        // defined(_MSC_VER)
      34                 :            : 
      35                 :            : #define BIG_CONSTANT(x) (x##LLU)
      36                 :            : 
      37                 :            : #endif // !defined(_MSC_VER)
      38                 :            : 
      39                 :            : //-----------------------------------------------------------------------------
      40                 :            : 
      41                 :         48 : uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )
      42                 :            : {
      43                 :            :   // 'm' and 'r' are mixing constants generated offline.
      44                 :            :   // They're not really 'magic', they just happen to work well.
      45                 :            : 
      46                 :         48 :   const uint32_t m = 0x5bd1e995;
      47                 :         48 :   const int r = 24;
      48                 :            : 
      49                 :            :   // Initialize the hash to a 'random' value
      50                 :            : 
      51                 :         48 :   uint32_t h = seed ^ len;
      52                 :            : 
      53                 :            :   // Mix 4 bytes at a time into the hash
      54                 :            : 
      55                 :         48 :   const unsigned char * data = (const unsigned char *)key;
      56                 :            : 
      57         [ +  + ]:         92 :   while (len >= 4)
      58                 :            :   {
      59                 :         44 :     uint32_t k = *(uint32_t*)data;
      60                 :            : 
      61                 :         44 :     k *= m;
      62                 :         44 :     k ^= k >> r;
      63                 :         44 :     k *= m;
      64                 :            : 
      65                 :         44 :     h *= m;
      66                 :         44 :     h ^= k;
      67                 :            : 
      68                 :         44 :     data += 4;
      69                 :         44 :     len -= 4;
      70                 :            :   }
      71                 :            : 
      72                 :            :   // Handle the last few bytes of the input array
      73                 :            : 
      74   [ +  -  -  - ]:         48 :   switch(len)
      75                 :            :   {
      76                 :         48 :   case 3: h ^= data[2] << 16; /* fall through */
      77                 :         48 :   case 2: h ^= data[1] << 8;  /* fall through */
      78                 :         48 :   case 1: h ^= data[0];       /* fall through */
      79                 :         48 :       h *= m;
      80                 :            :   };
      81                 :            : 
      82                 :            :   // Do a few final mixes of the hash to ensure the last few
      83                 :            :   // bytes are well-incorporated.
      84                 :            : 
      85                 :         48 :   h ^= h >> 13;
      86                 :         48 :   h *= m;
      87                 :         48 :   h ^= h >> 15;
      88                 :            : 
      89                 :         48 :   return h;
      90                 :            : }