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