I'm trying to find a constexpr compatible hash function to use for hashing strings in compile-time. The number of strings are really small (<10) and I have a separate check for collisions, so the algorithm can be far from perfect. I found the following version of FNV1A somewhere on the internet:
static constexpr unsigned int Fnv1aBasis = 0x811C9DC5;
static constexpr unsigned int Fnv1aPrime = 0x01000193;
constexpr unsigned int hashFnv1a(const char *s, unsigned int h = Fnv1aBasis)
{
return !*s ? h : hashFnv1a(s + 1, (h ^ *s) * Fnv1aPrime);
}
But when I compile this in MSVS 2015 I get the following warning:
warning C4307: '*': integral constant overflow
Since there's only one multiplication in the function I would assume the warning comes from (h ^ *s) * Fnv1aPrime
. It makes sense since multiplying 0x811C9DC5
(Fnv1aBasis
) with just about anything will make a 32-bit integer overflow.
Is there any way to work around this? I've tried a couple of other constexpr functions I've found for hashing strings, but all of them have the same issue.
If you don't mind the overflow then just silence the warning. Unsigned integer arithmetic is guaranteed to be modulo 2n arithmetic where n is the number of bits in the value representation, so this is well-defined no matter what. The warning is a sillywarning; it's warning you that you're using the main feature of unsigned integers.
I find that with a local #pragma warning( disable: 4307 )
for the function, the warning still appears for every use of the function.
This rewrite silences the warning for the 32-bit hash function:
constexpr auto hashFnv1a( char const* s, unsigned h = Fnv1aBasis )
-> unsigned
{
return !*s ? h : hashFnv1a(s + 1, static_cast<unsigned>( 1ULL*(h ^ *s) * Fnv1aPrime ));
}
Even extensive googling didn't find any way to disable the sillywarning about overflow of unsigned values while leaving it on for signed ones, so to deal with the 64-bit hash function it appears that the only recourse is to implement a constexpr
64-bit unsigned multiplication function. Since it's constexpr
it doesn't matter if it's particularly efficient or not. So:
#include <stdint.h>
namespace b32 {
static constexpr uint32_t Fnv1aBasis = 0x811C9DC5u;
static constexpr uint32_t Fnv1aPrime = 0x01000193u;
constexpr auto hashFnv1a( char const* s, uint32_t h = Fnv1aBasis )
-> uint32_t
{ return !*s ? h : hashFnv1a(s + 1, static_cast<uint32_t>( 1ULL*(h ^ *s)*Fnv1aPrime )); }
} // namespace b32
namespace b64 {
static constexpr uint64_t Fnv1aBasis = 0xCBF29CE484222325uLL;
static constexpr uint64_t Fnv1aPrime = 0x100000001B3uLL;
constexpr auto lo( uint64_t x )
-> uint64_t
{ return x & uint32_t( -1 ); }
constexpr auto hi( uint64_t x )
-> uint64_t
{ return x >> 32; }
constexpr auto mulu64( uint64_t a, uint64_t b )
-> uint64_t
{
return 0
+ (lo( a )*lo( b ) & uint32_t(-1))
+ (
(
(
(
(
hi( lo( a )*lo( b ) ) +
lo( a )*hi( b )
)
& uint32_t(-1)
)
+ hi( a )*lo( b )
)
& uint32_t(-1)
)
<< 32
);
}
constexpr auto hashFnv1a( char const* s, uint64_t h = Fnv1aBasis )
-> uint64_t
{ return !*s ? h : hashFnv1a( s + 1, mulu64( h ^ *s, Fnv1aPrime ) ); }
} // namepace b64
#include <assert.h>
#include <iostream>
using namespace std;
auto main()
-> int
{
constexpr auto x = b64::mulu64( b64::Fnv1aBasis, b64::Fnv1aPrime );
#ifdef _MSC_VER
# pragma warning( push )
# pragma warning( disable: 4307 )
constexpr auto y = b64::Fnv1aBasis*b64::Fnv1aPrime;
# pragma warning( pop )
#else
constexpr auto y = b64::Fnv1aBasis*b64::Fnv1aPrime;
#endif
cout << x << endl;
cout << y << endl;
assert( x == y );
static constexpr const char* const s = "blah!";
constexpr unsigned xs = b32::hashFnv1a( s );
constexpr uint64_t ys = b64::hashFnv1a( s );
int a[1 + xs%2]; (void) a;
int b[1 + ys%2]; (void) b;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With