PJW hash function

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.[1]

Algorithm

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

Below is the algorithm implementation used in Unix ELF format:[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;
}

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

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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.