Re: [Cellar] Barry Leiba's Discuss on draft-ietf-cellar-ffv1-17: (with DISCUSS and COMMENT)

[Michael Niedermayer <[e-mail]>]

On Thu, Dec 03, 2020 at 06:46:48PM -0500, Dave Rice wrote:
> Hi Barry,
> Thanks so much for your comments.
> 
> > On Dec 2, 2020, at 5:43 PM, Barry Leiba <[e-mail]> wrote:
> > 
> > OK, Dave, here's where I am with 3.8.1.x:
> > 
> > — Section 3.8.1 —
> > 
> >   CABAC was replaced by a Range coder based on an algorithm defined by
> >   G. Nigel N. Martin in 1979 [range-coding].
> > 
> > Keep in mind as you read my comments below that I’m not versed in this
> > field at all, I am not familiar with Range coding, and can’t easily
> > look up the reference.  Ha… but after typing that, I just did: I found
> > it here:
> > http://sachingarg.com/compression/entropy_coding/range_coder.pdf
> > 
> > Maybe it would help to add that URI to the reference?  Anyway, again,
> > this isn’t my area, so it’s valid to say, for any of this below, that
> > someone actually implementing this would already understand these
> > things.
> 
> We had some discussion on this at https://github.com/FFmpeg/FFV1/pull/219 and  considered adding a reference to http://www.compressconsult.com/rangecoder/#literature or https://web.archive.org/web/*/http://www.compressconsult.com/rangecoder/#literature. A reason against is that these are unofficial sources of this knowledge and thus perhaps not ideal to use for the citation.
> 
> I did just check to see if other RFCs cite this and found that RFC6716 cites http://en.wikipedia.org/w/index.php?title=Range_encoding&oldid=509582757 as an informative reference.
> 
> For IETF is there a preference for which of these citations if any to use?
> 
> > — Section 3.8.1.1 —
> > 
> >   To encode binary digits efficiently a Range coder is used.  C_(i) is
> >   the i-th Context.  B_(i) is the i-th byte of the bytestream. b_(i) is
> >   the i-th Range coded binary value, S_(0, i) is the i-th initial
> >   state.  The length of the bytestream encoding n binary symbols is
> >   j_(n) bytes.
> > 
> > Two things here:
> > 
> > Editorial: I think it would be easier to read this as an item list
> > (what do you think?):
> > 
> > NEW
> >   To encode binary digits efficiently a Range coder is used.
> >     - C_(i) is the i-th Context
> >     - B_(i) is the i-th byte of the bytestream
> >     - b_(i) is the i-th Range coded binary value
> >     - S_(0, i) is the i-th initial state
> >     - j_(n) is the length of the bytestream encoding n binary symbols
> > END
> 
> Locally, I’ve tested converting this into a definition list per https://tools.ietf.org/html/rfc7991#section-2.20, which rendered in the text output as:
> 
>    C_(i)  the i-th Context.
>    B_(i)  the i-th byte of the bytestream.
>    b_(i)  the i-th Range coded binary value.
>    S_(0, i)  the i-th initial State.
>    j_(n)  the length of the bytestream encoding n binary symbols.
> 
> > Substantive: It would also help to add to that list L_(i), l_(i),
> > R_(i), r_(i), and t_(i), so things are complete.  Maybe also S_(x, i),
> > where x is not 0.
> 
> Nudging Michael Niedermayer and Derek Buitenhuis on this for help. Some guess work but if I understand correctly.
> 
> L_(i) is the Low value of the Range
> l_(i) is a temporary storage variable used in assigning values to L_(i)
> R_(i) is the Range value
> r_(i) is a temporary storage variable used in assigning values to R_(i)
> t_(i) is a temporary storage variable used in assigning values to R_(i)
> S_(x, i) is the ‘x, 1’-th State.
> 
> >   S_(i + 1, C_(i)) =  zero_state_(S_(i, C_(i)))  AND
> >              l_(i) =  L_(i)                      AND
> >              t_(i) =  R_(i) - r_(i)              <==
> >              b_(i) =  0                          <==>
> >              L_(i) <  R_(i) - r_(i)
> > 
> > I still don’t understand how to read this.
> 
> I should note that these equation appear a bit differently in the HTML version of the draft where they are depicted in SVG images of LaTeX equations. In the SVG, the equation all exists on one line; however, in the plain text output it doesn’t fit in the line width so we wrap the output a bit for cosmetics. If more clear we could re-arrange the line breaks, such as:
> 
>    (
>      S_(i + 1, C_(i)) =  zero_state_(S_(i, C_(i)))  AND
>      l_(i) =  L_(i)                                 AND
>      t_(i) =  R_(i) - r_(i)
>     ) <== ( b_(i) = 0 ) <==> ( L_(i) <  R_(i) - r_(i) )
> 
> > Perhaps explain verbally
> > what it’s supposed to mean, and I can help figure out some words to
> > add that will help others?
> 
> b_(i) = 0 and L_(i) <  R_(i) - r_(i) would imply each other as well as implies the other group of three assignments.
> 
> > I don’t know what the “AND” and “<==“ and
> > “<==>” on the right are trying to tell me (I get what “A <== B” means,
> > but I don’t know how to interpret “<==“ at the end of the line, for
> > example).
> 
> It is only a line break, if not for the line width limitation this would be:
> 
> S_(i + 1, C_(i)) =  zero_state_(S_(i, C_(i))) AND l_(i) =  L_(i) AND t_(i) =  R_(i) - r_(i) <== b_(i) =  0 <==> L_(i) <  R_(i) - r_(i)
> 
> which is closer to how it looks in the SVG HTML version.
> 
> > Do others who haven’t worked on this understand it?  It’s quite
> > possible that it’s just me, in which case I’ll happily step aside.
> > But I’m also happy to try to make it more understandable.
> 
> Yes, please more understandability. :)
> 
> >   S_(i + 1, k) = S_(i, k) <== C_(i) != k
> > 
> >     Figure 13: The "i+1,k"-th State is equal to the "i,k"-th State if
> >         the value of "k" is unequal to the i-th value of Context.
> > 
> > The caption on this does help, so now I see what it’s getting at!  But
> > I would *never* understand it without the caption.  (1) The
> > right-to-left conditional is odd to me.  (2) I’m not used to that sort
> > of conditional being used as an “if-then” statement.  I’m curious why
> > you didn’t write this whole section in pseudo-code, and perhaps it’s
> > another artifact of my wading into a field that’s foreign to me.  Had
> > Figure 13 been written like this, I would understand it perfectly:
> > 
> >   if ( C_(i) != k ) then { S_(i + 1, k) = S_(i, k) }
> 
> Yes, in pseudo-code that is the same.
> Michael Niedermayer, any objection to converting some of the math to pseudocode?

Iam perfectly fine with changing the notation so it is easier to understand.

One disadavantage of pure pseudocode could be that it may be hard to describe
encoding in such a way that it describes not one bitstream but a set of
bitstreams which are guranteed to be decoded correctly.
That is if the encoder side is described by pseudocode.

If the approuch of trying to describe the bitstream by the non pseudocode
notation is disliked. Then maybe the decoder side can be described by
normative pseudocode and the encoder side by informative pseudocode
so that the encoder side would be "one possible" solution but not the only
one. 
We could of course also describe both by strict normative pseudocode but
that would be different from what the original intend was

None of this is specific to the quoted line of code above of course

I had not imagined that the notation would lead to so much confusion,
its definitly important that the text can be understood and implemented
by the average target audience, if the notation causes problems here it
certainly should be improved ...

Thanks

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

There will always be a question for which you do not know the correct answer.