Ryg_rans Is Not a Library

I wrote ryg_rans in 2014. I still regularly get questions and patch submissions from people who want to use it as a library. That is not what it’s for!

ryg_rans is not a library, never was. It’s a toy implementation of an algorithm whose core fits in something like 20 lines of code. It’s the equivalent of the wooden board you sometimes see in hardware stores where they have 30 different types and sizes of fasteners screwed, bolted or nailed in. The idea is not that you should use this in your builds; it’s a visual aid to show you the options available to you. A real project should pick one, or maybe two, options and stick with it.

You should not be using ryg_rans itself for anything. Its goal is to be a small example accompanying my writings on the subject, not to be a rANS encoding/decoding library. It is exceptionally bad at the latter. It is neither particularly optimized for speed (and, indeed, not fast, not even the SIMD versions – they are meant to show the idea, not to be used in production, and are appreciably worse than “proper” implementations), nor robust, nor “batteries included”, and the static model included in the code makes no sense to use with rANS, you would just use tANS instead. The only reason the static byte model is in there is because the code needed something to be a working implementation, and fully static byte-granular, although pointless, is the easiest model.

Our actual uses of rANS in codecs like Oodle LZNA use either the fully adaptive “exponential moving average”-type models described in https://fgiesen.wordpress.com/2015/05/26/models-for-adaptive-arithmetic-coding/ or a semi-static model based on running counts that is updated every few hundred symbols in BitKnit. Some more details in https://fgiesen.wordpress.com/2023/05/06/a-very-brief-bitknit-retrospective/.

Something like the alias table variant is cute but I would strongly advise against ever including it in any production bitstream because there is simply no case I can think of where it’s ever actually a good idea. I wrote it up because I thought it was interesting and that maybe I would come up with a compelling use case for it at some point, but it’s been 12 years and I’m still waiting. The alias encoding requires considerable-size extra tables in the encoder, still forces you into mostly-static models (which loses the main advantage of rANS), and is slow to both encode and decode. If you have a static distribution, tANS/FSE is almost always preferable.

Similarly, do not use multiple encoding/interleaving variants based on SIMD ISA availability in the same bitstream. That is a terrible idea. Again, ryg_rans is a toy example meant to illustrate the ideas in that design space, not a blueprint for a library. If you design a format or actual library, you have to make a choice. Bitstreams are forever, or as near as makes no difference. One of the fundamental problems with all interleaved ANS variants is that the number of interleaved streams is a “magic constant” that significantly constrains implementations. The “sweet spot” is very different between types of machines and microarchitectures, to the extent that e.g. there is no literally overlap between stream counts that make sense for something like a low-end 32-bit ARM microcontroller (like the Cortex M series) and say a GPU.

Having lots of variants in the same bitstream makes everything worse. Now, instead of one encoding that is good for some targets and bad for others, you have multiple encodings, multiple times the code complexity and attack surface, and for every target and application there is usually only one “good” choice of interleaving.

More to the point, an unintended side effect of the static byte models in the examples is that it skews things towards much higher interleave factors that are not actually sustainable in use cases where rANS makes sense. If you use any kind of adaptive model, as you should, because that is the main reason to use rANS, the practical degree of interleaving you can attain is usually limited by the number of independent model updates you can actually sustain before you get back to a model that has an update pending, and that number is frequently something like 2 or 3. While it is true that something like rANS can in principle use very large interleave factors, it is unfortunately not something that makes sense in most practical implementations because of the modeling limitations.

Which brings me to the final point: with rANS, same as with arithmetic encoders, probability modeling and the actual encoding are almost alway intertwined. The static byte model makes it so the two are actually separate, which is convenient for an example implementation, but this is not meant as an endorsement of the idea; it just makes it the obvious choice when writing a series about rANS coding that does not talk about probability modeling, which is an orthogonal concern.

Finally, sometimes I get patches trying to adapt the code to fix certain obvious defects like e.g. the absence of bounds checks. I don’t think being faithful to the bitstream decisions in ryg_rans serves any actual purpose. The ryg_rans bitstream format is quite bad, and I literally spent less than five minutes thinking about it. Once again, this is not something I would recommend. Just toss it out and do your own.

For what it’s worth, here are my actual recommendations if you want to write a rANS implementation:

• There’s no good reason to ever use byte-based renormalization on 32-bit+ targets (that I’ve found, anyway). That variant exists in the code more by analogy with conventional arithmetic/range coders than because there’s anything to recommend it. Use either 32-bit state with 16-bit granular renormalization if you care about 32-bit targets or encode on targets with slow 64-bit integer divides (this is what BitKnit does), or 64-bit state with 32-bit granular renormalization when you don’t.
• For interleaving, implicit interleaving with two alternating states is the sweet spot. It is extremely simple to code in both the encoder and decoder and will usually almost double your coding throughput.
• The same post also covers my preferred encoding/decoding strategy: decoder works forwards, encoder backwards, modeling always forwards. The latter means that the encoder needs to do its probability modeling in forward (“natural”) order and save the coding decisions to a buffer, and then periodically flush them with rANS encoding.
• Do not use the alias table method for anything unless you figure out a way to make it not suck in practice :) – it’s cute, but it’s kind of a mess to encode and slow to decode, so other than the idea being neat it really doesn’t have anything to recommend it, in its current incarnation anyway.
• If your model uses static symbol probabilities, you should probably be using tANS instead (exception: hardware or SIMD use cases where having math instead of gathers is a big advantage).
• For actual adaptive models, the exponential-moving-average type models linked above are, I think, still the sweet spot. Up to 17 symbols can be done quite cheaply with 128-bit SIMD (using 16-bit probability values, but that’s plenty), with 9 (or 8) being marginally cheaper still.
• The super-wide interleaving factors are an interesting curiosity but having that magic constant be baked into the bitstream in a way that makes it slow to decode on anything else (not to mention adding a fair amount of overhead in terms of wasted bits) is a serious problem. It’s not useless, but I’m not happy with it, and I’m not sure that I’d recommend it.

That’s about it!