Merge pull request #3398 from jepler/better-dictionary-compression

compression: Implement @ciscorn's dictionary approach

2 files changed, 28 insertions, 6 deletions

diff --git a/supervisor/shared/translate.c b/supervisor/shared/translate.c
index 5cd7b8dd8..44544c98d 100644
--- a/supervisor/shared/translate.c
+++ b/supervisor/shared/translate.c
@@ -47,13 +47,22 @@ STATIC int put_utf8(char *buf, int u) {
     if(u <= 0x7f) {
         *buf = u;
         return 1;
-    } else if(bigram_start <= u && u <= bigram_end) {
-        int n = (u - 0x80) * 2;
-        // (note that at present, entries in the bigrams table are
-        // guaranteed not to represent bigrams themselves, so this adds
+    } else if(word_start <= u && u <= word_end) {
+        uint n = (u - word_start);
+        size_t pos = 0;
+        if (n > 0) {
+            pos = wends[n - 1] + (n * 2);
+        }
+        int ret = 0;
+        // note that at present, entries in the words table are
+        // guaranteed not to represent words themselves, so this adds
         // at most 1 level of recursive call
-        int ret = put_utf8(buf, bigrams[n]);
-        return ret + put_utf8(buf + ret, bigrams[n+1]);
+        for(; pos < wends[n] + (n + 1) * 2; pos++) {
+            int len = put_utf8(buf, words[pos]);
+            buf += len;
+            ret += len;
+        }
+        return ret;
     } else if(u <= 0x07ff) {
         *buf++ = 0b11000000 | (u >> 6);
         *buf   = 0b10000000 | (u & 0b00111111);
diff --git a/supervisor/shared/translate.h b/supervisor/shared/translate.h
index 731b26d12..16296a416 100644
--- a/supervisor/shared/translate.h
+++ b/supervisor/shared/translate.h
@@ -43,6 +43,19 @@
 //   (building the huffman encoding on UTF-16 code points gave better
 //   compression than building it on UTF-8 bytes)
 //
+// - code points starting at 128 (word_start) and potentially extending
+//   to 255 (word_end) (but never interfering with the target
+//   language's used code points) stand for dictionary entries in a
+//   dictionary with size up to 256 code points.  The dictionary entries
+//   are computed with a heuristic based on frequent substrings of 2 to
+//   9 code points.  These are called "words" but are not, grammatically
+//   speaking, words.  They're just spans of code points that frequently
+//   occur together.
+//
+// - dictionary entries are non-overlapping, and the _ending_ index of each
+//   entry is stored in an array.  Since the index given is the ending
+//   index, the array is called "wends".
+//
 // 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