Subject: [Cbor] 7049bis-02: Equivalence of CBOR data items

From: Thiago Macieira <[email-masked]>
Date: Sat, 03 Mar 2018 10:52:01 -0800

Hello all

This is my first post to the mailing list. I am the author and maintainer of 
TinyCBOR[1] and I have prepared a set of wrapper classes for introduction into 
Qt[2] adding support for CBOR[3].

First of all, thanks for addressing some of the uncertain areas of RFC 7049. 
Specifically, the part about key equivalence and sorting. I've read through 
the previous thread that discussed this and I agree with some of the posters 
there.

In any case, let's start with the "Canonical CBOR" part. This is the part I 
like.

It says that keys in a canonical map must be sorted by their bytewise 
canonical representation. In other words, it suffices to memcmp() two keys' 
canonical encoding to determine whether one should be sorted before the other, 
even for strings. For those who, like me, want to sort before encoding, the 
current draft has these advantages:

 1) two keys of different types can be sorted by type alone, ignoring payload
This is important because in the internal implementation's data model, before 
encoding, the data could be stored in a fashion that makes comparing different 
payloads difficult. It is my case.

 2) unsigned numbers have the same order in both memcmp and payload
Because of the big-endian representation and the way that CBOR 8-, 16-, 32- 
and 64-bit numbers (unsigned integers, lengths and tags) are represented, 
given two unsigned integers a and b, if a < b, then a is sorted before b 
bytewise too.

 3) string comparison is still memcmp
But not strcmp. However, once the sorting by length is done, memcmp can be 
used.

 4) confirming a proper sorting order is easy for any decoder
Since all keys are in bytewise lexicographical order, if the decoder memcmp() 
two adjacent keys, the result should be positive. Any other value is a 
violation of CBOR canonical encoding. Please note this does not guarantee 
uniqueness of keys (see below).

So in order to sort keys in a map before generating the encoding, one only has 
to be careful about negative numbers, where a < b → a sorts after b (sort by 
absolute value) and floating point. For floating point, the suggested way to 
compare would be to memcpy the value to an integer of the same size and 
compare that.

Moving on to the "Equivalence of keys" section, which I don't like too much 
(i.e., it needs improving). This section makes the comparison of a data item 
when used as a key different from when simply comparing items in, say, an 
array. Unless it is intentional that the following two arrays should compare 
equal:

	[h'4d 41 3d 3d']		and		[34("MA==")]

Note I'm not talking just yet about using those arrays as keys. I'm merely 
asking if an implementation holding each of them should report that the two 
arrays are equal. I assume not.

Consequently, we cannot use the same code to check uniqueness of map keys as 
the function used to sort items when placing them in a map. By the rules in 
the section of "Equivalence of keys", the two arrays above are equivalent and 
therefore both must not appear at the same time in the same map.

Is that intentional?

If it is, I believe my classes would have the following functionality:

 1) strict data item comparison
     Uses the rules for core canonical requirements, by:
     a) comparing the type
     b) for floating point, attempt down-conversion to fp16 and float, 
         then memcpy to a 16-, 32- or 64-bit unsigned integer
     c) comparing the number (unsigned integer, absolute of negative, etc.)
     d) for strings, memcmp the byte representation
[My code currently does not compare an integer equal to a floating point of 
the same value]

  2) data item equivalence
    I'm uncertain how I want to implement this. I don't want to perform 
    recursive equivalence check in arrays -- that is to say, two arrays are 
    equivalent if and only if they are actually the same. I'd be tempted to 
    say the same for maps used as keys too, as implementing that equivalence 
    would require an O(n²) algorithm, since even a map sorted by keys could 
    have alternate representations of the same equivalent value and they don't 
    need to be adjacent, as in a map with the three keys h'41', h'42' and "A".

[1] https://github.com/intel/tinycbor
[2] https://qt.io
[3] https://codereview.qt-project.org/#/q/project:qt/qtbase+topic:cbor,n,z
-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel Open Source Technology Center

---

From: Jeffrey Yasskin <[email-masked]>
Date: Sun, 04 Mar 2018 23:12:35 +0000

I agree that https://github.com/cbor-wg/CBORbis/pull/11 needed some more
work before merging. It's inconsistent with
https://tools.ietf.org/html/draft-ietf-cbor-7049bis-02#section-2, which
states that "integer and floating-point values are distinct in this model,
even if they have the same numeric value."
https://tools.ietf.org/html/draft-ietf-cbor-7049bis-02#section-2.2 provides
a way to refine map equivalence for particular applications, by saying
"Specific data models can also specify that values of different types are
equivalent for the purposes of map keys and encoder freedom." It goes on to
directly contradict
https://tools.ietf.org/html/draft-ietf-cbor-7049bis-02#section-4.7.1: "a
valid map MAY have both "0" and "0.0" as keys, …".

This isn't particularly the PR author's fault: those bits of the data model
were added by https://github.com/cbor-wg/CBORbis/pull/12, which was merged
the same day as #11. When I sent #12, I probably should have reviewed #11
to point out the conflicts.

Jeffrey

On Sat, Mar 3, 2018 at 10:52 AM Thiago Macieira <[email-masked]>
wrote:

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