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

More efficient translation

2 files changed, 48 insertions, 10 deletions

diff --git a/supervisor/shared/translate.c b/supervisor/shared/translate.c
index 187d5ff8a..606f8fa91 100644
--- a/supervisor/shared/translate.c
+++ b/supervisor/shared/translate.c
@@ -37,7 +37,7 @@
 #include "supervisor/serial.h"
 
 void serial_write_compressed(const compressed_string_t* compressed) {
-    char decompressed[compressed->length];
+    char decompressed[decompress_length(compressed)];
     decompress(compressed, decompressed);
     serial_write(decompressed);
 }
@@ -58,12 +58,22 @@ STATIC int put_utf8(char *buf, int u) {
     }
 }
 
+uint16_t decompress_length(const compressed_string_t* compressed) {
+    if (compress_max_length_bits <= 8) {
+        return 1 + (compressed->data >> (8 - compress_max_length_bits));
+    } else {
+        return 1 + ((compressed->data * 256 + compressed->tail[0]) >> (16 - compress_max_length_bits));
+    }
+}
+
 char* decompress(const compressed_string_t* compressed, char* decompressed) {
-    uint8_t this_byte = 0;
-    uint8_t this_bit = 7;
-    uint8_t b = compressed->data[this_byte];
+    uint8_t this_byte = compress_max_length_bits / 8;
+    uint8_t this_bit = 7 - compress_max_length_bits % 8;
+    uint8_t b = (&compressed->data)[this_byte];
+    uint16_t length = decompress_length(compressed);
+
     // Stop one early because the last byte is always NULL.
-    for (uint16_t i = 0; i < compressed->length - 1;) {
+    for (uint16_t i = 0; i < length - 1;) {
         uint32_t bits = 0;
         uint8_t bit_length = 0;
         uint32_t max_code = lengths[0];
@@ -78,7 +88,7 @@ char* decompress(const compressed_string_t* compressed, char* decompressed) {
             if (this_bit == 0) {
                 this_bit = 7;
                 this_byte += 1;
-                b = compressed->data[this_byte]; // This may read past the end but its never used.
+                b = (&compressed->data)[this_byte]; // This may read past the end but its never used.
             } else {
                 this_bit -= 1;
             }
@@ -91,14 +101,14 @@ char* decompress(const compressed_string_t* compressed, char* decompressed) {
         i += put_utf8(decompressed + i, values[searched_length + bits - max_code]);
     }
 
-    decompressed[compressed->length-1] = '\0';
+    decompressed[length-1] = '\0';
     return decompressed;
 }
 
 inline __attribute__((always_inline)) const compressed_string_t* translate(const char* original) {
     #ifndef NO_QSTR
     #define QDEF(id, str)
-    #define TRANSLATION(id, len, compressed...) if (strcmp(original, id) == 0) { static const compressed_string_t v = {.length = len, .data = compressed}; return &v; } else
+    #define TRANSLATION(id, firstbyte, ...) if (strcmp(original, id) == 0) { static const compressed_string_t v = { .data = firstbyte, .tail = { __VA_ARGS__ } }; return &v; } else
     #include "genhdr/qstrdefs.generated.h"
     #undef TRANSLATION
     #undef QDEF
diff --git a/supervisor/shared/translate.h b/supervisor/shared/translate.h
index 5e8acbb6a..731b26d12 100644
--- a/supervisor/shared/translate.h
+++ b/supervisor/shared/translate.h
@@ -29,13 +29,41 @@
 
 #include <stdint.h>
 
+// 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 {
-    uint16_t length;
-    const uint8_t data[];
+    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);
+uint16_t decompress_length(const compressed_string_t* compressed);
 
 #endif  // MICROPY_INCLUDED_SUPERVISOR_TRANSLATE_H