Skip to content

Instantly share code, notes, and snippets.

@neudinger

neudinger/main.cpp

Last active May 30, 2024 15:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save neudinger/97a75228381e12d4ba2b435c3b86ba9e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save neudinger/97a75228381e12d4ba2b435c3b86ba9e to your computer and use it in GitHub Desktop.
Download ZIP
murmur3 32 et 128 bits Compile time and runtime hash C++20 templatized constexpr function (CTFE, CRTP, SFINAE, concept, constexpr)
Raw
main.cpp
#include <string_view>
#include <iostream>
#include <bit>
#include <bitset>
#include "murmur3.hpp"
// Will Create 2 overloaded operator ""
// With
_MURMURHASH3_128(42)
_MURMURHASH3_32(42)
using namespace std::string_view_literals;
using namespace std::literals;
// g++ -O3 -std=c++20 main.cc && ./a.out
int main(int argc, char const *argv[])
{
auto &&[v1, v2]{MurmurHash3(/* key= */ "The Key to be hashed",
/* seed= */ ((111UL) << 62UL))};
std::cout << "v1 " << v1 << std::endl;
auto &&v{MurmurHash3(/* key= */ "The Key to be hashed",
/* seed= */ ((111U) << 10))};
std::cout << "v " << v << std::endl;
std::cout << MurmurHash3(/* key= */ "The Key to be hashed"sv,
/* seed= */ ((111U) << 10))
<< std::endl;
switch (MurmurHash3("The Key to be hashed"sv, 0UL)[0])
{
case "The Key to be hashed"_MurmurHash3_128[0]:
std::cout << " _MurmurHash3_128 1" << std::endl;
break;
case "The Key to be hashed"_MurmurHash3_128[1]:
std::cout << " _MurmurHash3_128 2" << std::endl;
break;
// case "The Key to be hashed"_MurmurHash3_128_0[0]:
// break;
default:
break;
}
switch (MurmurHash3("The Key to be hashed", 0U))
{
case "The Key to be hashed"_MurmurHash3_32:
std::cout << " _MurmurHash3_32 1" << std::endl;
break;
case "The Key to be hashed 2"_MurmurHash3_32:
std::cout << " _MurmurHash3_32 2" << std::endl;
break;
// case "The Key to be hashed"_MurmurHash3_32_0:
// break;
default:
break;
}
std::cout << "The Key to be hashed"_MurmurHash3_32_42 << std::endl;
for (auto &&value : "The Key to be hashed"_MurmurHash3_128_42)
std::cout << value << ' ';
std::cout << std::endl;
return "OK"_MurmurHash3_32;
}
Raw
murmur3.hpp
#pragma once
#ifndef MURMUR3_HPP
#define MURMUR3_HPP
#include <cstdint>
#include <string_view>
#include <ranges>
// https://en.wikipedia.org/wiki/Compile-time_function_execution
// https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern
// https://en.cppreference.com/w/cpp/language/sfinae
// https://en.cppreference.com/w/cpp/language/attributes
// https://gcc.gnu.org/onlinedocs/gcc/Attribute-Syntax.html
// https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html
// https://clang.llvm.org/docs/AttributeReference.html
#define force_inline inline __attribute__((always_inline))
[[using gnu: always_inline, pure, hot]] static constexpr force_inline
uint32_t
finalization_mix(uint32_t h) noexcept
{
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;
return h;
}
[[using gnu: always_inline, pure, hot]] static constexpr force_inline
uint64_t
finalization_mix(uint64_t k) noexcept
{
k ^= k >> 33;
k *= 0xff51afd7ed558ccdUL;
k ^= k >> 33;
k *= 0xc4ceb9fe1a85ec53UL;
k ^= k >> 33;
return k;
}
[[using gnu: always_inline, pure, hot, access(read_only, 1)]] static constexpr force_inline
uint64_t
get_stride(std::string_view const &str,
uint64_t idx) noexcept
{
uint64_t k1 = str[idx + 7];
k1 <<= 8;
k1 ^= str[idx + 6];
k1 <<= 8;
k1 ^= str[idx + 5];
k1 <<= 8;
k1 ^= str[idx + 4];
k1 <<= 8;
k1 ^= str[idx + 3];
k1 <<= 8;
k1 ^= str[idx + 2];
k1 <<= 8;
k1 ^= str[idx + 1];
k1 <<= 8;
k1 ^= str[idx + 0];
return k1;
}
[[using gnu: always_inline, pure, hot, access(read_only, 1)]] static constexpr force_inline
uint32_t
get_stride(std::string_view const &str,
uint32_t idx) noexcept
{
uint32_t k1 = str[idx + 3];
k1 <<= 8;
k1 ^= str[idx + 2];
k1 <<= 8;
k1 ^= str[idx + 1];
k1 <<= 8;
k1 ^= str[idx + 0];
return k1;
}
[[using gnu: always_inline, pure, hot, access(read_only, 1)]] force_inline constexpr uint32_t
MurmurHash3(std::string_view const &str,
uint32_t seed) noexcept
{
constexpr uint32_t c1 = 0xcc9e2d51,
c2 = 0x1b873593;
uint32_t h1{seed};
uint32_t const block_size{uint32_t(str.size()) / 4U};
for (auto block_size_id : std::ranges::iota_view{0U, block_size})
{
block_size_id *= 4;
uint32_t k1{get_stride(str, block_size_id)};
k1 *= c1;
k1 = std::rotl(k1, 15);
k1 *= c2;
h1 ^= k1;
h1 = std::rotl(h1, 13);
h1 = h1 * 5 + 0xe6546b64;
}
uint32_t k1{};
switch (str.size() & 3)
{
case 3:
k1 ^= str[block_size * 4 + 2] << 16;
[[fallthrough]];
case 2:
k1 ^= str[block_size * 4 + 1] << 8;
[[fallthrough]];
case 1:
k1 ^= str[block_size * 4 + 0];
k1 *= c1;
k1 = std::rotl(k1, 15);
k1 *= c2;
h1 ^= k1;
};
h1 ^= str.size();
h1 = finalization_mix(h1);
return h1;
}
[[using gnu: always_inline, pure, hot, access(read_only, 1)]] force_inline constexpr std::array<uint64_t, 2> MurmurHash3(std::string_view const &str, uint64_t seed) noexcept
{
constexpr uint64_t c1{0x87c37b91114253d5ULL}, c2{0x4cf5ad432745937fULL};
uint64_t h1 = seed,
h2 = seed;
auto const block_size{str.size() / 16UL};
for (auto block_size_id : std::ranges::iota_view{0UL, block_size})
{
block_size_id *= 2;
uint64_t k1{get_stride(str, block_size_id)};
block_size_id += sizeof(uint64_t);
uint64_t k2{get_stride(str, block_size_id)};
k1 *= c1;
k1 = std::rotl(k1, 31UL);
k1 *= c2;
h1 ^= k1;
h1 = std::rotl(h1, 27UL);
h1 += h2;
h1 = h1 * 5 + 0x52dce729;
k2 *= c2;
k2 = std::rotl(k2, 33UL);
k2 *= c1;
h2 ^= k2;
h2 = std::rotl(h2, 31UL);
h2 += h1;
h2 = h2 * 5 + 0x38495ab5;
}
uint64_t k1{}, k2{};
auto last_stride_idx{block_size * 16UL};
switch (str.size() & 15)
{
case 15:
k2 ^= uint64_t(str[last_stride_idx + 14]) << 48;
[[fallthrough]];
case 14:
k2 ^= uint64_t(str[last_stride_idx + 13]) << 40;
[[fallthrough]];
case 13:
k2 ^= uint64_t(str[last_stride_idx + 12]) << 32;
[[fallthrough]];
case 12:
k2 ^= uint64_t(str[last_stride_idx + 11]) << 24;
[[fallthrough]];
case 11:
k2 ^= uint64_t(str[last_stride_idx + 10]) << 16;
[[fallthrough]];
case 10:
k2 ^= uint64_t(str[last_stride_idx + 9]) << 8;
[[fallthrough]];
case 9:
k2 ^= uint64_t(str[last_stride_idx + 8]) << 0;
k2 *= c2;
k2 = std::rotl(k2, 33UL);
k2 *= c1;
h2 ^= k2;
[[fallthrough]];
case 8:
k1 ^= uint64_t(str[last_stride_idx + 7]) << 56;
[[fallthrough]];
case 7:
k1 ^= uint64_t(str[last_stride_idx + 6]) << 48;
[[fallthrough]];
case 6:
k1 ^= uint64_t(str[last_stride_idx + 5]) << 40;
[[fallthrough]];
case 5:
k1 ^= uint64_t(str[last_stride_idx + 4]) << 32;
[[fallthrough]];
case 4:
k1 ^= uint64_t(str[last_stride_idx + 3]) << 24;
[[fallthrough]];
case 3:
k1 ^= uint64_t(str[last_stride_idx + 2]) << 16;
[[fallthrough]];
case 2:
k1 ^= uint64_t(str[last_stride_idx + 1]) << 8;
[[fallthrough]];
case 1:
k1 ^= uint64_t(str[last_stride_idx + 0]) << 0;
k1 *= c1;
k1 = std::rotl(k1, 31UL);
k1 *= c2;
h1 ^= k1;
default:
break;
};
//----------
// finalization
h1 ^= str.size();
h2 ^= str.size();
h1 += h2;
h2 += h1;
h1 = finalization_mix(h1);
h2 = finalization_mix(h2);
h1 += h2;
h2 += h1;
return std::array<uint64_t, 2>{h1, h2};
}
force_inline constexpr uint32_t
operator""_MurmurHash3_32(char const *str, size_t len) noexcept
{
return MurmurHash3(std::string_view(str, len), 0U);
}
force_inline constexpr std::array<uint64_t, 2>
operator""_MurmurHash3_128(char const *str, size_t len) noexcept
{
return MurmurHash3(std::string_view(str, len), 0UL);
}
#define _MURMURHASH3_128(seed) \
inline constexpr std::array<uint64_t, 2> \
operator""_MurmurHash3_128_##seed(char const *str, size_t len) noexcept \
{ \
return MurmurHash3(std::string_view(str, len), seed##UL); \
}
#define _MURMURHASH3_32(seed) \
inline constexpr uint32_t \
operator""_MurmurHash3_32_##seed(char const *str, size_t len) noexcept \
{ \
return MurmurHash3(std::string_view(str, len), seed##U); \
}
_MURMURHASH3_128(1010)
_MURMURHASH3_32(1010)
_MURMURHASH3_128(0)
_MURMURHASH3_32(0)
#endif /* MURMUR3_HPP */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment