Objective-C : Fowler–Noll–Vo (FNV) Hash implementation

Question

I have a HTTP connector in my iPhone project and queries must have a parameter set from the username using the Fowler–Noll–Vo (FNV) Hash.

I have a Java implementation working at this time, this is the code :

long fnv_prime = 0x811C9DC5;
long hash = 0;

for(int i = 0; i < str.length(); i++)
{
    hash *= fnv_prime;
    hash ^= str.charAt(i);
}

Now on the iPhone side, I did this :

int64_t fnv_prime = 0x811C9DC5;
int64_T hash = 0;

for (int i=0; i < [myString length]; i++)
{
    hash *= fnv_prime;
    hash ^= [myString characterAtIndex:i];
}

This script doesn't give me the same result has the Java one.

In first loop, I get this :

hash = 0

hash = 100 (first letter is "d")

hash = 1865261300 (for hash = 100 and fnv_prime = -2128831035 like in Java)

Do someone see something I'm missing ?

Thanks in advance for the help !

Answer 1

In Java, this line:

long fnv_prime = 0x811C9DC5;

will yield in fnv_prime the numerical value -2128831035, because the constant is interpreted as an int, which is a 32-bit signed value in Java. That value is then sign-extended when written in a long.

Conversely, in the Objective-C code:

int64_t fnv_prime = 0x811C9DC5;

the 0x811C9DC5 is interpreted as an unsigned int constant (because it does not fit in a signed 32-bit int), with numerical value 2166136261. That value is then written into fnv_prime, and there is no sign to extend since, as far as the C compiler is concerned, the value is positive.

Thus you end up with distinct values for fnv_prime, which explains your distinct results.

This can be corrected in Java by adding a "L" suffix, like this:

long fnv_prime = 0x811C9DC5L;

which forces the Java compiler to interpret the constant as a long, with the same numerical value than what you get with the Objective-C code.

Answer 2

Incidentally, 0x811C9DC5 is not a FNV prime (it is not even prime); it is the 32 bit FNV "offset basis". You will get incorrect hash values if you use this value (and more hash collisions). The correct value for the 32 bit FNV prime is 0x1000193. See http://www.isthe.com/chongo/tech/comp/fnv/index.html