FNV | это... Что такое FNV? (original) (raw)

FNV (англ. Fowler–Noll–Vo) — простая хэш-функция для общего применения, разработанная Гленом Фаулером, Лондоном Керт Нолом и Фогном Во. Не является криптографической функцией. Существуют варианты для 32-, 64-, 128-, 256-, 512-, и 1024 — битных хэшей.

Математическая запись

Функция FNV:

$h=x_{n+1}$ ,

$x_{i+1} = x_i p \oplus d_i \left( \mod 2^{32} \right)$ ,

x_0=2 166 135 261 ,

p=16777619 — простое число,

d_i — входная последовательность двойных слов.

Модифицированная функция FNV:

$h=x_{n+1}$ ,

$x_{i+1} = \left( x_i \oplus d_i \right) p \left( \mod 2^{32} \right)$ .

Пример кода

Функция проста в реализации. Ее основа — умножение на простое число и сложение по модулю 2 с входным текстом.

#define FNV_32_PRIME ((unsigned int)0x01000193)

unsigned int FNV1Hash (char *buf, unsigned int len) { unsigned char *bp = (unsigned char *)buf;
unsigned char *be = bp + len;
unsigned int hval = 0x811c9dc5;

while (bp < be) { hval *= FNV_32_PRIME; hval ^= (unsigned int)*bp++; }

return hval; }

Модификации

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

unsigned int FNV1aHash (char *buf, unsigned int len) { unsigned char *bp = (unsigned char *)buf;
unsigned char *be = bp + len;
unsigned int hval = 0x811c9dc5;

while (bp < be) { hval ^= (unsigned int)*bp++; hval *= FNV_32_PRIME; }

return hval; }

Помимо вышеуказанной модификации были разработаны некоторые редакции алгоритма, улучшающие производительность. Примером таких функций являются FNV1A_Jesteress и FNV1A_Yorikke. Помимо работы над ускорением алгоритма, автор уделил внимание и качеству распределения[1].

Коллизии

Так как значение хэш-функции 32-битное, вероятность появления коллизии значительно выше, чем у хэш-функций, возвращающих, к примеру, 128-битный хэш.

Примеры коллизий

62274fb9: ИЗБИТЫЕ НЕВЗНАЧАЙ

65194ecd: EKSISTENCIALIZEM ГРОБОКОПАТЕЛЬСТВО

Ссылки

Примечания

↑ Модификации FNV и тестирование функции

Хеш-функции
Общего назначения	Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash
Криптографические	JH • HAVAL • Keccak • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94