1/*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/*------------------------------------------------------------------------------
18
19    Table of contents
20
21     1. Include headers
22     2. External compiler flags
23     3. Module defines
24     4. Local function prototypes
25     5. Functions
26          ComparePictures
27          h264bsdReorderRefPicList
28          Mmcop1
29          Mmcop2
30          Mmcop3
31          Mmcop4
32          Mmcop5
33          Mmcop6
34          h264bsdMarkDecRefPic
35          h264bsdGetRefPicData
36          h264bsdAllocateDpbImage
37          SlidingWindowRefPicMarking
38          h264bsdInitDpb
39          h264bsdResetDpb
40          h264bsdInitRefPicList
41          FindDpbPic
42          SetPicNums
43          h264bsdCheckGapsInFrameNum
44          FindSmallestPicOrderCnt
45          OutputPicture
46          h264bsdDpbOutputPicture
47          h264bsdFlushDpb
48          h264bsdFreeDpb
49
50------------------------------------------------------------------------------*/
51
52/*------------------------------------------------------------------------------
53    1. Include headers
54------------------------------------------------------------------------------*/
55
56#include "h264bsd_cfg.h"
57#include "h264bsd_dpb.h"
58#include "h264bsd_slice_header.h"
59#include "h264bsd_image.h"
60#include "h264bsd_util.h"
61#include "basetype.h"
62
63#include <log/log.h>
64
65/*------------------------------------------------------------------------------
66    2. External compiler flags
67--------------------------------------------------------------------------------
68
69--------------------------------------------------------------------------------
70    3. Module defines
71------------------------------------------------------------------------------*/
72
73/* macros to determine picture status. Note that IS_SHORT_TERM macro returns
74 * true also for non-existing pictures because non-existing pictures are
75 * regarded short term pictures according to H.264 standard */
76#define IS_REFERENCE(a) ((a).status)
77#define IS_EXISTING(a) ((a).status > NON_EXISTING)
78#define IS_SHORT_TERM(a) \
79    ((a).status == NON_EXISTING || (a).status == SHORT_TERM)
80#define IS_LONG_TERM(a) ((a).status == LONG_TERM)
81
82/* macro to set a picture unused for reference */
83#define SET_UNUSED(a) (a).status = UNUSED;
84
85#define MAX_NUM_REF_IDX_L0_ACTIVE 16
86
87/*------------------------------------------------------------------------------
88    4. Local function prototypes
89------------------------------------------------------------------------------*/
90
91static i32 ComparePictures(const void *ptr1, const void *ptr2);
92
93static u32 Mmcop1(dpbStorage_t *dpb, u32 currPicNum, u32 differenceOfPicNums);
94
95static u32 Mmcop2(dpbStorage_t *dpb, u32 longTermPicNum);
96
97static u32 Mmcop3(dpbStorage_t *dpb, u32 currPicNum, u32 differenceOfPicNums,
98    u32 longTermFrameIdx);
99
100static u32 Mmcop4(dpbStorage_t *dpb, u32 maxLongTermFrameIdx);
101
102static u32 Mmcop5(dpbStorage_t *dpb);
103
104static u32 Mmcop6(dpbStorage_t *dpb, u32 frameNum, i32 picOrderCnt,
105    u32 longTermFrameIdx);
106
107static u32 SlidingWindowRefPicMarking(dpbStorage_t *dpb);
108
109static i32 FindDpbPic(dpbStorage_t *dpb, i32 picNum, u32 isShortTerm);
110
111static void SetPicNums(dpbStorage_t *dpb, u32 currFrameNum);
112
113static dpbPicture_t* FindSmallestPicOrderCnt(dpbStorage_t *dpb);
114
115static u32 OutputPicture(dpbStorage_t *dpb);
116
117static void ShellSort(dpbPicture_t *pPic, u32 num);
118
119/*------------------------------------------------------------------------------
120
121    Function: ComparePictures
122
123        Functional description:
124            Function to compare dpb pictures, used by the ShellSort() function.
125            Order of the pictures after sorting shall be as follows:
126                1) short term reference pictures starting with the largest
127                   picNum
128                2) long term reference pictures starting with the smallest
129                   longTermPicNum
130                3) pictures unused for reference but needed for display
131                4) other pictures
132
133        Returns:
134            -1      pic 1 is greater than pic 2
135             0      equal from comparison point of view
136             1      pic 2 is greater then pic 1
137
138------------------------------------------------------------------------------*/
139
140static i32 ComparePictures(const void *ptr1, const void *ptr2)
141{
142
143/* Variables */
144
145    dpbPicture_t *pic1, *pic2;
146
147/* Code */
148
149    ASSERT(ptr1);
150    ASSERT(ptr2);
151
152    pic1 = (dpbPicture_t*)ptr1;
153    pic2 = (dpbPicture_t*)ptr2;
154
155    /* both are non-reference pictures, check if needed for display */
156    if (!IS_REFERENCE(*pic1) && !IS_REFERENCE(*pic2))
157    {
158        if (pic1->toBeDisplayed && !pic2->toBeDisplayed)
159            return(-1);
160        else if (!pic1->toBeDisplayed && pic2->toBeDisplayed)
161            return(1);
162        else
163            return(0);
164    }
165    /* only pic 1 needed for reference -> greater */
166    else if (!IS_REFERENCE(*pic2))
167        return(-1);
168    /* only pic 2 needed for reference -> greater */
169    else if (!IS_REFERENCE(*pic1))
170        return(1);
171    /* both are short term reference pictures -> check picNum */
172    else if (IS_SHORT_TERM(*pic1) && IS_SHORT_TERM(*pic2))
173    {
174        if (pic1->picNum > pic2->picNum)
175            return(-1);
176        else if (pic1->picNum < pic2->picNum)
177            return(1);
178        else
179            return(0);
180    }
181    /* only pic 1 is short term -> greater */
182    else if (IS_SHORT_TERM(*pic1))
183        return(-1);
184    /* only pic 2 is short term -> greater */
185    else if (IS_SHORT_TERM(*pic2))
186        return(1);
187    /* both are long term reference pictures -> check picNum (contains the
188     * longTermPicNum */
189    else
190    {
191        if (pic1->picNum > pic2->picNum)
192            return(1);
193        else if (pic1->picNum < pic2->picNum)
194            return(-1);
195        else
196            return(0);
197    }
198}
199
200/*------------------------------------------------------------------------------
201
202    Function: h264bsdReorderRefPicList
203
204        Functional description:
205            Function to perform reference picture list reordering based on
206            reordering commands received in the slice header. See details
207            of the process in the H.264 standard.
208
209        Inputs:
210            dpb             pointer to dpb storage structure
211            order           pointer to reordering commands
212            currFrameNum    current frame number
213            numRefIdxActive number of active reference indices for current
214                            picture
215
216        Outputs:
217            dpb             'list' field of the structure reordered
218
219        Returns:
220            HANTRO_OK      success
221            HANTRO_NOK     if non-existing pictures referred to in the
222                           reordering commands
223
224------------------------------------------------------------------------------*/
225
226u32 h264bsdReorderRefPicList(
227  dpbStorage_t *dpb,
228  refPicListReordering_t *order,
229  u32 currFrameNum,
230  u32 numRefIdxActive)
231{
232
233/* Variables */
234
235    u32 i, j, k, picNumPred, refIdx;
236    i32 picNum, picNumNoWrap, index;
237    u32 isShortTerm;
238
239/* Code */
240
241    ASSERT(order);
242    ASSERT(currFrameNum <= dpb->maxFrameNum);
243    ASSERT(numRefIdxActive <= MAX_NUM_REF_IDX_L0_ACTIVE);
244
245    /* set dpb picture numbers for sorting */
246    SetPicNums(dpb, currFrameNum);
247
248    if (!order->refPicListReorderingFlagL0)
249        return(HANTRO_OK);
250
251    refIdx     = 0;
252    picNumPred = currFrameNum;
253
254    i = 0;
255    while (order->command[i].reorderingOfPicNumsIdc < 3)
256    {
257        /* short term */
258        if (order->command[i].reorderingOfPicNumsIdc < 2)
259        {
260            if (order->command[i].reorderingOfPicNumsIdc == 0)
261            {
262                picNumNoWrap =
263                    (i32)picNumPred - (i32)order->command[i].absDiffPicNum;
264                if (picNumNoWrap < 0)
265                    picNumNoWrap += (i32)dpb->maxFrameNum;
266            }
267            else
268            {
269                picNumNoWrap =
270                    (i32)(picNumPred + order->command[i].absDiffPicNum);
271                if (picNumNoWrap >= (i32)dpb->maxFrameNum)
272                    picNumNoWrap -= (i32)dpb->maxFrameNum;
273            }
274            picNumPred = (u32)picNumNoWrap;
275            picNum = picNumNoWrap;
276            if ((u32)picNumNoWrap > currFrameNum)
277                picNum -= (i32)dpb->maxFrameNum;
278            isShortTerm = HANTRO_TRUE;
279        }
280        /* long term */
281        else
282        {
283            picNum = (i32)order->command[i].longTermPicNum;
284            isShortTerm = HANTRO_FALSE;
285
286        }
287        /* find corresponding picture from dpb */
288        index = FindDpbPic(dpb, picNum, isShortTerm);
289        if (index < 0 || !IS_EXISTING(dpb->buffer[index]))
290            return(HANTRO_NOK);
291
292        /* shift pictures */
293        for (j = numRefIdxActive; j > refIdx; j--)
294            dpb->list[j] = dpb->list[j-1];
295        /* put picture into the list */
296        dpb->list[refIdx++] = &dpb->buffer[index];
297        /* remove later references to the same picture */
298        for (j = k = refIdx; j <= numRefIdxActive; j++)
299            if(dpb->list[j] != &dpb->buffer[index])
300                dpb->list[k++] = dpb->list[j];
301
302        i++;
303    }
304
305    return(HANTRO_OK);
306
307}
308
309/*------------------------------------------------------------------------------
310
311    Function: Mmcop1
312
313        Functional description:
314            Function to mark a short-term reference picture unused for
315            reference, memory_management_control_operation equal to 1
316
317        Returns:
318            HANTRO_OK      success
319            HANTRO_NOK     failure, picture does not exist in the buffer
320
321------------------------------------------------------------------------------*/
322
323static u32 Mmcop1(dpbStorage_t *dpb, u32 currPicNum, u32 differenceOfPicNums)
324{
325
326/* Variables */
327
328    i32 index, picNum;
329
330/* Code */
331
332    ASSERT(currPicNum < dpb->maxFrameNum);
333
334    picNum = (i32)currPicNum - (i32)differenceOfPicNums;
335
336    index = FindDpbPic(dpb, picNum, HANTRO_TRUE);
337    if (index < 0)
338        return(HANTRO_NOK);
339
340    SET_UNUSED(dpb->buffer[index]);
341    dpb->numRefFrames--;
342    if (!dpb->buffer[index].toBeDisplayed)
343        dpb->fullness--;
344
345    return(HANTRO_OK);
346
347}
348
349/*------------------------------------------------------------------------------
350
351    Function: Mmcop2
352
353        Functional description:
354            Function to mark a long-term reference picture unused for
355            reference, memory_management_control_operation equal to 2
356
357        Returns:
358            HANTRO_OK      success
359            HANTRO_NOK     failure, picture does not exist in the buffer
360
361------------------------------------------------------------------------------*/
362
363static u32 Mmcop2(dpbStorage_t *dpb, u32 longTermPicNum)
364{
365
366/* Variables */
367
368    i32 index;
369
370/* Code */
371
372    index = FindDpbPic(dpb, (i32)longTermPicNum, HANTRO_FALSE);
373    if (index < 0)
374        return(HANTRO_NOK);
375
376    SET_UNUSED(dpb->buffer[index]);
377    dpb->numRefFrames--;
378    if (!dpb->buffer[index].toBeDisplayed)
379        dpb->fullness--;
380
381    return(HANTRO_OK);
382
383}
384
385/*------------------------------------------------------------------------------
386
387    Function: Mmcop3
388
389        Functional description:
390            Function to assing a longTermFrameIdx to a short-term reference
391            frame (i.e. to change it to a long-term reference picture),
392            memory_management_control_operation equal to 3
393
394        Returns:
395            HANTRO_OK      success
396            HANTRO_NOK     failure, short-term picture does not exist in the
397                           buffer or is a non-existing picture, or invalid
398                           longTermFrameIdx given
399
400------------------------------------------------------------------------------*/
401
402static u32 Mmcop3(dpbStorage_t *dpb, u32 currPicNum, u32 differenceOfPicNums,
403    u32 longTermFrameIdx)
404{
405
406/* Variables */
407
408    i32 index, picNum;
409    u32 i;
410
411/* Code */
412
413    ASSERT(dpb);
414    ASSERT(currPicNum < dpb->maxFrameNum);
415
416    if ( (dpb->maxLongTermFrameIdx == NO_LONG_TERM_FRAME_INDICES) ||
417         (longTermFrameIdx > dpb->maxLongTermFrameIdx) )
418        return(HANTRO_NOK);
419
420    /* check if a long term picture with the same longTermFrameIdx already
421     * exist and remove it if necessary */
422    for (i = 0; i < dpb->maxRefFrames; i++)
423        if (IS_LONG_TERM(dpb->buffer[i]) &&
424          (u32)dpb->buffer[i].picNum == longTermFrameIdx)
425        {
426            SET_UNUSED(dpb->buffer[i]);
427            dpb->numRefFrames--;
428            if (!dpb->buffer[i].toBeDisplayed)
429                dpb->fullness--;
430            break;
431        }
432
433    picNum = (i32)currPicNum - (i32)differenceOfPicNums;
434
435    index = FindDpbPic(dpb, picNum, HANTRO_TRUE);
436    if (index < 0)
437        return(HANTRO_NOK);
438    if (!IS_EXISTING(dpb->buffer[index]))
439        return(HANTRO_NOK);
440
441    dpb->buffer[index].status = LONG_TERM;
442    dpb->buffer[index].picNum = (i32)longTermFrameIdx;
443
444    return(HANTRO_OK);
445
446}
447
448/*------------------------------------------------------------------------------
449
450    Function: Mmcop4
451
452        Functional description:
453            Function to set maxLongTermFrameIdx,
454            memory_management_control_operation equal to 4
455
456        Returns:
457            HANTRO_OK      success
458
459------------------------------------------------------------------------------*/
460
461static u32 Mmcop4(dpbStorage_t *dpb, u32 maxLongTermFrameIdx)
462{
463
464/* Variables */
465
466    u32 i;
467
468/* Code */
469
470    dpb->maxLongTermFrameIdx = maxLongTermFrameIdx;
471
472    for (i = 0; i < dpb->maxRefFrames; i++)
473        if (IS_LONG_TERM(dpb->buffer[i]) &&
474          ( ((u32)dpb->buffer[i].picNum > maxLongTermFrameIdx) ||
475            (dpb->maxLongTermFrameIdx == NO_LONG_TERM_FRAME_INDICES) ) )
476        {
477            SET_UNUSED(dpb->buffer[i]);
478            dpb->numRefFrames--;
479            if (!dpb->buffer[i].toBeDisplayed)
480                dpb->fullness--;
481        }
482
483    return(HANTRO_OK);
484
485}
486
487/*------------------------------------------------------------------------------
488
489    Function: Mmcop5
490
491        Functional description:
492            Function to mark all reference pictures unused for reference and
493            set maxLongTermFrameIdx to NO_LONG_TERM_FRAME_INDICES,
494            memory_management_control_operation equal to 5. Function flushes
495            the buffer and places all pictures that are needed for display into
496            the output buffer.
497
498        Returns:
499            HANTRO_OK      success
500
501------------------------------------------------------------------------------*/
502
503static u32 Mmcop5(dpbStorage_t *dpb)
504{
505
506/* Variables */
507
508    u32 i;
509
510/* Code */
511
512    for (i = 0; i < 16; i++)
513    {
514        if (IS_REFERENCE(dpb->buffer[i]))
515        {
516            SET_UNUSED(dpb->buffer[i]);
517            if (!dpb->buffer[i].toBeDisplayed)
518                dpb->fullness--;
519        }
520    }
521
522    /* output all pictures */
523    while (OutputPicture(dpb) == HANTRO_OK)
524        ;
525    dpb->numRefFrames = 0;
526    dpb->maxLongTermFrameIdx = NO_LONG_TERM_FRAME_INDICES;
527    dpb->prevRefFrameNum = 0;
528
529    return(HANTRO_OK);
530
531}
532
533/*------------------------------------------------------------------------------
534
535    Function: Mmcop6
536
537        Functional description:
538            Function to assign longTermFrameIdx to the current picture,
539            memory_management_control_operation equal to 6
540
541        Returns:
542            HANTRO_OK      success
543            HANTRO_NOK     invalid longTermFrameIdx or no room for current
544                           picture in the buffer
545
546------------------------------------------------------------------------------*/
547
548static u32 Mmcop6(dpbStorage_t *dpb, u32 frameNum, i32 picOrderCnt,
549    u32 longTermFrameIdx)
550{
551
552/* Variables */
553
554    u32 i;
555
556/* Code */
557
558    ASSERT(frameNum < dpb->maxFrameNum);
559
560    if ( (dpb->maxLongTermFrameIdx == NO_LONG_TERM_FRAME_INDICES) ||
561         (longTermFrameIdx > dpb->maxLongTermFrameIdx) )
562        return(HANTRO_NOK);
563
564    /* check if a long term picture with the same longTermFrameIdx already
565     * exist and remove it if necessary */
566    for (i = 0; i < dpb->maxRefFrames; i++)
567        if (IS_LONG_TERM(dpb->buffer[i]) &&
568          (u32)dpb->buffer[i].picNum == longTermFrameIdx)
569        {
570            SET_UNUSED(dpb->buffer[i]);
571            dpb->numRefFrames--;
572            if (!dpb->buffer[i].toBeDisplayed)
573                dpb->fullness--;
574            break;
575        }
576
577    if (dpb->numRefFrames < dpb->maxRefFrames)
578    {
579        dpb->currentOut->frameNum = frameNum;
580        dpb->currentOut->picNum   = (i32)longTermFrameIdx;
581        dpb->currentOut->picOrderCnt = picOrderCnt;
582        dpb->currentOut->status   = LONG_TERM;
583        if (dpb->noReordering)
584            dpb->currentOut->toBeDisplayed = HANTRO_FALSE;
585        else
586            dpb->currentOut->toBeDisplayed = HANTRO_TRUE;
587        dpb->numRefFrames++;
588        dpb->fullness++;
589        return(HANTRO_OK);
590    }
591    /* if there is no room, return an error */
592    else
593        return(HANTRO_NOK);
594
595}
596
597/*------------------------------------------------------------------------------
598
599    Function: h264bsdMarkDecRefPic
600
601        Functional description:
602            Function to perform reference picture marking process. This
603            function should be called both for reference and non-reference
604            pictures.  Non-reference pictures shall have mark pointer set to
605            NULL.
606
607        Inputs:
608            dpb         pointer to the DPB data structure
609            mark        pointer to reference picture marking commands
610            image       pointer to current picture to be placed in the buffer
611            frameNum    frame number of the current picture
612            picOrderCnt picture order count for the current picture
613            isIdr       flag to indicate if the current picture is an
614                        IDR picture
615            currentPicId    identifier for the current picture, from the
616                            application, stored along with the picture
617            numErrMbs       number of concealed macroblocks in the current
618                            picture, stored along with the picture
619
620        Outputs:
621            dpb         'buffer' modified, possible output frames placed into
622                        'outBuf'
623
624        Returns:
625            HANTRO_OK   success
626            HANTRO_NOK  failure
627
628------------------------------------------------------------------------------*/
629
630u32 h264bsdMarkDecRefPic(
631  dpbStorage_t *dpb,
632  decRefPicMarking_t *mark,
633  image_t *image,
634  u32 frameNum,
635  i32 picOrderCnt,
636  u32 isIdr,
637  u32 currentPicId,
638  u32 numErrMbs)
639{
640
641/* Variables */
642
643    u32 i, status;
644    u32 markedAsLongTerm;
645    u32 toBeDisplayed;
646
647/* Code */
648
649    ASSERT(dpb);
650    ASSERT(mark || !isIdr);
651    ASSERT(!isIdr || (frameNum == 0 && picOrderCnt == 0));
652    ASSERT(frameNum < dpb->maxFrameNum);
653
654    if (image->data != dpb->currentOut->data)
655    {
656        EPRINT("TRYING TO MARK NON-ALLOCATED IMAGE");
657        return(HANTRO_NOK);
658    }
659
660    dpb->lastContainsMmco5 = HANTRO_FALSE;
661    status = HANTRO_OK;
662
663    toBeDisplayed = dpb->noReordering ? HANTRO_FALSE : HANTRO_TRUE;
664
665    /* non-reference picture, stored for display reordering purposes */
666    if (mark == NULL)
667    {
668        dpb->currentOut->status = UNUSED;
669        dpb->currentOut->frameNum = frameNum;
670        dpb->currentOut->picNum = (i32)frameNum;
671        dpb->currentOut->picOrderCnt = picOrderCnt;
672        dpb->currentOut->toBeDisplayed = toBeDisplayed;
673        if (!dpb->noReordering)
674            dpb->fullness++;
675    }
676    /* IDR picture */
677    else if (isIdr)
678    {
679
680        /* h264bsdCheckGapsInFrameNum not called for IDR pictures -> have to
681         * reset numOut and outIndex here */
682        dpb->numOut = dpb->outIndex = 0;
683
684        /* flush the buffer */
685        Mmcop5(dpb);
686        /* if noOutputOfPriorPicsFlag was set -> the pictures preceding the
687         * IDR picture shall not be output -> set output buffer empty */
688        if (mark->noOutputOfPriorPicsFlag || dpb->noReordering)
689        {
690            dpb->numOut = 0;
691            dpb->outIndex = 0;
692        }
693
694        if (mark->longTermReferenceFlag)
695        {
696            dpb->currentOut->status = LONG_TERM;
697            dpb->maxLongTermFrameIdx = 0;
698        }
699        else
700        {
701            dpb->currentOut->status = SHORT_TERM;
702            dpb->maxLongTermFrameIdx = NO_LONG_TERM_FRAME_INDICES;
703        }
704        dpb->currentOut->frameNum  = 0;
705        dpb->currentOut->picNum    = 0;
706        dpb->currentOut->picOrderCnt = 0;
707        dpb->currentOut->toBeDisplayed = toBeDisplayed;
708        dpb->fullness = 1;
709        dpb->numRefFrames = 1;
710    }
711    /* reference picture */
712    else
713    {
714        markedAsLongTerm = HANTRO_FALSE;
715        if (mark->adaptiveRefPicMarkingModeFlag)
716        {
717            i = 0;
718            while (mark->operation[i].memoryManagementControlOperation)
719            {
720                switch (mark->operation[i].memoryManagementControlOperation)
721                {
722                    case 1:
723                        status = Mmcop1(
724                          dpb,
725                          frameNum,
726                          mark->operation[i].differenceOfPicNums);
727                        break;
728
729                    case 2:
730                        status = Mmcop2(dpb, mark->operation[i].longTermPicNum);
731                        break;
732
733                    case 3:
734                        status =  Mmcop3(
735                          dpb,
736                          frameNum,
737                          mark->operation[i].differenceOfPicNums,
738                          mark->operation[i].longTermFrameIdx);
739                        break;
740
741                    case 4:
742                        status = Mmcop4(
743                          dpb,
744                          mark->operation[i].maxLongTermFrameIdx);
745                        break;
746
747                    case 5:
748                        status = Mmcop5(dpb);
749                        dpb->lastContainsMmco5 = HANTRO_TRUE;
750                        frameNum = 0;
751                        break;
752
753                    case 6:
754                        status = Mmcop6(
755                          dpb,
756                          frameNum,
757                          picOrderCnt,
758                          mark->operation[i].longTermFrameIdx);
759                        if (status == HANTRO_OK)
760                            markedAsLongTerm = HANTRO_TRUE;
761                        break;
762
763                    default: /* invalid memory management control operation */
764                        status = HANTRO_NOK;
765                        break;
766                }
767                if (status != HANTRO_OK)
768                {
769                    break;
770                }
771                i++;
772            }
773        }
774        else
775        {
776            status = SlidingWindowRefPicMarking(dpb);
777        }
778        /* if current picture was not marked as long-term reference by
779         * memory management control operation 6 -> mark current as short
780         * term and insert it into dpb (if there is room) */
781        if (!markedAsLongTerm)
782        {
783            if (dpb->numRefFrames < dpb->maxRefFrames)
784            {
785                dpb->currentOut->frameNum = frameNum;
786                dpb->currentOut->picNum   = (i32)frameNum;
787                dpb->currentOut->picOrderCnt = picOrderCnt;
788                dpb->currentOut->status   = SHORT_TERM;
789                dpb->currentOut->toBeDisplayed = toBeDisplayed;
790                dpb->fullness++;
791                dpb->numRefFrames++;
792            }
793            /* no room */
794            else
795            {
796                status = HANTRO_NOK;
797            }
798        }
799    }
800
801    dpb->currentOut->isIdr = isIdr;
802    dpb->currentOut->picId = currentPicId;
803    dpb->currentOut->numErrMbs = numErrMbs;
804
805    /* dpb was initialized to not to reorder the pictures -> output current
806     * picture immediately */
807    if (dpb->noReordering)
808    {
809        ASSERT(dpb->numOut == 0);
810        ASSERT(dpb->outIndex == 0);
811        dpb->outBuf[dpb->numOut].data  = dpb->currentOut->data;
812        dpb->outBuf[dpb->numOut].isIdr = dpb->currentOut->isIdr;
813        dpb->outBuf[dpb->numOut].picId = dpb->currentOut->picId;
814        dpb->outBuf[dpb->numOut].numErrMbs = dpb->currentOut->numErrMbs;
815        dpb->numOut++;
816    }
817    else
818    {
819        /* output pictures if buffer full */
820        while (dpb->fullness > dpb->dpbSize)
821        {
822            i = OutputPicture(dpb);
823            ASSERT(i == HANTRO_OK);
824        }
825    }
826
827    /* sort dpb */
828    ShellSort(dpb->buffer, dpb->dpbSize+1);
829
830    return(status);
831
832}
833
834/*------------------------------------------------------------------------------
835
836    Function: h264bsdGetRefPicData
837
838        Functional description:
839            Function to get reference picture data from the reference picture
840            list
841
842        Returns:
843            pointer to desired reference picture data
844            NULL if invalid index or non-existing picture referred
845
846------------------------------------------------------------------------------*/
847
848u8* h264bsdGetRefPicData(dpbStorage_t *dpb, u32 index)
849{
850
851/* Variables */
852
853/* Code */
854
855    if(index > 16 || dpb->list[index] == NULL)
856        return(NULL);
857    else if(!IS_EXISTING(*dpb->list[index]))
858        return(NULL);
859    else
860        return(dpb->list[index]->data);
861
862}
863
864/*------------------------------------------------------------------------------
865
866    Function: h264bsdAllocateDpbImage
867
868        Functional description:
869            function to allocate memory for a image. This function does not
870            really allocate any memory but reserves one of the buffer
871            positions for decoding of current picture
872
873        Returns:
874            pointer to memory area for the image
875
876
877------------------------------------------------------------------------------*/
878
879u8* h264bsdAllocateDpbImage(dpbStorage_t *dpb)
880{
881
882/* Variables */
883
884/* Code */
885
886    ASSERT( !dpb->buffer[dpb->dpbSize].toBeDisplayed &&
887            !IS_REFERENCE(dpb->buffer[dpb->dpbSize]) );
888    ASSERT(dpb->fullness <=  dpb->dpbSize);
889
890    dpb->currentOut = dpb->buffer + dpb->dpbSize;
891
892    return(dpb->currentOut->data);
893
894}
895
896/*------------------------------------------------------------------------------
897
898    Function: SlidingWindowRefPicMarking
899
900        Functional description:
901            Function to perform sliding window refence picture marking process.
902
903        Outputs:
904            HANTRO_OK      success
905            HANTRO_NOK     failure, no short-term reference frame found that
906                           could be marked unused
907
908
909------------------------------------------------------------------------------*/
910
911static u32 SlidingWindowRefPicMarking(dpbStorage_t *dpb)
912{
913
914/* Variables */
915
916    i32 index, picNum;
917    u32 i;
918
919/* Code */
920
921    if (dpb->numRefFrames < dpb->maxRefFrames)
922    {
923        return(HANTRO_OK);
924    }
925    else
926    {
927        index = -1;
928        picNum = 0;
929        /* find the oldest short term picture */
930        for (i = 0; i < dpb->numRefFrames; i++)
931            if (IS_SHORT_TERM(dpb->buffer[i]))
932                if (dpb->buffer[i].picNum < picNum || index == -1)
933                {
934                    index = (i32)i;
935                    picNum = dpb->buffer[i].picNum;
936                }
937        if (index >= 0)
938        {
939            SET_UNUSED(dpb->buffer[index]);
940            dpb->numRefFrames--;
941            if (!dpb->buffer[index].toBeDisplayed)
942                dpb->fullness--;
943
944            return(HANTRO_OK);
945        }
946    }
947
948    return(HANTRO_NOK);
949
950}
951
952/*------------------------------------------------------------------------------
953
954    Function: h264bsdInitDpb
955
956        Functional description:
957            Function to initialize DPB. Reserves memories for the buffer,
958            reference picture list and output buffer. dpbSize indicates
959            the maximum DPB size indicated by the levelIdc in the stream.
960            If noReordering flag is FALSE the DPB stores dpbSize pictures
961            for display reordering purposes. On the other hand, if the
962            flag is TRUE the DPB only stores maxRefFrames reference pictures
963            and outputs all the pictures immediately.
964
965        Inputs:
966            picSizeInMbs    picture size in macroblocks
967            dpbSize         size of the DPB (number of pictures)
968            maxRefFrames    max number of reference frames
969            maxFrameNum     max frame number
970            noReordering    flag to indicate that DPB does not have to
971                            prepare to reorder frames for display
972
973        Outputs:
974            dpb             pointer to dpb data storage
975
976        Returns:
977            HANTRO_OK       success
978            MEMORY_ALLOCATION_ERROR if memory allocation failed
979
980------------------------------------------------------------------------------*/
981
982u32 h264bsdInitDpb(
983  dpbStorage_t *dpb,
984  u32 picSizeInMbs,
985  u32 dpbSize,
986  u32 maxRefFrames,
987  u32 maxFrameNum,
988  u32 noReordering)
989{
990
991/* Variables */
992
993    u32 i;
994
995/* Code */
996
997    ASSERT(picSizeInMbs);
998    ASSERT(maxRefFrames <= MAX_NUM_REF_PICS);
999    ASSERT(maxRefFrames <= dpbSize);
1000    ASSERT(maxFrameNum);
1001    ASSERT(dpbSize);
1002
1003    // see comment in loop below about size calculation
1004    if (picSizeInMbs > (UINT32_MAX - 32 - 15) / 384) {
1005        ALOGE("b/28533562");
1006        android_errorWriteLog(0x534e4554, "28533562");
1007        return(MEMORY_ALLOCATION_ERROR);
1008    }
1009
1010    dpb->maxLongTermFrameIdx = NO_LONG_TERM_FRAME_INDICES;
1011    dpb->maxRefFrames        = MAX(maxRefFrames, 1);
1012    if (noReordering)
1013        dpb->dpbSize         = dpb->maxRefFrames;
1014    else
1015        dpb->dpbSize         = dpbSize;
1016    dpb->maxFrameNum         = maxFrameNum;
1017    dpb->noReordering        = noReordering;
1018    dpb->fullness            = 0;
1019    dpb->numRefFrames        = 0;
1020    dpb->prevRefFrameNum     = 0;
1021
1022    ALLOCATE(dpb->buffer, MAX_NUM_REF_IDX_L0_ACTIVE + 1, dpbPicture_t);
1023    if (dpb->buffer == NULL)
1024        return(MEMORY_ALLOCATION_ERROR);
1025    H264SwDecMemset(dpb->buffer, 0,
1026            (MAX_NUM_REF_IDX_L0_ACTIVE + 1)*sizeof(dpbPicture_t));
1027    for (i = 0; i < dpb->dpbSize + 1; i++)
1028    {
1029        /* Allocate needed amount of memory, which is:
1030         * image size + 32 + 15, where 32 cames from the fact that in ARM OpenMax
1031         * DL implementation Functions may read beyond the end of an array,
1032         * by a maximum of 32 bytes. And +15 cames for the need to align memory
1033         * to 16-byte boundary */
1034        ALLOCATE(dpb->buffer[i].pAllocatedData, (picSizeInMbs*384 + 32+15), u8);
1035        if (dpb->buffer[i].pAllocatedData == NULL)
1036            return(MEMORY_ALLOCATION_ERROR);
1037
1038        dpb->buffer[i].data = ALIGN(dpb->buffer[i].pAllocatedData, 16);
1039    }
1040
1041    ALLOCATE(dpb->list, MAX_NUM_REF_IDX_L0_ACTIVE + 1, dpbPicture_t*);
1042    ALLOCATE(dpb->outBuf, dpb->dpbSize+1, dpbOutPicture_t);
1043
1044    if (dpb->list == NULL || dpb->outBuf == NULL)
1045        return(MEMORY_ALLOCATION_ERROR);
1046
1047    H264SwDecMemset(dpb->list, 0,
1048            ((MAX_NUM_REF_IDX_L0_ACTIVE + 1) * sizeof(dpbPicture_t*)) );
1049
1050    dpb->numOut = dpb->outIndex = 0;
1051
1052    return(HANTRO_OK);
1053
1054}
1055
1056/*------------------------------------------------------------------------------
1057
1058    Function: h264bsdResetDpb
1059
1060        Functional description:
1061            Function to reset DPB. This function should be called when an IDR
1062            slice (other than the first) activates new sequence parameter set.
1063            Function calls h264bsdFreeDpb to free old allocated memories and
1064            h264bsdInitDpb to re-initialize the DPB. Same inputs, outputs and
1065            returns as for h264bsdInitDpb.
1066
1067------------------------------------------------------------------------------*/
1068
1069u32 h264bsdResetDpb(
1070  dpbStorage_t *dpb,
1071  u32 picSizeInMbs,
1072  u32 dpbSize,
1073  u32 maxRefFrames,
1074  u32 maxFrameNum,
1075  u32 noReordering)
1076{
1077
1078/* Code */
1079
1080    ASSERT(picSizeInMbs);
1081    ASSERT(maxRefFrames <= MAX_NUM_REF_PICS);
1082    ASSERT(maxRefFrames <= dpbSize);
1083    ASSERT(maxFrameNum);
1084    ASSERT(dpbSize);
1085
1086    h264bsdFreeDpb(dpb);
1087
1088    return h264bsdInitDpb(dpb, picSizeInMbs, dpbSize, maxRefFrames,
1089                          maxFrameNum, noReordering);
1090}
1091
1092/*------------------------------------------------------------------------------
1093
1094    Function: h264bsdInitRefPicList
1095
1096        Functional description:
1097            Function to initialize reference picture list. Function just
1098            sets pointers in the list according to pictures in the buffer.
1099            The buffer is assumed to contain pictures sorted according to
1100            what the H.264 standard says about initial reference picture list.
1101
1102        Inputs:
1103            dpb     pointer to dpb data structure
1104
1105        Outputs:
1106            dpb     'list' field initialized
1107
1108        Returns:
1109            none
1110
1111------------------------------------------------------------------------------*/
1112
1113void h264bsdInitRefPicList(dpbStorage_t *dpb)
1114{
1115
1116/* Variables */
1117
1118    u32 i;
1119
1120/* Code */
1121
1122    for (i = 0; i < dpb->numRefFrames; i++)
1123        dpb->list[i] = &dpb->buffer[i];
1124
1125}
1126
1127/*------------------------------------------------------------------------------
1128
1129    Function: FindDpbPic
1130
1131        Functional description:
1132            Function to find a reference picture from the buffer. The picture
1133            to be found is identified by picNum and isShortTerm flag.
1134
1135        Returns:
1136            index of the picture in the buffer
1137            -1 if the specified picture was not found in the buffer
1138
1139------------------------------------------------------------------------------*/
1140
1141static i32 FindDpbPic(dpbStorage_t *dpb, i32 picNum, u32 isShortTerm)
1142{
1143
1144/* Variables */
1145
1146    u32 i = 0;
1147    u32 found = HANTRO_FALSE;
1148
1149/* Code */
1150
1151    if (isShortTerm)
1152    {
1153        while (i < dpb->maxRefFrames && !found)
1154        {
1155            if (IS_SHORT_TERM(dpb->buffer[i]) &&
1156              dpb->buffer[i].picNum == picNum)
1157                found = HANTRO_TRUE;
1158            else
1159                i++;
1160        }
1161    }
1162    else
1163    {
1164        ASSERT(picNum >= 0);
1165        while (i < dpb->maxRefFrames && !found)
1166        {
1167            if (IS_LONG_TERM(dpb->buffer[i]) &&
1168              dpb->buffer[i].picNum == picNum)
1169                found = HANTRO_TRUE;
1170            else
1171                i++;
1172        }
1173    }
1174
1175    if (found)
1176        return((i32)i);
1177    else
1178        return(-1);
1179
1180}
1181
1182/*------------------------------------------------------------------------------
1183
1184    Function: SetPicNums
1185
1186        Functional description:
1187            Function to set picNum values for short-term pictures in the
1188            buffer. Numbering of pictures is based on frame numbers and as
1189            frame numbers are modulo maxFrameNum -> frame numbers of older
1190            pictures in the buffer may be bigger than the currFrameNum.
1191            picNums will be set so that current frame has the largest picNum
1192            and all the short-term frames in the buffer will get smaller picNum
1193            representing their "distance" from the current frame. This
1194            function kind of maps the modulo arithmetic back to normal.
1195
1196------------------------------------------------------------------------------*/
1197
1198static void SetPicNums(dpbStorage_t *dpb, u32 currFrameNum)
1199{
1200
1201/* Variables */
1202
1203    u32 i;
1204    i32 frameNumWrap;
1205
1206/* Code */
1207
1208    ASSERT(dpb);
1209    ASSERT(currFrameNum < dpb->maxFrameNum);
1210
1211    for (i = 0; i < dpb->numRefFrames; i++)
1212        if (IS_SHORT_TERM(dpb->buffer[i]))
1213        {
1214            if (dpb->buffer[i].frameNum > currFrameNum)
1215                frameNumWrap =
1216                    (i32)dpb->buffer[i].frameNum - (i32)dpb->maxFrameNum;
1217            else
1218                frameNumWrap = (i32)dpb->buffer[i].frameNum;
1219            dpb->buffer[i].picNum = frameNumWrap;
1220        }
1221
1222}
1223
1224/*------------------------------------------------------------------------------
1225
1226    Function: h264bsdCheckGapsInFrameNum
1227
1228        Functional description:
1229            Function to check gaps in frame_num and generate non-existing
1230            (short term) reference pictures if necessary. This function should
1231            be called only for non-IDR pictures.
1232
1233        Inputs:
1234            dpb         pointer to dpb data structure
1235            frameNum    frame number of the current picture
1236            isRefPic    flag to indicate if current picture is a reference or
1237                        non-reference picture
1238            gapsAllowed Flag which indicates active SPS stance on whether
1239                        to allow gaps
1240
1241        Outputs:
1242            dpb         'buffer' possibly modified by inserting non-existing
1243                        pictures with sliding window marking process
1244
1245        Returns:
1246            HANTRO_OK   success
1247            HANTRO_NOK  error in sliding window reference picture marking or
1248                        frameNum equal to previous reference frame used for
1249                        a reference picture
1250
1251------------------------------------------------------------------------------*/
1252
1253u32 h264bsdCheckGapsInFrameNum(dpbStorage_t *dpb, u32 frameNum, u32 isRefPic,
1254                               u32 gapsAllowed)
1255{
1256
1257/* Variables */
1258
1259    u32 unUsedShortTermFrameNum;
1260    u8 *tmp;
1261
1262/* Code */
1263
1264    ASSERT(dpb);
1265    ASSERT(dpb->fullness <= dpb->dpbSize);
1266    ASSERT(frameNum < dpb->maxFrameNum);
1267
1268    dpb->numOut = 0;
1269    dpb->outIndex = 0;
1270
1271    if(!gapsAllowed)
1272        return(HANTRO_OK);
1273
1274    if ( (frameNum != dpb->prevRefFrameNum) &&
1275         (frameNum != ((dpb->prevRefFrameNum + 1) % dpb->maxFrameNum)))
1276    {
1277
1278        unUsedShortTermFrameNum = (dpb->prevRefFrameNum + 1) % dpb->maxFrameNum;
1279
1280        /* store data pointer of last buffer position to be used as next
1281         * "allocated" data pointer if last buffer position after this process
1282         * contains data pointer located in outBuf (buffer placed in the output
1283         * shall not be overwritten by the current picture) */
1284        tmp = dpb->buffer[dpb->dpbSize].data;
1285        do
1286        {
1287            SetPicNums(dpb, unUsedShortTermFrameNum);
1288
1289            if (SlidingWindowRefPicMarking(dpb) != HANTRO_OK)
1290            {
1291                return(HANTRO_NOK);
1292            }
1293
1294            /* output pictures if buffer full */
1295            while (dpb->fullness >= dpb->dpbSize)
1296            {
1297#ifdef _ASSERT_USED
1298                ASSERT(!dpb->noReordering);
1299                ASSERT(OutputPicture(dpb) == HANTRO_OK);
1300#else
1301                OutputPicture(dpb);
1302#endif
1303            }
1304
1305            /* add to end of list */
1306            ASSERT( !dpb->buffer[dpb->dpbSize].toBeDisplayed &&
1307                    !IS_REFERENCE(dpb->buffer[dpb->dpbSize]) );
1308            dpb->buffer[dpb->dpbSize].status = NON_EXISTING;
1309            dpb->buffer[dpb->dpbSize].frameNum = unUsedShortTermFrameNum;
1310            dpb->buffer[dpb->dpbSize].picNum   = (i32)unUsedShortTermFrameNum;
1311            dpb->buffer[dpb->dpbSize].picOrderCnt = 0;
1312            dpb->buffer[dpb->dpbSize].toBeDisplayed = HANTRO_FALSE;
1313            dpb->fullness++;
1314            dpb->numRefFrames++;
1315
1316            /* sort the buffer */
1317            ShellSort(dpb->buffer, dpb->dpbSize+1);
1318
1319            unUsedShortTermFrameNum = (unUsedShortTermFrameNum + 1) %
1320                dpb->maxFrameNum;
1321
1322        } while (unUsedShortTermFrameNum != frameNum);
1323
1324        /* pictures placed in output buffer -> check that 'data' in
1325         * buffer position dpbSize is not in the output buffer (this will be
1326         * "allocated" by h264bsdAllocateDpbImage). If it is -> exchange data
1327         * pointer with the one stored in the beginning */
1328        if (dpb->numOut)
1329        {
1330            u32 i;
1331
1332            for (i = 0; i < dpb->numOut; i++)
1333            {
1334                if (dpb->outBuf[i].data == dpb->buffer[dpb->dpbSize].data)
1335                {
1336                    /* find buffer position containing data pointer stored in
1337                     * tmp */
1338                    for (i = 0; i < dpb->dpbSize; i++)
1339                    {
1340                        if (dpb->buffer[i].data == tmp)
1341                        {
1342                            dpb->buffer[i].data =
1343                                dpb->buffer[dpb->dpbSize].data;
1344                            dpb->buffer[dpb->dpbSize].data = tmp;
1345                            break;
1346                        }
1347                    }
1348                    ASSERT(i < dpb->dpbSize);
1349                    break;
1350                }
1351            }
1352        }
1353    }
1354    /* frameNum for reference pictures shall not be the same as for previous
1355     * reference picture, otherwise accesses to pictures in the buffer cannot
1356     * be solved unambiguously */
1357    else if (isRefPic && frameNum == dpb->prevRefFrameNum)
1358    {
1359        return(HANTRO_NOK);
1360    }
1361
1362    /* save current frame_num in prevRefFrameNum. For non-reference frame
1363     * prevFrameNum is set to frame number of last non-existing frame above */
1364    if (isRefPic)
1365        dpb->prevRefFrameNum = frameNum;
1366    else if (frameNum != dpb->prevRefFrameNum)
1367    {
1368        dpb->prevRefFrameNum =
1369            (frameNum + dpb->maxFrameNum - 1) % dpb->maxFrameNum;
1370    }
1371
1372    return(HANTRO_OK);
1373
1374}
1375
1376/*------------------------------------------------------------------------------
1377
1378    Function: FindSmallestPicOrderCnt
1379
1380        Functional description:
1381            Function to find picture with smallest picture order count. This
1382            will be the next picture in display order.
1383
1384        Returns:
1385            pointer to the picture, NULL if no pictures to be displayed
1386
1387------------------------------------------------------------------------------*/
1388
1389dpbPicture_t* FindSmallestPicOrderCnt(dpbStorage_t *dpb)
1390{
1391
1392/* Variables */
1393
1394    u32 i;
1395    i32 picOrderCnt;
1396    dpbPicture_t *tmp;
1397
1398/* Code */
1399
1400    ASSERT(dpb);
1401
1402    picOrderCnt = 0x7FFFFFFF;
1403    tmp = NULL;
1404
1405    for (i = 0; i <= dpb->dpbSize; i++)
1406    {
1407        if (dpb->buffer[i].toBeDisplayed &&
1408            (dpb->buffer[i].picOrderCnt < picOrderCnt))
1409        {
1410            tmp = dpb->buffer + i;
1411            picOrderCnt = dpb->buffer[i].picOrderCnt;
1412        }
1413    }
1414
1415    return(tmp);
1416
1417}
1418
1419/*------------------------------------------------------------------------------
1420
1421    Function: OutputPicture
1422
1423        Functional description:
1424            Function to put next display order picture into the output buffer.
1425
1426        Returns:
1427            HANTRO_OK      success
1428            HANTRO_NOK     no pictures to display
1429
1430------------------------------------------------------------------------------*/
1431
1432u32 OutputPicture(dpbStorage_t *dpb)
1433{
1434
1435/* Variables */
1436
1437    dpbPicture_t *tmp;
1438
1439/* Code */
1440
1441    ASSERT(dpb);
1442
1443    if (dpb->noReordering)
1444        return(HANTRO_NOK);
1445
1446    tmp = FindSmallestPicOrderCnt(dpb);
1447
1448    /* no pictures to be displayed */
1449    if (tmp == NULL)
1450        return(HANTRO_NOK);
1451
1452    dpb->outBuf[dpb->numOut].data  = tmp->data;
1453    dpb->outBuf[dpb->numOut].isIdr = tmp->isIdr;
1454    dpb->outBuf[dpb->numOut].picId = tmp->picId;
1455    dpb->outBuf[dpb->numOut].numErrMbs = tmp->numErrMbs;
1456    dpb->numOut++;
1457
1458    tmp->toBeDisplayed = HANTRO_FALSE;
1459    if (!IS_REFERENCE(*tmp))
1460    {
1461        dpb->fullness--;
1462    }
1463
1464    return(HANTRO_OK);
1465
1466}
1467
1468/*------------------------------------------------------------------------------
1469
1470    Function: h264bsdDpbOutputPicture
1471
1472        Functional description:
1473            Function to get next display order picture from the output buffer.
1474
1475        Return:
1476            pointer to output picture structure, NULL if no pictures to
1477            display
1478
1479------------------------------------------------------------------------------*/
1480
1481dpbOutPicture_t* h264bsdDpbOutputPicture(dpbStorage_t *dpb)
1482{
1483
1484/* Variables */
1485
1486/* Code */
1487
1488    ASSERT(dpb);
1489
1490    if (dpb->outIndex < dpb->numOut)
1491        return(dpb->outBuf + dpb->outIndex++);
1492    else
1493        return(NULL);
1494
1495}
1496
1497/*------------------------------------------------------------------------------
1498
1499    Function: h264bsdFlushDpb
1500
1501        Functional description:
1502            Function to flush the DPB. Function puts all pictures needed for
1503            display into the output buffer. This function shall be called in
1504            the end of the stream to obtain pictures buffered for display
1505            re-ordering purposes.
1506
1507------------------------------------------------------------------------------*/
1508
1509void h264bsdFlushDpb(dpbStorage_t *dpb)
1510{
1511
1512    /* don't do anything if buffer not reserved */
1513    if (dpb->buffer)
1514    {
1515        dpb->flushed = 1;
1516        /* output all pictures */
1517        while (OutputPicture(dpb) == HANTRO_OK)
1518            ;
1519    }
1520
1521}
1522
1523/*------------------------------------------------------------------------------
1524
1525    Function: h264bsdFreeDpb
1526
1527        Functional description:
1528            Function to free memories reserved for the DPB.
1529
1530------------------------------------------------------------------------------*/
1531
1532void h264bsdFreeDpb(dpbStorage_t *dpb)
1533{
1534
1535/* Variables */
1536
1537    u32 i;
1538
1539/* Code */
1540
1541    ASSERT(dpb);
1542
1543    if (dpb->buffer)
1544    {
1545        for (i = 0; i < dpb->dpbSize+1; i++)
1546        {
1547            FREE(dpb->buffer[i].pAllocatedData);
1548        }
1549    }
1550    FREE(dpb->buffer);
1551    FREE(dpb->list);
1552    FREE(dpb->outBuf);
1553
1554}
1555
1556/*------------------------------------------------------------------------------
1557
1558    Function: ShellSort
1559
1560        Functional description:
1561            Sort pictures in the buffer. Function implements Shell's method,
1562            i.e. diminishing increment sort. See e.g. "Numerical Recipes in C"
1563            for more information.
1564
1565------------------------------------------------------------------------------*/
1566
1567static void ShellSort(dpbPicture_t *pPic, u32 num)
1568{
1569
1570    u32 i, j;
1571    u32 step;
1572    dpbPicture_t tmpPic;
1573
1574    step = 7;
1575
1576    while (step)
1577    {
1578        for (i = step; i < num; i++)
1579        {
1580            tmpPic = pPic[i];
1581            j = i;
1582            while (j >= step && ComparePictures(pPic + j - step, &tmpPic) > 0)
1583            {
1584                pPic[j] = pPic[j-step];
1585                j -= step;
1586            }
1587            pPic[j] = tmpPic;
1588        }
1589        step >>= 1;
1590    }
1591
1592}
1593
1594