Хэш-функция PJW
Хэш-функция PJW — это некриптографическая хэш-функция, созданная Питером Дж. Вайнбергером из AT&T Bell Labs.
Другие версии
[ редактировать ]Вариант хеша PJW использовался для создания хеша ElfHash или Elf64, который используется в объектных файлах Unix в формате ELF .
Аллен Голуб создал портативную версию хэш-алгоритма PJW, которая содержала ошибку и попала в несколько учебников, как позже признался автор одного из этих учебников. [1]
Алгоритм
[ редактировать ]Алгоритм хеширования PJW включает в себя сдвиг предыдущего хеша и добавление текущего байта с последующим перемещением старших битов: [2]
algorithm PJW_hash(s) is
uint h := 0
bits := uint size in bits
for i := 1 to |S| do
h := h << bits/8 + s[i]
high := get top bits/8 bits of h from left
if high ≠ 0 then
h := h xor (high >> bits * 3/4)
h := h & ~high
return h
Выполнение
[ редактировать ]Ниже приведена реализация алгоритма, используемая в формате Unix ELF: [3]
unsigned long ElfHash(const unsigned char *s)
{
unsigned long h = 0, high;
while (*s)
{
h = (h << 4) + *s++;
if (high = h & 0xF0000000)
h ^= high >> 24;
h &= ~high;
}
return h;
}
Этот код C ошибочно предполагает, что long это 32-битный тип данных. Когда long шире 32 бит, как и во многих 64-битных системах, код содержит ошибку. [4]
См. также
[ редактировать ]Некриптографические хэш-функции
Ссылки
[ редактировать ]- ^ Бинсток, Эндрю (1996). «Перефразирование хэширования» . Доктор Добб .
- ^ «Хеш-функции» . www.cs.hmc.edu . Проверено 10 июня 2015 г.
- ^ КОРПОРАТИВНАЯ UNIX Press (1993). Двоичный интерфейс приложения System V. ISBN 0-13-100439-5 .
- ^ «Хеш-функция ELF может переполниться» . Проверено 14 апреля 2023 г.