Compress all translated strings with Huffman coding.

This saves code space in builds which use link-time optimization.
The optimization drops the untranslated strings and replaces them
with a compressed_string_t struct. It can then be decompressed to
a c string.

Builds without LTO work as well but include both untranslated
strings and compressed strings.

This work could be expanded to include QSTRs and loaded strings if
a compress method is added to C. Its tracked in #531.

2 files changed, 59 insertions, 6 deletions

diff --git a/supervisor/shared/translate.c b/supervisor/shared/translate.c
index 570b4501e..1f338befc 100644
--- a/supervisor/shared/translate.c
+++ b/supervisor/shared/translate.c
@@ -26,17 +26,61 @@
 
 #include "supervisor/shared/translate.h"
 
+#include <stdbool.h>
+#include <stdint.h>
 #include <string.h>
 
-inline __attribute__((always_inline)) const char* translate(const char* c) {
+#ifndef NO_QSTR
+#include "genhdr/compression.generated.h"
+#endif
+
+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];
+    // Stop one early because the last byte is always NULL.
+    for (uint16_t i = 0; i < compressed->length - 1; i++) {
+        uint32_t bits = 0;
+        uint8_t bit_length = 0;
+        uint32_t max_code = lengths[0];
+        uint32_t searched_length = lengths[0];
+        while (true) {
+            bits <<= 1;
+            if ((0x80 & b) != 0) {
+                bits |= 1;
+            }
+            b <<= 1;
+            bit_length += 1;
+            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.
+            } else {
+                this_bit -= 1;
+            }
+            if (max_code > 0 && bits < max_code) {
+                break;
+            }
+            max_code = (max_code << 1) + lengths[bit_length];
+            searched_length += lengths[bit_length];
+        }
+        decompressed[i] = values[searched_length + bits - max_code];
+    }
+
+    decompressed[compressed->length-1] = '\0';
+    return decompressed;
+}
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wreturn-local-addr"
+inline __attribute__((always_inline)) const compressed_string_t* translate(const char* original) {
     #ifndef NO_QSTR
     #define QDEF(id, str)
-    #define TRANSLATION(id, str) if (strcmp(c, id) == 0) { return str; } else
+    #define TRANSLATION(id, len, compressed...) if (strcmp(original, id) == 0) { static compressed_string_t v = {.length = len, .data = compressed}; return &v; } else
     #include "genhdr/qstrdefs.generated.h"
     #undef TRANSLATION
     #undef QDEF
     #endif
-    {
-        return "";
-    }
+    return NULL;
 }
+#pragma GCC diagnostic pop
diff --git a/supervisor/shared/translate.h b/supervisor/shared/translate.h
index bd474e7eb..3a1ba4076 100644
--- a/supervisor/shared/translate.h
+++ b/supervisor/shared/translate.h
@@ -27,6 +27,15 @@
 #ifndef MICROPY_INCLUDED_SUPERVISOR_TRANSLATE_H
 #define MICROPY_INCLUDED_SUPERVISOR_TRANSLATE_H
 
-const char* translate(const char* c);
+#include <stdint.h>
+
+typedef struct {
+    uint16_t length;
+    const uint8_t data[];
+} compressed_string_t;
+
+const compressed_string_t* translate(const char* c);
+
+char* decompress(const compressed_string_t* compressed, char* decompressed);
 
 #endif  // MICROPY_INCLUDED_SUPERVISOR_TRANSLATE_H