SipHash-1-3

ハッシュ表用の文字列のハッシュ関数に SipHash が主流になった当初はラウンド数が 2-4 の使い方だったのですが、 2015 年末に Rust がラウンド数を 1-3 に切り詰めてから、 Perl5 *1Ruby も昨年末に、 Python も今年の 2 月始めにラウンド数を減らしました。

C++11 でも切り詰め版を使うことにしようと、 ruby の random.c にある rb_memhash 関数のような感じで使える SipHash-1-3 関数を C++11 で書いてみました。 16 バイトのシード列を渡し、 ポインタ s から長さ len のバイト列の 8 バイト整数のハッシュ値を求めます。 コメント・アウトしている sipround を動くようにすると SipHash-2-4 になります。 unordered_map で使うときは、 シングルトンの Hash クラスを作っておいて、 それにシード列をプロセス開始時に一度だけ乱数を設定しておいて、 プロセスが動いている間は、 そのシード列を使いつづけながらハッシュ値を求めるようにすれば良いのでしょう。

なお、 ラウンド数を切り詰めても SipHash は遅いので、 私はコンパイラのシンボル表等で攻撃を考慮しないで良い用途には速度重視で MurmurHash3 を、 不特定多数から送られてくる文字列を扱うウェブ・アプリケーションには SipHash をと使い分けています。

SipHash はテスト・ベクタが少ないのがちょっと困ります。 コーディングするなら、 オリジナルの SipHash-2-4 のテスト・ベクタを使ってコードを検証してから、 ラウンド数を落とすやりかたが早道のようです。

#include <cstdint>

std::uint64_t siphash13 (std::uint8_t const key[16], std::uint8_t const *s, std::size_t const len);

static inline void
sipround (std::uint64_t& v0, std::uint64_t& v1, std::uint64_t& v2, std::uint64_t& v3)
{
    v0 += v1;
    v1  = (v1 << 13) | (v1 >> 51);
    v1 ^= v0;
    v0  = (v0 << 32) | (v0 >> 32);
    v2 += v3;
    v3  = (v3 << 16) | (v3 >> 48);
    v3 ^= v2;
    v0 += v3;
    v3  = (v3 << 21) | (v3 >> 43);
    v3 ^= v0;
    v2 += v1;
    v1  = (v1 << 17) | (v1 >> 47);
    v1 ^= v2;
    v2  = (v2 << 32) | (v2 >> 32);
}

static inline std::uint64_t
u8to64_le(std::uint8_t const *s)
{
    return (std::uint64_t)(s[0])        | ((std::uint64_t)(s[1]) <<  8)
        | ((std::uint64_t)(s[2]) << 16) | ((std::uint64_t)(s[3]) << 24)
        | ((std::uint64_t)(s[4]) << 32) | ((std::uint64_t)(s[5]) << 40)
        | ((std::uint64_t)(s[6]) << 48) | ((std::uint64_t)(s[7]) << 56);
}

std::uint64_t
siphash13 (std::uint8_t const key[16], std::uint8_t const *s, std::size_t const len)
{
    std::uint64_t m;

    std::uint64_t k0 = u8to64_le (key);
    std::uint64_t k1 = u8to64_le (key + sizeof (std::uint64_t));

    std::uint64_t v0 = UINT64_C(0x736f6d6570736575);
    std::uint64_t v1 = UINT64_C(0x646f72616e646f6d);
    std::uint64_t v2 = UINT64_C(0x6c7967656e657261);
    std::uint64_t v3 = UINT64_C(0x7465646279746573);

    v3 ^= k1;
    v2 ^= k0;
    v1 ^= k1;
    v0 ^= k0;

    std::size_t n = len;
    for (; n >= 8; s += 8, n -= 8) {
        m = u8to64_le (s);
        v3 ^= m;
        sipround (v0, v1, v2, v3);
        //sipround (v0, v1, v2, v3);
        v0 ^= m;
    }

    std::uint64_t b = ((std::uint64_t) len) << 56;
    switch (n) {
    case 7: b ^= ((std::uint64_t)s[6]) << 48;
    case 6: b ^= ((std::uint64_t)s[5]) << 40;
    case 5: b ^= ((std::uint64_t)s[4]) << 32;
    case 4: b ^= ((std::uint64_t)s[3]) << 24;
    case 3: b ^= ((std::uint64_t)s[2]) << 16;
    case 2: b ^= ((std::uint64_t)s[1]) <<  8;
    case 1: b ^= ((std::uint64_t)s[0]);
    }
    v3 ^= b;
    sipround (v0, v1, v2, v3);
    //sipround (v0, v1, v2, v3);
    v0 ^= b;
    v2 ^= UINT64_C(0xff);
    sipround (v0, v1, v2, v3);
    sipround (v0, v1, v2, v3);
    sipround (v0, v1, v2, v3);
    //sipround (v0, v1, v2, v3);
    b = v0 ^ v1 ^ v2 ^ v3;
    return b;
}

*1:Perl5 が SipHash を使うのは 64ビット整数ビルト時のみ。