Hash Table Section

A hash table consists of Elf32_Word or Elf64_Word objects that provide for symbol table access. The SHT_HASH section provides this hash table. The symbol table to which the hashing is associated is specified in the sh_link entry of the hash table's section header. Labels are used in the following figure to help explain the hash table organization, but these labels are not part of the specification.

Figure 12-4 Symbol Hash Table

The bucket array contains nbucket entries, and the chain array contains nchain entries. Indexes start at 0. Both bucket and chain hold symbol table indexes. Chain table entries parallel the symbol table. The number of symbol table entries should equal nchain, so symbol table indexes also select chain table entries.

A hashing function that accepts a symbol name, returns a value to compute a bucket index. Consequently, if the hashing function returns the value x for some name, bucket [x% nbucket] gives an index y. This index is an index into both the symbol table and the chain table. If the symbol table entry is not the name desired, chain[y] gives the next symbol table entry with the same hash value.

The chain links can be followed until the selected symbol table entry holds the desired name, or the chain entry contains the value STN_UNDEF.

The hash function is as follows.

unsigned long
elf_Hash(const unsigned char *name)
{
    unsigned long h = 0, g;
 
        while (*name)
        {
             h = (h << 4) + *name++;
             if (g = h & 0xf0000000)
                  h ^= g >> 24;
                   h &= ~g;
        }
        return h;
}