Optimizing Lua string literals to save 400 bytes

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.

[1] https://github.com/madler/zlib/blob/develop/contrib/puff/puf...

[2] https://blog.cloudflare.com/improving-compression-with-prese...

> 125 KB of disk space on a diskette.

> I use SI prefixes for bytes. You should too!

The prefix for 1000 is lowercase.

I do something similar, embed large compressed data blocks as Lua string literals in some project, and I've just given up and used

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.

> 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:

    Lua 5.2.4  Copyright (C) 1994-2015 Lua.org, PUC-Rio
    > print [=[meow [=[ mrrp]=]
    meow [=[ mrrp

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.

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...