/home/mhx/git/github/libmoost/include/moost/hash/murmur3.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MOOST_HASH_MURMUR3_HPP
#define MOOST_HASH_MURMUR3_HPP

#include <vector>

#include <boost/cstdint.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits/is_pod.hpp>

namespace moost { namespace hash {

class murmur3
{
private:
   static uint32_t fmix(uint32_t h)
   {
     h ^= h >> 16;
     h *= 0x85ebca6b;
     h ^= h >> 13;
     h *= 0xc2b2ae35;
     h ^= h >> 16;

     return h;
   }

   static uint32_t getblock(const uint32_t *p, int i)
   {
     return p[i];
   }

   static uint32_t rotl32 (uint32_t x, int8_t r)
   {
     return (x << r) | (x >> (32 - r));
   }

public:
   static uint32_t compute32(const void *key, size_t len, uint32_t seed)
   {
      const uint8_t *data = reinterpret_cast<const uint8_t *>(key);
      const int nblocks = len/4;

      uint32_t h1 = seed;

      const uint32_t c1 = 0xcc9e2d51;
      const uint32_t c2 = 0x1b873593;

      //----------
      // body

      const uint32_t *blocks = reinterpret_cast<const uint32_t *>(data + nblocks*4);

      for(int i = -nblocks; i; i++)
      {
        uint32_t k1 = getblock(blocks, i);

        k1 *= c1;
        k1 = rotl32(k1, 15);
        k1 *= c2;

        h1 ^= k1;
        h1 = rotl32(h1, 13);
        h1 = h1*5+0xe6546b64;
      }

      //----------
      // tail

      const uint8_t *tail = reinterpret_cast<const uint8_t*>(data + nblocks*4);

      uint32_t k1 = 0;

      switch (len & 3)
      {
         case 3: k1 ^= tail[2] << 16;
         case 2: k1 ^= tail[1] << 8;
         case 1: k1 ^= tail[0];
                 k1 *= c1; k1 = rotl32(k1, 15); k1 *= c2; h1 ^= k1;
      }

      //----------
      // finalization

      h1 ^= len;

      return fmix(h1);
   }

   template <typename T>
   static uint32_t compute32(const T& key, uint32_t seed)
   {
      BOOST_STATIC_ASSERT(boost::is_pod<T>::value);
      return compute32(&key, sizeof(key), seed);
   }

   static uint32_t compute32(const std::string& key, uint32_t seed)
   {
      return compute32(key.data(), key.size(), seed);
   }

   template <typename T>
   static uint32_t compute32(const std::vector<T>& key, uint32_t seed)
   {
      BOOST_STATIC_ASSERT(boost::is_pod<T>::value);
      return compute32(&key[0], sizeof(T)*key.size(), seed);
   }

   template <typename T, unsigned Seed = 0U>
   struct hash32
   {
      size_t operator() (const T& key) const
      {
         return compute32(key, Seed);
      }
   };
};

}}

#endif