src/util/murmur3.cpp - master - smychkov/SStorage

src/util/murmur3.cpp
81 строка3 KB
Андрей Смычков
feat: util varint, crc32c, murmur3, compression (snappy)
25 апр 2026, 09:00
25 апр 2026, 09:00a7cf584
#include "murmur3.hpp"
#include <cstring>

namespace sstorage {
namespace util {

//============================================================================
// MurmurHash3_x86_32 — стандартная реализация
//============================================================================
// Магические константы подобраны экспериментально автором.
// Проверено на SMHasher — хорошее распределение битов.
//============================================================================

namespace {

// Ротация влево 32-битного числа
inline uint32_t rotl32(uint32_t x, int8_t r) {
    return (x << r) | (x >> (32 - r));
}

// Финализация хэша — смешивание битов для uniformity
inline uint32_t fmix32(uint32_t h) {
    h ^= h >> 16;
    h *= 0x85EBCA6B;
    h ^= h >> 13;
    h *= 0xC2B2AE35;
    h ^= h >> 16;
    return h;
}

}

uint32_t murmur3(const char* data, size_t len, uint32_t seed) {
    const uint8_t* bytes = reinterpret_cast<const uint8_t*>(data);
    const size_t nblocks = len / 4;
    uint32_t h1 = seed;

    // Магические константы MurmurHash3
    constexpr uint32_t c1 = 0xCC9E2D51;
    constexpr uint32_t c2 = 0x1B873593;

    //------------------------------------------------------------------------
    // Основной цикл: обрабатываем по 4 байта (блок)
    //------------------------------------------------------------------------
    for (size_t i = 0; i < nblocks; ++i) {
        uint32_t k1;
        std::memcpy(&k1, bytes + i * 4, sizeof(k1));

        k1 *= c1;
        k1 = rotl32(k1, 15);
        k1 *= c2;

        h1 ^= k1;
        h1 = rotl32(h1, 13);
        h1 = h1 * 5 + 0xE6546B64;
    }

    //------------------------------------------------------------------------
    // Обработка хвоста (0-3 байта, не вошедших в блоки)
    //------------------------------------------------------------------------
    const uint8_t* tail = bytes + nblocks * 4;
    uint32_t k1 = 0;
    switch (len & 3) {
        case 3: k1 ^= static_cast<uint32_t>(tail[2]) << 16; [[fallthrough]];
        case 2: k1 ^= static_cast<uint32_t>(tail[1]) << 8;  [[fallthrough]];
        case 1: k1 ^= static_cast<uint32_t>(tail[0]);
                k1 *= c1;
                k1 = rotl32(k1, 15);
                k1 *= c2;
                h1 ^= k1;
    }

    //------------------------------------------------------------------------
    // Финализация: добавляем длину и смешиваем биты
    //------------------------------------------------------------------------
    h1 ^= static_cast<uint32_t>(len);
    return fmix32(h1);
}

}
}