Merge pull request #2968 from jepler/more-efficient-translation

More efficient translation

5 files changed, 55 insertions, 16 deletions

diff --git a/py/builtinhelp.c b/py/builtinhelp.c
index 9a3407a16..01c0bc84e 100644
--- a/py/builtinhelp.c
+++ b/py/builtinhelp.c
@@ -135,7 +135,7 @@ STATIC void mp_help_print_modules(void) {
 
     // let the user know there may be other modules available from the filesystem
     const compressed_string_t* compressed = translate("Plus any modules on the filesystem\n");
-    char decompressed[compressed->length];
+    char decompressed[decompress_length(compressed)];
     decompress(compressed, decompressed);
     mp_print_str(MP_PYTHON_PRINTER, decompressed);
 }
@@ -181,7 +181,7 @@ STATIC mp_obj_t mp_builtin_help(size_t n_args, const mp_obj_t *args) {
         // print a general help message. Translate only works on single strings on one line.
         const compressed_string_t* compressed =
             translate("Welcome to Adafruit CircuitPython %s!\n\nPlease visit learn.adafruit.com/category/circuitpython for project guides.\n\nTo list built-in modules please do `help(\"modules\")`.\n");
-        char decompressed[compressed->length];
+        char decompressed[decompress_length(compressed)];
         decompress(compressed, decompressed);
         mp_printf(MP_PYTHON_PRINTER, decompressed, MICROPY_GIT_TAG);
     } else {
diff --git a/py/makeqstrdata.py b/py/makeqstrdata.py
index 0d667959d..df2c687e5 100644
--- a/py/makeqstrdata.py
+++ b/py/makeqstrdata.py
@@ -1,7 +1,10 @@
 """
 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.
+
+For documentation about the format of compressed translated strings, see
+supervisor/shared/translate.h
 """
 
 from __future__ import print_function
@@ -132,19 +135,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 +191,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 +204,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 +377,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 +423,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)
diff --git a/py/moduerrno.c b/py/moduerrno.c
index 7915603e4..3be5adba1 100644
--- a/py/moduerrno.c
+++ b/py/moduerrno.c
@@ -158,7 +158,7 @@ const char *mp_common_errno_to_str(mp_obj_t errno_val, char *buf, size_t len) {
         case ENOSPC: desc = translate("No space left on device"); break;
         case EROFS:  desc = translate("Read-only filesystem"); break;
     }
-    if (desc != NULL && desc->length <= len) {
+    if (desc != NULL && decompress_length(desc) <= len) {
         decompress(desc, buf);
         return buf;
     }
diff --git a/py/obj.c b/py/obj.c
index f1e00de1a..4fa2032dc 100644
--- a/py/obj.c
+++ b/py/obj.c
@@ -94,17 +94,17 @@ void mp_obj_print_exception(const mp_print_t *print, mp_obj_t exc) {
             assert(n % 3 == 0);
             // Decompress the format strings
             const compressed_string_t* traceback = translate("Traceback (most recent call last):\n");
-            char decompressed[traceback->length];
+            char decompressed[decompress_length(traceback)];
             decompress(traceback, decompressed);
 #if MICROPY_ENABLE_SOURCE_LINE
             const compressed_string_t* frame = translate("  File \"%q\", line %d");
 #else
             const compressed_string_t* frame = translate("  File \"%q\"");
 #endif
-            char decompressed_frame[frame->length];
+            char decompressed_frame[decompress_length(frame)];
             decompress(frame, decompressed_frame);
             const compressed_string_t* block_fmt = translate(", in %q\n");
-            char decompressed_block[block_fmt->length];
+            char decompressed_block[decompress_length(block_fmt)];
             decompress(block_fmt, decompressed_block);
 
             // Print the traceback
diff --git a/py/objexcept.c b/py/objexcept.c
index b7a536c5e..796be122f 100644
--- a/py/objexcept.c
+++ b/py/objexcept.c
@@ -400,7 +400,7 @@ mp_obj_t mp_obj_new_exception_msg_vlist(const mp_obj_type_t *exc_type, const com
 
     // Try to allocate memory for the message
     mp_obj_str_t *o_str = m_new_obj_maybe(mp_obj_str_t);
-    size_t o_str_alloc = fmt->length + 1;
+    size_t o_str_alloc = decompress_length(fmt);
     byte *o_str_buf = m_new_maybe(byte, o_str_alloc);
 
     bool used_emg_buf = false;
@@ -433,7 +433,7 @@ mp_obj_t mp_obj_new_exception_msg_vlist(const mp_obj_type_t *exc_type, const com
         // We have some memory to format the string
         struct _exc_printer_t exc_pr = {!used_emg_buf, o_str_alloc, 0, o_str_buf};
         mp_print_t print = {&exc_pr, exc_add_strn};
-        char fmt_decompressed[fmt->length];
+        char fmt_decompressed[decompress_length(fmt)];
         decompress(fmt, fmt_decompressed);
         mp_vprintf(&print, fmt_decompressed, ap);
         exc_pr.buf[exc_pr.len] = '\0';