Subject: [Cbor] cbor-packed: Circumfix expansion

From: Christian Amsüss <[email-masked]>
Date: Mon, 1 Feb 2021 12:57:25 +0100

Hello Carsten, hello CBOR group,

it occurred to me that a variant of compression is unexplored. Suppose
we have data like (please mentally replace strings with appropriate
numbers) in SenML assuming draft-groves-core-senml-bto:

[{"bn": "urn:dev:ow:X", "bu": "V", "v": 1.992, "t": 1.6e9, "bto": 2},
/* bto indicates all the following items are offset by 2 seconds each */
 {"v": 1.986},
 {"v": 1.874},
 {"v": 1.423},
 ...
]

It'd be tempting to write that as

TBD51([{"v": TBD(0)}], [], [],
  [{"bn": "urn:dev:ow:X", "bu": "V", "v": 2.047, "t": 1.6e9, "bto": 2},
   TBD6'(
     5([-7, 64(h'feefb6...')]) /* [0xfe, 0xef, 0xb6, ...] x 2^-7 */
   )])

which is combining bigfloats and arrays (if they, on their own, can they
be combined that way; otherwise one might be tempted to use second-table
units) to expand to

TBD51([{"v": TBD(0)}], [], [],
  [{"bn": "urn:dev:ow:X", "bu": "V", "v": 2.047, "t": 1.6e9, "bto": 2},
   TBD6'(
     [1.986, 1.874, 1.423]
   )])

and then would use circumfix expansion (a variant on the shared item)
to expand the array into the original one-element dictionary sets. The
rough rule could be that when the nth circumfix expansion is triggered,
the rump is iterated over expanded into the nth shared item (or picked
from another table -- details) with its occurrence of a given tag TBD
replaced with the rump's item at that position.

One straightforward application is like in the example -- generating
repetitive entries from data that can be sent right from some sampling
buffer by using typed arrays.

The straightforward reason not to do this is that it's more complex even
on the decompressor (let alone on the compressor, but that might usually
use manual compression anyway).

I'm not saying we *should* do this (that's what I hope to get from
starting discussion here) -- but if nothing else, it could help shape a
"what kind of compressions are in scope and what's out of scope"
paragraph.

BR
Christian

-- 
To use raw power is to make yourself infinitely vulnerable to greater powers.
  -- Bene Gesserit axiom

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 1 Feb 2021 13:24:26 +0100

https://tools.ietf.org/html/draft-bormann-lpwan-cbor-template-02

is the most general form of this that I have written up.
This assumes that the SCHC environment does the referencing, so it only defines the referee (template), not the referent (invocation).
The example has only one parameter, but could have more.

Can we package that in a way that is useful for cbor-packed?

(I do see the complexity issue.)

Grüße, Carsten

> On 2021-02-01, at 12:57, Christian Amsüss <[email-masked]> wrote:
>

---

From: Christian Amsüss <[email-masked]>
Date: Mon, 1 Feb 2021 19:22:06 +0100

On Mon, Feb 01, 2021 at 01:24:26PM +0100, Carsten Bormann wrote:
> This assumes that the SCHC environment does the referencing, so it
> only defines the referee (template), not the referent (invocation).

Possibly we may first want to do this the other way round -- for what is
a CBOR template other than a CBOR snippet that can be expanded to a full
CBOR item?

The only difference is that unlike in the regular case, the compressor
and uncompressor may not agree on the precise values to be expanded (but
still must on their semantics). The static context would define these
semantics, and the concrete table entries are set from the data the SCHC
environment picks out of whereever.

On a tangent, this opens questions about the applicability to core-href.
(If we can have compressed items that are only semantically but not
contentually agreed on, can core-href semantically always encode full
URIs but have packing tables prepopulated with "the current base
origin", "the current base uri without query parameters" etc?).

> (I do see the complexity issue.)

Come to think of it, if this is done smart, all the complexity of such
an expansion could sit in additional tags that build on cbor-packed.

For a strawman example, a For-Each-Tag could be defined in relatively
simple terms by making it an array [a_0, a_1, ..., a_n], with a_0 used as a
template, and it expands to an m long array (where m is the equal length
of all a_i). Before a_0 is expanded (as it WILL PROBABLY contain Tag-6
items), n-1 shared items are taken from a_1..a_n and injected at the
start of the Current Set.

Such a For-Each tag is clearly more complex in processing than all the
other packing substituion -- but (even if it turns out we want it, which
I don't consider settled) it wouldn't need to be part of cbor-packed,
and wouldn't scare users.

All we'd need to get "right" for this is to be clear about which scoping
rules apply in the recursive expansion for the case that something
between table-setup and item-use meddles with the Current Set. (AFAIU
it's implied by overriding dictionaries being useful, but words like
"dynmaic scoping" and examples should help).

LG
c