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