[daala] daala Digest, Vol 24, Issue 2

Tue Jul 28 08:51:53 UTC 2020

Hi,

This is Knight.

I looked into the PDF you attached.
It looks like I used 5.1 method on previous codec developments.
But it seems only 1 bit processing is allowed. Maybe it will affect overall
entropy performance.

I referenced google aom entropy encoder.
This can process 1 symbol per cycle, like 5.2 in your doc, if you change
the 1bit shift expander to lshift_cnt.
---------------------------------------------
lshift_cnt = 15 - get_msb(range);
low = low << lshift_cnt;
range = range << lshift_cnt;
---------------------------------------------

I am considering the carry process will be like below.
Just count all 1s bytes, and then add carry at carry occurred position.
Then reset the carry count, and monitor another all 1s byte.

[image: image.png]
In order to satisfy this scenario, carry value should be '1' always.
If it's bigger than '1', I cannot use this scenario. Maybe I have to
replace this with 5.1 on your doc.

Could you tell me what is the maximum number of carry value?
Do you think the scenario ablove could work? or other way to supplement it?

Thank you.
Knight.

2020년 7월 28일 (화) 오전 7:48, <daala-request at xiph.org>님이 작성:

> Send daala mailing list submissions to
>         daala at xiph.org
>
> To subscribe or unsubscribe via the World Wide Web, visit
>         http://lists.xiph.org/mailman/listinfo/daala
> or, via email, send a message with subject or body 'help' to
>         daala-request at xiph.org
>
> You can reach the person managing the list at
>         daala-owner at xiph.org
>
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of daala digest..."
>
>
> Today's Topics:
>
>    1. Re: Can I implement entropy of AV1 encoder without
>       back-propagation of precarry buffer? (Timothy B. Terriberry)
>
>
> ----------------------------------------------------------------------
>
> Message: 1
> Date: Mon, 27 Jul 2020 14:54:59 -0700
> From: "Timothy B. Terriberry" <tterriberry at mozilla.com>
> To: Jarek Duda <dudajar at gmail.com>, daala at xiph.org
> Subject: Re: [daala] Can I implement entropy of AV1 encoder without
>         back-propagation of precarry buffer?
> Message-ID: <3c41971f-b803-7d3b-1b02-5bfa7488b20d at xiph.org>
> Content-Type: text/plain; charset="utf-8"; Format="flowed"
>
> 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.pdf
> >
>
> ------------------------------
>
> Subject: Digest Footer
>
> _______________________________________________
> daala mailing list
> daala at xiph.org
> http://lists.xiph.org/mailman/listinfo/daala
>
>
> ------------------------------
>
> End of daala Digest, Vol 24, Issue 2
> ************************************
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.xiph.org/pipermail/daala/attachments/20200728/0a690542/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 17902 bytes
Desc: not available
URL: <http://lists.xiph.org/pipermail/daala/attachments/20200728/0a690542/attachment-0001.png>