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 //-----------------------------------------------------------------------------
  19 // Platform-specific functions and macros
  20
  21 // Microsoft Visual Studio
  22
  23 #if defined(_MSC_VER)
  24
  25 #define BIG_CONSTANT(x) (x)
  26
  27 // Other compilers
  28
  29 #else   // defined(_MSC_VER)
  30
  31 #define BIG_CONSTANT(x) (x##LLU)
  32
  33 #endif // !defined(_MSC_VER)
  34
  35 //-----------------------------------------------------------------------------
  36
  37 uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )
  38 {
  39   // 'm' and 'r' are mixing constants generated offline.
  40   // They're not really 'magic', they just happen to work well.
  41
  42   const uint32_t m = 0x5bd1e995;
  43   const int r = 24;
  44
  45   // Initialize the hash to a 'random' value
  46
  47   uint32_t h = seed ^ len;
  48
  49   // Mix 4 bytes at a time into the hash
  50
  51   const unsigned char * data = (const unsigned char *)key;
  52
  53   while (len >= 4)
  54   {
  55     uint32_t k = *(uint32_t*)data;
  56
  57     k *= m;
  58     k ^= k >> r;
  59     k *= m;
  60
  61     h *= m;
  62     h ^= k;
  63
  64     data += 4;
  65     len -= 4;
  66   }
  67
  68   // Handle the last few bytes of the input array
  69
  70   switch(len)
  71   {
  72   case 3: h ^= data[2] << 16; /* fall through */
  73   case 2: h ^= data[1] << 8;  /* fall through */
  74   case 1: h ^= data[0];       /* fall through */
  75       h *= m;
  76   };
  77
  78   // Do a few final mixes of the hash to ensure the last few
  79   // bytes are well-incorporated.
  80
  81   h ^= h >> 13;
  82   h *= m;
  83   h ^= h >> 15;
  84
  85   return h;
  86 }