<div dir="ltr">Hi,<div><br></div><div>This is Knight.</div><div><br></div><div>I looked into the PDF you attached.</div><div>It looks like I used 5.1 method on previous codec developments.</div><div>But it seems only 1 bit processing is allowed. Maybe it will affect overall entropy performance.</div><div><br></div><div>I referenced google aom entropy encoder. </div><div>This can process 1 symbol per cycle, like 5.2 in your doc, if you change the 1bit shift expander to lshift_cnt.</div><div>---------------------------------------------</div><div>lshift_cnt = 15 - get_msb(range);</div><div>low = low << lshift_cnt;</div><div>range = range << lshift_cnt;</div><div>---------------------------------------------</div><div><br></div><div>I am considering the carry process will be like below.</div><div>Just count all 1s bytes, and then add carry at carry occurred position.</div><div>Then reset the carry count, and monitor another all 1s byte.</div><div><br></div><div><div><img src="cid:ii_kd5oomqp0" alt="image.png" width="426" height="362" style="margin-right: 0px;"><br></div></div><div>In order to satisfy this scenario, carry value should be '1' always.</div><div>If it's bigger than '1', I cannot use this scenario. Maybe I have to replace this with 5.1 on your doc.</div><div><br></div><div>Could you tell me what is the maximum number of carry value?</div><div>Do you think the scenario ablove could work? or other way to supplement it?</div><div><br></div><div>Thank you.</div><div>Knight.</div><div><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">2020년 7월 28일 (화) 오전 7:48, <<a href="mailto:daala-request@xiph.org">daala-request@xiph.org</a>>님이 작성:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Send daala mailing list submissions to<br>
        <a href="mailto:daala@xiph.org" target="_blank">daala@xiph.org</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
        <a href="http://lists.xiph.org/mailman/listinfo/daala" rel="noreferrer" target="_blank">http://lists.xiph.org/mailman/listinfo/daala</a><br>
or, via email, send a message with subject or body 'help' to<br>
        <a href="mailto:daala-request@xiph.org" target="_blank">daala-request@xiph.org</a><br>
<br>
You can reach the person managing the list at<br>
        <a href="mailto:daala-owner@xiph.org" target="_blank">daala-owner@xiph.org</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than "Re: Contents of daala digest..."<br>
<br>
<br>
Today's Topics:<br>
<br>
   1. Re: Can I implement entropy of AV1 encoder without<br>
      back-propagation of precarry buffer? (Timothy B. Terriberry)<br>
<br>
<br>
----------------------------------------------------------------------<br>
<br>
Message: 1<br>
Date: Mon, 27 Jul 2020 14:54:59 -0700<br>
From: "Timothy B. Terriberry" <<a href="mailto:tterriberry@mozilla.com" target="_blank">tterriberry@mozilla.com</a>><br>
To: Jarek Duda <<a href="mailto:dudajar@gmail.com" target="_blank">dudajar@gmail.com</a>>, <a href="mailto:daala@xiph.org" target="_blank">daala@xiph.org</a><br>
Subject: Re: [daala] Can I implement entropy of AV1 encoder without<br>
        back-propagation of precarry buffer?<br>
Message-ID: <<a href="mailto:3c41971f-b803-7d3b-1b02-5bfa7488b20d@xiph.org" target="_blank">3c41971f-b803-7d3b-1b02-5bfa7488b20d@xiph.org</a>><br>
Content-Type: text/plain; charset="utf-8"; Format="flowed"<br>
<br>
Jarek Duda wrote:<br>
> I don't know the details, but might be the one to blame: sounds like an <br>
> artifact of being able to switch between RC (range coder) and rANS <br>
> during development (I think Alex Converse was responsible), while <br>
> finally RC was used.<br>
<br>
No, this was actually a totally unrelated software optimization. See <br>
Section 5.2 of Thomas Davies' 2008 paper "Speeding Up Arithmetic Coding <br>
and Decoding in the Schroedinger Implementation of Dirac." I can't <br>
actually find a copy online anymore to link, so I've attached it.<br>
<br>
> W dniu 27.07.2020 o 11:07, Knight Kim pisze:<br>
>> Hello,<br>
>><br>
>> I am implementing entropy HW for AV1 video codec.<br>
>> I want to make the HW with the smallest precarry buffer.<br>
>> Currently, aom encoder is scanning reverse direction adding precarry <br>
>> to previous buffer point.<br>
>> It means that I should keep all bitstreams in a tile, and scan all the <br>
>> bitstreams then generate it.<br>
>> At HW point of view, this kind of operation is quite inefficient.<br>
>> Is there any way to implement the entropy encoder without precarry <br>
>> back-propagation?<br>
>> Can I determine the maximum length of back-propagation?<br>
<br>
In general there is no limit to how far a carry can propagate. The <br>
traditional way to handle this (described, e.g., by witten, Neal, and <br>
Cleary in their 1987 Communications of the ACM paper, "Arithmetic Coding <br>
for Data Compression") is to maintain a counter storing how many <br>
outstanding 1 bits a carry *could* propagate through, in lieu of <br>
actually outputting those bits. Only once the final value of those bits <br>
is determined would you actually flush them to the buffer. We don't do <br>
this in modern software because it puts expensive branches in an inner loop.<br>
<br>
In practice you still need to have some maximum in order to know how <br>
many bits to use for the counter, but it could be as large as the <br>
maximum number of output bits for a tile, in theory (although this is <br>
exceedingly unlikely). In practice H.264's CABAC and other entropy <br>
coders (VP8, VP9, etc.) all require the exact same carry-propagation <br>
behavior, so whatever you are doing to deal with it for those codecs <br>
should apply just as easily for AV1.<br>
-------------- next part --------------<br>
A non-text attachment was scrubbed...<br>
Name: Davies08-_Speeding_Up_Arithmetic_Coding_and_Decoding_in_the_Schroedinger_Implementation_of_Dirac.pdf<br>
Type: application/pdf<br>
Size: 123626 bytes<br>
Desc: not available<br>
URL: <<a href="http://lists.xiph.org/pipermail/daala/attachments/20200727/148bc030/attachment.pdf" rel="noreferrer" target="_blank">http://lists.xiph.org/pipermail/daala/attachments/20200727/148bc030/attachment.pdf</a>><br>
<br>
------------------------------<br>
<br>
Subject: Digest Footer<br>
<br>
_______________________________________________<br>
daala mailing list<br>
<a href="mailto:daala@xiph.org" target="_blank">daala@xiph.org</a><br>
<a href="http://lists.xiph.org/mailman/listinfo/daala" rel="noreferrer" target="_blank">http://lists.xiph.org/mailman/listinfo/daala</a><br>
<br>
<br>
------------------------------<br>
<br>
End of daala Digest, Vol 24, Issue 2<br>
************************************<br>
</blockquote></div>