src/basic/MurmurHash2.c

   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 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   const uint32_t m = 0x5bd1e995;
  47   const int r = 24;
  48
  49   // Initialize the hash to a 'random' value
  50
  51   uint32_t h = seed ^ len;
  52
  53   // Mix 4 bytes at a time into the hash
  54
  55   const unsigned char * data = (const unsigned char *)key;
  56
  57   while (len >= 4)
  58   {
  59     uint32_t k = *(uint32_t*)data;
  60
  61     k *= m;
  62     k ^= k >> r;
  63     k *= m;
  64
  65     h *= m;
  66     h ^= k;
  67
  68     data += 4;
  69     len -= 4;
  70   }
  71
  72   // Handle the last few bytes of the input array
  73
  74   switch(len)
  75   {
  76   case 3: h ^= data[2] << 16; /* fall through */
  77   case 2: h ^= data[1] << 8;  /* fall through */
  78   case 1: h ^= data[0];       /* fall through */
  79       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   h ^= h >> 13;
  86   h *= m;
  87   h ^= h >> 15;
  88
  89   return h;
  90 }