> What is really interesting is combining FIFO with simplicity of ANS for large alphabet
Actually I'm still intending to use rangecoders for a while.
Most of rANS optimizations are easily applicable to rc,
and there's basically no difference in performance for binary alphabets.
Also, most non-linear model components (FSM counters, logistic mixing, SSE, etc)
are not compatible with non-binary alphabets anyway,
so I think its more important to look for speed optimizations for binary coders
instead, rather than just being happy about vectorized order0 models.
But if you want a FIFO ANS, I might have some ideas.
Well, its obvious that order reversing is inherent if you
want to use state'=state*SCALE+symbol.low updates.
Its the same as converting decimal to binary basically -
you can do FIFO decoding if you know all the coefs...
which you might actually know if you use a combinatoric model.
However, in that case either encoding would have to look like
or decoding like
bit = state/LUT[freq0,freq1]%SCALE > probability;
So if you require
decoding: symbol=LUT[state%SCALE]; state/=SCALE;
Then its obvious that the order would be inverted.
1) We can combine ANS w/o renorm with a high-precision rangecoder, like
this rc supports 64-bit symbol intervals, so we can encode 64-bit
rANS states with it, and its possible to pack quite a lot into 64 bits.
For example, it can be 4 bytes with a 16-bit freqtable.
Note that the number of ANS instances in this case is potentially unlimited,
because ANS states would be properly packed.
2) As I already mentioned, the "payload" in ANS state update
doesn't have to come from this specific state.
I mean, you always use
But the important part is actually
while the log2(symbol.range) bits of payload can be taken anywhere,
like from another block of data, or another interleaved stream at least.