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

[Jarek Duda]

> What we have is even more flexible
> (conveniently handles non-power-of-two frequency counts), has no
> multiplies at all, and can also take advantage of SIMD.

You are saying that you have multiplication-free large alphabet accurate 
entropy coder (and it is not tANS)?

Sounds very interesting - I was looking at your materials like slides, 
but found only range coding and mentioning CABAC - could you point me to 
some details?
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

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).

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

R_LPS = RTAB[m][(R > > 6) & 3];
R_MPS = R - R_LPS;
if (V < (R_MPS < < BitsLeft))
{R=R_MPS; value=valMPS;
Rnorm = (R_MPS > > 8) XOR 1;}
else
{V = V – (R_MPS < < BitsLeft)
R = R_LPS; value = !valMPS
Rnorm = RnormTAB[R_LPS > > 3];}
R = R << Rnorm;
BitsLeft = BitsLeft - Rnorm;
if (BitsLeft < = 0)
{V = (V < < M_BITS) | read_bits(M_BITS);
BitsLeft = BitsLeft + M_BITS;}

in contrast, here is analogous decoding step for tABS (binary tANS):

t = decodingTable[m][x];
value = valMPS XOR t.symbol;
x = t.newX + read_bits(t.nbBits);

with included renormalization, m is quantized probability of LPS.
For large alphabet tANS decoding step is nearly the same:

t = decodingTable[x];
symbol = t.symbol;
x = t.newX + read_bits(t.nbBits);