Subject: Re: [Cbor] Interactions of packed CBOR and tags

From: Brendan Moran <[email-masked]>
Date: Thu, 3 Sep 2020 11:56:30 +0000

I’m not certain whether this overlaps or not, but I think it does. There’s a limitation in the current specification of packed cbor: Only text prefixes and singular CBOR elements can be packed. This may not seem like a big limitation at first, however I think that there are some missed opportunities here.

I’ll use CIRIs (https://tools.ietf.org/html/draft-hartke-t2trg-ciri-01) as an example. I realise they may not be “representative” but they illustrate two observations I’ve made about packed CBOR:

1. Some things need postfix sharing rather than prefix sharing. Domain names are the primary example of this. Because subdomains are prepended, rather than appended like the rest of the URI path, they need postfix sharing, assuming that the TLD has lowest entropy and the subdomains have the highest entropy in a given structure.

2. Packing sub-sequences of elements within containers is something that we should consider.

For example, suppose that I need to many CIRIs that represent, for example, the following URIs:

https://www.ietf.org
http://www.ietf.org
https://datatracker.ietf.org/group/cbor/about/
https://datatracker.ietf.org/doc/draft-bormann-cbor-packed/

Encoded as CIRIs and arranged into an array, these URIs take up 161 bytes (N.B. it would only be 151 bytes for the raw URIs)
[
  [1,"https", 2, "www.ietf.org"],
  [1,"http", 2, "www.ietf.org"],
  [1,"https", 2, "datatracker.ietf.org", 5, 0, 6, "group", 6, "cbor", 6, "about"],
  [1,"https", 2, "datatracker.ietf.org", 5, 0, 6, "doc", 6, "draft-bormann-cbor-packed"]
]

If I wanted to pack this structure, I think the result would look something like this:

Naive (127 bytes, 78% compression ratio):
6([
  [
    [1, 6("s"), 2, simple(0)],
    [1, 6(""), 2, simple(0)],
    [1, 6("s"), 2, simple(1), 5, 0, 6, "group", 6, "cbor", 6, "about"],
    [1, 6("s"), 2, simple(1), 5, 0, 6, "doc", 6, "draft-bormann-cbor-packed"]
  ],
  [
    "http"
  ],
  "www.ietf.org",
  "datatracker.ietf.org"
])

Better (124 bytes, 77% compression ratio):
6([
  [
    [1, simple(1), 2, simple(2)],
    [1, simple(0), 2, simple(2)],
    [1, simple(1), 2, simple(3), 5, 0, 6, "group", 6, "cbor", 6, "about"],
    [1, simple(1), 2, simple(3), 5, 0, 6, "doc", 6, "draft-bormann-cbor-packed"]
  ],
  [
    simple(0)
  ],
  "http",
  6("s"),
  "www.ietf.org",
  "datatracker.ietf.org"
])

I think we can do a bit better, but it’s convoluted… (122 bytes, 76% compression ratio):
6([
  [
    [1, simple(1), 2, simple(3)],
    [1, simple(0), 2, simple(3)],
    [1, simple(1), 2, simple(4), 5, 0, 6, "group", 6, "cbor", 6, "about"],
    [1, simple(1), 2, simple(4), 5, 0, 6, "doc", 6, "draft-bormann-cbor-packed"]
  ],
  [
    simple(0),
    "www",
    "datatracker"
  ],
  "http",
  6("s"),
  ".ietf.org",
  224(simple(2)),
  225(simple(2))
])

Back to the observations I made above.

1. Compressing the domain names doesn’t work very well. Maybe this is unique to domain names, but I think we need more data on that.
2. There’s a lot of regularity left here, but it’s all in the form of sequences of array elements. For example, the sequence [1, simple(1), 2] shows up regularly, as does [simple(4), 5, 0 , 6].

Here’s where I think the discussion overlaps. Enabling packing of sequences of elements would require one of three changes:

1. Only indefinite-length containers can have packed items.
2. The container count refers to unpacked count, which makes the packed CBOR invalid.
3. The container count refers to packed count, which means the decoder must adjust the total whenever a reference is encountered. This has additional implications for maps.

If it turns out that postfix sharing of data really is unique to domain names and that the problem isn’t generic, maybe we could solve it another way, for example special handling of anything within Tag 32. Sequence packing, however, is a space where I think we need a solution.

Brendan

> On 28 Aug 2020, at 00:26, Jim Schaad <[email-masked]> wrote:
>
>
>
> -----Original Message-----
> From: Carsten Bormann <[email-masked]>
> Sent: Thursday, August 27, 2020 2:32 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]; [email-masked]
> Subject: Re: [Cbor] Interactions of packed CBOR and tags
>
>
>
>> On 2020-08-27, at 23:00, Jim Schaad <[email-masked]> wrote:
>>
>> While building a test library of strings for evaluating my algorithm,
>> I ended up with a question of how tags interact with the idea of CBOR packing.
>> Specifically, if I use a standard date/time string with tag 0, should
>> that text string be considered as a candidate for packing?
>>
>> 0("1970-01-01T00:00Z") could potentially be compressed to 0(simple(3))
>>
>> The problem is that this is no longer a valid CBOR encoding so it
>> would not seem to be a legal thing to do.
>>
>> Question:  Must packed CBOR be valid CBOR or does that requirement
>> only apply to unpacked CBOR?
>
> Great question.
>
> The cop-out could be: either.
> Since CBOR-valid packed CBOR is a subset of (just well-formed) packed CBOR, it could be a parameter given to the compressor whether that is allowed to use compression opportunities like the above or not.
>
> What are the benefits/drawbacks:
>
> * (just well-formed) packed CBOR may lead to trouble with a generic decoder that cannot handle (present to the application) invalid constructs like 0(simple(3)).
> The application can decide whether it wants to live with this limitation or not.
>
> * the structural coherence of the packed structure (that this draft is about) will be expressed as a validity constraint.  It is a bit weird to then relax validity of what goes in there, but not entirely without precedent (e.g., tag 24, even though there is a more explicit firewall here).
>
> * not using those compression opportunities can be wasteful, not just for the example given above (tag 0), but also for tags like 32.
>
> I think I would emphasize the (just well-formed) packed CBOR, but still introduce CBOR-valid packed CBOR as a selectable additional constraint for applications that need to work with pre-packed (designed before packed was invented) generic decoders.
>
> [JLS] Yes I agree that only requiring that the result be well-formed makes the most sense.  It probably makes sense to discuss the implications in the document.  A more interesting case might be tag 26 which could have duplicate or prefix lines of text coming up frequently.
>
> I think it might make sense to reference tag 25 and say that this does the same thing only much better.
> [/JLS]
>
> Do we need to encode this selection?  (E.g., via different top-level tags.)  Probably not.
>
> [JLS] I don't think that there needs to be different top-level tags.
>
> Jim
>
>
> 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: Jim Schaad <[email-masked]>
Date: Thu, 3 Sep 2020 09:03:14 -0700

-----Original Message-----
From: Brendan Moran <[email-masked]> 
Sent: Thursday, September 3, 2020 4:57 AM
To: Jim Schaad <[email-masked]>
Cc: Carsten Bormann <[email-masked]>; [email-masked]
Subject: Re: [Cbor] Interactions of packed CBOR and tags

https://www.ietf.org
http://www.ietf.org

Encoded as CIRIs and arranged into an array, these URIs take up 161 bytes (N.B. it would only be 151 bytes for the raw URIs) [
  [1,"https", 2, "www.ietf.org"],
  [1,"http", 2, "www.ietf.org"],
  [1,"https", 2, "datatracker.ietf.org", 5, 0, 6, "group", 6, "cbor", 6, "about"],
  [1,"https", 2, "datatracker.ietf.org", 5, 0, 6, "doc", 6, "draft-bormann-cbor-packed"] ]

[JLS] I really wish the updated CRI document would get published.  This issue was discussed last sprint from somewhere around IETF 107 and into May that produced a proposal that uses a well known URI pattern along with one built in dictionary.  Using that encoding you would end up with

[  [2, "www.ietf.org"],
  [1, "www.ietf.org"],
  [2, "datatracker.ietf.org", "group", "cbor", "about"],
  [2, "datatracker.ietf.org", "doc", "draft-bormann-cbor-packed"] ]

This means that we are looking at an encoding size of 125 bytes rather than 161 bytes.   So when that finally gets written up with will have a better starting point.

[/JLS]

[JLS]  I don't find this to be very convoluted at all and it is what my compression algorithm generates automatically.  I look at the piece I split off from the prefix and see if I have "enough" duplicates to compress them down.  I am still trying to decide how to do some extraction from "the middle" of things.  Consider looking at 
["www.merch.ietf.org", "www.datatracker.ietf.org"]

It would be nice to think about compressing that as 

6([ "www.", "merch", "datatracker"], [".ietf.org""], 224(225(simple(2))), 224(226(simple(2)))] 

Where we have pulled both prefix and postfix strings extracted and maximize the amount of commonality.  

[/JLS]

[JLS] This would be taken care of by the fact that we have discussed doing the same prefix processing on arrays as well.  This was brought up specifically for the CRI case where we saw that this was going to be an issue.

[JLS] I think that we can all agree that option 2 would be a completely unacceptable.  For the purpose of the compressed output, it needs to be definite length as that is going to be the shortest.  I think in the above however, you are potentially confusing the result of compression vs the result of decompression.  The compressed form should always be definite length encoded, the result of decompression could be either definite length or indefinite length according to how it operates and not what the compressed form looks like and therefore does not need to be specified in the document.

[JLS] I expect that for sequence and map compression we are going to find that we are going to end up looking at compression at the start, middle and end of these.  In the case of map compression then the question of how this is represented and made into a deterministic encoding might become very interesting.  It is much easier to just compressed the keys and values and ignore the map structure.

Jim
[/JLS]

Brendan

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 3 Sep 2020 18:53:23 +0200

> Where we have pulled both prefix and postfix strings extracted and maximize the amount of commonality.  

I like the idea of adding suffix packing.

In the current proposal, to distinguish shared items from prefix packing, we have

— a separate table (and thus number space), which makes sense if prefixes are rarely used as shared items and v.v. (using a prefix as shared item just requires prefixing it to the empty item, though);
— separate referents (one with no content, one with the content the prefix is prefixed to).

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.

We could also rethink the whole separation of shared items from prefix/suffix items in this process.

As Brendan says, being able to optimize the tables so the frequently used items land in the areas that have short referents is important.

[Apologies for using the term referent, which isn’t even in my dictionaries with the meaning I’m using it for (the thing that references).  But that’s the usage I learned when I learned about them in the 1970s… [1]]

Making prefix/suffix packing well-defined for arrays isn’t hard.  For maps, there is no difference (assuming we are always handling full key/value pairs — just doing a single key or a value can be done by sharing items).

I don’t think we want to address what would be “deterministic packing”.

Grüße, Carsten

[1]: https://scholar.google.com/scholar?hl=en&q=Ross%2C+D.+T.%2C+%22Uniform+Referents%3A+An+Essential+Property+for+a+Software+Engineering+Language.%22+Paper+presented+at+the+3rd+International+Symposium+on+Computer+and+Information+Sciences+%28COINS-69%29%2C+Miami+Beach%2C+Florida%2C+18%2D%2D20+December+1969.

---

From: Brendan Moran <[email-masked]>
Date: Thu, 3 Sep 2020 16:57:53 +0000

> On 3 Sep 2020, at 17:03, Jim Schaad <[email-masked]> wrote:
>
>
>

[BJM] That’s really interesting. I like where it’s going. However it’s still going to be bigger than a cbor-encoded plain text URIs if you have more than a few > 23 byte path segments, which is a bit annoying. For example, https:// is 8 bytes. The scheme above compresses that to 1 byte, but introduces an overhead of 1 byte for the array, so we’ve saved 6 bytes. Each path segment has a 1-byte separator in plain text. In the scheme above, it has a text tag. This is the same total, except that the text encoding can omit the last delimiter. This means that we’ve saved only 5 bytes. If there are more than 23 path segments, then we lose another byte. If 5 or more path segments are more than 23 bytes long, we are at parity.

It depends on what the goals of the scheme are. CRI not always smaller. If size were the only goal, a hybrid approach that retains path separators would yield smaller results:

75 bytes:
>  [2, "datatracker.ietf.org/a-24-character-path-1234/draft-bormann-cbor-packed"]
76 bytes:
>  [2, "datatracker.ietf.org", "a-24-character-path-1234", "draft-bormann-cbor-packed"]

[/BJM]

> Where we have pulled both prefix and postfix strings extracted and maximize the amount of commonality.

[BJM]
Under the existing -01 draft, I’m not sure you can do much better than:

6([
  [
    6(simple(1)),
    6(simple(2))
  ]
  [
    “www.”,
    “merch”,
    “datatracker"
  ],
  “.ietf.org”,
  224(simple(0)),
  225(simple(0))
]

[/BJM]

> [JLS] This would be taken care of by the fact that we have discussed doing the same prefix processing on arrays as well.  This was brought up specifically for the CRI case where we saw that this wa…

I’m glad to hear that. Did I miss something on the mailing list? I assumed that this was still TBD since I didn’t see it there. Does that mean that the use of Tag 6 as the first prefix is being dropped so that array references are explicit? Or are array prefixes prohibited in the first slot? Or something else?

> [JLS] I think that we can all agree that option 2 would be a completely unacceptable.  For the purpose of the compressed output, it needs to be definite length as that is going to be the shortest.…

[BJM] I think I may have been confusing things, yes. When considering how a parser should handle a string prefix, it’s clear that the size is the packed size. This will cause some interesting problems for pull parsers, particularly those that use lazy evaluation. The SUIT demo parser saves pointers into the manifest CBOR when setting variables, rather than storing the variables themselves. It occurs to me that this will need also need a list of current reference tables for lazy evaluation. In many cases, that may be larger than the value being set, which will make things interesting. This will require some careful handling and probably some usage notes for implementors.

> [JLS] I expect that for sequence and map compression we are going to find that we are going to end up looking at compression at the start, middle and end of these.  In the case of map compression t…

[BJM] I agree. It becomes more interesting if you want to pack odd numbers of elements, for example 2 keys and one value.

Brendan

---

From: Brendan Moran <[email-masked]>
Date: Thu, 3 Sep 2020 17:05:54 +0000

> On 3 Sep 2020, at 17:53, Carsten Bormann <[email-masked]> wrote:
>

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

> We could also rethink the whole separation of shared items from prefix/suffix items in this process.

[BJM] I’m not sure that will result in the gains we want, since it inflates the reference values on shared items, which sit in a different reference space due to the use of simple values and 6(int) values. However, it might also yield some reduced cross-referencing. I’m not sure how this plays out overall, but my intuition is that 2 tables is better.

---

From: Jim Schaad <[email-masked]>
Date: Thu, 3 Sep 2020 11:13:50 -0700

-----Original Message-----
From: Brendan Moran <[email-masked]> 
Sent: Thursday, September 3, 2020 9:58 AM
To: Jim Schaad <[email-masked]>
Cc: Carsten Bormann <[email-masked]>; [email-masked]
Subject: Re: [Cbor] Interactions of packed CBOR and tags

> Encoded as CIRIs and arranged into an array, these URIs take up 161 
> bytes (N.B. it would only be 151 bytes for the raw URIs) [  
> [1,"https", 2, "www.ietf.org"],  [1,"http", 2, "www.ietf.org"],  
> [1,"https", 2, "datatracker.ietf.org", 5, 0, 6, "group", 6, "cbor", 6, 
> "about"],  [1,"https", 2, "datatracker.ietf.org", 5, 0, 6, "doc", 6, 
> "draft-bormann-cbor-packed"] ]
>
> [JLS] I really wish the updated CRI document would get published.  
> This issue was discussed last sprint from somewhere around IETF 107 
> and into May that produced a proposal that uses a well known URI 
> pattern along with one built in dictionary.  Using that encoding you 
> would end up with
>
> [  [2, "www.ietf.org"],
>  [1, "www.ietf.org"],
>  [2, "datatracker.ietf.org", "group", "cbor", "about"],  [2, 
> "datatracker.ietf.org", "doc", "draft-bormann-cbor-packed"] ]
>

75 bytes:
>  [2, 
> "datatracker.ietf.org/a-24-character-path-1234/draft-bormann-cbor-pack
> ed"]

[/BJM]

[JLS]  The original goal was to free devices from the work of having to parse URIs and allow them to just do a simpler copy into CoAP options when it gets back answers from a directory server among others.  Then we did see that the proposals were inflating the sizes too much.  I believe that https://mailarchive.ietf.org/arch/msg/core/B1O1VezNNnUMAkfneNUjXN988f4/ contains the latest proposal although there may have been off line changes I don't know about.

>    [1, simple(1), 2, simple(4), 5, 0, 6, "doc", 6, 
> "draft-bormann-cbor-packed"]  ],  [
>    simple(0),
>    "www",
>    "datatracker"
>  ],
>  "http",
>  6("s"),
>  ".ietf.org",
>  224(simple(2)),
>  225(simple(2))
> ])
>
> [JLS]  I don't find this to be very convoluted at all and it is what 
> my compression algorithm generates automatically.  I look at the piece 
> I split off from the prefix and see if I have "enough" duplicates to 
> compress them down.  I am still trying to decide how to do some 
> extraction from "the middle" of things.  Consider looking at 
> 6([ "www.", "merch", "datatracker"], [".ietf.org""], 
> 224(225(simple(2))), 224(226(simple(2)))]
>

[BJM]

6([
  [
    6(simple(1)),
    6(simple(2))
  ]
  [
    “www.”,
    “merch”,
    “datatracker"
  ],
  “.ietf.org”,
  224(simple(0)),
  225(simple(0))
]

[/BJM]
[JLS] After correcting both of our notations, in this case the it seems that both of the notations are the same size.  From your response, I am not sure if you believe that the notation I gave was not legal under the current draft or not.

[JLS] https://mailarchive.ietf.org/arch/msg/cbor/QYqEfdkQ2iE98M1on5QZA35kgrM/ is the message where Carsten made a proposal which has not gotten into the draft yet.

[BJM] I agree. It becomes more interesting if you want to pack odd numbers of elements, for example 2 keys and one value.
[JLS] I don't think that would ever be legal since it would not produce valid CBOR in the packed case.  The best you could do would be to convert to an array and pack that.

Jim

Brendan
>>> While building a test library of strings for evaluating my 
>>> algorithm, I ended up with a question of how tags interact with the idea of CBOR packing.
>>> Specifically, if I use a standard date/time string with tag 0, 
>>> should that text string be considered as a candidate for packing?
>>>

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 3 Sep 2020 21:55:54 +0200

On 2020-09-03, at 18:57, Brendan Moran <[email-masked]> wrote:
> 
> However it’s still going to be bigger than a cbor-encoded plain text URIs if you have more than a few > 23 byte path segments, which is a bit annoying.

It’s all in your head :-)

The point of CBOR (which also was the point of JSON) was to be a reasonably appropriate encoding for much of what an application wants to do (the difference between JSON and CBOR is in what is “reasonably appropriate” in the areas of application).

There is *always* a way to create a more compact bespoke encoding.  For anything.
For URIs: We haven’t even started Huffman-coding the string parts.  (Or LZ-coding with some smart predefined dictionary.  Whatever.)  So why worry about the length indicator for > 23 byte path segments, where the text itself could be so much more efficiently coded?

Engineers have a tendency to react to perceived optimization opportunities.  That is of course a good thing.  It turns bad when we start to tweak something and incur complexity costs just because it is slightly worse than something else.
(If it is much worse in some metric, and that particular metric matters, well then back to the drawing board.  But not here.)

Learning to use CBOR includes learning to tolerate the occasional bouts of cognitive dissonance that come from knowing “I could do this better” where the “better” is a few percent.

Grüße, Carsten

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 4 Sep 2020 06:53:08 +0200

> [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 postf…

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

Grüße, Carsten

---

From: Brendan Moran <[email-masked]>
Date: Fri, 4 Sep 2020 11:05:21 +0000

> On 3 Sep 2020, at 19:13, Jim Schaad <[email-masked]> wrote:
>>
[BJM]

It doesn’t look legal to me. The draft says:
> Packed-CBOR = #6.6([rump, [*prefix], *shared])

Normalising it with the -01 draft, I think we get the following (45 bytes):
>> 6([[6(224(simple(2))), 6(225(simple(2)))], ["www.", "merch", "datatracker"], ".ietf.org"])

That’s 2 bytes better than what I suggested.

[/BJM]

> [JLS] https://mailarchive.ietf.org/arch/msg/cbor/QYqEfdkQ2iE98M1on5QZA35kgrM/ is the message where Carsten made a proposal which has not gotten into the draft yet.

[BJM]
I’d read that, but I didn’t realise it was any more than an off-hand comment. Do I understand correctly that the following is the intent?

[
  [1,2,3,4],
  [1,2,4,8]
]

Is packed to:

6([
  [
    224([3,4]),
    224([4,8])
  ],
  [
    null,
    [1,2]
  ]
])

(Yes, this is a bad example, since it inflates the original.)

[/BJM]

---

From: Brendan Moran <[email-masked]>
Date: Fri, 4 Sep 2020 11:43:53 +0000

> On 3 Sep 2020, at 20:55, Carsten Bormann <[email-masked]> wrote:
>

Normally, I’d agree with you. However, I did carefully consider the tradeoffs in this case. My argument is that there are two competing optimisations here:

1. Reduce parsing overhead for handling URIs by encoding them in CBOR
2. (Simply) Reduce encoding size of URIs.

I agree that scheme identification is better done by enum. I agree that domain name/IP is better identified with explicit text for domain name or bytes for IP. I agree that port number is better encoded as an integer.

I’m not yet convinced that there is a substantial reduction in complexity to be had by encoding a textual path as an array of CBOR text elements versus ‘/‘ delimited elements. I’ll have to go read through the mail archives on that one.

If it turns out that there is not a substantial reduction in complexity, then I don’t see why it would make sense to encode them in this way, rather than sticking with conventional URI path encoding.

Brendan

---

From: Brendan Moran <[email-masked]>
Date: Fri, 4 Sep 2020 12:08:30 +0000

> On 4 Sep 2020, at 05:53, Carsten Bormann <[email-masked]> wrote:
>

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

---

From: Jim Schaad <[email-masked]>
Date: Fri, 4 Sep 2020 09:16:56 -0700

-----Original Message-----
From: Brendan Moran <[email-masked]> 
Sent: Friday, September 4, 2020 4:05 AM
To: Jim Schaad <[email-masked]>
Cc: [email-masked]; Carsten Bormann <[email-masked]>
Subject: Re: [Cbor] Interactions of packed CBOR and tags

>> my compression algorithm generates automatically.  I look at the 
>> piece I split off from the prefix and see if I have "enough" 
>> duplicates to compress them down.  I am still trying to decide how to 
>> do some extraction from "the middle" of things.  Consider looking at 
[BJM]

> Packed-CBOR = #6.6([rump, [*prefix], *shared])

[JLS] - True, I did a fast "how to I move the rump to the end" in my code and that was what I did quickly just to see what it looked like.

>> "datatracker"], ".ietf.org"])

[JLS] Yes - this is what I should have had.  Not sure where the second byte came from, one was the lost array on the substitute table.

[/BJM]

[BJM]

[
  [1,2,3,4],
  [1,2,4,8]
]

Is packed to:

6([
  [
    224([3,4]),
    224([4,8])
  ],
  [
    null,
    [1,2]
  ]
])

[/BJM]

[JLS] Yes that was my intent.  Note that this leads to some interesting decisions during packing for CRIs as the number of times a string is references is going to be changed by the fact that the first part of the array gets packed. So that

[
  [1, "ietf.org", "a", "b"],
  [1, "ietf.org", "c", "d"]
]

Means that "ietf.org" only occurs once and therefore does not need to get packed itself anymore.
[/JLS]

---

From: Carsten Bormann <[email-masked]>
Date: Fri, 4 Sep 2020 18:33:31 +0200

Yes, that is the fun part. The large number of interdependencies of the optimization opportunities is why I’m not very impressed with my current implementation.  Fortunately, like with any compressor, the implementation just needs to be good enough...

Sent from mobile, sorry for terse

> On 4. Sep 2020, at 18:17, Jim Schaad <[email-masked]> wrote:
> 
> Note that this leads to some interesting decisions during packing for CRIs as the number of times a string is references is going to be changed by the fact that the first part of the array gets packed.