pd.if.org Git - nbds/blob - include/murmur.h

   1 //-----------------------------------------------------------------------------
   2 // MurmurHash2, by Austin Appleby
   3
   4 // Note - This code makes a few assumptions about how your machine behaves -
   5
   6 // 1. We can read a 4-byte value from any address without crashing
   7 // 2. sizeof(int) == 4
   8
   9 // And it has a few limitations -
  10
  11 // 1. It will not work incrementally.
  12 // 2. It will not produce the same results on little-endian and big-endian
  13 //    machines.
  14
  15 static inline unsigned int murmur32 (const char *key, int len)
  16 {
  17         // 'm' and 'r' are mixing constants generated offline.
  18         // They're not really 'magic', they just happen to work well.
  19
  20         const unsigned int m = 0x5bd1e995;
  21         const int r = 24;
  22
  23         // Initialize the hash to a 'random' value
  24         unsigned int h = len;
  25
  26         // Mix 4 bytes at a time into the hash
  27
  28         const unsigned char *data = (const unsigned char *)key;
  29
  30         while(len >= 4)
  31         {
  32                 uint32_t k = *(uint32_t *)data;
  33
  34                 k *= m;
  35                 k ^= k >> r;
  36                 k *= m;
  37
  38                 h *= m;
  39                 h ^= k;
  40
  41                 data += 4;
  42                 len -= 4;
  43         }
  44
  45         // Handle the last few bytes of the input array
  46
  47         switch(len)
  48         {
  49         case 3: h ^= data[2] << 16;
  50         case 2: h ^= data[1] << 8;
  51         case 1: h ^= data[0];
  52                 h *= m;
  53         };
  54
  55         // Do a few final mixes of the hash to ensure the last few
  56         // bytes are well-incorporated.
  57
  58         h ^= h >> 13;
  59         h *= m;
  60         h ^= h >> 15;
  61
  62         return h;
  63 }