2
$\begingroup$

An alternative version of FNV-1a hash spread on the internet, which operates directly on integers instead of bytes. The offset basis and prime are the same used in the original version, which operates on bytes.

With this version, is the statistical quality of the produced hash similar to the original algorithm?

Alternative version operating on integers:

#include <cstdint>

#define OFFSET_BASIS 2166136261ul
#define FNV_PRIME 16777619ul

uint32_t hash(uint32_t i, uint32_t j, uint32_t k) 
{ 
   return ((((((OFFSET_BASIS ^ i) * FNV_PRIME) ^ j) * FNV_PRIME) ^ k) * FNV_PRIME); 
}

Original version operating on bytes:

#include <cstdint>

#define OFFSET_BASIS 2166136261ul
#define FNV_PRIME 16777619ul

uint32_t hash(char* data, size_t bytes)
{
   uint32_t h = OFFSET_BASIS;

   for (size_t i = 0; i < bytes; ++i)
   {
      h = (h ^ data[i]) * FNV_PRIME;
   }

   return h;
}
$\endgroup$
4
$\begingroup$

It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing.

The core step that offers mixing of the bits is multiplication by FNV_PRIME modulo $2^{32}$. The original version (operating on bytes) does this once for each byte of the input. The alternative version (operating on integers) does this once for each integer, i.e., once for each four bytes. Thus, the alternative version does only one-fourth as many of these mixing operations.

For these reasons, I anticipate that the alternative version will provide poorer mixing of the bits and might offer poorer statistical properties or weaker collision resistance.

For instance, here is one weakness of the alternative version that isn't present in the original version. Suppose you simultaneously flip the high bit of i and j. Then it turns out that the output (the hash value) will remain unchanged, with the alternative version. This is a weakness in a hash function. The original version doesn't have this weakness: there's no simple set of bit flips you can do to the input that will have a similar effect. This is a result of the fact that the alternative version only does the multiplication-based mixing one-fourth as much as the original version.

Now, don't take this the wrong way. This doesn't necessarily mean that the alternative version is flawed or useless. The alternative version might still be good enough for applications; that will depend on the distribution of integers that you hash and the needs of the particular application. But you can't make an equivalence argument that it's "just as good" as the original version.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.