crc/murmur3.c

   1 #include "murmur3.h"
   2 #include "../compiler/compiler.h"
   3
   4 static inline uint32_t rotl32(uint32_t x, int8_t r)
   5 {
   6         return (x << r) | (x >> (32 - r));
   7 }
   8
   9 //-----------------------------------------------------------------------------
  10 // Finalization mix - force all bits of a hash block to avalanche
  11
  12 static inline uint32_t fmix32(uint32_t h)
  13 {
  14         h ^= h >> 16;
  15         h *= 0x85ebca6b;
  16         h ^= h >> 13;
  17         h *= 0xc2b2ae35;
  18         h ^= h >> 16;
  19
  20         return h;
  21 }
  22
  23 static uint32_t murmur3_tail(const uint8_t *data, const int nblocks,
  24                              uint32_t len, const uint32_t c1,
  25                              const uint32_t c2, uint32_t h1)
  26 {
  27         const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
  28
  29         uint32_t k1 = 0;
  30         switch (len & 3) {
  31         case 3:
  32                 k1 ^= tail[2] << 16;
  33                 fio_fallthrough;
  34         case 2:
  35                 k1 ^= tail[1] << 8;
  36                 fio_fallthrough;
  37         case 1:
  38                 k1 ^= tail[0];
  39                 k1 *= c1;
  40                 k1 = rotl32(k1, 15);
  41                 k1 *= c2;
  42                 h1 ^= k1;
  43         };
  44
  45         return fmix32(h1 ^ len);
  46 }
  47
  48 uint32_t murmurhash3(const void *key, uint32_t len, uint32_t seed)
  49 {
  50         const uint8_t *data = (const uint8_t *)key;
  51         const int nblocks = len / 4;
  52         uint32_t h1 = seed;
  53         const uint32_t c1 = 0xcc9e2d51;
  54         const uint32_t c2 = 0x1b873593;
  55         const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
  56         int i;
  57
  58         for (i = -nblocks; i; i++) {
  59                 uint32_t k1 = blocks[i];
  60
  61                 k1 *= c1;
  62                 k1 = rotl32(k1, 15);
  63                 k1 *= c2;
  64
  65                 h1 ^= k1;
  66                 h1 = rotl32(h1, 13);
  67                 h1 = h1 * 5 + 0xe6546b64;
  68         }
  69
  70         return murmur3_tail(data, nblocks, len, c1, c2, h1);
  71 }