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 uint32_t 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 uint32_t m = 0x5bd1e995;
  21         const int r = 24;
  22
  23         // Initialize the hash to a 'random' value
  24         uint32_t 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 }
  64
  65 static inline uint32_t murmur32_8b (uint64_t key)
  66 {
  67     // 'm' and 'r' are mixing constants generated offline.
  68     // They're not really 'magic', they just happen to work well.
  69
  70     const uint32_t m = 0x5bd1e995;
  71     const int r = 24;
  72
  73     // Initialize the hash to a 'random' value
  74     uint32_t h = 8;
  75
  76     const unsigned char *data = (const unsigned char *)&key;
  77
  78     uint32_t k1 = *(uint32_t *)data;
  79     uint32_t k2 = *(uint32_t *)(data + 4);
  80
  81     k1 *= m;
  82     k1 ^= k1 >> r;
  83     k1 *= m;
  84
  85     k2 *= m;
  86     k2 ^= k2 >> r;
  87     k2 *= m;
  88
  89     // Mix 4 bytes at a time into the hash
  90
  91     h *= m;
  92     h ^= k1;
  93     h *= m;
  94     h ^= k2;
  95
  96     // Do a few final mixes of the hash to ensure the last few
  97     // bytes are well-incorporated.
  98
  99     h ^= h >> 13;
 100     h *= m;
 101     h ^= h >> 15;
 102
 103     return h;
 104 }
 105
 106 static inline uint32_t murmur32_4b (uint32_t key)
 107 {
 108     // 'm' and 'r' are mixing constants generated offline.
 109     // They're not really 'magic', they just happen to work well.
 110
 111     const uint32_t m = 0x5bd1e995;
 112     const int r = 24;
 113
 114     // Initialize the hash to a 'random' value
 115     uint32_t h = 4;
 116
 117     uint32_t k = *(uint32_t *)&key;
 118
 119     k *= m;
 120     k ^= k >> r;
 121     k *= m;
 122
 123     // Mix 4 bytes at a time into the hash
 124
 125     h *= m;
 126     h ^= k;
 127
 128     // Do a few final mixes of the hash to ensure the last few
 129     // bytes are well-incorporated.
 130
 131     h ^= h >> 13;
 132     h *= m;
 133     h ^= h >> 15;
 134
 135     return h;
 136 }