MurmurHash3 の 32 ビット版

MurmurHash3 の 32 ビット版を書いてみました。

// MurmurHash3 was written by Austin Appleby, and is placed in the public domain.

#include <cstdint>
#include <string>

uint32_t murmurhash3_32 (std::string const& str, std::uint32_t const seed = 0);

文字列を 4 オクテットのブロック列として、 それぞれのブロックをリトル・エンディアンで 32 ビット符号なし整数に読み取っていきます。 末尾でオクテットが足りないときはゼロ・パディングします。 最後に文字列長と定数をミキシングしてハッシュ値とします。 試しに、 リトル・エンディアンx86 と、 ビッグ・エンディアンpower pc の両方でコンパイル & 実行し、 結果が同一になることを確認しています。

//@<byteswap32 インライン関数を定義します@>

std::uint32_t
murmurhash3_32 (std::string const& str, std::uint32_t const seed)
{
    enum { r1 = 15, r2 = 13 };
    static const std::uint32_t c1 = 0xcc9e2d51LU;
    static const std::uint32_t c2 = 0x1b873593LU;
    std::uint32_t hash = seed;
    std::uint32_t const len = str.size ();
    std::size_t const nblock = len / 4U;
    std::uint32_t const* s32 = reinterpret_cast<std::uint32_t const*> (&str[0]);

    std::size_t const nblock = len / 4U;
    std::uint32_t const* s32 = reinterpret_cast<std::uint32_t const*> (&str[0]);
    if (*(reinterpret_cast<std::uint8_t const*> (&c1)) == 0x51U) {
        for (std::size_t i = 0; i < nblock; ++i) {
            std::uint32_t k0 = *s32++;                 // リトル・エンディアン
            k0 *= c1;
            k0 = (k0 << r1) | (k0 >> (32 - r1));
            k0 *= c2;
            hash ^= k0;
            hash = (hash << r2) | (hash >> (32 - r2));
            hash = hash * 5U + 0xe6546b64LU;
        }
    }
    else {
        for (std::size_t i = 0; i < nblock; ++i) {
            std::uint32_t k0 = byteswap32 (*s32++);    // ビッグ・エンディアン
            k0 *= c1;
            k0 = (k0 << r1) | (k0 >> (32 - r1));
            k0 *= c2;
            hash ^= k0;
            hash = (hash << r2) | (hash >> (32 - r2));
            hash = hash * 5U + 0xe6546b64LU;
        }
    }

    std::uint8_t const* const s = reinterpret_cast<std::uint8_t const*> (s32);
    std::uint32_t k1 = 0;
    switch (len & 3U) {
    case 3:
        k1 ^= static_cast<unsigned char> (s[2]) << 16;
    case 2:
        k1 ^= static_cast<unsigned char> (s[1]) << 8;
    case 1:
        k1 ^= static_cast<unsigned char> (s[0]);
        k1 *= c1;
        k1 = (k1 << r1) | (k1 >> (32 - r1));
        k1 *= c2;
        hash ^= k1;
    }
    hash ^= len;
    hash ^= hash >> 16;
    hash *= 0x85ebca6bLU;
    hash ^= hash >> 13;
    hash *= 0xc2b2ae35LU;
    hash ^= hash >> 16;
    return hash;
}

上のコードは、 可搬性を重視して実行時にエンディアン判定をおこなって、 リトル・エンディアンのためのループと、 ビッグ・エンディアンのためのそれに条件分岐しています。 この 2 つのループは、 文字列から読み取るときにバイト・スワップをおこなうかどうかだけが異なっています。 賢いコンパイラなら、 繰り返し中に値が変化しない条件式がループ中に含まれていると、 上のコードのように条件文をくくりだす最適化をしてくれますが、 コンパイラの働きをあてにせずに手動で最適化をおこなっています。

//@<byteswap32 インライン関数を定義します@>=
#if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC__MINOR__ >= 3))
#define byteswap32(x) __builtin_bswap32(x)
#else
static inline std::uint32_t
byteswap32 (std::uint32_t x)
{
    x = ((x & 0x00ff00ffLU) << 8) | ((x & 0xff00ff00LU) >> 8);
    return (x << 16) | (x >> 16);
}
#endif