BaseTools/Source/C/TianoCompress/TianoCompress.c

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