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