Re: [Cbor] Interactions of packed CBOR and tags

[Brendan Moran <[e-mail]>]

> On 4 Sep 2020, at 05:53, Carsten Bormann <[e-mail]> wrote:
>
> On 2020-09-03, at 19:05, Brendan Moran <[e-mail]> wrote:
>>
>>> Adding suffix packing, we could have a third table and a third set of referents (also with content).  We also could have just separate referents, sharing the table/number space, if that makes sense.
>>
>> [BJM] Unless we have a way to obtain a whole new referent space with small values, I think that sharing the table is optimal. This also allows reuse of individual values as either prefixes or postfixes, which should yield some additional compression opportunities. This will be even more interesting in the array space.
>
> Yes, but how do you know that a referent asks you to do prepend/append?
>
> (1) encode prefix vs. suffix in the referent — but that does mean that we use more code points for the referents
> (2) encode prefix vs. suffix in the table entry — but that means such an entry cannot be used for both (ok, minor problem), and it also requires to represent another bit in the table (which in the end might cost two bytes per entry).
> (3) encode prefix vs. suffix in the position of the table entry — but that is exactly equivalent to (1) on the referent side but does create the need to manage holes.
>
> So I think we need to bite the bullet and provide more referent space (1).

Well, if you want to encode prefix vs. postfix in the table, I think the best option is likely a bitfield for the whole table:

#6.6([rump, [bstr .bits prepost-flags, *prepostfix], *shared])

That’s only 2 bytes per entry if you have one entry.

Another, more obtuse option would be to encode several integers:

1: The number of 2 byte references that are prefixes
2: The number of 3 byte references that are prefixes
3: The number of 5 byte references that are prefixes

Then, sort table entries so that prefixes come before postfixes in each size grouping. I doubt it’s possible to get smaller than that encoding, since it has an absolute maximum size of 10 bytes, but can be substantially smaller.

There’s one more mechanism to improve this slightly: use positive or negative integers. If there are more prefixes than postfixes, encode the number of postfixes as a negative integer. If there are more postfixes than prefixes, encode the number of prefixes as a positive integer.


While I’d rather if references could declare prefix or postfix usage on a per-reference basis without inflating the table, I don’t think this is necessarily the right answer. This would need to be a very common use case for it to yield a better result on average than the schemes above. Reuse can already be accomodated by referencing an existing prefix or postfix within the prefix/postfix table.

Brendan
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.