flat assembler
Message board for the users of flat assembler.

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

Joined: 06 Jan 2011
Posts: 408
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?

06 Oct 2011, 15:03
cod3b453

Joined: 25 Aug 2004
Posts: 618
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 () 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.
06 Oct 2011, 18:22
Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8000
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.
06 Oct 2011, 19:00
idle

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

compiles
06 Oct 2011, 19:55
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.
06 Oct 2011, 21:13
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum