[mirror_edk2.git] / ShellPkg / Library / UefiShellDebug1CommandsLib / Compress.c

/** @file\r
  Main file for compression routine.\r
\r
  Compression routine. The compression algorithm is a mixture of\r
  LZ77 and Huffman coding. LZ77 transforms the source data into a\r
  sequence of Original Characters and Pointers to repeated strings.\r
  This sequence is further divided into Blocks and Huffman codings\r
  are applied to each Block.\r
\r
  Copyright (c) 2007 - 2018, Intel Corporation. All rights reserved.<BR>\r
  SPDX-License-Identifier: BSD-2-Clause-Patent\r
\r
**/\r
#include <Uefi.h>\r
#include <Library/MemoryAllocationLib.h>\r
#include <Library/BaseMemoryLib.h>\r
#include <Library/DebugLib.h>\r
#include <Library/ShellLib.h>\r
\r
#include "Compress.h"\r
\r
//\r
// Macro Definitions\r
//\r
typedef INT16 NODE;\r
#define UINT8_MAX     0xff\r
#define UINT8_BIT     8\r
#define THRESHOLD     3\r
#define INIT_CRC      0\r
#define WNDBIT        13\r
#define WNDSIZ        (1U << WNDBIT)\r
#define MAXMATCH      256\r
#define BLKSIZ        (1U << 14)      // 16 * 1024U\r
#define PERC_FLAG     0x8000U\r
#define CODE_BIT      16\r
#define NIL           0\r
#define MAX_HASH_VAL  (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)\r
#define HASH(LoopVar7, LoopVar5)  ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)\r
#define CRCPOLY  0xA001\r
#define UPDATE_CRC(LoopVar5)  mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)\r
\r
//\r
// C: the Char&Len Set; P: the Position Set; T: the exTra Set\r
//\r
#define NC    (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)\r
#define CBIT  9\r
#define NP    (WNDBIT + 1)\r
#define PBIT  4\r
#define NT    (CODE_BIT + 3)\r
#define TBIT  5\r
#if NT > NP\r
#define                 NPT  NT\r
#else\r
#define                 NPT  NP\r
#endif\r
//\r
// Function Prototypes\r
//\r
\r
/**\r
  Put a dword to output stream\r
\r
  @param[in] Data    The dword to put.\r
**/\r
VOID\r
PutDword (\r
  IN UINT32  Data\r
  );\r
\r
//\r
//  Global Variables\r
//\r
STATIC UINT8  *mSrc;\r
STATIC UINT8  *mDst;\r
STATIC UINT8  *mSrcUpperLimit;\r
STATIC UINT8  *mDstUpperLimit;\r
\r
STATIC UINT8   *mLevel;\r
STATIC UINT8   *mText;\r
STATIC UINT8   *mChildCount;\r
STATIC UINT8   *mBuf;\r
STATIC UINT8   mCLen[NC];\r
STATIC UINT8   mPTLen[NPT];\r
STATIC UINT8   *mLen;\r
STATIC INT16   mHeap[NC + 1];\r
STATIC INT32   mRemainder;\r
STATIC INT32   mMatchLen;\r
STATIC INT32   mBitCount;\r
STATIC INT32   mHeapSize;\r
STATIC INT32   mTempInt32;\r
STATIC UINT32  mBufSiz = 0;\r
STATIC UINT32  mOutputPos;\r
STATIC UINT32  mOutputMask;\r
STATIC UINT32  mSubBitBuf;\r
STATIC UINT32  mCrc;\r
STATIC UINT32  mCompSize;\r
STATIC UINT32  mOrigSize;\r
\r
STATIC UINT16  *mFreq;\r
STATIC UINT16  *mSortPtr;\r
STATIC UINT16  mLenCnt[17];\r
STATIC UINT16  mLeft[2 * NC - 1];\r
STATIC UINT16  mRight[2 * NC - 1];\r
STATIC UINT16  mCrcTable[UINT8_MAX + 1];\r
STATIC UINT16  mCFreq[2 * NC - 1];\r
STATIC UINT16  mCCode[NC];\r
STATIC UINT16  mPFreq[2 * NP - 1];\r
STATIC UINT16  mPTCode[NPT];\r
STATIC UINT16  mTFreq[2 * NT - 1];\r
\r
STATIC NODE  mPos;\r
STATIC NODE  mMatchPos;\r
STATIC NODE  mAvail;\r
STATIC NODE  *mPosition;\r
STATIC NODE  *mParent;\r
STATIC NODE  *mPrev;\r
STATIC NODE  *mNext        = NULL;\r
INT32        mHuffmanDepth = 0;\r
\r
/**\r
  Make a CRC table.\r
\r
**/\r
VOID\r
MakeCrcTable (\r
  VOID\r
  )\r
{\r
  UINT32  LoopVar1;\r
\r
  UINT32  LoopVar2;\r
\r
  UINT32  LoopVar4;\r
\r
  for (LoopVar1 = 0; LoopVar1 <= UINT8_MAX; LoopVar1++) {\r
    LoopVar4 = LoopVar1;\r
    for (LoopVar2 = 0; LoopVar2 < UINT8_BIT; LoopVar2++) {\r
      if ((LoopVar4 & 1) != 0) {\r
        LoopVar4 = (LoopVar4 >> 1) ^ CRCPOLY;\r
      } else {\r
        LoopVar4 >>= 1;\r
      }\r
    }\r
\r
    mCrcTable[LoopVar1] = (UINT16)LoopVar4;\r
  }\r
}\r
\r
/**\r
  Put a dword to output stream\r
\r
  @param[in] Data    The dword to put.\r
**/\r
VOID\r
PutDword (\r
  IN UINT32  Data\r
  )\r
{\r
  if (mDst < mDstUpperLimit) {\r
    *mDst++ = (UINT8)(((UINT8)(Data)) & 0xff);\r
  }\r
\r
  if (mDst < mDstUpperLimit) {\r
    *mDst++ = (UINT8)(((UINT8)(Data >> 0x08)) & 0xff);\r
  }\r
\r
  if (mDst < mDstUpperLimit) {\r
    *mDst++ = (UINT8)(((UINT8)(Data >> 0x10)) & 0xff);\r
  }\r
\r
  if (mDst < mDstUpperLimit) {\r
    *mDst++ = (UINT8)(((UINT8)(Data >> 0x18)) & 0xff);\r
  }\r
}\r
\r
/**\r
  Allocate memory spaces for data structures used in compression process.\r
\r
  @retval EFI_SUCCESS           Memory was allocated successfully.\r
  @retval EFI_OUT_OF_RESOURCES  A memory allocation failed.\r
**/\r
EFI_STATUS\r
AllocateMemory (\r
  VOID\r
  )\r
{\r
  mText       = AllocateZeroPool (WNDSIZ * 2 + MAXMATCH);\r
  mLevel      = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));\r
  mChildCount = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));\r
  mPosition   = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));\r
  mParent     = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mParent));\r
  mPrev       = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mPrev));\r
  mNext       = AllocateZeroPool ((MAX_HASH_VAL + 1) * sizeof (*mNext));\r
\r
  mBufSiz = BLKSIZ;\r
  mBuf    = AllocateZeroPool (mBufSiz);\r
  while (mBuf == NULL) {\r
    mBufSiz = (mBufSiz / 10U) * 9U;\r
    if (mBufSiz < 4 * 1024U) {\r
      return EFI_OUT_OF_RESOURCES;\r
    }\r
\r
    mBuf = AllocateZeroPool (mBufSiz);\r
  }\r
\r
  mBuf[0] = 0;\r
\r
  return EFI_SUCCESS;\r
}\r
\r
/**\r
  Called when compression is completed to free memory previously allocated.\r
\r
**/\r
VOID\r
FreeMemory (\r
  VOID\r
  )\r
{\r
  SHELL_FREE_NON_NULL (mText);\r
  SHELL_FREE_NON_NULL (mLevel);\r
  SHELL_FREE_NON_NULL (mChildCount);\r
  SHELL_FREE_NON_NULL (mPosition);\r
  SHELL_FREE_NON_NULL (mParent);\r
  SHELL_FREE_NON_NULL (mPrev);\r
  SHELL_FREE_NON_NULL (mNext);\r
  SHELL_FREE_NON_NULL (mBuf);\r
}\r
\r
/**\r
  Initialize String Info Log data structures.\r
**/\r
VOID\r
InitSlide (\r
  VOID\r
  )\r
{\r
  NODE  LoopVar1;\r
\r
  SetMem (mLevel + WNDSIZ, (UINT8_MAX + 1) * sizeof (UINT8), 1);\r
  SetMem (mPosition + WNDSIZ, (UINT8_MAX + 1) * sizeof (NODE), 0);\r
\r
  SetMem (mParent + WNDSIZ, WNDSIZ * sizeof (NODE), 0);\r
\r
  mAvail = 1;\r
  for (LoopVar1 = 1; LoopVar1 < WNDSIZ - 1; LoopVar1++) {\r
    mNext[LoopVar1] = (NODE)(LoopVar1 + 1);\r
  }\r
\r
  mNext[WNDSIZ - 1] = NIL;\r
  SetMem (mNext + WNDSIZ * 2, (MAX_HASH_VAL - WNDSIZ * 2 + 1) * sizeof (NODE), 0);\r
}\r
\r
/**\r
  Find child node given the parent node and the edge character\r
\r
  @param[in] LoopVar6       The parent node.\r
  @param[in] LoopVar5       The edge character.\r
\r
  @return             The child node.\r
  @retval NIL(Zero)   No child could be found.\r
\r
**/\r
NODE\r
Child (\r
  IN NODE   LoopVar6,\r
  IN UINT8  LoopVar5\r
  )\r
{\r
  NODE  LoopVar4;\r
\r
  LoopVar4     = mNext[HASH (LoopVar6, LoopVar5)];\r
  mParent[NIL] = LoopVar6;   /* sentinel */\r
  while (mParent[LoopVar4] != LoopVar6) {\r
    LoopVar4 = mNext[LoopVar4];\r
  }\r
\r
  return LoopVar4;\r
}\r
\r
/**\r
  Create a new child for a given parent node.\r
\r
  @param[in] LoopVar6       The parent node.\r
  @param[in] LoopVar5       The edge character.\r
  @param[in] LoopVar4       The child node.\r
**/\r
VOID\r
MakeChild (\r
  IN NODE   LoopVar6,\r
  IN UINT8  LoopVar5,\r
  IN NODE   LoopVar4\r
  )\r
{\r
  NODE  LoopVar12;\r
\r
  NODE  LoopVar10;\r
\r
  LoopVar12         = (NODE)HASH (LoopVar6, LoopVar5);\r
  LoopVar10         = mNext[LoopVar12];\r
  mNext[LoopVar12]  = LoopVar4;\r
  mNext[LoopVar4]   = LoopVar10;\r
  mPrev[LoopVar10]  = LoopVar4;\r
  mPrev[LoopVar4]   = LoopVar12;\r
  mParent[LoopVar4] = LoopVar6;\r
  mChildCount[LoopVar6]++;\r
}\r
\r
/**\r
  Split a node.\r
\r
  @param[in] Old     The node to split.\r
**/\r
VOID\r
Split (\r
  IN NODE  Old\r
  )\r
{\r
  NODE  New;\r
\r
  NODE  LoopVar10;\r
\r
  New              = mAvail;\r
  mAvail           = mNext[New];\r
  mChildCount[New] = 0;\r
  LoopVar10        = mPrev[Old];\r
  mPrev[New]       = LoopVar10;\r
  mNext[LoopVar10] = New;\r
  LoopVar10        = mNext[Old];\r
  mNext[New]       = LoopVar10;\r
  mPrev[LoopVar10] = New;\r
  mParent[New]     = mParent[Old];\r
  mLevel[New]      = (UINT8)mMatchLen;\r
  mPosition[New]   = mPos;\r
  MakeChild (New, mText[mMatchPos + mMatchLen], Old);\r
  MakeChild (New, mText[mPos + mMatchLen], mPos);\r
}\r
\r
/**\r
  Insert string info for current position into the String Info Log.\r
\r
**/\r
VOID\r
InsertNode (\r
  VOID\r
  )\r
{\r
  NODE  LoopVar6;\r
\r
  NODE  LoopVar4;\r
\r
  NODE  LoopVar2;\r
\r
  NODE   LoopVar10;\r
  UINT8  LoopVar5;\r
  UINT8  *TempString3;\r
  UINT8  *TempString2;\r
\r
  if (mMatchLen >= 4) {\r
    //\r
    // We have just got a long match, the target tree\r
    // can be located by MatchPos + 1. Travese the tree\r
    // from bottom up to get to a proper starting point.\r
    // The usage of PERC_FLAG ensures proper node deletion\r
    // in DeleteNode() later.\r
    //\r
    mMatchLen--;\r
    LoopVar4 = (NODE)((mMatchPos + 1) | WNDSIZ);\r
    LoopVar6 = mParent[LoopVar4];\r
    while (LoopVar6 == NIL) {\r
      LoopVar4 = mNext[LoopVar4];\r
      LoopVar6 = mParent[LoopVar4];\r
    }\r
\r
    while (mLevel[LoopVar6] >= mMatchLen) {\r
      LoopVar4 = LoopVar6;\r
      LoopVar6 = mParent[LoopVar6];\r
    }\r
\r
    LoopVar10 = LoopVar6;\r
    while (mPosition[LoopVar10] < 0) {\r
      mPosition[LoopVar10] = mPos;\r
      LoopVar10            = mParent[LoopVar10];\r
    }\r
\r
    if (LoopVar10 < WNDSIZ) {\r
      mPosition[LoopVar10] = (NODE)(mPos | PERC_FLAG);\r
    }\r
  } else {\r
    //\r
    // Locate the target tree\r
    //\r
    LoopVar6 = (NODE)(mText[mPos] + WNDSIZ);\r
    LoopVar5 = mText[mPos + 1];\r
    LoopVar4 = Child (LoopVar6, LoopVar5);\r
    if (LoopVar4 == NIL) {\r
      MakeChild (LoopVar6, LoopVar5, mPos);\r
      mMatchLen = 1;\r
      return;\r
    }\r
\r
    mMatchLen = 2;\r
  }\r
\r
  //\r
  // Traverse down the tree to find a match.\r
  // Update Position value along the route.\r
  // Node split or creation is involved.\r
  //\r
  for ( ; ;) {\r
    if (LoopVar4 >= WNDSIZ) {\r
      LoopVar2  = MAXMATCH;\r
      mMatchPos = LoopVar4;\r
    } else {\r
      LoopVar2  = mLevel[LoopVar4];\r
      mMatchPos = (NODE)(mPosition[LoopVar4] & ~PERC_FLAG);\r
    }\r
\r
    if (mMatchPos >= mPos) {\r
      mMatchPos -= WNDSIZ;\r
    }\r
\r
    TempString3 = &mText[mPos + mMatchLen];\r
    TempString2 = &mText[mMatchPos + mMatchLen];\r
    while (mMatchLen < LoopVar2) {\r
      if (*TempString3 != *TempString2) {\r
        Split (LoopVar4);\r
        return;\r
      }\r
\r
      mMatchLen++;\r
      TempString3++;\r
      TempString2++;\r
    }\r
\r
    if (mMatchLen >= MAXMATCH) {\r
      break;\r
    }\r
\r
    mPosition[LoopVar4] = mPos;\r
    LoopVar6            = LoopVar4;\r
    LoopVar4            = Child (LoopVar6, *TempString3);\r
    if (LoopVar4 == NIL) {\r
      MakeChild (LoopVar6, *TempString3, mPos);\r
      return;\r
    }\r
\r
    mMatchLen++;\r
  }\r
\r
  LoopVar10         = mPrev[LoopVar4];\r
  mPrev[mPos]       = LoopVar10;\r
  mNext[LoopVar10]  = mPos;\r
  LoopVar10         = mNext[LoopVar4];\r
  mNext[mPos]       = LoopVar10;\r
  mPrev[LoopVar10]  = mPos;\r
  mParent[mPos]     = LoopVar6;\r
  mParent[LoopVar4] = NIL;\r
\r
  //\r
  // Special usage of 'next'\r
  //\r
  mNext[LoopVar4] = mPos;\r
}\r
\r
/**\r
  Delete outdated string info. (The Usage of PERC_FLAG\r
  ensures a clean deletion).\r
\r
**/\r
VOID\r
DeleteNode (\r
  VOID\r
  )\r
{\r
  NODE  LoopVar6;\r
\r
  NODE  LoopVar4;\r
\r
  NODE  LoopVar11;\r
\r
  NODE  LoopVar10;\r
\r
  NODE  LoopVar9;\r
\r
  if (mParent[mPos] == NIL) {\r
    return;\r
  }\r
\r
  LoopVar4         = mPrev[mPos];\r
  LoopVar11        = mNext[mPos];\r
  mNext[LoopVar4]  = LoopVar11;\r
  mPrev[LoopVar11] = LoopVar4;\r
  LoopVar4         = mParent[mPos];\r
  mParent[mPos]    = NIL;\r
  if (LoopVar4 >= WNDSIZ) {\r
    return;\r
  }\r
\r
  mChildCount[LoopVar4]--;\r
  if (mChildCount[LoopVar4] > 1) {\r
    return;\r
  }\r
\r
  LoopVar10 = (NODE)(mPosition[LoopVar4] & ~PERC_FLAG);\r
  if (LoopVar10 >= mPos) {\r
    LoopVar10 -= WNDSIZ;\r
  }\r
\r
  LoopVar11 = LoopVar10;\r
  LoopVar6  = mParent[LoopVar4];\r
  LoopVar9  = mPosition[LoopVar6];\r
  while ((LoopVar9 & PERC_FLAG) != 0) {\r
    LoopVar9 &= ~PERC_FLAG;\r
    if (LoopVar9 >= mPos) {\r
      LoopVar9 -= WNDSIZ;\r
    }\r
\r
    if (LoopVar9 > LoopVar11) {\r
      LoopVar11 = LoopVar9;\r
    }\r
\r
    mPosition[LoopVar6] = (NODE)(LoopVar11 | WNDSIZ);\r
    LoopVar6            = mParent[LoopVar6];\r
    LoopVar9            = mPosition[LoopVar6];\r
  }\r
\r
  if (LoopVar6 < WNDSIZ) {\r
    if (LoopVar9 >= mPos) {\r
      LoopVar9 -= WNDSIZ;\r
    }\r
\r
    if (LoopVar9 > LoopVar11) {\r
      LoopVar11 = LoopVar9;\r
    }\r
\r
    mPosition[LoopVar6] = (NODE)(LoopVar11 | WNDSIZ | PERC_FLAG);\r
  }\r
\r
  LoopVar11          = Child (LoopVar4, mText[LoopVar10 + mLevel[LoopVar4]]);\r
  LoopVar10          = mPrev[LoopVar11];\r
  LoopVar9           = mNext[LoopVar11];\r
  mNext[LoopVar10]   = LoopVar9;\r
  mPrev[LoopVar9]    = LoopVar10;\r
  LoopVar10          = mPrev[LoopVar4];\r
  mNext[LoopVar10]   = LoopVar11;\r
  mPrev[LoopVar11]   = LoopVar10;\r
  LoopVar10          = mNext[LoopVar4];\r
  mPrev[LoopVar10]   = LoopVar11;\r
  mNext[LoopVar11]   = LoopVar10;\r
  mParent[LoopVar11] = mParent[LoopVar4];\r
  mParent[LoopVar4]  = NIL;\r
  mNext[LoopVar4]    = mAvail;\r
  mAvail             = LoopVar4;\r
}\r
\r
/**\r
  Read in source data\r
\r
  @param[out] LoopVar7   The buffer to hold the data.\r
  @param[in] LoopVar8    The number of bytes to read.\r
\r
  @return The number of bytes actually read.\r
**/\r
INT32\r
FreadCrc (\r
  OUT UINT8  *LoopVar7,\r
  IN  INT32  LoopVar8\r
  )\r
{\r
  INT32  LoopVar1;\r
\r
  for (LoopVar1 = 0; mSrc < mSrcUpperLimit && LoopVar1 < LoopVar8; LoopVar1++) {\r
    *LoopVar7++ = *mSrc++;\r
  }\r
\r
  LoopVar8 = LoopVar1;\r
\r
  LoopVar7  -= LoopVar8;\r
  mOrigSize += LoopVar8;\r
  LoopVar1--;\r
  while (LoopVar1 >= 0) {\r
    UPDATE_CRC (*LoopVar7++);\r
    LoopVar1--;\r
  }\r
\r
  return LoopVar8;\r
}\r
\r
/**\r
  Advance the current position (read in new data if needed).\r
  Delete outdated string info. Find a match string for current position.\r
\r
  @retval TRUE      The operation was successful.\r
  @retval FALSE     The operation failed due to insufficient memory.\r
**/\r
BOOLEAN\r
GetNextMatch (\r
  VOID\r
  )\r
{\r
  INT32  LoopVar8;\r
  VOID   *Temp;\r
\r
  mRemainder--;\r
  mPos++;\r
  if (mPos == WNDSIZ * 2) {\r
    Temp = AllocateZeroPool (WNDSIZ + MAXMATCH);\r
    if (Temp == NULL) {\r
      return (FALSE);\r
    }\r
\r
    CopyMem (Temp, &mText[WNDSIZ], WNDSIZ + MAXMATCH);\r
    CopyMem (&mText[0], Temp, WNDSIZ + MAXMATCH);\r
    FreePool (Temp);\r
    LoopVar8    = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);\r
    mRemainder += LoopVar8;\r
    mPos        = WNDSIZ;\r
  }\r
\r
  DeleteNode ();\r
  InsertNode ();\r
\r
  return (TRUE);\r
}\r
\r
/**\r
  Send entry LoopVar1 down the queue.\r
\r
  @param[in] LoopVar1    The index of the item to move.\r
**/\r
VOID\r
DownHeap (\r
  IN INT32  i\r
  )\r
{\r
  INT32  LoopVar1;\r
\r
  INT32  LoopVar2;\r
\r
  //\r
  // priority queue: send i-th entry down heap\r
  //\r
  LoopVar2 = mHeap[i];\r
  LoopVar1 = 2 * i;\r
  while (LoopVar1 <= mHeapSize) {\r
    if ((LoopVar1 < mHeapSize) && (mFreq[mHeap[LoopVar1]] > mFreq[mHeap[LoopVar1 + 1]])) {\r
      LoopVar1++;\r
    }\r
\r
    if (mFreq[LoopVar2] <= mFreq[mHeap[LoopVar1]]) {\r
      break;\r
    }\r
\r
    mHeap[i] = mHeap[LoopVar1];\r
    i        = LoopVar1;\r
    LoopVar1 = 2 * i;\r
  }\r
\r
  mHeap[i] = (INT16)LoopVar2;\r
}\r
\r
/**\r
  Count the number of each code length for a Huffman tree.\r
\r
  @param[in] LoopVar1      The top node.\r
**/\r
VOID\r
CountLen (\r
  IN INT32  LoopVar1\r
  )\r
{\r
  if (LoopVar1 < mTempInt32) {\r
    mLenCnt[(mHuffmanDepth < 16) ? mHuffmanDepth : 16]++;\r
  } else {\r
    mHuffmanDepth++;\r
    CountLen (mLeft[LoopVar1]);\r
    CountLen (mRight[LoopVar1]);\r
    mHuffmanDepth--;\r
  }\r
}\r
\r
/**\r
  Create code length array for a Huffman tree.\r
\r
  @param[in] Root   The root of the tree.\r
**/\r
VOID\r
MakeLen (\r
  IN INT32  Root\r
  )\r
{\r
  INT32  LoopVar1;\r
\r
  INT32   LoopVar2;\r
  UINT32  Cum;\r
\r
  for (LoopVar1 = 0; LoopVar1 <= 16; LoopVar1++) {\r
    mLenCnt[LoopVar1] = 0;\r
  }\r
\r
  CountLen (Root);\r
\r
  //\r
  // Adjust the length count array so that\r
  // no code will be generated longer than its designated length\r
  //\r
  Cum = 0;\r
  for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {\r
    Cum += mLenCnt[LoopVar1] << (16 - LoopVar1);\r
  }\r
\r
  while (Cum != (1U << 16)) {\r
    mLenCnt[16]--;\r
    for (LoopVar1 = 15; LoopVar1 > 0; LoopVar1--) {\r
      if (mLenCnt[LoopVar1] != 0) {\r
        mLenCnt[LoopVar1]--;\r
        mLenCnt[LoopVar1 + 1] += 2;\r
        break;\r
      }\r
    }\r
\r
    Cum--;\r
  }\r
\r
  for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {\r
    LoopVar2 = mLenCnt[LoopVar1];\r
    LoopVar2--;\r
    while (LoopVar2 >= 0) {\r
      mLen[*mSortPtr++] = (UINT8)LoopVar1;\r
      LoopVar2--;\r
    }\r
  }\r
}\r
\r
/**\r
  Assign code to each symbol based on the code length array.\r
\r
  @param[in] LoopVar8      The number of symbols.\r
  @param[in] Len    The code length array.\r
  @param[out] Code  The stores codes for each symbol.\r
**/\r
VOID\r
MakeCode (\r
  IN  INT32   LoopVar8,\r
  IN  UINT8   Len[],\r
  OUT UINT16  Code[]\r
  )\r
{\r
  INT32   LoopVar1;\r
  UINT16  Start[18];\r
\r
  Start[1] = 0;\r
  for (LoopVar1 = 1; LoopVar1 <= 16; LoopVar1++) {\r
    Start[LoopVar1 + 1] = (UINT16)((Start[LoopVar1] + mLenCnt[LoopVar1]) << 1);\r
  }\r
\r
  for (LoopVar1 = 0; LoopVar1 < LoopVar8; LoopVar1++) {\r
    Code[LoopVar1] = Start[Len[LoopVar1]]++;\r
  }\r
}\r
\r
/**\r
  Generates Huffman codes given a frequency distribution of symbols.\r
\r
  @param[in] NParm      The number of symbols.\r
  @param[in] FreqParm   The frequency of each symbol.\r
  @param[out] LenParm   The code length for each symbol.\r
  @param[out] CodeParm  The code for each symbol.\r
\r
  @return The root of the Huffman tree.\r
**/\r
INT32\r
MakeTree (\r
  IN  INT32   NParm,\r
  IN  UINT16  FreqParm[],\r
  OUT UINT8   LenParm[],\r
  OUT UINT16  CodeParm[]\r
  )\r
{\r
  INT32  LoopVar1;\r
\r
  INT32  LoopVar2;\r
\r
  INT32  LoopVar3;\r
\r
  INT32  Avail;\r
\r
  //\r
  // make tree, calculate len[], return root\r
  //\r
  mTempInt32 = NParm;\r
  mFreq      = FreqParm;\r
  mLen       = LenParm;\r
  Avail      = mTempInt32;\r
  mHeapSize  = 0;\r
  mHeap[1]   = 0;\r
  for (LoopVar1 = 0; LoopVar1 < mTempInt32; LoopVar1++) {\r
    mLen[LoopVar1] = 0;\r
    if ((mFreq[LoopVar1]) != 0) {\r
      mHeapSize++;\r
      mHeap[mHeapSize] = (INT16)LoopVar1;\r
    }\r
  }\r
\r
  if (mHeapSize < 2) {\r
    CodeParm[mHeap[1]] = 0;\r
    return mHeap[1];\r
  }\r
\r
  for (LoopVar1 = mHeapSize / 2; LoopVar1 >= 1; LoopVar1--) {\r
    //\r
    // make priority queue\r
    //\r
    DownHeap (LoopVar1);\r
  }\r
\r
  mSortPtr = CodeParm;\r
  do {\r
    LoopVar1 = mHeap[1];\r
    if (LoopVar1 < mTempInt32) {\r
      *mSortPtr++ = (UINT16)LoopVar1;\r
    }\r
\r
    mHeap[1] = mHeap[mHeapSize--];\r
    DownHeap (1);\r
    LoopVar2 = mHeap[1];\r
    if (LoopVar2 < mTempInt32) {\r
      *mSortPtr++ = (UINT16)LoopVar2;\r
    }\r
\r
    LoopVar3        = Avail++;\r
    mFreq[LoopVar3] = (UINT16)(mFreq[LoopVar1] + mFreq[LoopVar2]);\r
    mHeap[1]        = (INT16)LoopVar3;\r
    DownHeap (1);\r
    mLeft[LoopVar3]  = (UINT16)LoopVar1;\r
    mRight[LoopVar3] = (UINT16)LoopVar2;\r
  } while (mHeapSize > 1);\r
\r
  mSortPtr = CodeParm;\r
  MakeLen (LoopVar3);\r
  MakeCode (NParm, LenParm, CodeParm);\r
\r
  //\r
  // return root\r
  //\r
  return LoopVar3;\r
}\r
\r
/**\r
  Outputs rightmost LoopVar8 bits of x\r
\r
  @param[in] LoopVar8   The rightmost LoopVar8 bits of the data is used.\r
  @param[in] x   The data.\r
**/\r
VOID\r
PutBits (\r
  IN INT32   LoopVar8,\r
  IN UINT32  x\r
  )\r
{\r
  UINT8  Temp;\r
\r
  if (LoopVar8 < mBitCount) {\r
    mSubBitBuf |= x << (mBitCount -= LoopVar8);\r
  } else {\r
    Temp = (UINT8)(mSubBitBuf | (x >> (LoopVar8 -= mBitCount)));\r
    if (mDst < mDstUpperLimit) {\r
      *mDst++ = Temp;\r
    }\r
\r
    mCompSize++;\r
\r
    if (LoopVar8 < UINT8_BIT) {\r
      mSubBitBuf = x << (mBitCount = UINT8_BIT - LoopVar8);\r
    } else {\r
      Temp = (UINT8)(x >> (LoopVar8 - UINT8_BIT));\r
      if (mDst < mDstUpperLimit) {\r
        *mDst++ = Temp;\r
      }\r
\r
      mCompSize++;\r
\r
      mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - LoopVar8);\r
    }\r
  }\r
}\r
\r
/**\r
  Encode a signed 32 bit number.\r
\r
  @param[in] LoopVar5     The number to encode.\r
**/\r
VOID\r
EncodeC (\r
  IN INT32  LoopVar5\r
  )\r
{\r
  PutBits (mCLen[LoopVar5], mCCode[LoopVar5]);\r
}\r
\r
/**\r
  Encode a unsigned 32 bit number.\r
\r
  @param[in] LoopVar7     The number to encode.\r
**/\r
VOID\r
EncodeP (\r
  IN UINT32  LoopVar7\r
  )\r
{\r
  UINT32  LoopVar5;\r
\r
  UINT32  LoopVar6;\r
\r
  LoopVar5 = 0;\r
  LoopVar6 = LoopVar7;\r
  while (LoopVar6 != 0) {\r
    LoopVar6 >>= 1;\r
    LoopVar5++;\r
  }\r
\r
  PutBits (mPTLen[LoopVar5], mPTCode[LoopVar5]);\r
  if (LoopVar5 > 1) {\r
    PutBits (LoopVar5 - 1, LoopVar7 & (0xFFFFU >> (17 - LoopVar5)));\r
  }\r
}\r
\r
/**\r
  Count the frequencies for the Extra Set.\r
\r
**/\r
VOID\r
CountTFreq (\r
  VOID\r
  )\r
{\r
  INT32  LoopVar1;\r
\r
  INT32  LoopVar3;\r
\r
  INT32  LoopVar8;\r
\r
  INT32  Count;\r
\r
  for (LoopVar1 = 0; LoopVar1 < NT; LoopVar1++) {\r
    mTFreq[LoopVar1] = 0;\r
  }\r
\r
  LoopVar8 = NC;\r
  while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {\r
    LoopVar8--;\r
  }\r
\r
  LoopVar1 = 0;\r
  while (LoopVar1 < LoopVar8) {\r
    LoopVar3 = mCLen[LoopVar1++];\r
    if (LoopVar3 == 0) {\r
      Count = 1;\r
      while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {\r
        LoopVar1++;\r
        Count++;\r
      }\r
\r
      if (Count <= 2) {\r
        mTFreq[0] = (UINT16)(mTFreq[0] + Count);\r
      } else if (Count <= 18) {\r
        mTFreq[1]++;\r
      } else if (Count == 19) {\r
        mTFreq[0]++;\r
        mTFreq[1]++;\r
      } else {\r
        mTFreq[2]++;\r
      }\r
    } else {\r
      ASSERT ((LoopVar3+2) < (2 * NT - 1));\r
      mTFreq[LoopVar3 + 2]++;\r
    }\r
  }\r
}\r
\r
/**\r
  Outputs the code length array for the Extra Set or the Position Set.\r
\r
  @param[in] LoopVar8       The number of symbols.\r
  @param[in] nbit           The number of bits needed to represent 'LoopVar8'.\r
  @param[in] Special        The special symbol that needs to be take care of.\r
\r
**/\r
VOID\r
WritePTLen (\r
  IN INT32  LoopVar8,\r
  IN INT32  nbit,\r
  IN INT32  Special\r
  )\r
{\r
  INT32  LoopVar1;\r
\r
  INT32  LoopVar3;\r
\r
  while (LoopVar8 > 0 && mPTLen[LoopVar8 - 1] == 0) {\r
    LoopVar8--;\r
  }\r
\r
  PutBits (nbit, LoopVar8);\r
  LoopVar1 = 0;\r
  while (LoopVar1 < LoopVar8) {\r
    LoopVar3 = mPTLen[LoopVar1++];\r
    if (LoopVar3 <= 6) {\r
      PutBits (3, LoopVar3);\r
    } else {\r
      PutBits (LoopVar3 - 3, (1U << (LoopVar3 - 3)) - 2);\r
    }\r
\r
    if (LoopVar1 == Special) {\r
      while (LoopVar1 < 6 && mPTLen[LoopVar1] == 0) {\r
        LoopVar1++;\r
      }\r
\r
      PutBits (2, (LoopVar1 - 3) & 3);\r
    }\r
  }\r
}\r
\r
/**\r
  Outputs the code length array for Char&Length Set.\r
**/\r
VOID\r
WriteCLen (\r
  VOID\r
  )\r
{\r
  INT32  LoopVar1;\r
\r
  INT32  LoopVar3;\r
\r
  INT32  LoopVar8;\r
\r
  INT32  Count;\r
\r
  LoopVar8 = NC;\r
  while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {\r
    LoopVar8--;\r
  }\r
\r
  PutBits (CBIT, LoopVar8);\r
  LoopVar1 = 0;\r
  while (LoopVar1 < LoopVar8) {\r
    LoopVar3 = mCLen[LoopVar1++];\r
    if (LoopVar3 == 0) {\r
      Count = 1;\r
      while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {\r
        LoopVar1++;\r
        Count++;\r
      }\r
\r
      if (Count <= 2) {\r
        for (LoopVar3 = 0; LoopVar3 < Count; LoopVar3++) {\r
          PutBits (mPTLen[0], mPTCode[0]);\r
        }\r
      } else if (Count <= 18) {\r
        PutBits (mPTLen[1], mPTCode[1]);\r
        PutBits (4, Count - 3);\r
      } else if (Count == 19) {\r
        PutBits (mPTLen[0], mPTCode[0]);\r
        PutBits (mPTLen[1], mPTCode[1]);\r
        PutBits (4, 15);\r
      } else {\r
        PutBits (mPTLen[2], mPTCode[2]);\r
        PutBits (CBIT, Count - 20);\r
      }\r
    } else {\r
      ASSERT ((LoopVar3+2) < NPT);\r
      PutBits (mPTLen[LoopVar3 + 2], mPTCode[LoopVar3 + 2]);\r
    }\r
  }\r
}\r
\r
/**\r
  Huffman code the block and output it.\r
\r
**/\r
VOID\r
SendBlock (\r
  VOID\r
  )\r
{\r
  UINT32  LoopVar1;\r
\r
  UINT32  LoopVar3;\r
\r
  UINT32  Flags;\r
\r
  UINT32  Root;\r
\r
  UINT32  Pos;\r
\r
  UINT32  Size;\r
\r
  Flags = 0;\r
\r
  Root = MakeTree (NC, mCFreq, mCLen, mCCode);\r
  Size = mCFreq[Root];\r
  PutBits (16, Size);\r
  if (Root >= NC) {\r
    CountTFreq ();\r
    Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);\r
    if (Root >= NT) {\r
      WritePTLen (NT, TBIT, 3);\r
    } else {\r
      PutBits (TBIT, 0);\r
      PutBits (TBIT, Root);\r
    }\r
\r
    WriteCLen ();\r
  } else {\r
    PutBits (TBIT, 0);\r
    PutBits (TBIT, 0);\r
    PutBits (CBIT, 0);\r
    PutBits (CBIT, Root);\r
  }\r
\r
  Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);\r
  if (Root >= NP) {\r
    WritePTLen (NP, PBIT, -1);\r
  } else {\r
    PutBits (PBIT, 0);\r
    PutBits (PBIT, Root);\r
  }\r
\r
  Pos = 0;\r
  for (LoopVar1 = 0; LoopVar1 < Size; LoopVar1++) {\r
    if (LoopVar1 % UINT8_BIT == 0) {\r
      Flags = mBuf[Pos++];\r
    } else {\r
      Flags <<= 1;\r
    }\r
\r
    if ((Flags & (1U << (UINT8_BIT - 1))) != 0) {\r
      EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));\r
      LoopVar3  = mBuf[Pos++] << UINT8_BIT;\r
      LoopVar3 += mBuf[Pos++];\r
\r
      EncodeP (LoopVar3);\r
    } else {\r
      EncodeC (mBuf[Pos++]);\r
    }\r
  }\r
\r
  SetMem (mCFreq, NC * sizeof (UINT16), 0);\r
  SetMem (mPFreq, NP * sizeof (UINT16), 0);\r
}\r
\r
/**\r
  Start the huffman encoding.\r
\r
**/\r
VOID\r
HufEncodeStart (\r
  VOID\r
  )\r
{\r
  SetMem (mCFreq, NC * sizeof (UINT16), 0);\r
  SetMem (mPFreq, NP * sizeof (UINT16), 0);\r
\r
  mOutputPos = mOutputMask = 0;\r
\r
  mBitCount  = UINT8_BIT;\r
  mSubBitBuf = 0;\r
}\r
\r
/**\r
  Outputs an Original Character or a Pointer.\r
\r
  @param[in] LoopVar5     The original character or the 'String Length' element of\r
                   a Pointer.\r
  @param[in] LoopVar7     The 'Position' field of a Pointer.\r
**/\r
VOID\r
CompressOutput (\r
  IN UINT32  LoopVar5,\r
  IN UINT32  LoopVar7\r
  )\r
{\r
  STATIC UINT32  CPos;\r
\r
  if ((mOutputMask >>= 1) == 0) {\r
    mOutputMask = 1U << (UINT8_BIT - 1);\r
    if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {\r
      SendBlock ();\r
      mOutputPos = 0;\r
    }\r
\r
    CPos       = mOutputPos++;\r
    mBuf[CPos] = 0;\r
  }\r
\r
  mBuf[mOutputPos++] = (UINT8)LoopVar5;\r
  mCFreq[LoopVar5]++;\r
  if (LoopVar5 >= (1U << UINT8_BIT)) {\r
    mBuf[CPos]         = (UINT8)(mBuf[CPos]|mOutputMask);\r
    mBuf[mOutputPos++] = (UINT8)(LoopVar7 >> UINT8_BIT);\r
    mBuf[mOutputPos++] = (UINT8)LoopVar7;\r
    LoopVar5           = 0;\r
    while (LoopVar7 != 0) {\r
      LoopVar7 >>= 1;\r
      LoopVar5++;\r
    }\r
\r
    mPFreq[LoopVar5]++;\r
  }\r
}\r
\r
/**\r
  End the huffman encoding.\r
\r
**/\r
VOID\r
HufEncodeEnd (\r
  VOID\r
  )\r
{\r
  SendBlock ();\r
\r
  //\r
  // Flush remaining bits\r
  //\r
  PutBits (UINT8_BIT - 1, 0);\r
}\r
\r
/**\r
  The main controlling routine for compression process.\r
\r
  @retval EFI_SUCCESS           The compression is successful.\r
  @retval EFI_OUT_0F_RESOURCES  Not enough memory for compression process.\r
**/\r
EFI_STATUS\r
Encode (\r
  VOID\r
  )\r
{\r
  EFI_STATUS  Status;\r
  INT32       LastMatchLen;\r
  NODE        LastMatchPos;\r
\r
  Status = AllocateMemory ();\r
  if (EFI_ERROR (Status)) {\r
    FreeMemory ();\r
    return Status;\r
  }\r
\r
  InitSlide ();\r
\r
  HufEncodeStart ();\r
\r
  mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);\r
\r
  mMatchLen = 0;\r
  mPos      = WNDSIZ;\r
  InsertNode ();\r
  if (mMatchLen > mRemainder) {\r
    mMatchLen = mRemainder;\r
  }\r
\r
  while (mRemainder > 0) {\r
    LastMatchLen = mMatchLen;\r
    LastMatchPos = mMatchPos;\r
    if (!GetNextMatch ()) {\r
      Status = EFI_OUT_OF_RESOURCES;\r
    }\r
\r
    if (mMatchLen > mRemainder) {\r
      mMatchLen = mRemainder;\r
    }\r
\r
    if ((mMatchLen > LastMatchLen) || (LastMatchLen < THRESHOLD)) {\r
      //\r
      // Not enough benefits are gained by outputting a pointer,\r
      // so just output the original character\r
      //\r
      CompressOutput (mText[mPos - 1], 0);\r
    } else {\r
      //\r
      // Outputting a pointer is beneficial enough, do it.\r
      //\r
\r
      CompressOutput (\r
        LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),\r
        (mPos - LastMatchPos - 2) & (WNDSIZ - 1)\r
        );\r
      LastMatchLen--;\r
      while (LastMatchLen > 0) {\r
        if (!GetNextMatch ()) {\r
          Status = EFI_OUT_OF_RESOURCES;\r
        }\r
\r
        LastMatchLen--;\r
      }\r
\r
      if (mMatchLen > mRemainder) {\r
        mMatchLen = mRemainder;\r
      }\r
    }\r
  }\r
\r
  HufEncodeEnd ();\r
  FreeMemory ();\r
  return (Status);\r
}\r
\r
/**\r
  The compression routine.\r
\r
  @param[in]       SrcBuffer     The buffer containing the source data.\r
  @param[in]       SrcSize       Number of bytes in SrcBuffer.\r
  @param[in]       DstBuffer     The buffer to put the compressed image in.\r
  @param[in, out]  DstSize       On input the size (in bytes) of DstBuffer, on\r
                                 return the number of bytes placed in DstBuffer.\r
\r
  @retval EFI_SUCCESS           The compression was sucessful.\r
  @retval EFI_BUFFER_TOO_SMALL  The buffer was too small.  DstSize is required.\r
**/\r
EFI_STATUS\r
Compress (\r
  IN      VOID    *SrcBuffer,\r
  IN      UINT64  SrcSize,\r
  IN      VOID    *DstBuffer,\r
  IN OUT  UINT64  *DstSize\r
  )\r
{\r
  EFI_STATUS  Status;\r
\r
  //\r
  // Initializations\r
  //\r
  mBufSiz     = 0;\r
  mBuf        = NULL;\r
  mText       = NULL;\r
  mLevel      = NULL;\r
  mChildCount = NULL;\r
  mPosition   = NULL;\r
  mParent     = NULL;\r
  mPrev       = NULL;\r
  mNext       = NULL;\r
\r
  mSrc           = SrcBuffer;\r
  mSrcUpperLimit = mSrc + SrcSize;\r
  mDst           = DstBuffer;\r
  mDstUpperLimit = mDst +*DstSize;\r
\r
  PutDword (0L);\r
  PutDword (0L);\r
\r
  MakeCrcTable ();\r
\r
  mOrigSize = mCompSize = 0;\r
  mCrc      = INIT_CRC;\r
\r
  //\r
  // Compress it\r
  //\r
  Status = Encode ();\r
  if (EFI_ERROR (Status)) {\r
    return EFI_OUT_OF_RESOURCES;\r
  }\r
\r
  //\r
  // Null terminate the compressed data\r
  //\r
  if (mDst < mDstUpperLimit) {\r
    *mDst++ = 0;\r
  }\r
\r
  //\r
  // Fill in compressed size and original size\r
  //\r
  mDst = DstBuffer;\r
  PutDword (mCompSize + 1);\r
  PutDword (mOrigSize);\r
\r
  //\r
  // Return\r
  //\r
  if (mCompSize + 1 + 8 > *DstSize) {\r
    *DstSize = mCompSize + 1 + 8;\r
    return EFI_BUFFER_TOO_SMALL;\r
  } else {\r
    *DstSize = mCompSize + 1 + 8;\r
    return EFI_SUCCESS;\r
  }\r
}\r