class GnuHash

The DT_GNU_HASH format provides a Bloom filter and a hash table. The data

is always aligned to address size but starts with a header of four uint32_t

words regardless of address size:

* nbucket: number of hash buckets

* bias: chain table index bias

* nfilter: power-of-two number of Bloom filter array elements

* shift: Bloom filter shift count

After the header is an array of address-size words that forms the Bloom

filter. The string hash value divided by address-size in bits (i.e. 32 or

64), modulo the size of the array (which is required to be a power of two)

is used as the index into this array, yielding an address-sized bitmask.

Two bit indices are derived from the string hash value: the hash value

modulo address-size in bits; and the hash value right-shifted by the shift

count, modulo address-size in bits. The bits at both indices are set in

the bitmask to indicate that this hash value may be present in the table;

if either bit is clear, no string with this hash value is present.

Then comes the array of uint32_t hash buckets, indexed by the string hash

value modulo the number of buckets. Zero indicates an empty hash bucket,

and other values are symbol table indices. This points to the first symbol

in that hash bucket. Additional symbols in the same bucket are consecutive

in the symbol table.

The remainder of the data forms an uint32_t array called the "chain table",

indexed by the index into the symbol table minus the chain table index bias.

The chain table element corresponding to a symbol table element holds the

high 31 bits of that symbol's name string's hash value. The low bit is zero

if the subsequent element resides in the same hash bucket and one if not.

So the lookup procedure is as follows:

* Compute the string hash value.

* Compute the index to the Bloom filter element.

* Check the filter element. If it says the hash value is definitely

not present in the table, the lookup has failed.

* Find the first candidate symbol table index in the hash bucket.

If this is zero, the lookup has failed.

* Find the corresponding chain table element (symtab index - bias).

* Compare the high 31 bits of the hash value to table element's high bits.

If those match, then compare the name strings. (The element's index

into the chain table + bias gives the symtab index.) If the name

strings match, the lookup has succeeded, yielding the symtab index.

* If the low bit of the table element is zero, advance to the next

table element and repeat the last step. If this reaches the end

of the table, the table's format is invalid (there must be an entry

with the low bit set to terminate each hash bucket's run).

* Otherwise (i.e. the low bit is one), the lookup has failed.