BaseTools/Source/C/TianoCompress/TianoCompress.c

   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.
   5 This sequence is further divided into Blocks and Huffman codings are applied to
   6 each Block.
   7
   8 Copyright (c) 2007 - 2016, Intel Corporation. All rights reserved.<BR>
   9 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 **/
  18
  19 #include "Compress.h"
  20 #include "TianoCompress.h"
  21 #include "EfiUtilityMsgs.h"
  22 #include "ParseInf.h"
  23 #include <stdio.h>
  24 #include "assert.h"
  25
  26 //
  27 // Macro Definitions
  28 //
  29 static BOOLEAN VerboseMode = FALSE;
  30 static BOOLEAN QuietMode = FALSE;
  31 #undef UINT8_MAX
  32 #define UINT8_MAX     0xff
  33 #define UINT8_BIT     8
  34 #define THRESHOLD     3
  35 #define INIT_CRC      0
  36 #define WNDBIT        19
  37 #define WNDSIZ        (1U << WNDBIT)
  38 #define MAXMATCH      256
  39 #define BLKSIZ        (1U << 14)  // 16 * 1024U
  40 #define PERC_FLAG     0x80000000U
  41 #define CODE_BIT      16
  42 #define NIL           0
  43 #define MAX_HASH_VAL  (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
  44 #define HASH(p, c)    ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
  45 #define CRCPOLY       0xA001
  46 #define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
  47
  48 //
  49 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
  50 //
  51 //#define NC    (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
  52 #define CBIT  9
  53 #define NP    (WNDBIT + 1)
  54 #define PBIT  5
  55 //#define NT    (CODE_BIT + 3)
  56 //#define TBIT  5
  57 //#if NT > NP
  58 //#define NPT NT
  59 //#else
  60 //#define NPT NP
  61 //#endif
  62
  63 //
  64 //  Global Variables
  65 //
  66 STATIC BOOLEAN ENCODE = FALSE;
  67 STATIC BOOLEAN DECODE = FALSE;
  68 STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
  69 STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
  70 STATIC INT16  mHeap[NC + 1];
  71 STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
  72 STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
  73 STATIC UINT32 mCompSize, mOrigSize;
  74
  75 STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],
  76   mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
  77
  78 STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
  79
  80 static  UINT64     DebugLevel;
  81 static  BOOLEAN    DebugMode;
  82 //
  83 // functions
  84 //
  85 EFI_STATUS
  86 TianoCompress (
  87   IN      UINT8   *SrcBuffer,
  88   IN      UINT32  SrcSize,
  89   IN      UINT8   *DstBuffer,
  90   IN OUT  UINT32  *DstSize
  91   )
  92 /*++
  93
  94 Routine Description:
  95
  96   The internal implementation of [Efi/Tiano]Compress().
  97
  98 Arguments:
  99
 100   SrcBuffer   - The buffer storing the source data
 101   SrcSize     - The size of source data
 102   DstBuffer   - The buffer to store the compressed data
 103
 104   Version     - The version of de/compression algorithm.
 105                 Version 1 for EFI 1.1 de/compression algorithm.
 106                 Version 2 for Tiano de/compression algorithm.
 107
 108 Returns:
 109
 110   EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,
 111                 DstSize contains the size needed.
 112   EFI_SUCCESS           - Compression is successful.
 113   EFI_OUT_OF_RESOURCES  - No resource to complete function.
 114   EFI_INVALID_PARAMETER - Parameter supplied is wrong.
 115
 116 --*/
 117 {
 118   EFI_STATUS  Status;
 119
 120   //
 121   // Initializations
 122   //
 123   mBufSiz         = 0;
 124   mBuf            = NULL;
 125   mText           = NULL;
 126   mLevel          = NULL;
 127   mChildCount     = NULL;
 128   mPosition       = NULL;
 129   mParent         = NULL;
 130   mPrev           = NULL;
 131   mNext           = NULL;
 132
 133
 134   mSrc            = SrcBuffer;
 135   mSrcUpperLimit  = mSrc + SrcSize;
 136   mDst            = DstBuffer;
 137   mDstUpperLimit  = mDst +*DstSize;
 138
 139   PutDword (0L);
 140   PutDword (0L);
 141
 142   MakeCrcTable ();
 143
 144   mOrigSize             = mCompSize = 0;
 145   mCrc                  = INIT_CRC;
 146
 147   //
 148   // Compress it
 149   //
 150   Status = Encode ();
 151   if (EFI_ERROR (Status)) {
 152     return EFI_OUT_OF_RESOURCES;
 153   }
 154
 155   //
 156   // Null terminate the compressed data
 157   //
 158
 159   if (mDst < mDstUpperLimit) {
 160     *mDst++ = 0;
 161   }
 162
 163   //
 164   // Fill in compressed size and original size
 165   //
 166   mDst = DstBuffer;
 167
 168   PutDword (mCompSize + 1);
 169   PutDword (mOrigSize);
 170   //
 171   // Return
 172   //
 173
 174   if (mCompSize + 1 + 8 > *DstSize) {
 175     *DstSize = mCompSize + 1 + 8;
 176     return EFI_BUFFER_TOO_SMALL;
 177   } else {
 178     *DstSize = mCompSize + 1 + 8;
 179     return EFI_SUCCESS;
 180   }
 181 }
 182
 183 STATIC
 184 VOID
 185 PutDword (
 186   IN UINT32 Data
 187   )
 188 /*++
 189
 190 Routine Description:
 191
 192   Put a dword to output stream
 193
 194 Arguments:
 195
 196   Data    - the dword to put
 197
 198 Returns: (VOID)
 199
 200 --*/
 201 {
 202   if (mDst < mDstUpperLimit) {
 203     *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
 204   }
 205
 206   if (mDst < mDstUpperLimit) {
 207     *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
 208   }
 209
 210   if (mDst < mDstUpperLimit) {
 211     *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
 212   }
 213
 214   if (mDst < mDstUpperLimit) {
 215     *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
 216   }
 217 }
 218
 219 STATIC
 220 EFI_STATUS
 221 AllocateMemory (
 222   VOID
 223   )
 224 /*++
 225
 226 Routine Description:
 227
 228   Allocate memory spaces for data structures used in compression process
 229
 230 Argements:
 231   VOID
 232
 233 Returns:
 234
 235   EFI_SUCCESS           - Memory is allocated successfully
 236   EFI_OUT_OF_RESOURCES  - Allocation fails
 237
 238 --*/
 239 {
 240   UINT32  Index;
 241
 242   mText = malloc (WNDSIZ * 2 + MAXMATCH);
 243   if (mText == NULL) {
 244     Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");
 245     return EFI_OUT_OF_RESOURCES;
 246   }
 247   for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {
 248     mText[Index] = 0;
 249   }
 250
 251   mLevel      = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
 252   mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
 253   mPosition   = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
 254   mParent     = malloc (WNDSIZ * 2 * sizeof (*mParent));
 255   mPrev       = malloc (WNDSIZ * 2 * sizeof (*mPrev));
 256   mNext       = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));
 257   if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
 258     mParent == NULL || mPrev == NULL || mNext == NULL) {
 259     Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");
 260     return EFI_OUT_OF_RESOURCES;
 261   }
 262
 263   mBufSiz     = BLKSIZ;
 264   mBuf        = malloc (mBufSiz);
 265   while (mBuf == NULL) {
 266     mBufSiz = (mBufSiz / 10U) * 9U;
 267     if (mBufSiz < 4 * 1024U) {
 268       return EFI_OUT_OF_RESOURCES;
 269     }
 270
 271     mBuf = malloc (mBufSiz);
 272   }
 273
 274   mBuf[0] = 0;
 275
 276   return EFI_SUCCESS;
 277 }
 278
 279 VOID
 280 FreeMemory (
 281   VOID
 282   )
 283 /*++
 284
 285 Routine Description:
 286
 287   Called when compression is completed to free memory previously allocated.
 288
 289 Arguments: (VOID)
 290
 291 Returns: (VOID)
 292
 293 --*/
 294 {
 295   if (mText != NULL) {
 296     free (mText);
 297   }
 298
 299   if (mLevel != NULL) {
 300     free (mLevel);
 301   }
 302
 303   if (mChildCount != NULL) {
 304     free (mChildCount);
 305   }
 306
 307   if (mPosition != NULL) {
 308     free (mPosition);
 309   }
 310
 311   if (mParent != NULL) {
 312     free (mParent);
 313   }
 314
 315   if (mPrev != NULL) {
 316     free (mPrev);
 317   }
 318
 319   if (mNext != NULL) {
 320     free (mNext);
 321   }
 322
 323   if (mBuf != NULL) {
 324     free (mBuf);
 325   }
 326
 327   return ;
 328 }
 329
 330 STATIC
 331 VOID
 332 InitSlide (
 333   VOID
 334   )
 335 /*++
 336
 337 Routine Description:
 338
 339   Initialize String Info Log data structures
 340
 341 Arguments: (VOID)
 342
 343 Returns: (VOID)
 344
 345 --*/
 346 {
 347   NODE  Index;
 348
 349   for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {
 350     mLevel[Index]     = 1;
 351     mPosition[Index]  = NIL;  // sentinel
 352   }
 353
 354   for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {
 355     mParent[Index] = NIL;
 356   }
 357
 358   mAvail = 1;
 359   for (Index = 1; Index < WNDSIZ - 1; Index++) {
 360     mNext[Index] = (NODE) (Index + 1);
 361   }
 362
 363   mNext[WNDSIZ - 1] = NIL;
 364   for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {
 365     mNext[Index] = NIL;
 366   }
 367 }
 368
 369 STATIC
 370 NODE
 371 Child (
 372   IN NODE  NodeQ,
 373   IN UINT8 CharC
 374   )
 375 /*++
 376
 377 Routine Description:
 378
 379   Find child node given the parent node and the edge character
 380
 381 Arguments:
 382
 383   NodeQ       - the parent node
 384   CharC       - the edge character
 385
 386 Returns:
 387
 388   The child node (NIL if not found)
 389
 390 --*/
 391 {
 392   NODE  NodeR;
 393
 394   NodeR = mNext[HASH (NodeQ, CharC)];
 395   //
 396   // sentinel
 397   //
 398   mParent[NIL] = NodeQ;
 399   while (mParent[NodeR] != NodeQ) {
 400     NodeR = mNext[NodeR];
 401   }
 402
 403   return NodeR;
 404 }
 405
 406 STATIC
 407 VOID
 408 MakeChild (
 409   IN NODE  Parent,
 410   IN UINT8 CharC,
 411   IN NODE  Child
 412   )
 413 /*++
 414
 415 Routine Description:
 416
 417   Create a new child for a given parent node.
 418
 419 Arguments:
 420
 421   Parent       - the parent node
 422   CharC   - the edge character
 423   Child       - the child node
 424
 425 Returns: (VOID)
 426
 427 --*/
 428 {
 429   NODE  Node1;
 430   NODE  Node2;
 431
 432   Node1           = (NODE) HASH (Parent, CharC);
 433   Node2           = mNext[Node1];
 434   mNext[Node1]    = Child;
 435   mNext[Child]    = Node2;
 436   mPrev[Node2]    = Child;
 437   mPrev[Child]    = Node1;
 438   mParent[Child]  = Parent;
 439   mChildCount[Parent]++;
 440 }
 441
 442 STATIC
 443 VOID
 444 Split (
 445   NODE Old
 446   )
 447 /*++
 448
 449 Routine Description:
 450
 451   Split a node.
 452
 453 Arguments:
 454
 455   Old     - the node to split
 456
 457 Returns: (VOID)
 458
 459 --*/
 460 {
 461   NODE  New;
 462   NODE  TempNode;
 463
 464   New               = mAvail;
 465   mAvail            = mNext[New];
 466   mChildCount[New]  = 0;
 467   TempNode          = mPrev[Old];
 468   mPrev[New]        = TempNode;
 469   mNext[TempNode]   = New;
 470   TempNode          = mNext[Old];
 471   mNext[New]        = TempNode;
 472   mPrev[TempNode]   = New;
 473   mParent[New]      = mParent[Old];
 474   mLevel[New]       = (UINT8) mMatchLen;
 475   mPosition[New]    = mPos;
 476   MakeChild (New, mText[mMatchPos + mMatchLen], Old);
 477   MakeChild (New, mText[mPos + mMatchLen], mPos);
 478 }
 479
 480 STATIC
 481 VOID
 482 InsertNode (
 483   VOID
 484   )
 485 /*++
 486
 487 Routine Description:
 488
 489   Insert string info for current position into the String Info Log
 490
 491 Arguments: (VOID)
 492
 493 Returns: (VOID)
 494
 495 --*/
 496 {
 497   NODE  NodeQ;
 498   NODE  NodeR;
 499   NODE  Index2;
 500   NODE  NodeT;
 501   UINT8 CharC;
 502   UINT8 *t1;
 503   UINT8 *t2;
 504
 505   if (mMatchLen >= 4) {
 506     //
 507     // We have just got a long match, the target tree
 508     // can be located by MatchPos + 1. Travese the tree
 509     // from bottom up to get to a proper starting point.
 510     // The usage of PERC_FLAG ensures proper node deletion
 511     // in DeleteNode() later.
 512     //
 513     mMatchLen--;
 514     NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);
 515     NodeQ = mParent[NodeR];
 516     while (NodeQ == NIL) {
 517       NodeR = mNext[NodeR];
 518       NodeQ = mParent[NodeR];
 519     }
 520
 521     while (mLevel[NodeQ] >= mMatchLen) {
 522       NodeR = NodeQ;
 523       NodeQ = mParent[NodeQ];
 524     }
 525
 526     NodeT = NodeQ;
 527     while (mPosition[NodeT] < 0) {
 528       mPosition[NodeT]  = mPos;
 529       NodeT             = mParent[NodeT];
 530     }
 531
 532     if (NodeT < WNDSIZ) {
 533       mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);
 534     }
 535   } else {
 536     //
 537     // Locate the target tree
 538     //
 539     NodeQ = (NODE) (mText[mPos] + WNDSIZ);
 540     CharC = mText[mPos + 1];
 541     NodeR = Child (NodeQ, CharC);
 542     if (NodeR == NIL) {
 543       MakeChild (NodeQ, CharC, mPos);
 544       mMatchLen = 1;
 545       return ;
 546     }
 547
 548     mMatchLen = 2;
 549   }
 550   //
 551   // Traverse down the tree to find a match.
 552   // Update Position value along the route.
 553   // Node split or creation is involved.
 554   //
 555   for (;;) {
 556     if (NodeR >= WNDSIZ) {
 557       Index2    = MAXMATCH;
 558       mMatchPos = NodeR;
 559     } else {
 560       Index2    = mLevel[NodeR];
 561       mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
 562     }
 563
 564     if (mMatchPos >= mPos) {
 565       mMatchPos -= WNDSIZ;
 566     }
 567
 568     t1  = &mText[mPos + mMatchLen];
 569     t2  = &mText[mMatchPos + mMatchLen];
 570     while (mMatchLen < Index2) {
 571       if (*t1 != *t2) {
 572         Split (NodeR);
 573         return ;
 574       }
 575
 576       mMatchLen++;
 577       t1++;
 578       t2++;
 579     }
 580
 581     if (mMatchLen >= MAXMATCH) {
 582       break;
 583     }
 584
 585     mPosition[NodeR]  = mPos;
 586     NodeQ             = NodeR;
 587     NodeR             = Child (NodeQ, *t1);
 588     if (NodeR == NIL) {
 589       MakeChild (NodeQ, *t1, mPos);
 590       return ;
 591     }
 592
 593     mMatchLen++;
 594   }
 595
 596   NodeT           = mPrev[NodeR];
 597   mPrev[mPos]     = NodeT;
 598   mNext[NodeT]    = mPos;
 599   NodeT           = mNext[NodeR];
 600   mNext[mPos]     = NodeT;
 601   mPrev[NodeT]    = mPos;
 602   mParent[mPos]   = NodeQ;
 603   mParent[NodeR]  = NIL;
 604
 605   //
 606   // Special usage of 'next'
 607   //
 608   mNext[NodeR] = mPos;
 609
 610 }
 611
 612 STATIC
 613 VOID
 614 DeleteNode (
 615   VOID
 616   )
 617 /*++
 618
 619 Routine Description:
 620
 621   Delete outdated string info. (The Usage of PERC_FLAG
 622   ensures a clean deletion)
 623
 624 Arguments: (VOID)
 625
 626 Returns: (VOID)
 627
 628 --*/
 629 {
 630   NODE  NodeQ;
 631   NODE  NodeR;
 632   NODE  NodeS;
 633   NODE  NodeT;
 634   NODE  NodeU;
 635
 636   if (mParent[mPos] == NIL) {
 637     return ;
 638   }
 639
 640   NodeR         = mPrev[mPos];
 641   NodeS         = mNext[mPos];
 642   mNext[NodeR]  = NodeS;
 643   mPrev[NodeS]  = NodeR;
 644   NodeR         = mParent[mPos];
 645   mParent[mPos] = NIL;
 646   if (NodeR >= WNDSIZ) {
 647     return ;
 648   }
 649
 650   mChildCount[NodeR]--;
 651   if (mChildCount[NodeR] > 1) {
 652     return ;
 653   }
 654
 655   NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
 656   if (NodeT >= mPos) {
 657     NodeT -= WNDSIZ;
 658   }
 659
 660   NodeS = NodeT;
 661   NodeQ = mParent[NodeR];
 662   NodeU = mPosition[NodeQ];
 663   while (NodeU & (UINT32) PERC_FLAG) {
 664     NodeU &= (UINT32)~PERC_FLAG;
 665     if (NodeU >= mPos) {
 666       NodeU -= WNDSIZ;
 667     }
 668
 669     if (NodeU > NodeS) {
 670       NodeS = NodeU;
 671     }
 672
 673     mPosition[NodeQ]  = (NODE) (NodeS | WNDSIZ);
 674     NodeQ             = mParent[NodeQ];
 675     NodeU             = mPosition[NodeQ];
 676   }
 677
 678   if (NodeQ < WNDSIZ) {
 679     if (NodeU >= mPos) {
 680       NodeU -= WNDSIZ;
 681     }
 682
 683     if (NodeU > NodeS) {
 684       NodeS = NodeU;
 685     }
 686
 687     mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);
 688   }
 689
 690   NodeS           = Child (NodeR, mText[NodeT + mLevel[NodeR]]);
 691   NodeT           = mPrev[NodeS];
 692   NodeU           = mNext[NodeS];
 693   mNext[NodeT]    = NodeU;
 694   mPrev[NodeU]    = NodeT;
 695   NodeT           = mPrev[NodeR];
 696   mNext[NodeT]    = NodeS;
 697   mPrev[NodeS]    = NodeT;
 698   NodeT           = mNext[NodeR];
 699   mPrev[NodeT]    = NodeS;
 700   mNext[NodeS]    = NodeT;
 701   mParent[NodeS]  = mParent[NodeR];
 702   mParent[NodeR]  = NIL;
 703   mNext[NodeR]    = mAvail;
 704   mAvail          = NodeR;
 705 }
 706
 707 STATIC
 708 VOID
 709 GetNextMatch (
 710   VOID
 711   )
 712 /*++
 713
 714 Routine Description:
 715
 716   Advance the current position (read in new data if needed).
 717   Delete outdated string info. Find a match string for current position.
 718
 719 Arguments: (VOID)
 720
 721 Returns: (VOID)
 722
 723 --*/
 724 {
 725   INT32 Number;
 726
 727   mRemainder--;
 728   mPos++;
 729   if (mPos == WNDSIZ * 2) {
 730     memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
 731     Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
 732     mRemainder += Number;
 733     mPos = WNDSIZ;
 734   }
 735
 736   DeleteNode ();
 737   InsertNode ();
 738 }
 739
 740 STATIC
 741 EFI_STATUS
 742 Encode (
 743   VOID
 744   )
 745 /*++
 746
 747 Routine Description:
 748
 749   The main controlling routine for compression process.
 750
 751 Arguments: (VOID)
 752
 753 Returns:
 754
 755   EFI_SUCCESS           - The compression is successful
 756   EFI_OUT_0F_RESOURCES  - Not enough memory for compression process
 757
 758 --*/
 759 {
 760   EFI_STATUS  Status;
 761   INT32       LastMatchLen;
 762   NODE        LastMatchPos;
 763
 764   Status = AllocateMemory ();
 765   if (EFI_ERROR (Status)) {
 766     FreeMemory ();
 767     return Status;
 768   }
 769
 770   InitSlide ();
 771
 772   HufEncodeStart ();
 773
 774   mRemainder  = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
 775
 776   mMatchLen   = 0;
 777   mPos        = WNDSIZ;
 778   InsertNode ();
 779   if (mMatchLen > mRemainder) {
 780     mMatchLen = mRemainder;
 781   }
 782
 783   while (mRemainder > 0) {
 784     LastMatchLen  = mMatchLen;
 785     LastMatchPos  = mMatchPos;
 786     GetNextMatch ();
 787     if (mMatchLen > mRemainder) {
 788       mMatchLen = mRemainder;
 789     }
 790
 791     if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
 792       //
 793       // Not enough benefits are gained by outputting a pointer,
 794       // so just output the original character
 795       //
 796       Output (mText[mPos - 1], 0);
 797
 798     } else {
 799
 800       if (LastMatchLen == THRESHOLD) {
 801         if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {
 802           Output (mText[mPos - 1], 0);
 803           continue;
 804         }
 805       }
 806       //
 807       // Outputting a pointer is beneficial enough, do it.
 808       //
 809       Output (
 810         LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
 811         (mPos - LastMatchPos - 2) & (WNDSIZ - 1)
 812         );
 813       LastMatchLen--;
 814       while (LastMatchLen > 0) {
 815         GetNextMatch ();
 816         LastMatchLen--;
 817       }
 818
 819       if (mMatchLen > mRemainder) {
 820         mMatchLen = mRemainder;
 821       }
 822     }
 823   }
 824
 825   HufEncodeEnd ();
 826   FreeMemory ();
 827   return EFI_SUCCESS;
 828 }
 829
 830 STATIC
 831 VOID
 832 CountTFreq (
 833   VOID
 834   )
 835 /*++
 836
 837 Routine Description:
 838
 839   Count the frequencies for the Extra Set
 840
 841 Arguments: (VOID)
 842
 843 Returns: (VOID)
 844
 845 --*/
 846 {
 847   INT32 Index;
 848   INT32 Index3;
 849   INT32 Number;
 850   INT32 Count;
 851
 852   for (Index = 0; Index < NT; Index++) {
 853     mTFreq[Index] = 0;
 854   }
 855
 856   Number = NC;
 857   while (Number > 0 && mCLen[Number - 1] == 0) {
 858     Number--;
 859   }
 860
 861   Index = 0;
 862   while (Index < Number) {
 863     Index3 = mCLen[Index++];
 864     if (Index3 == 0) {
 865       Count = 1;
 866       while (Index < Number && mCLen[Index] == 0) {
 867         Index++;
 868         Count++;
 869       }
 870
 871       if (Count <= 2) {
 872         mTFreq[0] = (UINT16) (mTFreq[0] + Count);
 873       } else if (Count <= 18) {
 874         mTFreq[1]++;
 875       } else if (Count == 19) {
 876         mTFreq[0]++;
 877         mTFreq[1]++;
 878       } else {
 879         mTFreq[2]++;
 880       }
 881     } else {
 882       mTFreq[Index3 + 2]++;
 883     }
 884   }
 885 }
 886
 887 STATIC
 888 VOID
 889 WritePTLen (
 890   IN INT32 Number,
 891   IN INT32 nbit,
 892   IN INT32 Special
 893   )
 894 /*++
 895
 896 Routine Description:
 897
 898   Outputs the code length array for the Extra Set or the Position Set.
 899
 900 Arguments:
 901
 902   Number       - the number of symbols
 903   nbit    - the number of bits needed to represent 'n'
 904   Special - the special symbol that needs to be take care of
 905
 906 Returns: (VOID)
 907
 908 --*/
 909 {
 910   INT32 Index;
 911   INT32 Index3;
 912
 913   while (Number > 0 && mPTLen[Number - 1] == 0) {
 914     Number--;
 915   }
 916
 917   PutBits (nbit, Number);
 918   Index = 0;
 919   while (Index < Number) {
 920     Index3 = mPTLen[Index++];
 921     if (Index3 <= 6) {
 922       PutBits (3, Index3);
 923     } else {
 924       PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);
 925     }
 926
 927     if (Index == Special) {
 928       while (Index < 6 && mPTLen[Index] == 0) {
 929         Index++;
 930       }
 931
 932       PutBits (2, (Index - 3) & 3);
 933     }
 934   }
 935 }
 936
 937 STATIC
 938 VOID
 939 WriteCLen (
 940   VOID
 941   )
 942 /*++
 943
 944 Routine Description:
 945
 946   Outputs the code length array for Char&Length Set
 947
 948 Arguments: (VOID)
 949
 950 Returns: (VOID)
 951
 952 --*/
 953 {
 954   INT32 Index;
 955   INT32 Index3;
 956   INT32 Number;
 957   INT32 Count;
 958
 959   Number = NC;
 960   while (Number > 0 && mCLen[Number - 1] == 0) {
 961     Number--;
 962   }
 963
 964   PutBits (CBIT, Number);
 965   Index = 0;
 966   while (Index < Number) {
 967     Index3 = mCLen[Index++];
 968     if (Index3 == 0) {
 969       Count = 1;
 970       while (Index < Number && mCLen[Index] == 0) {
 971         Index++;
 972         Count++;
 973       }
 974
 975       if (Count <= 2) {
 976         for (Index3 = 0; Index3 < Count; Index3++) {
 977           PutBits (mPTLen[0], mPTCode[0]);
 978         }
 979       } else if (Count <= 18) {
 980         PutBits (mPTLen[1], mPTCode[1]);
 981         PutBits (4, Count - 3);
 982       } else if (Count == 19) {
 983         PutBits (mPTLen[0], mPTCode[0]);
 984         PutBits (mPTLen[1], mPTCode[1]);
 985         PutBits (4, 15);
 986       } else {
 987         PutBits (mPTLen[2], mPTCode[2]);
 988         PutBits (CBIT, Count - 20);
 989       }
 990     } else {
 991       PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);
 992     }
 993   }
 994 }
 995
 996 STATIC
 997 VOID
 998 EncodeC (
 999   IN INT32 Value
1000   )
1001 {
1002   PutBits (mCLen[Value], mCCode[Value]);
1003 }
1004
1005 STATIC
1006 VOID
1007 EncodeP (
1008   IN UINT32 Value
1009   )
1010 {
1011   UINT32  Index;
1012   UINT32  NodeQ;
1013
1014   Index = 0;
1015   NodeQ = Value;
1016   while (NodeQ) {
1017     NodeQ >>= 1;
1018     Index++;
1019   }
1020
1021   PutBits (mPTLen[Index], mPTCode[Index]);
1022   if (Index > 1) {
1023     PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));
1024   }
1025 }
1026
1027 STATIC
1028 VOID
1029 SendBlock (
1030   VOID
1031   )
1032 /*++
1033
1034 Routine Description:
1035
1036   Huffman code the block and output it.
1037
1038 Arguments:
1039   (VOID)
1040
1041 Returns:
1042   (VOID)
1043
1044 --*/
1045 {
1046   UINT32  Index;
1047   UINT32  Index2;
1048   UINT32  Index3;
1049   UINT32  Flags;
1050   UINT32  Root;
1051   UINT32  Pos;
1052   UINT32  Size;
1053   Flags = 0;
1054
1055   Root  = MakeTree (NC, mCFreq, mCLen, mCCode);
1056   Size  = mCFreq[Root];
1057
1058   PutBits (16, Size);
1059   if (Root >= NC) {
1060     CountTFreq ();
1061     Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
1062     if (Root >= NT) {
1063       WritePTLen (NT, TBIT, 3);
1064     } else {
1065       PutBits (TBIT, 0);
1066       PutBits (TBIT, Root);
1067     }
1068
1069     WriteCLen ();
1070   } else {
1071     PutBits (TBIT, 0);
1072     PutBits (TBIT, 0);
1073     PutBits (CBIT, 0);
1074     PutBits (CBIT, Root);
1075   }
1076
1077   Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
1078   if (Root >= NP) {
1079     WritePTLen (NP, PBIT, -1);
1080   } else {
1081     PutBits (PBIT, 0);
1082     PutBits (PBIT, Root);
1083   }
1084
1085   Pos = 0;
1086   for (Index = 0; Index < Size; Index++) {
1087     if (Index % UINT8_BIT == 0) {
1088       Flags = mBuf[Pos++];
1089     } else {
1090       Flags <<= 1;
1091     }
1092
1093     if (Flags & (1U << (UINT8_BIT - 1))) {
1094       EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));
1095       Index3 = mBuf[Pos++];
1096       for (Index2 = 0; Index2 < 3; Index2++) {
1097         Index3 <<= UINT8_BIT;
1098         Index3 += mBuf[Pos++];
1099       }
1100
1101       EncodeP (Index3);
1102     } else {
1103       EncodeC (mBuf[Pos++]);
1104     }
1105   }
1106
1107   for (Index = 0; Index < NC; Index++) {
1108     mCFreq[Index] = 0;
1109   }
1110
1111   for (Index = 0; Index < NP; Index++) {
1112     mPFreq[Index] = 0;
1113   }
1114 }
1115
1116 STATIC
1117 VOID
1118 Output (
1119   IN UINT32 CharC,
1120   IN UINT32 Pos
1121   )
1122 /*++
1123
1124 Routine Description:
1125
1126   Outputs an Original Character or a Pointer
1127
1128 Arguments:
1129
1130   CharC     - The original character or the 'String Length' element of a Pointer
1131   Pos     - The 'Position' field of a Pointer
1132
1133 Returns: (VOID)
1134
1135 --*/
1136 {
1137   STATIC UINT32 CPos;
1138
1139   if ((mOutputMask >>= 1) == 0) {
1140     mOutputMask = 1U << (UINT8_BIT - 1);
1141     //
1142     // Check the buffer overflow per outputing UINT8_BIT symbols
1143     // which is an Original Character or a Pointer. The biggest
1144     // symbol is a Pointer which occupies 5 bytes.
1145     //
1146     if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {
1147       SendBlock ();
1148       mOutputPos = 0;
1149     }
1150
1151     CPos        = mOutputPos++;
1152     mBuf[CPos]  = 0;
1153   }
1154
1155   mBuf[mOutputPos++] = (UINT8) CharC;
1156   mCFreq[CharC]++;
1157   if (CharC >= (1U << UINT8_BIT)) {
1158     mBuf[CPos] |= mOutputMask;
1159     mBuf[mOutputPos++]  = (UINT8) (Pos >> 24);
1160     mBuf[mOutputPos++]  = (UINT8) (Pos >> 16);
1161     mBuf[mOutputPos++]  = (UINT8) (Pos >> (UINT8_BIT));
1162     mBuf[mOutputPos++]  = (UINT8) Pos;
1163     CharC               = 0;
1164     while (Pos) {
1165       Pos >>= 1;
1166       CharC++;
1167     }
1168
1169     mPFreq[CharC]++;
1170   }
1171 }
1172
1173 STATIC
1174 VOID
1175 HufEncodeStart (
1176   VOID
1177   )
1178 {
1179   INT32 Index;
1180
1181   for (Index = 0; Index < NC; Index++) {
1182     mCFreq[Index] = 0;
1183   }
1184
1185   for (Index = 0; Index < NP; Index++) {
1186     mPFreq[Index] = 0;
1187   }
1188
1189   mOutputPos = mOutputMask = 0;
1190   InitPutBits ();
1191   return ;
1192 }
1193
1194 STATIC
1195 VOID
1196 HufEncodeEnd (
1197   VOID
1198   )
1199 {
1200   SendBlock ();
1201
1202   //
1203   // Flush remaining bits
1204   //
1205   PutBits (UINT8_BIT - 1, 0);
1206
1207   return ;
1208 }
1209
1210 STATIC
1211 VOID
1212 MakeCrcTable (
1213   VOID
1214   )
1215 {
1216   UINT32  Index;
1217   UINT32  Index2;
1218   UINT32  Temp;
1219
1220   for (Index = 0; Index <= UINT8_MAX; Index++) {
1221     Temp = Index;
1222     for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {
1223       if (Temp & 1) {
1224         Temp = (Temp >> 1) ^ CRCPOLY;
1225       } else {
1226         Temp >>= 1;
1227       }
1228     }
1229
1230     mCrcTable[Index] = (UINT16) Temp;
1231   }
1232 }
1233
1234 STATIC
1235 VOID
1236 PutBits (
1237   IN INT32  Number,
1238   IN UINT32 Value
1239   )
1240 /*++
1241
1242 Routine Description:
1243
1244   Outputs rightmost n bits of x
1245
1246 Arguments:
1247
1248   Number   - the rightmost n bits of the data is used
1249   x   - the data
1250
1251 Returns: (VOID)
1252
1253 --*/
1254 {
1255   UINT8 Temp;
1256
1257   while (Number >= mBitCount) {
1258     //
1259     // Number -= mBitCount should never equal to 32
1260     //
1261     Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));
1262
1263     if (mDst < mDstUpperLimit) {
1264       *mDst++ = Temp;
1265     }
1266
1267     mCompSize++;
1268     mSubBitBuf  = 0;
1269     mBitCount   = UINT8_BIT;
1270   }
1271
1272   mSubBitBuf |= Value << (mBitCount -= Number);
1273 }
1274
1275 STATIC
1276 INT32
1277 FreadCrc (
1278   OUT UINT8 *Pointer,
1279   IN  INT32 Number
1280   )
1281 /*++
1282
1283 Routine Description:
1284
1285   Read in source data
1286
1287 Arguments:
1288
1289   Pointer   - the buffer to hold the data
1290   Number   - number of bytes to read
1291
1292 Returns:
1293
1294   number of bytes actually read
1295
1296 --*/
1297 {
1298   INT32 Index;
1299
1300   for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {
1301     *Pointer++ = *mSrc++;
1302   }
1303
1304   Number = Index;
1305
1306   Pointer -= Number;
1307   mOrigSize += Number;
1308
1309   Index--;
1310   while (Index >= 0) {
1311     UPDATE_CRC (*Pointer++);
1312     Index--;
1313   }
1314
1315   return Number;
1316 }
1317
1318 STATIC
1319 VOID
1320 InitPutBits (
1321   VOID
1322   )
1323 {
1324   mBitCount   = UINT8_BIT;
1325   mSubBitBuf  = 0;
1326 }
1327
1328 STATIC
1329 VOID
1330 CountLen (
1331   IN INT32 Index
1332   )
1333 /*++
1334
1335 Routine Description:
1336
1337   Count the number of each code length for a Huffman tree.
1338
1339 Arguments:
1340
1341   Index   - the top node
1342
1343 Returns: (VOID)
1344
1345 --*/
1346 {
1347   STATIC INT32  Depth = 0;
1348
1349   if (Index < mN) {
1350     mLenCnt[(Depth < 16) ? Depth : 16]++;
1351   } else {
1352     Depth++;
1353     CountLen (mLeft[Index]);
1354     CountLen (mRight[Index]);
1355     Depth--;
1356   }
1357 }
1358
1359 STATIC
1360 VOID
1361 MakeLen (
1362   IN INT32 Root
1363   )
1364 /*++
1365
1366 Routine Description:
1367
1368   Create code length array for a Huffman tree
1369
1370 Arguments:
1371
1372   Root   - the root of the tree
1373
1374 Returns:
1375
1376   VOID
1377
1378 --*/
1379 {
1380   INT32   Index;
1381   INT32   Index3;
1382   UINT32  Cum;
1383
1384   for (Index = 0; Index <= 16; Index++) {
1385     mLenCnt[Index] = 0;
1386   }
1387
1388   CountLen (Root);
1389
1390   //
1391   // Adjust the length count array so that
1392   // no code will be generated longer than its designated length
1393   //
1394   Cum = 0;
1395   for (Index = 16; Index > 0; Index--) {
1396     Cum += mLenCnt[Index] << (16 - Index);
1397   }
1398
1399   while (Cum != (1U << 16)) {
1400     mLenCnt[16]--;
1401     for (Index = 15; Index > 0; Index--) {
1402       if (mLenCnt[Index] != 0) {
1403         mLenCnt[Index]--;
1404         mLenCnt[Index + 1] += 2;
1405         break;
1406       }
1407     }
1408
1409     Cum--;
1410   }
1411
1412   for (Index = 16; Index > 0; Index--) {
1413     Index3 = mLenCnt[Index];
1414     Index3--;
1415     while (Index3 >= 0) {
1416       mLen[*mSortPtr++] = (UINT8) Index;
1417       Index3--;
1418     }
1419   }
1420 }
1421
1422 STATIC
1423 VOID
1424 DownHeap (
1425   IN INT32 Index
1426   )
1427 {
1428   INT32 Index2;
1429   INT32 Index3;
1430
1431   //
1432   // priority queue: send Index-th entry down heap
1433   //
1434   Index3  = mHeap[Index];
1435   Index2  = 2 * Index;
1436   while (Index2 <= mHeapSize) {
1437     if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {
1438       Index2++;
1439     }
1440
1441     if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {
1442       break;
1443     }
1444
1445     mHeap[Index]  = mHeap[Index2];
1446     Index         = Index2;
1447     Index2        = 2 * Index;
1448   }
1449
1450   mHeap[Index] = (INT16) Index3;
1451 }
1452
1453 STATIC
1454 VOID
1455 MakeCode (
1456   IN  INT32       Number,
1457   IN  UINT8 Len[  ],
1458   OUT UINT16 Code[]
1459   )
1460 /*++
1461
1462 Routine Description:
1463
1464   Assign code to each symbol based on the code length array
1465
1466 Arguments:
1467
1468   Number     - number of symbols
1469   Len   - the code length array
1470   Code  - stores codes for each symbol
1471
1472 Returns: (VOID)
1473
1474 --*/
1475 {
1476   INT32   Index;
1477   UINT16  Start[18];
1478
1479   Start[1] = 0;
1480   for (Index = 1; Index <= 16; Index++) {
1481     Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);
1482   }
1483
1484   for (Index = 0; Index < Number; Index++) {
1485     Code[Index] = Start[Len[Index]]++;
1486   }
1487 }
1488
1489 STATIC
1490 INT32
1491 MakeTree (
1492   IN  INT32            NParm,
1493   IN  UINT16  FreqParm[],
1494   OUT UINT8   LenParm[ ],
1495   OUT UINT16  CodeParm[]
1496   )
1497 /*++
1498
1499 Routine Description:
1500
1501   Generates Huffman codes given a frequency distribution of symbols
1502
1503 Arguments:
1504
1505   NParm    - number of symbols
1506   FreqParm - frequency of each symbol
1507   LenParm  - code length for each symbol
1508   CodeParm - code for each symbol
1509
1510 Returns:
1511
1512   Root of the Huffman tree.
1513
1514 --*/
1515 {
1516   INT32 Index;
1517   INT32 Index2;
1518   INT32 Index3;
1519   INT32 Avail;
1520
1521   //
1522   // make tree, calculate len[], return root
1523   //
1524   mN        = NParm;
1525   mFreq     = FreqParm;
1526   mLen      = LenParm;
1527   Avail     = mN;
1528   mHeapSize = 0;
1529   mHeap[1]  = 0;
1530   for (Index = 0; Index < mN; Index++) {
1531     mLen[Index] = 0;
1532     if (mFreq[Index]) {
1533       mHeapSize++;
1534       mHeap[mHeapSize] = (INT16) Index;
1535     }
1536   }
1537
1538   if (mHeapSize < 2) {
1539     CodeParm[mHeap[1]] = 0;
1540     return mHeap[1];
1541   }
1542
1543   for (Index = mHeapSize / 2; Index >= 1; Index--) {
1544     //
1545     // make priority queue
1546     //
1547     DownHeap (Index);
1548   }
1549
1550   mSortPtr = CodeParm;
1551   do {
1552     Index = mHeap[1];
1553     if (Index < mN) {
1554       *mSortPtr++ = (UINT16) Index;
1555     }
1556
1557     mHeap[1] = mHeap[mHeapSize--];
1558     DownHeap (1);
1559     Index2 = mHeap[1];
1560     if (Index2 < mN) {
1561       *mSortPtr++ = (UINT16) Index2;
1562     }
1563
1564     Index3        = Avail++;
1565     mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);
1566     mHeap[1]      = (INT16) Index3;
1567     DownHeap (1);
1568     mLeft[Index3]   = (UINT16) Index;
1569     mRight[Index3]  = (UINT16) Index2;
1570   } while (mHeapSize > 1);
1571
1572   mSortPtr = CodeParm;
1573   MakeLen (Index3);
1574   MakeCode (NParm, LenParm, CodeParm);
1575
1576   //
1577   // return root
1578   //
1579   return Index3;
1580 }
1581
1582 EFI_STATUS
1583 GetFileContents (
1584   IN char    *InputFileName,
1585   OUT UINT8   *FileBuffer,
1586   OUT UINT32  *BufferLength
1587   )
1588 /*++
1589
1590 Routine Description:
1591
1592   Get the contents of file specified in InputFileName
1593   into FileBuffer.
1594
1595 Arguments:
1596
1597   InputFileName  - Name of the input file.
1598
1599   FileBuffer     - Output buffer to contain data
1600
1601   BufferLength   - Actual length of the data
1602
1603 Returns:
1604
1605   EFI_SUCCESS on successful return
1606   EFI_ABORTED if unable to open input file.
1607
1608 --*/
1609 {
1610   UINTN   Size;
1611   UINTN   FileSize;
1612   FILE    *InputFile;
1613
1614   Size = 0;
1615   //
1616   // Copy the file contents to the output buffer.
1617   //
1618   InputFile = fopen (LongFilePath (InputFileName), "rb");
1619     if (InputFile == NULL) {
1620       Error (NULL, 0, 0001, "Error opening file: %s", InputFileName);
1621       return EFI_ABORTED;
1622     }
1623
1624   fseek (InputFile, 0, SEEK_END);
1625   FileSize = ftell (InputFile);
1626   fseek (InputFile, 0, SEEK_SET);
1627     //
1628     // Now read the contents of the file into the buffer
1629     //
1630     if (FileSize > 0 && FileBuffer != NULL) {
1631       if (fread (FileBuffer, FileSize, 1, InputFile) != 1) {
1632         Error (NULL, 0, 0004, "Error reading contents of input file: %s", InputFileName);
1633         fclose (InputFile);
1634         return EFI_ABORTED;
1635       }
1636     }
1637
1638   fclose (InputFile);
1639   Size += (UINTN) FileSize;
1640   *BufferLength = Size;
1641
1642   if (FileBuffer != NULL) {
1643     return EFI_SUCCESS;
1644   } else {
1645     return EFI_BUFFER_TOO_SMALL;
1646   }
1647 }
1648
1649 VOID
1650 Version (
1651   VOID
1652   )
1653 /*++
1654
1655 Routine Description:
1656
1657   Displays the standard utility information to SDTOUT
1658
1659 Arguments:
1660
1661   None
1662
1663 Returns:
1664
1665   None
1666
1667 --*/
1668 {
1669   fprintf (stdout, "%s Version %d.%d %s \n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION, __BUILD_VERSION);
1670 }
1671
1672 VOID
1673 Usage (
1674   VOID
1675   )
1676 /*++
1677
1678 Routine Description:
1679
1680   Displays the utility usage syntax to STDOUT
1681
1682 Arguments:
1683
1684   None
1685
1686 Returns:
1687
1688   None
1689
1690 --*/
1691 {
1692   //
1693   // Summary usage
1694   //
1695   fprintf (stdout, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME);
1696
1697   //
1698   // Copyright declaration
1699   //
1700   fprintf (stdout, "Copyright (c) 2007 - 2014, Intel Corporation. All rights reserved.\n\n");
1701
1702   //
1703   // Details Option
1704   //
1705   fprintf (stdout, "Options:\n");
1706   fprintf (stdout, "  -o FileName, --output FileName\n\
1707             File will be created to store the ouput content.\n");
1708   fprintf (stdout, "  -v, --verbose\n\
1709            Turn on verbose output with informational messages.\n");
1710   fprintf (stdout, "  -q, --quiet\n\
1711            Disable all messages except key message and fatal error\n");
1712   fprintf (stdout, "  --debug [0-9]\n\
1713            Enable debug messages, at input debug level.\n");
1714   fprintf (stdout, "  --version\n\
1715            Show program's version number and exit.\n");
1716   fprintf (stdout, "  -h, --help\n\
1717            Show this help message and exit.\n");
1718 }
1719
1720
1721 int
1722 main (
1723   int  argc,
1724   char *argv[]
1725   )
1726 /*++
1727
1728 Routine Description:
1729
1730   Main
1731
1732 Arguments:
1733
1734   command line parameters
1735
1736 Returns:
1737
1738   EFI_SUCCESS    Section header successfully generated and section concatenated.
1739   EFI_ABORTED    Could not generate the section
1740   EFI_OUT_OF_RESOURCES  No resource to complete the operation.
1741
1742 --*/
1743 {
1744   FILE       *OutputFile;
1745   char       *OutputFileName;
1746   char       *InputFileName;
1747   FILE       *InputFile;
1748   EFI_STATUS Status;
1749   UINT8      *FileBuffer;
1750   UINT8      *OutBuffer;
1751   UINT32     InputLength;
1752   UINT32     DstSize;
1753   SCRATCH_DATA      *Scratch;
1754   UINT8      *Src;
1755   UINT32     OrigSize;
1756
1757   SetUtilityName(UTILITY_NAME);
1758
1759   FileBuffer = NULL;
1760   Src = NULL;
1761   OutBuffer = NULL;
1762   Scratch   = NULL;
1763   OrigSize = 0;
1764   InputLength = 0;
1765   InputFileName = NULL;
1766   OutputFileName = NULL;
1767   DstSize=0;
1768   DebugLevel = 0;
1769   DebugMode = FALSE;
1770
1771   //
1772   // Verify the correct number of arguments
1773   //
1774   if (argc == 1) {
1775     Error (NULL, 0, 1001, "Missing options", "No input options specified.");
1776     Usage();
1777     return 0;
1778   }
1779
1780   if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) {
1781     Usage();
1782     return 0;
1783   }
1784
1785   if ((strcmp(argv[1], "--version") == 0)) {
1786     Version();
1787     return 0;
1788   }
1789
1790   argc--;
1791   argv++;
1792   if (strcmp(argv[0],"-e") == 0) {
1793     //
1794     // encode the input file
1795     //
1796     ENCODE = TRUE;
1797     argc--;
1798     argv++;
1799   } else if (strcmp(argv[0], "-d") == 0) {
1800     //
1801     // decode the input file
1802     //
1803     DECODE = TRUE;
1804     argc--;
1805     argv++;
1806   } else {
1807     //
1808     // Error command line
1809     //
1810     Error (NULL, 0, 1003, "Invalid option value", "the options specified are not recognized.");
1811     Usage();
1812     return 1;
1813   }
1814
1815   while (argc > 0) {
1816     if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) {
1817       VerboseMode = TRUE;
1818       argc--;
1819       argv++;
1820       continue;
1821     }
1822
1823     if (stricmp (argv[0], "--debug") == 0) {
1824       argc-=2;
1825       argv++;
1826       Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel);
1827       if (DebugLevel > 9) {
1828         Error (NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]);
1829         goto ERROR;
1830       }
1831       if (DebugLevel>=5 && DebugLevel <=9){
1832         DebugMode = TRUE;
1833       } else {
1834         DebugMode = FALSE;
1835       }
1836       argv++;
1837       continue;
1838     }
1839
1840     if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--quiet") == 0)) {
1841       QuietMode = TRUE;
1842       argc--;
1843       argv++;
1844       continue;
1845     }
1846
1847     if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) {
1848       if (argv[1] == NULL || argv[1][0] == '-') {
1849         Error (NULL, 0, 1003, "Invalid option value", "Output File name is missing for -o option");
1850         goto ERROR;
1851       }
1852       OutputFileName = argv[1];
1853       argc -=2;
1854       argv +=2;
1855       continue;
1856     }
1857
1858     if (argv[0][0]!='-') {
1859       InputFileName = argv[0];
1860       argc--;
1861       argv++;
1862       continue;
1863     }
1864
1865     Error (NULL, 0, 1000, "Unknown option", argv[0]);
1866     goto ERROR;
1867   }
1868
1869   if (InputFileName == NULL) {
1870     Error (NULL, 0, 1001, "Missing options", "No input files specified.");
1871     goto ERROR;
1872   }
1873
1874 //
1875 // All Parameters has been parsed, now set the message print level
1876 //
1877   if (QuietMode) {
1878     SetPrintLevel(40);
1879   } else if (VerboseMode) {
1880     SetPrintLevel(15);
1881   } else if (DebugMode) {
1882     SetPrintLevel(DebugLevel);
1883   }
1884
1885   if (VerboseMode) {
1886     VerboseMsg("%s tool start.\n", UTILITY_NAME);
1887    }
1888   Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA));
1889   if (Scratch == NULL) {
1890     Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1891     goto ERROR;
1892   }
1893
1894   InputFile = fopen (LongFilePath (InputFileName), "rb");
1895   if (InputFile == NULL) {
1896     Error (NULL, 0, 0001, "Error opening input file", InputFileName);
1897     goto ERROR;
1898   }
1899
1900   Status = GetFileContents(
1901             InputFileName,
1902             FileBuffer,
1903             &InputLength);
1904
1905   if (Status == EFI_BUFFER_TOO_SMALL) {
1906     FileBuffer = (UINT8 *) malloc (InputLength);
1907     if (FileBuffer == NULL) {
1908       Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1909       goto ERROR;
1910     }
1911
1912     Status = GetFileContents (
1913               InputFileName,
1914               FileBuffer,
1915               &InputLength
1916               );
1917   }
1918
1919   if (EFI_ERROR(Status)) {
1920     Error (NULL, 0, 0004, "Error getting contents of file: %s", InputFileName);
1921     goto ERROR;
1922   }
1923
1924   if (OutputFileName == NULL) {
1925     OutputFileName = DEFAULT_OUTPUT_FILE;
1926   }
1927   OutputFile = fopen (LongFilePath (OutputFileName), "wb");
1928   if (OutputFile == NULL) {
1929     Error (NULL, 0, 0001, "Error opening output file for writing", OutputFileName);
1930     if (InputFile != NULL) {
1931       fclose (InputFile);
1932     }
1933     goto ERROR;
1934   }
1935
1936   if (ENCODE) {
1937   //
1938   // First call TianoCompress to get DstSize
1939   //
1940   if (DebugMode) {
1941     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding", NULL);
1942   }
1943   Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
1944
1945   if (Status == EFI_BUFFER_TOO_SMALL) {
1946     OutBuffer = (UINT8 *) malloc (DstSize);
1947     if (OutBuffer == NULL) {
1948       Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1949       goto ERROR;
1950     }
1951   }
1952
1953   Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
1954   if (Status != EFI_SUCCESS) {
1955     Error (NULL, 0, 0007, "Error compressing file", NULL);
1956     goto ERROR;
1957   }
1958
1959   if (OutBuffer == NULL) {
1960     Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1961     goto ERROR;
1962   }
1963
1964   fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile);
1965   free(Scratch);
1966   free(FileBuffer);
1967   free(OutBuffer);
1968
1969   if (DebugMode) {
1970     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Successful!\n", NULL);
1971   }
1972   if (VerboseMode) {
1973     VerboseMsg("Encoding successful\n");
1974   }
1975   return 0;
1976   }
1977   else if (DECODE) {
1978   if (DebugMode) {
1979     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding\n", NULL);
1980   }
1981   //
1982   // Get Compressed file original size
1983   //
1984   Src     = (UINT8 *)FileBuffer;
1985   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
1986
1987   //
1988   // Allocate OutputBuffer
1989   //
1990   OutBuffer = (UINT8 *)malloc(OrigSize);
1991   if (OutBuffer == NULL) {
1992     Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1993     goto ERROR;
1994    }
1995
1996   Status = Decompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2);
1997   if (Status != EFI_SUCCESS) {
1998    goto ERROR;
1999   }
2000
2001   fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile);
2002   free(Scratch);
2003   free(FileBuffer);
2004   free(OutBuffer);
2005
2006   if (DebugMode) {
2007     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding successful!\n", NULL);
2008   }
2009
2010   if (VerboseMode) {
2011     VerboseMsg("Decoding successful\n");
2012   }
2013   return 0;
2014   }
2015
2016 ERROR:
2017   if (DebugMode) {
2018     if (ENCODE) {
2019       DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Error\n", NULL);
2020     } else if (DECODE) {
2021       DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding Error\n", NULL);
2022     }
2023   }
2024   if (Scratch != NULL) {
2025     free(Scratch);
2026   }
2027   if (FileBuffer != NULL) {
2028     free(FileBuffer);
2029   }
2030   if (OutBuffer != NULL) {
2031     free(OutBuffer);
2032   }
2033
2034   if (VerboseMode) {
2035     VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ());
2036   }
2037   return GetUtilityStatus ();
2038 }
2039
2040 VOID
2041 FillBuf (
2042   IN  SCRATCH_DATA  *Sd,
2043   IN  UINT16        NumOfBits
2044   )
2045 /*++
2046
2047 Routine Description:
2048
2049   Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
2050
2051 Arguments:
2052
2053   Sd        - The global scratch data
2054   NumOfBits  - The number of bits to shift and read.
2055
2056 Returns: (VOID)
2057
2058 --*/
2059 {
2060   Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);
2061
2062   while (NumOfBits > Sd->mBitCount) {
2063
2064     Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));
2065
2066     if (Sd->mCompSize > 0) {
2067       //
2068       // Get 1 byte into SubBitBuf
2069       //
2070       Sd->mCompSize--;
2071       Sd->mSubBitBuf  = 0;
2072       Sd->mSubBitBuf  = Sd->mSrcBase[Sd->mInBuf++];
2073       Sd->mBitCount   = 8;
2074
2075     } else {
2076       //
2077       // No more bits from the source, just pad zero bit.
2078       //
2079       Sd->mSubBitBuf  = 0;
2080       Sd->mBitCount   = 8;
2081
2082     }
2083   }
2084
2085   Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);
2086   Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;
2087 }
2088
2089 UINT32
2090 GetBits (
2091   IN  SCRATCH_DATA  *Sd,
2092   IN  UINT16        NumOfBits
2093   )
2094 /*++
2095
2096 Routine Description:
2097
2098   Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
2099   NumOfBits of bits from source. Returns NumOfBits of bits that are
2100   popped out.
2101
2102 Arguments:
2103
2104   Sd            - The global scratch data.
2105   NumOfBits     - The number of bits to pop and read.
2106
2107 Returns:
2108
2109   The bits that are popped out.
2110
2111 --*/
2112 {
2113   UINT32  OutBits;
2114
2115   OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
2116
2117   FillBuf (Sd, NumOfBits);
2118
2119   return OutBits;
2120 }
2121
2122 UINT16
2123 MakeTable (
2124   IN  SCRATCH_DATA  *Sd,
2125   IN  UINT16        NumOfChar,
2126   IN  UINT8         *BitLen,
2127   IN  UINT16        TableBits,
2128   OUT UINT16        *Table
2129   )
2130 /*++
2131
2132 Routine Description:
2133
2134   Creates Huffman Code mapping table according to code length array.
2135
2136 Arguments:
2137
2138   Sd        - The global scratch data
2139   NumOfChar - Number of symbols in the symbol set
2140   BitLen    - Code length array
2141   TableBits - The width of the mapping table
2142   Table     - The table
2143
2144 Returns:
2145
2146   0         - OK.
2147   BAD_TABLE - The table is corrupted.
2148
2149 --*/
2150 {
2151   UINT16  Count[17];
2152   UINT16  Weight[17];
2153   UINT16  Start[18];
2154   UINT16  *Pointer;
2155   UINT16  Index3;
2156   UINT16  Index;
2157   UINT16  Len;
2158   UINT16  Char;
2159   UINT16  JuBits;
2160   UINT16  Avail;
2161   UINT16  NextCode;
2162   UINT16  Mask;
2163   UINT16  WordOfStart;
2164   UINT16  WordOfCount;
2165
2166   for (Index = 0; Index <= 16; Index++) {
2167     Count[Index] = 0;
2168   }
2169
2170   for (Index = 0; Index < NumOfChar; Index++) {
2171     Count[BitLen[Index]]++;
2172   }
2173
2174   Start[0] = 0;
2175   Start[1] = 0;
2176
2177   for (Index = 1; Index <= 16; Index++) {
2178     WordOfStart = Start[Index];
2179     WordOfCount = Count[Index];
2180     Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));
2181   }
2182
2183   if (Start[17] != 0) {
2184     //
2185     //(1U << 16)
2186     //
2187     return (UINT16) BAD_TABLE;
2188   }
2189
2190   JuBits = (UINT16) (16 - TableBits);
2191
2192   Weight[0] = 0;
2193   for (Index = 1; Index <= TableBits; Index++) {
2194     Start[Index] >>= JuBits;
2195     Weight[Index] = (UINT16) (1U << (TableBits - Index));
2196   }
2197
2198   while (Index <= 16) {
2199     Weight[Index] = (UINT16) (1U << (16 - Index));
2200     Index++;
2201   }
2202
2203   Index = (UINT16) (Start[TableBits + 1] >> JuBits);
2204
2205   if (Index != 0) {
2206     Index3 = (UINT16) (1U << TableBits);
2207     while (Index != Index3) {
2208       Table[Index++] = 0;
2209     }
2210   }
2211
2212   Avail = NumOfChar;
2213   Mask  = (UINT16) (1U << (15 - TableBits));
2214
2215   for (Char = 0; Char < NumOfChar; Char++) {
2216
2217     Len = BitLen[Char];
2218     if (Len == 0 || Len >= 17) {
2219       continue;
2220     }
2221
2222     NextCode = (UINT16) (Start[Len] + Weight[Len]);
2223
2224     if (Len <= TableBits) {
2225
2226       for (Index = Start[Len]; Index < NextCode; Index++) {
2227         Table[Index] = Char;
2228       }
2229
2230     } else {
2231
2232       Index3  = Start[Len];
2233       Pointer = &Table[Index3 >> JuBits];
2234       Index   = (UINT16) (Len - TableBits);
2235
2236       while (Index != 0) {
2237         if (*Pointer == 0) {
2238           Sd->mRight[Avail]                     = Sd->mLeft[Avail] = 0;
2239           *Pointer = Avail++;
2240         }
2241
2242         if (Index3 & Mask) {
2243           Pointer = &Sd->mRight[*Pointer];
2244         } else {
2245           Pointer = &Sd->mLeft[*Pointer];
2246         }
2247
2248         Index3 <<= 1;
2249         Index--;
2250       }
2251
2252       *Pointer = Char;
2253
2254     }
2255
2256     Start[Len] = NextCode;
2257   }
2258   //
2259   // Succeeds
2260   //
2261   return 0;
2262 }
2263
2264 UINT32
2265 DecodeP (
2266   IN  SCRATCH_DATA  *Sd
2267   )
2268 /*++
2269
2270 Routine Description:
2271
2272   Decodes a position value.
2273
2274 Arguments:
2275
2276   Sd      - the global scratch data
2277
2278 Returns:
2279
2280   The position value decoded.
2281
2282 --*/
2283 {
2284   UINT16  Val;
2285   UINT32  Mask;
2286   UINT32  Pos;
2287
2288   Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
2289
2290   if (Val >= MAXNP) {
2291     Mask = 1U << (BITBUFSIZ - 1 - 8);
2292
2293     do {
2294
2295       if (Sd->mBitBuf & Mask) {
2296         Val = Sd->mRight[Val];
2297       } else {
2298         Val = Sd->mLeft[Val];
2299       }
2300
2301       Mask >>= 1;
2302     } while (Val >= MAXNP);
2303   }
2304   //
2305   // Advance what we have read
2306   //
2307   FillBuf (Sd, Sd->mPTLen[Val]);
2308
2309   Pos = Val;
2310   if (Val > 1) {
2311     Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
2312   }
2313
2314   return Pos;
2315 }
2316
2317 UINT16
2318 ReadPTLen (
2319   IN  SCRATCH_DATA  *Sd,
2320   IN  UINT16        nn,
2321   IN  UINT16        nbit,
2322   IN  UINT16        Special
2323   )
2324 /*++
2325
2326 Routine Description:
2327
2328   Reads code lengths for the Extra Set or the Position Set
2329
2330 Arguments:
2331
2332   Sd        - The global scratch data
2333   nn        - Number of symbols
2334   nbit      - Number of bits needed to represent nn
2335   Special   - The special symbol that needs to be taken care of
2336
2337 Returns:
2338
2339   0         - OK.
2340   BAD_TABLE - Table is corrupted.
2341
2342 --*/
2343 {
2344   UINT16  Number;
2345   UINT16  CharC;
2346   volatile UINT16  Index;
2347   UINT32  Mask;
2348
2349   assert (nn <= NPT);
2350
2351   Number = (UINT16) GetBits (Sd, nbit);
2352
2353   if (Number == 0) {
2354     CharC = (UINT16) GetBits (Sd, nbit);
2355
2356     for (Index = 0; Index < 256; Index++) {
2357       Sd->mPTTable[Index] = CharC;
2358     }
2359
2360     for (Index = 0; Index < nn; Index++) {
2361       Sd->mPTLen[Index] = 0;
2362     }
2363
2364     return 0;
2365   }
2366
2367   Index = 0;
2368
2369   while (Index < Number) {
2370
2371     CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
2372
2373     if (CharC == 7) {
2374       Mask = 1U << (BITBUFSIZ - 1 - 3);
2375       while (Mask & Sd->mBitBuf) {
2376         Mask >>= 1;
2377         CharC += 1;
2378       }
2379     }
2380
2381     FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
2382
2383     Sd->mPTLen[Index++] = (UINT8) CharC;
2384
2385     if (Index == Special) {
2386       CharC = (UINT16) GetBits (Sd, 2);
2387       while ((INT16) (--CharC) >= 0) {
2388         Sd->mPTLen[Index++] = 0;
2389       }
2390     }
2391   }
2392
2393   while (Index < nn) {
2394     Sd->mPTLen[Index++] = 0;
2395   }
2396
2397   return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
2398 }
2399
2400 VOID
2401 ReadCLen (
2402   SCRATCH_DATA  *Sd
2403   )
2404 /*++
2405
2406 Routine Description:
2407
2408   Reads code lengths for Char&Len Set.
2409
2410 Arguments:
2411
2412   Sd    - the global scratch data
2413
2414 Returns: (VOID)
2415
2416 --*/
2417 {
2418   UINT16  Number;
2419   UINT16  CharC;
2420   volatile UINT16  Index;
2421   UINT32  Mask;
2422
2423   Number = (UINT16) GetBits (Sd, CBIT);
2424
2425   if (Number == 0) {
2426     CharC = (UINT16) GetBits (Sd, CBIT);
2427
2428     for (Index = 0; Index < NC; Index++) {
2429       Sd->mCLen[Index] = 0;
2430     }
2431
2432     for (Index = 0; Index < 4096; Index++) {
2433       Sd->mCTable[Index] = CharC;
2434     }
2435
2436     return ;
2437   }
2438
2439   Index = 0;
2440   while (Index < Number) {
2441
2442     CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
2443     if (CharC >= NT) {
2444       Mask = 1U << (BITBUFSIZ - 1 - 8);
2445
2446       do {
2447
2448         if (Mask & Sd->mBitBuf) {
2449           CharC = Sd->mRight[CharC];
2450         } else {
2451           CharC = Sd->mLeft[CharC];
2452         }
2453
2454         Mask >>= 1;
2455
2456       } while (CharC >= NT);
2457     }
2458     //
2459     // Advance what we have read
2460     //
2461     FillBuf (Sd, Sd->mPTLen[CharC]);
2462
2463     if (CharC <= 2) {
2464
2465       if (CharC == 0) {
2466         CharC = 1;
2467       } else if (CharC == 1) {
2468         CharC = (UINT16) (GetBits (Sd, 4) + 3);
2469       } else if (CharC == 2) {
2470         CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
2471       }
2472
2473       while ((INT16) (--CharC) >= 0) {
2474         Sd->mCLen[Index++] = 0;
2475       }
2476
2477     } else {
2478
2479       Sd->mCLen[Index++] = (UINT8) (CharC - 2);
2480
2481     }
2482   }
2483
2484   while (Index < NC) {
2485     Sd->mCLen[Index++] = 0;
2486   }
2487
2488   MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
2489
2490   return ;
2491 }
2492
2493 UINT16
2494 DecodeC (
2495   SCRATCH_DATA  *Sd
2496   )
2497 /*++
2498
2499 Routine Description:
2500
2501   Decode a character/length value.
2502
2503 Arguments:
2504
2505   Sd    - The global scratch data.
2506
2507 Returns:
2508
2509   The value decoded.
2510
2511 --*/
2512 {
2513   UINT16  Index2;
2514   UINT32  Mask;
2515
2516   if (Sd->mBlockSize == 0) {
2517     //
2518     // Starting a new block
2519     //
2520     Sd->mBlockSize    = (UINT16) GetBits (Sd, 16);
2521     Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
2522     if (Sd->mBadTableFlag != 0) {
2523       return 0;
2524     }
2525
2526     ReadCLen (Sd);
2527
2528     Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
2529     if (Sd->mBadTableFlag != 0) {
2530       return 0;
2531     }
2532   }
2533
2534   Sd->mBlockSize--;
2535   Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
2536
2537   if (Index2 >= NC) {
2538     Mask = 1U << (BITBUFSIZ - 1 - 12);
2539
2540     do {
2541       if (Sd->mBitBuf & Mask) {
2542         Index2 = Sd->mRight[Index2];
2543       } else {
2544         Index2 = Sd->mLeft[Index2];
2545       }
2546
2547       Mask >>= 1;
2548     } while (Index2 >= NC);
2549   }
2550   //
2551   // Advance what we have read
2552   //
2553   FillBuf (Sd, Sd->mCLen[Index2]);
2554
2555   return Index2;
2556 }
2557
2558 VOID
2559 Decode (
2560   SCRATCH_DATA  *Sd
2561   )
2562 /*++
2563
2564 Routine Description:
2565
2566   Decode the source data and put the resulting data into the destination buffer.
2567
2568 Arguments:
2569
2570   Sd            - The global scratch data
2571
2572 Returns: (VOID)
2573
2574  --*/
2575 {
2576   UINT16  BytesRemain;
2577   UINT32  DataIdx;
2578   UINT16  CharC;
2579
2580   BytesRemain = (UINT16) (-1);
2581
2582   DataIdx     = 0;
2583
2584   for (;;) {
2585     CharC = DecodeC (Sd);
2586     if (Sd->mBadTableFlag != 0) {
2587       goto Done ;
2588     }
2589
2590     if (CharC < 256) {
2591       //
2592       // Process an Original character
2593       //
2594       if (Sd->mOutBuf >= Sd->mOrigSize) {
2595         goto Done ;
2596       } else {
2597         Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
2598       }
2599
2600     } else {
2601       //
2602       // Process a Pointer
2603       //
2604       CharC       = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));
2605
2606       BytesRemain = CharC;
2607
2608       DataIdx     = Sd->mOutBuf - DecodeP (Sd) - 1;
2609
2610       BytesRemain--;
2611       while ((INT16) (BytesRemain) >= 0) {
2612         Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
2613         if (Sd->mOutBuf >= Sd->mOrigSize) {
2614           goto Done ;
2615         }
2616
2617         BytesRemain--;
2618       }
2619     }
2620   }
2621
2622 Done:
2623   return ;
2624 }
2625
2626 RETURN_STATUS
2627 EFIAPI
2628 Decompress (
2629   IN VOID  *Source,
2630   IN OUT VOID    *Destination,
2631   IN OUT VOID    *Scratch,
2632   IN UINT32      Version
2633   )
2634 /*++
2635
2636 Routine Description:
2637
2638   The internal implementation of Decompress().
2639
2640 Arguments:
2641
2642   Source          - The source buffer containing the compressed data.
2643   Destination     - The destination buffer to store the decompressed data
2644   Scratch         - The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.
2645   Version         - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm
2646
2647 Returns:
2648
2649   RETURN_SUCCESS           - Decompression is successfull
2650   RETURN_INVALID_PARAMETER - The source data is corrupted
2651
2652 --*/
2653 {
2654   volatile UINT32  Index;
2655   UINT32           CompSize;
2656   UINT32           OrigSize;
2657   SCRATCH_DATA     *Sd;
2658   CONST UINT8      *Src;
2659   UINT8            *Dst;
2660
2661   //
2662   // Verify input is not NULL
2663   //
2664   assert(Source);
2665 //  assert(Destination);
2666   assert(Scratch);
2667
2668   Src     = (UINT8 *)Source;
2669   Dst     = (UINT8 *)Destination;
2670
2671   Sd      = (SCRATCH_DATA *) Scratch;
2672   CompSize  = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
2673   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
2674
2675   //
2676   // If compressed file size is 0, return
2677   //
2678   if (OrigSize == 0) {
2679     return RETURN_SUCCESS;
2680   }
2681
2682   Src = Src + 8;
2683
2684   for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
2685     ((UINT8 *) Sd)[Index] = 0;
2686   }
2687   //
2688   // The length of the field 'Position Set Code Length Array Size' in Block Header.
2689   // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
2690   // For Tiano de/compression algorithm(Version 2), mPBit = 5
2691   //
2692   switch (Version) {
2693     case 1 :
2694       Sd->mPBit = 4;
2695       break;
2696     case 2 :
2697       Sd->mPBit = 5;
2698       break;
2699     default:
2700       assert(FALSE);
2701   }
2702   Sd->mSrcBase  = (UINT8 *)Src;
2703   Sd->mDstBase  = Dst;
2704   Sd->mCompSize = CompSize;
2705   Sd->mOrigSize = OrigSize;
2706
2707   //
2708   // Fill the first BITBUFSIZ bits
2709   //
2710   FillBuf (Sd, BITBUFSIZ);
2711
2712   //
2713   // Decompress it
2714   //
2715
2716   Decode (Sd);
2717
2718   if (Sd->mBadTableFlag != 0) {
2719     //
2720     // Something wrong with the source
2721     //
2722     return RETURN_INVALID_PARAMETER;
2723   }
2724
2725   return RETURN_SUCCESS;
2726 }
2727
2728