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

Barry Leiba <barryleiba@computer.org> Tue, 26 January 2021 17:54 UTC

Return-Path: <barryleiba@gmail.com>
X-Original-To: cellar@ietfa.amsl.com
Delivered-To: cellar@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0AE723A0CE3; Tue, 26 Jan 2021 09:54:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.499
X-Spam-Level:
X-Spam-Status: No, score=0.499 tagged_above=-999 required=5 tests=[FREEMAIL_FORGED_FROMDOMAIN=0.249, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id b-t_CiykDbgD; Tue, 26 Jan 2021 09:54:22 -0800 (PST)
Received: from mail-lj1-f173.google.com (mail-lj1-f173.google.com [209.85.208.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0A6763A0CDF; Tue, 26 Jan 2021 09:54:22 -0800 (PST)
Received: by mail-lj1-f173.google.com with SMTP id c18so7881745ljd.9; Tue, 26 Jan 2021 09:54:21 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=mVtwRjGHXrxCQL4pd5ptMha5TD+9zg5KEatycruOOyA=; b=rjfaLz/JpI3ywvUJvGq2b4ZPcpgvVhqCVD7jSAm4s9vwNXaIiwtoNRCVY6byV6X6LT BZK6BrmjY9Med600W5dwm34N4tOLwiAi6NrW5PhcBidme017L0vU4r0m4n0OIJRQgqkc e0GLUGV+llZ7uM4891l24+Nst3XU09rGMrZ/QKsx2PI617jhnErGhQlmE7YZS8hG4GeD o5R7Oua36KKSWGZbD+H4zQTRJa/EogFn7PN5ASdzr8aVvs4mhzPCpSsIaczYLrTFOwgg D4xgCJu2qc6qYeMXU+bWRj5jiGF+uo+REBD99mVdg0P4abLSM96OcnrmCbV7uJYLPHgw QSvg==
X-Gm-Message-State: AOAM533I3kvKlJ0Em9sJ/FwYlsbTMONQJiqnoXSiUulCWZKJrVrOycQa j8ZTqj1U+igXulfwcFMSrgACUidDA4NJggZvxS4=
X-Google-Smtp-Source: ABdhPJzhe4uSKpnimxwIcZeEgpBr+cjg96MwM65rbLItLSXtMzQAHZ03LXwJfK5AnsptACTyiTQF3BsSv8HTyo6r7Gk=
X-Received: by 2002:a2e:959a:: with SMTP id w26mr3422769ljh.113.1611683660149; Tue, 26 Jan 2021 09:54:20 -0800 (PST)
MIME-Version: 1.0
References: <160049032442.20595.4616862102756589735@ietfa.amsl.com> <92029D16-621F-4AE0-BC3F-03C08AB21ADE@dericed.com> <C99936E0-F4EE-4F32-A731-CFB01E84C644@dericed.com> <CALaySJLqjY5muXMQRGeR7drZ7imYLVQFxZxsdD65g3f7onz51A@mail.gmail.com> <CALaySJK8q4k_WeuGxCDnaYrekm-_jKshnDOF56T3KYuUGHxWHw@mail.gmail.com> <3BDF43E9-1245-40D0-B589-7ABFC14C8823@dericed.com> <20201204183342.GO2389354@pb2>
In-Reply-To: <20201204183342.GO2389354@pb2>
From: Barry Leiba <barryleiba@computer.org>
Date: Tue, 26 Jan 2021 12:54:08 -0500
Message-ID: <CALaySJLcg90gt-aQC2fa=43GXSeihrbSRf4J=XgLMwwwopnnaA@mail.gmail.com>
To: Michael Niedermayer <michael@niedermayer.cc>
Cc: Dave Rice <dave@dericed.com>, cellar-chairs@ietf.org, derek.buitenhuis@gmail.com, Michael Richardson <mcr+ietf@sandelman.ca>, pb@das-werkstatt.com, draft-ietf-cellar-ffv1@ietf.org, Codec Encoding for LossLess Archiving and Realtime transmission <cellar@ietf.org>, The IESG <iesg@ietf.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cellar/AanPV47XMAPR1adYyw-k1Jy6Txs>
Subject: Re: [Cellar] Barry Leiba's Discuss on draft-ietf-cellar-ffv1-17: (with DISCUSS and COMMENT)
X-BeenThere: cellar@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Codec Encoding for LossLess Archiving and Realtime transmission <cellar.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/cellar>, <mailto:cellar-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cellar/>
List-Post: <mailto:cellar@ietf.org>
List-Help: <mailto:cellar-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/cellar>, <mailto:cellar-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 26 Jan 2021 17:54:24 -0000

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.

Thanks,
Barry

On Fri, Dec 4, 2020 at 1:34 PM Michael Niedermayer
<michael@niedermayer.cc> 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 <barryleiba@computer.org> 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.