FNV-1a (Fowler–Noll–Vo) hash function

#include <stdio.h>
#include <inttypes.h>

int main(void) {
	uint64_t hash = 14695981039346656037ULL;
	for (char c = getchar(); c != EOF; c = getchar()) {
		hash = (hash ^ c) * 1099511628211ULL;
	}
	printf("%" PRIu64 "\n", hash);
	return 0;
}

Constants

FNV seed

  • 32 bit: 2166136261
  • 64 bit: 14695981039346656037
  • 128 bit: 144066263297769815596495629667062367629
  • 256 bit: 100029257958052580907070968620625704837092796014241193945225284501741471925557
  • 512 bit: 
    96593031294966694980094354007163104660904
18745672637896108374329434462657994582932
19771643844981305189220653980578449532823
9340083876191928701583869517785
  • 1024 bit: 
    14197795064947621068722070641403218320880
62279544193396087847491461758272325229673
23037177221508640965212023555493656281746
69108571814760471015076148029755969804077
32015769245856300321530495715015740364446
03635505054127112859663616102678680828938
23963790439336411086884584107735010676915

FNV prime

  • 32 bit: 2^24 + 2^8 + 0x93 = 16777619
  • 64 bit: 2^40 + 2^8 + 0xb3 = 1099511628211
  • 128 bit: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
  • 256 bit: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
  • 512 bit: 2^344 + 2^8 + 0x57 = 
    35835915874844867368919076489095108449946
32795575439255839982561542066993888257512
6094039892345713852759
  • 1024 bit: 2^680 + 2^8 + 0x8d = 
    50164565101131186554345988110352789550307
65345404790744303017523831112055108147451
50915769222029538271616265187852689524938
52922918165243750837466913718040942718731
60484737966720260389217684476157468082573

Sources

  • https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
  • http://isthe.com/chongo/tech/comp/fnv
  • https://datatracker.ietf.org/doc/html/draft-eastlake-fnv-17.html