Add the framework needed for BEJ encoding
This change adds the framework needed for BEJ encoding. Inorder to keep
the patch smaller, I only added the basic framework needed to understand
how the encoding is done. Rest of the functionality and testing will
be added in the later patches.
Signed-off-by: Kasun Athukorala <kasunath@google.com>
Change-Id: If2bd315fe5a3e6c7afff2af1750434042517790b
diff --git a/src/bej_common.c b/src/bej_common.c
index 1d3be07..0e1cf10 100644
--- a/src/bej_common.c
+++ b/src/bej_common.c
@@ -23,3 +23,22 @@
// In nnint, first byte indicate how many bytes are there.
return *nnint + sizeof(uint8_t);
}
+
+uint8_t bejNnintEncodingSizeOfUInt(uint64_t val)
+{
+ uint8_t bytes = 0;
+ do
+ {
+ // Even if the value is 0, we need a byte for that.
+ ++bytes;
+ val = val >> 8;
+ } while (val != 0);
+ // Need 1 byte to add the nnint length.
+ return bytes + 1;
+}
+
+uint8_t bejNnintLengthFieldOfUInt(uint64_t val)
+{
+ // From the size of the encoded value, we need 1 byte for the length field.
+ return bejNnintEncodingSizeOfUInt(val) - 1;
+}
diff --git a/src/bej_decoder_core.c b/src/bej_decoder_core.c
index efed4fc..fe6dad6 100644
--- a/src/bej_decoder_core.c
+++ b/src/bej_decoder_core.c
@@ -30,21 +30,6 @@
} while (0)
/**
- * @brief Check a given varable is NULL. If it is NULL, this will return with
- * bejErrorNullParameter. If the variable is not NULL, this will will not
- * return.
- */
-#define NULL_CHECK(param, structStr) \
- do \
- { \
- if ((param) == NULL) \
- { \
- fprintf(stderr, "nullCheck: %s cannot be null\n", structStr); \
- return bejErrorNullParameter; \
- } \
- } while (0)
-
-/**
* @brief Get the integer value from BEJ byte stream.
*
* @param[in] bytes - valid pointer to a byte stream in little-endian format.
diff --git a/src/bej_encoder_core.c b/src/bej_encoder_core.c
new file mode 100644
index 0000000..e289032
--- /dev/null
+++ b/src/bej_encoder_core.c
@@ -0,0 +1,208 @@
+#include "bej_encoder_core.h"
+
+#include "bej_common.h"
+#include "bej_encoder_metadata.h"
+
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * @brief Encode a unsigned value with nnint format.
+ */
+static int bejEncodeNnint(uint64_t value,
+ struct BejEncoderOutputHandler* output)
+{
+ // The length of the value bytes in nnint.
+ uint8_t nnintLengthByte = bejNnintLengthFieldOfUInt(value);
+ RETURN_IF_IERROR(output->recvOutput(&nnintLengthByte, sizeof(uint8_t),
+ output->handlerContext));
+ // Write the nnint value bytes.
+ return output->recvOutput(&value, nnintLengthByte, output->handlerContext);
+}
+
+/**
+ * @brief Encode a BejTupleF type.
+ */
+static int bejEncodeFormat(const struct BejTupleF* format,
+ struct BejEncoderOutputHandler* output)
+{
+ return output->recvOutput(format, sizeof(struct BejTupleF),
+ output->handlerContext);
+}
+
+/**
+ * @brief Encode a BejSet or BejArray type.
+ */
+static int bejEncodeBejSetOrArray(struct RedfishPropertyParent* node,
+ struct BejEncoderOutputHandler* output)
+{
+ // Encode Sequence number.
+ RETURN_IF_IERROR(bejEncodeNnint(node->metaData.sequenceNumber, output));
+ // Add the format.
+ RETURN_IF_IERROR(bejEncodeFormat(&node->nodeAttr.format, output));
+ // Encode the value length.
+ RETURN_IF_IERROR(bejEncodeNnint(node->metaData.vSize, output));
+ // Encode the child count
+ return bejEncodeNnint(node->nChildren, output);
+}
+
+/**
+ * @brief Encode the provided node.
+ */
+static int bejEncodeNode(void* node, struct BejEncoderOutputHandler* output)
+{
+ struct RedfishPropertyNode* nodeInfo = node;
+ switch (nodeInfo->format.principalDataType)
+ {
+ case bejSet:
+ RETURN_IF_IERROR(bejEncodeBejSetOrArray(node, output));
+ break;
+ default:
+ fprintf(stderr, "Unsupported node type: %d\n",
+ nodeInfo->format.principalDataType);
+ return -1;
+ }
+ return 0;
+}
+
+/**
+ * @brief A helper function to add a parent to the stack.
+ */
+static int bejPushParentToStack(struct RedfishPropertyParent* parent,
+ struct BejPointerStackCallback* stack)
+{
+ // Before pushing the parent node, initialize its nextChild as the first
+ // child.
+ parent->metaData.nextChild = parent->firstChild;
+ return stack->stackPush(parent, stack->stackContext);
+}
+
+/**
+ * @brief Process all the child nodes of a parent.
+ */
+static int bejProcessChildNodes(struct RedfishPropertyParent* parent,
+ struct BejPointerStackCallback* stack,
+ struct BejEncoderOutputHandler* output)
+{
+ // Get the next child of the parent.
+ void* childPtr = parent->metaData.nextChild;
+
+ while (childPtr != NULL)
+ {
+ // First encode the current child node.
+ RETURN_IF_IERROR(bejEncodeNode(childPtr, output));
+ // If this child node has its own children, add it to the stack and
+ // return. Because we need to encode the children of the newly added
+ // node before continuing to encode the child nodes of the current
+ // parent.
+ if (bejTreeIsParentType(childPtr))
+ {
+ RETURN_IF_IERROR(bejPushParentToStack(childPtr, stack));
+ // Update the next child of the current parent we need to
+ // process.
+ bejParentGoToNextChild(parent, childPtr);
+ return 0;
+ }
+ childPtr = bejParentGoToNextChild(parent, childPtr);
+ }
+ return 0;
+}
+
+/**
+ * @brief Encode the provided JSON tree.
+ *
+ * The node metadata should be initialized before using this function.
+ */
+static int bejEncodeTree(struct RedfishPropertyParent* root,
+ struct BejPointerStackCallback* stack,
+ struct BejEncoderOutputHandler* output)
+{
+ // We need to encode a parent node before its child nodes. So encoding the
+ // root first.
+ RETURN_IF_IERROR(bejEncodeNode(root, output));
+ // Once the root is encoded, push it to the stack used to traverse the child
+ // nodes. We need to keep a parent in this stack until all the child nodes
+ // of this parent has been encoded. Only then we remove the parent node from
+ // the stack.
+ RETURN_IF_IERROR(bejPushParentToStack(root, stack));
+
+ while (!stack->stackEmpty(stack->stackContext))
+ {
+ struct RedfishPropertyParent* parent =
+ stack->stackPeek(stack->stackContext);
+
+ // Encode all the child nodes of the current parent node. If one of
+ // these child nodes has its own child nodes, that child node will be
+ // encoded and added to the stack and this function will return. The
+ // rest of the children of the current parent will be encoded later
+ // (after processing all the nodes under the child node added to the
+ // stack).
+ RETURN_IF_IERROR(bejProcessChildNodes(parent, stack, output));
+
+ // If a new node hasn't been added to the stack by
+ // bejProcessChildNodes(), we know that this parent's child nodes have
+ // been processed. If a new node has been added, then next we need to
+ // process the children of the newly added node.
+ if (parent != stack->stackPeek(stack->stackContext))
+ {
+ continue;
+ }
+ stack->stackPop(stack->stackContext);
+ }
+ return 0;
+}
+
+int bejEncode(const struct BejDictionaries* dictionaries,
+ uint16_t majorSchemaStartingOffset,
+ enum BejSchemaClass schemaClass,
+ struct RedfishPropertyParent* root,
+ struct BejEncoderOutputHandler* output,
+ struct BejPointerStackCallback* stack)
+{
+ NULL_CHECK(dictionaries, "dictionaries");
+ NULL_CHECK(dictionaries->schemaDictionary, "schemaDictionary");
+ NULL_CHECK(dictionaries->annotationDictionary, "annotationDictionary");
+
+ NULL_CHECK(root, "root");
+
+ NULL_CHECK(output, "output");
+ NULL_CHECK(stack, "stack");
+
+ // Assert root node.
+ if (root->nodeAttr.format.principalDataType != bejSet)
+ {
+ fprintf(stderr, "Invalid root node\n");
+ return -1;
+ }
+
+ // First we need to encode a parent node before its child nodes. But before
+ // encoding the parent node, the encoder has to figure out the total size
+ // need to encode the parent's child nodes. Therefore first the encoder need
+ // to visit the child nodes and calculate the size need to encode them
+ // before producing the encoded bytes for the parent node.
+ //
+ // So first the encoder will visit child nodes and calculate the size need
+ // to encode each child node. Then store this information in metadata
+ // properties in each node struct.
+ // Next the encoder will again visit each node starting from the parent
+ // node, and produce the encoded bytes.
+
+ // First calculate metadata for encoding each node.
+ RETURN_IF_IERROR(bejUpdateNodeMetadata(
+ dictionaries, majorSchemaStartingOffset, root, stack));
+
+ // Derive the header of the encoded output.
+ // BEJ version
+ uint32_t version = BEJ_VERSION;
+ RETURN_IF_IERROR(
+ output->recvOutput(&version, sizeof(uint32_t), output->handlerContext));
+ uint16_t reserved = 0;
+ RETURN_IF_IERROR(output->recvOutput(&reserved, sizeof(uint16_t),
+ output->handlerContext));
+ RETURN_IF_IERROR(output->recvOutput(&schemaClass, sizeof(uint8_t),
+ output->handlerContext));
+
+ // Produce the encoded bytes for the nodes using the previously calculated
+ // metadata.
+ return bejEncodeTree(root, stack, output);
+}
diff --git a/src/bej_encoder_metadata.c b/src/bej_encoder_metadata.c
new file mode 100644
index 0000000..16264c1
--- /dev/null
+++ b/src/bej_encoder_metadata.c
@@ -0,0 +1,192 @@
+#include "bej_encoder_metadata.h"
+
+#include "bej_common.h"
+#include "bej_dictionary.h"
+
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * @brief Update metadata of leaf nodes.
+ *
+ * @param dictionaries - dictionaries needed for encoding.
+ * @param parentDictionary - dictionary used by this node's parent.
+ * @param childPtr - a pointer to the leaf node.
+ * @param childIndex - if this node is an array element, this is the array
+ * index.
+ * @param dictStartingOffset - starting dictionary child offset value of this
+ * node's parent.
+ * @return 0 if successful.
+ */
+static int bejUpdateLeafNodeMetaData(const struct BejDictionaries* dictionaries,
+ const uint8_t* parentDictionary,
+ void* childPtr, uint16_t childIndex,
+ uint16_t dictStartingOffset)
+{
+ // TODO: Implement this
+ (void)dictionaries;
+ (void)parentDictionary;
+ (void)childIndex;
+ (void)dictStartingOffset;
+
+ struct RedfishPropertyLeaf* chNode = childPtr;
+ switch (chNode->nodeAttr.format.principalDataType)
+ {
+ default:
+ fprintf(stderr, "Child type %u not supported\n",
+ chNode->nodeAttr.format.principalDataType);
+ return -1;
+ }
+ return 0;
+}
+
+/**
+ * @brief Update metadata of a parent node.
+ *
+ * @param dictionaries - dictionaries needed for encoding.
+ * @param parentDictionary - dictionary used by this node's parent.
+ * @param dictStartingOffset - starting dictionary child offset value of this
+ * node's parent.
+ * @param node - a pointer to the parent node.
+ * @param nodeIndex - If this node is an array element, this is the array index.
+ * @return 0 if successful.
+ */
+static int bejUpdateParentMetaData(const struct BejDictionaries* dictionaries,
+ const uint8_t* parentDictionary,
+ uint16_t dictStartingOffset,
+ struct RedfishPropertyParent* node,
+ uint16_t nodeIndex)
+{
+ // TODO: Implement this
+ (void)dictionaries;
+ (void)parentDictionary;
+ (void)dictStartingOffset;
+ (void)node;
+ (void)nodeIndex;
+
+ return -1;
+}
+
+/**
+ * @brief Update metadata of child nodes.
+ *
+ * If a child node contains its own child nodes, it will be added to the stack
+ * and function will return.
+ *
+ * @param dictionaries - dictionaries needed for encoding.
+ * @param parent - parent node.
+ * @param stack - stack holding parent nodes.
+ * @return 0 if successful.
+ */
+static int bejProcessChildNodes(const struct BejDictionaries* dictionaries,
+ struct RedfishPropertyParent* parent,
+ struct BejPointerStackCallback* stack)
+{
+ // Get the next child of the parent.
+ void* childPtr = parent->metaData.nextChild;
+
+ // Process all the children belongs to the parent.
+ while (childPtr != NULL)
+ {
+ // If we find a child with its own child nodes, add it to the stack and
+ // return.
+ if (bejTreeIsParentType(childPtr))
+ {
+ RETURN_IF_IERROR(bejUpdateParentMetaData(
+ dictionaries, parent->metaData.dictionary,
+ parent->metaData.childrenDictPropOffset, childPtr,
+ parent->metaData.nextChildIndex));
+
+ RETURN_IF_IERROR(stack->stackPush(childPtr, stack->stackContext));
+ bejParentGoToNextChild(parent, childPtr);
+ return 0;
+ }
+
+ RETURN_IF_IERROR(
+ bejUpdateLeafNodeMetaData(dictionaries, parent->metaData.dictionary,
+ childPtr, parent->metaData.nextChildIndex,
+ parent->metaData.childrenDictPropOffset));
+ // Use the child value size to update the parent value size.
+ struct RedfishPropertyLeaf* leafChild = childPtr;
+ // V: Include the child size in parent's value size.
+ parent->metaData.vSize +=
+ (leafChild->metaData.sflSize + leafChild->metaData.vSize);
+
+ // Get the next child belongs to the parent.
+ childPtr = bejParentGoToNextChild(parent, childPtr);
+ }
+ return 0;
+}
+
+int bejUpdateNodeMetadata(const struct BejDictionaries* dictionaries,
+ uint16_t majorSchemaStartingOffset,
+ struct RedfishPropertyParent* root,
+ struct BejPointerStackCallback* stack)
+{
+ // Decide the starting property offset of the dictionary.
+ uint16_t dictOffset = bejDictGetPropertyHeadOffset();
+ if (majorSchemaStartingOffset != BEJ_DICTIONARY_START_AT_HEAD)
+ {
+ dictOffset = majorSchemaStartingOffset;
+ }
+
+ // Initialize root node metadata.
+ RETURN_IF_IERROR(
+ bejUpdateParentMetaData(dictionaries, dictionaries->schemaDictionary,
+ dictOffset, root, /*childIndex=*/0));
+
+ // Push the root to the stack. Because we are not done with the parent node
+ // yet. Need to figure out all bytes need to encode children of this parent,
+ // and save it in the parent metadata.
+ RETURN_IF_IERROR(stack->stackPush(root, stack->stackContext));
+
+ while (!stack->stackEmpty(stack->stackContext))
+ {
+ // Get the parent at the top of the stack. Stack is only popped if the
+ // parent stack entry has no pending children; That is
+ // parent->metaData.nextChild == NULL.
+ struct RedfishPropertyParent* parent =
+ stack->stackPeek(stack->stackContext);
+
+ // Calculate metadata of all the child nodes of the current parent node.
+ // If one of these child nodes has its own child nodes, that child node
+ // will be added to the stack and this function will return.
+ RETURN_IF_IERROR(bejProcessChildNodes(dictionaries, parent, stack));
+
+ // If a new node hasn't been added to the stack, we know that this
+ // parent's child nodes have been processed. If not, do not pop the
+ // stack.
+ if (parent != stack->stackPeek(stack->stackContext))
+ {
+ continue;
+ }
+
+ // If we are here;
+ // Then "parent" is the top element of the stack.
+ // All the children of "parent" has been processed.
+
+ // Remove the "parent" from the stack.
+ parent = stack->stackPop(stack->stackContext);
+ // L: Add the length needed to store the number of bytes used for the
+ // parent's value.
+ parent->metaData.sflSize +=
+ bejNnintEncodingSizeOfUInt(parent->metaData.vSize);
+
+ // Since we now know the total size needs to encode the node pointed by
+ // "parent" variable, we should add that to the value size of this
+ // node's parent. Since we already popped this node from the stack, top
+ // of the stack element is this nodes's parent. "parentsParent" can be
+ // NULL if the node pointed by "parent" variable is the root.
+ struct RedfishPropertyParent* parentsParent =
+ stack->stackPeek(stack->stackContext);
+ if (parentsParent != NULL)
+ {
+ // V: Include the total size to encode the current parent in its
+ // parent's value size.
+ parentsParent->metaData.vSize +=
+ (parent->metaData.sflSize + parent->metaData.vSize);
+ }
+ }
+ return 0;
+}
diff --git a/src/bej_tree.c b/src/bej_tree.c
index 6bec216..53511eb 100644
--- a/src/bej_tree.c
+++ b/src/bej_tree.c
@@ -128,3 +128,16 @@
node->format.readOnlyProperty = readOnlyProperty;
node->format.nullableProperty = nullableProperty;
}
+
+void* bejParentGoToNextChild(struct RedfishPropertyParent* parent,
+ struct RedfishPropertyNode* currentChild)
+{
+ if (parent == NULL || currentChild == NULL)
+ {
+ return NULL;
+ }
+
+ parent->metaData.nextChildIndex += 1;
+ parent->metaData.nextChild = currentChild->sibling;
+ return currentChild->sibling;
+}
diff --git a/src/meson.build b/src/meson.build
index 051b397..4876d80 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -4,6 +4,8 @@
'bej_common.c',
'bej_dictionary.c',
'bej_tree.c',
+ 'bej_encoder_core.c',
+ 'bej_encoder_metadata.c',
'bej_decoder_json.cpp',
include_directories : libbej_incs,
implicit_include_directories: false,