ext/tdb/murmur3.c

   1 #include "rbtdb.h"
   2 /*
   3  * https://sites.google.com/site/murmurhash/
   4  *
   5  * MurmurHash3 was written by Austin Appleby, and is placed in the public
   6  * domain. The author hereby disclaims copyright to this source code.
   7  *
   8  * Eric Wong trivially ported this to C for Ruby tdb (32-bit version only)
   9  */
  10
  11 #include <stdint.h>
  12 #define FORCE_INLINE __attribute__((always_inline))
  13
  14 static inline uint32_t rotl32(uint32_t x, int8_t r)
  15 {
  16         return (x << r) | (x >> (32 - r));
  17 }
  18
  19 #define ROTL32(x,y)     rotl32(x,y)
  20
  21 #define BIG_CONSTANT(x) (x##LLU)
  22
  23 /* ----------------------------------------------------------------------------
  24  * Block read - if your platform needs to do endian-swapping or can only
  25  * handle aligned reads, do the conversion here
  26  */
  27
  28 static FORCE_INLINE uint32_t getblock(const uint32_t * p, int i)
  29 {
  30         return p[i];
  31 }
  32
  33 /* ----------------------------------------------------------------------------
  34  * Finalization mix - force all bits of a hash block to avalanche
  35  */
  36
  37 static FORCE_INLINE uint32_t fmix(uint32_t h)
  38 {
  39         h ^= h >> 16;
  40         h *= 0x85ebca6b;
  41         h ^= h >> 13;
  42         h *= 0xc2b2ae35;
  43         h ^= h >> 16;
  44
  45         return h;
  46 }
  47
  48 unsigned int rbtdb_murmur3a(TDB_DATA * key)
  49 {
  50         const uint8_t *data = key->dptr;
  51         int len = (int)key->dsize;
  52         const int nblocks = len / 4;
  53         static const uint32_t seed;
  54         uint32_t h1 = seed;
  55         int i;
  56
  57         static const uint32_t c1 = 0xcc9e2d51;
  58         static const uint32_t c2 = 0x1b873593;
  59
  60         /* body */
  61         const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
  62
  63         for (i = -nblocks; i; i++) {
  64                 uint32_t k1 = getblock(blocks, i);
  65
  66                 k1 *= c1;
  67                 k1 = ROTL32(k1, 15);
  68                 k1 *= c2;
  69
  70                 h1 ^= k1;
  71                 h1 = ROTL32(h1, 13);
  72                 h1 = h1 * 5 + 0xe6546b64;
  73         }
  74
  75         /* tail */
  76         {
  77                 const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
  78                 uint32_t k1 = 0;
  79
  80                 switch (len & 3) {
  81                 case 3:
  82                         k1 ^= tail[2] << 16;
  83                 case 2:
  84                         k1 ^= tail[1] << 8;
  85                 case 1:
  86                         k1 ^= tail[0];
  87                         k1 *= c1;
  88                         k1 = ROTL32(k1, 15);
  89                         k1 *= c2;
  90                         h1 ^= k1;
  91                 };
  92         }
  93
  94         /* finalization */
  95
  96         h1 ^= len;
  97
  98         return fmix(h1);
  99 }