MurmurHash3 32 ビット char const* 用

今度は char const* 用の関数を作ります。

std::uint32_t murmurhash3_32 (std::size_t const len, char const* const str, std::uint32_t const seed = 0);

昨日の MurmurHash3 32 ビット版は std::string の文字列本体がほとんどの場合 4 バイト・アラインメントされていることを利用して、 ブロックの読み出しを楽にしていました。 4 バイト・アラインメントになっているときは、 同じやりかたで計算します。

// リトル・エンディアンで 4 バイト・アラインメントされた str
uint32_t
murmurhash3_32le_align (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    union {
        std::uint8_t const* p8;
        std::uint32_t const* p32;
        char const* str;
    } s;

    s.str = str;
    std::size_t const count32 = len / 4U;
    std::size_t const tail = len - count32 * 4U;
    std::uint32_t hash = seed;
    for (std::size_t i = 0; i < count32; ++i) {
        hash = murmurhash3_32block (hash, *s.p32++);
    }
    if (tail > 0) {
        std::uint32_t k = read_partial_bytes (s.p8, tail);
        hash = murmurhash3_32mix (hash, k);
    }
    return murmurhash3_32padding (hash, len);
}

ワード読み出しをバイト・スワップするとビッグ・エンディアン用になります。

// ビッグ・エンディアンで 4 バイト・アラインメントされた str
uint32_t
murmurhash3_32be_align (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    // 省略 (リトル・エンディアン murmurhash3_32le_align と同じ)
    for (std::size_t i = 0; i < count32; ++i) {
        hash = murmurhash3_32block (hash, byteswap32 (*s.p32++));
    }
    // 省略 (同上)
}

一般の char const* では、 4 バイト・アラインメントになっていないときがあります。

速度重視の実装なら、 ワード読み出しにこだわることになります。 その場合、 ワード単位で読んだものと欲しいブロックのバイトがずれることがあるので、 バッファリングとバイト・シフトでブロックを組み立ていきます。 例えば、 下の場合では、 先頭 2 バイトをバイト単位で読むと、 次からは 4 バイト・アラインメントでワード読み出しができるので、 3 回ワード単位で読みます。 その後、 残りの 3 バイトをバイト読み出します。 先頭の 2 バイト分がワード読み出しとブロックのずれになります。

    アドレス
    843c6672 'H' バイト読み出し  block[0]  0ビット目の桁
    843c6673 'e' バイト読み出し  block[0]  8ビット目の桁
    843c6674 'l' ワード読み出し  block[0] 16ビット目の桁 lower_shift==16ビット
    843c6675 'l' ↓              block[0] 24ビット目の桁
    843c6676 'o' ↓              block[1]  0ビット目の桁 upper_shift==16ビット
    843c6677 ' ' ↓              block[1]  8ビット目の桁
    843c6678 'M' ワード読み出し  block[1] 16ビット目の桁 lower_shift==16ビット
    843c6679 'u' ↓              block[1] 24ビット目の桁
    843c667a 'r' ↓              block[2]
    843c667b 'm' ↓              block[2]
    843c667c 'u' ワード読み出し  block[2]
    843c667d 'r' ↓              block[2]
    843c667e 'H' ↓              block[3]
    843c667f 'a' ↓              block[3]
    843c6680 's' バイト読み出し  block[3]
    843c6681 'h' バイト読み出し  block[3]
    843c6682 '3' バイト読み出し  block[4]
    843c6683 '\0'

この例のように、 文字列ポインタの指すアドレスから、 ワード読み出しする最初のアドレスまでのバイトアドレスのずれ byteoff を計算すれば、 先頭のバイト読み出し回数 head、 ワード読み出し回数 count32、 末尾のバイト読み出し回数 tail を求めることができます。 なお、 ポインタの指すアドレスを整数演算しなければならないため、 union 型を使って型検査をごまかすことにします。

lower_shift はリトル・エンディアンで読んだワードの下位をブロックへ補充するためのビット・シフト量です。 upper_shift はワードの上位を次のブロックへ格納するビット・シフト量です。 両方とも、 head から算出できます。

//  0123012301230123012301230123
//  c___^___^___^___^___^000....    head==1 count32==5 tail==0
//  c___^___^___^___^___^c00....    head==1 count32==5 tail==1
//  c___^___^___^___^___^cc0....    head==1 count32==5 tail==2
//  c___^___^___^___^___^ccc....    head==1 count32==5 tail==3
//  cc__^^__^^__^^__^^__^^00....    head==2 count32==5 tail==0
//  cc__^^__^^__^^__^^__^^c0....    head==2 count32==5 tail==1
//  cc__^^__^^__^^__^^__^^cc....    head==2 count32==5 tail==2
//  cc__^^__^^__^^__^^__^^ccc000    head==2 count32==5 tail==3
//  ccc_^^^_^^^_^^^_^^^_^^^0....    head==3 count32==5 tail==0
//  ccc_^^^_^^^_^^^_^^^_^^^c....    head==3 count32==5 tail==1
//  ccc_^^^_^^^_^^^_^^^_^^^cc000    head==3 count32==5 tail==2
//  ccc_^^^_^^^_^^^_^^^_^^^ccc00    head==3 count32==5 tail==3
//
//  _ lower_shift, ^ upper_shift, c load uint8_t, 0 zero padding

// リトル・エンディアンで 4 バイト・アラインメントされていない str
uint32_t
murmurhash3_32le_unalign (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    union {
        std::uint8_t const* p8;
        std::uint32_t const* p32;
        char const* str;
        std::uintptr_t i;
    } s;

    s.str = str;
    std::size_t const byteoff = (4U - (s.i & 3U)) & 3U;
    std::size_t const head = byteoff < len ? byteoff : len;
    std::size_t const count32 = (len - head) / 4U;
    std::size_t const tail = len - head - count32 * 4U;
    int const lower_shift = head * 8;
    int const upper_shift = 32 - lower_shift;

    std::uint32_t hash = seed;
    std::uint32_t k = read_partial_bytes (s.p8, head);
    s.p8 += head;
    for (std::size_t i = 0; i < count32; ++i) {
        uint32_t const w = *s.p32++;
        k |= w << lower_shift;
        hash = murmurhash3_32block (hash, k);
        k = w >> upper_shift;
    }
    std::uint32_t v = read_partial_bytes (s.p8, tail);
    k |= v << lower_shift;
    v >>= upper_shift;
    hash = murmurhash3_32mix_unalign (hash, k, v, head + tail);
    return murmurhash3_32padding (hash, len);
}

ビッグ・エンディアン用で、 ワードを読み取ってバイト・スワップするのは同じです。

// ビッグ・エンディアンで 4 バイト・アラインメントされていない str
uint32_t
murmurhash3_32be_unalign (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    // 省略 (リトル・エンディアン murmurhash3_32le_unalign と同じ)
    for (std::size_t i = 0; i < count32; ++i) {
        uint32_t const w = byteswap32 (*s.p32++);
        k |= w << lower_shift;
        hash = murmurhash3_32block (hash, k);
        k = w >> upper_shift;
    }
    // 省略 (同上)
}

上記のブロックの組み立て例のように、 末尾の扱いは tail バイト数だけでなく、 head バイト数も勘定にいれて、 最後のブロックを閉じて、 余りのバイト列をハッシュへ加えます。

// 末尾のバイト列をハッシュへ加えます
static inline uint32_t
murmurhash3_32mix_unalign (std::uint32_t hash, std::uint32_t k, uint32_t v, std::size_t rem_bytes)
{
    // rem_bytes == head + tail
    if (rem_bytes == 4) {
        hash = murmurhash3_32block (hash, k);
    }
    else if (rem_bytes > 4) {
        hash = murmurhash3_32block (hash, k);
        hash = murmurhash3_32mix (hash, v);
    }
    else if (rem_bytes > 0) {
        hash = murmurhash3_32mix (hash, k);
    }
    return hash;
}

ここまでの関数では 4 バイトより小さなバイト列を読み出すインライン関数を使っています。

static inline std::uint32_t
read_partial_bytes (std::uint8_t const* s, std::size_t const byte_count)
{
    std::uint32_t w = 0;
    switch (byte_count) {
    case 3:
        w |= s[2] << 16;
    case 2:
        w |= s[1] << 8;
    case 1:
        w |= s[0];
    }
    return w;
}

MurmurHash3 のそれぞれのブロックをハッシュへミキシングする操作はインライン関数へくくりだしておいたものを使います。

static inline std::uint32_t
murmurhash3_32block (std::uint32_t hash, std::uint32_t k)
{
    k *= 0xcc9e2d51LU;                  // C1
    k = (k << 15) | (k >> 17);          // R1==15
    k *= 0x1b873593LU;                  // C2
    hash ^= k;
    hash = (hash << 13) | (hash >> 19); // R2==13
    hash = hash * 5U + 0xe6546b64LU;
    return hash;
}

ブロック幅に満たない余りのバイト列のミキシング操作も同様にくくりだしています。

static inline std::uint32_t
murmurhash3_32mix (std::uint32_t hash, std::uint32_t k)
{
    k *= 0xcc9e2d51LU;                  // C1
    k = (k << 15) | (k >> 17);          // R1==15
    k *= 0x1b873593LU;                  // C2
    hash ^= k;
    return hash;
}

最後のパディング操作も同様です。

static inline std::uint32_t
murmurhash3_32padding (std::uint32_t hash, std::uint32_t len)
{
    hash ^= len;
    hash ^= hash >> 16;
    hash *= 0x85ebca6bLU;
    hash ^= hash >> 13;
    hash *= 0xc2b2ae35LU;
    hash ^= hash >> 16;
    return hash;
}

エントリ・ポイントではエンディアンとアラインメントをチェックして、 それぞれの関数を呼ぶようにします。

uint32_t
murmurhash3_32 (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    static const std::uint32_t ck = 0x04030201LU;
    static const bool little_endian = *(reinterpret_cast<std::uint8_t const*> (&ck)) == 0x01U;

    union {
        char const* str;
        std::uintptr_t i;
    } s;

    s.str = str;
    if (little_endian) {
        if ((s.i & 3U) == 0) {
            return murmurhash3_32le_align (len, str, seed);
        }
        else {
            return murmurhash3_32le_unalign (len, str, seed);
        }
    }
    else {
        if ((s.i & 3U) == 0) {
            return murmurhash3_32be_align (len, str, seed);
        }
        else {
            return murmurhash3_32be_unalign (len, str, seed);
        }
    }
}