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.

14 files changed, 257 insertions, 75 deletions

diff --git a/py/compile.c b/py/compile.c
index c4f447c56..1218aa07e 100644
--- a/py/compile.c
+++ b/py/compile.c
@@ -156,7 +156,7 @@ STATIC void compile_error_set_line(compiler_t *comp, mp_parse_node_t pn) {
     }
 }
 
-STATIC void compile_syntax_error(compiler_t *comp, mp_parse_node_t pn, const char *msg) {
+STATIC void compile_syntax_error(compiler_t *comp, mp_parse_node_t pn, const compressed_string_t *msg) {
     // only register the error if there has been no other error
     if (comp->compile_error == MP_OBJ_NULL) {
         comp->compile_error = mp_obj_new_exception_msg(&mp_type_SyntaxError, msg);
@@ -949,7 +949,7 @@ STATIC void compile_del_stmt(compiler_t *comp, mp_parse_node_struct_t *pns) {
 
 STATIC void compile_break_cont_stmt(compiler_t *comp, mp_parse_node_struct_t *pns) {
     uint16_t label;
-    const char *error_msg;
+    const compressed_string_t *error_msg;
     if (MP_PARSE_NODE_STRUCT_KIND(pns) == PN_break_stmt) {
         label = comp->break_label;
         error_msg = translate("'break' outside loop");
diff --git a/py/makeqstrdata.py b/py/makeqstrdata.py
index adf065c72..ea8629ef3 100644
--- a/py/makeqstrdata.py
+++ b/py/makeqstrdata.py
@@ -12,6 +12,10 @@ import sys
 import collections
 import gettext
 
+sys.path.append("../../tools/huffman")
+
+import huffman
+
 # Python 2/3 compatibility:
 #   - iterating through bytes is different
 #   - codepoint2name lives in a different module
@@ -83,9 +87,144 @@ def translate(translation_file, i18ns):
             unescaped = original
             for s in C_ESCAPES:
                 unescaped = unescaped.replace(C_ESCAPES[s], s)
-            translations.append((original, table.gettext(unescaped)))
+            translation = table.gettext(unescaped)
+            # Add in carriage returns to work in terminals
+            translation = translation.replace("\n", "\r\n")
+            translations.append((original, translation))
         return translations
 
+def compute_huffman_coding(translations, qstrs, compression_filename):
+    all_strings = [x[1] for x in translations]
+
+    # go through each qstr and print it out
+    for _, _, qstr in qstrs.values():
+        all_strings.append(qstr)
+    all_strings_concat = "".join(all_strings).encode("utf-8")
+    counts = collections.Counter(all_strings_concat)
+    # add other values
+    for i in range(256):
+        if i not in counts:
+            counts[i] = 0
+    cb = huffman.codebook(counts.items())
+    values = bytearray()
+    length_count = {}
+    renumbered = 0
+    last_l = None
+    canonical = {}
+    for ch, code in sorted(cb.items(), key=lambda x: (len(x[1]), x[0])):
+        values.append(ch)
+        l = len(code)
+        if l not in length_count:
+            length_count[l] = 0
+        length_count[l] += 1
+        if last_l:
+            renumbered <<= (l - last_l)
+        canonical[ch] = '{0:0{width}b}'.format(renumbered, width=l)
+        if chr(ch) in C_ESCAPES:
+            s = C_ESCAPES[chr(ch)]
+        else:
+            s = chr(ch)
+        print("//", ch, s, counts[ch], canonical[ch], renumbered)
+        renumbered += 1
+        last_l = l
+    lengths = bytearray()
+    for i in range(1, max(length_count) + 1):
+        lengths.append(length_count.get(i, 0))
+    print("//", values, lengths)
+    with open(compression_filename, "w") as f:
+        f.write("const uint8_t lengths[] = {{ {} }};\n".format(", ".join(map(str, lengths))))
+        f.write("const uint8_t values[256] = {{ {} }};\n".format(", ".join(map(str, values))))
+    return values, lengths
+
+def decompress(encoding_table, length, encoded):
+    values, lengths = encoding_table
+    #print(l, encoded)
+    dec = bytearray(length)
+    this_byte = 0
+    this_bit = 7
+    b = encoded[this_byte]
+    for i in range(length):
+        bits = 0
+        bit_length = 0
+        max_code = lengths[0]
+        searched_length = lengths[0]
+        while True:
+            bits <<= 1
+            if 0x80 & b:
+                bits |= 1
+
+            b <<= 1
+            bit_length += 1
+            if this_bit == 0:
+                this_bit = 7
+                this_byte += 1
+                if this_byte < len(encoded):
+                    b = encoded[this_byte]
+            else:
+                this_bit -= 1
+            if max_code > 0 and bits < max_code:
+                #print('{0:0{width}b}'.format(bits, width=bit_length))
+                break
+            max_code = (max_code << 1) + lengths[bit_length]
+            searched_length += lengths[bit_length]
+
+        v = values[searched_length + bits - max_code]
+        dec[i] = v
+    return dec
+
+def compress(encoding_table, decompressed):
+    if not isinstance(decompressed, bytes):
+        raise TypeError()
+    values, lengths = encoding_table
+    enc = bytearray(len(decompressed))
+    #print(decompressed)
+    #print(lengths)
+    current_bit = 7
+    current_byte = 0
+    for c in decompressed:
+        #print()
+        #print("char", c, values.index(c))
+        start = 0
+        end = lengths[0]
+        bits = 1
+        compressed = None
+        code = 0
+        while compressed is None:
+            s = start
+            e = end
+            #print("{0:0{width}b}".format(code, width=bits))
+            # Binary search!
+            while e > s:
+                midpoint = (s + e) // 2
+                #print(s, e, midpoint)
+                if values[midpoint] == c:
+                    compressed = code + (midpoint - start)
+                    #print("found {0:0{width}b}".format(compressed, width=bits))
+                    break
+                elif c < values[midpoint]:
+                    e = midpoint
+                else:
+                    s = midpoint + 1
+            code += end - start
+            code <<= 1
+            start = end
+            end += lengths[bits]
+            bits += 1
+            #print("next bit", bits)
+
+        for i in range(bits - 1, 0, -1):
+            if compressed & (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
+    if current_bit != 7:
+        current_byte += 1
+    return enc[:current_byte]
+
 def qstr_escape(qst):
     def esc_char(m):
         c = ord(m.group(0))
@@ -178,7 +317,7 @@ def make_bytes(cfg_bytes_len, cfg_bytes_hash, qstr):
     qhash_str = ('\\x%02x' * cfg_bytes_hash) % tuple(((qhash >> (8 * i)) & 0xff) for i in range(cfg_bytes_hash))
     return '(const byte*)"%s%s" "%s"' % (qhash_str, qlen_str, qdata)
 
-def print_qstr_data(qcfgs, qstrs, i18ns):
+def print_qstr_data(encoding_table, qcfgs, qstrs, i18ns):
     # get config variables
     cfg_bytes_len = int(qcfgs['BYTES_IN_LEN'])
     cfg_bytes_hash = int(qcfgs['BYTES_IN_HASH'])
@@ -191,6 +330,7 @@ def print_qstr_data(qcfgs, qstrs, i18ns):
     print('QDEF(MP_QSTR_NULL, (const byte*)"%s%s" "")' % ('\\x00' * cfg_bytes_hash, '\\x00' * cfg_bytes_len))
 
     total_qstr_size = 0
+    total_qstr_compressed_size = 0
     # go through each qstr and print it out
     for order, ident, qstr in sorted(qstrs.values(), key=lambda x: x[0]):
         qbytes = make_bytes(cfg_bytes_len, cfg_bytes_hash, qstr)
@@ -198,17 +338,23 @@ def print_qstr_data(qcfgs, qstrs, i18ns):
         total_qstr_size += len(qstr)
 
     total_text_size = 0
+    total_text_compressed_size = 0
     for original, translation in i18ns:
-        # Add in carriage returns to work in terminals
-        translation = translation.replace("\n", "\r\n")
-        for s in C_ESCAPES:
-            translation = translation.replace(s, C_ESCAPES[s])
-        print("TRANSLATION(\"{}\", \"{}\")".format(original, translation))
-        total_text_size += len(translation)
+        translation_encoded = translation.encode("utf-8")
+        compressed = compress(encoding_table, translation_encoded)
+        total_text_compressed_size += len(compressed)
+        decompressed = decompress(encoding_table, len(translation_encoded), compressed).decode("utf-8")
+        for c in C_ESCAPES:
+            decompressed.replace(c, C_ESCAPES[c])
+        #print("// \"{}\"".format(translation))
+        print("TRANSLATION(\"{}\", {}, {{ {} }}) // {}".format(original, len(translation_encoded)+1, ", ".join(["0x{:02x}".format(x) for x in compressed]), decompressed))
+        total_text_size += len(translation.encode("utf-8"))
 
     print()
     print("// {} bytes worth of qstr".format(total_qstr_size))
     print("// {} bytes worth of translations".format(total_text_size))
+    print("// {} bytes worth of translations compressed".format(total_text_compressed_size))
+    print("// {} bytes saved".format(total_text_size - total_text_compressed_size))
 
 def print_qstr_enums(qstrs):
     # print out the starter of the generated C header file
@@ -230,12 +376,15 @@ if __name__ == "__main__":
                         help='an integer for the accumulator')
     parser.add_argument('--translation', default=None, type=str,
                         help='translations for i18n() items')
+    parser.add_argument('--compression_filename', default=None, type=str,
+                        help='header for compression info')
 
     args = parser.parse_args()
 
     qcfgs, qstrs, i18ns = parse_input_headers(args.infiles)
     if args.translation:
         translations = translate(args.translation, i18ns)
-        print_qstr_data(qcfgs, qstrs, translations)
+        encoding_table = compute_huffman_coding(translations, qstrs, args.compression_filename)
+        print_qstr_data(encoding_table, qcfgs, qstrs, translations)
     else:
         print_qstr_enums(qstrs)
diff --git a/py/modbuiltins.c b/py/modbuiltins.c
index 4b24e8811..fc7ec24c7 100644
--- a/py/modbuiltins.c
+++ b/py/modbuiltins.c
@@ -316,7 +316,7 @@ MP_DEFINE_CONST_FUN_OBJ_KW(mp_builtin_min_obj, 1, mp_builtin_min);
 STATIC mp_obj_t mp_builtin_next(mp_obj_t o) {
     mp_obj_t ret = mp_iternext_allow_raise(o);
     if (ret == MP_OBJ_STOP_ITERATION) {
-        mp_raise_msg(&mp_type_StopIteration, "");
+        mp_raise_msg(&mp_type_StopIteration, NULL);
     } else {
         return ret;
     }
diff --git a/py/moduerrno.c b/py/moduerrno.c
index 1b925dfc9..255c1a73e 100644
--- a/py/moduerrno.c
+++ b/py/moduerrno.c
@@ -102,20 +102,6 @@ const mp_obj_module_t mp_module_uerrno = {
 };
 
 const char* mp_errno_to_str(mp_obj_t errno_val) {
-    // For commonly encountered errors, return human readable strings
-    if (MP_OBJ_IS_SMALL_INT(errno_val)) {
-        switch (MP_OBJ_SMALL_INT_VALUE(errno_val)) {
-            case EPERM:  return translate("Permission denied");
-            case ENOENT: return translate("No such file/directory");
-            case EIO:    return translate("Input/output error");
-            case EACCES: return translate("Permission denied");
-            case EEXIST: return translate("File exists");
-            case ENODEV: return translate("Unsupported operation");
-            case EINVAL: return translate("Invalid argument");
-            case EROFS:  return translate("Read-only filesystem");
-        }
-    }
-
     // Otherwise, return the Exxxx string for that error code
     #if MICROPY_PY_UERRNO_ERRORCODE
     // We have the errorcode dict so can do a lookup using the hash map
@@ -148,3 +134,21 @@ const char* mp_errno_to_str(mp_obj_t errno_val) {
 }
 
 #endif //MICROPY_PY_UERRNO
+
+
+// For commonly encountered errors, return human readable strings
+const compressed_string_t* mp_common_errno_to_str(mp_obj_t errno_val) {
+    if (MP_OBJ_IS_SMALL_INT(errno_val)) {
+        switch (MP_OBJ_SMALL_INT_VALUE(errno_val)) {
+            case EPERM:  return translate("Permission denied");
+            case ENOENT: return translate("No such file/directory");
+            case EIO:    return translate("Input/output error");
+            case EACCES: return translate("Permission denied");
+            case EEXIST: return translate("File exists");
+            case ENODEV: return translate("Unsupported operation");
+            case EINVAL: return translate("Invalid argument");
+            case EROFS:  return translate("Read-only filesystem");
+        }
+    }
+    return NULL;
+}
diff --git a/py/mperrno.h b/py/mperrno.h
index c530ab183..876b090b5 100644
--- a/py/mperrno.h
+++ b/py/mperrno.h
@@ -141,5 +141,7 @@
 #endif
 
 const char* mp_errno_to_str(mp_obj_t errno_val);
+// For commonly encountered errors, return compressed human readable strings
+const compressed_string_t* mp_common_errno_to_str(mp_obj_t errno_val);
 
 #endif // MICROPY_INCLUDED_PY_MPERRNO_H
diff --git a/py/obj.c b/py/obj.c
index 72bf9bda1..35a7519bb 100644
--- a/py/obj.c
+++ b/py/obj.c
@@ -86,19 +86,35 @@ void mp_obj_print_exception(const mp_print_t *print, mp_obj_t exc) {
         mp_obj_exception_get_traceback(exc, &n, &values);
         if (n > 0) {
             assert(n % 3 == 0);
-            mp_print_str(print, translate("Traceback (most recent call last):\n"));
+            // Decompress the format strings
+            const compressed_string_t* traceback = translate("Traceback (most recent call last):\n");
+            char decompressed[traceback->length];
+            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];
+            decompress(frame, decompressed_frame);
+            const compressed_string_t* block_fmt = translate(", in %q\n");
+            char decompressed_block[block_fmt->length];
+            decompress(block_fmt, decompressed_block);
+
+            // Print the traceback
+            mp_print_str(print, decompressed);
             for (int i = n - 3; i >= 0; i -= 3) {
 #if MICROPY_ENABLE_SOURCE_LINE
-                mp_printf(print, translate("  File \"%q\", line %d"), values[i], (int)values[i + 1]);
+                mp_printf(print, decompressed_frame, values[i], (int)values[i + 1]);
 #else
-                mp_printf(print, translate("  File \"%q\""), values[i]);
+                mp_printf(print, decompressed_frame, values[i]);
 #endif
                 // the block name can be NULL if it's unknown
                 qstr block = values[i + 2];
                 if (block == MP_QSTR_NULL) {
                     mp_print_str(print, "\n");
                 } else {
-                    mp_printf(print, translate(", in %q\n"), block);
+                    mp_printf(print, decompressed_block, block);
                 }
             }
         }
diff --git a/py/obj.h b/py/obj.h
index 6d314e461..143751cbf 100644
--- a/py/obj.h
+++ b/py/obj.h
@@ -34,6 +34,8 @@
 #include "py/mpprint.h"
 #include "py/runtime0.h"
 
+#include "supervisor/shared/translate.h"
+
 // This is the definition of the opaque MicroPython object type.
 // All concrete objects have an encoding within this type and the
 // particular encoding is specified by MICROPY_OBJ_REPR.
@@ -639,9 +641,9 @@ mp_obj_t mp_obj_new_complex(mp_float_t real, mp_float_t imag);
 mp_obj_t mp_obj_new_exception(const mp_obj_type_t *exc_type);
 mp_obj_t mp_obj_new_exception_arg1(const mp_obj_type_t *exc_type, mp_obj_t arg);
 mp_obj_t mp_obj_new_exception_args(const mp_obj_type_t *exc_type, size_t n_args, const mp_obj_t *args);
-mp_obj_t mp_obj_new_exception_msg(const mp_obj_type_t *exc_type, const char *msg);
-mp_obj_t mp_obj_new_exception_msg_varg(const mp_obj_type_t *exc_type, const char *fmt, ...); // counts args by number of % symbols in fmt, excluding %%; can only handle void* sizes (ie no float/double!)
-mp_obj_t mp_obj_new_exception_msg_vlist(const mp_obj_type_t *exc_type, const char *fmt, va_list ap); // counts args by number of % symbols in fmt, excluding %%; can only handle void* sizes (ie no float/double!)
+mp_obj_t mp_obj_new_exception_msg(const mp_obj_type_t *exc_type, const compressed_string_t *msg);
+mp_obj_t mp_obj_new_exception_msg_varg(const mp_obj_type_t *exc_type, const compressed_string_t *fmt, ...); // counts args by number of % symbols in fmt, excluding %%; can only handle void* sizes (ie no float/double!)
+mp_obj_t mp_obj_new_exception_msg_vlist(const mp_obj_type_t *exc_type, const compressed_string_t *fmt, va_list ap); // counts args by number of % symbols in fmt, excluding %%; can only handle void* sizes (ie no float/double!)
 mp_obj_t mp_obj_new_fun_bc(mp_obj_t def_args, mp_obj_t def_kw_args, const byte *code, const mp_uint_t *const_table);
 mp_obj_t mp_obj_new_fun_native(mp_obj_t def_args_in, mp_obj_t def_kw_args, const void *fun_data, const mp_uint_t *const_table);
 mp_obj_t mp_obj_new_fun_viper(size_t n_args, void *fun_data, mp_uint_t type_sig);
diff --git a/py/objexcept.c b/py/objexcept.c
index 68897d44d..f211f19a3 100644
--- a/py/objexcept.c
+++ b/py/objexcept.c
@@ -114,7 +114,15 @@ void mp_obj_exception_print(const mp_print_t *print, mp_obj_t o_in, mp_print_kin
         } else if (o->args->len == 1) {
             // try to provide a nice OSError error message
             if (o->base.type == &mp_type_OSError && MP_OBJ_IS_SMALL_INT(o->args->items[0])) {
-                const char* msg = mp_errno_to_str(o->args->items[0]);
+                const compressed_string_t* common = mp_common_errno_to_str(o->args->items[0]);
+                const char* msg;
+                if (common != NULL) {
+                    char decompressed[common->length];
+                    decompress(common, decompressed);
+                    msg = decompressed;
+                } else {
+                    msg = mp_errno_to_str(o->args->items[0]);
+                }
                 if (msg[0] != '\0') {
                     mp_printf(print, "[Errno " INT_FMT "] %s", MP_OBJ_SMALL_INT_VALUE(o->args->items[0]), msg);
                     return;
@@ -311,7 +319,7 @@ mp_obj_t mp_obj_new_exception_args(const mp_obj_type_t *exc_type, size_t n_args,
     return exc_type->make_new(exc_type, n_args, 0, args);
 }
 
-mp_obj_t mp_obj_new_exception_msg(const mp_obj_type_t *exc_type, const char *msg) {
+mp_obj_t mp_obj_new_exception_msg(const mp_obj_type_t *exc_type, const compressed_string_t *msg) {
     return mp_obj_new_exception_msg_varg(exc_type, msg);
 }
 
@@ -349,7 +357,7 @@ STATIC void exc_add_strn(void *data, const char *str, size_t len) {
 }
 
 
-mp_obj_t mp_obj_new_exception_msg_varg(const mp_obj_type_t *exc_type, const char *fmt, ...) {
+mp_obj_t mp_obj_new_exception_msg_varg(const mp_obj_type_t *exc_type, const compressed_string_t *fmt, ...) {
     va_list ap;
     va_start(ap, fmt);
     mp_obj_t exception = mp_obj_new_exception_msg_vlist(exc_type, fmt, ap);
@@ -357,7 +365,7 @@ mp_obj_t mp_obj_new_exception_msg_varg(const mp_obj_type_t *exc_type, const char
     return exception;
 }
 
-mp_obj_t mp_obj_new_exception_msg_vlist(const mp_obj_type_t *exc_type, const char *fmt, va_list ap) {
+mp_obj_t mp_obj_new_exception_msg_vlist(const mp_obj_type_t *exc_type, const compressed_string_t *fmt, va_list ap) {
     assert(fmt != NULL);
 
     // Check that the given type is an exception type
@@ -365,7 +373,7 @@ mp_obj_t mp_obj_new_exception_msg_vlist(const mp_obj_type_t *exc_type, const cha
 
     // 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 = strlen(fmt) + 1;
+    size_t o_str_alloc = fmt->length + 1;
     byte *o_str_buf = m_new_maybe(byte, o_str_alloc);
 
     bool used_emg_buf = false;
@@ -391,15 +399,16 @@ mp_obj_t mp_obj_new_exception_msg_vlist(const mp_obj_type_t *exc_type, const cha
     }
 
     if (o_str_buf == NULL) {
-        // No memory for the string buffer: assume that the fmt string is in ROM
-        // and use that data as the data of the string
-        o_str->len = o_str_alloc - 1; // will be equal to strlen(fmt)
-        o_str->data = (const byte*)fmt;
+        // No memory for the string buffer: the string is compressed so don't add it.
+        o_str->len = 0;
+        o_str->data = NULL;
     } else {
         // 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};
-        mp_vprintf(&print, fmt, ap);
+        char fmt_decompressed[fmt->length];
+        decompress(fmt, fmt_decompressed);
+        mp_vprintf(&print, fmt_decompressed, ap);
         exc_pr.buf[exc_pr.len] = '\0';
         o_str->len = exc_pr.len;
         o_str->data = exc_pr.buf;
diff --git a/py/parsenum.c b/py/parsenum.c
index f6d419b91..6ef309b47 100644
--- a/py/parsenum.c
+++ b/py/parsenum.c
@@ -148,11 +148,11 @@ overflow:
 value_error:
     if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_TERSE) {
         mp_obj_t exc = mp_obj_new_exception_msg(&mp_type_ValueError,
-            "invalid syntax for integer");
+            translate("invalid syntax for integer"));
         raise_exc(exc, lex);
     } else if (MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_NORMAL) {
         mp_obj_t exc = mp_obj_new_exception_msg_varg(&mp_type_ValueError,
-            "invalid syntax for integer with base %d", base);
+            translate("invalid syntax for integer with base %d"), base);
         raise_exc(exc, lex);
     } else {
         vstr_t vstr;
@@ -328,7 +328,7 @@ mp_obj_t mp_parse_num_decimal(const char *str, size_t len, bool allow_imag, bool
     }
 #else
     if (imag || force_complex) {
-        raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, "complex values not supported"), lex);
+        raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, translate("complex values not supported")), lex);
     }
 #endif
     else {
@@ -336,9 +336,9 @@ mp_obj_t mp_parse_num_decimal(const char *str, size_t len, bool allow_imag, bool
     }
 
 value_error:
-    raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, "invalid syntax for number"), lex);
+    raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, translate("invalid syntax for number")), lex);
 
 #else
-    raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, "decimal numbers not supported"), lex);
+    raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, translate("decimal numbers not supported")), lex);
 #endif
 }
diff --git a/py/py.mk b/py/py.mk
index dcaa0e805..9874dde4d 100644
--- a/py/py.mk
+++ b/py/py.mk
@@ -315,7 +315,7 @@ $(HEADER_BUILD)/qstrdefs.enum.h: $(PY_SRC)/makeqstrdata.py $(HEADER_BUILD)/qstrd
 # the lines in "" and then unwrap after the preprocessor is finished.
 $(HEADER_BUILD)/qstrdefs.generated.h: $(PY_SRC)/makeqstrdata.py $(HEADER_BUILD)/$(TRANSLATION).mo $(HEADER_BUILD)/qstrdefs.preprocessed.h
 	$(STEPECHO) "GEN $@"
-	$(PYTHON3) $(PY_SRC)/makeqstrdata.py --translation $(HEADER_BUILD)/$(TRANSLATION).mo $(HEADER_BUILD)/qstrdefs.preprocessed.h > $@
+	$(PYTHON3) $(PY_SRC)/makeqstrdata.py --compression_filename $(HEADER_BUILD)/compression.generated.h --translation $(HEADER_BUILD)/$(TRANSLATION).mo $(HEADER_BUILD)/qstrdefs.preprocessed.h > $@
 
 $(PY_BUILD)/qstr.o: $(HEADER_BUILD)/qstrdefs.generated.h
 
diff --git a/py/qstr.c b/py/qstr.c
index 90581664c..eea57c1e0 100755
--- a/py/qstr.c
+++ b/py/qstr.c
@@ -104,7 +104,7 @@ const qstr_pool_t mp_qstr_const_pool = {
     {
 #ifndef NO_QSTR
 #define QDEF(id, str) str,
-#define TRANSLATION(id, str)
+#define TRANSLATION(id, length, compressed...)
 #include "genhdr/qstrdefs.generated.h"
 #undef TRANSLATION
 #undef QDEF
diff --git a/py/runtime.c b/py/runtime.c
index 20e3e578e..3d7a97f58 100644
--- a/py/runtime.c
+++ b/py/runtime.c
@@ -1539,7 +1539,7 @@ NORETURN void m_malloc_fail(size_t num_bytes) {
         translate("memory allocation failed, allocating %u bytes"), (uint)num_bytes);
 }
 
-NORETURN void mp_raise_msg(const mp_obj_type_t *exc_type, const char *msg) {
+NORETURN void mp_raise_msg(const mp_obj_type_t *exc_type, const compressed_string_t *msg) {
     if (msg == NULL) {
         nlr_raise(mp_obj_new_exception(exc_type));
     } else {
@@ -1547,7 +1547,7 @@ NORETURN void mp_raise_msg(const mp_obj_type_t *exc_type, const char *msg) {
     }
 }
 
-NORETURN void mp_raise_msg_varg(const mp_obj_type_t *exc_type, const char *fmt, ...) {
+NORETURN void mp_raise_msg_varg(const mp_obj_type_t *exc_type, const compressed_string_t *fmt, ...) {
     va_list argptr;
     va_start(argptr,fmt);
     mp_obj_t exception = mp_obj_new_exception_msg_vlist(exc_type, fmt, argptr);
@@ -1555,27 +1555,27 @@ NORETURN void mp_raise_msg_varg(const mp_obj_type_t *exc_type, const char *fmt,
     nlr_raise(exception);
 }
 
-NORETURN void mp_raise_AttributeError(const char *msg) {
+NORETURN void mp_raise_AttributeError(const compressed_string_t *msg) {
     mp_raise_msg(&mp_type_AttributeError, msg);
 }
 
-NORETURN void mp_raise_RuntimeError(const char *msg) {
+NORETURN void mp_raise_RuntimeError(const compressed_string_t *msg) {
     mp_raise_msg(&mp_type_RuntimeError, msg);
 }
 
-NORETURN void mp_raise_ImportError(const char *msg) {
+NORETURN void mp_raise_ImportError(const compressed_string_t *msg) {
     mp_raise_msg(&mp_type_ImportError, msg);
 }
 
-NORETURN void mp_raise_IndexError(const char *msg) {
+NORETURN void mp_raise_IndexError(const compressed_string_t *msg) {
     mp_raise_msg(&mp_type_IndexError, msg);
 }
 
-NORETURN void mp_raise_ValueError(const char *msg) {
+NORETURN void mp_raise_ValueError(const compressed_string_t *msg) {
     mp_raise_msg(&mp_type_ValueError, msg);
 }
 
-NORETURN void mp_raise_ValueError_varg(const char *fmt, ...) {
+NORETURN void mp_raise_ValueError_varg(const compressed_string_t *fmt, ...) {
     va_list argptr;
     va_start(argptr,fmt);
     mp_obj_t exception = mp_obj_new_exception_msg_vlist(&mp_type_ValueError, fmt, argptr);
@@ -1583,11 +1583,11 @@ NORETURN void mp_raise_ValueError_varg(const char *fmt, ...) {
     nlr_raise(exception);
 }
 
-NORETURN void mp_raise_TypeError(const char *msg) {
+NORETURN void mp_raise_TypeError(const compressed_string_t *msg) {
     mp_raise_msg(&mp_type_TypeError, msg);
 }
 
-NORETURN void mp_raise_TypeError_varg(const char *fmt, ...) {
+NORETURN void mp_raise_TypeError_varg(const compressed_string_t *fmt, ...) {
     va_list argptr;
     va_start(argptr,fmt);
     mp_obj_t exception = mp_obj_new_exception_msg_vlist(&mp_type_TypeError, fmt, argptr);
@@ -1600,7 +1600,7 @@ NORETURN void mp_raise_OSError(int errno_) {
 }
 
 
-NORETURN void mp_raise_NotImplementedError(const char *msg) {
+NORETURN void mp_raise_NotImplementedError(const compressed_string_t *msg) {
     mp_raise_msg(&mp_type_NotImplementedError, msg);
 }
 
diff --git a/py/runtime.h b/py/runtime.h
index 95f89ee9e..9c7ffc02f 100644
--- a/py/runtime.h
+++ b/py/runtime.h
@@ -147,18 +147,18 @@ mp_obj_t mp_import_name(qstr name, mp_obj_t fromlist, mp_obj_t level);
 mp_obj_t mp_import_from(mp_obj_t module, qstr name);
 void mp_import_all(mp_obj_t module);
 
-NORETURN void mp_raise_msg(const mp_obj_type_t *exc_type, const char *msg);
-NORETURN void mp_raise_msg_varg(const mp_obj_type_t *exc_type, const char *fmt, ...);
-NORETURN void mp_raise_ValueError(const char *msg);
-NORETURN void mp_raise_ValueError_varg(const char *fmt, ...);
-NORETURN void mp_raise_TypeError(const char *msg);
-NORETURN void mp_raise_TypeError_varg(const char *fmt, ...);
-NORETURN void mp_raise_AttributeError(const char *msg);
-NORETURN void mp_raise_RuntimeError(const char *msg);
-NORETURN void mp_raise_ImportError(const char *msg);
-NORETURN void mp_raise_IndexError(const char *msg);
+NORETURN void mp_raise_msg(const mp_obj_type_t *exc_type, const compressed_string_t *msg);
+NORETURN void mp_raise_msg_varg(const mp_obj_type_t *exc_type, const compressed_string_t *fmt, ...);
+NORETURN void mp_raise_ValueError(const compressed_string_t *msg);
+NORETURN void mp_raise_ValueError_varg(const compressed_string_t *fmt, ...);
+NORETURN void mp_raise_TypeError(const compressed_string_t *msg);
+NORETURN void mp_raise_TypeError_varg(const compressed_string_t *fmt, ...);
+NORETURN void mp_raise_AttributeError(const compressed_string_t *msg);
+NORETURN void mp_raise_RuntimeError(const compressed_string_t *msg);
+NORETURN void mp_raise_ImportError(const compressed_string_t *msg);
+NORETURN void mp_raise_IndexError(const compressed_string_t *msg);
 NORETURN void mp_raise_OSError(int errno_);
-NORETURN void mp_raise_NotImplementedError(const char *msg);
+NORETURN void mp_raise_NotImplementedError(const compressed_string_t *msg);
 NORETURN void mp_raise_recursion_depth(void);
 
 #if MICROPY_BUILTIN_METHOD_CHECK_SELF_ARG
diff --git a/py/vm.c b/py/vm.c
index 498ecb491..72d0d0d60 100644
--- a/py/vm.c
+++ b/py/vm.c
@@ -252,7 +252,7 @@ dispatch_loop:
                     if (obj_shared == MP_OBJ_NULL) {
                         local_name_error: {
                             MARK_EXC_IP_SELECTIVE();
-                            mp_obj_t obj = mp_obj_new_exception_msg(&mp_type_NameError, "local variable referenced before assignment");
+                            mp_obj_t obj = mp_obj_new_exception_msg(&mp_type_NameError, translate("local variable referenced before assignment"));
                             RAISE(obj);
                         }
                     }
@@ -1139,7 +1139,7 @@ unwind_return:
                             }
                         }
                         if (obj == MP_OBJ_NULL) {
-                            obj = mp_obj_new_exception_msg(&mp_type_RuntimeError, "no active exception to reraise");
+                            obj = mp_obj_new_exception_msg(&mp_type_RuntimeError, translate("no active exception to reraise"));
                             RAISE(obj);
                         }
                     } else {
@@ -1281,7 +1281,7 @@ yield:
                     } else
 #endif
                 {
-                    mp_obj_t obj = mp_obj_new_exception_msg(&mp_type_NotImplementedError, "byte code not implemented");
+                    mp_obj_t obj = mp_obj_new_exception_msg(&mp_type_NotImplementedError, translate("byte code not implemented"));
                     nlr_pop();
                     fastn[0] = obj;
                     return MP_VM_RETURN_EXCEPTION;