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

From: Jim Schaad <[email-masked]>
Date: Thu, 27 Aug 2020 01:05:23 -0700

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?

Jim

---

From: Michael Richardson <[email-masked]>
Date: Fri, 28 Aug 2020 14:24:46 -0400

> entry 3 in the table is 6.2872("foo")), does that entry need to occur after

I also asked that question.
If we don't enforce that rule, then the decoder has to take care of dealing
with loops.

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.

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

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 28 Aug 2020 20:30:22 +0200

> If we don't enforce that rule, then the decoder has to take care of dealing

Right.

> 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.

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

---

From: Jim Schaad <[email-masked]>
Date: Fri, 28 Aug 2020 14:16:00 -0700

-----Original Message-----
From: Carsten Bormann <[email-masked]> 
Sent: Friday, August 28, 2020 11:30 AM
To: Michael Richardson <[email-masked]>
Cc: Jim Schaad <[email-masked]>; [email-masked]; [email-masked]
Subject: Re: [Cbor] Ordering of items in the prefix table

On 2020-08-28, at 20:24, Michael Richardson <[email-masked]> 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.
>> entry 3 in the table is 6.2872("foo")), does that entry need to occur 
>> after the entry it references?
> 
> 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.

(Backward references?)

[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

Grüße, Carsten

---

From: Jim Schaad <[email-masked]>
Date: Fri, 28 Aug 2020 14:46:14 -0700

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

Jim

-----Original Message-----
From: CBOR <[email-masked]> On Behalf Of Jim Schaad
Sent: Friday, August 28, 2020 2:16 PM
To: 'Carsten Bormann' <[email-masked]>; 'Michael Richardson' <[email-masked]>
Cc: [email-masked]; [email-masked]
Subject: Re: [Cbor] Ordering of items in the prefix table

-----Original Message-----
From: Carsten Bormann <[email-masked]>
Sent: Friday, August 28, 2020 11:30 AM
To: Michael Richardson <[email-masked]>
Cc: Jim Schaad <[email-masked]>; [email-masked]; [email-masked]
Subject: Re: [Cbor] Ordering of items in the prefix table

Right.

(Backward references?)

Grüße, Carsten

_______________________________________________
CBOR mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/cbor

---

From: Michael Richardson <[email-masked]>
Date: Fri, 28 Aug 2020 18:06:18 -0400

> (Backward references?)

I guess it depends upon your point of view. All references need to point in
the same direction :-)

    > 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.

I think that things in the static dictionary(ies) can not reference things in
the shared (dynamic) dictionary.  I am grumpy about the terminology now, btw.
"shared" is a bit ambiguous now.

I also think that my understanding of the prefix space is too shallow.

But, it seems that we ought to be able to build a reasonable DAG.

    > 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.

When you say merged, do you mean that they receive some kind of collective
numbering?

    > 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.

unidirectional references are just one way of dealing with the loop.
Another is just to have a big enough bitmap to be able to mark things.

A third loop detection involves two pointers, one which moves at half the
rate of the other: I know this works for single-linked lists, but it might
not work for a tree. I have think about this.

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 29 Aug 2020 00:14:14 +0200

> "shared" is a bit ambiguous now.

The draft currently does not have dictionaries (which would be a term for external dictionaries to be added to the information in the internal tables).

It has two tables:

— shared items
— prefix items

The internal referencing works by giving the index of the item in the table; these are the “numbers” I have been talking about.  The ordering of items in the number space is relevant for the achievable compactness.  Both shared items and prefix items can contain references to shared items and prefix items.

None of this is static or dynamic; adding external dictionaries might give these terms a useful meaning (that I haven’t picked up yet).

Grüße, Carsten