Приложение 3: FNV хэш-функции

 

[ Стабильный билд • Вспомогательные типы данных и функции • Sims3: FNV (eng) • Википедия: FNV • Википедия: Хеширование ]

 

Програмный модуль и версия

DBPF2Utils.pas, rev.120825

 

Краткий обзор

 

FNV (англ. Fowler–Noll–Vo) – семейство простых некриптографических хэш-функций общего применения, в The Sims 3 FNV-функции используются в различных ресурсах игры в виде 32-разрядной или 64-разрядной форм для генерации идентификаторов свойств, экземпляров записей, костей и т.п. Изредка используется 24-разрядый хэш, который вычисляется как 32-разрядый хэш, а затем старший байт отбрасывается, а младший складывается по "исключающему или" (xor) со старшим

 

Описание алгоритма

 

Реализация функции хэширования проста, ее реализация – берется некое начальное число, а затем последовательно для каждого байта данных умножается на простое число и складывается (xor-ится) с ними по модулю 2.

Когда хэшируются строки, их символы вначале конвертируются в нижний регистр (в прописные), в связи с этим связана невозможность использования кириллицы в них.

 

 

Примеры реализации алгоритмов FNV хэширования для строк и массивов байт:

function FNV64(s: string): UInt64;
// вычисляет FNV64 для ASCII строки
const
  mul: UInt64 = $00000100000001B3;
var
  i, l: integer;
  b: byte;
begin
  result:= $CBF29CE484222325;
  s:= LowerCase(s);
  l:= Length(s);
  for i:= 1 to l do begin
    b:= ord(s[i]);
    result:= (result*mul) xor b;
  end
end;

function FNV32(a: TBytes; ABegin: integer; AEnd: integer): DWORD;
// вычисляет FNV32 для массива байт
const
  mul: DWORD = $01000193;
var
  i: integer;
begin
  result:= $811C9DC5;
  if AEnd=0 then AEnd:= High(a);
  for i:= ABegin to AEnd do
    result:= (result*mul) xor a[i];
end;