I built a benchmark harness for exploring compression of Lua script source files embedded in a Lua app binary as individual static constant C arrays. I settled on gzip, specifically deflate/inflate. Deflate does as well or better for small source files compared to xz, bzip2, and zstd.[0] More importantly, the inflate algorithm is tiny[1]; embedding the zstd decompressor blew up the binary.
I also explored building precomputed dictionaries, which means you can easily embed the files individually (C source file inclusion and runtime loading through the Lua C API remains relatively straight-forward compared to gymnastics of parsing and transforming preprocessed files) while getting similar compression ratios as when compressing an enormous file (e.g. a concatenation of all the source files). This is trivial with the zstd reference utility. It's also simple for deflate, though you have to roll your own dictionary builder by hacking the zlib implementation, or just writing it from scratch[2]. But I never bothered implementing it beyond the benchmark harness. I probably would have stuck with deflate rather than switching to zstd just because the compiled inflate implementation is so small.
[0] This is because the greatest advantage of the alternatives over deflate is the larger dictionary size they build up; deflate has a very small, upper bound. But for short inputs this advantage is diminished.
How small are we talking? We've had great success with bzip-style compression on ~400 KB (about 20% better than gzip), but I don't know if it scales well. It's also relatively fast to decode (something like 2x slower than DEFLATE, IIRC).
I was also considering other approaches, specifically GLZA (https://encode.su/threads/2427-GLZA) looks promising. I think it should be well-suited for code due to its design, and it seems to produce better results than bzip on LTCB (https://mattmahoney.net/dc/text.html), and with a faster decompression time.
Very small, less than a few kilobytes, and many less than 1KB. I was compressing and embedding Lua source files individually. There were smarter ways to do it if I cared about overall size, but doing it per file kept the build simple. I spent way more time on the compression test harness, which was more about satisfying my curiosity and penchant for diversion than anything :) I did the tests after the actual embedding work.
> Raw strings are started by [=[ (any number of =s) and terminated by ]=] (same number of =s) and must contain neither their starter nor their terminator. This makes [=[meow [=[ mrrp]=] an invalid string, but [[meow [=[ mrrp]] is valid.
That's not right. You can include the start delimiter in the string:
Another note that this doesn't cover is ending with a part of the ending terminator. For instance, if you want to encode the string `foo]`, you can't just put it in zero-equal-sign long delimiters, because you'll have `[[foo]]]`, which fails because you actually have a trailing bracket. The same as if you have the string `]]foo]=`, so you use one equal sign, having `[=[]]foo]=]=]`, leaving you with a trailing `=]`. You need to consider partial end delimiters as well.
Another couple considerations from the reference manual:
> Literals in this bracketed form can run for several lines, do not interpret any escape sequences, and ignore long brackets of any other level. Any kind of end-of-line sequence (carriage return, newline, carriage return followed by newline, or newline followed by carriage return) is converted to a simple newline. When the opening long bracket is immediately followed by a newline, the newline is not included in the string.
So you can't just use the bracketed form to encode arbitrary byte sequences, even checking for the delimiters inside, if you care about the exact representation of line breaks (including if you're packing binary data into a literal lua source file, which you can otherwise do, as lua source files can contain arbitrary bytes), you have to be very careful with the bracketed form for that. Leading newlines are also removed.
So, to put an arbitrary sequence of bytes into a Lua string, you have these general options:
1. Encode the string into an ASCII form (such as base64) and set it as a string literal, and include a decoding step.
2. Encode it into a bracket-delimited string literal, scanning ahead of time to be sure you are using the right number of equal signs based on the enclosed closing brackets (including the ending), and deal with losing all carriage returns and having adjacent carriage returns and line feeds collapsed.
3. Put it as a single-or-double-quoted string literal, and escape the quote delimiter, carriage returns, line feeds, and backslashes.
This works for PUC Lua from 5.2+. I don't know about jlua or forks of that, though. Generally, Option 1 is the best for readable sources, 3 is the best for arbitrary payloads and compactness (but often makes your source file not actually a text file), and 2 is best for actual text where you don't care about the literal shape of the newlines.
Thanks! I relayed this to Yuki and we'll make sure to fix the issues.
> You can include the start delimiter in the string:
At first I had no clue why we thought that didn't work, in fact, my prototype had a fun commit specifically about adding opening brackets:
-while b"]" + b"=" * level + b"]" in obj:
+# Somewhat surprisingly, Lua forbids even opening brackets inside brackets.
+while b"[" + b"=" * level + b"[" in obj or b"]" + b"=" * level + b"]" in obj:
...but I think I've figured out the problem. It seems like Lua 5.1 specifically forbids level-0 opening brackets within level-0 strings:
> print [[ a [[b c ]]
stdin:1: nesting of [[...]] is deprecated near '['
...and Cobalt implements this check for compatibility. So that's another edge case to handle, I guess.
> Another note that this doesn't cover is ending with a part of the ending terminator.
That's very useful to know, thanks!
> So you can't just use the bracketed form to encode arbitrary byte sequences, [...] if you care about the exact representation of line breaks
That's right, and the post actually covers how we resolved that closer to the end. In a nutshell, we replace CRs with an escape character, and then use a bitset to denote which symbols are supposed to be CRs and which ones are literal characters. It's not quite a string literal per se, but it's rather cheap in runtime and minimizes file size.
interesting! have you tried putting the compressed payload into a large block comment at the end/start of the file, and recovering it by loading your own source as bytes to prevent the compiler from mangling the payload? I'm not sure if that would work but could be worth a try...
We considered it, but that requires knowing the path to the file and being able to open it, which I don't think is possible in general (e.g. if the file is loaded with `loadstring`, or if it's loaded from tmpfs and then deleted, etc.).
I also explored building precomputed dictionaries, which means you can easily embed the files individually (C source file inclusion and runtime loading through the Lua C API remains relatively straight-forward compared to gymnastics of parsing and transforming preprocessed files) while getting similar compression ratios as when compressing an enormous file (e.g. a concatenation of all the source files). This is trivial with the zstd reference utility. It's also simple for deflate, though you have to roll your own dictionary builder by hacking the zlib implementation, or just writing it from scratch[2]. But I never bothered implementing it beyond the benchmark harness. I probably would have stuck with deflate rather than switching to zstd just because the compiled inflate implementation is so small.
[0] This is because the greatest advantage of the alternatives over deflate is the larger dictionary size they build up; deflate has a very small, upper bound. But for short inputs this advantage is diminished.
[1] https://github.com/madler/zlib/blob/develop/contrib/puff/puf...
[2] https://blog.cloudflare.com/improving-compression-with-prese...
How small are we talking? We've had great success with bzip-style compression on ~400 KB (about 20% better than gzip), but I don't know if it scales well. It's also relatively fast to decode (something like 2x slower than DEFLATE, IIRC).
I was also considering other approaches, specifically GLZA (https://encode.su/threads/2427-GLZA) looks promising. I think it should be well-suited for code due to its design, and it seems to produce better results than bzip on LTCB (https://mattmahoney.net/dc/text.html), and with a faster decompression time.
> I use SI prefixes for bytes. You should too!
The prefix for 1000 is lowercase.
lua_string_literal = string.format("%q", compressor(data))
I don't know if that's available in Cobalt, but for standard Lua I like the compromise, it's not /that/ wasteful.
That's not right. You can include the start delimiter in the string:
Another note that this doesn't cover is ending with a part of the ending terminator. For instance, if you want to encode the string `foo]`, you can't just put it in zero-equal-sign long delimiters, because you'll have `[[foo]]]`, which fails because you actually have a trailing bracket. The same as if you have the string `]]foo]=`, so you use one equal sign, having `[=[]]foo]=]=]`, leaving you with a trailing `=]`. You need to consider partial end delimiters as well.Another couple considerations from the reference manual:
> Literals in this bracketed form can run for several lines, do not interpret any escape sequences, and ignore long brackets of any other level. Any kind of end-of-line sequence (carriage return, newline, carriage return followed by newline, or newline followed by carriage return) is converted to a simple newline. When the opening long bracket is immediately followed by a newline, the newline is not included in the string.
So you can't just use the bracketed form to encode arbitrary byte sequences, even checking for the delimiters inside, if you care about the exact representation of line breaks (including if you're packing binary data into a literal lua source file, which you can otherwise do, as lua source files can contain arbitrary bytes), you have to be very careful with the bracketed form for that. Leading newlines are also removed.
So, to put an arbitrary sequence of bytes into a Lua string, you have these general options:
1. Encode the string into an ASCII form (such as base64) and set it as a string literal, and include a decoding step.
2. Encode it into a bracket-delimited string literal, scanning ahead of time to be sure you are using the right number of equal signs based on the enclosed closing brackets (including the ending), and deal with losing all carriage returns and having adjacent carriage returns and line feeds collapsed.
3. Put it as a single-or-double-quoted string literal, and escape the quote delimiter, carriage returns, line feeds, and backslashes.
This works for PUC Lua from 5.2+. I don't know about jlua or forks of that, though. Generally, Option 1 is the best for readable sources, 3 is the best for arbitrary payloads and compactness (but often makes your source file not actually a text file), and 2 is best for actual text where you don't care about the literal shape of the newlines.
> You can include the start delimiter in the string:
At first I had no clue why we thought that didn't work, in fact, my prototype had a fun commit specifically about adding opening brackets:
...but I think I've figured out the problem. It seems like Lua 5.1 specifically forbids level-0 opening brackets within level-0 strings: ...and Cobalt implements this check for compatibility. So that's another edge case to handle, I guess.> Another note that this doesn't cover is ending with a part of the ending terminator.
That's very useful to know, thanks!
> So you can't just use the bracketed form to encode arbitrary byte sequences, [...] if you care about the exact representation of line breaks
That's right, and the post actually covers how we resolved that closer to the end. In a nutshell, we replace CRs with an escape character, and then use a bitset to denote which symbols are supposed to be CRs and which ones are literal characters. It's not quite a string literal per se, but it's rather cheap in runtime and minimizes file size.