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