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

[Michael Niedermayer <[e-mail]>]

On Tue, Jan 26, 2021 at 12:54:08PM -0500, Barry Leiba wrote:
> Where are we on this?  I had thought you had the token to try to move
> the notation to pseudocode, but given the time lag I'm not sure we're
> all in agreement about what the next step is and who has it to take.
> So let's sync up and try to get this done.

I thought derek or someone else was working on the range coder description / pseudocode
because of: https://github.com/FFmpeg/FFV1/issues/231#issuecomment-697328963
But iam starting to have the feeling i have mixed this up a bit

Thanks

> 
> Thanks,
> Barry
> 
> On Fri, Dec 4, 2020 at 1:34 PM Michael Niedermayer
> <[e-mail]> wrote:
> >
> > 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.
> 
> _______________________________________________
> Cellar mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/cellar

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

If the United States is serious about tackling the national security threats 
related to an insecure 5G network, it needs to rethink the extent to which it
values corporate profits and government espionage over security.-Bruce Schneier