Skip to content

Instantly share code, notes, and snippets.

@neudinger

neudinger/FNV1a.hpp

Last active November 24, 2025 21:11
Show Gist options

  • Select an option

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

Select an option

Learn more about clone URLs
Save neudinger/4921e8cf323b2be544982e8b5968cd57 to your computer and use it in GitHub Desktop.
Download ZIP
Fowler–Noll–Vo (or FNV) Compile time and runtime hash C++20 templatized constexpr function (CTFE, CRTP, SFINAE, concept, constexpr)
Raw
FNV1a.hpp
#pragma once
#ifndef FNV1a_HPP
#define FNV1a_HPP
// From https://gist.github.com/neudinger/4921e8cf323b2be544982e8b5968cd57
#include <unistd.h>
#include <string_view>
#include <cstdint> // uint8_t, uint16_t, uint64_t
#include <type_traits>
#include <cassert>
// The FNV-1 hash parameters are as follows:
// hash is an n bit unsigned integer, where n is the bit length of hash.
// The multiplication is performed modulo 2n where n is the bit length of hash.
// The xor is performed on the low order octet (8 bits) of hash.
// The FNV_prime is dependent on n, the size of the hash:
// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV_hash_parameters
// 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))
template <typename T>
concept StringLike = std::is_convertible_v<T, std::string_view>;
template <typename T, typename... U>
concept IsAnyOf = (std::same_as<T, U> or ...);
template <typename TYPE>
concept DOMAIN_TYPE = IsAnyOf<TYPE, uint32_t, uint64_t>;
template <DOMAIN_TYPE HASH_TYPE>
static constexpr HASH_TYPE offset() noexcept
{
if constexpr (std::is_same_v<HASH_TYPE, uint32_t>)
return HASH_TYPE{0x811c9dc5U};
if constexpr (std::is_same_v<HASH_TYPE, uint64_t>)
return HASH_TYPE{0xcbf29ce484222325UL};
}
template <DOMAIN_TYPE HASH_TYPE>
static constexpr HASH_TYPE prime() noexcept
{
if constexpr (std::is_same_v<HASH_TYPE, uint32_t>)
return HASH_TYPE{0x01000193U};
if constexpr (std::is_same_v<HASH_TYPE, uint64_t>)
return HASH_TYPE{0x00000100000001B3UL};
}
template <DOMAIN_TYPE HASH_TYPE = uint32_t, StringLike Str>
[[using gnu: always_inline, pure, hot, access(read_only, 1)]] static constexpr force_inline
HASH_TYPE
FNV1a(Str const &toHash) noexcept
{
static_assert(sizeof(uint32_t) == sizeof(HASH_TYPE) or
sizeof(uint64_t) == sizeof(HASH_TYPE));
HASH_TYPE _basis{offset<HASH_TYPE>()};
assert(_basis > 0 && "Offset FNV1a must be positive");
[[assume(_basis > 0)]];
constexpr HASH_TYPE const _prime{prime<HASH_TYPE>()};
assert(_prime > 0 && "Prime number are alway positive");
[[assume(_prime > 0)]];
for (char const &low_order_octet : std::string_view(toHash))
{
_basis ^= static_cast<HASH_TYPE>(low_order_octet);
_basis *= _prime;
}
return _basis;
}
template <uint8_t SIZE, StringLike Str>
struct [[nodiscard]] FNV1a_impl;
template <uint8_t SIZE, StringLike Str>
static inline constexpr auto FNV1a(Str const &toHash) noexcept
{
return FNV1a_impl<SIZE, Str>::_(toHash);
}
template <StringLike Str>
struct [[nodiscard]] FNV1a_impl<32, Str>
{
static inline constexpr auto _(Str const &toHash) noexcept
{
return FNV1a<uint32_t>(toHash);
}
};
template <StringLike Str>
struct [[nodiscard]] FNV1a_impl<64, Str>
{
static inline constexpr auto _(Str const &toHash) noexcept
{
return FNV1a<uint64_t>(toHash);
}
};
inline constexpr auto
operator""_FNV1a_64(char const *__str, size_t __len) noexcept
{
return FNV1a<uint64_t>(std::string_view(__str, __len));
}
inline constexpr auto
operator""_FNV1a_32(char const *__str, size_t __len) noexcept
{
[[assume(__len > 0)]];
return FNV1a<uint32_t>(std::string_view(__str, __len));
}
inline constexpr auto
operator""_FNV1a(char const *__str, size_t __len) noexcept
{
return FNV1a(std::string_view(__str, __len));
}
#endif /* FNV1a_HPP */
Raw
main.cpp
auto main(int /* argc */, char const* /* argv */[]) -> int {
std::string const data("data");
/* -------------------- FNV1a<32> -------------------- */
std::println("{} is FNV1a {} at run time with uint32_t by default", data,
kbhash::FNV1a(data));
std::println("{} is FNV1a {} at run time with uint32_t by default", data,
kbhash::FNV1a<kbhash::bytesize_32>(data));
std::println("{} is FNV1a {} at compile time", data,
kbhash::FNV1a<kbhash::bytesize_32>("data"));
std::println("{} is FNV1a {} at compile time", data,
kbhash::FNV1a<uint32_t>("data"sv));
std::println("{} is FNV1a {} at compile time", data,
kbhash::FNV1a<uint32_t>("data"));
std::println("{} is FNV1a {} at compile time", data, "data"_FNV1a_32);
/* -------------------- FNV1a<64> -------------------- */
std::println("{} is FNV1a {} at run time", data,
kbhash::FNV1a<uint64_t>(data));
std::println("{} is FNV1a {} at run time", data,
kbhash::FNV1a<kbhash::bytesize_64>(data));
std::println("{} is FNV1a {} at compile time", data,
kbhash::FNV1a<kbhash::bytesize_64>("data"));
std::println("{} is FNV1a {} at compile time", data,
kbhash::FNV1a<uint64_t>("data"));
std::println("{} is FNV1a {} at compile time", data, "data"_FNV1a_64);
/* */
std::string const color("blue");
/* ------------- FNV1a<32> with SFINAE HASH FUNCTION ----------- */
// FNV1a is a hash function that is designed to be fast and simple.
// It is a non-cryptographic hash function that is designed to be
// very fast and simple to compute.
// Without anny template parameter, the default is uint32_t
switch (kbhash::FNV1a(color)) {
// inside the switch statement, you can use the hash function
// to compute the hash of the string, with the literal operator
case "blue"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
case "red"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
case "green"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
case "yellow"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
case "black"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
case "white"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
case "orange"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
case "purple"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
case "pink"_FNV1a_32: {
std::println("Case handled is {} With FNV1a_32", color);
} break;
default: {
std::println("Sorry the color {} is not supported", color);
} break;
}
/* ------------- FNV1a<64> with SFINAE HASH FUNCTION ----------- */
// With a template parameter, you can specify the size of the hash
// function to use. The default is uint32_t but you can also use
// uint64_t or the number 64.
switch (kbhash::FNV1a<uint64_t>(color)) {
// inside the switch statement, you can use the hash function
// to compute the hash of the string, with the literal operator
// ""_FNV1a_64
case "blue"_FNV1a_64: {
std::println("Case handled is {} With FNV1a_64", color);
} break;
case "red"_FNV1a_64: {
std::println("Case handled is {} With FNV1a_64", color);
} break;
default: {
std::println("Sorry the collor {} is not supported", color);
} break;
}
return EXIT_SUCCESS;
}
@neudinger
Copy link
Author

neudinger commented Mar 15, 2024

g++ -std=c++20 main.cc && ./a.out

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment