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