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 8Copyright (c) 2006, Intel Corporation 9All rights reserved. This program and the accompanying materials 10are licensed and made available under the terms and conditions of the BSD License 11which accompanies this distribution. The full text of the license may be found at 12http://opensource.org/licenses/bsd-license.php 13 14THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, 15WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. 16 17Module Name: 18 19 EfiCompress.c 20 21Abstract: 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 47typedef 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 82STATIC 83VOID 84PutDword( 85 IN UINT32 Data 86 ); 87 88STATIC 89EFI_STATUS 90AllocateMemory ( 91 ); 92 93STATIC 94VOID 95FreeMemory ( 96 ); 97 98STATIC 99VOID 100InitSlide ( 101 ); 102 103STATIC 104NODE 105Child ( 106 IN NODE q, 107 IN UINT8 c 108 ); 109 110STATIC 111VOID 112MakeChild ( 113 IN NODE q, 114 IN UINT8 c, 115 IN NODE r 116 ); 117 118STATIC 119VOID 120Split ( 121 IN NODE Old 122 ); 123 124STATIC 125VOID 126InsertNode ( 127 ); 128 129STATIC 130VOID 131DeleteNode ( 132 ); 133 134STATIC 135VOID 136GetNextMatch ( 137 ); 138 139STATIC 140EFI_STATUS 141Encode ( 142 ); 143 144STATIC 145VOID 146CountTFreq ( 147 ); 148 149STATIC 150VOID 151WritePTLen ( 152 IN INT32 n, 153 IN INT32 nbit, 154 IN INT32 Special 155 ); 156 157STATIC 158VOID 159WriteCLen ( 160 ); 161 162STATIC 163VOID 164EncodeC ( 165 IN INT32 c 166 ); 167 168STATIC 169VOID 170EncodeP ( 171 IN UINT32 p 172 ); 173 174STATIC 175VOID 176SendBlock ( 177 ); 178 179STATIC 180VOID 181Output ( 182 IN UINT32 c, 183 IN UINT32 p 184 ); 185 186STATIC 187VOID 188HufEncodeStart ( 189 ); 190 191STATIC 192VOID 193HufEncodeEnd ( 194 ); 195 196STATIC 197VOID 198MakeCrcTable ( 199 ); 200 201STATIC 202VOID 203PutBits ( 204 IN INT32 n, 205 IN UINT32 x 206 ); 207 208STATIC 209INT32 210FreadCrc ( 211 OUT UINT8 *p, 212 IN INT32 n 213 ); 214 215STATIC 216VOID 217InitPutBits ( 218 ); 219 220STATIC 221VOID 222CountLen ( 223 IN INT32 i 224 ); 225 226STATIC 227VOID 228MakeLen ( 229 IN INT32 Root 230 ); 231 232STATIC 233VOID 234DownHeap ( 235 IN INT32 i 236 ); 237 238STATIC 239VOID 240MakeCode ( 241 IN INT32 n, 242 IN UINT8 Len[], 243 OUT UINT16 Code[] 244 ); 245 246STATIC 247INT32 248MakeTree ( 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 260STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit; 261 262STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen; 263STATIC INT16 mHeap[NC + 1]; 264STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN; 265STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc; 266STATIC UINT32 mCompSize, mOrigSize; 267 268STATIC 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 272STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL; 273 274 275// 276// functions 277// 278 279EFI_STATUS 280EfiCompress ( 281 IN UINT8 *SrcBuffer, 282 IN UINT32 SrcSize, 283 IN UINT8 *DstBuffer, 284 IN OUT UINT32 *DstSize 285 ) 286/*++ 287 288Routine Description: 289 290 The main compression routine. 291 292Arguments: 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 300Returns: 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 374STATIC 375VOID 376PutDword( 377 IN UINT32 Data 378 ) 379/*++ 380 381Routine Description: 382 383 Put a dword to output stream 384 385Arguments: 386 387 Data - the dword to put 388 389Returns: (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 410STATIC 411EFI_STATUS 412AllocateMemory () 413/*++ 414 415Routine Description: 416 417 Allocate memory spaces for data structures used in compression process 418 419Argements: (VOID) 420 421Returns: 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 454VOID 455FreeMemory () 456/*++ 457 458Routine Description: 459 460 Called when compression is completed to free memory previously allocated. 461 462Arguments: (VOID) 463 464Returns: (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 504STATIC 505VOID 506InitSlide () 507/*++ 508 509Routine Description: 510 511 Initialize String Info Log data structures 512 513Arguments: (VOID) 514 515Returns: (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 540STATIC 541NODE 542Child ( 543 IN NODE q, 544 IN UINT8 c 545 ) 546/*++ 547 548Routine Description: 549 550 Find child node given the parent node and the edge character 551 552Arguments: 553 554 q - the parent node 555 c - the edge character 556 557Returns: 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 574STATIC 575VOID 576MakeChild ( 577 IN NODE q, 578 IN UINT8 c, 579 IN NODE r 580 ) 581/*++ 582 583Routine Description: 584 585 Create a new child for a given parent node. 586 587Arguments: 588 589 q - the parent node 590 c - the edge character 591 r - the child node 592 593Returns: (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 609STATIC 610VOID 611Split ( 612 NODE Old 613 ) 614/*++ 615 616Routine Description: 617 618 Split a node. 619 620Arguments: 621 622 Old - the node to split 623 624Returns: (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 646STATIC 647VOID 648InsertNode () 649/*++ 650 651Routine Description: 652 653 Insert string info for current position into the String Info Log 654 655Arguments: (VOID) 656 657Returns: (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 761STATIC 762VOID 763DeleteNode () 764/*++ 765 766Routine Description: 767 768 Delete outdated string info. (The Usage of PERC_FLAG 769 ensures a clean deletion) 770 771Arguments: (VOID) 772 773Returns: (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 835STATIC 836VOID 837GetNextMatch () 838/*++ 839 840Routine 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 845Arguments: (VOID) 846 847Returns: (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 864STATIC 865EFI_STATUS 866Encode () 867/*++ 868 869Routine Description: 870 871 The main controlling routine for compression process. 872 873Arguments: (VOID) 874 875Returns: 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 942STATIC 943VOID 944CountTFreq () 945/*++ 946 947Routine Description: 948 949 Count the frequencies for the Extra Set 950 951Arguments: (VOID) 952 953Returns: (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 991STATIC 992VOID 993WritePTLen ( 994 IN INT32 n, 995 IN INT32 nbit, 996 IN INT32 Special 997 ) 998/*++ 999 1000Routine Description: 1001 1002 Outputs the code length array for the Extra Set or the Position Set. 1003 1004Arguments: 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 1010Returns: (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 1037STATIC 1038VOID 1039WriteCLen () 1040/*++ 1041 1042Routine Description: 1043 1044 Outputs the code length array for Char&Length Set 1045 1046Arguments: (VOID) 1047 1048Returns: (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 1089STATIC 1090VOID 1091EncodeC ( 1092 IN INT32 c 1093 ) 1094{ 1095 PutBits(mCLen[c], mCCode[c]); 1096} 1097 1098STATIC 1099VOID 1100EncodeP ( 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 1118STATIC 1119VOID 1120SendBlock () 1121/*++ 1122 1123Routine Description: 1124 1125 Huffman code the block and output it. 1126 1127Argument: (VOID) 1128 1129Returns: (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 1187STATIC 1188VOID 1189Output ( 1190 IN UINT32 c, 1191 IN UINT32 p 1192 ) 1193/*++ 1194 1195Routine Description: 1196 1197 Outputs an Original Character or a Pointer 1198 1199Arguments: 1200 1201 c - The original character or the 'String Length' element of a Pointer 1202 p - The 'Position' field of a Pointer 1203 1204Returns: (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 1234STATIC 1235VOID 1236HufEncodeStart () 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 1251STATIC 1252VOID 1253HufEncodeEnd () 1254{ 1255 SendBlock(); 1256 1257 // 1258 // Flush remaining bits 1259 // 1260 PutBits(UINT8_BIT - 1, 0); 1261 1262 return; 1263} 1264 1265 1266STATIC 1267VOID 1268MakeCrcTable () 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 1285STATIC 1286VOID 1287PutBits ( 1288 IN INT32 n, 1289 IN UINT32 x 1290 ) 1291/*++ 1292 1293Routine Description: 1294 1295 Outputs rightmost n bits of x 1296 1297Argments: 1298 1299 n - the rightmost n bits of the data is used 1300 x - the data 1301 1302Returns: (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 1333STATIC 1334INT32 1335FreadCrc ( 1336 OUT UINT8 *p, 1337 IN INT32 n 1338 ) 1339/*++ 1340 1341Routine Description: 1342 1343 Read in source data 1344 1345Arguments: 1346 1347 p - the buffer to hold the data 1348 n - number of bytes to read 1349 1350Returns: 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 1372STATIC 1373VOID 1374InitPutBits () 1375{ 1376 mBitCount = UINT8_BIT; 1377 mSubBitBuf = 0; 1378} 1379 1380STATIC 1381VOID 1382CountLen ( 1383 IN INT32 i 1384 ) 1385/*++ 1386 1387Routine Description: 1388 1389 Count the number of each code length for a Huffman tree. 1390 1391Arguments: 1392 1393 i - the top node 1394 1395Returns: (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 1411STATIC 1412VOID 1413MakeLen ( 1414 IN INT32 Root 1415 ) 1416/*++ 1417 1418Routine Description: 1419 1420 Create code length array for a Huffman tree 1421 1422Arguments: 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 1464STATIC 1465VOID 1466DownHeap ( 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 1490STATIC 1491VOID 1492MakeCode ( 1493 IN INT32 n, 1494 IN UINT8 Len[], 1495 OUT UINT16 Code[] 1496 ) 1497/*++ 1498 1499Routine Description: 1500 1501 Assign code to each symbol based on the code length array 1502 1503Arguments: 1504 1505 n - number of symbols 1506 Len - the code length array 1507 Code - stores codes for each symbol 1508 1509Returns: (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 1525STATIC 1526INT32 1527MakeTree ( 1528 IN INT32 NParm, 1529 IN UINT16 FreqParm[], 1530 OUT UINT8 LenParm[], 1531 OUT UINT16 CodeParm[] 1532 ) 1533/*++ 1534 1535Routine Description: 1536 1537 Generates Huffman codes given a frequency distribution of symbols 1538 1539Arguments: 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 1546Returns: 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 1613int 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 1716done4: 1717 fclose(ofp); 1718 1719done3: 1720 free(obuf); 1721 1722done2: 1723 free(ibuf); 1724 1725done1: 1726 fclose(ifp); 1727 1728 return retval; 1729} 1730#endif // FOR_LIBRARY 1731