https://github.com/python/cpython/commit/dd1d4f0c4965ea9643d0e5e32bf7c0cea4e7b0c1 commit: dd1d4f0c4965ea9643d0e5e32bf7c0cea4e7b0c1 branch: main author: Stan Ulbrych <[email protected]> committer: StanFromIreland <[email protected]> date: 2026-11-06T16:34:22Z summary:
gh-131725: Generate GNU hash table in `msgfmt.py` (#131727) Co-authored-by: Serhiy Storchaka <[email protected]> files: A Misc/NEWS.d/next/Tools-Demos/2025-03-25-18-00-00.gh-issue-131725.qwfh321.rst M Lib/test/test_tools/msgfmt_data/fuzzy.mo M Lib/test/test_tools/msgfmt_data/general.mo M Lib/test/test_tools/test_msgfmt.py M Tools/i18n/msgfmt.py diff --git a/Lib/test/test_tools/msgfmt_data/fuzzy.mo b/Lib/test/test_tools/msgfmt_data/fuzzy.mo index 4b144831cf5f75c..273edbbbd7cbd79 100644 Binary files a/Lib/test/test_tools/msgfmt_data/fuzzy.mo and b/Lib/test/test_tools/msgfmt_data/fuzzy.mo differ diff --git a/Lib/test/test_tools/msgfmt_data/general.mo b/Lib/test/test_tools/msgfmt_data/general.mo index ee905cbb3ec58db..3107f6711bdd10b 100644 Binary files a/Lib/test/test_tools/msgfmt_data/general.mo and b/Lib/test/test_tools/msgfmt_data/general.mo differ diff --git a/Lib/test/test_tools/test_msgfmt.py b/Lib/test/test_tools/test_msgfmt.py index 3019e52d22ec82d..0b39f509e0a415d 100644 --- a/Lib/test/test_tools/test_msgfmt.py +++ b/Lib/test/test_tools/test_msgfmt.py @@ -47,6 +47,29 @@ def test_compilation(self): self.assertDictEqual(actual._catalog, expected._catalog) + def test_hash_table(self): + # Check _hashpjw generates correct hash values + self.assertEqual(msgfmt._hashpjw(b"stan"), 502398) + self.assertEqual(msgfmt._hashpjw(b"foo"), 27999) + # Carries into bit 32 are discarded, as GNU gettext does + self.assertEqual(msgfmt._hashpjw(b"kL{M-#[J)pxyz"), 32778) + + # Check hash table is generated correctly for general.po + with temp_cwd(): + tmp_mo_file = "messages.mo" + compile_messages(data_dir / "general.po", tmp_mo_file) + with open(tmp_mo_file, "rb") as f: + mo_data = f.read() + + header = struct.unpack("=7I", mo_data[:28]) + hash_table_size, hash_table_offset = header[5:7] + + hash_tab_end = hash_table_offset + hash_table_size * 4 + hash_tab = struct.unpack(f"={hash_table_size}I", + mo_data[hash_table_offset:hash_tab_end]) + + self.assertEqual(hash_tab, (1, 3, 0, 8, 9, 7, 2, 0, 4, 5, 0, 6, 0)) + def test_binary_header(self): with temp_cwd(): tmp_mo_file = 'messages.mo' @@ -69,8 +92,8 @@ def test_binary_header(self): self.assertEqual(num_strings, 9) self.assertEqual(orig_table_offset, 28) self.assertEqual(trans_table_offset, 100) - self.assertEqual(hash_table_size, 0) - self.assertEqual(hash_table_offset, 0) + self.assertEqual(hash_table_size, 13) + self.assertEqual(hash_table_offset, 172) def test_translations(self): with open(data_dir / 'general.mo', 'rb') as f: diff --git a/Misc/NEWS.d/next/Tools-Demos/2025-03-25-18-00-00.gh-issue-131725.qwfh321.rst b/Misc/NEWS.d/next/Tools-Demos/2025-03-25-18-00-00.gh-issue-131725.qwfh321.rst new file mode 100644 index 000000000000000..c7a8a3e492ad82b --- /dev/null +++ b/Misc/NEWS.d/next/Tools-Demos/2025-03-25-18-00-00.gh-issue-131725.qwfh321.rst @@ -0,0 +1,2 @@ +``Tools/i18n/msgfmt.py`` now writes a hash table to the generated ``.mo`` +file, as GNU :program:`msgfmt` does. diff --git a/Tools/i18n/msgfmt.py b/Tools/i18n/msgfmt.py index 3351511bbc8f2b7..0ca61a0af9e35a1 100755 --- a/Tools/i18n/msgfmt.py +++ b/Tools/i18n/msgfmt.py @@ -59,21 +59,39 @@ def add(ctxt, id, str, fuzzy): def generate(): "Return the generated output." global MESSAGES + + # The hash table uses open addressing with double hashing, as in GNU + # gettext's write-mo.c: the first probe is V % M and each following probe + # adds 1 + V % (M - 2), where V is the hash of the string and M is the + # table size. M is the smallest prime greater than 4/3 * N (N being the + # number of strings), which keeps the expected number of probes small. + # See Knuth, The Art of Computer Programming, Volume 3, section 6.4. + hash_tab_size = _next_prime((len(MESSAGES) * 4) // 3) + if hash_tab_size <= 2: + hash_tab_size = 3 + hash_table = array.array("I", [0] * hash_tab_size) + # the keys are sorted in the .mo file keys = sorted(MESSAGES.keys()) offsets = [] ids = strs = b'' - for id in keys: + for i, id in enumerate(keys): + hash_val = _hashpjw(id) + idx = hash_val % hash_tab_size + inc = 1 + (hash_val % (hash_tab_size - 2)) + while hash_table[idx]: + idx = (idx + inc) % hash_tab_size + hash_table[idx] = i + 1 # For each string, we need size and file offset. Each string is NUL # terminated; the NUL does not count into the size. offsets.append((len(ids), len(id), len(strs), len(MESSAGES[id]))) ids += id + b'\0' strs += MESSAGES[id] + b'\0' - output = '' - # The header is 7 32-bit unsigned integers. We don't use hash tables, so - # the keys start right after the index tables. - # translated string. - keystart = 7*4+16*len(keys) + + # The header is 7 32-bit unsigned integers, followed by the index tables, + # then the hash table, then the keys. + hashstart = 7*4+16*len(keys) + keystart = hashstart+hash_tab_size*4 # and the values start after the keys valuestart = keystart + len(ids) koffsets = [] @@ -85,13 +103,15 @@ def generate(): voffsets += [l2, o2+valuestart] offsets = koffsets + voffsets output = struct.pack("Iiiiiii", - 0x950412de, # Magic + 0x950412de, # Magic 0, # Version len(keys), # # of entries 7*4, # start of key index 7*4+len(keys)*8, # start of value index - 0, 0) # size and offset of hash table + hash_tab_size, # size of hash table + hashstart) # offset of hash table output += array.array("i", offsets).tobytes() + output += hash_table.tobytes() output += ids output += strs return output @@ -257,5 +277,39 @@ def main(): make(filename, outfile) +# Utilities for writing hash table + +# Peter J. Weinberger hash function +# See: https://www.drdobbs.com/database/hashing-rehashed/184409859 +def _hashpjw(strs): + hval = 0 + for s in strs: + if not s: + break + hval <<= 4 + hval += s + g = hval & (0xF << 28) + if g: + hval ^= g >> 24 + hval ^= g + return hval & 0xFFFFFFFF + + +def _next_prime(start): + def is_prime(num): + divn = 3 + sq = divn * divn + while sq < num and num % divn != 0: + divn += 1 + sq += 4 * divn + divn += 1 + + return num % divn != 0 + + candidate = start | 1 + while not is_prime(candidate): + candidate += 2 + return candidate + if __name__ == '__main__': main() _______________________________________________ Python-checkins mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3//lists/python-checkins.python.org Member address: [email protected]
