From fe3e8d1589e54de999cccc775f269a39443c82d6 Mon Sep 17 00:00:00 2001 From: Jeff Epler Date: Thu, 28 May 2020 07:40:56 -0500 Subject: string compression: save a few bits per string Length was stored as a 16-bit number always. Most translations have a max length far less. For example, US English translation lengths always fit in just 8 bits. probably all languages fit in 9 bits. This also has the side effect of reducing the alignment of compressed_string_t from 2 bytes to 1. testing performed: ran in german and english on pyruler, printed messages looked right. Firmware size, en_US Before: 3044 bytes free in flash After: 3408 bytes free in flash Firmware size, de_DE (with #2967 merged to restore translations) Before: 1236 bytes free in flash After: 1600 bytes free in flash --- py/makeqstrdata.py | 52 ++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 44 insertions(+), 8 deletions(-) (limited to 'py/makeqstrdata.py') diff --git a/py/makeqstrdata.py b/py/makeqstrdata.py index 0d667959d..64e4d26f4 100644 --- a/py/makeqstrdata.py +++ b/py/makeqstrdata.py @@ -1,7 +1,7 @@ """ Process raw qstr file and output qstr data with length, hash and data bytes. -This script works with Python 2.6, 2.7, 3.3 and 3.4. +This script works with Python 2.7, 3.3 and 3.4. """ from __future__ import print_function @@ -132,19 +132,37 @@ def compute_huffman_coding(translations, qstrs, compression_filename): print("// estimated total memory size", len(lengths) + 2*len(values) + sum(len(cb[u]) for u in all_strings_concat)) print("//", values, lengths) values_type = "uint16_t" if max(ord(u) for u in values) > 255 else "uint8_t" + max_translation_encoded_length = max(len(translation.encode("utf-8")) for original,translation in translations) with open(compression_filename, "w") as f: f.write("const uint8_t lengths[] = {{ {} }};\n".format(", ".join(map(str, lengths)))) f.write("const {} values[] = {{ {} }};\n".format(values_type, ", ".join(str(ord(u)) for u in values))) + f.write("#define compress_max_length_bits ({})\n".format(max_translation_encoded_length.bit_length())) return values, lengths -def decompress(encoding_table, length, encoded): +def decompress(encoding_table, encoded, encoded_length_bits): values, lengths = encoding_table - #print(l, encoded) dec = [] this_byte = 0 this_bit = 7 b = encoded[this_byte] - for i in range(length): + bits = 0 + for i in range(encoded_length_bits): + bits <<= 1 + if 0x80 & b: + bits |= 1 + + b <<= 1 + if this_bit == 0: + this_bit = 7 + this_byte += 1 + if this_byte < len(encoded): + b = encoded[this_byte] + else: + this_bit -= 1 + length = bits + + i = 0 + while i < length: bits = 0 bit_length = 0 max_code = lengths[0] @@ -170,10 +188,11 @@ def decompress(encoding_table, length, encoded): searched_length += lengths[bit_length] v = values[searched_length + bits - max_code] + i += len(v.encode('utf-8')) dec.append(v) return ''.join(dec) -def compress(encoding_table, decompressed): +def compress(encoding_table, decompressed, encoded_length_bits, len_translation_encoded): if not isinstance(decompressed, str): raise TypeError() values, lengths = encoding_table @@ -182,6 +201,19 @@ def compress(encoding_table, decompressed): #print(lengths) current_bit = 7 current_byte = 0 + + code = len_translation_encoded + bits = encoded_length_bits+1 + for i in range(bits - 1, 0, -1): + if len_translation_encoded & (1 << (i - 1)): + enc[current_byte] |= 1 << current_bit + if current_bit == 0: + current_bit = 7 + #print("packed {0:0{width}b}".format(enc[current_byte], width=8)) + current_byte += 1 + else: + current_bit -= 1 + for c in decompressed: #print() #print("char", c, values.index(c)) @@ -342,14 +374,17 @@ def print_qstr_data(encoding_table, qcfgs, qstrs, i18ns): total_text_size = 0 total_text_compressed_size = 0 + max_translation_encoded_length = max(len(translation.encode("utf-8")) for original, translation in i18ns) + encoded_length_bits = max_translation_encoded_length.bit_length() for original, translation in i18ns: translation_encoded = translation.encode("utf-8") - compressed = compress(encoding_table, translation) + compressed = compress(encoding_table, translation, encoded_length_bits, len(translation_encoded)) total_text_compressed_size += len(compressed) - decompressed = decompress(encoding_table, len(translation_encoded), compressed) + decompressed = decompress(encoding_table, compressed, encoded_length_bits) + assert decompressed == translation for c in C_ESCAPES: decompressed = decompressed.replace(c, C_ESCAPES[c]) - print("TRANSLATION(\"{}\", {}, {{ {} }}) // {}".format(original, len(translation_encoded)+1, ", ".join(["0x{:02x}".format(x) for x in compressed]), decompressed)) + print("TRANSLATION(\"{}\", {}) // {}".format(original, ", ".join(["{:d}".format(x) for x in compressed]), decompressed)) total_text_size += len(translation.encode("utf-8")) print() @@ -385,6 +420,7 @@ if __name__ == "__main__": qcfgs, qstrs, i18ns = parse_input_headers(args.infiles) if args.translation: + i18ns = sorted(i18ns) translations = translate(args.translation, i18ns) encoding_table = compute_huffman_coding(translations, qstrs, args.compression_filename) print_qstr_data(encoding_table, qcfgs, qstrs, translations) -- cgit v1.2.3 From d0f9b5901e37a751a0bf5770c2f26a5c6c039dd4 Mon Sep 17 00:00:00 2001 From: Jeff Epler Date: Thu, 28 May 2020 11:29:28 -0500 Subject: translations: document the compressed format --- py/makeqstrdata.py | 3 +++ supervisor/shared/translate.h | 27 +++++++++++++++++++++++++++ 2 files changed, 30 insertions(+) (limited to 'py/makeqstrdata.py') diff --git a/py/makeqstrdata.py b/py/makeqstrdata.py index 64e4d26f4..df2c687e5 100644 --- a/py/makeqstrdata.py +++ b/py/makeqstrdata.py @@ -2,6 +2,9 @@ Process raw qstr file and output qstr data with length, hash and data bytes. This script works with Python 2.7, 3.3 and 3.4. + +For documentation about the format of compressed translated strings, see +supervisor/shared/translate.h """ from __future__ import print_function diff --git a/supervisor/shared/translate.h b/supervisor/shared/translate.h index 067a44e1f..731b26d12 100644 --- a/supervisor/shared/translate.h +++ b/supervisor/shared/translate.h @@ -29,11 +29,38 @@ #include +// The format of the compressed data is: +// - the size of the uncompressed string in UTF-8 bytes, encoded as a +// (compress_max_length_bits)-bit number. compress_max_length_bits is +// computed during dictionary generation time, and happens to be 8 +// for all current platforms. However, it'll probably end up being +// 9 in some translations sometime in the future. This length excludes +// the trailing NUL, though notably decompress_length includes it. +// +// - followed by the huffman encoding of the individual UTF-16 code +// points that make up the string. The trailing "\0" is not +// represented by a huffman code, but is implied by the length. +// (building the huffman encoding on UTF-16 code points gave better +// compression than building it on UTF-8 bytes) +// +// The "data" / "tail" construct is so that the struct's last member is a +// "flexible array". However, the _only_ member is not permitted to be +// a flexible member, so we have to declare the first byte as a separte +// member of the structure. +// +// For translations where length needs 8 bits, this saves about 1.5 +// bytes per string on average compared to a structure of {uint16_t, +// flexible array}, but is also future-proofed against strings with +// UTF-8 length above 256, with a savings of about 1.375 bytes per +// string. typedef struct { uint8_t data; const uint8_t tail[]; } compressed_string_t; +// Return the compressed, translated version of a source string +// Usually, due to LTO, this is optimized into a load of a constant +// pointer. const compressed_string_t* translate(const char* c); void serial_write_compressed(const compressed_string_t* compressed); char* decompress(const compressed_string_t* compressed, char* decompressed); -- cgit v1.2.3