PJW hash function
PJW hash function is a non-cryptographic hash function created by Peter J. Weinberger of AT&T Bell Labs.
Other versions
[edit ]A variant of PJW hash had been used to create ElfHash or Elf64 hash that is used in Unix object files with ELF format.
Allen Holub has created a portable version of PJW hash algorithm that had a bug and ended up in several textbooks, as the author of one of these textbooks later admitted.[1]
Algorithm
[edit ]PJW hash algorithm involves shifting the previous hash and adding the current byte followed by moving the high bits:[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
Implementation
[edit ]Below is the algorithm implementation used in Unix ELF format:[3]
unsignedlongElfHash(constunsignedchar*s) { unsignedlongh=0,high; while(*s) { h=(h<<4)+*s++; if(high=h&0xF0000000) h^=high>>24; h&=~high; } returnh; }
This C code incorrectly assumes that long is a 32-bit data type. When long is wider than 32 bits, as it is on many 64-bit systems, the code contains a bug.[4]
See also
[edit ]Non-cryptographic hash functions
References
[edit ]- ^ Binstock, Andrew (1996). "Hashing Rehashed". Dr. Dobb's .
- ^ "Hash Functions". www.cs.hmc.edu. Retrieved 2015年06月10日.
- ^ CORPORATE UNIX Press (1993). System V application binary interface . ISBN 0-13-100439-5.
- ^ "ELF hash function may overflow". 12 April 2023. Retrieved 2023年04月14日.