murmurbreak.cpp

#include <cstdint>
#include <cstring>
#include <cstdlib>
#include <iostream>

template<class T>
T loadword(const void* p) {
    T r;
    std::memcpy(&r, p, sizeof(r));
    return r;
}

uint64_t murmurhash64a(const char* s, size_t len, uint64_t seed) {
    static const uint64_t mul = 0xc6a4a7935bd1e995ULL;

    uint64_t hash = seed ^ (len * mul);
    for (const char* p = s; p != s + len; p += 8) {
        uint64_t data = loadword<uint64_t>(p);
        data *= mul;
        data ^= data >> 47;
        data *= mul;
        hash ^= data;
        hash *= mul;
    }

    hash ^= hash >> 47;
    hash *= mul;
    hash ^= hash >> 47;
    return hash;
}

void murmurhash64a_preimage32(uint64_t hash, char* s, uint64_t seed) {
    static const uint64_t mul = 0xc6a4a7935bd1e995ULL;
    static const uint64_t mulinv = 0x5f7a0ea7e59b19bdULL;
    
    // Invert target hash transformation.
                        // return hash;
    hash ^= hash >> 47; // hash ^= hash >> 47;
    hash *= mulinv;     // hash *= mul;
    hash ^= hash >> 47; // hash ^= hash >> 47;

    // Compute the hash state for the first 24 bytes as normal.
    uint64_t state = seed ^ (32 * mul);
    for (const char* p = s; p != s + 24; p += 8) {
        uint64_t data = loadword<uint64_t>(p);
        data *= mul;
        data ^= data >> 47;
        data *= mul;
        state ^= data;
        state *= mul;
    }
    
    // Invert last iteration for last 8 bytes.
    hash *= mulinv;                // hash *= mul;
    uint64_t data = state ^ hash;  // hash = hash ^ data;
    data *= mulinv;                // data *= mul;
    data ^= data >> 47;            // data ^= data >> 47;
    data *= mulinv;                // data *= mul;
    std::memcpy(s + 24, &data, 8); // data = loadword<uint64_t>(s);
}


int main(int argc, char** argv) {
    char input[33] = {0};
    std::strcpy(input, "orlp-murmurhash64---------------");

    for (uint64_t seed = 0; true; ++seed) {
        uint64_t s = seed; 
        for (int i = 0; i < 6; ++i) {
            input[18 + i] = 'a' + (s % 26);
            s /= 26;
        }
        if (s > 0) break;

        murmurhash64a_preimage32(1337, input, 0xc70f6907);

        bool all_printable = true;
        for (int i = 0; i < 8; ++i) {
            all_printable &= input[24 + i] >= 32;
            all_printable &= input[24 + i] <= 126;
        }

        if (all_printable) {
            std::cout << input << " " << std::hash<std::string>()(input) << "\n";
        }
    }

    return 0;
}