Duplicate map label detection for encoding (#209)
This adds duplicate map label detection during encoding as part of sorting.
There was a lot of rework of map sorting.
UsefulOutBuf_Compare() was changed to behave differently and more universally.
* Duplicate detection for encoding
* rework UsefulOutBuf_Compare and test
* Dup detection seems to be working
* Final tidy-up
---------
Co-authored-by: Laurence Lundblade <lgl@securitytheory.com>
diff --git a/src/UsefulBuf.c b/src/UsefulBuf.c
index 847395c..dae4eb1 100644
--- a/src/UsefulBuf.c
+++ b/src/UsefulBuf.c
@@ -1,6 +1,6 @@
/*==============================================================================
Copyright (c) 2016-2018, The Linux Foundation.
- Copyright (c) 2018-2023, Laurence Lundblade.
+ Copyright (c) 2018-2024, Laurence Lundblade.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
@@ -41,6 +41,7 @@
when who what, where, why
-------- ---- ---------------------------------------------------
+ 28/02/2022 llundblade Rearrange UsefulOutBuf_Compare().
19/11/2023 llundblade Add UsefulOutBuf_GetOutput().
19/11/2023 llundblade Add UsefulOutBuf_Swap().
19/11/2023 llundblade Add UsefulOutBuf_Compare().
@@ -433,21 +434,27 @@
*
* Code Reviewers: THIS FUNCTION DOES POINTER MATH
*/
-int UsefulOutBuf_Compare(UsefulOutBuf *me, size_t uStart1, size_t uStart2)
+int UsefulOutBuf_Compare(UsefulOutBuf *pMe,
+ const size_t uStart1, const size_t uLen1,
+ const size_t uStart2, const size_t uLen2)
{
const uint8_t *pBase;
const uint8_t *pEnd;
const uint8_t *p1;
const uint8_t *p2;
+ const uint8_t *p1End;
+ const uint8_t *p2End;
int uComparison;
- pBase = me->UB.ptr;
- pEnd = (const uint8_t *)pBase + me->data_len;
+ pBase = pMe->UB.ptr;
+ pEnd = (const uint8_t *)pBase + pMe->data_len;
p1 = pBase + uStart1;
p2 = pBase + uStart2;
+ p1End = p1 + uLen1;
+ p2End = p2 + uLen2;
uComparison = 0;
- while(p1 < pEnd && p2 < pEnd) {
+ while(p1 < pEnd && p2 < pEnd && p1 < p1End && p2 < p2End) {
uComparison = *p2 - *p1;
if(uComparison != 0) {
break;;
@@ -456,10 +463,21 @@
p2++;
}
+ if(uComparison == 0 && p1 != p1End && p2 != p2End) {
+ if(uLen1 > uLen2) {
+ uComparison = 1;
+ } else if(uLen2 < uLen1){
+ uComparison = -1;
+ } else {
+ return 0;
+ }
+ }
+
return uComparison;
}
+
/**
* @brief Reverse order of bytes in a buffer.
*
@@ -473,7 +491,7 @@
while(pStart < pEnd) {
pEnd--;
- uTmp = *pStart;
+ uTmp = *pStart;
*pStart = *pEnd;
*pEnd = uTmp;
pStart++;
diff --git a/src/qcbor_encode.c b/src/qcbor_encode.c
index 37b1c89..e4a7bf6 100644
--- a/src/qcbor_encode.c
+++ b/src/qcbor_encode.c
@@ -1287,7 +1287,7 @@
/**
- * @brief Decoded next item to get its length.
+ * @brief Decoded next item to get its lengths.
*
* Decode the next item in map no matter what type it is. It works
* recursively when an item is a map or array It returns offset just
@@ -1299,16 +1299,25 @@
* stuff that came in from outside. We still want a check for safety
* in case of bugs here, but it is OK to report end of input on error.
*/
-static uint32_t
+struct ItemLens {
+ uint32_t uLabelLen;
+ uint32_t uItemLen;
+};
+
+static struct ItemLens
QCBOREncode_Private_DecodeNextInMap(QCBOREncodeContext *pMe, uint32_t uStart)
{
- UsefulInputBuf InBuf;
- UsefulBufC EncodedMapBytes;
- QCBORError uCBORError;
+ UsefulInputBuf InBuf;
+ UsefulBufC EncodedMapBytes;
+ QCBORError uCBORError;
+ struct ItemLens Result;
+
+ Result.uLabelLen = 0;
+ Result.uItemLen = 0;
EncodedMapBytes = UsefulOutBuf_OutUBufOffset(&(pMe->OutBuf), uStart);
if(UsefulBuf_IsNULLC(EncodedMapBytes)) {
- return 0;
+ return Result;
}
UsefulInputBuf_Init(&InBuf, EncodedMapBytes);
@@ -1316,15 +1325,22 @@
/* This is always used on maps, so consume two, the label and the value */
uCBORError = QCBOR_Private_ConsumeNext(&InBuf);
if(uCBORError) {
- return 0;
- }
- uCBORError = QCBOR_Private_ConsumeNext(&InBuf);
- if(uCBORError) {
- return 0;
+ return Result;
}
/* Cast is safe because this is QCBOR which limits sizes to UINT32_MAX */
- return (uint32_t)UsefulInputBuf_Tell(&InBuf);
+ Result.uLabelLen = (uint32_t)UsefulInputBuf_Tell(&InBuf);
+
+ uCBORError = QCBOR_Private_ConsumeNext(&InBuf);
+ if(uCBORError) {
+ Result.uLabelLen = 0;
+ return Result;
+ }
+
+ Result.uItemLen = (uint32_t)UsefulInputBuf_Tell(&InBuf);
+
+ /* Cast is safe because this is QCBOR which limits sizes to UINT32_MAX */
+ return Result;
}
@@ -1342,12 +1358,13 @@
static void
QCBOREncode_Private_SortMap(QCBOREncodeContext *pMe, uint32_t uStart)
{
- bool bSwapped;
- int nComparison;
- uint32_t uLen2;
- uint32_t uLen1;
- uint32_t uStart1;
- uint32_t uStart2;
+ bool bSwapped;
+ int nComparison;
+ uint32_t uStart1;
+ uint32_t uStart2;
+ struct ItemLens Lens1;
+ struct ItemLens Lens2;
+
if(pMe->uError != QCBOR_SUCCESS) {
return;
@@ -1367,31 +1384,38 @@
* sizes are not the same and overlap may occur in the bytes being
* swapped.
*/
- do {
- uLen1 = QCBOREncode_Private_DecodeNextInMap(pMe, uStart);
- if(uLen1 == 0) {
+ do { /* Loop until nothing was swapped */
+ Lens1 = QCBOREncode_Private_DecodeNextInMap(pMe, uStart);
+ if(Lens1.uLabelLen == 0) {
/* It's an empty map. Nothing to do. */
break;
}
uStart1 = uStart;
- uStart2 = uStart1 + uLen1;
+ uStart2 = uStart1 + Lens1.uItemLen;
bSwapped = false;
while(1) {
- uLen2 = QCBOREncode_Private_DecodeNextInMap(pMe, uStart2);
- if(uLen2 == 0) {
+ Lens2 = QCBOREncode_Private_DecodeNextInMap(pMe, uStart2);
+ if(Lens2.uLabelLen == 0) {
break;
}
- nComparison = UsefulOutBuf_Compare(&(pMe->OutBuf), uStart1, uStart2);
+ nComparison = UsefulOutBuf_Compare(&(pMe->OutBuf),
+ uStart1, Lens1.uLabelLen,
+ uStart2, Lens2.uLabelLen);
if(nComparison < 0) {
- UsefulOutBuf_Swap(&(pMe->OutBuf), uStart1, uStart2, uStart2 + uLen2);
- uStart1 = uStart1 + uLen2;
+ UsefulOutBuf_Swap(&(pMe->OutBuf), uStart1, uStart2, uStart2 + Lens2.uItemLen);
+ uStart1 = uStart1 + Lens2.uItemLen; /* item 2 now in position of item 1 */
+ /* Lens1 is still valid as Lens1 for the next loop */
bSwapped = true;
- } else {
+ } else if(nComparison > 0) {
uStart1 = uStart2;
+ Lens1 = Lens2;
+ } else /* nComparison == 0 */ {
+ pMe->uError = QCBOR_ERR_DUPLICATE_LABEL;
+ return;
}
- uStart2 = uStart2 + uLen2;
+ uStart2 = uStart2 + Lens2.uItemLen;
}
} while(bSwapped);
}
@@ -1400,7 +1424,8 @@
/*
* Public functions for closing sorted maps. See qcbor/qcbor_encode.h
*/
-void QCBOREncode_CloseAndSortMap(QCBOREncodeContext *pMe)
+void
+QCBOREncode_CloseAndSortMap(QCBOREncodeContext *pMe)
{
uint32_t uStart;
@@ -1419,7 +1444,8 @@
/*
* Public functions for closing sorted maps. See qcbor/qcbor_encode.h
*/
-void QCBOREncode_CloseAndSortMapIndef(QCBOREncodeContext *pMe)
+void
+QCBOREncode_CloseAndSortMapIndef(QCBOREncodeContext *pMe)
{
uint32_t uStart;