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   InputFile = NULL;
1768   OutputFile = NULL;
1769   DstSize=0;
1770   DebugLevel = 0;
1771   DebugMode = FALSE;
1772
1773   //
1774   // Verify the correct number of arguments
1775   //
1776   if (argc == 1) {
1777     Error (NULL, 0, 1001, "Missing options", "No input options specified.");
1778     Usage();
1779     return 0;
1780   }
1781
1782   if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) {
1783     Usage();
1784     return 0;
1785   }
1786
1787   if ((strcmp(argv[1], "--version") == 0)) {
1788     Version();
1789     return 0;
1790   }
1791
1792   argc--;
1793   argv++;
1794   if (strcmp(argv[0],"-e") == 0) {
1795     //
1796     // encode the input file
1797     //
1798     ENCODE = TRUE;
1799     argc--;
1800     argv++;
1801   } else if (strcmp(argv[0], "-d") == 0) {
1802     //
1803     // decode the input file
1804     //
1805     DECODE = TRUE;
1806     argc--;
1807     argv++;
1808   } else {
1809     //
1810     // Error command line
1811     //
1812     Error (NULL, 0, 1003, "Invalid option value", "the options specified are not recognized.");
1813     Usage();
1814     return 1;
1815   }
1816
1817   while (argc > 0) {
1818     if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) {
1819       VerboseMode = TRUE;
1820       argc--;
1821       argv++;
1822       continue;
1823     }
1824
1825     if (stricmp (argv[0], "--debug") == 0) {
1826       argc-=2;
1827       argv++;
1828       Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel);
1829       if (DebugLevel > 9) {
1830         Error (NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]);
1831         goto ERROR;
1832       }
1833       if (DebugLevel>=5 && DebugLevel <=9){
1834         DebugMode = TRUE;
1835       } else {
1836         DebugMode = FALSE;
1837       }
1838       argv++;
1839       continue;
1840     }
1841
1842     if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--quiet") == 0)) {
1843       QuietMode = TRUE;
1844       argc--;
1845       argv++;
1846       continue;
1847     }
1848
1849     if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) {
1850       if (argv[1] == NULL || argv[1][0] == '-') {
1851         Error (NULL, 0, 1003, "Invalid option value", "Output File name is missing for -o option");
1852         goto ERROR;
1853       }
1854       OutputFileName = argv[1];
1855       argc -=2;
1856       argv +=2;
1857       continue;
1858     }
1859
1860     if (argv[0][0]!='-') {
1861       InputFileName = argv[0];
1862       argc--;
1863       argv++;
1864       continue;
1865     }
1866
1867     Error (NULL, 0, 1000, "Unknown option", argv[0]);
1868     goto ERROR;
1869   }
1870
1871   if (InputFileName == NULL) {
1872     Error (NULL, 0, 1001, "Missing options", "No input files specified.");
1873     goto ERROR;
1874   }
1875
1876 //
1877 // All Parameters has been parsed, now set the message print level
1878 //
1879   if (QuietMode) {
1880     SetPrintLevel(40);
1881   } else if (VerboseMode) {
1882     SetPrintLevel(15);
1883   } else if (DebugMode) {
1884     SetPrintLevel(DebugLevel);
1885   }
1886
1887   if (VerboseMode) {
1888     VerboseMsg("%s tool start.\n", UTILITY_NAME);
1889    }
1890   Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA));
1891   if (Scratch == NULL) {
1892     Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1893     goto ERROR;
1894   }
1895
1896   InputFile = fopen (LongFilePath (InputFileName), "rb");
1897   if (InputFile == NULL) {
1898     Error (NULL, 0, 0001, "Error opening input file", InputFileName);
1899     goto ERROR;
1900   }
1901
1902   Status = GetFileContents(
1903             InputFileName,
1904             FileBuffer,
1905             &InputLength);
1906
1907   if (Status == EFI_BUFFER_TOO_SMALL) {
1908     FileBuffer = (UINT8 *) malloc (InputLength);
1909     if (FileBuffer == NULL) {
1910       Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1911       goto ERROR;
1912     }
1913
1914     Status = GetFileContents (
1915               InputFileName,
1916               FileBuffer,
1917               &InputLength
1918               );
1919   }
1920
1921   if (EFI_ERROR(Status)) {
1922     Error (NULL, 0, 0004, "Error getting contents of file: %s", InputFileName);
1923     goto ERROR;
1924   }
1925
1926   if (OutputFileName == NULL) {
1927     OutputFileName = DEFAULT_OUTPUT_FILE;
1928   }
1929   OutputFile = fopen (LongFilePath (OutputFileName), "wb");
1930   if (OutputFile == NULL) {
1931     Error (NULL, 0, 0001, "Error opening output file for writing", OutputFileName);
1932     goto ERROR;
1933   }
1934
1935   if (ENCODE) {
1936   //
1937   // First call TianoCompress to get DstSize
1938   //
1939   if (DebugMode) {
1940     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding", NULL);
1941   }
1942   Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
1943
1944   if (Status == EFI_BUFFER_TOO_SMALL) {
1945     OutBuffer = (UINT8 *) malloc (DstSize);
1946     if (OutBuffer == NULL) {
1947       Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1948       goto ERROR;
1949     }
1950   }
1951
1952   Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
1953   if (Status != EFI_SUCCESS) {
1954     Error (NULL, 0, 0007, "Error compressing file", NULL);
1955     goto ERROR;
1956   }
1957
1958   if (OutBuffer == NULL) {
1959     Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1960     goto ERROR;
1961   }
1962
1963   fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile);
1964   fclose(OutputFile);
1965   fclose(InputFile);
1966   free(Scratch);
1967   free(FileBuffer);
1968   free(OutBuffer);
1969
1970   if (DebugMode) {
1971     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Successful!\n", NULL);
1972   }
1973   if (VerboseMode) {
1974     VerboseMsg("Encoding successful\n");
1975   }
1976   return 0;
1977   }
1978   else if (DECODE) {
1979   if (DebugMode) {
1980     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding\n", NULL);
1981   }
1982   //
1983   // Get Compressed file original size
1984   //
1985   Src     = (UINT8 *)FileBuffer;
1986   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
1987
1988   //
1989   // Allocate OutputBuffer
1990   //
1991   OutBuffer = (UINT8 *)malloc(OrigSize);
1992   if (OutBuffer == NULL) {
1993     Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
1994     goto ERROR;
1995    }
1996
1997   Status = Decompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2);
1998   if (Status != EFI_SUCCESS) {
1999    goto ERROR;
2000   }
2001
2002   fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile);
2003   fclose(OutputFile);
2004   fclose(InputFile);
2005   free(Scratch);
2006   free(FileBuffer);
2007   free(OutBuffer);
2008
2009   if (DebugMode) {
2010     DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding successful!\n", NULL);
2011   }
2012
2013   if (VerboseMode) {
2014     VerboseMsg("Decoding successful\n");
2015   }
2016   return 0;
2017   }
2018
2019 ERROR:
2020   if (DebugMode) {
2021     if (ENCODE) {
2022       DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Error\n", NULL);
2023     } else if (DECODE) {
2024       DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding Error\n", NULL);
2025     }
2026   }
2027   if (OutputFile != NULL) {
2028     fclose(OutputFile);
2029   }
2030   if (InputFile != NULL) {
2031     fclose (InputFile);
2032   }
2033   if (Scratch != NULL) {
2034     free(Scratch);
2035   }
2036   if (FileBuffer != NULL) {
2037     free(FileBuffer);
2038   }
2039   if (OutBuffer != NULL) {
2040     free(OutBuffer);
2041   }
2042
2043   if (VerboseMode) {
2044     VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ());
2045   }
2046   return GetUtilityStatus ();
2047 }
2048
2049 VOID
2050 FillBuf (
2051   IN  SCRATCH_DATA  *Sd,
2052   IN  UINT16        NumOfBits
2053   )
2054 /*++
2055
2056 Routine Description:
2057
2058   Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
2059
2060 Arguments:
2061
2062   Sd        - The global scratch data
2063   NumOfBits  - The number of bits to shift and read.
2064
2065 Returns: (VOID)
2066
2067 --*/
2068 {
2069   Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);
2070
2071   while (NumOfBits > Sd->mBitCount) {
2072
2073     Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));
2074
2075     if (Sd->mCompSize > 0) {
2076       //
2077       // Get 1 byte into SubBitBuf
2078       //
2079       Sd->mCompSize--;
2080       Sd->mSubBitBuf  = 0;
2081       Sd->mSubBitBuf  = Sd->mSrcBase[Sd->mInBuf++];
2082       Sd->mBitCount   = 8;
2083
2084     } else {
2085       //
2086       // No more bits from the source, just pad zero bit.
2087       //
2088       Sd->mSubBitBuf  = 0;
2089       Sd->mBitCount   = 8;
2090
2091     }
2092   }
2093
2094   Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);
2095   Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;
2096 }
2097
2098 UINT32
2099 GetBits (
2100   IN  SCRATCH_DATA  *Sd,
2101   IN  UINT16        NumOfBits
2102   )
2103 /*++
2104
2105 Routine Description:
2106
2107   Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
2108   NumOfBits of bits from source. Returns NumOfBits of bits that are
2109   popped out.
2110
2111 Arguments:
2112
2113   Sd            - The global scratch data.
2114   NumOfBits     - The number of bits to pop and read.
2115
2116 Returns:
2117
2118   The bits that are popped out.
2119
2120 --*/
2121 {
2122   UINT32  OutBits;
2123
2124   OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
2125
2126   FillBuf (Sd, NumOfBits);
2127
2128   return OutBits;
2129 }
2130
2131 UINT16
2132 MakeTable (
2133   IN  SCRATCH_DATA  *Sd,
2134   IN  UINT16        NumOfChar,
2135   IN  UINT8         *BitLen,
2136   IN  UINT16        TableBits,
2137   OUT UINT16        *Table
2138   )
2139 /*++
2140
2141 Routine Description:
2142
2143   Creates Huffman Code mapping table according to code length array.
2144
2145 Arguments:
2146
2147   Sd        - The global scratch data
2148   NumOfChar - Number of symbols in the symbol set
2149   BitLen    - Code length array
2150   TableBits - The width of the mapping table
2151   Table     - The table
2152
2153 Returns:
2154
2155   0         - OK.
2156   BAD_TABLE - The table is corrupted.
2157
2158 --*/
2159 {
2160   UINT16  Count[17];
2161   UINT16  Weight[17];
2162   UINT16  Start[18];
2163   UINT16  *Pointer;
2164   UINT16  Index3;
2165   UINT16  Index;
2166   UINT16  Len;
2167   UINT16  Char;
2168   UINT16  JuBits;
2169   UINT16  Avail;
2170   UINT16  NextCode;
2171   UINT16  Mask;
2172   UINT16  WordOfStart;
2173   UINT16  WordOfCount;
2174
2175   for (Index = 0; Index <= 16; Index++) {
2176     Count[Index] = 0;
2177   }
2178
2179   for (Index = 0; Index < NumOfChar; Index++) {
2180     Count[BitLen[Index]]++;
2181   }
2182
2183   Start[0] = 0;
2184   Start[1] = 0;
2185
2186   for (Index = 1; Index <= 16; Index++) {
2187     WordOfStart = Start[Index];
2188     WordOfCount = Count[Index];
2189     Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));
2190   }
2191
2192   if (Start[17] != 0) {
2193     //
2194     //(1U << 16)
2195     //
2196     return (UINT16) BAD_TABLE;
2197   }
2198
2199   JuBits = (UINT16) (16 - TableBits);
2200
2201   Weight[0] = 0;
2202   for (Index = 1; Index <= TableBits; Index++) {
2203     Start[Index] >>= JuBits;
2204     Weight[Index] = (UINT16) (1U << (TableBits - Index));
2205   }
2206
2207   while (Index <= 16) {
2208     Weight[Index] = (UINT16) (1U << (16 - Index));
2209     Index++;
2210   }
2211
2212   Index = (UINT16) (Start[TableBits + 1] >> JuBits);
2213
2214   if (Index != 0) {
2215     Index3 = (UINT16) (1U << TableBits);
2216     while (Index != Index3) {
2217       Table[Index++] = 0;
2218     }
2219   }
2220
2221   Avail = NumOfChar;
2222   Mask  = (UINT16) (1U << (15 - TableBits));
2223
2224   for (Char = 0; Char < NumOfChar; Char++) {
2225
2226     Len = BitLen[Char];
2227     if (Len == 0 || Len >= 17) {
2228       continue;
2229     }
2230
2231     NextCode = (UINT16) (Start[Len] + Weight[Len]);
2232
2233     if (Len <= TableBits) {
2234
2235       for (Index = Start[Len]; Index < NextCode; Index++) {
2236         Table[Index] = Char;
2237       }
2238
2239     } else {
2240
2241       Index3  = Start[Len];
2242       Pointer = &Table[Index3 >> JuBits];
2243       Index   = (UINT16) (Len - TableBits);
2244
2245       while (Index != 0) {
2246         if (*Pointer == 0) {
2247           Sd->mRight[Avail]                     = Sd->mLeft[Avail] = 0;
2248           *Pointer = Avail++;
2249         }
2250
2251         if (Index3 & Mask) {
2252           Pointer = &Sd->mRight[*Pointer];
2253         } else {
2254           Pointer = &Sd->mLeft[*Pointer];
2255         }
2256
2257         Index3 <<= 1;
2258         Index--;
2259       }
2260
2261       *Pointer = Char;
2262
2263     }
2264
2265     Start[Len] = NextCode;
2266   }
2267   //
2268   // Succeeds
2269   //
2270   return 0;
2271 }
2272
2273 UINT32
2274 DecodeP (
2275   IN  SCRATCH_DATA  *Sd
2276   )
2277 /*++
2278
2279 Routine Description:
2280
2281   Decodes a position value.
2282
2283 Arguments:
2284
2285   Sd      - the global scratch data
2286
2287 Returns:
2288
2289   The position value decoded.
2290
2291 --*/
2292 {
2293   UINT16  Val;
2294   UINT32  Mask;
2295   UINT32  Pos;
2296
2297   Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
2298
2299   if (Val >= MAXNP) {
2300     Mask = 1U << (BITBUFSIZ - 1 - 8);
2301
2302     do {
2303
2304       if (Sd->mBitBuf & Mask) {
2305         Val = Sd->mRight[Val];
2306       } else {
2307         Val = Sd->mLeft[Val];
2308       }
2309
2310       Mask >>= 1;
2311     } while (Val >= MAXNP);
2312   }
2313   //
2314   // Advance what we have read
2315   //
2316   FillBuf (Sd, Sd->mPTLen[Val]);
2317
2318   Pos = Val;
2319   if (Val > 1) {
2320     Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
2321   }
2322
2323   return Pos;
2324 }
2325
2326 UINT16
2327 ReadPTLen (
2328   IN  SCRATCH_DATA  *Sd,
2329   IN  UINT16        nn,
2330   IN  UINT16        nbit,
2331   IN  UINT16        Special
2332   )
2333 /*++
2334
2335 Routine Description:
2336
2337   Reads code lengths for the Extra Set or the Position Set
2338
2339 Arguments:
2340
2341   Sd        - The global scratch data
2342   nn        - Number of symbols
2343   nbit      - Number of bits needed to represent nn
2344   Special   - The special symbol that needs to be taken care of
2345
2346 Returns:
2347
2348   0         - OK.
2349   BAD_TABLE - Table is corrupted.
2350
2351 --*/
2352 {
2353   UINT16  Number;
2354   UINT16  CharC;
2355   volatile UINT16  Index;
2356   UINT32  Mask;
2357
2358   assert (nn <= NPT);
2359
2360   Number = (UINT16) GetBits (Sd, nbit);
2361
2362   if (Number == 0) {
2363     CharC = (UINT16) GetBits (Sd, nbit);
2364
2365     for (Index = 0; Index < 256; Index++) {
2366       Sd->mPTTable[Index] = CharC;
2367     }
2368
2369     for (Index = 0; Index < nn; Index++) {
2370       Sd->mPTLen[Index] = 0;
2371     }
2372
2373     return 0;
2374   }
2375
2376   Index = 0;
2377
2378   while (Index < Number) {
2379
2380     CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
2381
2382     if (CharC == 7) {
2383       Mask = 1U << (BITBUFSIZ - 1 - 3);
2384       while (Mask & Sd->mBitBuf) {
2385         Mask >>= 1;
2386         CharC += 1;
2387       }
2388     }
2389
2390     FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
2391
2392     Sd->mPTLen[Index++] = (UINT8) CharC;
2393
2394     if (Index == Special) {
2395       CharC = (UINT16) GetBits (Sd, 2);
2396       while ((INT16) (--CharC) >= 0) {
2397         Sd->mPTLen[Index++] = 0;
2398       }
2399     }
2400   }
2401
2402   while (Index < nn) {
2403     Sd->mPTLen[Index++] = 0;
2404   }
2405
2406   return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
2407 }
2408
2409 VOID
2410 ReadCLen (
2411   SCRATCH_DATA  *Sd
2412   )
2413 /*++
2414
2415 Routine Description:
2416
2417   Reads code lengths for Char&Len Set.
2418
2419 Arguments:
2420
2421   Sd    - the global scratch data
2422
2423 Returns: (VOID)
2424
2425 --*/
2426 {
2427   UINT16  Number;
2428   UINT16  CharC;
2429   volatile UINT16  Index;
2430   UINT32  Mask;
2431
2432   Number = (UINT16) GetBits (Sd, CBIT);
2433
2434   if (Number == 0) {
2435     CharC = (UINT16) GetBits (Sd, CBIT);
2436
2437     for (Index = 0; Index < NC; Index++) {
2438       Sd->mCLen[Index] = 0;
2439     }
2440
2441     for (Index = 0; Index < 4096; Index++) {
2442       Sd->mCTable[Index] = CharC;
2443     }
2444
2445     return ;
2446   }
2447
2448   Index = 0;
2449   while (Index < Number) {
2450
2451     CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
2452     if (CharC >= NT) {
2453       Mask = 1U << (BITBUFSIZ - 1 - 8);
2454
2455       do {
2456
2457         if (Mask & Sd->mBitBuf) {
2458           CharC = Sd->mRight[CharC];
2459         } else {
2460           CharC = Sd->mLeft[CharC];
2461         }
2462
2463         Mask >>= 1;
2464
2465       } while (CharC >= NT);
2466     }
2467     //
2468     // Advance what we have read
2469     //
2470     FillBuf (Sd, Sd->mPTLen[CharC]);
2471
2472     if (CharC <= 2) {
2473
2474       if (CharC == 0) {
2475         CharC = 1;
2476       } else if (CharC == 1) {
2477         CharC = (UINT16) (GetBits (Sd, 4) + 3);
2478       } else if (CharC == 2) {
2479         CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
2480       }
2481
2482       while ((INT16) (--CharC) >= 0) {
2483         Sd->mCLen[Index++] = 0;
2484       }
2485
2486     } else {
2487
2488       Sd->mCLen[Index++] = (UINT8) (CharC - 2);
2489
2490     }
2491   }
2492
2493   while (Index < NC) {
2494     Sd->mCLen[Index++] = 0;
2495   }
2496
2497   MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
2498
2499   return ;
2500 }
2501
2502 UINT16
2503 DecodeC (
2504   SCRATCH_DATA  *Sd
2505   )
2506 /*++
2507
2508 Routine Description:
2509
2510   Decode a character/length value.
2511
2512 Arguments:
2513
2514   Sd    - The global scratch data.
2515
2516 Returns:
2517
2518   The value decoded.
2519
2520 --*/
2521 {
2522   UINT16  Index2;
2523   UINT32  Mask;
2524
2525   if (Sd->mBlockSize == 0) {
2526     //
2527     // Starting a new block
2528     //
2529     Sd->mBlockSize    = (UINT16) GetBits (Sd, 16);
2530     Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
2531     if (Sd->mBadTableFlag != 0) {
2532       return 0;
2533     }
2534
2535     ReadCLen (Sd);
2536
2537     Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
2538     if (Sd->mBadTableFlag != 0) {
2539       return 0;
2540     }
2541   }
2542
2543   Sd->mBlockSize--;
2544   Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
2545
2546   if (Index2 >= NC) {
2547     Mask = 1U << (BITBUFSIZ - 1 - 12);
2548
2549     do {
2550       if (Sd->mBitBuf & Mask) {
2551         Index2 = Sd->mRight[Index2];
2552       } else {
2553         Index2 = Sd->mLeft[Index2];
2554       }
2555
2556       Mask >>= 1;
2557     } while (Index2 >= NC);
2558   }
2559   //
2560   // Advance what we have read
2561   //
2562   FillBuf (Sd, Sd->mCLen[Index2]);
2563
2564   return Index2;
2565 }
2566
2567 VOID
2568 Decode (
2569   SCRATCH_DATA  *Sd
2570   )
2571 /*++
2572
2573 Routine Description:
2574
2575   Decode the source data and put the resulting data into the destination buffer.
2576
2577 Arguments:
2578
2579   Sd            - The global scratch data
2580
2581 Returns: (VOID)
2582
2583  --*/
2584 {
2585   UINT16  BytesRemain;
2586   UINT32  DataIdx;
2587   UINT16  CharC;
2588
2589   BytesRemain = (UINT16) (-1);
2590
2591   DataIdx     = 0;
2592
2593   for (;;) {
2594     CharC = DecodeC (Sd);
2595     if (Sd->mBadTableFlag != 0) {
2596       goto Done ;
2597     }
2598
2599     if (CharC < 256) {
2600       //
2601       // Process an Original character
2602       //
2603       if (Sd->mOutBuf >= Sd->mOrigSize) {
2604         goto Done ;
2605       } else {
2606         Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
2607       }
2608
2609     } else {
2610       //
2611       // Process a Pointer
2612       //
2613       CharC       = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));
2614
2615       BytesRemain = CharC;
2616
2617       DataIdx     = Sd->mOutBuf - DecodeP (Sd) - 1;
2618
2619       BytesRemain--;
2620       while ((INT16) (BytesRemain) >= 0) {
2621         Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
2622         if (Sd->mOutBuf >= Sd->mOrigSize) {
2623           goto Done ;
2624         }
2625
2626         BytesRemain--;
2627       }
2628     }
2629   }
2630
2631 Done:
2632   return ;
2633 }
2634
2635 RETURN_STATUS
2636 EFIAPI
2637 Decompress (
2638   IN VOID  *Source,
2639   IN OUT VOID    *Destination,
2640   IN OUT VOID    *Scratch,
2641   IN UINT32      Version
2642   )
2643 /*++
2644
2645 Routine Description:
2646
2647   The internal implementation of Decompress().
2648
2649 Arguments:
2650
2651   Source          - The source buffer containing the compressed data.
2652   Destination     - The destination buffer to store the decompressed data
2653   Scratch         - The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.
2654   Version         - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm
2655
2656 Returns:
2657
2658   RETURN_SUCCESS           - Decompression is successfull
2659   RETURN_INVALID_PARAMETER - The source data is corrupted
2660
2661 --*/
2662 {
2663   volatile UINT32  Index;
2664   UINT32           CompSize;
2665   UINT32           OrigSize;
2666   SCRATCH_DATA     *Sd;
2667   CONST UINT8      *Src;
2668   UINT8            *Dst;
2669
2670   //
2671   // Verify input is not NULL
2672   //
2673   assert(Source);
2674 //  assert(Destination);
2675   assert(Scratch);
2676
2677   Src     = (UINT8 *)Source;
2678   Dst     = (UINT8 *)Destination;
2679
2680   Sd      = (SCRATCH_DATA *) Scratch;
2681   CompSize  = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
2682   OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
2683
2684   //
2685   // If compressed file size is 0, return
2686   //
2687   if (OrigSize == 0) {
2688     return RETURN_SUCCESS;
2689   }
2690
2691   Src = Src + 8;
2692
2693   for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
2694     ((UINT8 *) Sd)[Index] = 0;
2695   }
2696   //
2697   // The length of the field 'Position Set Code Length Array Size' in Block Header.
2698   // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
2699   // For Tiano de/compression algorithm(Version 2), mPBit = 5
2700   //
2701   switch (Version) {
2702     case 1 :
2703       Sd->mPBit = 4;
2704       break;
2705     case 2 :
2706       Sd->mPBit = 5;
2707       break;
2708     default:
2709       assert(FALSE);
2710   }
2711   Sd->mSrcBase  = (UINT8 *)Src;
2712   Sd->mDstBase  = Dst;
2713   Sd->mCompSize = CompSize;
2714   Sd->mOrigSize = OrigSize;
2715
2716   //
2717   // Fill the first BITBUFSIZ bits
2718   //
2719   FillBuf (Sd, BITBUFSIZ);
2720
2721   //
2722   // Decompress it
2723   //
2724
2725   Decode (Sd);
2726
2727   if (Sd->mBadTableFlag != 0) {
2728     //
2729     // Something wrong with the source
2730     //
2731     return RETURN_INVALID_PARAMETER;
2732   }
2733
2734   return RETURN_SUCCESS;
2735 }
2736
2737