Хэш-функция PJW — это некриптографическая хэш-функция, созданная Питером Дж. Вайнбергером из AT&T Bell Labs.
Вариант хеша PJW использовался для создания хеша ElfHash или Elf64, который используется в объектных файлах Unix с форматом ELF .
Аллен Холуб создал переносимую версию алгоритма хеширования PJW, в которой была ошибка, и которая попала в несколько учебников, как позже признался автор одного из этих учебников. [1]
Алгоритм хэширования PJW включает сдвиг предыдущего хеша и добавление текущего байта с последующим перемещением старших битов: [2]
алгоритм PJW_hash(s) — это uint h := 0 биты := размер uint в битах для i := 1 до |S| сделать h := h << бит/8 + s[i] high := получить верхние биты/8 бит h слева если высокий ≠ 0 тогда h := h xor (high >> биты * 3/4) ч := ч & ~высокий вернуться ч
Ниже представлена реализация алгоритма, используемая в формате 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]
Некриптографические хэш-функции