[Cbor] Cbor-packed gem 0.1.5

[Carsten Bormann <[e-mail]>]

TL;DR: gem update

I pushed an updated version of the cbor-packed gem yesterday.  The cbor-packed gem can be used with cbor-diag to pack and unpack a CBOR data item.

The bug I fixed was a bit surprising to me, and it only occurs in larger examples, so I’ll give a quick summary.

References to the 17th and further shared-item table entries are expressed using Tag 6 with an zigzag-encoded integer value, e.g.,

6(0)
references the 17th item,
6(-1)
references the 18th item,
6(1)
references the 19th item, etc.

I had implemented that correctly.

Now in a larger example, the shared item table grew larger, actually large enough that the value of that tag became large enough to itself benefit from shared item compression:

6(6(-7))
references an item that is indexed by the result of referencing another shared item via 6(-7) and reversing the zigzag encoding (see Table 1 of cbor-packed).

The result of referencing 6(-7) was 44, i.e., a two-encoding-bytes reference yielded a two-encoding-bytes value — that was bug number one: The threshold for using a shared item reference should not be that the reference is not worse than the value, but it should require that the reference be shorter than the value.  But that was just a performance bug.

Bug number two was in my code that distinguishes shared item references from prefix references (some of which also might use tag 6).  The code did not dereference the tag value of the outer 6(…) before testing for an integer tag value, so it didn’t find an integer (meaning shared item), but instead incorrectly assumed a prefix reference.

This shows the value of running contorted examples.  It also demonstrates that in a compressor some bugs only get triggered in rare cases, which might be exposed first in the vicinity of another bug.

The next step clearly is writing a fuzzer(**) for CBOR data items and running that against the cbor-packed gem.

But before that happens, you can get the bug fix now:

    gem update cbor-packed

And if you haven’t used that yet, more about how to use cbor-packed in the context of cbor-diag is in:

<https://mailarchive.ietf.org/arch/msg/cbor/x0lFCFZ5j6N21JWDiABHQNn0ccA>

Grüße, Carsten

(**): Fun task: making the fuzzer “sticky” (non-random) enough so the packer actually finds redundancy that it can do something with...

PS.: An interesting distraction when chasing the bug was that my long and contrived test data had occurrences of 19 00FF (1+2-byte representation of 255), which of course became 18 FF (1+1-byte representation) after any kind of processing, so things never seemed to match up before I looked more closely.  Does anyone remember which CBOR implementation had that off-by-one error?