581dc0c8947a761689705f07b91732b19d32c4f9
[keystone-rtos/fvid2.git] / src / fvid2_graph.c
1 /*
2  *  Copyright (c) Texas Instruments Incorporated 2018
3  *
4  *  Redistribution and use in source and binary forms, with or without
5  *  modification, are permitted provided that the following conditions
6  *  are met:
7  *
8  *    Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  *
11  *    Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the
14  *    distribution.
15  *
16  *    Neither the name of Texas Instruments Incorporated nor the names of
17  *    its contributors may be used to endorse or promote products derived
18  *    from this software without specific prior written permission.
19  *
20  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24  *  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25  *  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26  *  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27  *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28  *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
33 /**
34  *  \file fvid2_graph.c
35  *
36  *  \brief File containing the graph functions for resource management.
37  *
38  */
40 /* ========================================================================== */
41 /*                             Include Files                                  */
42 /* ========================================================================== */
44 #include <stdint.h>
45 #include <ti/drv/fvid2/fvid2.h>
47 /* ========================================================================== */
48 /*                           Macros & Typedefs                                */
49 /* ========================================================================== */
51 /* None */
53 /* ========================================================================== */
54 /*                         Structure Declarations                             */
55 /* ========================================================================== */
57 typedef struct Fvid2_GraphStack_t
58 {
59     Fvid2_GraphNodeInfo *node[FVID2_GRAPH_MAX_NODES];
60     /**< Array of node pointers */
61     int32_t stNum[FVID2_GRAPH_MAX_NODES];
62     /**< Keeps track of which child of this node is next to be visited, on
63      *   the stack for a node. */
64     uint8_t isVisited[FVID2_GRAPH_MAX_NODES];
65     /**< Flag keeps track of whether given node is visited or not */
66     int32_t top;
67     /**< Top marker of the stack */
68 } Fvid2_GraphStack;
70 /* ========================================================================== */
71 /*                         Internal Function Declarations                     */
72 /* ========================================================================== */
74 static int32_t Fvid2_graphConnect(const Fvid2_GraphNodeInfoList *inNodeList,
75                                   const Fvid2_GraphEdgeInfoList *inEdgeList);
76 static void Fvid2_graphStackReset(void);
77 static void Fvid2_graphStackPush(Fvid2_GraphNodeInfo *node);
78 static void Fvid2_graphStackPop(void);
79 static uint32_t Fvid2_graphStackIsVisited(const Fvid2_GraphNodeInfo *node);
80 int32_t Fvid2_graphStackIsLastNode(const Fvid2_GraphNodeInfo *currNode,
81                                    uint32_t isForward);
83 /* ========================================================================== */
84 /*                            Global Variables                                */
85 /* ========================================================================== */
87 static Fvid2_GraphStack gFvid2GraphNodeStack;
89 /* ========================================================================== */
90 /*                          Function Definitions                              */
91 /* ========================================================================== */
93 /* Helper function */
94 static int32_t Fvid2_graphConnect(const Fvid2_GraphNodeInfoList *inNodeList,
95                                   const Fvid2_GraphEdgeInfoList *inEdgeList)
96 {
97     Fvid2_GraphNodeInfo *nodes = inNodeList->list;
98     Fvid2_GraphEdgeInfo *edges = inEdgeList->list;
99     uint32_t cnt, startNode, endNode, index1, index2;
100     for (cnt = 0; cnt < inNodeList->numNodes; cnt++)
101     {
102         Fvid2Utils_memset(&nodes[cnt].input, 0, sizeof (Fvid2_GraphNodeSet));
103         Fvid2Utils_memset(&nodes[cnt].output, 0, sizeof (Fvid2_GraphNodeSet));
104     }
106     for (cnt = 0U; cnt < inEdgeList->numEdges; cnt++)
107     {
108         startNode = edges[cnt].startNode;
109         endNode   = edges[cnt].endNode;
110         /* End Node is output node for the start Node so update
111          * information in start node*/
112         index1 = nodes[startNode].output.numNodes;
113         nodes[startNode].output.node[index1] = &nodes[endNode];
114         nodes[startNode].output.numNodes++;
115         GT_assert(Fvid2Trace, (index1 < FVID2_GRAPH_MAX_NUM_PATHS));
117         /* Start Node is input node for the end Node so update
118          * information in end node*/
119         index2 = nodes[endNode].input.numNodes;
120         nodes[endNode].input.node[index2] = &nodes[startNode];
121         nodes[endNode].input.numNodes++;
122         GT_assert(Fvid2Trace, (index2 < FVID2_GRAPH_MAX_NUM_PATHS));
124         /* Dummy node's input is always enabled */
125         if ((TRUE == nodes[endNode].isDummy) &&
126             (TRUE == nodes[startNode].isDummy))
127         {
128             nodes[startNode].output.isEnabled[index1] = TRUE;
129             nodes[endNode].input.isEnabled[index2]    = TRUE;
130         }
131     }
133     return FVID2_SOK;
136 /** \brief Creates static DSS topology for the fixed edges/nodes. There
137  *  are some dummy nodes in the DSS topology. Input and output of these
138  *  nodes are always enabled and cannot be changed. This function creates
139  *  this static table.
140  *  Called at the init time only
141  */
142 Fvid2_GraphInfo *Fvid2_graphInit(const Fvid2_GraphNodeInfoList *inNodeList,
143                                  const Fvid2_GraphEdgeInfoList *inEdgeList,
144                                  Fvid2_GraphInfo *graphHandle)
146     GT_assert(Fvid2Trace, (graphHandle != NULL));
147     GT_assert(Fvid2Trace, (graphHandle->nodeList != NULL));
148     GT_assert(Fvid2Trace, (graphHandle->edgeList != NULL));
150     GT_assert(Fvid2Trace, (inNodeList != NULL));
151     GT_assert(Fvid2Trace, (inEdgeList != NULL));
153     graphHandle->nodeList->numNodes = inNodeList->numNodes;
154     graphHandle->edgeList->numEdges = inEdgeList->numEdges;
155     graphHandle->nodeList->list     = inNodeList->list;
156     graphHandle->edgeList->list     = inEdgeList->list;
158     Fvid2_graphConnect(inNodeList, inEdgeList);
159     return graphHandle;
162 int32_t Fvid2_graphDeInit(Fvid2_GraphInfo *graphHandle)
164     return FVID2_SOK;
167 /** \brief Function to get the pointer to node for the given index
168  */
169 Fvid2_GraphNodeInfo *Fvid2_graphGetNodeInfo(
170                             const Fvid2_GraphNodeInfoList *nodeList,
171                             uint32_t cnt)
173     Fvid2_GraphNodeInfo *node = NULL;
174     if (cnt < nodeList->numNodes)
175     {
176         node = &nodeList->list[cnt];
177     }
178     return (node);
181 /** \brief This function allocates nodes within the CORE by enabling
182  *  specified edges.
183  *
184  *  To enable an edge, it enables output of source node and
185  *  enables input of the target node.
186  *
187  *  Returns error if a node is already active.
188  *
189  *  TODO: First edge is assumed as input, Why/How to disable edges?,
190  *  Multiple handle support.
191  *  TODO: If FAIL, run through again and disable if anything was enabled.
192  */
194 uint32_t Fvid2_graphIsNodeInputAvailable(
195                             const Fvid2_GraphNodeInfoList *nodeList,
196                             uint32_t nodeNum)
198     uint32_t j;
199     uint32_t retVal  = TRUE;
200     Fvid2_GraphNodeInfo *curNode = Fvid2_graphGetNodeInfo(nodeList, nodeNum);
201     if (NULL == curNode)
202     {
203         retVal = FALSE;
204     }
205     else
206     {
207         for (j = 0; j < curNode->input.numNodes; j++)
208         {
209             if (FVID2_GRAPH_NM_ENABLE == curNode->input.isEnabled[j])
210             {
211                 retVal = FALSE;
212                 break;
213             }
214         }
215     }
216     return retVal;
219 uint32_t Fvid2_graphIsNodeOutputAvailable(
220                             const Fvid2_GraphNodeInfoList *nodeList,
221                             uint32_t nodeNum)
223     uint32_t j;
224     uint32_t retVal  = TRUE;
225     Fvid2_GraphNodeInfo *curNode = Fvid2_graphGetNodeInfo(nodeList, nodeNum);
226     if (NULL == curNode)
227     {
228         retVal = FALSE;
229     }
230     else
231     {
232         for (j = 0; j < curNode->output.numNodes; j++)
233         {
234             if (FVID2_GRAPH_NM_ENABLE == curNode->output.isEnabled[j])
235             {
236                 retVal = FALSE;
237                 break;
238             }
239         }
240     }
241     return retVal;
244 int32_t Fvid2_graphAllocNodes(const Fvid2_GraphNodeInfoList *nodeList,
245                               const Fvid2_GraphEdgeInfoList *edgeList,
246                               Fvid2_GraphNodeMode mode)
248     uint32_t i, j;
249     int32_t retVal = FVID2_SOK;
250     Fvid2_GraphEdgeInfo *inputEdgeList = edgeList->list;
251     for (i = 0; i < edgeList->numEdges; i++)
252     {
253         Fvid2_GraphNodeInfo *startNode = Fvid2_graphGetNodeInfo(
254             nodeList, inputEdgeList[i].startNode);
255         GT_assert(Fvid2Trace, (startNode != NULL));
256         Fvid2_GraphNodeInfo *endNode = Fvid2_graphGetNodeInfo(
257             nodeList, inputEdgeList[i].endNode);
258         GT_assert(Fvid2Trace, (endNode != NULL));
259         if ((startNode->nodeNum == FVID2_GRAPH_INVALID_NODE_ID) &&
260             (endNode->nodeNum == FVID2_GRAPH_INVALID_NODE_ID))
261         {
262             break;
263         }
265         /* TODO: Multiple connections from different path probably does not work
266         **/
267         /*      here. Will it be ever required? */
268         /* Example: One handle connects one source for blender, Second handle */
269         /*         connects second source for blender - Is such a case required?
270         **/
271         if (FVID2_GRAPH_NT_OUT_SINGLE == startNode->outType)
272         {
273             uint32_t inUse = FALSE;
274             for (j = 0; j < startNode->output.numNodes; j++)
275             {
276                 if (FVID2_GRAPH_NM_ENABLE == startNode->output.isEnabled[j])
277                 {
278                     inUse = TRUE;
279                     break;
280                 }
281             }
282             if ((FALSE == inUse) || (FVID2_GRAPH_NM_DISABLE == mode))
283             {
284                 for (j = 0; j < startNode->output.numNodes; j++)
285                 {
286                     if (startNode->output.node[j] == endNode)
287                     {
288                         startNode->output.isEnabled[j] = mode;
289                         break;
290                     }
291                 }
292                 if (j == startNode->output.numNodes)
293                 {
294                     retVal = FVID2_EFAIL;
295                 }
296             }
297         }
298         else if (FVID2_GRAPH_NT_OUT_MULTI == startNode->outType)
299         {
300             for (j = 0; j < startNode->output.numNodes; j++)
301             {
302                 if (startNode->output.node[j] == endNode)
303                 {
304                     startNode->output.isEnabled[j] = mode;
305                     break;
306                 }
307             }
308             if (j == startNode->output.numNodes)
309             {
310                 retVal = FVID2_EFAIL;
311             }
312         }
313         else
314         {
315             /*Do nothing */
316         }
318         if (FVID2_GRAPH_NT_IN_SINGLE == endNode->inType)
319         {
320             uint32_t inUse = FALSE;
321             for (j = 0; j < endNode->input.numNodes; j++)
322             {
323                 if (FVID2_GRAPH_NM_ENABLE == endNode->input.isEnabled[j])
324                 {
325                     inUse = TRUE;
326                     break;
327                 }
328             }
329             if ((FALSE == inUse) || (FVID2_GRAPH_NM_DISABLE == mode))
330             {
331                 for (j = 0; j < endNode->input.numNodes; j++)
332                 {
333                     if (endNode->input.node[j] == startNode)
334                     {
335                         endNode->input.isEnabled[j] = mode;
336                         break;
337                     }
338                 }
339                 if (j == endNode->input.numNodes)
340                 {
341                     retVal = FVID2_EFAIL;
342                 }
343             }
344         }
345         else if (FVID2_GRAPH_NT_IN_MULTI == endNode->inType)
346         {
347             for (j = 0; j < endNode->input.numNodes; j++)
348             {
349                 if (endNode->input.node[j] == startNode)
350                 {
351                     endNode->input.isEnabled[j] = mode;
352                     break;
353                 }
354             }
355             if (j == endNode->input.numNodes)
356             {
357                 retVal = FVID2_EFAIL;
358             }
359         }
360         else
361         {
362             /*Do nothing */
363         }
364     }
366     return retVal;
369 /**
370  * findPath()
371  */
372 /**
373  * Inputs
374  * PORTA/B_08/16/24
375  * isCSCEnabled
376  * isSCEnabled
377  */
378 /**
379  * Algo:
380  * Decide FirstNode
381  * Decide LastNodes
382  * curNode = FirstNode
383  * if(isCSCEnabled) {join curNode to CSC; curNode = CSC}
384  * if(isSCEnabled)  {join curNode to SC; curNode = SC}
385  * foreach(LastNode_option1, LastNode_option2)
386  * {
387  * join curNode to LastNode
388  * if (successful) break
389  * else next
390  * }
391  */
393 /** \brief This function gets a list of valid nodes in an edge list and
394  *  also enable the input in each entry. Fill in VpsCore_VipPathObj
395  *
396  *  Should be called only after Fvid2_graphAllocNodes() is successful
397  *
398  *  TODO: Connections should be made in this function and not copied from
399  *  main graph (as is done currently) since this will fail for multiple handle
400  *  scenarios.
401  */
402 int32_t Fvid2_graphGetPath(const Fvid2_GraphNodeInfoList *inNodeList,
403                            const Fvid2_GraphEdgeInfoList *inEdgeList,
404                            Fvid2_GraphNodeInfoList *outNodeList,
405                            Fvid2_GraphEdgeInfoList *outEdgeList,
406                            uint32_t maxOutNodeCnt,
407                            uint32_t maxOutEdgeCnt)
409     uint32_t i, j;
410     uint32_t pathEdgeCount = inEdgeList->numEdges;
411     uint32_t pathNodeCount = 0;
412     uint32_t numInNodes = inNodeList->numNodes;
413     uint32_t nodes[FVID2_GRAPH_MAX_NODES] = {0};
415     for (i = 0; i < inEdgeList->numEdges; i++)
416     {
417         j = inEdgeList->list[i].startNode;
418         nodes[j] = 1U;
419         j = inEdgeList->list[i].endNode;
420         nodes[j] = 1U;
421     }
423     for (i = 0; i < numInNodes; i++)
424     {
425         if (nodes[i] == 1U)
426         {
427             pathNodeCount++;
428         }
429     }
431     GT_assert(Fvid2Trace, (pathNodeCount < maxOutNodeCnt));
432     outNodeList->numNodes = pathNodeCount;
434     GT_assert(Fvid2Trace, (outNodeList->list != NULL));
436     GT_assert(Fvid2Trace, (pathEdgeCount < maxOutEdgeCnt));
437     outEdgeList->numEdges = pathEdgeCount;
438     GT_assert(Fvid2Trace, (outEdgeList->list != NULL));
440     for (i = 0; i < pathEdgeCount; i++)
441     {
442         outEdgeList->list[i].startNode =
443             inEdgeList->list[i].startNode;
444         outEdgeList->list[i].endNode =
445             inEdgeList->list[i].endNode;
446     }
448     j = 0;
449     for (i = 0; i < numInNodes; i++)
450     {
451         if (nodes[i] == 1U)
452         {
453             Fvid2Utils_memcpy((void *) &outNodeList->list[j],
454                             (void *) &inNodeList->list[i],
455                             sizeof (Fvid2_GraphNodeInfo));
457             /* Reset connection info from the original graph */
458             Fvid2Utils_memset((void *) (outNodeList->list[j].input.node), 0,
459                               sizeof (Fvid2_GraphNodeInfo *) * FVID2_GRAPH_MAX_NUM_PATHS);
460             Fvid2Utils_memset((void *) (outNodeList->list[j].output.node), 0,
461                               sizeof (Fvid2_GraphNodeInfo *) * FVID2_GRAPH_MAX_NUM_PATHS);
462             j++;
463         }
464     }
466     return FVID2_SOK;
469 int32_t Fvid2_graphFreePath(Fvid2_GraphNodeInfoList *nodeList,
470                       Fvid2_GraphEdgeInfoList *edgeList)
472     if (NULL != nodeList->list)
473     {
474         nodeList->numNodes = 0;
475         nodeList->list     = NULL;
476     }
477     if (NULL != edgeList->list)
478     {
479         edgeList->numEdges = 0;
480         edgeList->list     = NULL;
481     }
482     return FVID2_SOK;
485 void Fvid2_graphInitTraverser(Fvid2_GraphNodeInfo *node)
487     /* Initialize Stack */
488     Fvid2_graphStackReset();
490     /* Push root node onto stack */
491     Fvid2_graphStackPush(node);
494 static void Fvid2_graphStackReset(void)
496     Fvid2Utils_memset(&gFvid2GraphNodeStack, 0, sizeof (gFvid2GraphNodeStack));
497     gFvid2GraphNodeStack.top = (-(int32_t)1);
499     /* Initialize All stack numbers with -1 */
500     Fvid2Utils_memset(gFvid2GraphNodeStack.stNum, 0, sizeof (uint32_t) * FVID2_GRAPH_MAX_NODES);
501     Fvid2Utils_memset(gFvid2GraphNodeStack.isVisited, 0, sizeof (FVID2_GRAPH_MAX_NODES));
504 /* Push a node on the stack */
505 static void Fvid2_graphStackPush(Fvid2_GraphNodeInfo *node)
507     gFvid2GraphNodeStack.top++;
508     gFvid2GraphNodeStack.node[gFvid2GraphNodeStack.top] = node;
511 /* Remove top node from the stack */
512 static void Fvid2_graphStackPop(void)
514     /* Remove the node from the stack */
515     gFvid2GraphNodeStack.stNum[gFvid2GraphNodeStack.top] = 0;
516     gFvid2GraphNodeStack.node[gFvid2GraphNodeStack.top]  = NULL;
517     gFvid2GraphNodeStack.top--;
520 static uint32_t Fvid2_graphStackIsVisited(const Fvid2_GraphNodeInfo *node)
522     uint32_t visited = TRUE;
524     if (0 == gFvid2GraphNodeStack.isVisited[node->nodeNum])
525     {
526         visited = FALSE;
527     }
529     return (visited);
532 int32_t Fvid2_graphStackIsLastNode(const Fvid2_GraphNodeInfo *currNode,
533                                    uint32_t isForward)
535     int32_t ret = (int32_t) TRUE;
537     if (((TRUE == isForward) && (0 != currNode->output.numNodes)) ||
538         ((FALSE == isForward) && (0 != currNode->input.numNodes)))
539     {
540         ret = (int32_t) FALSE;
541     }
543     return (ret);
546 /* Function to get the next enabled node for the currNode */
547 Fvid2_GraphNodeInfo *Fvid2_graphGetNextChildNode(
548                             const Fvid2_GraphNodeInfo *currNode,
549                             uint32_t isForward)
551     Fvid2_GraphNodeInfo *node = NULL;
552     uint32_t isEnabled = TRUE;
553     uint32_t nodeNum, nextNodeNum;
554     uint32_t loopEnd = 1U;
556     nodeNum = gFvid2GraphNodeStack.top;
557     nextNodeNum = (uint32_t) gFvid2GraphNodeStack.stNum[nodeNum];
558     do
559     {
560         /* Traversing from input Node to Venc Nodes */
561         if (TRUE == isForward)
562         {
563             /* Get the next node from the output nodes */
564             if (nextNodeNum < currNode->output.numNodes)
565             {
566                 node = currNode->output.node[nextNodeNum];
567                 isEnabled = currNode->output.isEnabled[nextNodeNum];
568             }
569             else
570             {
571                 loopEnd = 0;
572             }
573         }
574         else  /* Traversing from Venc Nodes to input node */
575         {
576             /* Get the next node from the input nodes */
577             if (nextNodeNum < currNode->input.numNodes)
578             {
579                 node = currNode->input.node[(nextNodeNum)];
580                 isEnabled = currNode->input.isEnabled[nextNodeNum];
581             }
582             else
583             {
584                 loopEnd = 0;
585             }
586         }
587         if (0U == loopEnd)
588         {
589             break;
590         }
591         nextNodeNum += 1U;
592     } while (FALSE == isEnabled);
594     if (FALSE == isEnabled)
595     {
596         node = NULL;
597     }
598     else
599     {
600         gFvid2GraphNodeStack.stNum[nodeNum] = (int32_t) nextNodeNum;
601     }
602     return (node);
605 /* Get the top node on the stack */
606 Fvid2_GraphNodeInfo *Fvid2_graphStackPeak(uint32_t *stNum)
608     *stNum = (uint32_t) gFvid2GraphNodeStack.stNum[gFvid2GraphNodeStack.top];
609     return (gFvid2GraphNodeStack.node[gFvid2GraphNodeStack.top]);
612 Fvid2_GraphNodeInfo *Fvid2_graphGetNextNodeToTraverse(uint32_t isForward)
614     uint32_t nodeNum;
615     Fvid2_GraphNodeInfo *currNode = NULL, *nextNode = NULL;
617     while (gFvid2GraphNodeStack.top > (-(int32_t)1))
618     {
619         /* Get the stack top node */
620         currNode = Fvid2_graphStackPeak(&nodeNum);
622         if (FALSE == Fvid2_graphStackIsVisited(currNode))
623         {
624             /* If current node is ot visited, return it to the caller. */
625             break;
626         }
627         else
628         {
629             /* Get the Next Node */
630             nextNode = Fvid2_graphGetNextChildNode(currNode, isForward);
632             /* If next node is not null, push it onto stack so that it can
633              * be traversed */
634             if (NULL != nextNode)
635             {
636                 /* Push the start node onto stack */
637                 Fvid2_graphStackPush(nextNode);
638             }
639             else
640             {
641                 /* Remove the node from the stack */
642                 Fvid2_graphStackPop();
643             }
644         }
645     }
646     if ((-(int32_t)1) == gFvid2GraphNodeStack.top)
647     {
648         currNode = NULL;
649     }
651     if (NULL != currNode)
652     {
653         nodeNum = currNode->nodeNum;
654         gFvid2GraphNodeStack.isVisited[nodeNum] = (uint8_t) 1;
655     }
657     return (currNode);
660 int32_t Fvid2_graphGetEnabledIndex(const uint32_t *array, uint32_t size)
662     uint32_t i;
663     int32_t  retVal = FVID2_EFAIL;
665     for (i = 0; i < size; i++)
666     {
667         if ((uint32_t) 0 != array[i])
668         {
669             retVal = (int32_t) i;
670             break;
671         }
672     }
673     return retVal;
676 void Fvid2_graphAddEdge(Fvid2_GraphEdgeInfo *edge,
677                         uint32_t startNode,
678                         uint32_t endNode)
680     if (startNode != endNode)
681     {
682         edge->startNode = startNode;
683         edge->endNode = endNode;
684     }