source: vbox/trunk/src/VBox/Devices/EFI/Firmware/ShellPkg/Library/UefiShellDebug1CommandsLib/Compress.c@ 80924

/** @file
  Main file for compression routine.

  Compression routine. The compression algorithm is a mixture of
  LZ77 and Huffman coding. LZ77 transforms the source data into a
  sequence of Original Characters and Pointers to repeated strings.
  This sequence is further divided into Blocks and Huffman codings
  are applied to each Block.

  Copyright (c) 2007 - 2018, Intel Corporation. All rights reserved.<BR>
  SPDX-License-Identifier: BSD-2-Clause-Patent

**/
#include <Uefi.h>
#include <Library/MemoryAllocationLib.h>
#include <Library/BaseMemoryLib.h>
#include <Library/DebugLib.h>
#include <Library/ShellLib.h>

#include "Compress.h"

//
// Macro Definitions
//
typedef INT16             NODE;
#define UINT8_MAX         0xff
#define UINT8_BIT         8
#define THRESHOLD         3
#define INIT_CRC          0
#define WNDBIT            13
#define WNDSIZ            (1U << WNDBIT)
#define MAXMATCH          256
#define BLKSIZ            (1U << 14)  // 16 * 1024U
#define PERC_FLAG         0x8000U
#define CODE_BIT          16
#define NIL               0
#define MAX_HASH_VAL      (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
#define HASH(LoopVar7, LoopVar5)        ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)
#define CRCPOLY           0xA001
#define UPDATE_CRC(LoopVar5)     mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)

//
// C: the Char&Len Set; P: the Position Set; T: the exTra Set
//
#define NC                (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
#define CBIT              9
#define NP                (WNDBIT + 1)
#define PBIT              4
#define NT                (CODE_BIT + 3)
#define TBIT              5
#if NT > NP
  #define                 NPT NT
#else
  #define                 NPT NP
#endif
//
// Function Prototypes
//

/**
  Put a dword to output stream

  @param[in] Data    The dword to put.
**/
VOID
PutDword(
  IN UINT32 Data
  );

//
//  Global Variables
//
STATIC UINT8  *mSrc;
STATIC UINT8  *mDst;
STATIC UINT8  *mSrcUpperLimit;
STATIC UINT8  *mDstUpperLimit;

STATIC UINT8  *mLevel;
STATIC UINT8  *mText;
STATIC UINT8  *mChildCount;
STATIC UINT8  *mBuf;
STATIC UINT8  mCLen[NC];
STATIC UINT8  mPTLen[NPT];
STATIC UINT8  *mLen;
STATIC INT16  mHeap[NC + 1];
STATIC INT32  mRemainder;
STATIC INT32  mMatchLen;
STATIC INT32  mBitCount;
STATIC INT32  mHeapSize;
STATIC INT32  mTempInt32;
STATIC UINT32 mBufSiz = 0;
STATIC UINT32 mOutputPos;
STATIC UINT32 mOutputMask;
STATIC UINT32 mSubBitBuf;
STATIC UINT32 mCrc;
STATIC UINT32 mCompSize;
STATIC UINT32 mOrigSize;

STATIC UINT16 *mFreq;
STATIC UINT16 *mSortPtr;
STATIC UINT16 mLenCnt[17];
STATIC UINT16 mLeft[2 * NC - 1];
STATIC UINT16 mRight[2 * NC - 1];
STATIC UINT16 mCrcTable[UINT8_MAX + 1];
STATIC UINT16 mCFreq[2 * NC - 1];
STATIC UINT16 mCCode[NC];
STATIC UINT16 mPFreq[2 * NP - 1];
STATIC UINT16 mPTCode[NPT];
STATIC UINT16 mTFreq[2 * NT - 1];

STATIC NODE   mPos;
STATIC NODE   mMatchPos;
STATIC NODE   mAvail;
STATIC NODE   *mPosition;
STATIC NODE   *mParent;
STATIC NODE   *mPrev;
STATIC NODE   *mNext = NULL;
INT32         mHuffmanDepth = 0;

/**
  Make a CRC table.

**/
VOID
MakeCrcTable (
  VOID
  )
{
  UINT32  LoopVar1;

  UINT32  LoopVar2;

  UINT32  LoopVar4;

  for (LoopVar1 = 0; LoopVar1 <= UINT8_MAX; LoopVar1++) {
    LoopVar4 = LoopVar1;
    for (LoopVar2 = 0; LoopVar2 < UINT8_BIT; LoopVar2++) {
      if ((LoopVar4 & 1) != 0) {
        LoopVar4 = (LoopVar4 >> 1) ^ CRCPOLY;
      } else {
        LoopVar4 >>= 1;
      }
    }

    mCrcTable[LoopVar1] = (UINT16) LoopVar4;
  }
}

/**
  Put a dword to output stream

  @param[in] Data    The dword to put.
**/
VOID
PutDword (
  IN UINT32 Data
  )
{
  if (mDst < mDstUpperLimit) {
    *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
  }

  if (mDst < mDstUpperLimit) {
    *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
  }

  if (mDst < mDstUpperLimit) {
    *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
  }

  if (mDst < mDstUpperLimit) {
    *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
  }
}

/**
  Allocate memory spaces for data structures used in compression process.

  @retval EFI_SUCCESS           Memory was allocated successfully.
  @retval EFI_OUT_OF_RESOURCES  A memory allocation failed.
**/
EFI_STATUS
AllocateMemory (
  VOID
  )
{
  mText       = AllocateZeroPool (WNDSIZ * 2 + MAXMATCH);
  mLevel      = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
  mChildCount = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
  mPosition   = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
  mParent     = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mParent));
  mPrev       = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mPrev));
  mNext       = AllocateZeroPool ((MAX_HASH_VAL + 1) * sizeof (*mNext));

  mBufSiz     = BLKSIZ;
  mBuf        = AllocateZeroPool (mBufSiz);
  while (mBuf == NULL) {
    mBufSiz = (mBufSiz / 10U) * 9U;
    if (mBufSiz < 4 * 1024U) {
      return EFI_OUT_OF_RESOURCES;
    }

    mBuf = AllocateZeroPool (mBufSiz);
  }

  mBuf[0] = 0;

  return EFI_SUCCESS;
}

/**
  Called when compression is completed to free memory previously allocated.

**/
VOID
FreeMemory (
  VOID
  )
{
  SHELL_FREE_NON_NULL (mText);
  SHELL_FREE_NON_NULL (mLevel);
  SHELL_FREE_NON_NULL (mChildCount);
  SHELL_FREE_NON_NULL (mPosition);
  SHELL_FREE_NON_NULL (mParent);
  SHELL_FREE_NON_NULL (mPrev);
  SHELL_FREE_NON_NULL (mNext);
  SHELL_FREE_NON_NULL (mBuf);
}

/**
  Initialize String Info Log data structures.
**/
VOID
InitSlide (
  VOID
  )
{
  NODE  LoopVar1;

  SetMem (mLevel + WNDSIZ, (UINT8_MAX + 1) * sizeof (UINT8), 1);
  SetMem (mPosition + WNDSIZ, (UINT8_MAX + 1) * sizeof (NODE), 0);

  SetMem (mParent + WNDSIZ, WNDSIZ * sizeof (NODE), 0);

  mAvail = 1;
  for (LoopVar1 = 1; LoopVar1 < WNDSIZ - 1; LoopVar1++) {
    mNext[LoopVar1] = (NODE) (LoopVar1 + 1);
  }

  mNext[WNDSIZ - 1] = NIL;
  SetMem (mNext + WNDSIZ * 2, (MAX_HASH_VAL - WNDSIZ * 2 + 1) * sizeof (NODE), 0);
}

/**
  Find child node given the parent node and the edge character

  @param[in] LoopVar6       The parent node.
  @param[in] LoopVar5       The edge character.

  @return             The child node.
  @retval NIL(Zero)   No child could be found.

**/
NODE
Child (
  IN NODE   LoopVar6,
  IN UINT8  LoopVar5
  )
{
  NODE  LoopVar4;

  LoopVar4             = mNext[HASH (LoopVar6, LoopVar5)];
  mParent[NIL]  = LoopVar6;  /* sentinel */
  while (mParent[LoopVar4] != LoopVar6) {
    LoopVar4 = mNext[LoopVar4];
  }

  return LoopVar4;
}

/**
  Create a new child for a given parent node.

  @param[in] LoopVar6       The parent node.
  @param[in] LoopVar5       The edge character.
  @param[in] LoopVar4       The child node.
**/
VOID
MakeChild (
  IN NODE   LoopVar6,
  IN UINT8  LoopVar5,
  IN NODE   LoopVar4
  )
{
  NODE  LoopVar12;

  NODE  LoopVar10;

  LoopVar12          = (NODE) HASH (LoopVar6, LoopVar5);
  LoopVar10          = mNext[LoopVar12];
  mNext[LoopVar12]   = LoopVar4;
  mNext[LoopVar4]    = LoopVar10;
  mPrev[LoopVar10]   = LoopVar4;
  mPrev[LoopVar4]    = LoopVar12;
  mParent[LoopVar4]  = LoopVar6;
  mChildCount[LoopVar6]++;
}

/**
  Split a node.

  @param[in] Old     The node to split.
**/
VOID
Split (
  IN NODE Old
  )
{
  NODE  New;

  NODE  LoopVar10;

  New               = mAvail;
  mAvail            = mNext[New];
  mChildCount[New]  = 0;
  LoopVar10                 = mPrev[Old];
  mPrev[New]        = LoopVar10;
  mNext[LoopVar10]          = New;
  LoopVar10                 = mNext[Old];
  mNext[New]        = LoopVar10;
  mPrev[LoopVar10]          = New;
  mParent[New]      = mParent[Old];
  mLevel[New]       = (UINT8) mMatchLen;
  mPosition[New]    = mPos;
  MakeChild (New, mText[mMatchPos + mMatchLen], Old);
  MakeChild (New, mText[mPos + mMatchLen], mPos);
}

/**
  Insert string info for current position into the String Info Log.

**/
VOID
InsertNode (
  VOID
  )
{
  NODE  LoopVar6;

  NODE  LoopVar4;

  NODE  LoopVar2;

  NODE  LoopVar10;
  UINT8 LoopVar5;
  UINT8 *TempString3;
  UINT8 *TempString2;

  if (mMatchLen >= 4) {
    //
    // We have just got a long match, the target tree
    // can be located by MatchPos + 1. Travese the tree
    // from bottom up to get to a proper starting point.
    // The usage of PERC_FLAG ensures proper node deletion
    // in DeleteNode() later.
    //
    mMatchLen--;
    LoopVar4 = (NODE) ((mMatchPos + 1) | WNDSIZ);
    LoopVar6 = mParent[LoopVar4];
    while (LoopVar6 == NIL) {
      LoopVar4 = mNext[LoopVar4];
      LoopVar6 = mParent[LoopVar4];
    }

    while (mLevel[LoopVar6] >= mMatchLen) {
      LoopVar4 = LoopVar6;
      LoopVar6 = mParent[LoopVar6];
    }

    LoopVar10 = LoopVar6;
    while (mPosition[LoopVar10] < 0) {
      mPosition[LoopVar10]  = mPos;
      LoopVar10             = mParent[LoopVar10];
    }

    if (LoopVar10 < WNDSIZ) {
      mPosition[LoopVar10] = (NODE) (mPos | PERC_FLAG);
    }
  } else {
    //
    // Locate the target tree
    //
    LoopVar6 = (NODE) (mText[mPos] + WNDSIZ);
    LoopVar5 = mText[mPos + 1];
    LoopVar4 = Child (LoopVar6, LoopVar5);
    if (LoopVar4 == NIL) {
      MakeChild (LoopVar6, LoopVar5, mPos);
      mMatchLen = 1;
      return ;
    }

    mMatchLen = 2;
  }
  //
  // Traverse down the tree to find a match.
  // Update Position value along the route.
  // Node split or creation is involved.
  //
  for (;;) {
    if (LoopVar4 >= WNDSIZ) {
      LoopVar2         = MAXMATCH;
      mMatchPos = LoopVar4;
    } else {
      LoopVar2         = mLevel[LoopVar4];
      mMatchPos = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
    }

    if (mMatchPos >= mPos) {
      mMatchPos -= WNDSIZ;
    }

    TempString3  = &mText[mPos + mMatchLen];
    TempString2  = &mText[mMatchPos + mMatchLen];
    while (mMatchLen < LoopVar2) {
      if (*TempString3 != *TempString2) {
        Split (LoopVar4);
        return ;
      }

      mMatchLen++;
      TempString3++;
      TempString2++;
    }

    if (mMatchLen >= MAXMATCH) {
      break;
    }

    mPosition[LoopVar4]  = mPos;
    LoopVar6             = LoopVar4;
    LoopVar4             = Child (LoopVar6, *TempString3);
    if (LoopVar4 == NIL) {
      MakeChild (LoopVar6, *TempString3, mPos);
      return ;
    }

    mMatchLen++;
  }

  LoopVar10             = mPrev[LoopVar4];
  mPrev[mPos]   = LoopVar10;
  mNext[LoopVar10]      = mPos;
  LoopVar10             = mNext[LoopVar4];
  mNext[mPos]   = LoopVar10;
  mPrev[LoopVar10]      = mPos;
  mParent[mPos] = LoopVar6;
  mParent[LoopVar4]    = NIL;

  //
  // Special usage of 'next'
  //
  mNext[LoopVar4] = mPos;

}

/**
  Delete outdated string info. (The Usage of PERC_FLAG
  ensures a clean deletion).

**/
VOID
DeleteNode (
  VOID
  )
{
  NODE  LoopVar6;

  NODE  LoopVar4;

  NODE  LoopVar11;

  NODE  LoopVar10;

  NODE  LoopVar9;

  if (mParent[mPos] == NIL) {
    return ;
  }

  LoopVar4             = mPrev[mPos];
  LoopVar11             = mNext[mPos];
  mNext[LoopVar4]      = LoopVar11;
  mPrev[LoopVar11]      = LoopVar4;
  LoopVar4             = mParent[mPos];
  mParent[mPos] = NIL;
  if (LoopVar4 >= WNDSIZ) {
    return ;
  }

  mChildCount[LoopVar4]--;
  if (mChildCount[LoopVar4] > 1) {
    return ;
  }

  LoopVar10 = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
  if (LoopVar10 >= mPos) {
    LoopVar10 -= WNDSIZ;
  }

  LoopVar11 = LoopVar10;
  LoopVar6 = mParent[LoopVar4];
  LoopVar9 = mPosition[LoopVar6];
  while ((LoopVar9 & PERC_FLAG) != 0){
    LoopVar9 &= ~PERC_FLAG;
    if (LoopVar9 >= mPos) {
      LoopVar9 -= WNDSIZ;
    }

    if (LoopVar9 > LoopVar11) {
      LoopVar11 = LoopVar9;
    }

    mPosition[LoopVar6]  = (NODE) (LoopVar11 | WNDSIZ);
    LoopVar6             = mParent[LoopVar6];
    LoopVar9             = mPosition[LoopVar6];
  }

  if (LoopVar6 < WNDSIZ) {
    if (LoopVar9 >= mPos) {
      LoopVar9 -= WNDSIZ;
    }

    if (LoopVar9 > LoopVar11) {
      LoopVar11 = LoopVar9;
    }

    mPosition[LoopVar6] = (NODE) (LoopVar11 | WNDSIZ | PERC_FLAG);
  }

  LoopVar11           = Child (LoopVar4, mText[LoopVar10 + mLevel[LoopVar4]]);
  LoopVar10           = mPrev[LoopVar11];
  LoopVar9           = mNext[LoopVar11];
  mNext[LoopVar10]    = LoopVar9;
  mPrev[LoopVar9]    = LoopVar10;
  LoopVar10           = mPrev[LoopVar4];
  mNext[LoopVar10]    = LoopVar11;
  mPrev[LoopVar11]    = LoopVar10;
  LoopVar10           = mNext[LoopVar4];
  mPrev[LoopVar10]    = LoopVar11;
  mNext[LoopVar11]    = LoopVar10;
  mParent[LoopVar11]  = mParent[LoopVar4];
  mParent[LoopVar4]  = NIL;
  mNext[LoopVar4]    = mAvail;
  mAvail      = LoopVar4;
}

/**
  Read in source data

  @param[out] LoopVar7   The buffer to hold the data.
  @param[in] LoopVar8    The number of bytes to read.

  @return The number of bytes actually read.
**/
INT32
FreadCrc (
  OUT UINT8 *LoopVar7,
  IN  INT32 LoopVar8
  )
{
  INT32 LoopVar1;

  for (LoopVar1 = 0; mSrc < mSrcUpperLimit && LoopVar1 < LoopVar8; LoopVar1++) {
    *LoopVar7++ = *mSrc++;
  }

  LoopVar8 = LoopVar1;

  LoopVar7 -= LoopVar8;
  mOrigSize += LoopVar8;
  LoopVar1--;
  while (LoopVar1 >= 0) {
    UPDATE_CRC (*LoopVar7++);
    LoopVar1--;
  }

  return LoopVar8;
}

/**
  Advance the current position (read in new data if needed).
  Delete outdated string info. Find a match string for current position.

  @retval TRUE      The operation was successful.
  @retval FALSE     The operation failed due to insufficient memory.
**/
BOOLEAN
GetNextMatch (
  VOID
  )
{
  INT32 LoopVar8;
  VOID  *Temp;

  mRemainder--;
  mPos++;
  if (mPos == WNDSIZ * 2) {
    Temp = AllocateZeroPool (WNDSIZ + MAXMATCH);
    if (Temp == NULL) {
      return (FALSE);
    }
    CopyMem (Temp, &mText[WNDSIZ], WNDSIZ + MAXMATCH);
    CopyMem (&mText[0], Temp, WNDSIZ + MAXMATCH);
    FreePool (Temp);
    LoopVar8 = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
    mRemainder += LoopVar8;
    mPos = WNDSIZ;
  }

  DeleteNode ();
  InsertNode ();

  return (TRUE);
}

/**
  Send entry LoopVar1 down the queue.

  @param[in] LoopVar1    The index of the item to move.
**/
VOID
DownHeap (
  IN INT32 i
  )
{
  INT32 LoopVar1;

  INT32 LoopVar2;

  //
  // priority queue: send i-th entry down heap
  //
  LoopVar2 = mHeap[i];
  LoopVar1 = 2 * i;
  while (LoopVar1 <= mHeapSize) {
    if (LoopVar1 < mHeapSize && mFreq[mHeap[LoopVar1]] > mFreq[mHeap[LoopVar1 + 1]]) {
      LoopVar1++;
    }

    if (mFreq[LoopVar2] <= mFreq[mHeap[LoopVar1]]) {
      break;
    }

    mHeap[i]  = mHeap[LoopVar1];
    i         = LoopVar1;
    LoopVar1         = 2 * i;
  }

  mHeap[i] = (INT16) LoopVar2;
}

/**
  Count the number of each code length for a Huffman tree.

  @param[in] LoopVar1      The top node.
**/
VOID
CountLen (
  IN INT32 LoopVar1
  )
{
  if (LoopVar1 < mTempInt32) {
    mLenCnt[(mHuffmanDepth < 16) ? mHuffmanDepth : 16]++;
  } else {
    mHuffmanDepth++;
    CountLen (mLeft[LoopVar1]);
    CountLen (mRight[LoopVar1]);
    mHuffmanDepth--;
  }
}

/**
  Create code length array for a Huffman tree.

  @param[in] Root   The root of the tree.
**/
VOID
MakeLen (
  IN INT32 Root
  )
{
  INT32   LoopVar1;

  INT32   LoopVar2;
  UINT32  Cum;

  for (LoopVar1 = 0; LoopVar1 <= 16; LoopVar1++) {
    mLenCnt[LoopVar1] = 0;
  }

  CountLen (Root);

  //
  // Adjust the length count array so that
  // no code will be generated longer than its designated length
  //
  Cum = 0;
  for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
    Cum += mLenCnt[LoopVar1] << (16 - LoopVar1);
  }

  while (Cum != (1U << 16)) {
    mLenCnt[16]--;
    for (LoopVar1 = 15; LoopVar1 > 0; LoopVar1--) {
      if (mLenCnt[LoopVar1] != 0) {
        mLenCnt[LoopVar1]--;
        mLenCnt[LoopVar1 + 1] += 2;
        break;
      }
    }

    Cum--;
  }

  for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
    LoopVar2 = mLenCnt[LoopVar1];
    LoopVar2--;
    while (LoopVar2 >= 0) {
      mLen[*mSortPtr++] = (UINT8) LoopVar1;
      LoopVar2--;
    }
  }
}

/**
  Assign code to each symbol based on the code length array.

  @param[in] LoopVar8      The number of symbols.
  @param[in] Len    The code length array.
  @param[out] Code  The stores codes for each symbol.
**/
VOID
MakeCode (
  IN  INT32         LoopVar8,
  IN  UINT8 Len[    ],
  OUT UINT16 Code[  ]
  )
{
  INT32   LoopVar1;
  UINT16  Start[18];

  Start[1] = 0;
  for (LoopVar1 = 1; LoopVar1 <= 16; LoopVar1++) {
    Start[LoopVar1 + 1] = (UINT16) ((Start[LoopVar1] + mLenCnt[LoopVar1]) << 1);
  }

  for (LoopVar1 = 0; LoopVar1 < LoopVar8; LoopVar1++) {
    Code[LoopVar1] = Start[Len[LoopVar1]]++;
  }
}

/**
  Generates Huffman codes given a frequency distribution of symbols.

  @param[in] NParm      The number of symbols.
  @param[in] FreqParm   The frequency of each symbol.
  @param[out] LenParm   The code length for each symbol.
  @param[out] CodeParm  The code for each symbol.

  @return The root of the Huffman tree.
**/
INT32
MakeTree (
  IN  INT32             NParm,
  IN  UINT16  FreqParm[ ],
  OUT UINT8   LenParm[  ],
  OUT UINT16  CodeParm[ ]
  )
{
  INT32 LoopVar1;

  INT32 LoopVar2;

  INT32 LoopVar3;

  INT32 Avail;

  //
  // make tree, calculate len[], return root
  //
  mTempInt32        = NParm;
  mFreq     = FreqParm;
  mLen      = LenParm;
  Avail     = mTempInt32;
  mHeapSize = 0;
  mHeap[1]  = 0;
  for (LoopVar1 = 0; LoopVar1 < mTempInt32; LoopVar1++) {
    mLen[LoopVar1] = 0;
    if ((mFreq[LoopVar1]) != 0) {
      mHeapSize++;
      mHeap[mHeapSize] = (INT16) LoopVar1;
    }
  }

  if (mHeapSize < 2) {
    CodeParm[mHeap[1]] = 0;
    return mHeap[1];
  }

  for (LoopVar1 = mHeapSize / 2; LoopVar1 >= 1; LoopVar1--) {
    //
    // make priority queue
    //
    DownHeap (LoopVar1);
  }

  mSortPtr = CodeParm;
  do {
    LoopVar1 = mHeap[1];
    if (LoopVar1 < mTempInt32) {
      *mSortPtr++ = (UINT16) LoopVar1;
    }

    mHeap[1] = mHeap[mHeapSize--];
    DownHeap (1);
    LoopVar2 = mHeap[1];
    if (LoopVar2 < mTempInt32) {
      *mSortPtr++ = (UINT16) LoopVar2;
    }

    LoopVar3         = Avail++;
    mFreq[LoopVar3]  = (UINT16) (mFreq[LoopVar1] + mFreq[LoopVar2]);
    mHeap[1]  = (INT16) LoopVar3;
    DownHeap (1);
    mLeft[LoopVar3]  = (UINT16) LoopVar1;
    mRight[LoopVar3] = (UINT16) LoopVar2;
  } while (mHeapSize > 1);

  mSortPtr = CodeParm;
  MakeLen (LoopVar3);
  MakeCode (NParm, LenParm, CodeParm);

  //
  // return root
  //
  return LoopVar3;
}

/**
  Outputs rightmost LoopVar8 bits of x

  @param[in] LoopVar8   The rightmost LoopVar8 bits of the data is used.
  @param[in] x   The data.
**/
VOID
PutBits (
  IN INT32    LoopVar8,
  IN UINT32   x
  )
{
  UINT8 Temp;

  if (LoopVar8 < mBitCount) {
    mSubBitBuf |= x << (mBitCount -= LoopVar8);
  } else {

    Temp = (UINT8)(mSubBitBuf | (x >> (LoopVar8 -= mBitCount)));
    if (mDst < mDstUpperLimit) {
      *mDst++ = Temp;
    }
    mCompSize++;

    if (LoopVar8 < UINT8_BIT) {
      mSubBitBuf = x << (mBitCount = UINT8_BIT - LoopVar8);
    } else {

      Temp = (UINT8)(x >> (LoopVar8 - UINT8_BIT));
      if (mDst < mDstUpperLimit) {
        *mDst++ = Temp;
      }
      mCompSize++;

      mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - LoopVar8);
    }
  }
}

/**
  Encode a signed 32 bit number.

  @param[in] LoopVar5     The number to encode.
**/
VOID
EncodeC (
  IN INT32 LoopVar5
  )
{
  PutBits (mCLen[LoopVar5], mCCode[LoopVar5]);
}

/**
  Encode a unsigned 32 bit number.

  @param[in] LoopVar7     The number to encode.
**/
VOID
EncodeP (
  IN UINT32 LoopVar7
  )
{
  UINT32  LoopVar5;

  UINT32  LoopVar6;

  LoopVar5 = 0;
  LoopVar6 = LoopVar7;
  while (LoopVar6 != 0) {
    LoopVar6 >>= 1;
    LoopVar5++;
  }

  PutBits (mPTLen[LoopVar5], mPTCode[LoopVar5]);
  if (LoopVar5 > 1) {
    PutBits(LoopVar5 - 1, LoopVar7 & (0xFFFFU >> (17 - LoopVar5)));
  }
}

/**
  Count the frequencies for the Extra Set.

**/
VOID
CountTFreq (
  VOID
  )
{
  INT32 LoopVar1;

  INT32 LoopVar3;

  INT32 LoopVar8;

  INT32 Count;

  for (LoopVar1 = 0; LoopVar1 < NT; LoopVar1++) {
    mTFreq[LoopVar1] = 0;
  }

  LoopVar8 = NC;
  while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
    LoopVar8--;
  }

  LoopVar1 = 0;
  while (LoopVar1 < LoopVar8) {
    LoopVar3 = mCLen[LoopVar1++];
    if (LoopVar3 == 0) {
      Count = 1;
      while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
        LoopVar1++;
        Count++;
      }

      if (Count <= 2) {
        mTFreq[0] = (UINT16) (mTFreq[0] + Count);
      } else if (Count <= 18) {
        mTFreq[1]++;
      } else if (Count == 19) {
        mTFreq[0]++;
        mTFreq[1]++;
      } else {
        mTFreq[2]++;
      }
    } else {
      ASSERT((LoopVar3+2)<(2 * NT - 1));
      mTFreq[LoopVar3 + 2]++;
    }
  }
}

/**
  Outputs the code length array for the Extra Set or the Position Set.

  @param[in] LoopVar8       The number of symbols.
  @param[in] nbit           The number of bits needed to represent 'LoopVar8'.
  @param[in] Special        The special symbol that needs to be take care of.

**/
VOID
WritePTLen (
  IN INT32 LoopVar8,
  IN INT32 nbit,
  IN INT32 Special
  )
{
  INT32 LoopVar1;

  INT32 LoopVar3;

  while (LoopVar8 > 0 && mPTLen[LoopVar8 - 1] == 0) {
    LoopVar8--;
  }

  PutBits (nbit, LoopVar8);
  LoopVar1 = 0;
  while (LoopVar1 < LoopVar8) {
    LoopVar3 = mPTLen[LoopVar1++];
    if (LoopVar3 <= 6) {
      PutBits (3, LoopVar3);
    } else {
      PutBits (LoopVar3 - 3, (1U << (LoopVar3 - 3)) - 2);
    }

    if (LoopVar1 == Special) {
      while (LoopVar1 < 6 && mPTLen[LoopVar1] == 0) {
        LoopVar1++;
      }

      PutBits (2, (LoopVar1 - 3) & 3);
    }
  }
}

/**
  Outputs the code length array for Char&Length Set.
**/
VOID
WriteCLen (
  VOID
  )
{
  INT32 LoopVar1;

  INT32 LoopVar3;

  INT32 LoopVar8;

  INT32 Count;

  LoopVar8 = NC;
  while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
    LoopVar8--;
  }

  PutBits (CBIT, LoopVar8);
  LoopVar1 = 0;
  while (LoopVar1 < LoopVar8) {
    LoopVar3 = mCLen[LoopVar1++];
    if (LoopVar3 == 0) {
      Count = 1;
      while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
        LoopVar1++;
        Count++;
      }

      if (Count <= 2) {
        for (LoopVar3 = 0; LoopVar3 < Count; LoopVar3++) {
          PutBits (mPTLen[0], mPTCode[0]);
        }
      } else if (Count <= 18) {
        PutBits (mPTLen[1], mPTCode[1]);
        PutBits (4, Count - 3);
      } else if (Count == 19) {
        PutBits (mPTLen[0], mPTCode[0]);
        PutBits (mPTLen[1], mPTCode[1]);
        PutBits (4, 15);
      } else {
        PutBits (mPTLen[2], mPTCode[2]);
        PutBits (CBIT, Count - 20);
      }
    } else {
      ASSERT((LoopVar3+2)<NPT);
      PutBits (mPTLen[LoopVar3 + 2], mPTCode[LoopVar3 + 2]);
    }
  }
}

/**
  Huffman code the block and output it.

**/
VOID
SendBlock (
  VOID
  )
{
  UINT32  LoopVar1;

  UINT32  LoopVar3;

  UINT32  Flags;

  UINT32  Root;

  UINT32  Pos;

  UINT32  Size;
  Flags = 0;

  Root  = MakeTree (NC, mCFreq, mCLen, mCCode);
  Size  = mCFreq[Root];
  PutBits (16, Size);
  if (Root >= NC) {
    CountTFreq ();
    Root = MakeTree (NT, mTFreq, mPTLen, mPTCode);
    if (Root >= NT) {
      WritePTLen (NT, TBIT, 3);
    } else {
      PutBits (TBIT, 0);
      PutBits (TBIT, Root);
    }

    WriteCLen ();
  } else {
    PutBits (TBIT, 0);
    PutBits (TBIT, 0);
    PutBits (CBIT, 0);
    PutBits (CBIT, Root);
  }

  Root = MakeTree (NP, mPFreq, mPTLen, mPTCode);
  if (Root >= NP) {
    WritePTLen (NP, PBIT, -1);
  } else {
    PutBits (PBIT, 0);
    PutBits (PBIT, Root);
  }

  Pos = 0;
  for (LoopVar1 = 0; LoopVar1 < Size; LoopVar1++) {
    if (LoopVar1 % UINT8_BIT == 0) {
      Flags = mBuf[Pos++];
    } else {
      Flags <<= 1;
    }
    if ((Flags & (1U << (UINT8_BIT - 1))) != 0){
      EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
      LoopVar3 = mBuf[Pos++] << UINT8_BIT;
      LoopVar3 += mBuf[Pos++];

      EncodeP (LoopVar3);
    } else {
      EncodeC (mBuf[Pos++]);
    }
  }

  SetMem (mCFreq, NC * sizeof (UINT16), 0);
  SetMem (mPFreq, NP * sizeof (UINT16), 0);
}

/**
  Start the huffman encoding.

**/
VOID
HufEncodeStart (
  VOID
  )
{
  SetMem (mCFreq, NC * sizeof (UINT16), 0);
  SetMem (mPFreq, NP * sizeof (UINT16), 0);

  mOutputPos = mOutputMask = 0;

  mBitCount   = UINT8_BIT;
  mSubBitBuf  = 0;
}

/**
  Outputs an Original Character or a Pointer.

  @param[in] LoopVar5     The original character or the 'String Length' element of
                   a Pointer.
  @param[in] LoopVar7     The 'Position' field of a Pointer.
**/
VOID
CompressOutput (
  IN UINT32 LoopVar5,
  IN UINT32 LoopVar7
  )
{
  STATIC UINT32 CPos;

  if ((mOutputMask >>= 1) == 0) {
    mOutputMask = 1U << (UINT8_BIT - 1);
    if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
      SendBlock ();
      mOutputPos = 0;
    }

    CPos        = mOutputPos++;
    mBuf[CPos]  = 0;
  }
  mBuf[mOutputPos++] = (UINT8) LoopVar5;
  mCFreq[LoopVar5]++;
  if (LoopVar5 >= (1U << UINT8_BIT)) {
    mBuf[CPos] = (UINT8)(mBuf[CPos]|mOutputMask);
    mBuf[mOutputPos++] = (UINT8)(LoopVar7 >> UINT8_BIT);
    mBuf[mOutputPos++] = (UINT8) LoopVar7;
    LoopVar5                  = 0;
    while (LoopVar7!=0) {
      LoopVar7 >>= 1;
      LoopVar5++;
    }
    mPFreq[LoopVar5]++;
  }
}

/**
  End the huffman encoding.

**/
VOID
HufEncodeEnd (
  VOID
  )
{
  SendBlock ();

  //
  // Flush remaining bits
  //
  PutBits (UINT8_BIT - 1, 0);
}

/**
  The main controlling routine for compression process.

  @retval EFI_SUCCESS           The compression is successful.
  @retval EFI_OUT_0F_RESOURCES  Not enough memory for compression process.
**/
EFI_STATUS
Encode (
  VOID
  )
{
  EFI_STATUS  Status;
  INT32       LastMatchLen;
  NODE        LastMatchPos;

  Status = AllocateMemory ();
  if (EFI_ERROR (Status)) {
    FreeMemory ();
    return Status;
  }

  InitSlide ();

  HufEncodeStart ();

  mRemainder  = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);

  mMatchLen   = 0;
  mPos        = WNDSIZ;
  InsertNode ();
  if (mMatchLen > mRemainder) {
    mMatchLen = mRemainder;
  }

  while (mRemainder > 0) {
    LastMatchLen  = mMatchLen;
    LastMatchPos  = mMatchPos;
    if (!GetNextMatch ()) {
      Status = EFI_OUT_OF_RESOURCES;
    }
    if (mMatchLen > mRemainder) {
      mMatchLen = mRemainder;
    }

    if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
      //
      // Not enough benefits are gained by outputting a pointer,
      // so just output the original character
      //
      CompressOutput(mText[mPos - 1], 0);
    } else {
      //
      // Outputting a pointer is beneficial enough, do it.
      //

      CompressOutput(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
             (mPos - LastMatchPos - 2) & (WNDSIZ - 1));
      LastMatchLen--;
      while (LastMatchLen > 0) {
        if (!GetNextMatch ()) {
          Status = EFI_OUT_OF_RESOURCES;
        }
        LastMatchLen--;
      }

      if (mMatchLen > mRemainder) {
        mMatchLen = mRemainder;
      }
    }
  }

  HufEncodeEnd ();
  FreeMemory ();
  return (Status);
}

/**
  The compression routine.

  @param[in]       SrcBuffer     The buffer containing the source data.
  @param[in]       SrcSize       Number of bytes in SrcBuffer.
  @param[in]       DstBuffer     The buffer to put the compressed image in.
  @param[in, out]  DstSize       On input the size (in bytes) of DstBuffer, on
                                 return the number of bytes placed in DstBuffer.

  @retval EFI_SUCCESS           The compression was sucessful.
  @retval EFI_BUFFER_TOO_SMALL  The buffer was too small.  DstSize is required.
**/
EFI_STATUS
Compress (
  IN      VOID    *SrcBuffer,
  IN      UINT64  SrcSize,
  IN      VOID    *DstBuffer,
  IN OUT  UINT64  *DstSize
  )
{
  EFI_STATUS  Status;

  //
  // Initializations
  //
  mBufSiz         = 0;
  mBuf            = NULL;
  mText           = NULL;
  mLevel          = NULL;
  mChildCount     = NULL;
  mPosition       = NULL;
  mParent         = NULL;
  mPrev           = NULL;
  mNext           = NULL;

  mSrc            = SrcBuffer;
  mSrcUpperLimit  = mSrc + SrcSize;
  mDst            = DstBuffer;
  mDstUpperLimit  = mDst +*DstSize;

  PutDword (0L);
  PutDword (0L);

  MakeCrcTable ();

  mOrigSize             = mCompSize = 0;
  mCrc                  = INIT_CRC;

  //
  // Compress it
  //
  Status = Encode ();
  if (EFI_ERROR (Status)) {
    return EFI_OUT_OF_RESOURCES;
  }
  //
  // Null terminate the compressed data
  //
  if (mDst < mDstUpperLimit) {
    *mDst++ = 0;
  }
  //
  // Fill in compressed size and original size
  //
  mDst = DstBuffer;
  PutDword (mCompSize + 1);
  PutDword (mOrigSize);

  //
  // Return
  //
  if (mCompSize + 1 + 8 > *DstSize) {
    *DstSize = mCompSize + 1 + 8;
    return EFI_BUFFER_TOO_SMALL;
  } else {
    *DstSize = mCompSize + 1 + 8;
    return EFI_SUCCESS;
  }

}