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