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