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