I am trying to do an implementation of Fowler–Noll–Vo hash function
The Pseudocode looks like this
hash = FNV_offset_basis
for each byte_of_data to be hashed
hash = hash × FNV_prime
hash = hash XOR byte_of_data
return hash
This is my code for that
uint8_t byte_of_data;
uint16_t hash;
uint16_t FNV_offset_basis;
uint16_t FNV_prime;
void computeHash(std::string p)
{
FNV_offset_basis = 0xcbf29ce484222325;
FNV_prime = 0x100000001b3;
hash = FNV_offset_basis;
//Iterate through the string
for(int i=0 ; i<p.size();i++)
{
hash = hash * FNV_prime;
hash = hash ^ p.at(i);
}
std::cout << hash; //output 2983
std::cout << std::hex << hash ; //ba7
}
Now I am using it as this
int main()
{
computeHash("Hello");
}
I am testing my result here and I get the result as 0d47307150c412cf
Update:
I fixed my types to
uint8_t byte_of_data;
uint64_t hash;
uint64_t FNV_offset_basis;
uint64_t FNV_prime;
and I get the result fa365282a44c0ba7 which still does not match the result 0d47307150c412cf
Any suggestions on how I can fix this
Your current result fa365282a44c0ba7
is correct according to the official reference
source code (in C) and manual calculation too... this makes the test site wrong.
The reference source files are linked here: C file and H file
I removed the includes of longlong.h
and added following two code parts instead:
/*before the reference code*/
#include <stdint.h>
#define HAVE_64BIT_LONG_LONG
typedef uint64_t u_int64_t;
typedef uint32_t u_int32_t;
/*after it*/
#include<stdio.h>
int main()
{
printf("%llx\n", fnv_64_str("Hello", FNV1_64_INIT));
}
to make it compile with gcc -std=c11 source.c
(gcc (i686-posix-sjlj-rev0, Built by MinGW-W64 project) 4.9.1
)
Output: fa365282a44c0ba7
.
And Ideone says so too