murmur3break.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;
}

uint32_t rotl32(uint32_t x, int r) {
    return (x << r) | (x >> (32 - r));
}

uint32_t murmurhash3_x86_32(const char* s, int len, uint32_t seed) {
    const uint32_t c1 = 0xcc9e2d51;
    const uint32_t c2 = 0x1b873593;
    const uint32_t c3 = 0x85ebca6b;
    const uint32_t c4 = 0xc2b2ae35;

    uint32_t h = seed;
    for (const char* p = s; p != s + len; p += 4) {
        uint32_t k = loadword<uint32_t>(p);
        k *= c1;
        k = rotl32(k, 15);
        k *= c2;

        h ^= k;
        h = rotl32(h, 13);
        h = h * 5 + 0xe6546b64;
    }

    h ^= len;
    h ^= h >> 16;
    h *= c3;
    h ^= h >> 13;
    h *= c4;
    h ^= h >> 16;
    return h;
} 

void murmurhash_x86_32_preimage32(uint32_t hash, char* s, uint32_t seed) {
    const uint32_t c1 = 0xcc9e2d51;
    const uint32_t c2 = 0x1b873593;
    const uint32_t c3 = 0x85ebca6b;
    const uint32_t c4 = 0xc2b2ae35;
    const uint32_t c1inv = 0xdee13bb1;
    const uint32_t c2inv = 0x56ed309b;
    const uint32_t c3inv = 0xa5cb9243;
    const uint32_t c4inv = 0x7ed1b41d;
    const uint32_t fiveinv = 0xcccccccd;
    
    // Invert target hash transformation.
    uint32_t h = hash;
    h ^= h >> 16;
    h *= c4inv;
    h ^= h >> 13;
    h ^= h >> 26;
    h *= c3inv;
    h ^= h >> 16;
    h ^= 32;

    // Compute the hash state for the first 24 bytes as normal.
    uint32_t state = seed;
    for (const char* p = s; p != s + 28; p += 4) {
        uint32_t k = loadword<uint32_t>(p);
        k *= c1;
        k = rotl32(k, 15);
        k *= c2;

        state ^= k;
        state = rotl32(state, 13);
        state = state * 5 + 0xe6546b64;
    }
    
    // Invert last iteration for last 4 bytes.
    h -= 0xe6546b64;
    h *= fiveinv;
    h = rotl32(h, 19);
    h ^= state;

    h *= c2inv;
    h = rotl32(h, 17);
    h *= c1inv;
    std::memcpy(s + 28, &h, 4);
}


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

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

        murmurhash_x86_32_preimage32(1337, input, 0);

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

        if (all_printable) {
            std::cout << input << " " << murmurhash3_x86_32(input, 32, 0) << "\n";
        }
    }

    return 0;
}