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