[daala] Can I implement entropy of AV1 encoder without back-propagation of precarry buffer?

[Timothy B. Terriberry]

Jarek Duda wrote:
> I don't know the details, but might be the one to blame: sounds like an 
> artifact of being able to switch between RC (range coder) and rANS 
> during development (I think Alex Converse was responsible), while 
> finally RC was used.

No, this was actually a totally unrelated software optimization. See 
Section 5.2 of Thomas Davies' 2008 paper "Speeding Up Arithmetic Coding 
and Decoding in the Schroedinger Implementation of Dirac." I can't 
actually find a copy online anymore to link, so I've attached it.

> W dniu 27.07.2020 o 11:07, Knight Kim pisze:
>> Hello,
>>
>> I am implementing entropy HW for AV1 video codec.
>> I want to make the HW with the smallest precarry buffer.
>> Currently, aom encoder is scanning reverse direction adding precarry 
>> to previous buffer point.
>> It means that I should keep all bitstreams in a tile, and scan all the 
>> bitstreams then generate it.
>> At HW point of view, this kind of operation is quite inefficient.
>> Is there any way to implement the entropy encoder without precarry 
>> back-propagation?
>> Can I determine the maximum length of back-propagation?

In general there is no limit to how far a carry can propagate. The 
traditional way to handle this (described, e.g., by witten, Neal, and 
Cleary in their 1987 Communications of the ACM paper, "Arithmetic Coding 
for Data Compression") is to maintain a counter storing how many 
outstanding 1 bits a carry *could* propagate through, in lieu of 
actually outputting those bits. Only once the final value of those bits 
is determined would you actually flush them to the buffer. We don't do 
this in modern software because it puts expensive branches in an inner loop.

In practice you still need to have some maximum in order to know how 
many bits to use for the counter, but it could be as large as the 
maximum number of output bits for a tile, in theory (although this is 
exceedingly unlikely). In practice H.264's CABAC and other entropy 
coders (VP8, VP9, etc.) all require the exact same carry-propagation 
behavior, so whatever you are doing to deal with it for those codecs 
should apply just as easily for AV1.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Davies08-_Speeding_Up_Arithmetic_Coding_and_Decoding_in_the_Schroedinger_Implementation_of_Dirac.pdf
Type: application/pdf
Size: 123626 bytes
Desc: not available
URL: <http://lists.xiph.org/pipermail/daala/attachments/20200727/148bc030/attachment-0001.pdf>