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

Question

Hi !

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

Are the characters in Java and Objective-c the same? NSString will give you unichars.

Answer 2

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 3

Is it a difference in sign extension assigning the 32-bit value 0x811C9DC5 to a 64-bit var?