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 - 2016, 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 if (mText == NULL) { 421 return EFI_OUT_OF_RESOURCES; 422 } 423 for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) { 424 mText[Index] = 0; 425 } 426 427 mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel)); 428 mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount)); 429 mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition)); 430 mParent = malloc (WNDSIZ * 2 * sizeof (*mParent)); 431 mPrev = malloc (WNDSIZ * 2 * sizeof (*mPrev)); 432 mNext = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext)); 433 if (mLevel == NULL || mChildCount == NULL || mPosition == NULL || 434 mParent == NULL || mPrev == NULL || mNext == NULL) { 435 return EFI_OUT_OF_RESOURCES; 436 } 437 438 mBufSiz = BLKSIZ; 439 mBuf = malloc (mBufSiz); 440 while (mBuf == NULL) { 441 mBufSiz = (mBufSiz / 10U) * 9U; 442 if (mBufSiz < 4 * 1024U) { 443 return EFI_OUT_OF_RESOURCES; 444 } 445 446 mBuf = malloc (mBufSiz); 447 } 448 449 mBuf[0] = 0; 450 451 return EFI_SUCCESS; 452 } 453 454 VOID 455 FreeMemory ( 456 VOID 457 ) 458 /*++ 459 460 Routine Description: 461 462 Called when compression is completed to free memory previously allocated. 463 464 Arguments: (VOID) 465 466 Returns: (VOID) 467 468 --*/ 469 { 470 if (mText != NULL) { 471 free (mText); 472 } 473 474 if (mLevel != NULL) { 475 free (mLevel); 476 } 477 478 if (mChildCount != NULL) { 479 free (mChildCount); 480 } 481 482 if (mPosition != NULL) { 483 free (mPosition); 484 } 485 486 if (mParent != NULL) { 487 free (mParent); 488 } 489 490 if (mPrev != NULL) { 491 free (mPrev); 492 } 493 494 if (mNext != NULL) { 495 free (mNext); 496 } 497 498 if (mBuf != NULL) { 499 free (mBuf); 500 } 501 502 return ; 503 } 504 505 STATIC 506 VOID 507 InitSlide ( 508 VOID 509 ) 510 /*++ 511 512 Routine Description: 513 514 Initialize String Info Log data structures 515 516 Arguments: (VOID) 517 518 Returns: (VOID) 519 520 --*/ 521 { 522 NODE Index; 523 524 for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) { 525 mLevel[Index] = 1; 526 mPosition[Index] = NIL; /* sentinel */ 527 } 528 529 for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) { 530 mParent[Index] = NIL; 531 } 532 533 mAvail = 1; 534 for (Index = 1; Index < WNDSIZ - 1; Index++) { 535 mNext[Index] = (NODE) (Index + 1); 536 } 537 538 mNext[WNDSIZ - 1] = NIL; 539 for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) { 540 mNext[Index] = NIL; 541 } 542 } 543 544 STATIC 545 NODE 546 Child ( 547 IN NODE NodeQ, 548 IN UINT8 CharC 549 ) 550 /*++ 551 552 Routine Description: 553 554 Find child node given the parent node and the edge character 555 556 Arguments: 557 558 NodeQ - the parent node 559 CharC - the edge character 560 561 Returns: 562 563 The child node (NIL if not found) 564 565 --*/ 566 { 567 NODE NodeR; 568 569 NodeR = mNext[HASH (NodeQ, CharC)]; 570 // 571 // sentinel 572 // 573 mParent[NIL] = NodeQ; 574 while (mParent[NodeR] != NodeQ) { 575 NodeR = mNext[NodeR]; 576 } 577 578 return NodeR; 579 } 580 581 STATIC 582 VOID 583 MakeChild ( 584 IN NODE Parent, 585 IN UINT8 CharC, 586 IN NODE Child 587 ) 588 /*++ 589 590 Routine Description: 591 592 Create a new child for a given parent node. 593 594 Arguments: 595 596 Parent - the parent node 597 CharC - the edge character 598 Child - the child node 599 600 Returns: (VOID) 601 602 --*/ 603 { 604 NODE Node1; 605 NODE Node2; 606 607 Node1 = (NODE) HASH (Parent, CharC); 608 Node2 = mNext[Node1]; 609 mNext[Node1] = Child; 610 mNext[Child] = Node2; 611 mPrev[Node2] = Child; 612 mPrev[Child] = Node1; 613 mParent[Child] = Parent; 614 mChildCount[Parent]++; 615 } 616 617 STATIC 618 VOID 619 Split ( 620 NODE Old 621 ) 622 /*++ 623 624 Routine Description: 625 626 Split a node. 627 628 Arguments: 629 630 Old - the node to split 631 632 Returns: (VOID) 633 634 --*/ 635 { 636 NODE New; 637 NODE TempNode; 638 639 New = mAvail; 640 mAvail = mNext[New]; 641 mChildCount[New] = 0; 642 TempNode = mPrev[Old]; 643 mPrev[New] = TempNode; 644 mNext[TempNode] = New; 645 TempNode = mNext[Old]; 646 mNext[New] = TempNode; 647 mPrev[TempNode] = New; 648 mParent[New] = mParent[Old]; 649 mLevel[New] = (UINT8) mMatchLen; 650 mPosition[New] = mPos; 651 MakeChild (New, mText[mMatchPos + mMatchLen], Old); 652 MakeChild (New, mText[mPos + mMatchLen], mPos); 653 } 654 655 STATIC 656 VOID 657 InsertNode ( 658 VOID 659 ) 660 /*++ 661 662 Routine Description: 663 664 Insert string info for current position into the String Info Log 665 666 Arguments: (VOID) 667 668 Returns: (VOID) 669 670 --*/ 671 { 672 NODE NodeQ; 673 NODE NodeR; 674 NODE Index2; 675 NODE NodeT; 676 UINT8 CharC; 677 UINT8 *t1; 678 UINT8 *t2; 679 680 if (mMatchLen >= 4) { 681 // 682 // We have just got a long match, the target tree 683 // can be located by MatchPos + 1. Travese the tree 684 // from bottom up to get to a proper starting point. 685 // The usage of PERC_FLAG ensures proper node deletion 686 // in DeleteNode() later. 687 // 688 mMatchLen--; 689 NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ); 690 NodeQ = mParent[NodeR]; 691 while (NodeQ == NIL) { 692 NodeR = mNext[NodeR]; 693 NodeQ = mParent[NodeR]; 694 } 695 696 while (mLevel[NodeQ] >= mMatchLen) { 697 NodeR = NodeQ; 698 NodeQ = mParent[NodeQ]; 699 } 700 701 NodeT = NodeQ; 702 while (mPosition[NodeT] < 0) { 703 mPosition[NodeT] = mPos; 704 NodeT = mParent[NodeT]; 705 } 706 707 if (NodeT < WNDSIZ) { 708 mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG); 709 } 710 } else { 711 // 712 // Locate the target tree 713 // 714 NodeQ = (NODE) (mText[mPos] + WNDSIZ); 715 CharC = mText[mPos + 1]; 716 NodeR = Child (NodeQ, CharC); 717 if (NodeR == NIL) { 718 MakeChild (NodeQ, CharC, mPos); 719 mMatchLen = 1; 720 return ; 721 } 722 723 mMatchLen = 2; 724 } 725 // 726 // Traverse down the tree to find a match. 727 // Update Position value along the route. 728 // Node split or creation is involved. 729 // 730 for (;;) { 731 if (NodeR >= WNDSIZ) { 732 Index2 = MAXMATCH; 733 mMatchPos = NodeR; 734 } else { 735 Index2 = mLevel[NodeR]; 736 mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG); 737 } 738 739 if (mMatchPos >= mPos) { 740 mMatchPos -= WNDSIZ; 741 } 742 743 t1 = &mText[mPos + mMatchLen]; 744 t2 = &mText[mMatchPos + mMatchLen]; 745 while (mMatchLen < Index2) { 746 if (*t1 != *t2) { 747 Split (NodeR); 748 return ; 749 } 750 751 mMatchLen++; 752 t1++; 753 t2++; 754 } 755 756 if (mMatchLen >= MAXMATCH) { 757 break; 758 } 759 760 mPosition[NodeR] = mPos; 761 NodeQ = NodeR; 762 NodeR = Child (NodeQ, *t1); 763 if (NodeR == NIL) { 764 MakeChild (NodeQ, *t1, mPos); 765 return ; 766 } 767 768 mMatchLen++; 769 } 770 771 NodeT = mPrev[NodeR]; 772 mPrev[mPos] = NodeT; 773 mNext[NodeT] = mPos; 774 NodeT = mNext[NodeR]; 775 mNext[mPos] = NodeT; 776 mPrev[NodeT] = mPos; 777 mParent[mPos] = NodeQ; 778 mParent[NodeR] = NIL; 779 780 // 781 // Special usage of 'next' 782 // 783 mNext[NodeR] = mPos; 784 785 } 786 787 STATIC 788 VOID 789 DeleteNode ( 790 VOID 791 ) 792 /*++ 793 794 Routine Description: 795 796 Delete outdated string info. (The Usage of PERC_FLAG 797 ensures a clean deletion) 798 799 Arguments: (VOID) 800 801 Returns: (VOID) 802 803 --*/ 804 { 805 NODE NodeQ; 806 NODE NodeR; 807 NODE NodeS; 808 NODE NodeT; 809 NODE NodeU; 810 811 if (mParent[mPos] == NIL) { 812 return ; 813 } 814 815 NodeR = mPrev[mPos]; 816 NodeS = mNext[mPos]; 817 mNext[NodeR] = NodeS; 818 mPrev[NodeS] = NodeR; 819 NodeR = mParent[mPos]; 820 mParent[mPos] = NIL; 821 if (NodeR >= WNDSIZ) { 822 return ; 823 } 824 825 mChildCount[NodeR]--; 826 if (mChildCount[NodeR] > 1) { 827 return ; 828 } 829 830 NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG); 831 if (NodeT >= mPos) { 832 NodeT -= WNDSIZ; 833 } 834 835 NodeS = NodeT; 836 NodeQ = mParent[NodeR]; 837 NodeU = mPosition[NodeQ]; 838 while (NodeU & (UINT32) PERC_FLAG) { 839 NodeU &= (UINT32)~PERC_FLAG; 840 if (NodeU >= mPos) { 841 NodeU -= WNDSIZ; 842 } 843 844 if (NodeU > NodeS) { 845 NodeS = NodeU; 846 } 847 848 mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ); 849 NodeQ = mParent[NodeQ]; 850 NodeU = mPosition[NodeQ]; 851 } 852 853 if (NodeQ < WNDSIZ) { 854 if (NodeU >= mPos) { 855 NodeU -= WNDSIZ; 856 } 857 858 if (NodeU > NodeS) { 859 NodeS = NodeU; 860 } 861 862 mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG); 863 } 864 865 NodeS = Child (NodeR, mText[NodeT + mLevel[NodeR]]); 866 NodeT = mPrev[NodeS]; 867 NodeU = mNext[NodeS]; 868 mNext[NodeT] = NodeU; 869 mPrev[NodeU] = NodeT; 870 NodeT = mPrev[NodeR]; 871 mNext[NodeT] = NodeS; 872 mPrev[NodeS] = NodeT; 873 NodeT = mNext[NodeR]; 874 mPrev[NodeT] = NodeS; 875 mNext[NodeS] = NodeT; 876 mParent[NodeS] = mParent[NodeR]; 877 mParent[NodeR] = NIL; 878 mNext[NodeR] = mAvail; 879 mAvail = NodeR; 880 } 881 882 STATIC 883 VOID 884 GetNextMatch ( 885 VOID 886 ) 887 /*++ 888 889 Routine Description: 890 891 Advance the current position (read in new data if needed). 892 Delete outdated string info. Find a match string for current position. 893 894 Arguments: (VOID) 895 896 Returns: (VOID) 897 898 --*/ 899 { 900 INT32 Number; 901 902 mRemainder--; 903 mPos++; 904 if (mPos == WNDSIZ * 2) { 905 memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH); 906 Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ); 907 mRemainder += Number; 908 mPos = WNDSIZ; 909 } 910 911 DeleteNode (); 912 InsertNode (); 913 } 914 915 STATIC 916 EFI_STATUS 917 Encode ( 918 VOID 919 ) 920 /*++ 921 922 Routine Description: 923 924 The main controlling routine for compression process. 925 926 Arguments: (VOID) 927 928 Returns: 929 930 EFI_SUCCESS - The compression is successful 931 EFI_OUT_0F_RESOURCES - Not enough memory for compression process 932 933 --*/ 934 { 935 EFI_STATUS Status; 936 INT32 LastMatchLen; 937 NODE LastMatchPos; 938 939 Status = AllocateMemory (); 940 if (EFI_ERROR (Status)) { 941 FreeMemory (); 942 return Status; 943 } 944 945 InitSlide (); 946 947 HufEncodeStart (); 948 949 mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH); 950 951 mMatchLen = 0; 952 mPos = WNDSIZ; 953 InsertNode (); 954 if (mMatchLen > mRemainder) { 955 mMatchLen = mRemainder; 956 } 957 958 while (mRemainder > 0) { 959 LastMatchLen = mMatchLen; 960 LastMatchPos = mMatchPos; 961 GetNextMatch (); 962 if (mMatchLen > mRemainder) { 963 mMatchLen = mRemainder; 964 } 965 966 if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) { 967 // 968 // Not enough benefits are gained by outputting a pointer, 969 // so just output the original character 970 // 971 Output (mText[mPos - 1], 0); 972 973 } else { 974 975 if (LastMatchLen == THRESHOLD) { 976 if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) { 977 Output (mText[mPos - 1], 0); 978 continue; 979 } 980 } 981 // 982 // Outputting a pointer is beneficial enough, do it. 983 // 984 Output ( 985 LastMatchLen + (UINT8_MAX + 1 - THRESHOLD), 986 (mPos - LastMatchPos - 2) & (WNDSIZ - 1) 987 ); 988 LastMatchLen--; 989 while (LastMatchLen > 0) { 990 GetNextMatch (); 991 LastMatchLen--; 992 } 993 994 if (mMatchLen > mRemainder) { 995 mMatchLen = mRemainder; 996 } 997 } 998 } 999 1000 HufEncodeEnd (); 1001 FreeMemory (); 1002 return EFI_SUCCESS; 1003 } 1004 1005 STATIC 1006 VOID 1007 CountTFreq ( 1008 VOID 1009 ) 1010 /*++ 1011 1012 Routine Description: 1013 1014 Count the frequencies for the Extra Set 1015 1016 Arguments: (VOID) 1017 1018 Returns: (VOID) 1019 1020 --*/ 1021 { 1022 INT32 Index; 1023 INT32 Index3; 1024 INT32 Number; 1025 INT32 Count; 1026 1027 for (Index = 0; Index < NT; Index++) { 1028 mTFreq[Index] = 0; 1029 } 1030 1031 Number = NC; 1032 while (Number > 0 && mCLen[Number - 1] == 0) { 1033 Number--; 1034 } 1035 1036 Index = 0; 1037 while (Index < Number) { 1038 Index3 = mCLen[Index++]; 1039 if (Index3 == 0) { 1040 Count = 1; 1041 while (Index < Number && mCLen[Index] == 0) { 1042 Index++; 1043 Count++; 1044 } 1045 1046 if (Count <= 2) { 1047 mTFreq[0] = (UINT16) (mTFreq[0] + Count); 1048 } else if (Count <= 18) { 1049 mTFreq[1]++; 1050 } else if (Count == 19) { 1051 mTFreq[0]++; 1052 mTFreq[1]++; 1053 } else { 1054 mTFreq[2]++; 1055 } 1056 } else { 1057 mTFreq[Index3 + 2]++; 1058 } 1059 } 1060 } 1061 1062 STATIC 1063 VOID 1064 WritePTLen ( 1065 IN INT32 Number, 1066 IN INT32 nbit, 1067 IN INT32 Special 1068 ) 1069 /*++ 1070 1071 Routine Description: 1072 1073 Outputs the code length array for the Extra Set or the Position Set. 1074 1075 Arguments: 1076 1077 Number - the number of symbols 1078 nbit - the number of bits needed to represent 'n' 1079 Special - the special symbol that needs to be take care of 1080 1081 Returns: (VOID) 1082 1083 --*/ 1084 { 1085 INT32 Index; 1086 INT32 Index3; 1087 1088 while (Number > 0 && mPTLen[Number - 1] == 0) { 1089 Number--; 1090 } 1091 1092 PutBits (nbit, Number); 1093 Index = 0; 1094 while (Index < Number) { 1095 Index3 = mPTLen[Index++]; 1096 if (Index3 <= 6) { 1097 PutBits (3, Index3); 1098 } else { 1099 PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2); 1100 } 1101 1102 if (Index == Special) { 1103 while (Index < 6 && mPTLen[Index] == 0) { 1104 Index++; 1105 } 1106 1107 PutBits (2, (Index - 3) & 3); 1108 } 1109 } 1110 } 1111 1112 STATIC 1113 VOID 1114 WriteCLen ( 1115 VOID 1116 ) 1117 /*++ 1118 1119 Routine Description: 1120 1121 Outputs the code length array for Char&Length Set 1122 1123 Arguments: (VOID) 1124 1125 Returns: (VOID) 1126 1127 --*/ 1128 { 1129 INT32 Index; 1130 INT32 Index3; 1131 INT32 Number; 1132 INT32 Count; 1133 1134 Number = NC; 1135 while (Number > 0 && mCLen[Number - 1] == 0) { 1136 Number--; 1137 } 1138 1139 PutBits (CBIT, Number); 1140 Index = 0; 1141 while (Index < Number) { 1142 Index3 = mCLen[Index++]; 1143 if (Index3 == 0) { 1144 Count = 1; 1145 while (Index < Number && mCLen[Index] == 0) { 1146 Index++; 1147 Count++; 1148 } 1149 1150 if (Count <= 2) { 1151 for (Index3 = 0; Index3 < Count; Index3++) { 1152 PutBits (mPTLen[0], mPTCode[0]); 1153 } 1154 } else if (Count <= 18) { 1155 PutBits (mPTLen[1], mPTCode[1]); 1156 PutBits (4, Count - 3); 1157 } else if (Count == 19) { 1158 PutBits (mPTLen[0], mPTCode[0]); 1159 PutBits (mPTLen[1], mPTCode[1]); 1160 PutBits (4, 15); 1161 } else { 1162 PutBits (mPTLen[2], mPTCode[2]); 1163 PutBits (CBIT, Count - 20); 1164 } 1165 } else { 1166 PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]); 1167 } 1168 } 1169 } 1170 1171 STATIC 1172 VOID 1173 EncodeC ( 1174 IN INT32 Value 1175 ) 1176 { 1177 PutBits (mCLen[Value], mCCode[Value]); 1178 } 1179 1180 STATIC 1181 VOID 1182 EncodeP ( 1183 IN UINT32 Value 1184 ) 1185 { 1186 UINT32 Index; 1187 UINT32 NodeQ; 1188 1189 Index = 0; 1190 NodeQ = Value; 1191 while (NodeQ) { 1192 NodeQ >>= 1; 1193 Index++; 1194 } 1195 1196 PutBits (mPTLen[Index], mPTCode[Index]); 1197 if (Index > 1) { 1198 PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1))); 1199 } 1200 } 1201 1202 STATIC 1203 VOID 1204 SendBlock ( 1205 VOID 1206 ) 1207 /*++ 1208 1209 Routine Description: 1210 1211 Huffman code the block and output it. 1212 1213 Arguments: 1214 (VOID) 1215 1216 Returns: 1217 (VOID) 1218 1219 --*/ 1220 { 1221 UINT32 Index; 1222 UINT32 Index2; 1223 UINT32 Index3; 1224 UINT32 Flags; 1225 UINT32 Root; 1226 UINT32 Pos; 1227 UINT32 Size; 1228 Flags = 0; 1229 1230 Root = MakeTree (NC, mCFreq, mCLen, mCCode); 1231 Size = mCFreq[Root]; 1232 PutBits (16, Size); 1233 if (Root >= NC) { 1234 CountTFreq (); 1235 Root = MakeTree (NT, mTFreq, mPTLen, mPTCode); 1236 if (Root >= NT) { 1237 WritePTLen (NT, TBIT, 3); 1238 } else { 1239 PutBits (TBIT, 0); 1240 PutBits (TBIT, Root); 1241 } 1242 1243 WriteCLen (); 1244 } else { 1245 PutBits (TBIT, 0); 1246 PutBits (TBIT, 0); 1247 PutBits (CBIT, 0); 1248 PutBits (CBIT, Root); 1249 } 1250 1251 Root = MakeTree (NP, mPFreq, mPTLen, mPTCode); 1252 if (Root >= NP) { 1253 WritePTLen (NP, PBIT, -1); 1254 } else { 1255 PutBits (PBIT, 0); 1256 PutBits (PBIT, Root); 1257 } 1258 1259 Pos = 0; 1260 for (Index = 0; Index < Size; Index++) { 1261 if (Index % UINT8_BIT == 0) { 1262 Flags = mBuf[Pos++]; 1263 } else { 1264 Flags <<= 1; 1265 } 1266 1267 if (Flags & (1U << (UINT8_BIT - 1))) { 1268 EncodeC (mBuf[Pos++] + (1U << UINT8_BIT)); 1269 Index3 = mBuf[Pos++]; 1270 for (Index2 = 0; Index2 < 3; Index2++) { 1271 Index3 <<= UINT8_BIT; 1272 Index3 += mBuf[Pos++]; 1273 } 1274 1275 EncodeP (Index3); 1276 } else { 1277 EncodeC (mBuf[Pos++]); 1278 } 1279 } 1280 1281 for (Index = 0; Index < NC; Index++) { 1282 mCFreq[Index] = 0; 1283 } 1284 1285 for (Index = 0; Index < NP; Index++) { 1286 mPFreq[Index] = 0; 1287 } 1288 } 1289 1290 STATIC 1291 VOID 1292 Output ( 1293 IN UINT32 CharC, 1294 IN UINT32 Pos 1295 ) 1296 /*++ 1297 1298 Routine Description: 1299 1300 Outputs an Original Character or a Pointer 1301 1302 Arguments: 1303 1304 CharC - The original character or the 'String Length' element of a Pointer 1305 Pos - The 'Position' field of a Pointer 1306 1307 Returns: (VOID) 1308 1309 --*/ 1310 { 1311 STATIC UINT32 CPos; 1312 1313 if ((mOutputMask >>= 1) == 0) { 1314 mOutputMask = 1U << (UINT8_BIT - 1); 1315 // 1316 // Check the buffer overflow per outputing UINT8_BIT symbols 1317 // which is an Original Character or a Pointer. The biggest 1318 // symbol is a Pointer which occupies 5 bytes. 1319 // 1320 if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) { 1321 SendBlock (); 1322 mOutputPos = 0; 1323 } 1324 1325 CPos = mOutputPos++; 1326 mBuf[CPos] = 0; 1327 } 1328 1329 mBuf[mOutputPos++] = (UINT8) CharC; 1330 mCFreq[CharC]++; 1331 if (CharC >= (1U << UINT8_BIT)) { 1332 mBuf[CPos] |= mOutputMask; 1333 mBuf[mOutputPos++] = (UINT8) (Pos >> 24); 1334 mBuf[mOutputPos++] = (UINT8) (Pos >> 16); 1335 mBuf[mOutputPos++] = (UINT8) (Pos >> (UINT8_BIT)); 1336 mBuf[mOutputPos++] = (UINT8) Pos; 1337 CharC = 0; 1338 while (Pos) { 1339 Pos >>= 1; 1340 CharC++; 1341 } 1342 1343 mPFreq[CharC]++; 1344 } 1345 } 1346 1347 STATIC 1348 VOID 1349 HufEncodeStart ( 1350 VOID 1351 ) 1352 { 1353 INT32 Index; 1354 1355 for (Index = 0; Index < NC; Index++) { 1356 mCFreq[Index] = 0; 1357 } 1358 1359 for (Index = 0; Index < NP; Index++) { 1360 mPFreq[Index] = 0; 1361 } 1362 1363 mOutputPos = mOutputMask = 0; 1364 InitPutBits (); 1365 return ; 1366 } 1367 1368 STATIC 1369 VOID 1370 HufEncodeEnd ( 1371 VOID 1372 ) 1373 { 1374 SendBlock (); 1375 1376 // 1377 // Flush remaining bits 1378 // 1379 PutBits (UINT8_BIT - 1, 0); 1380 1381 return ; 1382 } 1383 1384 STATIC 1385 VOID 1386 MakeCrcTable ( 1387 VOID 1388 ) 1389 { 1390 UINT32 Index; 1391 UINT32 Index2; 1392 UINT32 Temp; 1393 1394 for (Index = 0; Index <= UINT8_MAX; Index++) { 1395 Temp = Index; 1396 for (Index2 = 0; Index2 < UINT8_BIT; Index2++) { 1397 if (Temp & 1) { 1398 Temp = (Temp >> 1) ^ CRCPOLY; 1399 } else { 1400 Temp >>= 1; 1401 } 1402 } 1403 1404 mCrcTable[Index] = (UINT16) Temp; 1405 } 1406 } 1407 1408 STATIC 1409 VOID 1410 PutBits ( 1411 IN INT32 Number, 1412 IN UINT32 Value 1413 ) 1414 /*++ 1415 1416 Routine Description: 1417 1418 Outputs rightmost n bits of x 1419 1420 Arguments: 1421 1422 Number - the rightmost n bits of the data is used 1423 x - the data 1424 1425 Returns: (VOID) 1426 1427 --*/ 1428 { 1429 UINT8 Temp; 1430 1431 while (Number >= mBitCount) { 1432 // 1433 // Number -= mBitCount should never equal to 32 1434 // 1435 Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount))); 1436 if (mDst < mDstUpperLimit) { 1437 *mDst++ = Temp; 1438 } 1439 1440 mCompSize++; 1441 mSubBitBuf = 0; 1442 mBitCount = UINT8_BIT; 1443 } 1444 1445 mSubBitBuf |= Value << (mBitCount -= Number); 1446 } 1447 1448 STATIC 1449 INT32 1450 FreadCrc ( 1451 OUT UINT8 *Pointer, 1452 IN INT32 Number 1453 ) 1454 /*++ 1455 1456 Routine Description: 1457 1458 Read in source data 1459 1460 Arguments: 1461 1462 Pointer - the buffer to hold the data 1463 Number - number of bytes to read 1464 1465 Returns: 1466 1467 number of bytes actually read 1468 1469 --*/ 1470 { 1471 INT32 Index; 1472 1473 for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) { 1474 *Pointer++ = *mSrc++; 1475 } 1476 1477 Number = Index; 1478 1479 Pointer -= Number; 1480 mOrigSize += Number; 1481 Index--; 1482 while (Index >= 0) { 1483 UPDATE_CRC (*Pointer++); 1484 Index--; 1485 } 1486 1487 return Number; 1488 } 1489 1490 STATIC 1491 VOID 1492 InitPutBits ( 1493 VOID 1494 ) 1495 { 1496 mBitCount = UINT8_BIT; 1497 mSubBitBuf = 0; 1498 } 1499 1500 STATIC 1501 VOID 1502 CountLen ( 1503 IN INT32 Index 1504 ) 1505 /*++ 1506 1507 Routine Description: 1508 1509 Count the number of each code length for a Huffman tree. 1510 1511 Arguments: 1512 1513 Index - the top node 1514 1515 Returns: (VOID) 1516 1517 --*/ 1518 { 1519 STATIC INT32 Depth = 0; 1520 1521 if (Index < mN) { 1522 mLenCnt[(Depth < 16) ? Depth : 16]++; 1523 } else { 1524 Depth++; 1525 CountLen (mLeft[Index]); 1526 CountLen (mRight[Index]); 1527 Depth--; 1528 } 1529 } 1530 1531 STATIC 1532 VOID 1533 MakeLen ( 1534 IN INT32 Root 1535 ) 1536 /*++ 1537 1538 Routine Description: 1539 1540 Create code length array for a Huffman tree 1541 1542 Arguments: 1543 1544 Root - the root of the tree 1545 1546 Returns: 1547 1548 VOID 1549 1550 --*/ 1551 { 1552 INT32 Index; 1553 INT32 Index3; 1554 UINT32 Cum; 1555 1556 for (Index = 0; Index <= 16; Index++) { 1557 mLenCnt[Index] = 0; 1558 } 1559 1560 CountLen (Root); 1561 1562 // 1563 // Adjust the length count array so that 1564 // no code will be generated longer than its designated length 1565 // 1566 Cum = 0; 1567 for (Index = 16; Index > 0; Index--) { 1568 Cum += mLenCnt[Index] << (16 - Index); 1569 } 1570 1571 while (Cum != (1U << 16)) { 1572 mLenCnt[16]--; 1573 for (Index = 15; Index > 0; Index--) { 1574 if (mLenCnt[Index] != 0) { 1575 mLenCnt[Index]--; 1576 mLenCnt[Index + 1] += 2; 1577 break; 1578 } 1579 } 1580 1581 Cum--; 1582 } 1583 1584 for (Index = 16; Index > 0; Index--) { 1585 Index3 = mLenCnt[Index]; 1586 Index3--; 1587 while (Index3 >= 0) { 1588 mLen[*mSortPtr++] = (UINT8) Index; 1589 Index3--; 1590 } 1591 } 1592 } 1593 1594 STATIC 1595 VOID 1596 DownHeap ( 1597 IN INT32 Index 1598 ) 1599 { 1600 INT32 Index2; 1601 INT32 Index3; 1602 1603 // 1604 // priority queue: send Index-th entry down heap 1605 // 1606 Index3 = mHeap[Index]; 1607 Index2 = 2 * Index; 1608 while (Index2 <= mHeapSize) { 1609 if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) { 1610 Index2++; 1611 } 1612 1613 if (mFreq[Index3] <= mFreq[mHeap[Index2]]) { 1614 break; 1615 } 1616 1617 mHeap[Index] = mHeap[Index2]; 1618 Index = Index2; 1619 Index2 = 2 * Index; 1620 } 1621 1622 mHeap[Index] = (INT16) Index3; 1623 } 1624 1625 STATIC 1626 VOID 1627 MakeCode ( 1628 IN INT32 Number, 1629 IN UINT8 Len[ ], 1630 OUT UINT16 Code[] 1631 ) 1632 /*++ 1633 1634 Routine Description: 1635 1636 Assign code to each symbol based on the code length array 1637 1638 Arguments: 1639 1640 Number - number of symbols 1641 Len - the code length array 1642 Code - stores codes for each symbol 1643 1644 Returns: (VOID) 1645 1646 --*/ 1647 { 1648 INT32 Index; 1649 UINT16 Start[18]; 1650 1651 Start[1] = 0; 1652 for (Index = 1; Index <= 16; Index++) { 1653 Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1); 1654 } 1655 1656 for (Index = 0; Index < Number; Index++) { 1657 Code[Index] = Start[Len[Index]]++; 1658 } 1659 } 1660 1661 STATIC 1662 INT32 1663 MakeTree ( 1664 IN INT32 NParm, 1665 IN UINT16 FreqParm[], 1666 OUT UINT8 LenParm[ ], 1667 OUT UINT16 CodeParm[] 1668 ) 1669 /*++ 1670 1671 Routine Description: 1672 1673 Generates Huffman codes given a frequency distribution of symbols 1674 1675 Arguments: 1676 1677 NParm - number of symbols 1678 FreqParm - frequency of each symbol 1679 LenParm - code length for each symbol 1680 CodeParm - code for each symbol 1681 1682 Returns: 1683 1684 Root of the Huffman tree. 1685 1686 --*/ 1687 { 1688 INT32 Index; 1689 INT32 Index2; 1690 INT32 Index3; 1691 INT32 Avail; 1692 1693 // 1694 // make tree, calculate len[], return root 1695 // 1696 mN = NParm; 1697 mFreq = FreqParm; 1698 mLen = LenParm; 1699 Avail = mN; 1700 mHeapSize = 0; 1701 mHeap[1] = 0; 1702 for (Index = 0; Index < mN; Index++) { 1703 mLen[Index] = 0; 1704 if (mFreq[Index]) { 1705 mHeapSize++; 1706 mHeap[mHeapSize] = (INT16) Index; 1707 } 1708 } 1709 1710 if (mHeapSize < 2) { 1711 CodeParm[mHeap[1]] = 0; 1712 return mHeap[1]; 1713 } 1714 1715 for (Index = mHeapSize / 2; Index >= 1; Index--) { 1716 // 1717 // make priority queue 1718 // 1719 DownHeap (Index); 1720 } 1721 1722 mSortPtr = CodeParm; 1723 do { 1724 Index = mHeap[1]; 1725 if (Index < mN) { 1726 *mSortPtr++ = (UINT16) Index; 1727 } 1728 1729 mHeap[1] = mHeap[mHeapSize--]; 1730 DownHeap (1); 1731 Index2 = mHeap[1]; 1732 if (Index2 < mN) { 1733 *mSortPtr++ = (UINT16) Index2; 1734 } 1735 1736 Index3 = Avail++; 1737 mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]); 1738 mHeap[1] = (INT16) Index3; 1739 DownHeap (1); 1740 mLeft[Index3] = (UINT16) Index; 1741 mRight[Index3] = (UINT16) Index2; 1742 } while (mHeapSize > 1); 1743 1744 mSortPtr = CodeParm; 1745 MakeLen (Index3); 1746 MakeCode (NParm, LenParm, CodeParm); 1747 1748 // 1749 // return root 1750 // 1751 return Index3; 1752 } 1753
