[daala] Why not upgrading Daala range coding with much faster rANS or tANS?

[Timothy B. Terriberry]

Jarek Duda wrote:
> but found only range coding and mentioning CABAC - could you point me to
> some details?

Sure: 
<https://tools.ietf.org/html/draft-terriberry-netvc-codingtools-00#section-2>. 
The interesting bits for what you are after probably start in Section 2.3.

> How fast is its encoding/decoding?
> Maybe you could put it in some benchmarks, like
> http://encode.ru/threads/1920-In-memory-open-source-benchmark-of-entropy-coders

That wouldn't really tell us much useful, because of course what's in 
that benchmark is not how an entropy coder is used in a video codec. The 
relevant test would be to put your alternative into Daala.

> As I see it, sure we could put some behavior of range coding into a
> table like divide[R][s]={L',R'}, where R is the current range length, s
> is symbol, but
> - it would be limited to a small range (poor accuracy) and number of
> symbols (not true for ANS),
> - you still need to add quite nontrivial renormalization (ANS
> renormalization is trivial, like 4 byte "if(x < 2^32) x = x<<32 |
> read32bits()" for rANS),
> - modifying frequencies for adaptation would be terribly costly (for
> rANS it is really cheap, see e.g. LZNA).

Yeah, none of those things apply here. Read the draft. Maybe you can 
argue about the renormalization, but ours is pretty cheap. I have no 
doubt it could be made faster with 64-bit arithmetic, but at the moment 
portability to platforms without fast 64-bit operations (e.g., 16-bit 
DSPs) is more important. LZNA's frequency adaptation is described in 
Section 2.2 of the draft I linked (and was there in the initial version 
published in October 2012), but honestly at this point we don't even 
bother. We just use frequency counts that sum to non-powers-of-2, which 
are even cheaper. We'll revisit that later on, probably, but as I said, 
we're focused on improving quality/bit first.

> Regarding mentioned CABAC - here is its optimized decoding step from
> http://iphome.hhi.de/marpe/download/iwk06_marpe_et_al.pdf

CABAC is heavily patented and thus not relevant.