Subject: [Cellar] draft-ietf-cellar-ebml questions regarding "vints"

From: Tony Arcieri <[email-masked]>
Date: Sat, 20 Jul 2019 14:55:05 -0700

Hello, I recently came across draft-ietf-cellar-ebml and was pleased to see
it specified a "prefix varint" format. It's a bit serendipitous, as I (as
part of a personal, outside-of-IETF project) had written a similar
specification which also called them "vints":

https://github.com/clasp-lang/veriform/blob/master/spec/draft-veriform-spec.md#little-endian-prefixed-variable-width-integers

I think there are a few places the "vints" described in this draft could
potentially be improved (or perhaps I'm misunderstanding). The things I'd
be interested in proposing are micro-optimizations. I'm curious if there's
still time/interest in that sort of thing, and more generally comparing
these two approaches, or has the ship already sailed?

Notably, if I'm understanding correctly: draft-ietf-cellar-ebml vint
decoding appears to involve a loop, whereas the ones I have spec'd can be
done entirely with an unaligned load and a shift and does not require a
loop.

Regardless, "Cellar" looks quite interesting and I'm glad there's IETF work
on specifying this sort of construction.

-- 
Tony Arcieri

---

From: Andreas Rheinhardt <[email-masked]>
Date: Sat, 20 Jul 2019 23:08:00 +0000

Hello,

> these two approaches, or has the ship already sailed?
The whole aim of this working group is to create specifications for an
already existing format: Matroska (defined more than a decade ago,
probably billions of files in existence). Matroska is based on EBML
and so that ship has definitely sailed.

> done entirely with an unaligned load and a shift and does not require a

On a big-endian system (or more generally, on a system where one can
easily perform unaligned big-endian loads -- I would count x86/x64
among them), one can read EBML's vint via a 64bit unaligned BE load,
then one has to get the number of leading zeroes in the first (most
serious) byte, mask the marker bit away and perform an appropriate
right shift.

On a little-endian system and your proposal, one can use a LE load,
count the number of trailing zeroes in the least serious byte, mask
the bytes that have been read but don't belong to the number away and
perform a right shift. So it is pretty much the same, just for
little-endian. The only difference is that you have the special-case
of the first byte being all zero in order to encode the whole uint64_t
range. That's not a concern for EBML.

- Andreas

---

From: Tony Arcieri <[email-masked]>
Date: Sat, 20 Jul 2019 16:20:12 -0700

Thanks for the clarifications. Makes perfect sense.

On Sat, Jul 20, 2019 at 4:09 PM Andreas Rheinhardt <
[email-masked]> wrote:

> _______________________________________________
> Cellar mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cellar
>

-- 
Tony Arcieri

---

From: Michael Richardson <[email-masked]>
Date: Mon, 22 Jul 2019 17:34:45 -0400

Tony Arcieri <[email-masked]> wrote:
    > Hello, I recently came across draft-ietf-cellar-ebml and was pleased to
    > see it specified a "prefix varint" format. It's a bit serendipitous, as
    > I (as part of a personal, outside-of-IETF project) had written a
    > similar specification which also called them "vints":

    > I think there are a few places the "vints" described in this draft
    > could potentially be improved (or perhaps I'm misunderstanding). The
    > things I'd be interested in proposing are micro-optimizations. I'm
    > curious if there's still time/interest in that sort of thing, and more
    > generally comparing these two approaches, or has the ship already
    > sailed?

Sorry,
a) the ship has sailed, EBML is past WGLC.
b) as was said, this is documenting an existing protocol.... if not we would
   have used CBOR.  Is there a reason your document didn't use CBOR?

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Tony Arcieri <[email-masked]>
Date: Mon, 22 Jul 2019 18:03:36 -0700

>    have used CBOR.  Is there a reason your document didn't use CBOR?

I am exploring a different set of tradeoffs from the ones CBOR made. Most
notably, what I'm working on is very much "schema first".

I'm also working on an abstract object model that spans encodings, and CBOR
is one of them. Think ASN, but made this millennium. This encoding is the
"native" encoding of the object model, however CBOR is (or more like can,
with some PoC code) also be supported. The primary purpose is content-aware
hashing that works across different encodings, a problem e.g. JWT/CWT
punted on completely, and my encoding is both size-optimal and ultimately
must be computed anyway to verify content hashes from foreign encodings.
Yes, [img:xkcd], I'm all too aware...

My primary application is credentials and other cryptographically
verifiable data. This is an area where the set of tradeoffs made by CBOR
aren't working particularly well. One of the original goals of CBOR was to
avoid multiple encodings ala ASN.1, however together with the absence of a
schema language CBOR is rather suboptimal in this regard, and thus we get
things like "Packed CBOR".

I could keep going, e.g. my solutions to the problems in RFC 7049 2.4.4.2
take the diametrical opposite approach by enriching JSON with type
annotations rather than complicating the binary protocol, but this probably
isn't the appropriate venue for an extended CBOR rant.

-- 
Tony Arcieri