Alternative map sorting

[sijohans]

Hello,

I've been looking into the CBOR validator and how maps are considered as sorted or not. In another project, I have previously been using another serialization standard that strictly defines maps in another way. Such as keys must only be strings, keys must be stored in lexicographical order and that no duplicates are allowed. Now we are looking into changing to cbor.

The CBOR specification does not strictly specifies what an ordered map is, but recommends that they should also be sorted in length. Meaning that "aa" > "b".

The alternatives are:

• Change sorting specification in our protocol (to order the fields like CBOR specification recommends)
• Not having sorted maps
• Finding/adapting a cbor library to allow for alternative sorting

Sorting is nice since is allows for linear parsing. Since we rely on this, we cannot directly swap to cbor. I would like to start a discussion of supporting an alternative sorting in tinycbor.

Wrote a short proof of concept for this (removes old sorting behavior) cborvalidation.c:475:

        if (flags & CborValidateMapIsSorted) {
            if (previous) {
                uint64_t len1, len2;
                const uint8_t *ptr;

                /* extract the two lengths */
                ptr = previous;
                _cbor_value_extract_number(&ptr, it->parser->end, &len1);
                ptr = current;
                _cbor_value_extract_number(&ptr, it->parser->end, &len2);


                size_t bytelen1 = (size_t)(previous_end - previous);
                size_t bytelen2 = (size_t)(it->ptr - current);

                /*
                 * Offset of actual key value (not including type information) is bytelenX - lenX??
                 * What if key value is indefinite??
                 */

                int r = memcmp(&previous[bytelen1 - len1], &current[bytelen2 - len2], len1 <= len2 ? len1 : len2);

                if (r == 0 && len1 != len2)
                    r = len1 < len2 ? -1 : +1;
                if (r > 0)
                    return CborErrorMapNotSorted;
                if (r == 0 && (flags & CborValidateMapKeysAreUnique) == CborValidateMapKeysAreUnique)
                    return CborErrorMapKeysNotUnique;

            }

Would it be possible to add a flag that would allow for this kind of sorting?

[thiagomacieira]

I don't want to add it to TinyCBOR. You don't have to obey the sorting order specified by the CBOR RFC. And, to be honest, what's in the RFC is pretty vague -- the updated RFC should have some clarifications.

If you're using the validating API, you can skip the flag that tests the sorting order and then simply validate your order in your own code.

Note you don't have to validate either.