1 /** @file 2 Compression routine. The compression algorithm is a mixture of LZ77 and Huffman 3 coding. LZ77 transforms the source data into a sequence of Original Characters 4 and Pointers to repeated strings. This sequence is further divided into Blocks 5 and Huffman codings are applied to each Block. 6 7 Copyright (c) 2006 - 2014, Intel Corporation. All rights reserved.<BR> 8 This program and the accompanying materials 9 are licensed and made available under the terms and conditions of the BSD License 10 which accompanies this distribution. The full text of the license may be found at 11 http://opensource.org/licenses/bsd-license.php 12 13 THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, 14 WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. 15 16 **/ 17 18 #include "Compress.h" 19 20 // 21 // Macro Definitions 22 // 23 #undef UINT8_MAX 24 typedef INT32 NODE; 25 #define UINT8_MAX 0xff 26 #define UINT8_BIT 8 27 #define THRESHOLD 3 28 #define INIT_CRC 0 29 #define WNDBIT 19 30 #define WNDSIZ (1U << WNDBIT) 31 #define MAXMATCH 256 32 #define BLKSIZ (1U << 14) // 16 * 1024U 33 #define PERC_FLAG 0x80000000U 34 #define CODE_BIT 16 35 #define NIL 0 36 #define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX) 37 #define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2) 38 #define CRCPOLY 0xA001 39 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT) 40 41 // 42 // C: the Char&Len Set; P: the Position Set; T: the exTra Set 43 // 44 #define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD) 45 #define CBIT 9 46 #define NP (WNDBIT + 1) 47 #define PBIT 5 48 #define NT (CODE_BIT + 3) 49 #define TBIT 5 50 #if NT > NP 51 #define NPT NT 52 #else 53 #define NPT NP 54 #endif 55 // 56 // Function Prototypes 57 // 58 59 STATIC 60 VOID 61 PutDword( 62 IN UINT32 Data 63 ); 64 65 STATIC 66 EFI_STATUS 67 AllocateMemory ( 68 VOID 69 ); 70 71 STATIC 72 VOID 73 FreeMemory ( 74 VOID 75 ); 76 77 STATIC 78 VOID 79 InitSlide ( 80 VOID 81 ); 82 83 STATIC 84 NODE 85 Child ( 86 IN NODE NodeQ, 87 IN UINT8 CharC 88 ); 89 90 STATIC 91 VOID 92 MakeChild ( 93 IN NODE NodeQ, 94 IN UINT8 CharC, 95 IN NODE NodeR 96 ); 97 98 STATIC 99 VOID 100 Split ( 101 IN NODE Old 102 ); 103 104 STATIC 105 VOID 106 InsertNode ( 107 VOID 108 ); 109 110 STATIC 111 VOID 112 DeleteNode ( 113 VOID 114 ); 115 116 STATIC 117 VOID 118 GetNextMatch ( 119 VOID 120 ); 121 122 STATIC 123 EFI_STATUS 124 Encode ( 125 VOID 126 ); 127 128 STATIC 129 VOID 130 CountTFreq ( 131 VOID 132 ); 133 134 STATIC 135 VOID 136 WritePTLen ( 137 IN INT32 Number, 138 IN INT32 nbit, 139 IN INT32 Special 140 ); 141 142 STATIC 143 VOID 144 WriteCLen ( 145 VOID 146 ); 147 148 STATIC 149 VOID 150 EncodeC ( 151 IN INT32 Value 152 ); 153 154 STATIC 155 VOID 156 EncodeP ( 157 IN UINT32 Value 158 ); 159 160 STATIC 161 VOID 162 SendBlock ( 163 VOID 164 ); 165 166 STATIC 167 VOID 168 Output ( 169 IN UINT32 c, 170 IN UINT32 p 171 ); 172 173 STATIC 174 VOID 175 HufEncodeStart ( 176 VOID 177 ); 178 179 STATIC 180 VOID 181 HufEncodeEnd ( 182 VOID 183 ); 184 185 STATIC 186 VOID 187 MakeCrcTable ( 188 VOID 189 ); 190 191 STATIC 192 VOID 193 PutBits ( 194 IN INT32 Number, 195 IN UINT32 Value 196 ); 197 198 STATIC 199 INT32 200 FreadCrc ( 201 OUT UINT8 *Pointer, 202 IN INT32 Number 203 ); 204 205 STATIC 206 VOID 207 InitPutBits ( 208 VOID 209 ); 210 211 STATIC 212 VOID 213 CountLen ( 214 IN INT32 Index 215 ); 216 217 STATIC 218 VOID 219 MakeLen ( 220 IN INT32 Root 221 ); 222 223 STATIC 224 VOID 225 DownHeap ( 226 IN INT32 Index 227 ); 228 229 STATIC 230 VOID 231 MakeCode ( 232 IN INT32 Number, 233 IN UINT8 Len[ ], 234 OUT UINT16 Code[] 235 ); 236 237 STATIC 238 INT32 239 MakeTree ( 240 IN INT32 NParm, 241 IN UINT16 FreqParm[], 242 OUT UINT8 LenParm[ ], 243 OUT UINT16 CodeParm[] 244 ); 245 246 // 247 // Global Variables 248 // 249 STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit; 250 251 STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen; 252 STATIC INT16 mHeap[NC + 1]; 253 STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN; 254 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc; 255 STATIC UINT32 mCompSize, mOrigSize; 256 257 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1], 258 mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1]; 259 260 STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL; 261 262 // 263 // functions 264 // 265 EFI_STATUS 266 TianoCompress ( 267 IN UINT8 *SrcBuffer, 268 IN UINT32 SrcSize, 269 IN UINT8 *DstBuffer, 270 IN OUT UINT32 *DstSize 271 ) 272 /*++ 273 274 Routine Description: 275 276 The internal implementation of [Efi/Tiano]Compress(). 277 278 Arguments: 279 280 SrcBuffer - The buffer storing the source data 281 SrcSize - The size of source data 282 DstBuffer - The buffer to store the compressed data 283 DstSize - On input, the size of DstBuffer; On output, 284 the size of the actual compressed data. 285 Version - The version of de/compression algorithm. 286 Version 1 for UEFI 2.0 de/compression algorithm. 287 Version 2 for Tiano de/compression algorithm. 288 289 Returns: 290 291 EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case, 292 DstSize contains the size needed. 293 EFI_SUCCESS - Compression is successful. 294 EFI_OUT_OF_RESOURCES - No resource to complete function. 295 EFI_INVALID_PARAMETER - Parameter supplied is wrong. 296 297 --*/ 298 { 299 EFI_STATUS Status; 300 301 // 302 // Initializations 303 // 304 mBufSiz = 0; 305 mBuf = NULL; 306 mText = NULL; 307 mLevel = NULL; 308 mChildCount = NULL; 309 mPosition = NULL; 310 mParent = NULL; 311 mPrev = NULL; 312 mNext = NULL; 313 314 mSrc = SrcBuffer; 315 mSrcUpperLimit = mSrc + SrcSize; 316 mDst = DstBuffer; 317 mDstUpperLimit = mDst +*DstSize; 318 319 PutDword (0L); 320 PutDword (0L); 321 322 MakeCrcTable (); 323 324 mOrigSize = mCompSize = 0; 325 mCrc = INIT_CRC; 326 327 // 328 // Compress it 329 // 330 Status = Encode (); 331 if (EFI_ERROR (Status)) { 332 return EFI_OUT_OF_RESOURCES; 333 } 334 // 335 // Null terminate the compressed data 336 // 337 if (mDst < mDstUpperLimit) { 338 *mDst++ = 0; 339 } 340 // 341 // Fill in compressed size and original size 342 // 343 mDst = DstBuffer; 344 PutDword (mCompSize + 1); 345 PutDword (mOrigSize); 346 347 // 348 // Return 349 // 350 if (mCompSize + 1 + 8 > *DstSize) { 351 *DstSize = mCompSize + 1 + 8; 352 return EFI_BUFFER_TOO_SMALL; 353 } else { 354 *DstSize = mCompSize + 1 + 8; 355 return EFI_SUCCESS; 356 } 357 358 } 359 360 STATIC 361 VOID 362 PutDword ( 363 IN UINT32 Data 364 ) 365 /*++ 366 367 Routine Description: 368 369 Put a dword to output stream 370 371 Arguments: 372 373 Data - the dword to put 374 375 Returns: (VOID) 376 377 --*/ 378 { 379 if (mDst < mDstUpperLimit) { 380 *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff); 381 } 382 383 if (mDst < mDstUpperLimit) { 384 *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff); 385 } 386 387 if (mDst < mDstUpperLimit) { 388 *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff); 389 } 390 391 if (mDst < mDstUpperLimit) { 392 *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff); 393 } 394 } 395 396 STATIC 397 EFI_STATUS 398 AllocateMemory ( 399 VOID 400 ) 401 /*++ 402 403 Routine Description: 404 405 Allocate memory spaces for data structures used in compression process 406 407 Argements: 408 VOID 409 410 Returns: 411 412 EFI_SUCCESS - Memory is allocated successfully 413 EFI_OUT_OF_RESOURCES - Allocation fails 414 415 --*/ 416 { 417 UINT32 Index; 418 419 mText = malloc (WNDSIZ * 2 + MAXMATCH); 420 for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) { 421 mText[Index] = 0; 422 } 423 424 mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel)); 425 mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount)); 426 mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition)); 427 mParent = malloc (WNDSIZ * 2 * sizeof (*mParent)); 428 mPrev = malloc (WNDSIZ * 2 * sizeof (*mPrev)); 429 mNext = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext)); 430 431 mBufSiz = BLKSIZ; 432 mBuf = malloc (mBufSiz); 433 while (mBuf == NULL) { 434 mBufSiz = (mBufSiz / 10U) * 9U; 435 if (mBufSiz < 4 * 1024U) { 436 return EFI_OUT_OF_RESOURCES; 437 } 438 439 mBuf = malloc (mBufSiz); 440 } 441 442 mBuf[0] = 0; 443 444 return EFI_SUCCESS; 445 } 446 447 VOID 448 FreeMemory ( 449 VOID 450 ) 451 /*++ 452 453 Routine Description: 454 455 Called when compression is completed to free memory previously allocated. 456 457 Arguments: (VOID) 458 459 Returns: (VOID) 460 461 --*/ 462 { 463 if (mText != NULL) { 464 free (mText); 465 } 466 467 if (mLevel != NULL) { 468 free (mLevel); 469 } 470 471 if (mChildCount != NULL) { 472 free (mChildCount); 473 } 474 475 if (mPosition != NULL) { 476 free (mPosition); 477 } 478 479 if (mParent != NULL) { 480 free (mParent); 481 } 482 483 if (mPrev != NULL) { 484 free (mPrev); 485 } 486 487 if (mNext != NULL) { 488 free (mNext); 489 } 490 491 if (mBuf != NULL) { 492 free (mBuf); 493 } 494 495 return ; 496 } 497 498 STATIC 499 VOID 500 InitSlide ( 501 VOID 502 ) 503 /*++ 504 505 Routine Description: 506 507 Initialize String Info Log data structures 508 509 Arguments: (VOID) 510 511 Returns: (VOID) 512 513 --*/ 514 { 515 NODE Index; 516 517 for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) { 518 mLevel[Index] = 1; 519 mPosition[Index] = NIL; /* sentinel */ 520 } 521 522 for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) { 523 mParent[Index] = NIL; 524 } 525 526 mAvail = 1; 527 for (Index = 1; Index < WNDSIZ - 1; Index++) { 528 mNext[Index] = (NODE) (Index + 1); 529 } 530 531 mNext[WNDSIZ - 1] = NIL; 532 for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) { 533 mNext[Index] = NIL; 534 } 535 } 536 537 STATIC 538 NODE 539 Child ( 540 IN NODE NodeQ, 541 IN UINT8 CharC 542 ) 543 /*++ 544 545 Routine Description: 546 547 Find child node given the parent node and the edge character 548 549 Arguments: 550 551 NodeQ - the parent node 552 CharC - the edge character 553 554 Returns: 555 556 The child node (NIL if not found) 557 558 --*/ 559 { 560 NODE NodeR; 561 562 NodeR = mNext[HASH (NodeQ, CharC)]; 563 // 564 // sentinel 565 // 566 mParent[NIL] = NodeQ; 567 while (mParent[NodeR] != NodeQ) { 568 NodeR = mNext[NodeR]; 569 } 570 571 return NodeR; 572 } 573 574 STATIC 575 VOID 576 MakeChild ( 577 IN NODE Parent, 578 IN UINT8 CharC, 579 IN NODE Child 580 ) 581 /*++ 582 583 Routine Description: 584 585 Create a new child for a given parent node. 586 587 Arguments: 588 589 Parent - the parent node 590 CharC - the edge character 591 Child - the child node 592 593 Returns: (VOID) 594 595 --*/ 596 { 597 NODE Node1; 598 NODE Node2; 599 600 Node1 = (NODE) HASH (Parent, CharC); 601 Node2 = mNext[Node1]; 602 mNext[Node1] = Child; 603 mNext[Child] = Node2; 604 mPrev[Node2] = Child; 605 mPrev[Child] = Node1; 606 mParent[Child] = Parent; 607 mChildCount[Parent]++; 608 } 609 610 STATIC 611 VOID 612 Split ( 613 NODE Old 614 ) 615 /*++ 616 617 Routine Description: 618 619 Split a node. 620 621 Arguments: 622 623 Old - the node to split 624 625 Returns: (VOID) 626 627 --*/ 628 { 629 NODE New; 630 NODE TempNode; 631 632 New = mAvail; 633 mAvail = mNext[New]; 634 mChildCount[New] = 0; 635 TempNode = mPrev[Old]; 636 mPrev[New] = TempNode; 637 mNext[TempNode] = New; 638 TempNode = mNext[Old]; 639 mNext[New] = TempNode; 640 mPrev[TempNode] = New; 641 mParent[New] = mParent[Old]; 642 mLevel[New] = (UINT8) mMatchLen; 643 mPosition[New] = mPos; 644 MakeChild (New, mText[mMatchPos + mMatchLen], Old); 645 MakeChild (New, mText[mPos + mMatchLen], mPos); 646 } 647 648 STATIC 649 VOID 650 InsertNode ( 651 VOID 652 ) 653 /*++ 654 655 Routine Description: 656 657 Insert string info for current position into the String Info Log 658 659 Arguments: (VOID) 660 661 Returns: (VOID) 662 663 --*/ 664 { 665 NODE NodeQ; 666 NODE NodeR; 667 NODE Index2; 668 NODE NodeT; 669 UINT8 CharC; 670 UINT8 *t1; 671 UINT8 *t2; 672 673 if (mMatchLen >= 4) { 674 // 675 // We have just got a long match, the target tree 676 // can be located by MatchPos + 1. Travese the tree 677 // from bottom up to get to a proper starting point. 678 // The usage of PERC_FLAG ensures proper node deletion 679 // in DeleteNode() later. 680 // 681 mMatchLen--; 682 NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ); 683 NodeQ = mParent[NodeR]; 684 while (NodeQ == NIL) { 685 NodeR = mNext[NodeR]; 686 NodeQ = mParent[NodeR]; 687 } 688 689 while (mLevel[NodeQ] >= mMatchLen) { 690 NodeR = NodeQ; 691 NodeQ = mParent[NodeQ]; 692 } 693 694 NodeT = NodeQ; 695 while (mPosition[NodeT] < 0) { 696 mPosition[NodeT] = mPos; 697 NodeT = mParent[NodeT]; 698 } 699 700 if (NodeT < WNDSIZ) { 701 mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG); 702 } 703 } else { 704 // 705 // Locate the target tree 706 // 707 NodeQ = (NODE) (mText[mPos] + WNDSIZ); 708 CharC = mText[mPos + 1]; 709 NodeR = Child (NodeQ, CharC); 710 if (NodeR == NIL) { 711 MakeChild (NodeQ, CharC, mPos); 712 mMatchLen = 1; 713 return ; 714 } 715 716 mMatchLen = 2; 717 } 718 // 719 // Traverse down the tree to find a match. 720 // Update Position value along the route. 721 // Node split or creation is involved. 722 // 723 for (;;) { 724 if (NodeR >= WNDSIZ) { 725 Index2 = MAXMATCH; 726 mMatchPos = NodeR; 727 } else { 728 Index2 = mLevel[NodeR]; 729 mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG); 730 } 731 732 if (mMatchPos >= mPos) { 733 mMatchPos -= WNDSIZ; 734 } 735 736 t1 = &mText[mPos + mMatchLen]; 737 t2 = &mText[mMatchPos + mMatchLen]; 738 while (mMatchLen < Index2) { 739 if (*t1 != *t2) { 740 Split (NodeR); 741 return ; 742 } 743 744 mMatchLen++; 745 t1++; 746 t2++; 747 } 748 749 if (mMatchLen >= MAXMATCH) { 750 break; 751 } 752 753 mPosition[NodeR] = mPos; 754 NodeQ = NodeR; 755 NodeR = Child (NodeQ, *t1); 756 if (NodeR == NIL) { 757 MakeChild (NodeQ, *t1, mPos); 758 return ; 759 } 760 761 mMatchLen++; 762 } 763 764 NodeT = mPrev[NodeR]; 765 mPrev[mPos] = NodeT; 766 mNext[NodeT] = mPos; 767 NodeT = mNext[NodeR]; 768 mNext[mPos] = NodeT; 769 mPrev[NodeT] = mPos; 770 mParent[mPos] = NodeQ; 771 mParent[NodeR] = NIL; 772 773 // 774 // Special usage of 'next' 775 // 776 mNext[NodeR] = mPos; 777 778 } 779 780 STATIC 781 VOID 782 DeleteNode ( 783 VOID 784 ) 785 /*++ 786 787 Routine Description: 788 789 Delete outdated string info. (The Usage of PERC_FLAG 790 ensures a clean deletion) 791 792 Arguments: (VOID) 793 794 Returns: (VOID) 795 796 --*/ 797 { 798 NODE NodeQ; 799 NODE NodeR; 800 NODE NodeS; 801 NODE NodeT; 802 NODE NodeU; 803 804 if (mParent[mPos] == NIL) { 805 return ; 806 } 807 808 NodeR = mPrev[mPos]; 809 NodeS = mNext[mPos]; 810 mNext[NodeR] = NodeS; 811 mPrev[NodeS] = NodeR; 812 NodeR = mParent[mPos]; 813 mParent[mPos] = NIL; 814 if (NodeR >= WNDSIZ) { 815 return ; 816 } 817 818 mChildCount[NodeR]--; 819 if (mChildCount[NodeR] > 1) { 820 return ; 821 } 822 823 NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG); 824 if (NodeT >= mPos) { 825 NodeT -= WNDSIZ; 826 } 827 828 NodeS = NodeT; 829 NodeQ = mParent[NodeR]; 830 NodeU = mPosition[NodeQ]; 831 while (NodeU & (UINT32) PERC_FLAG) { 832 NodeU &= (UINT32)~PERC_FLAG; 833 if (NodeU >= mPos) { 834 NodeU -= WNDSIZ; 835 } 836 837 if (NodeU > NodeS) { 838 NodeS = NodeU; 839 } 840 841 mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ); 842 NodeQ = mParent[NodeQ]; 843 NodeU = mPosition[NodeQ]; 844 } 845 846 if (NodeQ < WNDSIZ) { 847 if (NodeU >= mPos) { 848 NodeU -= WNDSIZ; 849 } 850 851 if (NodeU > NodeS) { 852 NodeS = NodeU; 853 } 854 855 mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG); 856 } 857 858 NodeS = Child (NodeR, mText[NodeT + mLevel[NodeR]]); 859 NodeT = mPrev[NodeS]; 860 NodeU = mNext[NodeS]; 861 mNext[NodeT] = NodeU; 862 mPrev[NodeU] = NodeT; 863 NodeT = mPrev[NodeR]; 864 mNext[NodeT] = NodeS; 865 mPrev[NodeS] = NodeT; 866 NodeT = mNext[NodeR]; 867 mPrev[NodeT] = NodeS; 868 mNext[NodeS] = NodeT; 869 mParent[NodeS] = mParent[NodeR]; 870 mParent[NodeR] = NIL; 871 mNext[NodeR] = mAvail; 872 mAvail = NodeR; 873 } 874 875 STATIC 876 VOID 877 GetNextMatch ( 878 VOID 879 ) 880 /*++ 881 882 Routine Description: 883 884 Advance the current position (read in new data if needed). 885 Delete outdated string info. Find a match string for current position. 886 887 Arguments: (VOID) 888 889 Returns: (VOID) 890 891 --*/ 892 { 893 INT32 Number; 894 895 mRemainder--; 896 mPos++; 897 if (mPos == WNDSIZ * 2) { 898 memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH); 899 Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ); 900 mRemainder += Number; 901 mPos = WNDSIZ; 902 } 903 904 DeleteNode (); 905 InsertNode (); 906 } 907 908 STATIC 909 EFI_STATUS 910 Encode ( 911 VOID 912 ) 913 /*++ 914 915 Routine Description: 916 917 The main controlling routine for compression process. 918 919 Arguments: (VOID) 920 921 Returns: 922 923 EFI_SUCCESS - The compression is successful 924 EFI_OUT_0F_RESOURCES - Not enough memory for compression process 925 926 --*/ 927 { 928 EFI_STATUS Status; 929 INT32 LastMatchLen; 930 NODE LastMatchPos; 931 932 Status = AllocateMemory (); 933 if (EFI_ERROR (Status)) { 934 FreeMemory (); 935 return Status; 936 } 937 938 InitSlide (); 939 940 HufEncodeStart (); 941 942 mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH); 943 944 mMatchLen = 0; 945 mPos = WNDSIZ; 946 InsertNode (); 947 if (mMatchLen > mRemainder) { 948 mMatchLen = mRemainder; 949 } 950 951 while (mRemainder > 0) { 952 LastMatchLen = mMatchLen; 953 LastMatchPos = mMatchPos; 954 GetNextMatch (); 955 if (mMatchLen > mRemainder) { 956 mMatchLen = mRemainder; 957 } 958 959 if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) { 960 // 961 // Not enough benefits are gained by outputting a pointer, 962 // so just output the original character 963 // 964 Output (mText[mPos - 1], 0); 965 966 } else { 967 968 if (LastMatchLen == THRESHOLD) { 969 if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) { 970 Output (mText[mPos - 1], 0); 971 continue; 972 } 973 } 974 // 975 // Outputting a pointer is beneficial enough, do it. 976 // 977 Output ( 978 LastMatchLen + (UINT8_MAX + 1 - THRESHOLD), 979 (mPos - LastMatchPos - 2) & (WNDSIZ - 1) 980 ); 981 LastMatchLen--; 982 while (LastMatchLen > 0) { 983 GetNextMatch (); 984 LastMatchLen--; 985 } 986 987 if (mMatchLen > mRemainder) { 988 mMatchLen = mRemainder; 989 } 990 } 991 } 992 993 HufEncodeEnd (); 994 FreeMemory (); 995 return EFI_SUCCESS; 996 } 997 998 STATIC 999 VOID 1000 CountTFreq ( 1001 VOID 1002 ) 1003 /*++ 1004 1005 Routine Description: 1006 1007 Count the frequencies for the Extra Set 1008 1009 Arguments: (VOID) 1010 1011 Returns: (VOID) 1012 1013 --*/ 1014 { 1015 INT32 Index; 1016 INT32 Index3; 1017 INT32 Number; 1018 INT32 Count; 1019 1020 for (Index = 0; Index < NT; Index++) { 1021 mTFreq[Index] = 0; 1022 } 1023 1024 Number = NC; 1025 while (Number > 0 && mCLen[Number - 1] == 0) { 1026 Number--; 1027 } 1028 1029 Index = 0; 1030 while (Index < Number) { 1031 Index3 = mCLen[Index++]; 1032 if (Index3 == 0) { 1033 Count = 1; 1034 while (Index < Number && mCLen[Index] == 0) { 1035 Index++; 1036 Count++; 1037 } 1038 1039 if (Count <= 2) { 1040 mTFreq[0] = (UINT16) (mTFreq[0] + Count); 1041 } else if (Count <= 18) { 1042 mTFreq[1]++; 1043 } else if (Count == 19) { 1044 mTFreq[0]++; 1045 mTFreq[1]++; 1046 } else { 1047 mTFreq[2]++; 1048 } 1049 } else { 1050 mTFreq[Index3 + 2]++; 1051 } 1052 } 1053 } 1054 1055 STATIC 1056 VOID 1057 WritePTLen ( 1058 IN INT32 Number, 1059 IN INT32 nbit, 1060 IN INT32 Special 1061 ) 1062 /*++ 1063 1064 Routine Description: 1065 1066 Outputs the code length array for the Extra Set or the Position Set. 1067 1068 Arguments: 1069 1070 Number - the number of symbols 1071 nbit - the number of bits needed to represent 'n' 1072 Special - the special symbol that needs to be take care of 1073 1074 Returns: (VOID) 1075 1076 --*/ 1077 { 1078 INT32 Index; 1079 INT32 Index3; 1080 1081 while (Number > 0 && mPTLen[Number - 1] == 0) { 1082 Number--; 1083 } 1084 1085 PutBits (nbit, Number); 1086 Index = 0; 1087 while (Index < Number) { 1088 Index3 = mPTLen[Index++]; 1089 if (Index3 <= 6) { 1090 PutBits (3, Index3); 1091 } else { 1092 PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2); 1093 } 1094 1095 if (Index == Special) { 1096 while (Index < 6 && mPTLen[Index] == 0) { 1097 Index++; 1098 } 1099 1100 PutBits (2, (Index - 3) & 3); 1101 } 1102 } 1103 } 1104 1105 STATIC 1106 VOID 1107 WriteCLen ( 1108 VOID 1109 ) 1110 /*++ 1111 1112 Routine Description: 1113 1114 Outputs the code length array for Char&Length Set 1115 1116 Arguments: (VOID) 1117 1118 Returns: (VOID) 1119 1120 --*/ 1121 { 1122 INT32 Index; 1123 INT32 Index3; 1124 INT32 Number; 1125 INT32 Count; 1126 1127 Number = NC; 1128 while (Number > 0 && mCLen[Number - 1] == 0) { 1129 Number--; 1130 } 1131 1132 PutBits (CBIT, Number); 1133 Index = 0; 1134 while (Index < Number) { 1135 Index3 = mCLen[Index++]; 1136 if (Index3 == 0) { 1137 Count = 1; 1138 while (Index < Number && mCLen[Index] == 0) { 1139 Index++; 1140 Count++; 1141 } 1142 1143 if (Count <= 2) { 1144 for (Index3 = 0; Index3 < Count; Index3++) { 1145 PutBits (mPTLen[0], mPTCode[0]); 1146 } 1147 } else if (Count <= 18) { 1148 PutBits (mPTLen[1], mPTCode[1]); 1149 PutBits (4, Count - 3); 1150 } else if (Count == 19) { 1151 PutBits (mPTLen[0], mPTCode[0]); 1152 PutBits (mPTLen[1], mPTCode[1]); 1153 PutBits (4, 15); 1154 } else { 1155 PutBits (mPTLen[2], mPTCode[2]); 1156 PutBits (CBIT, Count - 20); 1157 } 1158 } else { 1159 PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]); 1160 } 1161 } 1162 } 1163 1164 STATIC 1165 VOID 1166 EncodeC ( 1167 IN INT32 Value 1168 ) 1169 { 1170 PutBits (mCLen[Value], mCCode[Value]); 1171 } 1172 1173 STATIC 1174 VOID 1175 EncodeP ( 1176 IN UINT32 Value 1177 ) 1178 { 1179 UINT32 Index; 1180 UINT32 NodeQ; 1181 1182 Index = 0; 1183 NodeQ = Value; 1184 while (NodeQ) { 1185 NodeQ >>= 1; 1186 Index++; 1187 } 1188 1189 PutBits (mPTLen[Index], mPTCode[Index]); 1190 if (Index > 1) { 1191 PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1))); 1192 } 1193 } 1194 1195 STATIC 1196 VOID 1197 SendBlock ( 1198 VOID 1199 ) 1200 /*++ 1201 1202 Routine Description: 1203 1204 Huffman code the block and output it. 1205 1206 Arguments: 1207 (VOID) 1208 1209 Returns: 1210 (VOID) 1211 1212 --*/ 1213 { 1214 UINT32 Index; 1215 UINT32 Index2; 1216 UINT32 Index3; 1217 UINT32 Flags; 1218 UINT32 Root; 1219 UINT32 Pos; 1220 UINT32 Size; 1221 Flags = 0; 1222 1223 Root = MakeTree (NC, mCFreq, mCLen, mCCode); 1224 Size = mCFreq[Root]; 1225 PutBits (16, Size); 1226 if (Root >= NC) { 1227 CountTFreq (); 1228 Root = MakeTree (NT, mTFreq, mPTLen, mPTCode); 1229 if (Root >= NT) { 1230 WritePTLen (NT, TBIT, 3); 1231 } else { 1232 PutBits (TBIT, 0); 1233 PutBits (TBIT, Root); 1234 } 1235 1236 WriteCLen (); 1237 } else { 1238 PutBits (TBIT, 0); 1239 PutBits (TBIT, 0); 1240 PutBits (CBIT, 0); 1241 PutBits (CBIT, Root); 1242 } 1243 1244 Root = MakeTree (NP, mPFreq, mPTLen, mPTCode); 1245 if (Root >= NP) { 1246 WritePTLen (NP, PBIT, -1); 1247 } else { 1248 PutBits (PBIT, 0); 1249 PutBits (PBIT, Root); 1250 } 1251 1252 Pos = 0; 1253 for (Index = 0; Index < Size; Index++) { 1254 if (Index % UINT8_BIT == 0) { 1255 Flags = mBuf[Pos++]; 1256 } else { 1257 Flags <<= 1; 1258 } 1259 1260 if (Flags & (1U << (UINT8_BIT - 1))) { 1261 EncodeC (mBuf[Pos++] + (1U << UINT8_BIT)); 1262 Index3 = mBuf[Pos++]; 1263 for (Index2 = 0; Index2 < 3; Index2++) { 1264 Index3 <<= UINT8_BIT; 1265 Index3 += mBuf[Pos++]; 1266 } 1267 1268 EncodeP (Index3); 1269 } else { 1270 EncodeC (mBuf[Pos++]); 1271 } 1272 } 1273 1274 for (Index = 0; Index < NC; Index++) { 1275 mCFreq[Index] = 0; 1276 } 1277 1278 for (Index = 0; Index < NP; Index++) { 1279 mPFreq[Index] = 0; 1280 } 1281 } 1282 1283 STATIC 1284 VOID 1285 Output ( 1286 IN UINT32 CharC, 1287 IN UINT32 Pos 1288 ) 1289 /*++ 1290 1291 Routine Description: 1292 1293 Outputs an Original Character or a Pointer 1294 1295 Arguments: 1296 1297 CharC - The original character or the 'String Length' element of a Pointer 1298 Pos - The 'Position' field of a Pointer 1299 1300 Returns: (VOID) 1301 1302 --*/ 1303 { 1304 STATIC UINT32 CPos; 1305 1306 if ((mOutputMask >>= 1) == 0) { 1307 mOutputMask = 1U << (UINT8_BIT - 1); 1308 // 1309 // Check the buffer overflow per outputing UINT8_BIT symbols 1310 // which is an Original Character or a Pointer. The biggest 1311 // symbol is a Pointer which occupies 5 bytes. 1312 // 1313 if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) { 1314 SendBlock (); 1315 mOutputPos = 0; 1316 } 1317 1318 CPos = mOutputPos++; 1319 mBuf[CPos] = 0; 1320 } 1321 1322 mBuf[mOutputPos++] = (UINT8) CharC; 1323 mCFreq[CharC]++; 1324 if (CharC >= (1U << UINT8_BIT)) { 1325 mBuf[CPos] |= mOutputMask; 1326 mBuf[mOutputPos++] = (UINT8) (Pos >> 24); 1327 mBuf[mOutputPos++] = (UINT8) (Pos >> 16); 1328 mBuf[mOutputPos++] = (UINT8) (Pos >> (UINT8_BIT)); 1329 mBuf[mOutputPos++] = (UINT8) Pos; 1330 CharC = 0; 1331 while (Pos) { 1332 Pos >>= 1; 1333 CharC++; 1334 } 1335 1336 mPFreq[CharC]++; 1337 } 1338 } 1339 1340 STATIC 1341 VOID 1342 HufEncodeStart ( 1343 VOID 1344 ) 1345 { 1346 INT32 Index; 1347 1348 for (Index = 0; Index < NC; Index++) { 1349 mCFreq[Index] = 0; 1350 } 1351 1352 for (Index = 0; Index < NP; Index++) { 1353 mPFreq[Index] = 0; 1354 } 1355 1356 mOutputPos = mOutputMask = 0; 1357 InitPutBits (); 1358 return ; 1359 } 1360 1361 STATIC 1362 VOID 1363 HufEncodeEnd ( 1364 VOID 1365 ) 1366 { 1367 SendBlock (); 1368 1369 // 1370 // Flush remaining bits 1371 // 1372 PutBits (UINT8_BIT - 1, 0); 1373 1374 return ; 1375 } 1376 1377 STATIC 1378 VOID 1379 MakeCrcTable ( 1380 VOID 1381 ) 1382 { 1383 UINT32 Index; 1384 UINT32 Index2; 1385 UINT32 Temp; 1386 1387 for (Index = 0; Index <= UINT8_MAX; Index++) { 1388 Temp = Index; 1389 for (Index2 = 0; Index2 < UINT8_BIT; Index2++) { 1390 if (Temp & 1) { 1391 Temp = (Temp >> 1) ^ CRCPOLY; 1392 } else { 1393 Temp >>= 1; 1394 } 1395 } 1396 1397 mCrcTable[Index] = (UINT16) Temp; 1398 } 1399 } 1400 1401 STATIC 1402 VOID 1403 PutBits ( 1404 IN INT32 Number, 1405 IN UINT32 Value 1406 ) 1407 /*++ 1408 1409 Routine Description: 1410 1411 Outputs rightmost n bits of x 1412 1413 Arguments: 1414 1415 Number - the rightmost n bits of the data is used 1416 x - the data 1417 1418 Returns: (VOID) 1419 1420 --*/ 1421 { 1422 UINT8 Temp; 1423 1424 while (Number >= mBitCount) { 1425 // 1426 // Number -= mBitCount should never equal to 32 1427 // 1428 Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount))); 1429 if (mDst < mDstUpperLimit) { 1430 *mDst++ = Temp; 1431 } 1432 1433 mCompSize++; 1434 mSubBitBuf = 0; 1435 mBitCount = UINT8_BIT; 1436 } 1437 1438 mSubBitBuf |= Value << (mBitCount -= Number); 1439 } 1440 1441 STATIC 1442 INT32 1443 FreadCrc ( 1444 OUT UINT8 *Pointer, 1445 IN INT32 Number 1446 ) 1447 /*++ 1448 1449 Routine Description: 1450 1451 Read in source data 1452 1453 Arguments: 1454 1455 Pointer - the buffer to hold the data 1456 Number - number of bytes to read 1457 1458 Returns: 1459 1460 number of bytes actually read 1461 1462 --*/ 1463 { 1464 INT32 Index; 1465 1466 for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) { 1467 *Pointer++ = *mSrc++; 1468 } 1469 1470 Number = Index; 1471 1472 Pointer -= Number; 1473 mOrigSize += Number; 1474 Index--; 1475 while (Index >= 0) { 1476 UPDATE_CRC (*Pointer++); 1477 Index--; 1478 } 1479 1480 return Number; 1481 } 1482 1483 STATIC 1484 VOID 1485 InitPutBits ( 1486 VOID 1487 ) 1488 { 1489 mBitCount = UINT8_BIT; 1490 mSubBitBuf = 0; 1491 } 1492 1493 STATIC 1494 VOID 1495 CountLen ( 1496 IN INT32 Index 1497 ) 1498 /*++ 1499 1500 Routine Description: 1501 1502 Count the number of each code length for a Huffman tree. 1503 1504 Arguments: 1505 1506 Index - the top node 1507 1508 Returns: (VOID) 1509 1510 --*/ 1511 { 1512 STATIC INT32 Depth = 0; 1513 1514 if (Index < mN) { 1515 mLenCnt[(Depth < 16) ? Depth : 16]++; 1516 } else { 1517 Depth++; 1518 CountLen (mLeft[Index]); 1519 CountLen (mRight[Index]); 1520 Depth--; 1521 } 1522 } 1523 1524 STATIC 1525 VOID 1526 MakeLen ( 1527 IN INT32 Root 1528 ) 1529 /*++ 1530 1531 Routine Description: 1532 1533 Create code length array for a Huffman tree 1534 1535 Arguments: 1536 1537 Root - the root of the tree 1538 1539 Returns: 1540 1541 VOID 1542 1543 --*/ 1544 { 1545 INT32 Index; 1546 INT32 Index3; 1547 UINT32 Cum; 1548 1549 for (Index = 0; Index <= 16; Index++) { 1550 mLenCnt[Index] = 0; 1551 } 1552 1553 CountLen (Root); 1554 1555 // 1556 // Adjust the length count array so that 1557 // no code will be generated longer than its designated length 1558 // 1559 Cum = 0; 1560 for (Index = 16; Index > 0; Index--) { 1561 Cum += mLenCnt[Index] << (16 - Index); 1562 } 1563 1564 while (Cum != (1U << 16)) { 1565 mLenCnt[16]--; 1566 for (Index = 15; Index > 0; Index--) { 1567 if (mLenCnt[Index] != 0) { 1568 mLenCnt[Index]--; 1569 mLenCnt[Index + 1] += 2; 1570 break; 1571 } 1572 } 1573 1574 Cum--; 1575 } 1576 1577 for (Index = 16; Index > 0; Index--) { 1578 Index3 = mLenCnt[Index]; 1579 Index3--; 1580 while (Index3 >= 0) { 1581 mLen[*mSortPtr++] = (UINT8) Index; 1582 Index3--; 1583 } 1584 } 1585 } 1586 1587 STATIC 1588 VOID 1589 DownHeap ( 1590 IN INT32 Index 1591 ) 1592 { 1593 INT32 Index2; 1594 INT32 Index3; 1595 1596 // 1597 // priority queue: send Index-th entry down heap 1598 // 1599 Index3 = mHeap[Index]; 1600 Index2 = 2 * Index; 1601 while (Index2 <= mHeapSize) { 1602 if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) { 1603 Index2++; 1604 } 1605 1606 if (mFreq[Index3] <= mFreq[mHeap[Index2]]) { 1607 break; 1608 } 1609 1610 mHeap[Index] = mHeap[Index2]; 1611 Index = Index2; 1612 Index2 = 2 * Index; 1613 } 1614 1615 mHeap[Index] = (INT16) Index3; 1616 } 1617 1618 STATIC 1619 VOID 1620 MakeCode ( 1621 IN INT32 Number, 1622 IN UINT8 Len[ ], 1623 OUT UINT16 Code[] 1624 ) 1625 /*++ 1626 1627 Routine Description: 1628 1629 Assign code to each symbol based on the code length array 1630 1631 Arguments: 1632 1633 Number - number of symbols 1634 Len - the code length array 1635 Code - stores codes for each symbol 1636 1637 Returns: (VOID) 1638 1639 --*/ 1640 { 1641 INT32 Index; 1642 UINT16 Start[18]; 1643 1644 Start[1] = 0; 1645 for (Index = 1; Index <= 16; Index++) { 1646 Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1); 1647 } 1648 1649 for (Index = 0; Index < Number; Index++) { 1650 Code[Index] = Start[Len[Index]]++; 1651 } 1652 } 1653 1654 STATIC 1655 INT32 1656 MakeTree ( 1657 IN INT32 NParm, 1658 IN UINT16 FreqParm[], 1659 OUT UINT8 LenParm[ ], 1660 OUT UINT16 CodeParm[] 1661 ) 1662 /*++ 1663 1664 Routine Description: 1665 1666 Generates Huffman codes given a frequency distribution of symbols 1667 1668 Arguments: 1669 1670 NParm - number of symbols 1671 FreqParm - frequency of each symbol 1672 LenParm - code length for each symbol 1673 CodeParm - code for each symbol 1674 1675 Returns: 1676 1677 Root of the Huffman tree. 1678 1679 --*/ 1680 { 1681 INT32 Index; 1682 INT32 Index2; 1683 INT32 Index3; 1684 INT32 Avail; 1685 1686 // 1687 // make tree, calculate len[], return root 1688 // 1689 mN = NParm; 1690 mFreq = FreqParm; 1691 mLen = LenParm; 1692 Avail = mN; 1693 mHeapSize = 0; 1694 mHeap[1] = 0; 1695 for (Index = 0; Index < mN; Index++) { 1696 mLen[Index] = 0; 1697 if (mFreq[Index]) { 1698 mHeapSize++; 1699 mHeap[mHeapSize] = (INT16) Index; 1700 } 1701 } 1702 1703 if (mHeapSize < 2) { 1704 CodeParm[mHeap[1]] = 0; 1705 return mHeap[1]; 1706 } 1707 1708 for (Index = mHeapSize / 2; Index >= 1; Index--) { 1709 // 1710 // make priority queue 1711 // 1712 DownHeap (Index); 1713 } 1714 1715 mSortPtr = CodeParm; 1716 do { 1717 Index = mHeap[1]; 1718 if (Index < mN) { 1719 *mSortPtr++ = (UINT16) Index; 1720 } 1721 1722 mHeap[1] = mHeap[mHeapSize--]; 1723 DownHeap (1); 1724 Index2 = mHeap[1]; 1725 if (Index2 < mN) { 1726 *mSortPtr++ = (UINT16) Index2; 1727 } 1728 1729 Index3 = Avail++; 1730 mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]); 1731 mHeap[1] = (INT16) Index3; 1732 DownHeap (1); 1733 mLeft[Index3] = (UINT16) Index; 1734 mRight[Index3] = (UINT16) Index2; 1735 } while (mHeapSize > 1); 1736 1737 mSortPtr = CodeParm; 1738 MakeLen (Index3); 1739 MakeCode (NParm, LenParm, CodeParm); 1740 1741 // 1742 // return root 1743 // 1744 return Index3; 1745 } 1746
