Hash table and sort table descriptions

The NB09 and NB11 signature CodeView information contains hash/sort tables in the sstGlobalSym, sstGlobalPub, and sstStaticSym subsections.

Name hash table (symhash == 10):

The symbol name hash table uses the following checksum algorithm to generate the hash.

byt_toupper(b) <- (b&0xDF)

dwrd_toupper(dw) <- (dw&0xDFDFDFDF)

cb = {Number of characters in the name}

lpbName = {pointer to the first character of the name}

ulEnd = 0;

while ( cb & 3 ) {

ulEnd |= byt_toupper ( lpbName [ cb - 1 ] );

ulEnd <<= 8;

cb -= 1;

}

cul = cb / 4;

lpulName = lpbName;

for ( iul = 0; iul < cul; iul++ ) {

ulSum ^= dwrd_toupper(lpulName[iul]);

_lrotl ( ulSum, 4 );

}

ulSum ^= ulEnd;

The hash bucket number is derived from ulSum by taking the modulo of ulSum with the total number of hash buckets.

The format of the table is as follows.

2

cHash(n)

Number of hash buckets

2

Alignment

Filler to preserve alignment

4n

Hash Table[n]

Each ulong entry is a file offset from the beginning of the chain table to the first chain item for each hash bucket.

4n

Bucket Counts[n]

Each ulong entry is the count of items in the chain for each hash bucket.

8m

Chain table[m]

Each entry is a pair of dwords. The first dword is the file offset of the referenced symbol from the beginning of the symbols. The second dword is the checksum of the referenced symbol generated by the above algorithm.


n = the number of hash buckets

m = the number of symbols (with names) = the number of entries in the chain table

Address sort table (addrhash == 12):

The address sort table is a grouping of logical segments (or sections) where each symbol reference within the segment/section is sorted by its segment/section relative offset.

The format of the table is as follows.

2

cSeg(n)

Number of logical segments/sections

2

Alignment

Filler to preserve alignment

4n

Segment Table[n]

Each ulong entry is a file offset from the beginning of the offset table to the first offset item for each segment/section.

4n

Offset Counts[n]

Each ulong entry is the count of items in the offset table for each segment.

8m

Offset Table[m]

Each entry is a pair of dwords. The first dword is the file offset of the referenced symbol from the beginning of the symbols. The second dword is the segment/section relative offset of the referenced symbol in memory.


n = the number of segments/sections

m = the number of symbols (with addresses) = the number of entries in the offset table