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 !

This is *not* FNV. You used the number intended as initial value as prime and initialized to 0 instead. The initial value should be `0x811C9DC5` and the prime should be `0x01000193` (for a 32-bit hash). For a 64-bit hash the values are different. — Mark Jeronimus, Jun 03 '20 at 11:50

score 4 · Accepted Answer · answered May 18 '10 at 11:20

4

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.

answered May 18 '10 at 11:20

Thomas Pornin

72,986
14
147
189

In Java as in Obj-C I get the same value for prime = -2128831035 In Java when I put "0x811C9DC5L" I get value = 2166136261 – Dough May 18 '10 at 11:29
You should not get -2128831035 in Obj-C. Are you sure this is not an artefact of how you print that value ? (i.e. did you use "%lld" or "%d" in your `printf()` ?) – Thomas Pornin May 18 '10 at 12:25
And a clue that -2128831035 isn't the correct numerical value: it's not prime! -2128831035 = -(3*5*17*101*82657) – David Gelhar May 18 '10 at 13:24
Thank you all ! I changed the Java value from "0x811C9DC5" to "0x811C9DC5L". To get the correct value in Objective-C I have to do : NSLog(@"My FNV = %lld", hash); – Dough May 18 '10 at 14:02

score 3 · Answer 2 · answered Dec 01 '12 at 09:31

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

score 1 · Answer 3 · edited Dec 01 '12 at 09:36

1

It is a difference in sign extension assigning the 32-bit value 0x811C9DC5 to a 64-bit var.

edited Dec 01 '12 at 09:36

answered May 18 '10 at 11:36

David Gelhar

27,873
3
67
84

score 0 · Answer 4 · answered May 18 '10 at 10:59

0

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

answered May 18 '10 at 10:59

Thanks for your answer ! Char, in Java en Objective-Cn is returning the ASCII value of the char. For exemple : a = 97 b = 98 c = 99 d = 100 and so on ! – Dough May 18 '10 at 11:00
@dough: it's definitely not using ASCII, though the first 127 characters may have the same numerical values. As an exercise, what do you get if you print the character 'ﬂ'? And what's the ASCII value of 'ﬂ'? – May 19 '10 at 08:47
'fl' is not a character, it is two : f and l ! – Dough May 20 '10 at 07:05
@Dough: no, that's a ligature. Go on, try and select just the f in ﬂ. Or, if you don't like that example, tell me the ASCII value of ·, « or ◊. – May 20 '10 at 10:20

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

4 Answers4