Create a hash table data structure to represent hash table sections

Overview

NOT ACCURATE. SEE THIS COMMENT FOR MORE.

A hash table section is used to very quickly find a symbol by it's name. Given the name, the hash table can be used in an iterative way to find potential matching symbols until the symbol with the correct name is found.

The hash table is made up of:

A number representing the number of "buckets" (nbucket)
A number representing the number of "chains" (nchain)
A "bucket" array of type Elf32_Word or Elf64_Word elements
A "chain" array of indices into the symbol table (what size? same as buckets?)

To find a symbol:

A hashing function (see reference code) takes a string and converts it to a long value x
A symbol index can be calculated with bucket [ x % nbucket]
The symbol should be checked to see if the name is correct
If it's not, the same index can be used to access a "chain" item: chain[x] = y
The y can be used as an index into the symbol table for the next match
The symbol should be checked to see if the name is correct
If it's not, the y can be used to access the next "chain" item: chain[y] = z
And so on, until the actual symbol is found

Reference

See: https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter6-48031.html

Reference hash function (generated by GPT-4, so verify it):

fn elf_hash(name: &[u8]) -> u32 {
    let mut h: u32 = 0;
    let mut g: u32;

    for &c in name {
        h = (h << 4) + c as u32;
        g = h & 0xf000_0000;

        if g != 0 {
            h ^= g >> 24;
            h &= !g;
        }
    }

    h
}

Notes

This data structure should have add/remove/append methods etc.
When a symbol is removed from a symbol table, it should also be removed from the appropriate hash table
The symbol table that the hash section is associated with is referenced through the sh_link attribute in the section header

mjhouse / deaf

Create a hash table data structure to represent hash table sections #26

Overview

Reference

Notes