Last active
January 29, 2025 04:46
-
-
Save ruby0x1/81308642d0325fd386237cfa3b44785c to your computer and use it in GitHub Desktop.
FNV1a c++11 constexpr compile time hash functions, 32 and 64 bit
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#pragma once | |
#include <stdint.h> | |
//fnv1a 32 and 64 bit hash functions | |
// key is the data to hash, len is the size of the data (or how much of it to hash against) | |
// code license: public domain or equivalent | |
// post: https://notes.underscorediscovery.com/constexpr-fnv1a/ | |
inline const uint32_t hash_32_fnv1a(const void* key, const uint32_t len) { | |
const char* data = (char*)key; | |
uint32_t hash = 0x811c9dc5; | |
uint32_t prime = 0x1000193; | |
for(int i = 0; i < len; ++i) { | |
uint8_t value = data[i]; | |
hash = hash ^ value; | |
hash *= prime; | |
} | |
return hash; | |
} //hash_32_fnv1a | |
inline const uint64_t hash_64_fnv1a(const void* key, const uint64_t len) { | |
const char* data = (char*)key; | |
uint64_t hash = 0xcbf29ce484222325; | |
uint64_t prime = 0x100000001b3; | |
for(int i = 0; i < len; ++i) { | |
uint8_t value = data[i]; | |
hash = hash ^ value; | |
hash *= prime; | |
} | |
return hash; | |
} //hash_64_fnv1a |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#pragma once | |
#include <stdint.h> | |
// FNV1a c++11 constexpr compile time hash functions, 32 and 64 bit | |
// str should be a null terminated string literal, value should be left out | |
// e.g hash_32_fnv1a_const("example") | |
// code license: public domain or equivalent | |
// post: https://notes.underscorediscovery.com/constexpr-fnv1a/ | |
constexpr uint32_t val_32_const = 0x811c9dc5; | |
constexpr uint32_t prime_32_const = 0x1000193; | |
constexpr uint64_t val_64_const = 0xcbf29ce484222325; | |
constexpr uint64_t prime_64_const = 0x100000001b3; | |
inline constexpr uint32_t hash_32_fnv1a_const(const char* const str, const uint32_t value = val_32_const) noexcept { | |
return (str[0] == '\0') ? value : hash_32_fnv1a_const(&str[1], (value ^ uint32_t((uint8_t)str[0])) * prime_32_const); | |
} | |
inline constexpr uint64_t hash_64_fnv1a_const(const char* const str, const uint64_t value = val_64_const) noexcept { | |
return (str[0] == '\0') ? value : hash_64_fnv1a_const(&str[1], (value ^ uint64_t((uint8_t)str[0])) * prime_64_const); | |
} |
How would one use this to hash wstrings?
With std::wstring text = L"Hello There"
, I get different results from hash_64_fnv1a_const(L"Hello There")
and hash_64_fnv1a(text.c_str(), string.size() * 2 + 1)
.
@epicabsol
c_str()
adds a \0
byte at the end.
Actually, this code still only delivers the same result when the string is only using 7-bit ASCII when the system has a signed char (as is default on gcc/clang/msvc). The original non-constexpr code solves this issue by using uint8_t
. So there needs to be an added cast, to the the constexpr code to:
inline constexpr uint32_t hash_32_fnv1a_const(const char* const str, const uint32_t value = val_32_const) noexcept {
return (str[0] == '\0') ? value : hash_32_fnv1a_const(&str[1], (value ^ uint32_t((uint8_t)str[0])) * prime_32_const);
}
inline constexpr uint64_t hash_64_fnv1a_const(const char* const str, const uint64_t value = val_64_const) noexcept {
return (str[0] == '\0') ? value : hash_64_fnv1a_const(&str[1], (value ^ uint64_t((uint8_t)str[0])) * prime_64_const);
}
Now the results are the same for the full range of char even on a signed char system.
(edit: original was updated)
I think we can also get rid of the recursion too!
constexpr std::uint32_t hash_32_fnv1a_const2(const char* str, std::uint32_t value = val_32_const) noexcept {
for (; *str != '\0'; ++str) {
value = (value ^ static_cast<std::uint32_t>(static_cast<uint8_t>(*str))) * prime_32_const;
}
return value;
}
constexpr std::uint64_t hash_64_fnv1a_const2(const char* str, std::uint64_t value = val_64_const) noexcept {
for (; *str != '\0'; ++str) {
value = (value ^ static_cast<std::uint64_t>(static_cast<uint8_t>(*str))) * prime_64_const;
}
return value;
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Is there any license on this code? I would love to use this in a little graphics demo that I am building. It's for a non-commercial purpose, just for fun and learning :).