flat assembler
Message board for the users of flat assembler.

Index > Main > fnv hashing theory - can you share?

Author
Thread Post new topic Reply to topic
idle



Joined: 06 Jan 2011
Posts: 359
Location: Ukraine
idle
intro:
Fnv algo outputs a DWord, other word results while input is arbitrary long.
C-code i found:
Code:
 1 unsigned fnv_hash ( void *key, int len )
 2 {
 3   unsigned char *p = key;
 4   unsigned h = 2166136261;
 5   int i;
 6 
 7   for ( i = 0; i < len; i++ )
 8     h = ( h * 16777619 ) ^ p[i];
 9 
10   return h;
11 }
    


confusion:
What is the basis?/How Does it work?
What are FNV limits?/Is there a way to find a collision?
Fasm uses the algo too & fasm limits symbols length to 2xx chars: is it proved no collisions appear ever.
Is FNV limit 2^32?
Can you explain step by step?

Thanks for your attention.
Post 06 Oct 2011, 15:03
View user's profile Send private message Reply with quote
cod3b453



Joined: 25 Aug 2004
Posts: 619
cod3b453
I don't know the algorithm but I think the values 16777619 and 2166136261 are prime so any multiple in the field h (2^32) will not collide. This is similar to the linear congruence method used for PRNG functions, where you choose "good" (usually prime) values. When mixing the key stream into the calculation, XOR is a good choice because, unlike addition or multiplication, values such as 0,1,2^n (Question) cannot skew the accumulation in h towards a collision so easily. It's also important that p is smaller (2^8 ) than h so that the upper 24bits are not affected by the current round and carry over to the next iteration.

Given that h is 2^32, there will certainly be a collision after 2^32 different inputs; there is also a fair chance that if you tried 2^32 different keys you'd find one or more collisions.

Hope that helps.
Post 06 Oct 2011, 18:22
View user's profile Send private message Reply with quote
Tomasz Grysztar
Assembly Artist


Joined: 16 Jun 2003
Posts: 7712
Location: Kraków, Poland
Tomasz Grysztar
idle wrote:
Fasm uses the algo too & fasm limits symbols length to 2xx chars: is it proved no collisions appear ever.
fasm uses FNV-1a xor-folded down to 24 bits, and it is actually quite easy to get the collision. Quick search gave me collision with "aaigb" and "arsga" texts.
Post 06 Oct 2011, 19:00
View user's profile Send private message Visit poster's website Reply with quote
idle



Joined: 06 Jan 2011
Posts: 359
Location: Ukraine
idle
Code:
aaigb:
arsga:
    

compiles
Post 06 Oct 2011, 19:55
View user's profile Send private message Reply with quote
Goplat



Joined: 15 Sep 2006
Posts: 181
Goplat
fasm has a linked list for each used hash value, so you're allowed to have multiple labels with the same hash value, it'll just be slow if there's a whole lot of them. Unless you're making collisions on purpose it won't be a problem.
Post 06 Oct 2011, 21:13
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar.

Powered by rwasa.