The hash table of an MO file

The hash table lets a reader find an original string without searching the sorted table. It is an array of S 32-bit numbers at the offset H of the header. Each number is either 0, an empty slot, or the number of an original string plus one, so that 0 is free to mean empty. The table is optional: the header says S is 0 when it is left out, and msgfmt --no-hash omits it from a catalogue of minor revision 0. A catalogue of minor revision 1 always has one.

The hash function

The function is “hashpjw”, by P. J. Weinberger, from the book Compilers: Principles, Techniques and Tools by Aho, Sethi and Ullman. It works on the bytes of the string up to its first NUL, with 32-bit arithmetic: the value is moved four bits left and the byte added, and whenever any of the top four bits is set they are folded down into bits 4 to 7 and cleared.

hval = 0
for each byte b of the string, up to the first NUL:
    hval = (hval << 4) + b            (kept to 32 bits)
    g = hval and 0xF0000000
    if g is not 0:
        hval = hval xor (g >> 24)
        hval = hval xor g

The hash of gettext, hash-string.c; HASHWORDBITS is 32

The string that is hashed is the original as stored: with a context, the context, the byte 0x04 and the message; and with a plural, only the singular, because the NUL that separates the plural ends the string.

The size

msgfmt makes the size S the next prime number after 4/3 of the number of strings, counting the system-dependent ones, and at least 3, so that S is more than 2. The lookup below divides by S − 2, so a table of size 2 or less cannot be used.

With N = 2 strings the size is 3; with 4 strings, 5; with 4 strings and 1 system-dependent string, 7. Those are the sizes msgfmt 1.0 wrote for the examples on this site.

Looking a string up

Take h, the hash of the string, and compute idx = h mod S and incr = 1 + (h mod (S − 2)).
Read the slot at idx. If it is 0, the string is not in the catalogue.
Otherwise the slot holds the number of an original, plus one. Compare the string with that original. The lengths are compared with “at least”, not equals, because a plural entry’s original holds an embedded NUL. If they are the same, the translation with that number is the answer.
If not, move to the next slot: if idx ≥ S − incr then idx = idx − (S − incr), otherwise idx = idx + incr, and go back to step 2.

This is double hashing; because S is prime and more than 2, incr is never 0 and the sequence visits every slot. msgfmt places the strings with the same steps: it puts original j at the first empty slot of its sequence and stores j + 1 there.

A slot that holds a number larger than N refers to a system-dependent string, whose number is N plus its index among them. The loader of gettext adds those to the table itself when it reads a file, and msgfmt does not store them in the file: the slots are free in the file’s table. See system-dependent strings.

Worked example

In the small catalogue with S = 3:

String	Hash	idx = h mod 3	Slot holds
the empty string	0	0	1: original 0, the header entry
`Real`	`0x58B7C` (363,388)	1	2: original 1

For “Real”: R is 82; 82 × 16 + 101 (e) is 1,413; 1,413 × 16 + 97 (a) is 22,705; 22,705 × 16 + 108 (l) is 363,388. None of the top four bits were ever set, so there was no folding. Slot 2 stays 0. The lookup of a string that is not there, such as Imaginary, ends at the first empty slot it meets.

Checking a file

A file is consistent when each original of the table can be found by the steps above, and each non-zero slot is at most N (or N plus the number of system-dependent strings). The explorer does this for every original and lists those it cannot find.

Not described

Known, not yet covered

Reference: hash tables written by programs other than msgfmt may place strings differently; a reader needs only the lookup above to find them, and the explorer checks that, but no other writer’s rule was read.

.MO File Format – The hash table