Misplaced Pages

PJW hash function

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Computing algorithm

PJW hash function is a non-cryptographic hash function created by Peter J. Weinberger of AT&T Bell Labs.

Other versions

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.

Algorithm

PJW hash algorithm involves shifting the previous hash and adding the current byte followed by moving the high bits:

algorithm PJW_hash(s) is
    uint h := 0
    bits := uint size in bits
    for i := 1 to |S| do
        h := h << bits/8 + s
        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

Below is the algorithm implementation used in Unix ELF format:

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;
}

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.

See also

Non-cryptographic hash functions

References

  1. Binstock, Andrew (1996). "Hashing Rehashed". Dr. Dobb's.
  2. "Hash Functions". www.cs.hmc.edu. Retrieved 2015-06-10.
  3. CORPORATE UNIX Press (1993). System V application binary interface. ISBN 0-13-100439-5.
  4. "ELF hash function may overflow". 12 April 2023. Retrieved 2023-04-14.
Category: