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/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
*/