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   // Traverse down the tree to find a match.
 406   // Update Position value along the route.
 407   // Node split or creation is involved.
 408   //
 409   for (;;) {
 410     if (LoopVar4 >= WNDSIZ) {
 411       LoopVar2         = MAXMATCH;
 412       mMatchPos = LoopVar4;
 413     } else {
 414       LoopVar2         = mLevel[LoopVar4];
 415       mMatchPos = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
 416     }
 417
 418     if (mMatchPos >= mPos) {
 419       mMatchPos -= WNDSIZ;
 420     }
 421
 422     TempString3  = &mText[mPos + mMatchLen];
 423     TempString2  = &mText[mMatchPos + mMatchLen];
 424     while (mMatchLen < LoopVar2) {
 425       if (*TempString3 != *TempString2) {
 426         Split (LoopVar4);
 427         return ;
 428       }
 429
 430       mMatchLen++;
 431       TempString3++;
 432       TempString2++;
 433     }
 434
 435     if (mMatchLen >= MAXMATCH) {
 436       break;
 437     }
 438
 439     mPosition[LoopVar4]  = mPos;
 440     LoopVar6             = LoopVar4;
 441     LoopVar4             = Child (LoopVar6, *TempString3);
 442     if (LoopVar4 == NIL) {
 443       MakeChild (LoopVar6, *TempString3, mPos);
 444       return ;
 445     }
 446
 447     mMatchLen++;
 448   }
 449
 450   LoopVar10             = mPrev[LoopVar4];
 451   mPrev[mPos]   = LoopVar10;
 452   mNext[LoopVar10]      = mPos;
 453   LoopVar10             = mNext[LoopVar4];
 454   mNext[mPos]   = LoopVar10;
 455   mPrev[LoopVar10]      = mPos;
 456   mParent[mPos] = LoopVar6;
 457   mParent[LoopVar4]    = NIL;
 458
 459   //
 460   // Special usage of 'next'
 461   //
 462   mNext[LoopVar4] = mPos;
 463
 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     CopyMem (Temp, &mText[WNDSIZ], WNDSIZ + MAXMATCH);
 613     CopyMem (&mText[0], Temp, WNDSIZ + MAXMATCH);
 614     FreePool (Temp);
 615     LoopVar8 = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
 616     mRemainder += LoopVar8;
 617     mPos = WNDSIZ;
 618   }
 619
 620   DeleteNode ();
 621   InsertNode ();
 622
 623   return (TRUE);
 624 }
 625
 626 /**
 627   Send entry LoopVar1 down the queue.
 628
 629   @param[in] LoopVar1    The index of the item to move.
 630 **/
 631 VOID
 632 DownHeap (
 633   IN INT32 i
 634   )
 635 {
 636   INT32 LoopVar1;
 637
 638   INT32 LoopVar2;
 639
 640   //
 641   // priority queue: send i-th entry down heap
 642   //
 643   LoopVar2 = mHeap[i];
 644   LoopVar1 = 2 * i;
 645   while (LoopVar1 <= mHeapSize) {
 646     if (LoopVar1 < mHeapSize && mFreq[mHeap[LoopVar1]] > mFreq[mHeap[LoopVar1 + 1]]) {
 647       LoopVar1++;
 648     }
 649
 650     if (mFreq[LoopVar2] <= mFreq[mHeap[LoopVar1]]) {
 651       break;
 652     }
 653
 654     mHeap[i]  = mHeap[LoopVar1];
 655     i         = LoopVar1;
 656     LoopVar1         = 2 * i;
 657   }
 658
 659   mHeap[i] = (INT16) LoopVar2;
 660 }
 661
 662 /**
 663   Count the number of each code length for a Huffman tree.
 664
 665   @param[in] LoopVar1      The top node.
 666 **/
 667 VOID
 668 CountLen (
 669   IN INT32 LoopVar1
 670   )
 671 {
 672   if (LoopVar1 < mTempInt32) {
 673     mLenCnt[(mHuffmanDepth < 16) ? mHuffmanDepth : 16]++;
 674   } else {
 675     mHuffmanDepth++;
 676     CountLen (mLeft[LoopVar1]);
 677     CountLen (mRight[LoopVar1]);
 678     mHuffmanDepth--;
 679   }
 680 }
 681
 682 /**
 683   Create code length array for a Huffman tree.
 684
 685   @param[in] Root   The root of the tree.
 686 **/
 687 VOID
 688 MakeLen (
 689   IN INT32 Root
 690   )
 691 {
 692   INT32   LoopVar1;
 693
 694   INT32   LoopVar2;
 695   UINT32  Cum;
 696
 697   for (LoopVar1 = 0; LoopVar1 <= 16; LoopVar1++) {
 698     mLenCnt[LoopVar1] = 0;
 699   }
 700
 701   CountLen (Root);
 702
 703   //
 704   // Adjust the length count array so that
 705   // no code will be generated longer than its designated length
 706   //
 707   Cum = 0;
 708   for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
 709     Cum += mLenCnt[LoopVar1] << (16 - LoopVar1);
 710   }
 711
 712   while (Cum != (1U << 16)) {
 713     mLenCnt[16]--;
 714     for (LoopVar1 = 15; LoopVar1 > 0; LoopVar1--) {
 715       if (mLenCnt[LoopVar1] != 0) {
 716         mLenCnt[LoopVar1]--;
 717         mLenCnt[LoopVar1 + 1] += 2;
 718         break;
 719       }
 720     }
 721
 722     Cum--;
 723   }
 724
 725   for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
 726     LoopVar2 = mLenCnt[LoopVar1];
 727     LoopVar2--;
 728     while (LoopVar2 >= 0) {
 729       mLen[*mSortPtr++] = (UINT8) LoopVar1;
 730       LoopVar2--;
 731     }
 732   }
 733 }
 734
 735 /**
 736   Assign code to each symbol based on the code length array.
 737
 738   @param[in] LoopVar8      The number of symbols.
 739   @param[in] Len    The code length array.
 740   @param[out] Code  The stores codes for each symbol.
 741 **/
 742 VOID
 743 MakeCode (
 744   IN  INT32         LoopVar8,
 745   IN  UINT8 Len[    ],
 746   OUT UINT16 Code[  ]
 747   )
 748 {
 749   INT32   LoopVar1;
 750   UINT16  Start[18];
 751
 752   Start[1] = 0;
 753   for (LoopVar1 = 1; LoopVar1 <= 16; LoopVar1++) {
 754     Start[LoopVar1 + 1] = (UINT16) ((Start[LoopVar1] + mLenCnt[LoopVar1]) << 1);
 755   }
 756
 757   for (LoopVar1 = 0; LoopVar1 < LoopVar8; LoopVar1++) {
 758     Code[LoopVar1] = Start[Len[LoopVar1]]++;
 759   }
 760 }
 761
 762 /**
 763   Generates Huffman codes given a frequency distribution of symbols.
 764
 765   @param[in] NParm      The number of symbols.
 766   @param[in] FreqParm   The frequency of each symbol.
 767   @param[out] LenParm   The code length for each symbol.
 768   @param[out] CodeParm  The code for each symbol.
 769
 770   @return The root of the Huffman tree.
 771 **/
 772 INT32
 773 MakeTree (
 774   IN  INT32             NParm,
 775   IN  UINT16  FreqParm[ ],
 776   OUT UINT8   LenParm[  ],
 777   OUT UINT16  CodeParm[ ]
 778   )
 779 {
 780   INT32 LoopVar1;
 781
 782   INT32 LoopVar2;
 783
 784   INT32 LoopVar3;
 785
 786   INT32 Avail;
 787
 788   //
 789   // make tree, calculate len[], return root
 790   //
 791   mTempInt32        = NParm;
 792   mFreq     = FreqParm;
 793   mLen      = LenParm;
 794   Avail     = mTempInt32;
 795   mHeapSize = 0;
 796   mHeap[1]  = 0;
 797   for (LoopVar1 = 0; LoopVar1 < mTempInt32; LoopVar1++) {
 798     mLen[LoopVar1] = 0;
 799     if ((mFreq[LoopVar1]) != 0) {
 800       mHeapSize++;
 801       mHeap[mHeapSize] = (INT16) LoopVar1;
 802     }
 803   }
 804
 805   if (mHeapSize < 2) {
 806     CodeParm[mHeap[1]] = 0;
 807     return mHeap[1];
 808   }
 809
 810   for (LoopVar1 = mHeapSize / 2; LoopVar1 >= 1; LoopVar1--) {
 811     //
 812     // make priority queue
 813     //
 814     DownHeap (LoopVar1);
 815   }
 816
 817   mSortPtr = CodeParm;
 818   do {
 819     LoopVar1 = mHeap[1];
 820     if (LoopVar1 < mTempInt32) {
 821       *mSortPtr++ = (UINT16) LoopVar1;
 822     }
 823
 824     mHeap[1] = mHeap[mHeapSize--];
 825     DownHeap (1);
 826     LoopVar2 = mHeap[1];
 827     if (LoopVar2 < mTempInt32) {
 828       *mSortPtr++ = (UINT16) LoopVar2;
 829     }
 830
 831     LoopVar3         = Avail++;
 832     mFreq[LoopVar3]  = (UINT16) (mFreq[LoopVar1] + mFreq[LoopVar2]);
 833     mHeap[1]  = (INT16) LoopVar3;
 834     DownHeap (1);
 835     mLeft[LoopVar3]  = (UINT16) LoopVar1;
 836     mRight[LoopVar3] = (UINT16) LoopVar2;
 837   } while (mHeapSize > 1);
 838
 839   mSortPtr = CodeParm;
 840   MakeLen (LoopVar3);
 841   MakeCode (NParm, LenParm, CodeParm);
 842
 843   //
 844   // return root
 845   //
 846   return LoopVar3;
 847 }
 848
 849 /**
 850   Outputs rightmost LoopVar8 bits of x
 851
 852   @param[in] LoopVar8   The rightmost LoopVar8 bits of the data is used.
 853   @param[in] x   The data.
 854 **/
 855 VOID
 856 PutBits (
 857   IN INT32    LoopVar8,
 858   IN UINT32   x
 859   )
 860 {
 861   UINT8 Temp;
 862
 863   if (LoopVar8 < mBitCount) {
 864     mSubBitBuf |= x << (mBitCount -= LoopVar8);
 865   } else {
 866
 867     Temp = (UINT8)(mSubBitBuf | (x >> (LoopVar8 -= mBitCount)));
 868     if (mDst < mDstUpperLimit) {
 869       *mDst++ = Temp;
 870     }
 871     mCompSize++;
 872
 873     if (LoopVar8 < UINT8_BIT) {
 874       mSubBitBuf = x << (mBitCount = UINT8_BIT - LoopVar8);
 875     } else {
 876
 877       Temp = (UINT8)(x >> (LoopVar8 - UINT8_BIT));
 878       if (mDst < mDstUpperLimit) {
 879         *mDst++ = Temp;
 880       }
 881       mCompSize++;
 882
 883       mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - LoopVar8);
 884     }
 885   }
 886 }
 887
 888 /**
 889   Encode a signed 32 bit number.
 890
 891   @param[in] LoopVar5     The number to encode.
 892 **/
 893 VOID
 894 EncodeC (
 895   IN INT32 LoopVar5
 896   )
 897 {
 898   PutBits (mCLen[LoopVar5], mCCode[LoopVar5]);
 899 }
 900
 901 /**
 902   Encode a unsigned 32 bit number.
 903
 904   @param[in] LoopVar7     The number to encode.
 905 **/
 906 VOID
 907 EncodeP (
 908   IN UINT32 LoopVar7
 909   )
 910 {
 911   UINT32  LoopVar5;
 912
 913   UINT32  LoopVar6;
 914
 915   LoopVar5 = 0;
 916   LoopVar6 = LoopVar7;
 917   while (LoopVar6 != 0) {
 918     LoopVar6 >>= 1;
 919     LoopVar5++;
 920   }
 921
 922   PutBits (mPTLen[LoopVar5], mPTCode[LoopVar5]);
 923   if (LoopVar5 > 1) {
 924     PutBits(LoopVar5 - 1, LoopVar7 & (0xFFFFU >> (17 - LoopVar5)));
 925   }
 926 }
 927
 928 /**
 929   Count the frequencies for the Extra Set.
 930
 931 **/
 932 VOID
 933 CountTFreq (
 934   VOID
 935   )
 936 {
 937   INT32 LoopVar1;
 938
 939   INT32 LoopVar3;
 940
 941   INT32 LoopVar8;
 942
 943   INT32 Count;
 944
 945   for (LoopVar1 = 0; LoopVar1 < NT; LoopVar1++) {
 946     mTFreq[LoopVar1] = 0;
 947   }
 948
 949   LoopVar8 = NC;
 950   while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
 951     LoopVar8--;
 952   }
 953
 954   LoopVar1 = 0;
 955   while (LoopVar1 < LoopVar8) {
 956     LoopVar3 = mCLen[LoopVar1++];
 957     if (LoopVar3 == 0) {
 958       Count = 1;
 959       while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
 960         LoopVar1++;
 961         Count++;
 962       }
 963
 964       if (Count <= 2) {
 965         mTFreq[0] = (UINT16) (mTFreq[0] + Count);
 966       } else if (Count <= 18) {
 967         mTFreq[1]++;
 968       } else if (Count == 19) {
 969         mTFreq[0]++;
 970         mTFreq[1]++;
 971       } else {
 972         mTFreq[2]++;
 973       }
 974     } else {
 975       ASSERT((LoopVar3+2)<(2 * NT - 1));
 976       mTFreq[LoopVar3 + 2]++;
 977     }
 978   }
 979 }
 980
 981 /**
 982   Outputs the code length array for the Extra Set or the Position Set.
 983
 984   @param[in] LoopVar8       The number of symbols.
 985   @param[in] nbit           The number of bits needed to represent 'LoopVar8'.
 986   @param[in] Special        The special symbol that needs to be take care of.
 987
 988 **/
 989 VOID
 990 WritePTLen (
 991   IN INT32 LoopVar8,
 992   IN INT32 nbit,
 993   IN INT32 Special
 994   )
 995 {
 996   INT32 LoopVar1;
 997
 998   INT32 LoopVar3;
 999
1000   while (LoopVar8 > 0 && mPTLen[LoopVar8 - 1] == 0) {
1001     LoopVar8--;
1002   }
1003
1004   PutBits (nbit, LoopVar8);
1005   LoopVar1 = 0;
1006   while (LoopVar1 < LoopVar8) {
1007     LoopVar3 = mPTLen[LoopVar1++];
1008     if (LoopVar3 <= 6) {
1009       PutBits (3, LoopVar3);
1010     } else {
1011       PutBits (LoopVar3 - 3, (1U << (LoopVar3 - 3)) - 2);
1012     }
1013
1014     if (LoopVar1 == Special) {
1015       while (LoopVar1 < 6 && mPTLen[LoopVar1] == 0) {
1016         LoopVar1++;
1017       }
1018
1019       PutBits (2, (LoopVar1 - 3) & 3);
1020     }
1021   }
1022 }
1023
1024 /**
1025   Outputs the code length array for Char&Length Set.
1026 **/
1027 VOID
1028 WriteCLen (
1029   VOID
1030   )
1031 {
1032   INT32 LoopVar1;
1033
1034   INT32 LoopVar3;
1035
1036   INT32 LoopVar8;
1037
1038   INT32 Count;
1039
1040   LoopVar8 = NC;
1041   while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
1042     LoopVar8--;
1043   }
1044
1045   PutBits (CBIT, LoopVar8);
1046   LoopVar1 = 0;
1047   while (LoopVar1 < LoopVar8) {
1048     LoopVar3 = mCLen[LoopVar1++];
1049     if (LoopVar3 == 0) {
1050       Count = 1;
1051       while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
1052         LoopVar1++;
1053         Count++;
1054       }
1055
1056       if (Count <= 2) {
1057         for (LoopVar3 = 0; LoopVar3 < Count; LoopVar3++) {
1058           PutBits (mPTLen[0], mPTCode[0]);
1059         }
1060       } else if (Count <= 18) {
1061         PutBits (mPTLen[1], mPTCode[1]);
1062         PutBits (4, Count - 3);
1063       } else if (Count == 19) {
1064         PutBits (mPTLen[0], mPTCode[0]);
1065         PutBits (mPTLen[1], mPTCode[1]);
1066         PutBits (4, 15);
1067       } else {
1068         PutBits (mPTLen[2], mPTCode[2]);
1069         PutBits (CBIT, Count - 20);
1070       }
1071     } else {
1072       ASSERT((LoopVar3+2)<NPT);
1073       PutBits (mPTLen[LoopVar3 + 2], mPTCode[LoopVar3 + 2]);
1074     }
1075   }
1076 }
1077
1078 /**
1079   Huffman code the block and output it.
1080
1081 **/
1082 VOID
1083 SendBlock (
1084   VOID
1085   )
1086 {
1087   UINT32  LoopVar1;
1088
1089   UINT32  LoopVar3;
1090
1091   UINT32  Flags;
1092
1093   UINT32  Root;
1094
1095   UINT32  Pos;
1096
1097   UINT32  Size;
1098   Flags = 0;
1099
1100   Root  = MakeTree (NC, mCFreq, mCLen, mCCode);
1101   Size  = mCFreq[Root];
1102   PutBits (16, Size);
1103   if (Root >= NC) {
1104     CountTFreq ();
1105     Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
1106     if (Root >= NT) {
1107       WritePTLen (NT, TBIT, 3);
1108     } else {
1109       PutBits (TBIT, 0);
1110       PutBits (TBIT, Root);
1111     }
1112
1113     WriteCLen ();
1114   } else {
1115     PutBits (TBIT, 0);
1116     PutBits (TBIT, 0);
1117     PutBits (CBIT, 0);
1118     PutBits (CBIT, Root);
1119   }
1120
1121   Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
1122   if (Root >= NP) {
1123     WritePTLen (NP, PBIT, -1);
1124   } else {
1125     PutBits (PBIT, 0);
1126     PutBits (PBIT, Root);
1127   }
1128
1129   Pos = 0;
1130   for (LoopVar1 = 0; LoopVar1 < Size; LoopVar1++) {
1131     if (LoopVar1 % UINT8_BIT == 0) {
1132       Flags = mBuf[Pos++];
1133     } else {
1134       Flags <<= 1;
1135     }
1136     if ((Flags & (1U << (UINT8_BIT - 1))) != 0){
1137       EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
1138       LoopVar3 = mBuf[Pos++] << UINT8_BIT;
1139       LoopVar3 += mBuf[Pos++];
1140
1141       EncodeP (LoopVar3);
1142     } else {
1143       EncodeC (mBuf[Pos++]);
1144     }
1145   }
1146
1147   SetMem (mCFreq, NC * sizeof (UINT16), 0);
1148   SetMem (mPFreq, NP * sizeof (UINT16), 0);
1149 }
1150
1151 /**
1152   Start the huffman encoding.
1153
1154 **/
1155 VOID
1156 HufEncodeStart (
1157   VOID
1158   )
1159 {
1160   SetMem (mCFreq, NC * sizeof (UINT16), 0);
1161   SetMem (mPFreq, NP * sizeof (UINT16), 0);
1162
1163   mOutputPos = mOutputMask = 0;
1164
1165   mBitCount   = UINT8_BIT;
1166   mSubBitBuf  = 0;
1167 }
1168
1169 /**
1170   Outputs an Original Character or a Pointer.
1171
1172   @param[in] LoopVar5     The original character or the 'String Length' element of
1173                    a Pointer.
1174   @param[in] LoopVar7     The 'Position' field of a Pointer.
1175 **/
1176 VOID
1177 CompressOutput (
1178   IN UINT32 LoopVar5,
1179   IN UINT32 LoopVar7
1180   )
1181 {
1182   STATIC UINT32 CPos;
1183
1184   if ((mOutputMask >>= 1) == 0) {
1185     mOutputMask = 1U << (UINT8_BIT - 1);
1186     if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
1187       SendBlock ();
1188       mOutputPos = 0;
1189     }
1190
1191     CPos        = mOutputPos++;
1192     mBuf[CPos]  = 0;
1193   }
1194   mBuf[mOutputPos++] = (UINT8) LoopVar5;
1195   mCFreq[LoopVar5]++;
1196   if (LoopVar5 >= (1U << UINT8_BIT)) {
1197     mBuf[CPos] = (UINT8)(mBuf[CPos]|mOutputMask);
1198     mBuf[mOutputPos++] = (UINT8)(LoopVar7 >> UINT8_BIT);
1199     mBuf[mOutputPos++] = (UINT8) LoopVar7;
1200     LoopVar5                  = 0;
1201     while (LoopVar7!=0) {
1202       LoopVar7 >>= 1;
1203       LoopVar5++;
1204     }
1205     mPFreq[LoopVar5]++;
1206   }
1207 }
1208
1209 /**
1210   End the huffman encoding.
1211
1212 **/
1213 VOID
1214 HufEncodeEnd (
1215   VOID
1216   )
1217 {
1218   SendBlock ();
1219
1220   //
1221   // Flush remaining bits
1222   //
1223   PutBits (UINT8_BIT - 1, 0);
1224 }
1225
1226 /**
1227   The main controlling routine for compression process.
1228
1229   @retval EFI_SUCCESS           The compression is successful.
1230   @retval EFI_OUT_0F_RESOURCES  Not enough memory for compression process.
1231 **/
1232 EFI_STATUS
1233 Encode (
1234   VOID
1235   )
1236 {
1237   EFI_STATUS  Status;
1238   INT32       LastMatchLen;
1239   NODE        LastMatchPos;
1240
1241   Status = AllocateMemory ();
1242   if (EFI_ERROR (Status)) {
1243     FreeMemory ();
1244     return Status;
1245   }
1246
1247   InitSlide ();
1248
1249   HufEncodeStart ();
1250
1251   mRemainder  = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
1252
1253   mMatchLen   = 0;
1254   mPos        = WNDSIZ;
1255   InsertNode ();
1256   if (mMatchLen > mRemainder) {
1257     mMatchLen = mRemainder;
1258   }
1259
1260   while (mRemainder > 0) {
1261     LastMatchLen  = mMatchLen;
1262     LastMatchPos  = mMatchPos;
1263     if (!GetNextMatch ()) {
1264       Status = EFI_OUT_OF_RESOURCES;
1265     }
1266     if (mMatchLen > mRemainder) {
1267       mMatchLen = mRemainder;
1268     }
1269
1270     if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
1271       //
1272       // Not enough benefits are gained by outputting a pointer,
1273       // so just output the original character
1274       //
1275       CompressOutput(mText[mPos - 1], 0);
1276     } else {
1277       //
1278       // Outputting a pointer is beneficial enough, do it.
1279       //
1280
1281       CompressOutput(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
1282              (mPos - LastMatchPos - 2) & (WNDSIZ - 1));
1283       LastMatchLen--;
1284       while (LastMatchLen > 0) {
1285         if (!GetNextMatch ()) {
1286           Status = EFI_OUT_OF_RESOURCES;
1287         }
1288         LastMatchLen--;
1289       }
1290
1291       if (mMatchLen > mRemainder) {
1292         mMatchLen = mRemainder;
1293       }
1294     }
1295   }
1296
1297   HufEncodeEnd ();
1298   FreeMemory ();
1299   return (Status);
1300 }
1301
1302 /**
1303   The compression routine.
1304
1305   @param[in]       SrcBuffer     The buffer containing the source data.
1306   @param[in]       SrcSize       Number of bytes in SrcBuffer.
1307   @param[in]       DstBuffer     The buffer to put the compressed image in.
1308   @param[in, out]  DstSize       On input the size (in bytes) of DstBuffer, on
1309                                  return the number of bytes placed in DstBuffer.
1310
1311   @retval EFI_SUCCESS           The compression was sucessful.
1312   @retval EFI_BUFFER_TOO_SMALL  The buffer was too small.  DstSize is required.
1313 **/
1314 EFI_STATUS
1315 Compress (
1316   IN      VOID    *SrcBuffer,
1317   IN      UINT64  SrcSize,
1318   IN      VOID    *DstBuffer,
1319   IN OUT  UINT64  *DstSize
1320   )
1321 {
1322   EFI_STATUS  Status;
1323
1324   //
1325   // Initializations
1326   //
1327   mBufSiz         = 0;
1328   mBuf            = NULL;
1329   mText           = NULL;
1330   mLevel          = NULL;
1331   mChildCount     = NULL;
1332   mPosition       = NULL;
1333   mParent         = NULL;
1334   mPrev           = NULL;
1335   mNext           = NULL;
1336
1337   mSrc            = SrcBuffer;
1338   mSrcUpperLimit  = mSrc + SrcSize;
1339   mDst            = DstBuffer;
1340   mDstUpperLimit  = mDst +*DstSize;
1341
1342   PutDword (0L);
1343   PutDword (0L);
1344
1345   MakeCrcTable ();
1346
1347   mOrigSize             = mCompSize = 0;
1348   mCrc                  = INIT_CRC;
1349
1350   //
1351   // Compress it
1352   //
1353   Status = Encode ();
1354   if (EFI_ERROR (Status)) {
1355     return EFI_OUT_OF_RESOURCES;
1356   }
1357   //
1358   // Null terminate the compressed data
1359   //
1360   if (mDst < mDstUpperLimit) {
1361     *mDst++ = 0;
1362   }
1363   //
1364   // Fill in compressed size and original size
1365   //
1366   mDst = DstBuffer;
1367   PutDword (mCompSize + 1);
1368   PutDword (mOrigSize);
1369
1370   //
1371   // Return
1372   //
1373   if (mCompSize + 1 + 8 > *DstSize) {
1374     *DstSize = mCompSize + 1 + 8;
1375     return EFI_BUFFER_TOO_SMALL;
1376   } else {
1377     *DstSize = mCompSize + 1 + 8;
1378     return EFI_SUCCESS;
1379   }
1380
1381 }
1382