Re: [Cbor] Ordering of items in the prefix table

It dawns on me that enforcing the order might be an IoT vs the Ocean choice.

Jim

-----Original Message-----
From: CBOR <cbor-bounces@ietf.org> On Behalf Of Jim Schaad
Sent: Friday, August 28, 2020 2:16 PM
To: 'Carsten Bormann' <cabo@tzi.org>; 'Michael Richardson' <mcr+ietf@sandelman.ca>
Cc: cbor@ietf.org; draft-bormann-cbor-packed@ietf.org
Subject: Re: [Cbor] Ordering of items in the prefix table

-----Original Message-----
From: Carsten Bormann <cabo@tzi.org>
Sent: Friday, August 28, 2020 11:30 AM
To: Michael Richardson <mcr+ietf@sandelman.ca>
Cc: Jim Schaad <ietf@augustcellars.com>; draft-bormann-cbor-packed@ietf.org; cbor@ietf.org
Subject: Re: [Cbor] Ordering of items in the prefix table

On 2020-08-28, at 20:24, Michael Richardson <mcr+ietf@sandelman.ca> wrote:
> 
> 
> Jim Schaad <ietf@augustcellars.com> wrote:
>> I was just going through an expansion algorithm and I started to 
>> wonder if we should have a requirement about order of items in the prefix table.
>> Specifically if an entry in the prefix table uses a prefix itself  (i.e.
>> entry 3 in the table is 6.2872("foo")), does that entry need to occur 
>> after the entry it references?
> 
> I also asked that question.
> If we don't enforce that rule, then the decoder has to take care of 
> dealing with loops.

Right.

> This means either having a maximum loop depth, or, using a mark to 
> refuse to expand any specific dictionary item more than once.
> I would prefer that all references are forward references.

(Backward references?)

This is easy with just one kind of table entry, but gets harder when prefixes can reference shared items which can reference other prefixes and so on.

[JLS] I think my mind just crashed.  For some reason I had made an assumption that items in the shared space are never tagged, but that does seem reasonable.  Of course until earlier today I never thought about the fact that a packed item could have an empty right value in the case that V1 is a prefix of V2.  Since I am just looking at getting the tables started,  I haven't looked hard yet at how I would encode this so it may not end up that way.
Jim

Of course, the tables could be merged, but that loses exactly one bit per reference that can be derived from the prefix vs. shared reference.

One other thing to keep in mind is that not all places in the table are equal — the compressor will likely sort the entries by frequency of use.  Requiring infrequent entries to occupy all the good positions does not lead to very compact encoding.

Grüße, Carsten

_______________________________________________
CBOR mailing list
CBOR@ietf.org
https://www.ietf.org/mailman/listinfo/cbor