Implementation of FNV

Question

I am trying to implement FNV hash from http://isthe.com/chongo/tech/comp/fnv/

I converted the PowerBasic's inline asm on that page into Delphi.

    function ReadFileToMem(sPath:string):Pointer;
    var
    hFile:    THandle;
    pBuffer:  Pointer;
    dSize:    DWORD;
    dRead:    DWORD;
    begin
    hFile := CreateFile(PChar(sPath), GENERIC_READ, FILE_SHARE_READ, nil, OPEN_EXISTING, 0, 0);
    if hFile <> 0 then
        dSize := GetFileSize(hFile, nil);
        if dSize <> 0 then
        begin
          SetFilePointer(hFile, 0, nil, FILE_BEGIN);
          GetMem(Result, dSize);
          ReadFile(hFile, Result^, dSize, dRead, nil);
          if dRead = 0 then
            MessageBox(0, PChar('Error reading file.'), PChar('Read Error'), MB_ICONEXCLAMATION)
         end;
        CloseHandle(hFile);
    end;

    function GetPointerSize(lpBuffer: Pointer): Cardinal; // Function by ErazerZ
    begin
      if lpBuffer = nil then
        Result := Cardinal(-1)
      else
        Result := Cardinal(Pointer(Cardinal(lpBuffer) -4)^) and $7FFFFFFC -4;
    end;

     FUNCTION FNV32( dwOffset : Pointer; dwLen : DWORD; offset_basis : DWORD) : DWORD ;
      asm
     mov esi, dwOffset      //;esi = ptr to buffer
     mov ecx, dwLen         //;ecx = length of buffer (counter)
     mov eax, offset_basis  //;set to 2166136261 for FNV-1
     mov edi, 16777619//&h01000193    //;FNV_32_PRIME = 16777619
     xor ebx, ebx           //;ebx = 0
      @nextbyte:
     mul edi                //;eax = eax * FNV_32_PRIME
     mov bl, [esi]          //;bl = byte from esi
     xor eax, ebx           //;al = al xor bl
     inc esi                //;esi = esi + 1 (buffer pos)
     dec ecx                //;ecx = ecx - 1 (counter)
     jnz @nextbyte           //;if ecx is 0, jmp to NextByte
     mov @result, eax      //;else, function = eax

    end;

procedure TForm1.Button1Click(Sender: TObject);
var
pFile : Pointer;
hFile : Cardinal;
begin
//Profiler1['Test'].Start;
pFile := ReadFileToMem(fn);
hFile := FNV32(pFile,GetPointerSize(pFile),2166136261);
//Profiler1['Test'].Stop;
//OutputDebugString(pchar(Profiler1['Test'].AsText[tiAll]));
OutputDebugString(pchar(inttostr(hFile)));
end;

If a size of given file is more that 200KB, the output is random (hash) number. Am I missing something?

Answer 1

Your asm code is somewhat buggy, IMHO. It will crash your application, as it is written.

• You need to preseve esi/edi/ebx registers
• parameters are passed in eax,ecx,edx registers
• result is the eax register

Correct way to do it could be (not tested, just written here there):

function fnv32(dwOffset : Pointer; dwLen : DWORD; offset_basis: DWORD) : DWORD ;
asm // eax=dwOffset ecx=dwLen edx=offset_basis -> result in eax
  push esi
  push edi
  mov esi,eax
  mov eax,edx
  or ecx,ecx
  je @z
  mov edi,16777619
  xor edx,edx
@1:
  mul edi
  mov dl,[esi]
  xor eax,edx
  inc esi
  dec ecx
  jnz @1
@z:
  pop edi
  pop esi
end;

So to read and hash any file, in a pure Delphi way (don't use Windows API like you did):

function fnv32file(const aFileName: TFileName): DWORD;
begin
  with TMemoryStream.Create do
  try
    LoadFromFile(aFileName);
    result := fnv32(Memory,Size,0);
  finally
    Free;
  end;
end;

A pure pascal version won't be much slower IMHO (the bottleneck is definitively reading the data from the hard drive):

function fnv32(dwOffset : PByteArray; dwLen : DWORD; offset_basis: DWORD): DWORD ;
var i: integer;
begin
  result := offset_basis;
  for i := 0 to dwLen-1 do
    result := (result*16777619) xor DWORD(dwOffset^[i]);
end;