31 Aug 2020
In an earlier post, I talked about building an rABS entropy decoder on 6502, which became the heart of my new 4k intro packer experiment for C64. While exploring several different entropy coder variants for simple LZ codecs, and in particular tANS or an approximation of it with adaptive probabilities (spoiler alert: this was a dead-end), I realized that rABS was not only a possible alternative, but actually an OK fit for the system, providing a high precision entropy coder with… well, good enough decode speed and a not-as-tricky-as-I-had-originally-feared implementation :) .
However, I intentionally left out several details of the rest of the codec. The earlier post only describes how the entropy decoder is implemented and some of the modeling, the combination of which is kindof the novel thing here. But essentially, it only gives us a way to pull modeled bits out of an encoded bitstream. The bits we actually encode/decode and how we model those is what a codec is really all about; the entropy coding part, while certainly important, is really just a piece of machinery that allows us to build the rest of the codec effectively and take as much advantage of the modeling choices we make as possible.
So, in this post I’d like to go into detail about the rest of the codec, including the LZ scheme chosen, how we model various symbols, how some of these techniques were chosen/tested, and several parts of the encoder. I’ll save the rABS-specific encoding details/intuitions for a future post where I can talk about that specifically in more depth.
23 Mar 2019
Edit 31/08/2020: OK so, I gotta admit, I made some funny mistakes here. For starters, even though I’m quite familiar with the use of [blue] noise/stochastic stuff in rendering/dithering, I somehow completely missed the connection here, which is one of the most obvious oversights I can remember making during my entire programmer life. Ugh. This also explains how I didn’t even think to implement the rounding in the most obvious/best way, which I later outlined in the earlier edit at the bottom of the post. For completeness and documenting my learning journey, I think it’s useful to leave the post up as-is, but yeah - try not to laugh too hard. In any case, I think the actual idea of applying stochastic rounding to model probabilities in compression is something novel (to me at least).
So here’s a little quickie based on something I encountered in my new job :) .
The main motivation is that you’d like to work with lower precision numbers than you typically work with for some reason (typically to reduce storage for some model and ideally do faster calculations). But ofc to do that you need to drop some precision, which involves rounding.
Often times this rounding ends up being a floor or towards-zero round, sometimes a nearest round, but whichever you choose you’re still losing fractional information.
So the idea behind a stochastic round is that you use some random number that decides whether you round up or down, instead of always doing one or the other or taking the closest integer. The critical detail here is that the distribution of that number matches that of the fractional part of the number you’re rounding.
11 Feb 2019
Of the various compression/packer experiments that I’ve toyed with, one of my favorites has to be a rABS-based packer on C64 for 4k intros. It’s an interesting challenge to try and beat state-of-the-art packers for the platform for this use case, and I’m quite pleased with construction I came up with, as well as the results. In particular, the way the decoder is built and how probabilities are modeled are particularly interesting, and that’s what I’d like to focus on in this post.
Quick note: while rANS is a more likely fit for a resource-constrained system like C64, I went with rABS instead, the difference being that we’re going to work with binary symbols. The reason for this is that we typically observe better compression with adaptive modeling, and updating symbol predictions is much, much simpler with a binary alphabet (look ma, no divides!). This of course makes per-symbol decoding much more expensive as we have to break symbols down into individual bit components and perform decoding/model updates on those (so, much more frequently), but for this particular use case, this is a tradeoff worth making for the higher compression ratio achieved.
10 Feb 2019
Hello world!! Time to start another blog. But yeah uhm why?
I’ve been working on a few (particularly compression-related) projects that are difficult to cover nicely in stream format, as I’d like to 1. have the information in writing, which should be easier to digest; and 2. not spend a lot of time preparing for such a stream/series that would be organized enough to be useful. I’d of course still like to do streams on these projects, and plan to do so, but they’d probably be more like high-level overviews with Q&A and would use the relevant blog post(s) as a rough outline and place to point to for learning more.