The dictionary lets a linker find the module that defines a public name without reading every module. It is a hash table, stored in blocks of 512 bytes. The library header gives its offset and its number of blocks.
A block
0buckets: 37 bytes, each an entry’s offset in the block divided by 2, or 0 if empty37 bytes37free pointer: where free space starts, divided by 2, or 0xFF when the block is full1 byte38entriesto 512 bytes
Entries
| Size | Field | Meaning |
|---|---|---|
| 1 | Length | The length of the name |
| Length | Name | The public name |
| 2 | Page number | The module’s page number, little-endian |
Entries start at even offsets, so that a bucket’s offset divided by 2 fits in a byte.
The hash
A name gives four numbers from four running values over its bytes, read case-insensitively by setting bit 5 of each byte. The 16-bit values start from the name’s length (with bit 5 set) or from 0, and each step rotates by 2 bits and exclusive-ors a byte:
blockX = len | 0x20 (rotated left, xor the bytes from the front)
bucketD = len | 0x20 (rotated right, xor the bytes from the front)
bucketX = 0 (rotated right, xor the bytes from the back)
blockD = 0 (rotated left, xor the bytes from the back)
first block = blockX % blocks
first bucket = bucketX % 37
block step = blockD % blocks, or 1 if that is 0
bucket step = bucketD % 37, or 1 if that is 0To look up a name, start at the first block and bucket. If the bucket is occupied by a different name, step the bucket by the bucket step, modulo 37; when the buckets of a block are exhausted, step the block by the block step and go on.
After the dictionary
Some librarian tools write more bytes after the dictionary, an extended dictionary. Its layout is not described here.