Murmur3 Hash als constexpr

MrSandman

Hallo zusammen!

ich versuche jetzt schon seit einer gefühlten Ewigkeit den Murmur3 Hash Algorithmus in C++11 als constant expression zu implementieren. Das ist mir auch halbwegs gelungen. Also, es ist eine gültige constexpr und die Hashes stimmen weitestgehend mit der Referenzimplementierung überein. Nur wenn ich negative Werte in meinem Key habe, stimmt meine Implementierung nicht mit der Referenz überein. "Wert" heisst in diesem Fall char. Meine Implementation nimmt const char* als Key. Wenn einer davon negativ ist (weil man zum Beispiel UTF8 benutzt oder halt einen beliebigen Blob in const char* convertiert hat) kommt es zu den Unstimmigkeiten. Mir ist es zum ersten mal aufgefallen, als ich das Zeichen "§" in einem String hatte, welches kein ASCII-Zeichen ist und von meiner IDE als zwei negative Zeichen codiert wurde. Ich habe das dann mal getestet (chars mit Werten von -128 bis 127) und alle negativen Werte passen nicht. Ich habe den Code jetzt schon was-weiss-ich-wie-oft durchgepflügt und durch den Debugger gejagt aber mir gehen so langsam echt die Ideen aus. Vielleicht hat ja einer von euch eine Idee oder hat Lust auf eine Herausforderung!

Der Code ist leider etwas schwer zu lesen, weil ich durch die Einschränkungen die für constant expressions gelten in fast reinem funktionalen Stil programmieren musste und auch durch ein paar andere Reifen springen musste. Falls jemand Vorschläge hat die Leserlichkeit zu verbessern bin ich ganz Ohr, aber constant expressions sind extrem eingeschränkt was die legale Syntax angeht.

Das hier ist die Referenz:
https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp

und das hier ist mein Code:

#include <cstdint>
#include <string>
#include <cstring>

// can calculate hashes of strings at run- and compile time.
// use only for ASCII characters!
class StringHash {
public:
    constexpr StringHash(const char* string) : value(hash(string)){}
    constexpr StringHash(StringHash& other) : value(other.value){}
    constexpr StringHash(StringHash&& other) : value(other.value){}

    bool operator == (StringHash& other) {
        return this->value == other.value;
    }

    bool operator == (StringHash&& other) {
        return this->value == other.value;
    }

    bool operator != (StringHash& other) {
        return this->value != other.value;
    }

    bool operator != (StringHash&& other) {
        return this->value != other.value;
    }

    constexpr inline static uint32_t hash(const char* string) {
        return murmur3(string, strlen(string), seed);
    }

    const uint32_t value;
    static const uint32_t seed = 0xB0F57EE3;

private:
    static const uint32_t c1 = 0xcc9e2d51;
    static const uint32_t c2 = 0x1b873593;

    constexpr inline static uint32_t _add(const uint32_t x, const int add) {
        return x + add;
    }

    constexpr inline static uint32_t _mult(const uint32_t x, const int mult) {
        return x * mult;
    }

    constexpr inline static uint32_t _xor(const uint32_t lhs, const int rhs) {
        return lhs ^ rhs;
    }

    constexpr inline static uint32_t _downshift_xor(const uint32_t x, const int downshift) {
        return x ^ (x >> downshift);
    }

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

    constexpr inline static uint32_t _fmix32(const uint32_t x) {
        return _downshift_xor(
                    _mult(
                        _downshift_xor(
                            _mult(
                                _downshift_xor(x, 16),
                                0x85ebca6b),
                            13),
                        0xc2b2ae35),
                    16);
    }

    // get blocks in 32bit increments
    constexpr inline static uint32_t _getblock32 ( const char* p, const int i ) {
        return uint32_t(p[i*4+0])
                | uint32_t(p[i*4+1]) << 8
                | uint32_t(p[i*4+2]) << 16
                | uint32_t(p[i*4+3]) << 24;
    }

    constexpr inline static uint32_t _body(uint32_t x, const uint32_t block) {
        return _add(
                    _mult(
                          _rotl32(
                                  _xor(x,
                                       _mult(
                                             _rotl32(
                                                     _mult(
                                                           block,
                                                           c1),
                                                     15),
                                             c2)
                                       ),
                                  13),
                          5),
                    0xe6546b64);
    }

    constexpr inline static uint32_t _body_rec(uint32_t x, const char * blocks, int i) {
        return ((i < 0) ? _body_rec(_body(x, _getblock32(blocks, i)), blocks, i + 1) : x);
    }

    constexpr inline static uint32_t _tail1(uint32_t x, const char * tail) {
        return _mult(
                     _rotl32(
                             _mult(
                                   _xor(x,
                                        tail[0]),
                                   c1),
                             15),
                     c2);
    }

    constexpr inline static uint32_t _tail(uint32_t x, const char * tail, const int len) {
        return ((len & 3) == 3) ? _xor(
                                       x,
                                       _tail1(
                                              _xor(tail[2] << 16,
                                                   tail[1] << 8),
                                              tail))
                                : ((len & 3) == 2) ? _xor(
                                                         x,
                                                         _tail1(
                                                                tail[1] << 8,
                                                                tail))
                                                   : ((len & 3) == 1) ? _xor(
                                                                             x,
                                                                             _tail1(
                                                                                    0,
                                                                                    tail))
                                                                      : x;
    }

    constexpr inline static uint32_t _final(uint32_t tail, const int len) {
        return _fmix32(_xor(tail, len));
    }

    constexpr inline static uint32_t murmur3(const char *key, const int len, uint32_t seed) {
        return _final(
                      _tail(
                            _body_rec(seed,
                                      (key + (len/4)*4),
                                      -1*(len/4)),
                            (key + ((len/4)*4)),
                            len),
                      len);
    }
};

constexpr uint32_t operator "" _h(const char* str, size_t len)
{
    return StringHash(str).value;
}

Ist mit C++14 obsolet.

MrSandman

Warum das denn? C++ hebt zwar einige Einschränkungen auf (Loops, zum Beispiel), aber Casts sind zum Beispiel immer noch nicht erlaubt. Und unter Windows habe ich noch keinen C++14 Compiler. Selbst der GCC 4.9 ist noch nicht voll C++14 kompatibel. Aber ich stimme zu, mit C++14 wäre es lesbarer. Werde das bei Gelegenheit mal umschreiben, ich compilieren den Code für's erste sowieso hauptsächlich mit Clang, der ist schon vollständig kompatibel mit C++14.