Line data    Source code

       1             : /* This file is based on the public domain MurmurHash3 from Austin Appleby:
       2             :  * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
       3             :  *
       4             :  * We use only the 32 bit variant because the 2 produce different result while
       5             :  * we need to produce the same result regardless of the architecture as
       6             :  * clients can be both 64 or 32 bit at the same time.
       7             :  */
       8             : 
       9             : #include <stdlib.h>
      10             : #include <stdint.h>
      11             : #include <string.h>
      12             : 
      13             : #include "config.h"
      14             : #include "util/murmurhash3.h"
      15             : #include "util/sss_endian.h"
      16             : 
      17         998 : static uint32_t rotl(uint32_t x, int8_t r)
      18             : {
      19        1040 :     return (x << r) | (x >> (32 - r));
      20             : }
      21             : 
      22             : /* slower than original but is endian neutral and handles platforms that
      23             :  * do only aligned reads */
      24             : __attribute__((always_inline))
      25             : static inline uint32_t getblock(const uint8_t *p, int i)
      26             : {
      27             :     uint32_t r;
      28         482 :     size_t size = sizeof(uint32_t);
      29             : 
      30         482 :     memcpy(&r, &p[i * size], size);
      31             : 
      32         462 :     return le32toh(r);
      33             : }
      34             : 
      35             : /*
      36             :  * Finalization mix - force all bits of a hash block to avalanche
      37             :  */
      38             : 
      39             : __attribute__((always_inline))
      40             : static inline uint32_t fmix(uint32_t h)
      41             : {
      42          94 :     h ^= h >> 16;
      43          94 :     h *= 0x85ebca6b;
      44          94 :     h ^= h >> 13;
      45          94 :     h *= 0xc2b2ae35;
      46          94 :     h ^= h >> 16;
      47             : 
      48          92 :     return h;
      49             : }
      50             : 
      51             : 
      52          94 : uint32_t murmurhash3(const char *key, int len, uint32_t seed)
      53             : {
      54             :     const uint8_t *blocks;
      55             :     const uint8_t *tail;
      56             :     int nblocks;
      57             :     uint32_t h1;
      58             :     uint32_t k1;
      59             :     uint32_t c1;
      60             :     uint32_t c2;
      61             :     int i;
      62             : 
      63          94 :     blocks = (const uint8_t *)key;
      64          94 :     nblocks = len / 4;
      65          94 :     h1 = seed;
      66          94 :     c1 = 0xcc9e2d51;
      67          94 :     c2 = 0x1b873593;
      68             : 
      69             :     /* body */
      70             : 
      71         576 :     for (i = 0; i < nblocks; i++) {
      72             : 
      73         482 :         k1 = getblock(blocks, i);
      74             : 
      75         482 :         k1 *= c1;
      76         482 :         k1 = rotl(k1, 15);
      77         482 :         k1 *= c2;
      78             : 
      79         482 :         h1 ^= k1;
      80         482 :         h1 = rotl(h1, 13);
      81         482 :         h1 = h1 * 5 + 0xe6546b64;
      82             :     }
      83             : 
      84             :     /* tail */
      85             : 
      86          94 :     tail = (const uint8_t *)key + nblocks * 4;
      87             : 
      88          94 :     k1 = 0;
      89             : 
      90          94 :     switch (len & 3) {
      91             :     case 3:
      92           7 :         k1 ^= tail[2] << 16;
      93             :     case 2:
      94          46 :         k1 ^= tail[1] << 8;
      95             :     case 1:
      96          76 :         k1 ^= tail[0];
      97          76 :         k1 *= c1;
      98          76 :         k1 = rotl(k1, 15);
      99          76 :         k1 *= c2;
     100          76 :         h1 ^= k1;
     101             :     default:
     102          92 :         break;
     103             :     }
     104             : 
     105             :     /* finalization */
     106             : 
     107          94 :     h1 ^= len;
     108          94 :     h1 = fmix(h1);
     109             : 
     110          94 :     return h1;
     111             : }
     112             : 
     113             :