[jkbonfield]

As the author of the CRAM implementationn of rANS, I can say that these sort of articles aren't helpful. Clearly my work predates this by several years, so there is nothing here which can realistically impact on CRAM, however fear alone is sufficient to damage uptake and usage. It's back to the classic strategy of FUD: Fear, Uncertainty, Doubt.

Sadly the patent is woefully vague. I understand RANS and a lot of the optimisations used for doing it efficiently, but I don't understand that patent. It's just not clear enough for someone skilled in that field to know exactly what it is they're patenting.

Specifically rANS states are updated on a symbol by symbol basis. A query is made to get a range, that is looked up to determine the symbol for that range, and then the state is updated and possibly renormalised to fit in the desired range of valid states. There is no whether-or-not a previous symbol was decoded scenario. So I think they're talking at a higher level of block based decoding and using stats from the previous block for decoding the current block, and the possibility of a symbol in the current block not being observed in the previous one (ie escape codes, as used in PPM etc). However I'm really not sure. That's just me grasping at straws trying to think of something that makes sense.

In short, the patent fails the most basic test of being implementable by someone else having read the patent. It's deliberately vague, so they can then apply it to as much of the problem space as possible. That annoys me! As does patenting trivial modifications to rANS that aren't inventive. rANS is just a drop in replacement for the earlier (arithmetic) range-coders, albeit in reverse order. Therefore any tricks and techniques previously applied to range coders can also be applied to rANS. However being the first to do such a thing is no more an invention that the first person to use fiberglass or carbon-fiber in a boring every day item such as a chair. The new material is the invention, not being the first to use it in a particular manner that is obvious to all.