Subject: [Cbor] Packing CBOR (draft-bormann-cbor-packed-00)

From: Carsten Bormann <[email-masked]>
Date: Mon, 13 Jul 2020 21:48:17 +0200

This draft may seem a bit unusual, in that it allocates 268439585 tags, including one of the 12 remaining precious single-byte ones.
But if you read it, that will seem perfectly normal.

Please see
https://www.ietf.org/id/draft-bormann-cbor-packed-00.html#name-acknowledgements
for how this came to be.

I’m going to ask for WG adoption at IETF 108...

Grüße, Carsten

> Begin forwarded message:
> 
> From: [email-masked]
> Subject: New Version Notification for draft-bormann-cbor-packed-00.txt
> Date: 2020-07-13 at 21:42:21 CEST
> To: "Carsten Bormann" <[email-masked]>
> 
> 
> A new version of I-D, draft-bormann-cbor-packed-00.txt
> has been successfully submitted by Carsten Bormann and posted to the
> IETF repository.
> 
> Name:		draft-bormann-cbor-packed
> Revision:	00
> Title:		Packed CBOR
> Document date:	2020-07-13
> Group:		Individual Submission
> Pages:		9
> URL:            https://www.ietf.org/internet-drafts/draft-bormann-cbor-packed-00.txt
> Status:         https://datatracker.ietf.org/doc/draft-bormann-cbor-packed/
> Htmlized:       https://tools.ietf.org/html/draft-bormann-cbor-packed-00
> Htmlized:       https://datatracker.ietf.org/doc/html/draft-bormann-cbor-packed
> 
> 
> Abstract:
>   The Concise Binary Object Representation (CBOR, RFC 7049) is a data
>   format whose design goals include the possibility of extremely small
>   code size, fairly small message size, and extensibility without the
>   need for version negotiation.
> 
>   CBOR does not provide any forms of data compression.  CBOR data
>   items, in particular when generated from legacy data models often
>   allow considerable gains in compactness when applying data
>   compression.  While traditional data compression techniques such as
>   DEFLATE (RFC 1951) work well for CBOR, their disadvantage is that the
>   receiver needs to unpack the compressed form to make use of data.
> 
>   This specification describes Packed CBOR, a simple transformation of
>   a CBOR data item into another CBOR data item that is almost as easy
>   to consume as the original CBOR data item.  A separate decompression
>   step is therefore often not required at the receiver.
> 
> 
> 
> 
> Please note that it may take a couple of minutes from the time of submission
> until the htmlized version and diff are available at tools.ietf.org.
> 
> The IETF Secretariat
> 
>

---

From: [email-masked] (Dale R. Worley)
Date: Wed, 29 Jul 2020 02:53:14 -0400

After a very quick look, these points about the draft stand out.  The
abstract contains:

   While traditional data compression techniques such as
   DEFLATE (RFC 1951) work well for CBOR, their disadvantage is that the
   receiver needs to unpack the compressed form to make use of data.

   This specification describes Packed CBOR, a simple transformation of
   a CBOR data item into another CBOR data item that is almost as easy
   to consume as the original CBOR data item.

The first sentence is probably not exactly what you want to say, because
of course, in order to make use of the content of any "compressed form"
you first have to "unpack" it, in that you have to reverse whatever the
compression was.  I *think* what you mean is that in order to make use
of even a small portion of the data, the entire prefix from the start to
that portion of the data must be unpacked.

The second sentence seems also to not state what you care about.  I can
define "a simple transformation of a CBOR data item into another CBOR
data item" that is *just as easy* to consume as the original:  the
identity transformation.  I *think* what you mean is that the packed
form can (in many cases) be significantly smaller than the original
form, and yet "random access" of individual items in the packed form is
only constant-factor-slower than it is in the original form.

Note that I'm depending on "random access" to mean extracting an item
when the indexes into the nested arrays and keys of the nestd maps are
provided.

Note that this isn't just nit-picking, you're explaining the
characteristics that differentiate Packed CBOR, that is, the reason for
this work.

The other thing that stands out is that the document is very terse.
It promises to define the unpacking operation, but that definition is
largely implicit.  E.g., 2.1 says:

   Shared items are stored in the third to last element of the array
   used as tag content for tag number 6, numbered starting by 2.

   The shared data items are referenced by using the data items in
   Table 1.  When reconstructing the original data item, such a
   reference is replaced by the referenced data item, which is then
   recursively unpacked.

I *think* what this means is, "Unpacking a packed-CBOR object is done by
starting with the rump structure and replacing references within it
copies of the referenced structure.  Within the rump structure, tag 6
(which I think is CDDL #6.6) is used not to designate a packed-CBOR
structure but rather a reference to one of the shared structures.  The
tagged value in such a reference is either a simple value or an integer,
interpreted according to Table 1.  Implicitly, each reference is
replaced by a copy of the referended shared value.  The shared
structures may themselves contain uses of tag 6, whose values are
packed-CBOR structures."

The difference in the above description is that it is explicit about the
operations that convert the packed-CBOR structure into its unpacked
form.

Also, it's not clear to me whether a packed-CBOR (a value tagged with 6)
can appear anywhere other than the top level of the CBOR structure.  I
would expect by the nature of CBOR it can be, but section 2 isn't clear
about it.

Dale

---

From: Carsten Bormann <[email-masked]>
Date: Wed, 29 Jul 2020 07:19:01 +0200

Hi Dale,

+1 to all your editorial points; this sure was written up quickly.

To the technical point: Yes, there is no reason tag 6 cannot be used deeper within the structure.  The interesting technical question is what happens if there are two or more packed structures: Do they sail like ships in the night, or is there interaction (e.g., for nested compression, do the tables get merged in some way?)?
We don’t have an answer for that (but probably should).

A related question is how to support CBOR sequences: is there a way for one of the data items to use a prefix/sharing table entry in another data item in the sequence?

Grüße, Carsten

> On 2020-07-29, at 08:53, Dale R. Worley <[email-masked]> wrote:
> 
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: [email-masked] (Dale R. Worley)
Date: Fri, 31 Jul 2020 02:39:42 -0400

Spending more time thinking about this, and reading the -01:

I'm glad to see that the Abstract pays more attention to the usages that
Packed CBOR with aid.  It seems that the major advantage is where the
entire Packed CBOR value will be read into storage, and then individual
items will be indexed out of it and utilized.  Conversely, a situation
where it would not help is when the entire CBOR is parsed and its values
put into an internal data structure, from which they are consumed by the
application.  That latter is a situation where the stream parsers that
others have mentioned would be useful.  With selective access, there
would be particular gains if only a small number of items are accessed,
but it was not predictable in advance which ones they would be.  Whether
this is a common pattern, I don't know.

It seems to be expected that implementations will not generate the
unpacked structure and use that.  However, to access items directly in
Packed CBOR requires that the top-level array must be scanned to locate
the shared items.  Or at least, it must be scanned lazily as references
are found that need expanding.  This goes back to the expectation that
the entire Packed CBOR will be directly accessible whenever an item is
to be extracted, but also that the packing saves storage space, not
processing time, as the entire packed astructure may need to be parsed to
extract an element that is "early" in the unpacked structure.

It seems to be open where a Packed CBOR can be placed.  The options seem
to be (1) only at the top level, (2) multiple instances are permitted
(and hence, not necessarily at the top level) but not nested within each
other, and (3) Packed CBORs can be nested.

Another choice is whether shared prefixes and shared structures may
contain references to shared things.  Interestingly, if one is indexing
into the structure, following shared references doesn't require a
recursion stack even if shared structures may themselves contain
references.  But following shared prefixes does, as the final value may
be composed of an arbitrary number of fragments and the first byte of
the value is from the deepest-nested fragment.

If shared things may contain references, what Packed CBOR are they
interpreted within?  If there is only one, that is the one.  But if
Packed CBOR can be nested, a possibility is that they are interpreted in
the *outer* Packed CBOR -- that is, a references is interpreted witin
the smallest Packed CBOR within whose rump the reference is contained.
That has the interesting property that it eliminates circular references
(and I think that ensures that expansion would always terminate), but
probably isn't useful in practice.

It seems natural for CBOR that Packed CBOR could be included as an item
within a larger CBOR structure.  That makes it easier to assemble larger
structures from smaller ones, but makes parsing more complex.  Though it
shouldn't be too hard to write a "Packed CBOR unifier" that turns two or
more Packed CBORs into one by unioning their dictionaries and
renumbering all the references, then assembling the structure containg
the input rumps.

In regard to prefix sharing in strings, the idea of allowing the same
prefix to be used by both byte and character strings is attractive but
seems semantically fraught.  A subtle point is that the current draft
talks about concatenation but doesn't specify what it must, that the
concatenation is as sequences of bytes that are (for UTF-8 strings)
subsequently interpreted as characters.  CBOR is careful to require that
character strings always consist of a series of proper UTF-8 characters,
even the components of an "indefinite" character string.  But
concatenating an arbitrary sequence of bytes to the beginning may or may
not preserve that property.  So it may be more consistent with CBOR's
semantics to only allow prefixing UTF-8 strings with UTF-8 strings.

And it probably needs to be stated how packing works in "indefinite"
constructions.  For indefinite byte strings and UTF-8 strings,
presumably references are not allowed as components (although the
tag-prefix-reference can be applied *to* the indefinite string).  For
indefinite arrays, component items can be references.  For indefinite
maps, component keys and values can be references, but a contained
reference cannot be used to provide a shared subset of key/value pairs.

I wonder if it might be better to define the Packed CBOR structure as a
map:

   Packed-CBOR = #6.6({0:rump, 1:[*prefix], 2:[*shared]})

If I counted correctly, this format has these overhead bytes:  tag.6,
map.3, int.0, int.1, array.(# of prefixes), int.2, array.(# of shareds).
The current format has these:  tag.6, array.(# of shareds+2),
array.(# of prefixes).
A map usually costs 4 more bytes, but allows lots of extensibility.
OTOH, I don't know if we want to allow much extensibility.

Dale

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 31 Jul 2020 08:53:37 +0200

Hi Dale,

great set of deliberation/discussion points.  I’ll try to turn some of them into issues on the draft once IETF is over and I have a repo to put issues into.

Let me pick just one for now:

> OTOH, I don't know if we want to allow much extensibility.

The original draft went for a 1+0-byte tag to save bytes (it still needs to put in two array heads, one for the outer array, one for the inner prefix array, so the total overhead for setting up packing is 3 bytes [one tag, one container, one sub-container for prefix], as opposed to the 7 [tag, map, 0, 1, array, 2, array] from above).  (A map would also make it indeterminate which parts arrive first.)

A cheaper way to get extensibility is to use a larger number of tags to select a specific variant; we probably would go into 1+1 or 1+2-land with that, but could stay with a more dense encoding of each variant.

Grüße, Carsten