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 versions only)
   9  */
  10
  11 #include <stdint.h>
  12
  13 static inline uint32_t rotl32(uint32_t x, int8_t r)
  14 {
  15         return (x << r) | (x >> (32 - r));
  16 }
  17
  18 #define ROTL32(x,y)     rotl32(x,y)
  19
  20 #define BIG_CONSTANT(x) (x##LLU)
  21
  22 /* ----------------------------------------------------------------------------
  23  * Block read - if your platform needs to do endian-swapping or can only
  24  * handle aligned reads, do the conversion here
  25  */
  26
  27 static inline uint32_t getblock(const uint32_t * p, int i)
  28 {
  29         return p[i];
  30 }
  31
  32 /* ----------------------------------------------------------------------------
  33  * Finalization mix - force all bits of a hash block to avalanche
  34  */
  35
  36 static inline uint32_t fmix(uint32_t h)
  37 {
  38         h ^= h >> 16;
  39         h *= 0x85ebca6b;
  40         h ^= h >> 13;
  41         h *= 0xc2b2ae35;
  42         h ^= h >> 16;
  43
  44         return h;
  45 }
  46
  47 unsigned int rbtdb_murmur3a(TDB_DATA * key)
  48 {
  49         const uint8_t *data = key->dptr;
  50         int len = (int)key->dsize;
  51         const int nblocks = len / 4;
  52         static const uint32_t seed;
  53         uint32_t h1 = seed;
  54         int i;
  55
  56         static const uint32_t c1 = 0xcc9e2d51;
  57         static const uint32_t c2 = 0x1b873593;
  58
  59         /* body */
  60         const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
  61
  62         for (i = -nblocks; i; i++) {
  63                 uint32_t k1 = getblock(blocks, i);
  64
  65                 k1 *= c1;
  66                 k1 = ROTL32(k1, 15);
  67                 k1 *= c2;
  68
  69                 h1 ^= k1;
  70                 h1 = ROTL32(h1, 13);
  71                 h1 = h1 * 5 + 0xe6546b64;
  72         }
  73
  74         /* tail */
  75         {
  76                 const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
  77                 uint32_t k1 = 0;
  78
  79                 switch (len & 3) {
  80                 case 3:
  81                         k1 ^= tail[2] << 16;
  82                 case 2:
  83                         k1 ^= tail[1] << 8;
  84                 case 1:
  85                         k1 ^= tail[0];
  86                         k1 *= c1;
  87                         k1 = ROTL32(k1, 15);
  88                         k1 *= c2;
  89                         h1 ^= k1;
  90                 };
  91         }
  92
  93         /* finalization */
  94
  95         h1 ^= len;
  96
  97         return fmix(h1);
  98 }
  99
 100 static inline uint64_t rotl64(uint64_t x, int8_t r)
 101 {
 102         return (x << r) | (x >> (64 - r));
 103 }
 104
 105 #define ROTL64(x,y)     rotl64(x,y)
 106
 107 static inline uint64_t getblock64(const uint64_t * p, int i)
 108 {
 109         return p[i];
 110 }
 111
 112 static inline uint64_t fmix64(uint64_t k)
 113 {
 114         k ^= k >> 33;
 115         k *= BIG_CONSTANT(0xff51afd7ed558ccd);
 116         k ^= k >> 33;
 117         k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
 118         k ^= k >> 33;
 119
 120         return k;
 121 }
 122
 123 /* this was a 128-bit hash for x86_64, but we only want 32-bits */
 124 unsigned int rbtdb_murmur3f(TDB_DATA * key)
 125 {
 126         const uint8_t *data = key->dptr;
 127         int len = (int)key->dsize;
 128         const int nblocks = len / 16;
 129         static const uint32_t seed;
 130         uint64_t h1 = seed;
 131         uint64_t h2 = seed;
 132         uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
 133         uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
 134         int i;
 135
 136         /* body */
 137         const uint64_t *blocks = (const uint64_t *)(data);
 138
 139         for (i = 0; i < nblocks; i++) {
 140                 uint64_t k1 = getblock64(blocks, i * 2 + 0);
 141                 uint64_t k2 = getblock64(blocks, i * 2 + 1);
 142
 143                 k1 *= c1;
 144                 k1 = ROTL64(k1, 31);
 145                 k1 *= c2;
 146                 h1 ^= k1;
 147
 148                 h1 = ROTL64(h1, 27);
 149                 h1 += h2;
 150                 h1 = h1 * 5 + 0x52dce729;
 151
 152                 k2 *= c2;
 153                 k2 = ROTL64(k2, 33);
 154                 k2 *= c1;
 155                 h2 ^= k2;
 156
 157                 h2 = ROTL64(h2, 31);
 158                 h2 += h1;
 159                 h2 = h2 * 5 + 0x38495ab5;
 160         }
 161
 162         /* tail */
 163         {
 164                 const uint8_t *tail = (const uint8_t *)(data + nblocks * 16);
 165
 166                 uint64_t k1 = 0;
 167                 uint64_t k2 = 0;
 168                 #define CAST64(x) ((uint64_t)(x))
 169
 170                 switch (len & 15) {
 171                 case 15:
 172                         k2 ^= CAST64(tail[14]) << 48;
 173                 case 14:
 174                         k2 ^= CAST64(tail[13]) << 40;
 175                 case 13:
 176                         k2 ^= CAST64(tail[12]) << 32;
 177                 case 12:
 178                         k2 ^= CAST64(tail[11]) << 24;
 179                 case 11:
 180                         k2 ^= CAST64(tail[10]) << 16;
 181                 case 10:
 182                         k2 ^= CAST64(tail[9]) << 8;
 183                 case 9:
 184                         k2 ^= CAST64(tail[8]) << 0;
 185                         k2 *= c2;
 186                         k2 = ROTL64(k2, 33);
 187                         k2 *= c1;
 188                         h2 ^= k2;
 189
 190                 case 8:
 191                         k1 ^= CAST64(tail[7]) << 56;
 192                 case 7:
 193                         k1 ^= CAST64(tail[6]) << 48;
 194                 case 6:
 195                         k1 ^= CAST64(tail[5]) << 40;
 196                 case 5:
 197                         k1 ^= CAST64(tail[4]) << 32;
 198                 case 4:
 199                         k1 ^= CAST64(tail[3]) << 24;
 200                 case 3:
 201                         k1 ^= CAST64(tail[2]) << 16;
 202                 case 2:
 203                         k1 ^= CAST64(tail[1]) << 8;
 204                 case 1:
 205                         k1 ^= CAST64(tail[0]) << 0;
 206                         k1 *= c1;
 207                         k1 = ROTL64(k1, 31);
 208                         k1 *= c2;
 209                         h1 ^= k1;
 210                 };
 211         }
 212
 213         /* finalization */
 214
 215         h1 ^= len;
 216         h2 ^= len;
 217
 218         h1 += h2;
 219         h2 += h1;
 220
 221         h1 = fmix64(h1);
 222         h2 = fmix64(h2);
 223
 224         h1 += h2;
 225
 226         /* not needed for 32-bit hash */
 227         /* h2 += h1; */
 228
 229         return (unsigned int)h1; /* truncate to 32-bits */
 230 }