Map sorting
* Checkpoint work on sorting and CDE
* sort seems to be working
* Complete testing and doc
* revert float stuff so this PR is only sorting
* Documentation and tidiness for UsefulOutBuf
* Final tidy-up of sorting doc and code
---------
Co-authored-by: Laurence Lundblade <lgl@securitytheory.com>
diff --git a/src/UsefulBuf.c b/src/UsefulBuf.c
index b36e5d0..847395c 100644
--- a/src/UsefulBuf.c
+++ b/src/UsefulBuf.c
@@ -1,6 +1,6 @@
/*==============================================================================
Copyright (c) 2016-2018, The Linux Foundation.
- Copyright (c) 2018-2022, Laurence Lundblade.
+ Copyright (c) 2018-2023, Laurence Lundblade.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
@@ -41,9 +41,12 @@
when who what, where, why
-------- ---- ---------------------------------------------------
+ 19/11/2023 llundblade Add UsefulOutBuf_GetOutput().
+ 19/11/2023 llundblade Add UsefulOutBuf_Swap().
+ 19/11/2023 llundblade Add UsefulOutBuf_Compare().
19/12/2022 llundblade Don't pass NULL to memmove when adding empty data.
4/11/2022 llundblade Add GetOutPlace and Advance to UsefulOutBuf
- 3/6/2021 mcr/llundblade Fix warnings related to --Wcast-qual
+ 3/6/2021 mcr/llundblade Fix warnings related to --Wcast-qual
01/28/2020 llundblade Refine integer signedness to quiet static analysis.
01/08/2020 llundblade Documentation corrections & improved code formatting.
11/08/2019 llundblade Re check pointer math and update comments
@@ -424,3 +427,105 @@
return result;
}
+
+/*
+ * Public function -- see UsefulBuf.h
+ *
+ * Code Reviewers: THIS FUNCTION DOES POINTER MATH
+ */
+int UsefulOutBuf_Compare(UsefulOutBuf *me, size_t uStart1, size_t uStart2)
+{
+ const uint8_t *pBase;
+ const uint8_t *pEnd;
+ const uint8_t *p1;
+ const uint8_t *p2;
+ int uComparison;
+
+ pBase = me->UB.ptr;
+ pEnd = (const uint8_t *)pBase + me->data_len;
+ p1 = pBase + uStart1;
+ p2 = pBase + uStart2;
+
+ uComparison = 0;
+ while(p1 < pEnd && p2 < pEnd) {
+ uComparison = *p2 - *p1;
+ if(uComparison != 0) {
+ break;;
+ }
+ p1++;
+ p2++;
+ }
+
+ return uComparison;
+}
+
+
+/**
+ * @brief Reverse order of bytes in a buffer.
+ *
+ * This reverses bytes starting at pStart, up to, but not including
+ * the byte at pEnd
+ */
+static void
+UsefulOutBuf_Private_ReverseBytes(uint8_t *pStart, uint8_t *pEnd)
+{
+ uint8_t uTmp;
+
+ while(pStart < pEnd) {
+ pEnd--;
+ uTmp = *pStart;
+ *pStart = *pEnd;
+ *pEnd = uTmp;
+ pStart++;
+ }
+}
+
+
+/*
+ * Public function -- see UsefulBuf.h
+ *
+ * Code Reviewers: THIS FUNCTION DOES POINTER MATH
+ */
+void UsefulOutBuf_Swap(UsefulOutBuf *pMe, size_t uStartOffset, size_t uPivotOffset, size_t uEndOffset)
+{
+ uint8_t *pBase;
+
+ if(uStartOffset > pMe->data_len || uPivotOffset > pMe->data_len || uEndOffset > pMe->data_len) {
+ return;
+ }
+
+ if(uStartOffset > uPivotOffset || uStartOffset > uEndOffset || uPivotOffset > uEndOffset) {
+ return;
+ }
+
+ /* This is the "reverse" algorithm to swap two memory regions */
+ pBase = pMe->UB.ptr;
+ UsefulOutBuf_Private_ReverseBytes(pBase + uStartOffset, pBase + uPivotOffset);
+ UsefulOutBuf_Private_ReverseBytes(pBase + uPivotOffset, pBase + uEndOffset);
+ UsefulOutBuf_Private_ReverseBytes(pBase + uStartOffset, pBase + uEndOffset);
+}
+
+
+/*
+ * Public function -- see UsefulBuf.h
+ */
+UsefulBufC
+UsefulOutBuf_OutUBufOffset(UsefulOutBuf *pMe, size_t uOffset)
+{
+ UsefulBufC ReturnValue;
+
+ ReturnValue = UsefulOutBuf_OutUBuf(pMe);
+
+ if(UsefulBuf_IsNULLC(ReturnValue)) {
+ return NULLUsefulBufC;
+ }
+
+ if(uOffset >= ReturnValue.len) {
+ return NULLUsefulBufC;
+ }
+
+ ReturnValue.ptr = (const uint8_t *)ReturnValue.ptr + uOffset;
+ ReturnValue.len -= uOffset;
+
+ return ReturnValue;
+}
diff --git a/src/qcbor_encode.c b/src/qcbor_encode.c
index 53df657..754f7c5 100644
--- a/src/qcbor_encode.c
+++ b/src/qcbor_encode.c
@@ -1,6 +1,6 @@
/*==============================================================================
Copyright (c) 2016-2018, The Linux Foundation.
- Copyright (c) 2018-2022, Laurence Lundblade.
+ Copyright (c) 2018-2023, Laurence Lundblade.
Copyright (c) 2021, Arm Limited.
All rights reserved.
@@ -570,7 +570,7 @@
(void)uMajorType;
(void)pMe;
#endif
-
+
return false;
}
@@ -778,6 +778,32 @@
/*
+ * Public functions for adding a double. See qcbor/qcbor_encode.h
+ */
+void QCBOREncode_AddDoubleDeterministic(QCBOREncodeContext *me, double dNum)
+{
+ if(dNum <= (double)UINT64_MAX && dNum >= 0) {
+ uint64_t uNum = (uint64_t)dNum;
+ if((double)uNum == dNum) {
+ QCBOREncode_AddUInt64(me, uNum);
+ return;
+ }
+ /* Fall through */
+ } else if(dNum >= (double)INT64_MIN && dNum < 0) {
+ int64_t nNum = (int64_t)dNum;
+ if((double)nNum == dNum) {
+ QCBOREncode_AddInt64(me, nNum);
+ return;
+ }
+ /* Fall through */
+ }
+ //const IEEE754_union uNum = IEEE754_DoubleToSmallest(dNum);
+
+ //QCBOREncode_AddType7(me, uNum.uSize, uNum.uValue);
+}
+
+
+/*
* Public functions for adding a float. See qcbor/qcbor_encode.h
*/
void QCBOREncode_AddFloatNoPreferred(QCBOREncodeContext *me, float fNum)
@@ -917,6 +943,299 @@
}
+
+/**
+ * @brief Decode a CBOR item head.
+ *
+ * @param[in] pUInBuf UsefulInputBuf to read from.
+ * @param[out] pnMajorType Major type of decoded head.
+ * @param[out] puArgument Argument of decoded head.
+ * @param[out] pnAdditionalInfo Additional info from decoded head.
+ *
+ * @return SUCCESS if a head was decoded
+ * HIT_END if there were not enough bytes to decode a head
+ * UNSUPPORTED if the decoded item is not one that is supported
+ *
+ * This is copied from qcbor_decode.c rather than referenced. This
+ * makes the core decoder 60 bytes smaller because it gets inlined.
+ * It would not get inlined if it was referenced. It is important to
+ * make the core decoder as small as possible. The copy here does make
+ * map sorting 200 bytes bigger, but map sorting is rarely used in
+ * environments that need small object code. It would also make
+ * qcbor_encode.c depend on qcbor_decode.c
+ *
+ * This is also super stable and tested. It implements the very
+ * well-defined part of CBOR that will never change. So this won't
+ * change.
+ */
+static QCBORError
+QCBOREncodePriv_DecodeHead(UsefulInputBuf *pUInBuf,
+ int *pnMajorType,
+ uint64_t *puArgument,
+ int *pnAdditionalInfo)
+{
+ QCBORError uReturn;
+
+ /* Get the initial byte that every CBOR data item has and break it
+ * down. */
+ const int nInitialByte = (int)UsefulInputBuf_GetByte(pUInBuf);
+ const int nTmpMajorType = nInitialByte >> 5;
+ const int nAdditionalInfo = nInitialByte & 0x1f;
+
+ /* Where the argument accumulates */
+ uint64_t uArgument;
+
+ if(nAdditionalInfo >= LEN_IS_ONE_BYTE && nAdditionalInfo <= LEN_IS_EIGHT_BYTES) {
+ /* Need to get 1,2,4 or 8 additional argument bytes. Map
+ * LEN_IS_ONE_BYTE..LEN_IS_EIGHT_BYTES to actual length.
+ */
+ static const uint8_t aIterate[] = {1,2,4,8};
+
+ /* Loop getting all the bytes in the argument */
+ uArgument = 0;
+ for(int i = aIterate[nAdditionalInfo - LEN_IS_ONE_BYTE]; i; i--) {
+ /* This shift and add gives the endian conversion. */
+ uArgument = (uArgument << 8) + UsefulInputBuf_GetByte(pUInBuf);
+ }
+ } else if(nAdditionalInfo >= ADDINFO_RESERVED1 && nAdditionalInfo <= ADDINFO_RESERVED3) {
+ /* The reserved and thus-far unused additional info values */
+ uReturn = QCBOR_ERR_UNSUPPORTED;
+ goto Done;
+ } else {
+ /* Less than 24, additional info is argument or 31, an
+ * indefinite-length. No more bytes to get.
+ */
+ uArgument = (uint64_t)nAdditionalInfo;
+ }
+
+ if(UsefulInputBuf_GetError(pUInBuf)) {
+ uReturn = QCBOR_ERR_HIT_END;
+ goto Done;
+ }
+
+ /* All successful if arrived here. */
+ uReturn = QCBOR_SUCCESS;
+ *pnMajorType = nTmpMajorType;
+ *puArgument = uArgument;
+ *pnAdditionalInfo = nAdditionalInfo;
+
+Done:
+ return uReturn;
+}
+
+
+/**
+ * @brief Consume the next item from a UsefulInputBuf.
+ *
+ * @param[in] pInBuf UsefulInputBuf from which to consume item.
+ *
+ * Recursive, but stack usage is light and encoding depth limit
+ */
+static QCBORError
+QCBOREncodePriv_ConsumeNext(UsefulInputBuf *pInBuf)
+{
+ int nMajor;
+ uint64_t uArgument;
+ int nAdditional;
+ uint16_t uItemCount;
+ uint16_t uMul;
+ uint16_t i;
+ QCBORError uCBORError;
+
+ uCBORError = QCBOREncodePriv_DecodeHead(pInBuf, &nMajor, &uArgument, &nAdditional);
+ if(uCBORError != QCBOR_SUCCESS) {
+ return uCBORError;
+ }
+
+ uMul = 1;
+
+ switch(nMajor) {
+ case CBOR_MAJOR_TYPE_POSITIVE_INT: /* Major type 0 */
+ case CBOR_MAJOR_TYPE_NEGATIVE_INT: /* Major type 1 */
+ break;
+
+ case CBOR_MAJOR_TYPE_SIMPLE:
+ return uArgument == CBOR_SIMPLE_BREAK ? 1 : 0;
+ break;
+
+ case CBOR_MAJOR_TYPE_BYTE_STRING:
+ case CBOR_MAJOR_TYPE_TEXT_STRING:
+ if(nAdditional == LEN_IS_INDEFINITE) {
+ /* Segments of indefinite length */
+ while(QCBOREncodePriv_ConsumeNext(pInBuf) == 0);
+ }
+ (void)UsefulInputBuf_GetBytes(pInBuf, uArgument);
+ break;
+
+ case CBOR_MAJOR_TYPE_TAG:
+ QCBOREncodePriv_ConsumeNext(pInBuf);
+ break;
+
+ case CBOR_MAJOR_TYPE_MAP:
+ uMul = 2;
+ /* Fallthrough */
+ case CBOR_MAJOR_TYPE_ARRAY:
+ uItemCount = (uint16_t)uArgument * uMul;
+ if(nAdditional == LEN_IS_INDEFINITE) {
+ uItemCount = UINT16_MAX;
+ }
+ for(i = uItemCount; i > 0; i--) {
+ if(QCBOREncodePriv_ConsumeNext(pInBuf)) {
+ /* End of indefinite length */
+ break;
+ }
+ }
+ break;
+ }
+
+ return QCBOR_SUCCESS;
+}
+
+
+/**
+ * @brief Decoded next item to get its length.
+ *
+ * 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
+ * past the item decoded or zero there are no more items in the output
+ * buffer.
+ *
+ * This doesn't distinguish between end of the input and an error
+ * because it is used to decode stuff we encoded into a buffer, not
+ * 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
+QCBOREncodePriv_DecodeNextInMap(QCBOREncodeContext *pMe, uint32_t uStart)
+{
+ UsefulInputBuf InBuf;
+ UsefulBufC EncodedMapBytes;
+ QCBORError uCBORError;
+
+ EncodedMapBytes = UsefulOutBuf_OutUBufOffset(&(pMe->OutBuf), uStart);
+ if(UsefulBuf_IsNULLC(EncodedMapBytes)) {
+ return 0;
+ }
+
+ UsefulInputBuf_Init(&InBuf, EncodedMapBytes);
+
+ /* This is always used on maps, so consume two, the label and the value */
+ uCBORError = QCBOREncodePriv_ConsumeNext(&InBuf);
+ if(uCBORError) {
+ return 0;
+ }
+ uCBORError = QCBOREncodePriv_ConsumeNext(&InBuf);
+ if(uCBORError) {
+ return 0;
+ }
+
+ /* Cast is safe because this is QCBOR which limits sizes to UINT32_MAX */
+ return (uint32_t)UsefulInputBuf_Tell(&InBuf);
+}
+
+
+/**
+ * @brief Sort items lexographically by encoded labels.
+ *
+ * @param[in] pMe Encoding context.
+ * @param[in] uStart Offset in outbuf of first item for sorting.
+ *
+ * This reaches into the UsefulOutBuf in the encoding context and
+ * sorts encoded CBOR items. The byte offset start of the items is at
+ * @c uStart and it goes to the end of valid bytes in the
+ * UsefulOutBuf.
+ */
+static void
+QCBOREncodePriv_SortMap(QCBOREncodeContext *pMe, uint32_t uStart)
+{
+ bool bSwapped;
+ int nComparison;
+ uint32_t uLen2;
+ uint32_t uLen1;
+ uint32_t uStart1;
+ uint32_t uStart2;
+
+ if(pMe->uError != QCBOR_SUCCESS) {
+ return;
+ }
+
+ /* Bubble sort because the sizes of all the items are not the
+ * same. It works with adjacent pairs so the swap is not too
+ * difficult even though sizes are different.
+ *
+ * While bubble sort is n-squared, it seems OK here because n will
+ * usually be small and the comparison and swap functions aren't
+ * too CPU intensive.
+ *
+ * Another approach would be to have an array of offsets to the
+ * items. However this requires memory allocation and the swap
+ * operation for quick sort or such is complicated because the item
+ * sizes are not the same and overlap may occur in the bytes being
+ * swapped.
+ */
+ do {
+ uLen1 = QCBOREncodePriv_DecodeNextInMap(pMe, uStart);
+ if(uLen1 == 0) {
+ /* It's an empty map. Nothing to do. */
+ break;
+ }
+ uStart1 = uStart;
+ uStart2 = uStart1 + uLen1;
+ bSwapped = false;
+
+ while(1) {
+ uLen2 = QCBOREncodePriv_DecodeNextInMap(pMe, uStart2);
+ if(uLen2 == 0) {
+ break;
+ }
+
+ nComparison = UsefulOutBuf_Compare(&(pMe->OutBuf), uStart1, uStart2);
+ if(nComparison < 0) {
+ UsefulOutBuf_Swap(&(pMe->OutBuf), uStart1, uStart2, uStart2 + uLen2);
+ uStart1 = uStart1 + uLen2;
+ bSwapped = true;
+ } else {
+ uStart1 = uStart2;
+ }
+ uStart2 = uStart2 + uLen2;
+ }
+ } while(bSwapped);
+}
+
+
+/*
+ * Public functions for closing sorted maps. See qcbor/qcbor_encode.h
+ */
+void QCBOREncode_CloseAndSortMap(QCBOREncodeContext *pMe)
+{
+ uint32_t uStart;
+
+ /* The Header for the map we are about to sort hasn't been
+ * inserted yet, so uStart is the position of the first item
+ * and the end out the UsefulOutBuf data is the end of the
+ * items we are about to sort.
+ */
+ uStart = Nesting_GetStartPos(&(pMe->nesting));
+ QCBOREncodePriv_SortMap(pMe, uStart);
+
+ QCBOREncode_CloseMapOrArray(pMe, CBOR_MAJOR_TYPE_MAP);
+}
+
+
+/*
+ * Public functions for closing sorted maps. See qcbor/qcbor_encode.h
+ */
+void QCBOREncode_CloseAndSortMapIndef(QCBOREncodeContext *pMe)
+{
+ uint32_t uStart;
+
+ uStart = Nesting_GetStartPos(&(pMe->nesting));
+ QCBOREncodePriv_SortMap(pMe, uStart);
+
+ QCBOREncode_CloseMapOrArrayIndefiniteLength(pMe, CBOR_MAJOR_NONE_TYPE_MAP_INDEFINITE_LEN);
+}
+
+
/*
* Public functions for closing bstr wrapping. See qcbor/qcbor_encode.h
*/