ShellPkg/Library/UefiShellDebug1CommandsLib/Compress.c

   1 /** @file
   2   Main file for compression routine.
   3
   4   Compression routine. The compression algorithm is a mixture of
   5   LZ77 and Huffman coding. LZ77 transforms the source data into a
   6   sequence of Original Characters and Pointers to repeated strings.
   7   This sequence is further divided into Blocks and Huffman codings
   8   are applied to each Block.
   9
  10   Copyright (c) 2007 - 2014, Intel Corporation. All rights reserved.<BR>
  11   This program and the accompanying materials
  12   are licensed and made available under the terms and conditions of the BSD License
  13   which accompanies this distribution.  The full text of the license may be found at
  14   http://opensource.org/licenses/bsd-license.php
  15
  16   THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  17   WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  18
  19 **/
  20
  21 #include <Library/MemoryAllocationLib.h>
  22 #include <Library/BaseMemoryLib.h>
  23 #include <Library/DebugLib.h>
  24 #include <ShellBase.h>
  25 #include <Uefi.h>
  26
  27 //
  28 // Macro Definitions
  29 //
  30 typedef INT16             NODE;
  31 #define UINT8_MAX         0xff
  32 #define UINT8_BIT         8
  33 #define THRESHOLD         3
  34 #define INIT_CRC          0
  35 #define WNDBIT            13
  36 #define WNDSIZ            (1U << WNDBIT)
  37 #define MAXMATCH          256
  38 #define BLKSIZ            (1U << 14)  // 16 * 1024U
  39 #define PERC_FLAG         0x8000U
  40 #define CODE_BIT          16
  41 #define NIL               0
  42 #define MAX_HASH_VAL      (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
  43 #define HASH(LoopVar7, LoopVar5)        ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)
  44 #define CRCPOLY           0xA001
  45 #define UPDATE_CRC(LoopVar5)     mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)
  46
  47 //
  48 // C: the Char&Len Set; P: the Position Set; T: the exTra Set
  49 //
  50 #define NC                (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
  51 #define CBIT              9
  52 #define NP                (WNDBIT + 1)
  53 #define PBIT              4
  54 #define NT                (CODE_BIT + 3)
  55 #define TBIT              5
  56 #if NT > NP
  57   #define                 NPT NT
  58 #else
  59   #define                 NPT NP
  60 #endif
  61 //
  62 // Function Prototypes
  63 //
  64
  65 /**
  66   Put a dword to output stream
  67
  68   @param[in] Data    The dword to put.
  69 **/
  70 VOID
  71 PutDword(
  72   IN UINT32 Data
  73   );
  74
  75 //
  76 //  Global Variables
  77 //
  78 STATIC UINT8  *mSrc;
  79 STATIC UINT8  *mDst;
  80 STATIC UINT8  *mSrcUpperLimit;
  81 STATIC UINT8  *mDstUpperLimit;
  82
  83 STATIC UINT8  *mLevel;
  84 STATIC UINT8  *mText;
  85 STATIC UINT8  *mChildCount;
  86 STATIC UINT8  *mBuf;
  87 STATIC UINT8  mCLen[NC];
  88 STATIC UINT8  mPTLen[NPT];
  89 STATIC UINT8  *mLen;
  90 STATIC INT16  mHeap[NC + 1];
  91 STATIC INT32  mRemainder;
  92 STATIC INT32  mMatchLen;
  93 STATIC INT32  mBitCount;
  94 STATIC INT32  mHeapSize;
  95 STATIC INT32  mTempInt32;
  96 STATIC UINT32 mBufSiz = 0;
  97 STATIC UINT32 mOutputPos;
  98 STATIC UINT32 mOutputMask;
  99 STATIC UINT32 mSubBitBuf;
 100 STATIC UINT32 mCrc;
 101 STATIC UINT32 mCompSize;
 102 STATIC UINT32 mOrigSize;
 103
 104 STATIC UINT16 *mFreq;
 105 STATIC UINT16 *mSortPtr;
 106 STATIC UINT16 mLenCnt[17];
 107 STATIC UINT16 mLeft[2 * NC - 1];
 108 STATIC UINT16 mRight[2 * NC - 1];
 109 STATIC UINT16 mCrcTable[UINT8_MAX + 1];
 110 STATIC UINT16 mCFreq[2 * NC - 1];
 111 STATIC UINT16 mCCode[NC];
 112 STATIC UINT16 mPFreq[2 * NP - 1];
 113 STATIC UINT16 mPTCode[NPT];
 114 STATIC UINT16 mTFreq[2 * NT - 1];
 115
 116 STATIC NODE   mPos;
 117 STATIC NODE   mMatchPos;
 118 STATIC NODE   mAvail;
 119 STATIC NODE   *mPosition;
 120 STATIC NODE   *mParent;
 121 STATIC NODE   *mPrev;
 122 STATIC NODE   *mNext = NULL;
 123 INT32         mHuffmanDepth = 0;
 124
 125 /**
 126   Make a CRC table.
 127
 128 **/
 129 VOID
 130 MakeCrcTable (
 131   VOID
 132   )
 133 {
 134   UINT32  LoopVar1;
 135
 136   UINT32  LoopVar2;
 137
 138   UINT32  LoopVar4;
 139
 140   for (LoopVar1 = 0; LoopVar1 <= UINT8_MAX; LoopVar1++) {
 141     LoopVar4 = LoopVar1;
 142     for (LoopVar2 = 0; LoopVar2 < UINT8_BIT; LoopVar2++) {
 143       if ((LoopVar4 & 1) != 0) {
 144         LoopVar4 = (LoopVar4 >> 1) ^ CRCPOLY;
 145       } else {
 146         LoopVar4 >>= 1;
 147       }
 148     }
 149
 150     mCrcTable[LoopVar1] = (UINT16) LoopVar4;
 151   }
 152 }
 153
 154 /**
 155   Put a dword to output stream
 156
 157   @param[in] Data    The dword to put.
 158 **/
 159 VOID
 160 PutDword (
 161   IN UINT32 Data
 162   )
 163 {
 164   if (mDst < mDstUpperLimit) {
 165     *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
 166   }
 167
 168   if (mDst < mDstUpperLimit) {
 169     *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
 170   }
 171
 172   if (mDst < mDstUpperLimit) {
 173     *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
 174   }
 175
 176   if (mDst < mDstUpperLimit) {
 177     *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
 178   }
 179 }
 180
 181 /**
 182   Allocate memory spaces for data structures used in compression process.
 183
 184   @retval EFI_SUCCESS           Memory was allocated successfully.
 185   @retval EFI_OUT_OF_RESOURCES  A memory allocation failed.
 186 **/
 187 EFI_STATUS
 188 AllocateMemory (
 189   VOID
 190   )
 191 {
 192   mText       = AllocateZeroPool (WNDSIZ * 2 + MAXMATCH);
 193   mLevel      = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
 194   mChildCount = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
 195   mPosition   = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
 196   mParent     = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mParent));
 197   mPrev       = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mPrev));
 198   mNext       = AllocateZeroPool ((MAX_HASH_VAL + 1) * sizeof (*mNext));
 199
 200   mBufSiz     = BLKSIZ;
 201   mBuf        = AllocateZeroPool (mBufSiz);
 202   while (mBuf == NULL) {
 203     mBufSiz = (mBufSiz / 10U) * 9U;
 204     if (mBufSiz < 4 * 1024U) {
 205       return EFI_OUT_OF_RESOURCES;
 206     }
 207
 208     mBuf = AllocateZeroPool (mBufSiz);
 209   }
 210
 211   mBuf[0] = 0;
 212
 213   return EFI_SUCCESS;
 214 }
 215
 216 /**
 217   Called when compression is completed to free memory previously allocated.
 218
 219 **/
 220 VOID
 221 FreeMemory (
 222   VOID
 223   )
 224 {
 225   SHELL_FREE_NON_NULL (mText);
 226   SHELL_FREE_NON_NULL (mLevel);
 227   SHELL_FREE_NON_NULL (mChildCount);
 228   SHELL_FREE_NON_NULL (mPosition);
 229   SHELL_FREE_NON_NULL (mParent);
 230   SHELL_FREE_NON_NULL (mPrev);
 231   SHELL_FREE_NON_NULL (mNext);
 232   SHELL_FREE_NON_NULL (mBuf);
 233 }
 234
 235 /**
 236   Initialize String Info Log data structures.
 237 **/
 238 VOID
 239 InitSlide (
 240   VOID
 241   )
 242 {
 243   NODE  LoopVar1;
 244
 245   SetMem (mLevel + WNDSIZ, (UINT8_MAX + 1) * sizeof (UINT8), 1);
 246   SetMem (mPosition + WNDSIZ, (UINT8_MAX + 1) * sizeof (NODE), 0);
 247
 248   SetMem (mParent + WNDSIZ, WNDSIZ * sizeof (NODE), 0);
 249
 250   mAvail = 1;
 251   for (LoopVar1 = 1; LoopVar1 < WNDSIZ - 1; LoopVar1++) {
 252     mNext[LoopVar1] = (NODE) (LoopVar1 + 1);
 253   }
 254
 255   mNext[WNDSIZ - 1] = NIL;
 256   SetMem (mNext + WNDSIZ * 2, (MAX_HASH_VAL - WNDSIZ * 2 + 1) * sizeof (NODE), 0);
 257 }
 258
 259 /**
 260   Find child node given the parent node and the edge character
 261
 262   @param[in] LoopVar6       The parent node.
 263   @param[in] LoopVar5       The edge character.
 264
 265   @return             The child node.
 266   @retval NIL(Zero)   No child could be found.
 267
 268 **/
 269 NODE
 270 Child (
 271   IN NODE   LoopVar6,
 272   IN UINT8  LoopVar5
 273   )
 274 {
 275   NODE  LoopVar4;
 276
 277   LoopVar4             = mNext[HASH (LoopVar6, LoopVar5)];
 278   mParent[NIL]  = LoopVar6;  /* sentinel */
 279   while (mParent[LoopVar4] != LoopVar6) {
 280     LoopVar4 = mNext[LoopVar4];
 281   }
 282
 283   return LoopVar4;
 284 }
 285
 286 /**
 287   Create a new child for a given parent node.
 288
 289   @param[in] LoopVar6       The parent node.
 290   @param[in] LoopVar5       The edge character.
 291   @param[in] LoopVar4       The child node.
 292 **/
 293 VOID
 294 MakeChild (
 295   IN NODE   LoopVar6,
 296   IN UINT8  LoopVar5,
 297   IN NODE   LoopVar4
 298   )
 299 {
 300   NODE  LoopVar12;
 301
 302   NODE  LoopVar10;
 303
 304   LoopVar12          = (NODE) HASH (LoopVar6, LoopVar5);
 305   LoopVar10          = mNext[LoopVar12];
 306   mNext[LoopVar12]   = LoopVar4;
 307   mNext[LoopVar4]    = LoopVar10;
 308   mPrev[LoopVar10]   = LoopVar4;
 309   mPrev[LoopVar4]    = LoopVar12;
 310   mParent[LoopVar4]  = LoopVar6;
 311   mChildCount[LoopVar6]++;
 312 }
 313
 314 /**
 315   Split a node.
 316
 317   @param[in] Old     The node to split.
 318 **/
 319 VOID
 320 Split (
 321   IN NODE Old
 322   )
 323 {
 324   NODE  New;
 325
 326   NODE  LoopVar10;
 327
 328   New               = mAvail;
 329   mAvail            = mNext[New];
 330   mChildCount[New]  = 0;
 331   LoopVar10                 = mPrev[Old];
 332   mPrev[New]        = LoopVar10;
 333   mNext[LoopVar10]          = New;
 334   LoopVar10                 = mNext[Old];
 335   mNext[New]        = LoopVar10;
 336   mPrev[LoopVar10]          = New;
 337   mParent[New]      = mParent[Old];
 338   mLevel[New]       = (UINT8) mMatchLen;
 339   mPosition[New]    = mPos;
 340   MakeChild (New, mText[mMatchPos + mMatchLen], Old);
 341   MakeChild (New, mText[mPos + mMatchLen], mPos);
 342 }
 343
 344 /**
 345   Insert string info for current position into the String Info Log.
 346
 347 **/
 348 VOID
 349 InsertNode (
 350   VOID
 351   )
 352 {
 353   NODE  LoopVar6;
 354
 355   NODE  LoopVar4;
 356
 357   NODE  LoopVar2;
 358
 359   NODE  LoopVar10;
 360   UINT8 LoopVar5;
 361   UINT8 *TempString3;
 362   UINT8 *TempString2;
 363
 364   if (mMatchLen >= 4) {
 365     //
 366     // We have just got a long match, the target tree
 367     // can be located by MatchPos + 1. Travese the tree
 368     // from bottom up to get to a proper starting point.
 369     // The usage of PERC_FLAG ensures proper node deletion
 370     // in DeleteNode() later.
 371     //
 372     mMatchLen--;
 373     LoopVar4 = (NODE) ((mMatchPos + 1) | WNDSIZ);
 374     LoopVar6 = mParent[LoopVar4];
 375     while (LoopVar6 == NIL) {
 376       LoopVar4 = mNext[LoopVar4];
 377       LoopVar6 = mParent[LoopVar4];
 378     }
 379
 380     while (mLevel[LoopVar6] >= mMatchLen) {
 381       LoopVar4 = LoopVar6;
 382       LoopVar6 = mParent[LoopVar6];
 383     }
 384
 385     LoopVar10 = LoopVar6;
 386     while (mPosition[LoopVar10] < 0) {
 387       mPosition[LoopVar10]  = mPos;
 388       LoopVar10             = mParent[LoopVar10];
 389     }
 390
 391     if (LoopVar10 < WNDSIZ) {
 392       mPosition[LoopVar10] = (NODE) (mPos | PERC_FLAG);
 393     }
 394   } else {
 395     //
 396     // Locate the target tree
 397     //
 398     LoopVar6 = (NODE) (mText[mPos] + WNDSIZ);
 399     LoopVar5 = mText[mPos + 1];
 400     LoopVar4 = Child (LoopVar6, LoopVar5);
 401     if (LoopVar4 == NIL) {
 402       MakeChild (LoopVar6, LoopVar5, mPos);
 403       mMatchLen = 1;
 404       return ;
 405     }
 406
 407     mMatchLen = 2;
 408   }
 409   //
 410   // Traverse down the tree to find a match.
 411   // Update Position value along the route.
 412   // Node split or creation is involved.
 413   //
 414   for (;;) {
 415     if (LoopVar4 >= WNDSIZ) {
 416       LoopVar2         = MAXMATCH;
 417       mMatchPos = LoopVar4;
 418     } else {
 419       LoopVar2         = mLevel[LoopVar4];
 420       mMatchPos = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
 421     }
 422
 423     if (mMatchPos >= mPos) {
 424       mMatchPos -= WNDSIZ;
 425     }
 426
 427     TempString3  = &mText[mPos + mMatchLen];
 428     TempString2  = &mText[mMatchPos + mMatchLen];
 429     while (mMatchLen < LoopVar2) {
 430       if (*TempString3 != *TempString2) {
 431         Split (LoopVar4);
 432         return ;
 433       }
 434
 435       mMatchLen++;
 436       TempString3++;
 437       TempString2++;
 438     }
 439
 440     if (mMatchLen >= MAXMATCH) {
 441       break;
 442     }
 443
 444     mPosition[LoopVar4]  = mPos;
 445     LoopVar6             = LoopVar4;
 446     LoopVar4             = Child (LoopVar6, *TempString3);
 447     if (LoopVar4 == NIL) {
 448       MakeChild (LoopVar6, *TempString3, mPos);
 449       return ;
 450     }
 451
 452     mMatchLen++;
 453   }
 454
 455   LoopVar10             = mPrev[LoopVar4];
 456   mPrev[mPos]   = LoopVar10;
 457   mNext[LoopVar10]      = mPos;
 458   LoopVar10             = mNext[LoopVar4];
 459   mNext[mPos]   = LoopVar10;
 460   mPrev[LoopVar10]      = mPos;
 461   mParent[mPos] = LoopVar6;
 462   mParent[LoopVar4]    = NIL;
 463
 464   //
 465   // Special usage of 'next'
 466   //
 467   mNext[LoopVar4] = mPos;
 468
 469 }
 470
 471 /**
 472   Delete outdated string info. (The Usage of PERC_FLAG
 473   ensures a clean deletion).
 474
 475 **/
 476 VOID
 477 DeleteNode (
 478   VOID
 479   )
 480 {
 481   NODE  LoopVar6;
 482
 483   NODE  LoopVar4;
 484
 485   NODE  LoopVar11;
 486
 487   NODE  LoopVar10;
 488
 489   NODE  LoopVar9;
 490
 491   if (mParent[mPos] == NIL) {
 492     return ;
 493   }
 494
 495   LoopVar4             = mPrev[mPos];
 496   LoopVar11             = mNext[mPos];
 497   mNext[LoopVar4]      = LoopVar11;
 498   mPrev[LoopVar11]      = LoopVar4;
 499   LoopVar4             = mParent[mPos];
 500   mParent[mPos] = NIL;
 501   if (LoopVar4 >= WNDSIZ) {
 502     return ;
 503   }
 504
 505   mChildCount[LoopVar4]--;
 506   if (mChildCount[LoopVar4] > 1) {
 507     return ;
 508   }
 509
 510   LoopVar10 = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
 511   if (LoopVar10 >= mPos) {
 512     LoopVar10 -= WNDSIZ;
 513   }
 514
 515   LoopVar11 = LoopVar10;
 516   LoopVar6 = mParent[LoopVar4];
 517   LoopVar9 = mPosition[LoopVar6];
 518   while ((LoopVar9 & PERC_FLAG) != 0){
 519     LoopVar9 &= ~PERC_FLAG;
 520     if (LoopVar9 >= mPos) {
 521       LoopVar9 -= WNDSIZ;
 522     }
 523
 524     if (LoopVar9 > LoopVar11) {
 525       LoopVar11 = LoopVar9;
 526     }
 527
 528     mPosition[LoopVar6]  = (NODE) (LoopVar11 | WNDSIZ);
 529     LoopVar6             = mParent[LoopVar6];
 530     LoopVar9             = mPosition[LoopVar6];
 531   }
 532
 533   if (LoopVar6 < WNDSIZ) {
 534     if (LoopVar9 >= mPos) {
 535       LoopVar9 -= WNDSIZ;
 536     }
 537
 538     if (LoopVar9 > LoopVar11) {
 539       LoopVar11 = LoopVar9;
 540     }
 541
 542     mPosition[LoopVar6] = (NODE) (LoopVar11 | WNDSIZ | PERC_FLAG);
 543   }
 544
 545   LoopVar11           = Child (LoopVar4, mText[LoopVar10 + mLevel[LoopVar4]]);
 546   LoopVar10           = mPrev[LoopVar11];
 547   LoopVar9           = mNext[LoopVar11];
 548   mNext[LoopVar10]    = LoopVar9;
 549   mPrev[LoopVar9]    = LoopVar10;
 550   LoopVar10           = mPrev[LoopVar4];
 551   mNext[LoopVar10]    = LoopVar11;
 552   mPrev[LoopVar11]    = LoopVar10;
 553   LoopVar10           = mNext[LoopVar4];
 554   mPrev[LoopVar10]    = LoopVar11;
 555   mNext[LoopVar11]    = LoopVar10;
 556   mParent[LoopVar11]  = mParent[LoopVar4];
 557   mParent[LoopVar4]  = NIL;
 558   mNext[LoopVar4]    = mAvail;
 559   mAvail      = LoopVar4;
 560 }
 561
 562 /**
 563   Read in source data
 564
 565   @param[out] LoopVar7   The buffer to hold the data.
 566   @param[in] LoopVar8    The number of bytes to read.
 567
 568   @return The number of bytes actually read.
 569 **/
 570 INT32
 571 FreadCrc (
 572   OUT UINT8 *LoopVar7,
 573   IN  INT32 LoopVar8
 574   )
 575 {
 576   INT32 LoopVar1;
 577
 578   for (LoopVar1 = 0; mSrc < mSrcUpperLimit && LoopVar1 < LoopVar8; LoopVar1++) {
 579     *LoopVar7++ = *mSrc++;
 580   }
 581
 582   LoopVar8 = LoopVar1;
 583
 584   LoopVar7 -= LoopVar8;
 585   mOrigSize += LoopVar8;
 586   LoopVar1--;
 587   while (LoopVar1 >= 0) {
 588     UPDATE_CRC (*LoopVar7++);
 589     LoopVar1--;
 590   }
 591
 592   return LoopVar8;
 593 }
 594
 595 /**
 596   Advance the current position (read in new data if needed).
 597   Delete outdated string info. Find a match string for current position.
 598
 599   @retval TRUE      The operation was successful.
 600   @retval FALSE     The operation failed due to insufficient memory.
 601 **/
 602 BOOLEAN
 603 GetNextMatch (
 604   VOID
 605   )
 606 {
 607   INT32 LoopVar8;
 608   VOID  *Temp;
 609
 610   mRemainder--;
 611   mPos++;
 612   if (mPos == WNDSIZ * 2) {
 613     Temp = AllocateZeroPool (WNDSIZ + MAXMATCH);
 614     if (Temp == NULL) {
 615       return (FALSE);
 616     }
 617     CopyMem (Temp, &mText[WNDSIZ], WNDSIZ + MAXMATCH);
 618     CopyMem (&mText[0], Temp, WNDSIZ + MAXMATCH);
 619     FreePool (Temp);
 620     LoopVar8 = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
 621     mRemainder += LoopVar8;
 622     mPos = WNDSIZ;
 623   }
 624
 625   DeleteNode ();
 626   InsertNode ();
 627
 628   return (TRUE);
 629 }
 630
 631 /**
 632   Send entry LoopVar1 down the queue.
 633
 634   @param[in] LoopVar1    The index of the item to move.
 635 **/
 636 VOID
 637 DownHeap (
 638   IN INT32 i
 639   )
 640 {
 641   INT32 LoopVar1;
 642
 643   INT32 LoopVar2;
 644
 645   //
 646   // priority queue: send i-th entry down heap
 647   //
 648   LoopVar2 = mHeap[i];
 649   LoopVar1 = 2 * i;
 650   while (LoopVar1 <= mHeapSize) {
 651     if (LoopVar1 < mHeapSize && mFreq[mHeap[LoopVar1]] > mFreq[mHeap[LoopVar1 + 1]]) {
 652       LoopVar1++;
 653     }
 654
 655     if (mFreq[LoopVar2] <= mFreq[mHeap[LoopVar1]]) {
 656       break;
 657     }
 658
 659     mHeap[i]  = mHeap[LoopVar1];
 660     i         = LoopVar1;
 661     LoopVar1         = 2 * i;
 662   }
 663
 664   mHeap[i] = (INT16) LoopVar2;
 665 }
 666
 667 /**
 668   Count the number of each code length for a Huffman tree.
 669
 670   @param[in] LoopVar1      The top node.
 671 **/
 672 VOID
 673 CountLen (
 674   IN INT32 LoopVar1
 675   )
 676 {
 677   if (LoopVar1 < mTempInt32) {
 678     mLenCnt[(mHuffmanDepth < 16) ? mHuffmanDepth : 16]++;
 679   } else {
 680     mHuffmanDepth++;
 681     CountLen (mLeft[LoopVar1]);
 682     CountLen (mRight[LoopVar1]);
 683     mHuffmanDepth--;
 684   }
 685 }
 686
 687 /**
 688   Create code length array for a Huffman tree.
 689
 690   @param[in] Root   The root of the tree.
 691 **/
 692 VOID
 693 MakeLen (
 694   IN INT32 Root
 695   )
 696 {
 697   INT32   LoopVar1;
 698
 699   INT32   LoopVar2;
 700   UINT32  Cum;
 701
 702   for (LoopVar1 = 0; LoopVar1 <= 16; LoopVar1++) {
 703     mLenCnt[LoopVar1] = 0;
 704   }
 705
 706   CountLen (Root);
 707
 708   //
 709   // Adjust the length count array so that
 710   // no code will be generated longer than its designated length
 711   //
 712   Cum = 0;
 713   for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
 714     Cum += mLenCnt[LoopVar1] << (16 - LoopVar1);
 715   }
 716
 717   while (Cum != (1U << 16)) {
 718     mLenCnt[16]--;
 719     for (LoopVar1 = 15; LoopVar1 > 0; LoopVar1--) {
 720       if (mLenCnt[LoopVar1] != 0) {
 721         mLenCnt[LoopVar1]--;
 722         mLenCnt[LoopVar1 + 1] += 2;
 723         break;
 724       }
 725     }
 726
 727     Cum--;
 728   }
 729
 730   for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
 731     LoopVar2 = mLenCnt[LoopVar1];
 732     LoopVar2--;
 733     while (LoopVar2 >= 0) {
 734       mLen[*mSortPtr++] = (UINT8) LoopVar1;
 735       LoopVar2--;
 736     }
 737   }
 738 }
 739
 740 /**
 741   Assign code to each symbol based on the code length array.
 742
 743   @param[in] LoopVar8      The number of symbols.
 744   @param[in] Len    The code length array.
 745   @param[out] Code  The stores codes for each symbol.
 746 **/
 747 VOID
 748 MakeCode (
 749   IN  INT32         LoopVar8,
 750   IN  UINT8 Len[    ],
 751   OUT UINT16 Code[  ]
 752   )
 753 {
 754   INT32   LoopVar1;
 755   UINT16  Start[18];
 756
 757   Start[1] = 0;
 758   for (LoopVar1 = 1; LoopVar1 <= 16; LoopVar1++) {
 759     Start[LoopVar1 + 1] = (UINT16) ((Start[LoopVar1] + mLenCnt[LoopVar1]) << 1);
 760   }
 761
 762   for (LoopVar1 = 0; LoopVar1 < LoopVar8; LoopVar1++) {
 763     Code[LoopVar1] = Start[Len[LoopVar1]]++;
 764   }
 765 }
 766
 767 /**
 768   Generates Huffman codes given a frequency distribution of symbols.
 769
 770   @param[in] NParm      The number of symbols.
 771   @param[in] FreqParm   The frequency of each symbol.
 772   @param[out] LenParm   The code length for each symbol.
 773   @param[out] CodeParm  The code for each symbol.
 774
 775   @return The root of the Huffman tree.
 776 **/
 777 INT32
 778 MakeTree (
 779   IN  INT32             NParm,
 780   IN  UINT16  FreqParm[ ],
 781   OUT UINT8   LenParm[  ],
 782   OUT UINT16  CodeParm[ ]
 783   )
 784 {
 785   INT32 LoopVar1;
 786
 787   INT32 LoopVar2;
 788
 789   INT32 LoopVar3;
 790
 791   INT32 Avail;
 792
 793   //
 794   // make tree, calculate len[], return root
 795   //
 796   mTempInt32        = NParm;
 797   mFreq     = FreqParm;
 798   mLen      = LenParm;
 799   Avail     = mTempInt32;
 800   mHeapSize = 0;
 801   mHeap[1]  = 0;
 802   for (LoopVar1 = 0; LoopVar1 < mTempInt32; LoopVar1++) {
 803     mLen[LoopVar1] = 0;
 804     if ((mFreq[LoopVar1]) != 0) {
 805       mHeapSize++;
 806       mHeap[mHeapSize] = (INT16) LoopVar1;
 807     }
 808   }
 809
 810   if (mHeapSize < 2) {
 811     CodeParm[mHeap[1]] = 0;
 812     return mHeap[1];
 813   }
 814
 815   for (LoopVar1 = mHeapSize / 2; LoopVar1 >= 1; LoopVar1--) {
 816     //
 817     // make priority queue
 818     //
 819     DownHeap (LoopVar1);
 820   }
 821
 822   mSortPtr = CodeParm;
 823   do {
 824     LoopVar1 = mHeap[1];
 825     if (LoopVar1 < mTempInt32) {
 826       *mSortPtr++ = (UINT16) LoopVar1;
 827     }
 828
 829     mHeap[1] = mHeap[mHeapSize--];
 830     DownHeap (1);
 831     LoopVar2 = mHeap[1];
 832     if (LoopVar2 < mTempInt32) {
 833       *mSortPtr++ = (UINT16) LoopVar2;
 834     }
 835
 836     LoopVar3         = Avail++;
 837     mFreq[LoopVar3]  = (UINT16) (mFreq[LoopVar1] + mFreq[LoopVar2]);
 838     mHeap[1]  = (INT16) LoopVar3;
 839     DownHeap (1);
 840     mLeft[LoopVar3]  = (UINT16) LoopVar1;
 841     mRight[LoopVar3] = (UINT16) LoopVar2;
 842   } while (mHeapSize > 1);
 843
 844   mSortPtr = CodeParm;
 845   MakeLen (LoopVar3);
 846   MakeCode (NParm, LenParm, CodeParm);
 847
 848   //
 849   // return root
 850   //
 851   return LoopVar3;
 852 }
 853
 854 /**
 855   Outputs rightmost LoopVar8 bits of x
 856
 857   @param[in] LoopVar8   The rightmost LoopVar8 bits of the data is used.
 858   @param[in] x   The data.
 859 **/
 860 VOID
 861 PutBits (
 862   IN INT32    LoopVar8,
 863   IN UINT32   x
 864   )
 865 {
 866   UINT8 Temp;
 867
 868   if (LoopVar8 < mBitCount) {
 869     mSubBitBuf |= x << (mBitCount -= LoopVar8);
 870   } else {
 871
 872     Temp = (UINT8)(mSubBitBuf | (x >> (LoopVar8 -= mBitCount)));
 873     if (mDst < mDstUpperLimit) {
 874       *mDst++ = Temp;
 875     }
 876     mCompSize++;
 877
 878     if (LoopVar8 < UINT8_BIT) {
 879       mSubBitBuf = x << (mBitCount = UINT8_BIT - LoopVar8);
 880     } else {
 881
 882       Temp = (UINT8)(x >> (LoopVar8 - UINT8_BIT));
 883       if (mDst < mDstUpperLimit) {
 884         *mDst++ = Temp;
 885       }
 886       mCompSize++;
 887
 888       mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - LoopVar8);
 889     }
 890   }
 891 }
 892
 893 /**
 894   Encode a signed 32 bit number.
 895
 896   @param[in] LoopVar5     The number to encode.
 897 **/
 898 VOID
 899 EncodeC (
 900   IN INT32 LoopVar5
 901   )
 902 {
 903   PutBits (mCLen[LoopVar5], mCCode[LoopVar5]);
 904 }
 905
 906 /**
 907   Encode a unsigned 32 bit number.
 908
 909   @param[in] LoopVar7     The number to encode.
 910 **/
 911 VOID
 912 EncodeP (
 913   IN UINT32 LoopVar7
 914   )
 915 {
 916   UINT32  LoopVar5;
 917
 918   UINT32  LoopVar6;
 919
 920   LoopVar5 = 0;
 921   LoopVar6 = LoopVar7;
 922   while (LoopVar6 != 0) {
 923     LoopVar6 >>= 1;
 924     LoopVar5++;
 925   }
 926
 927   PutBits (mPTLen[LoopVar5], mPTCode[LoopVar5]);
 928   if (LoopVar5 > 1) {
 929     PutBits(LoopVar5 - 1, LoopVar7 & (0xFFFFU >> (17 - LoopVar5)));
 930   }
 931 }
 932
 933 /**
 934   Count the frequencies for the Extra Set.
 935
 936 **/
 937 VOID
 938 CountTFreq (
 939   VOID
 940   )
 941 {
 942   INT32 LoopVar1;
 943
 944   INT32 LoopVar3;
 945
 946   INT32 LoopVar8;
 947
 948   INT32 Count;
 949
 950   for (LoopVar1 = 0; LoopVar1 < NT; LoopVar1++) {
 951     mTFreq[LoopVar1] = 0;
 952   }
 953
 954   LoopVar8 = NC;
 955   while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
 956     LoopVar8--;
 957   }
 958
 959   LoopVar1 = 0;
 960   while (LoopVar1 < LoopVar8) {
 961     LoopVar3 = mCLen[LoopVar1++];
 962     if (LoopVar3 == 0) {
 963       Count = 1;
 964       while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
 965         LoopVar1++;
 966         Count++;
 967       }
 968
 969       if (Count <= 2) {
 970         mTFreq[0] = (UINT16) (mTFreq[0] + Count);
 971       } else if (Count <= 18) {
 972         mTFreq[1]++;
 973       } else if (Count == 19) {
 974         mTFreq[0]++;
 975         mTFreq[1]++;
 976       } else {
 977         mTFreq[2]++;
 978       }
 979     } else {
 980       ASSERT((LoopVar3+2)<(2 * NT - 1));
 981       mTFreq[LoopVar3 + 2]++;
 982     }
 983   }
 984 }
 985
 986 /**
 987   Outputs the code length array for the Extra Set or the Position Set.
 988
 989   @param[in] LoopVar8       The number of symbols.
 990   @param[in] nbit           The number of bits needed to represent 'LoopVar8'.
 991   @param[in] Special        The special symbol that needs to be take care of.
 992
 993 **/
 994 VOID
 995 WritePTLen (
 996   IN INT32 LoopVar8,
 997   IN INT32 nbit,
 998   IN INT32 Special
 999   )
1000 {
1001   INT32 LoopVar1;
1002
1003   INT32 LoopVar3;
1004
1005   while (LoopVar8 > 0 && mPTLen[LoopVar8 - 1] == 0) {
1006     LoopVar8--;
1007   }
1008
1009   PutBits (nbit, LoopVar8);
1010   LoopVar1 = 0;
1011   while (LoopVar1 < LoopVar8) {
1012     LoopVar3 = mPTLen[LoopVar1++];
1013     if (LoopVar3 <= 6) {
1014       PutBits (3, LoopVar3);
1015     } else {
1016       PutBits (LoopVar3 - 3, (1U << (LoopVar3 - 3)) - 2);
1017     }
1018
1019     if (LoopVar1 == Special) {
1020       while (LoopVar1 < 6 && mPTLen[LoopVar1] == 0) {
1021         LoopVar1++;
1022       }
1023
1024       PutBits (2, (LoopVar1 - 3) & 3);
1025     }
1026   }
1027 }
1028
1029 /**
1030   Outputs the code length array for Char&Length Set.
1031 **/
1032 VOID
1033 WriteCLen (
1034   VOID
1035   )
1036 {
1037   INT32 LoopVar1;
1038
1039   INT32 LoopVar3;
1040
1041   INT32 LoopVar8;
1042
1043   INT32 Count;
1044
1045   LoopVar8 = NC;
1046   while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
1047     LoopVar8--;
1048   }
1049
1050   PutBits (CBIT, LoopVar8);
1051   LoopVar1 = 0;
1052   while (LoopVar1 < LoopVar8) {
1053     LoopVar3 = mCLen[LoopVar1++];
1054     if (LoopVar3 == 0) {
1055       Count = 1;
1056       while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
1057         LoopVar1++;
1058         Count++;
1059       }
1060
1061       if (Count <= 2) {
1062         for (LoopVar3 = 0; LoopVar3 < Count; LoopVar3++) {
1063           PutBits (mPTLen[0], mPTCode[0]);
1064         }
1065       } else if (Count <= 18) {
1066         PutBits (mPTLen[1], mPTCode[1]);
1067         PutBits (4, Count - 3);
1068       } else if (Count == 19) {
1069         PutBits (mPTLen[0], mPTCode[0]);
1070         PutBits (mPTLen[1], mPTCode[1]);
1071         PutBits (4, 15);
1072       } else {
1073         PutBits (mPTLen[2], mPTCode[2]);
1074         PutBits (CBIT, Count - 20);
1075       }
1076     } else {
1077       ASSERT((LoopVar3+2)<NPT);
1078       PutBits (mPTLen[LoopVar3 + 2], mPTCode[LoopVar3 + 2]);
1079     }
1080   }
1081 }
1082
1083 /**
1084   Huffman code the block and output it.
1085
1086 **/
1087 VOID
1088 SendBlock (
1089   VOID
1090   )
1091 {
1092   UINT32  LoopVar1;
1093
1094   UINT32  LoopVar3;
1095
1096   UINT32  Flags;
1097
1098   UINT32  Root;
1099
1100   UINT32  Pos;
1101
1102   UINT32  Size;
1103   Flags = 0;
1104
1105   Root  = MakeTree (NC, mCFreq, mCLen, mCCode);
1106   Size  = mCFreq[Root];
1107   PutBits (16, Size);
1108   if (Root >= NC) {
1109     CountTFreq ();
1110     Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
1111     if (Root >= NT) {
1112       WritePTLen (NT, TBIT, 3);
1113     } else {
1114       PutBits (TBIT, 0);
1115       PutBits (TBIT, Root);
1116     }
1117
1118     WriteCLen ();
1119   } else {
1120     PutBits (TBIT, 0);
1121     PutBits (TBIT, 0);
1122     PutBits (CBIT, 0);
1123     PutBits (CBIT, Root);
1124   }
1125
1126   Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
1127   if (Root >= NP) {
1128     WritePTLen (NP, PBIT, -1);
1129   } else {
1130     PutBits (PBIT, 0);
1131     PutBits (PBIT, Root);
1132   }
1133
1134   Pos = 0;
1135   for (LoopVar1 = 0; LoopVar1 < Size; LoopVar1++) {
1136     if (LoopVar1 % UINT8_BIT == 0) {
1137       Flags = mBuf[Pos++];
1138     } else {
1139       Flags <<= 1;
1140     }
1141     if ((Flags & (1U << (UINT8_BIT - 1))) != 0){
1142       EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
1143       LoopVar3 = mBuf[Pos++] << UINT8_BIT;
1144       LoopVar3 += mBuf[Pos++];
1145
1146       EncodeP (LoopVar3);
1147     } else {
1148       EncodeC (mBuf[Pos++]);
1149     }
1150   }
1151
1152   SetMem (mCFreq, NC * sizeof (UINT16), 0);
1153   SetMem (mPFreq, NP * sizeof (UINT16), 0);
1154 }
1155
1156 /**
1157   Start the huffman encoding.
1158
1159 **/
1160 VOID
1161 HufEncodeStart (
1162   VOID
1163   )
1164 {
1165   SetMem (mCFreq, NC * sizeof (UINT16), 0);
1166   SetMem (mPFreq, NP * sizeof (UINT16), 0);
1167
1168   mOutputPos = mOutputMask = 0;
1169
1170   mBitCount   = UINT8_BIT;
1171   mSubBitBuf  = 0;
1172 }
1173
1174 /**
1175   Outputs an Original Character or a Pointer.
1176
1177   @param[in] LoopVar5     The original character or the 'String Length' element of
1178                    a Pointer.
1179   @param[in] LoopVar7     The 'Position' field of a Pointer.
1180 **/
1181 VOID
1182 CompressOutput (
1183   IN UINT32 LoopVar5,
1184   IN UINT32 LoopVar7
1185   )
1186 {
1187   STATIC UINT32 CPos;
1188
1189   if ((mOutputMask >>= 1) == 0) {
1190     mOutputMask = 1U << (UINT8_BIT - 1);
1191     if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
1192       SendBlock ();
1193       mOutputPos = 0;
1194     }
1195
1196     CPos        = mOutputPos++;
1197     mBuf[CPos]  = 0;
1198   }
1199   mBuf[mOutputPos++] = (UINT8) LoopVar5;
1200   mCFreq[LoopVar5]++;
1201   if (LoopVar5 >= (1U << UINT8_BIT)) {
1202     mBuf[CPos] = (UINT8)(mBuf[CPos]|mOutputMask);
1203     mBuf[mOutputPos++] = (UINT8)(LoopVar7 >> UINT8_BIT);
1204     mBuf[mOutputPos++] = (UINT8) LoopVar7;
1205     LoopVar5                  = 0;
1206     while (LoopVar7!=0) {
1207       LoopVar7 >>= 1;
1208       LoopVar5++;
1209     }
1210     mPFreq[LoopVar5]++;
1211   }
1212 }
1213
1214 /**
1215   End the huffman encoding.
1216
1217 **/
1218 VOID
1219 HufEncodeEnd (
1220   VOID
1221   )
1222 {
1223   SendBlock ();
1224
1225   //
1226   // Flush remaining bits
1227   //
1228   PutBits (UINT8_BIT - 1, 0);
1229 }
1230
1231 /**
1232   The main controlling routine for compression process.
1233
1234   @retval EFI_SUCCESS           The compression is successful.
1235   @retval EFI_OUT_0F_RESOURCES  Not enough memory for compression process.
1236 **/
1237 EFI_STATUS
1238 Encode (
1239   VOID
1240   )
1241 {
1242   EFI_STATUS  Status;
1243   INT32       LastMatchLen;
1244   NODE        LastMatchPos;
1245
1246   Status = AllocateMemory ();
1247   if (EFI_ERROR (Status)) {
1248     FreeMemory ();
1249     return Status;
1250   }
1251
1252   InitSlide ();
1253
1254   HufEncodeStart ();
1255
1256   mRemainder  = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
1257
1258   mMatchLen   = 0;
1259   mPos        = WNDSIZ;
1260   InsertNode ();
1261   if (mMatchLen > mRemainder) {
1262     mMatchLen = mRemainder;
1263   }
1264
1265   while (mRemainder > 0) {
1266     LastMatchLen  = mMatchLen;
1267     LastMatchPos  = mMatchPos;
1268     if (!GetNextMatch ()) {
1269       Status = EFI_OUT_OF_RESOURCES;
1270     }
1271     if (mMatchLen > mRemainder) {
1272       mMatchLen = mRemainder;
1273     }
1274
1275     if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
1276       //
1277       // Not enough benefits are gained by outputting a pointer,
1278       // so just output the original character
1279       //
1280       CompressOutput(mText[mPos - 1], 0);
1281     } else {
1282       //
1283       // Outputting a pointer is beneficial enough, do it.
1284       //
1285
1286       CompressOutput(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
1287              (mPos - LastMatchPos - 2) & (WNDSIZ - 1));
1288       LastMatchLen--;
1289       while (LastMatchLen > 0) {
1290         if (!GetNextMatch ()) {
1291           Status = EFI_OUT_OF_RESOURCES;
1292         }
1293         LastMatchLen--;
1294       }
1295
1296       if (mMatchLen > mRemainder) {
1297         mMatchLen = mRemainder;
1298       }
1299     }
1300   }
1301
1302   HufEncodeEnd ();
1303   FreeMemory ();
1304   return (Status);
1305 }
1306
1307 /**
1308   The compression routine.
1309
1310   @param[in]       SrcBuffer     The buffer containing the source data.
1311   @param[in]       SrcSize       The number of bytes in SrcBuffer.
1312   @param[in]       DstBuffer     The buffer to put the compressed image in.
1313   @param[in, out]  DstSize       On input the size (in bytes) of DstBuffer, on
1314                                 return the number of bytes placed in DstBuffer.
1315
1316   @retval EFI_SUCCESS           The compression was sucessful.
1317   @retval EFI_BUFFER_TOO_SMALL  The buffer was too small.  DstSize is required.
1318 **/
1319 EFI_STATUS
1320 Compress (
1321   IN       VOID   *SrcBuffer,
1322   IN       UINT64 SrcSize,
1323   IN       VOID   *DstBuffer,
1324   IN OUT   UINT64 *DstSize
1325   )
1326 {
1327   EFI_STATUS  Status;
1328
1329   //
1330   // Initializations
1331   //
1332   mBufSiz         = 0;
1333   mBuf            = NULL;
1334   mText           = NULL;
1335   mLevel          = NULL;
1336   mChildCount     = NULL;
1337   mPosition       = NULL;
1338   mParent         = NULL;
1339   mPrev           = NULL;
1340   mNext           = NULL;
1341
1342   mSrc            = SrcBuffer;
1343   mSrcUpperLimit  = mSrc + SrcSize;
1344   mDst            = DstBuffer;
1345   mDstUpperLimit  = mDst +*DstSize;
1346
1347   PutDword (0L);
1348   PutDword (0L);
1349
1350   MakeCrcTable ();
1351
1352   mOrigSize             = mCompSize = 0;
1353   mCrc                  = INIT_CRC;
1354
1355   //
1356   // Compress it
1357   //
1358   Status = Encode ();
1359   if (EFI_ERROR (Status)) {
1360     return EFI_OUT_OF_RESOURCES;
1361   }
1362   //
1363   // Null terminate the compressed data
1364   //
1365   if (mDst < mDstUpperLimit) {
1366     *mDst++ = 0;
1367   }
1368   //
1369   // Fill in compressed size and original size
1370   //
1371   mDst = DstBuffer;
1372   PutDword (mCompSize + 1);
1373   PutDword (mOrigSize);
1374
1375   //
1376   // Return
1377   //
1378   if (mCompSize + 1 + 8 > *DstSize) {
1379     *DstSize = mCompSize + 1 + 8;
1380     return EFI_BUFFER_TOO_SMALL;
1381   } else {
1382     *DstSize = mCompSize + 1 + 8;
1383     return EFI_SUCCESS;
1384   }
1385
1386 }
1387