This post is set in the same cinematic universe as my previous post about Lua string. Alisa replaced Huffman encoding with rANS, and she needed to store a list of relatively small 16-bit integers, most of which fit into 6 or 7 bits, that has a lot of zeros, and only a handful of really big numbers greater than 10 bits. This list needs to be stored alongside the compressed data, and needs to be somehow restored programmatically with as little code as posssible.
Here are the possible ideas.
Native Lua lists like { 1, 2, 3 } are probably the first idea,
but they have very low density, especially for sequences of zeros
(yeah I'd like to waste 16 bits per zero, please)
and for relatively large numbers
(yeah I'd like to store 16-bit number with 48 bits).
This method is not that bad, as it does not need any special decoding. You just, y'know, use the list you have.
If we look at the previous method, we see that it has a minimal overhead of 16 bits per element.
Encoding a 16-bit element with at least 16 bits per element seems suboptimal,
so why not dump a sequence of bytes and use string.unpack?
Barring minor issues with bytes with value of 13[1], this seems like a good baseline. That unfortunately still uses 16 bits per null elements, and we have a lot of these. A good analogy might be that we're storing mostly ASCII text in UTF-16 and expect it not to be suboptimal, except that our ASCII text is a bit outnumbered by literal zeros.
There is a way of storing batches of equal elements, it's called RLE, and there is a way of storing integers of variable lengths in a more optimal way than by allocating full width, it's called a varint.
Technically, a decimal notation as used in the Lua list approach is a varint, it's just optimized for readability instead of storage.
Protobuf uses base-128 varints, with sign bit indicating whether there's more bytes coming. Unfortunately, this kind of varint requires some decoding code, and we'd need to fit RLE0[2] somewhere. It would probably work, but it already feels messy.
What if there was some support for varints in your language? Wouldn't it be nice to use it instead of ad-hocing another standard...
UTF-8 spends more bits per value than might be needed (compare its 6-byte encoding of 2^32-1 with UTF-1), but most programming languages nowadays support UTF-8 strings in one way or another and allow iterating over its codepoints, making it a good built-in varint.
This includes Lua, which includes UTF-8 library since version 5.3,
which also conveniently provides utf8.codes iterator and
a clone of string.byte named utf8.codepoint.
And for _, p in utf8.codes(_) is so succinct,
that it might be the smallest varint decoder in Lua.
There is again, some nuance.
Rust chars are Unicode scalar values, which have a glaring hole in the middle,
making 0..0xD800 and 0xE000..0x110000 the valid ranges.
This gap occurs in the lower 16 bits, as surrogates are a UTF-16 feature.
Lua does not care about surrogate pairs and unpaired surrogates,
and is happy to treat UTF-8 as a varint with range from 0 to 0x10FFFF inclusive.
Semantically, it's possible to soft-cap values at 0xD7FF, so that they don't overflow,
and use some codepoints starting from 0xD800 as RLE0.
We settled on an alternative solution,
which is saying we have 14-bit values now instead of 16-bit values,
and using normal codepoints from 0x4000 as RLE0.
I have learned somewhere (or I'm making it up lol) that if a cheap-to-decode built-in varint is needed, one might have luck at trying UTF-8.
I have originally suggested this as a joke, knowing that it has potential to yield good results and has obscenely short decoder. Little did I know that we couldn't come up with anything to beat it (yet?).
Think outside the box and try weird ideas; some of them might even work.