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