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

From: Brendan Moran <[email-masked]>
Date: Fri, 4 Sep 2020 15:50:47 +0000

I’ve been thinking about how dictionaries and nested tables interact. I have been wondering about the possibility of using references that overflow the nearest table to handle nesting. For the nesting-only case, this is straight-forward: when the decoder encounters a reference, it first checks to see if the reference fits in the nearest table. If it overflows the number of elements in that table, the size of the table is subtracted from the reference, then the decoder checks the next-nearest table.

This allows the decoder to treat the nested tables as a stack, pushing the most-recently encountered table onto the stack each time it finds one. Each time the traversal of a packed structure ends, it pops the table off of the stack.

This has the advantage a packed object can be included as-is in a larger packed object. A packed object can either be aware of the higher-level object or oblivious.

I’m assuming that a dictionary reference will live in its own tag, with an identifier:

7([rump, id])

That would make it easy to use the technique above with dictionaries. If the identifier is anything other than an array, we don’t need a separate tag, which is pretty nice.

Brendan

> On 28 Aug 2020, at 23:14, Carsten Bormann <[email-masked]> wrote:
>
> On 2020-08-29, at 00:06, Michael Richardson <[email-masked]> wrote:
>>
>>> 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.
>
> 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
>
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

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.

---

From: Michael Richardson <[email-masked]>
Date: Fri, 04 Sep 2020 23:10:15 -0400

Brendan Moran <[email-masked]> wrote:
    > I’ve been thinking about how dictionaries and nested tables interact. I
    > have been wondering about the possibility of using references that
    > overflow the nearest table to handle nesting. For the nesting-only
    > case, this is straight-forward: when the decoder encounters a
    > reference, it first checks to see if the reference fits in the nearest
    > table. If it overflows the number of elements in that table, the size
    > of the table is subtracted from the reference, then the decoder checks
    > the next-nearest table.

That's a good idea, and it allows the shorter references to be reused.
It also allows for locality, so we no longer have to worry about the global
frequency, but some local frequency of use.

--
Michael Richardson <[email-masked]>   . o O ( IPv6 IøT consulting )
           Sandelman Software Works Inc, Ottawa and Worldwide