intel / intel/tinycbor

Alternative map sorting

Open
#173 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C
Stars
630
Forks
222
Avg merge
1d 3h
Merged PRs (30d)
1

Description

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:
```c
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], ¤t[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?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.