[mirror_edk2.git] / BaseTools / Source / C / TianoCompress / TianoCompress.c

/** @file\r
Compression routine. The compression algorithm is a mixture of LZ77 and Huffman\r
coding. LZ77 transforms the source data into a sequence of Original Characters\r
and Pointers to repeated strings.\r
This sequence is further divided into Blocks and Huffman codings are applied to\r
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
\r
#include "Compress.h"\r
#include "Decompress.h"\r
#include "TianoCompress.h"\r
#include "EfiUtilityMsgs.h"\r
#include "ParseInf.h"\r
#include <stdio.h>\r
#include "assert.h"\r
\r
//\r
// Macro Definitions\r
//\r
static BOOLEAN VerboseMode = FALSE;\r
static BOOLEAN QuietMode = FALSE;\r
#undef UINT8_MAX\r
#define UINT8_MAX     0xff\r
#define UINT8_BIT     8\r
#define THRESHOLD     3\r
#define INIT_CRC      0\r
#define WNDBIT        19\r
#define WNDSIZ        (1U << WNDBIT)\r
#define MAXMATCH      256\r
#define BLKSIZ        (1U << 14)  // 16 * 1024U\r
#define PERC_FLAG     0x80000000U\r
#define CODE_BIT      16\r
#define NIL           0\r
#define MAX_HASH_VAL  (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)\r
#define HASH(p, c)    ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)\r
#define CRCPOLY       0xA001\r
#define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 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  5\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
//\r
//  Global Variables\r
//\r
STATIC BOOLEAN ENCODE = FALSE;\r
STATIC BOOLEAN DECODE = FALSE;\r
STATIC BOOLEAN UEFIMODE = FALSE;\r
STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;\r
STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;\r
STATIC INT16  mHeap[NC + 1];\r
STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;\r
STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;\r
STATIC UINT32 mCompSize, mOrigSize;\r
\r
STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],\r
  mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];\r
\r
STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;\r
\r
static  UINT64     DebugLevel;\r
static  BOOLEAN    DebugMode;\r
//\r
// functions\r
//\r
EFI_STATUS\r
TianoCompress (\r
  IN      UINT8   *SrcBuffer,\r
  IN      UINT32  SrcSize,\r
  IN      UINT8   *DstBuffer,\r
  IN OUT  UINT32  *DstSize\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  The internal implementation of [Efi/Tiano]Compress().\r
\r
Arguments:\r
\r
  SrcBuffer   - The buffer storing the source data\r
  SrcSize     - The size of source data\r
  DstBuffer   - The buffer to store the compressed data\r
\r
  Version     - The version of de/compression algorithm.\r
                Version 1 for EFI 1.1 de/compression algorithm.\r
                Version 2 for Tiano de/compression algorithm.\r
\r
Returns:\r
\r
  EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,\r
                DstSize contains the size needed.\r
  EFI_SUCCESS           - Compression is successful.\r
  EFI_OUT_OF_RESOURCES  - No resource to complete function.\r
  EFI_INVALID_PARAMETER - Parameter supplied is wrong.\r
\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
\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
\r
  if (mDst < mDstUpperLimit) {\r
    *mDst++ = 0;\r
  }\r
\r
  //\r
  // Fill in compressed size and original size\r
  //\r
  mDst = DstBuffer;\r
\r
  PutDword (mCompSize + 1);\r
  PutDword (mOrigSize);\r
  //\r
  // Return\r
  //\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
\r
STATIC\r
VOID\r
PutDword (\r
  IN UINT32 Data\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Put a dword to output stream\r
\r
Arguments:\r
\r
  Data    - the dword to put\r
\r
Returns: (VOID)\r
\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
STATIC\r
EFI_STATUS\r
AllocateMemory (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Allocate memory spaces for data structures used in compression process\r
\r
Arguments:\r
  VOID\r
\r
Returns:\r
\r
  EFI_SUCCESS           - Memory is allocated successfully\r
  EFI_OUT_OF_RESOURCES  - Allocation fails\r
\r
--*/\r
{\r
  UINT32  Index;\r
\r
  mText = malloc (WNDSIZ * 2 + MAXMATCH);\r
  if (mText == NULL) {\r
    Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");\r
    return EFI_OUT_OF_RESOURCES;\r
  }\r
  for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {\r
    mText[Index] = 0;\r
  }\r
\r
  mLevel      = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));\r
  mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));\r
  mPosition   = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));\r
  mParent     = malloc (WNDSIZ * 2 * sizeof (*mParent));\r
  mPrev       = malloc (WNDSIZ * 2 * sizeof (*mPrev));\r
  mNext       = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));\r
  if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||\r
    mParent == NULL || mPrev == NULL || mNext == NULL) {\r
    Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!");\r
    return EFI_OUT_OF_RESOURCES;\r
  }\r
\r
  mBufSiz     = BLKSIZ;\r
  mBuf        = malloc (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 = malloc (mBufSiz);\r
  }\r
\r
  mBuf[0] = 0;\r
\r
  return EFI_SUCCESS;\r
}\r
\r
VOID\r
FreeMemory (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Called when compression is completed to free memory previously allocated.\r
\r
Arguments: (VOID)\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  if (mText != NULL) {\r
    free (mText);\r
  }\r
\r
  if (mLevel != NULL) {\r
    free (mLevel);\r
  }\r
\r
  if (mChildCount != NULL) {\r
    free (mChildCount);\r
  }\r
\r
  if (mPosition != NULL) {\r
    free (mPosition);\r
  }\r
\r
  if (mParent != NULL) {\r
    free (mParent);\r
  }\r
\r
  if (mPrev != NULL) {\r
    free (mPrev);\r
  }\r
\r
  if (mNext != NULL) {\r
    free (mNext);\r
  }\r
\r
  if (mBuf != NULL) {\r
    free (mBuf);\r
  }\r
\r
  return ;\r
}\r
\r
STATIC\r
VOID\r
InitSlide (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Initialize String Info Log data structures\r
\r
Arguments: (VOID)\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  NODE  Index;\r
\r
  for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {\r
    mLevel[Index]     = 1;\r
    mPosition[Index]  = NIL;  // sentinel\r
  }\r
\r
  for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {\r
    mParent[Index] = NIL;\r
  }\r
\r
  mAvail = 1;\r
  for (Index = 1; Index < WNDSIZ - 1; Index++) {\r
    mNext[Index] = (NODE) (Index + 1);\r
  }\r
\r
  mNext[WNDSIZ - 1] = NIL;\r
  for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {\r
    mNext[Index] = NIL;\r
  }\r
}\r
\r
STATIC\r
NODE\r
Child (\r
  IN NODE  NodeQ,\r
  IN UINT8 CharC\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Find child node given the parent node and the edge character\r
\r
Arguments:\r
\r
  NodeQ       - the parent node\r
  CharC       - the edge character\r
\r
Returns:\r
\r
  The child node (NIL if not found)\r
\r
--*/\r
{\r
  NODE  NodeR;\r
\r
  NodeR = mNext[HASH (NodeQ, CharC)];\r
  //\r
  // sentinel\r
  //\r
  mParent[NIL] = NodeQ;\r
  while (mParent[NodeR] != NodeQ) {\r
    NodeR = mNext[NodeR];\r
  }\r
\r
  return NodeR;\r
}\r
\r
STATIC\r
VOID\r
MakeChild (\r
  IN NODE  Parent,\r
  IN UINT8 CharC,\r
  IN NODE  Child\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Create a new child for a given parent node.\r
\r
Arguments:\r
\r
  Parent       - the parent node\r
  CharC   - the edge character\r
  Child       - the child node\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  NODE  Node1;\r
  NODE  Node2;\r
\r
  Node1           = (NODE) HASH (Parent, CharC);\r
  Node2           = mNext[Node1];\r
  mNext[Node1]    = Child;\r
  mNext[Child]    = Node2;\r
  mPrev[Node2]    = Child;\r
  mPrev[Child]    = Node1;\r
  mParent[Child]  = Parent;\r
  mChildCount[Parent]++;\r
}\r
\r
STATIC\r
VOID\r
Split (\r
  NODE Old\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Split a node.\r
\r
Arguments:\r
\r
  Old     - the node to split\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  NODE  New;\r
  NODE  TempNode;\r
\r
  New               = mAvail;\r
  mAvail            = mNext[New];\r
  mChildCount[New]  = 0;\r
  TempNode          = mPrev[Old];\r
  mPrev[New]        = TempNode;\r
  mNext[TempNode]   = New;\r
  TempNode          = mNext[Old];\r
  mNext[New]        = TempNode;\r
  mPrev[TempNode]   = 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
STATIC\r
VOID\r
InsertNode (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Insert string info for current position into the String Info Log\r
\r
Arguments: (VOID)\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  NODE  NodeQ;\r
  NODE  NodeR;\r
  NODE  Index2;\r
  NODE  NodeT;\r
  UINT8 CharC;\r
  UINT8 *t1;\r
  UINT8 *t2;\r
\r
  if (mMatchLen >= 4) {\r
    //\r
    // We have just got a long match, the target tree\r
    // can be located by MatchPos + 1. Traverse 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
    NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);\r
    NodeQ = mParent[NodeR];\r
    while (NodeQ == NIL) {\r
      NodeR = mNext[NodeR];\r
      NodeQ = mParent[NodeR];\r
    }\r
\r
    while (mLevel[NodeQ] >= mMatchLen) {\r
      NodeR = NodeQ;\r
      NodeQ = mParent[NodeQ];\r
    }\r
\r
    NodeT = NodeQ;\r
    while (mPosition[NodeT] < 0) {\r
      mPosition[NodeT]  = mPos;\r
      NodeT             = mParent[NodeT];\r
    }\r
\r
    if (NodeT < WNDSIZ) {\r
      mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);\r
    }\r
  } else {\r
    //\r
    // Locate the target tree\r
    //\r
    NodeQ = (NODE) (mText[mPos] + WNDSIZ);\r
    CharC = mText[mPos + 1];\r
    NodeR = Child (NodeQ, CharC);\r
    if (NodeR == NIL) {\r
      MakeChild (NodeQ, CharC, mPos);\r
      mMatchLen = 1;\r
      return ;\r
    }\r
\r
    mMatchLen = 2;\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 (NodeR >= WNDSIZ) {\r
      Index2    = MAXMATCH;\r
      mMatchPos = NodeR;\r
    } else {\r
      Index2    = mLevel[NodeR];\r
      mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);\r
    }\r
\r
    if (mMatchPos >= mPos) {\r
      mMatchPos -= WNDSIZ;\r
    }\r
\r
    t1  = &mText[mPos + mMatchLen];\r
    t2  = &mText[mMatchPos + mMatchLen];\r
    while (mMatchLen < Index2) {\r
      if (*t1 != *t2) {\r
        Split (NodeR);\r
        return ;\r
      }\r
\r
      mMatchLen++;\r
      t1++;\r
      t2++;\r
    }\r
\r
    if (mMatchLen >= MAXMATCH) {\r
      break;\r
    }\r
\r
    mPosition[NodeR]  = mPos;\r
    NodeQ             = NodeR;\r
    NodeR             = Child (NodeQ, *t1);\r
    if (NodeR == NIL) {\r
      MakeChild (NodeQ, *t1, mPos);\r
      return ;\r
    }\r
\r
    mMatchLen++;\r
  }\r
\r
  NodeT           = mPrev[NodeR];\r
  mPrev[mPos]     = NodeT;\r
  mNext[NodeT]    = mPos;\r
  NodeT           = mNext[NodeR];\r
  mNext[mPos]     = NodeT;\r
  mPrev[NodeT]    = mPos;\r
  mParent[mPos]   = NodeQ;\r
  mParent[NodeR]  = NIL;\r
\r
  //\r
  // Special usage of 'next'\r
  //\r
  mNext[NodeR] = mPos;\r
\r
}\r
\r
STATIC\r
VOID\r
DeleteNode (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Delete outdated string info. (The Usage of PERC_FLAG\r
  ensures a clean deletion)\r
\r
Arguments: (VOID)\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  NODE  NodeQ;\r
  NODE  NodeR;\r
  NODE  NodeS;\r
  NODE  NodeT;\r
  NODE  NodeU;\r
\r
  if (mParent[mPos] == NIL) {\r
    return ;\r
  }\r
\r
  NodeR         = mPrev[mPos];\r
  NodeS         = mNext[mPos];\r
  mNext[NodeR]  = NodeS;\r
  mPrev[NodeS]  = NodeR;\r
  NodeR         = mParent[mPos];\r
  mParent[mPos] = NIL;\r
  if (NodeR >= WNDSIZ) {\r
    return ;\r
  }\r
\r
  mChildCount[NodeR]--;\r
  if (mChildCount[NodeR] > 1) {\r
    return ;\r
  }\r
\r
  NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);\r
  if (NodeT >= mPos) {\r
    NodeT -= WNDSIZ;\r
  }\r
\r
  NodeS = NodeT;\r
  NodeQ = mParent[NodeR];\r
  NodeU = mPosition[NodeQ];\r
  while (NodeU & (UINT32) PERC_FLAG) {\r
    NodeU &= (UINT32)~PERC_FLAG;\r
    if (NodeU >= mPos) {\r
      NodeU -= WNDSIZ;\r
    }\r
\r
    if (NodeU > NodeS) {\r
      NodeS = NodeU;\r
    }\r
\r
    mPosition[NodeQ]  = (NODE) (NodeS | WNDSIZ);\r
    NodeQ             = mParent[NodeQ];\r
    NodeU             = mPosition[NodeQ];\r
  }\r
\r
  if (NodeQ < WNDSIZ) {\r
    if (NodeU >= mPos) {\r
      NodeU -= WNDSIZ;\r
    }\r
\r
    if (NodeU > NodeS) {\r
      NodeS = NodeU;\r
    }\r
\r
    mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);\r
  }\r
\r
  NodeS           = Child (NodeR, mText[NodeT + mLevel[NodeR]]);\r
  NodeT           = mPrev[NodeS];\r
  NodeU           = mNext[NodeS];\r
  mNext[NodeT]    = NodeU;\r
  mPrev[NodeU]    = NodeT;\r
  NodeT           = mPrev[NodeR];\r
  mNext[NodeT]    = NodeS;\r
  mPrev[NodeS]    = NodeT;\r
  NodeT           = mNext[NodeR];\r
  mPrev[NodeT]    = NodeS;\r
  mNext[NodeS]    = NodeT;\r
  mParent[NodeS]  = mParent[NodeR];\r
  mParent[NodeR]  = NIL;\r
  mNext[NodeR]    = mAvail;\r
  mAvail          = NodeR;\r
}\r
\r
STATIC\r
VOID\r
GetNextMatch (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\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
Arguments: (VOID)\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  INT32 Number;\r
\r
  mRemainder--;\r
  mPos++;\r
  if (mPos == WNDSIZ * 2) {\r
    memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);\r
    Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);\r
    mRemainder += Number;\r
    mPos = WNDSIZ;\r
  }\r
\r
  DeleteNode ();\r
  InsertNode ();\r
}\r
\r
STATIC\r
EFI_STATUS\r
Encode (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  The main controlling routine for compression process.\r
\r
Arguments: (VOID)\r
\r
Returns:\r
\r
  EFI_SUCCESS           - The compression is successful\r
  EFI_OUT_0F_RESOURCES  - Not enough memory for compression process\r
\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
    GetNextMatch ();\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
      Output (mText[mPos - 1], 0);\r
\r
    } else {\r
\r
      if (LastMatchLen == THRESHOLD) {\r
        if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {\r
          Output (mText[mPos - 1], 0);\r
          continue;\r
        }\r
      }\r
      //\r
      // Outputting a pointer is beneficial enough, do it.\r
      //\r
      Output (\r
        LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),\r
        (mPos - LastMatchPos - 2) & (WNDSIZ - 1)\r
        );\r
      LastMatchLen--;\r
      while (LastMatchLen > 0) {\r
        GetNextMatch ();\r
        LastMatchLen--;\r
      }\r
\r
      if (mMatchLen > mRemainder) {\r
        mMatchLen = mRemainder;\r
      }\r
    }\r
  }\r
\r
  HufEncodeEnd ();\r
  FreeMemory ();\r
  return EFI_SUCCESS;\r
}\r
\r
STATIC\r
VOID\r
CountTFreq (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Count the frequencies for the Extra Set\r
\r
Arguments: (VOID)\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  INT32 Index;\r
  INT32 Index3;\r
  INT32 Number;\r
  INT32 Count;\r
\r
  for (Index = 0; Index < NT; Index++) {\r
    mTFreq[Index] = 0;\r
  }\r
\r
  Number = NC;\r
  while (Number > 0 && mCLen[Number - 1] == 0) {\r
    Number--;\r
  }\r
\r
  Index = 0;\r
  while (Index < Number) {\r
    Index3 = mCLen[Index++];\r
    if (Index3 == 0) {\r
      Count = 1;\r
      while (Index < Number && mCLen[Index] == 0) {\r
        Index++;\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
      mTFreq[Index3 + 2]++;\r
    }\r
  }\r
}\r
\r
STATIC\r
VOID\r
WritePTLen (\r
  IN INT32 Number,\r
  IN INT32 nbit,\r
  IN INT32 Special\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Outputs the code length array for the Extra Set or the Position Set.\r
\r
Arguments:\r
\r
  Number       - the number of symbols\r
  nbit    - the number of bits needed to represent 'n'\r
  Special - the special symbol that needs to be take care of\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  INT32 Index;\r
  INT32 Index3;\r
\r
  while (Number > 0 && mPTLen[Number - 1] == 0) {\r
    Number--;\r
  }\r
\r
  PutBits (nbit, Number);\r
  Index = 0;\r
  while (Index < Number) {\r
    Index3 = mPTLen[Index++];\r
    if (Index3 <= 6) {\r
      PutBits (3, Index3);\r
    } else {\r
      PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);\r
    }\r
\r
    if (Index == Special) {\r
      while (Index < 6 && mPTLen[Index] == 0) {\r
        Index++;\r
      }\r
\r
      PutBits (2, (Index - 3) & 3);\r
    }\r
  }\r
}\r
\r
STATIC\r
VOID\r
WriteCLen (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Outputs the code length array for Char&Length Set\r
\r
Arguments: (VOID)\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  INT32 Index;\r
  INT32 Index3;\r
  INT32 Number;\r
  INT32 Count;\r
\r
  Number = NC;\r
  while (Number > 0 && mCLen[Number - 1] == 0) {\r
    Number--;\r
  }\r
\r
  PutBits (CBIT, Number);\r
  Index = 0;\r
  while (Index < Number) {\r
    Index3 = mCLen[Index++];\r
    if (Index3 == 0) {\r
      Count = 1;\r
      while (Index < Number && mCLen[Index] == 0) {\r
        Index++;\r
        Count++;\r
      }\r
\r
      if (Count <= 2) {\r
        for (Index3 = 0; Index3 < Count; Index3++) {\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
      PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);\r
    }\r
  }\r
}\r
\r
STATIC\r
VOID\r
EncodeC (\r
  IN INT32 Value\r
  )\r
{\r
  PutBits (mCLen[Value], mCCode[Value]);\r
}\r
\r
STATIC\r
VOID\r
EncodeP (\r
  IN UINT32 Value\r
  )\r
{\r
  UINT32  Index;\r
  UINT32  NodeQ;\r
\r
  Index = 0;\r
  NodeQ = Value;\r
  while (NodeQ) {\r
    NodeQ >>= 1;\r
    Index++;\r
  }\r
\r
  PutBits (mPTLen[Index], mPTCode[Index]);\r
  if (Index > 1) {\r
    PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));\r
  }\r
}\r
\r
STATIC\r
VOID\r
SendBlock (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Huffman code the block and output it.\r
\r
Arguments:\r
  (VOID)\r
\r
Returns:\r
  (VOID)\r
\r
--*/\r
{\r
  UINT32  Index;\r
  UINT32  Index2;\r
  UINT32  Index3;\r
  UINT32  Flags;\r
  UINT32  Root;\r
  UINT32  Pos;\r
  UINT32  Size;\r
  Flags = 0;\r
\r
  Root  = MakeTree (NC, mCFreq, mCLen, mCCode);\r
  Size  = mCFreq[Root];\r
\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 (Index = 0; Index < Size; Index++) {\r
    if (Index % UINT8_BIT == 0) {\r
      Flags = mBuf[Pos++];\r
    } else {\r
      Flags <<= 1;\r
    }\r
\r
    if (Flags & (1U << (UINT8_BIT - 1))) {\r
      EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));\r
      Index3 = mBuf[Pos++];\r
      for (Index2 = 0; Index2 < 3; Index2++) {\r
        Index3 <<= UINT8_BIT;\r
        Index3 += mBuf[Pos++];\r
      }\r
\r
      EncodeP (Index3);\r
    } else {\r
      EncodeC (mBuf[Pos++]);\r
    }\r
  }\r
\r
  for (Index = 0; Index < NC; Index++) {\r
    mCFreq[Index] = 0;\r
  }\r
\r
  for (Index = 0; Index < NP; Index++) {\r
    mPFreq[Index] = 0;\r
  }\r
}\r
\r
STATIC\r
VOID\r
Output (\r
  IN UINT32 CharC,\r
  IN UINT32 Pos\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Outputs an Original Character or a Pointer\r
\r
Arguments:\r
\r
  CharC     - The original character or the 'String Length' element of a Pointer\r
  Pos     - The 'Position' field of a Pointer\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  STATIC UINT32 CPos;\r
\r
  if ((mOutputMask >>= 1) == 0) {\r
    mOutputMask = 1U << (UINT8_BIT - 1);\r
    //\r
    // Check the buffer overflow per outputing UINT8_BIT symbols\r
    // which is an Original Character or a Pointer. The biggest\r
    // symbol is a Pointer which occupies 5 bytes.\r
    //\r
    if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {\r
      SendBlock ();\r
      mOutputPos = 0;\r
    }\r
\r
    CPos        = mOutputPos++;\r
    mBuf[CPos]  = 0;\r
  }\r
\r
  mBuf[mOutputPos++] = (UINT8) CharC;\r
  mCFreq[CharC]++;\r
  if (CharC >= (1U << UINT8_BIT)) {\r
    mBuf[CPos] |= mOutputMask;\r
    mBuf[mOutputPos++]  = (UINT8) (Pos >> 24);\r
    mBuf[mOutputPos++]  = (UINT8) (Pos >> 16);\r
    mBuf[mOutputPos++]  = (UINT8) (Pos >> (UINT8_BIT));\r
    mBuf[mOutputPos++]  = (UINT8) Pos;\r
    CharC               = 0;\r
    while (Pos) {\r
      Pos >>= 1;\r
      CharC++;\r
    }\r
\r
    mPFreq[CharC]++;\r
  }\r
}\r
\r
STATIC\r
VOID\r
HufEncodeStart (\r
  VOID\r
  )\r
{\r
  INT32 Index;\r
\r
  for (Index = 0; Index < NC; Index++) {\r
    mCFreq[Index] = 0;\r
  }\r
\r
  for (Index = 0; Index < NP; Index++) {\r
    mPFreq[Index] = 0;\r
  }\r
\r
  mOutputPos = mOutputMask = 0;\r
  InitPutBits ();\r
  return ;\r
}\r
\r
STATIC\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
  return ;\r
}\r
\r
STATIC\r
VOID\r
MakeCrcTable (\r
  VOID\r
  )\r
{\r
  UINT32  Index;\r
  UINT32  Index2;\r
  UINT32  Temp;\r
\r
  for (Index = 0; Index <= UINT8_MAX; Index++) {\r
    Temp = Index;\r
    for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {\r
      if (Temp & 1) {\r
        Temp = (Temp >> 1) ^ CRCPOLY;\r
      } else {\r
        Temp >>= 1;\r
      }\r
    }\r
\r
    mCrcTable[Index] = (UINT16) Temp;\r
  }\r
}\r
\r
STATIC\r
VOID\r
PutBits (\r
  IN INT32  Number,\r
  IN UINT32 Value\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Outputs rightmost n bits of x\r
\r
Arguments:\r
\r
  Number   - the rightmost n bits of the data is used\r
  x   - the data\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  UINT8 Temp;\r
\r
  while (Number >= mBitCount) {\r
    //\r
    // Number -= mBitCount should never equal to 32\r
    //\r
    Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));\r
\r
    if (mDst < mDstUpperLimit) {\r
      *mDst++ = Temp;\r
    }\r
\r
    mCompSize++;\r
    mSubBitBuf  = 0;\r
    mBitCount   = UINT8_BIT;\r
  }\r
\r
  mSubBitBuf |= Value << (mBitCount -= Number);\r
}\r
\r
STATIC\r
INT32\r
FreadCrc (\r
  OUT UINT8 *Pointer,\r
  IN  INT32 Number\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Read in source data\r
\r
Arguments:\r
\r
  Pointer   - the buffer to hold the data\r
  Number   - number of bytes to read\r
\r
Returns:\r
\r
  number of bytes actually read\r
\r
--*/\r
{\r
  INT32 Index;\r
\r
  for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {\r
    *Pointer++ = *mSrc++;\r
  }\r
\r
  Number = Index;\r
\r
  Pointer -= Number;\r
  mOrigSize += Number;\r
\r
  Index--;\r
  while (Index >= 0) {\r
    UPDATE_CRC (*Pointer++);\r
    Index--;\r
  }\r
\r
  return Number;\r
}\r
\r
STATIC\r
VOID\r
InitPutBits (\r
  VOID\r
  )\r
{\r
  mBitCount   = UINT8_BIT;\r
  mSubBitBuf  = 0;\r
}\r
\r
STATIC\r
VOID\r
CountLen (\r
  IN INT32 Index\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Count the number of each code length for a Huffman tree.\r
\r
Arguments:\r
\r
  Index   - the top node\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  STATIC INT32  Depth = 0;\r
\r
  if (Index < mN) {\r
    mLenCnt[(Depth < 16) ? Depth : 16]++;\r
  } else {\r
    Depth++;\r
    CountLen (mLeft[Index]);\r
    CountLen (mRight[Index]);\r
    Depth--;\r
  }\r
}\r
\r
STATIC\r
VOID\r
MakeLen (\r
  IN INT32 Root\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Create code length array for a Huffman tree\r
\r
Arguments:\r
\r
  Root   - the root of the tree\r
\r
Returns:\r
\r
  VOID\r
\r
--*/\r
{\r
  INT32   Index;\r
  INT32   Index3;\r
  UINT32  Cum;\r
\r
  for (Index = 0; Index <= 16; Index++) {\r
    mLenCnt[Index] = 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 (Index = 16; Index > 0; Index--) {\r
    Cum += mLenCnt[Index] << (16 - Index);\r
  }\r
\r
  while (Cum != (1U << 16)) {\r
    mLenCnt[16]--;\r
    for (Index = 15; Index > 0; Index--) {\r
      if (mLenCnt[Index] != 0) {\r
        mLenCnt[Index]--;\r
        mLenCnt[Index + 1] += 2;\r
        break;\r
      }\r
    }\r
\r
    Cum--;\r
  }\r
\r
  for (Index = 16; Index > 0; Index--) {\r
    Index3 = mLenCnt[Index];\r
    Index3--;\r
    while (Index3 >= 0) {\r
      mLen[*mSortPtr++] = (UINT8) Index;\r
      Index3--;\r
    }\r
  }\r
}\r
\r
STATIC\r
VOID\r
DownHeap (\r
  IN INT32 Index\r
  )\r
{\r
  INT32 Index2;\r
  INT32 Index3;\r
\r
  //\r
  // priority queue: send Index-th entry down heap\r
  //\r
  Index3  = mHeap[Index];\r
  Index2  = 2 * Index;\r
  while (Index2 <= mHeapSize) {\r
    if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {\r
      Index2++;\r
    }\r
\r
    if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {\r
      break;\r
    }\r
\r
    mHeap[Index]  = mHeap[Index2];\r
    Index         = Index2;\r
    Index2        = 2 * Index;\r
  }\r
\r
  mHeap[Index] = (INT16) Index3;\r
}\r
\r
STATIC\r
VOID\r
MakeCode (\r
  IN  INT32       Number,\r
  IN  UINT8 Len[  ],\r
  OUT UINT16 Code[]\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Assign code to each symbol based on the code length array\r
\r
Arguments:\r
\r
  Number     - number of symbols\r
  Len   - the code length array\r
  Code  - stores codes for each symbol\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  INT32   Index;\r
  UINT16  Start[18];\r
\r
  Start[1] = 0;\r
  for (Index = 1; Index <= 16; Index++) {\r
    Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);\r
  }\r
\r
  for (Index = 0; Index < Number; Index++) {\r
    Code[Index] = Start[Len[Index]]++;\r
  }\r
}\r
\r
STATIC\r
INT32\r
MakeTree (\r
  IN  INT32            NParm,\r
  IN  UINT16  FreqParm[],\r
  OUT UINT8   LenParm[ ],\r
  OUT UINT16  CodeParm[]\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Generates Huffman codes given a frequency distribution of symbols\r
\r
Arguments:\r
\r
  NParm    - number of symbols\r
  FreqParm - frequency of each symbol\r
  LenParm  - code length for each symbol\r
  CodeParm - code for each symbol\r
\r
Returns:\r
\r
  Root of the Huffman tree.\r
\r
--*/\r
{\r
  INT32 Index;\r
  INT32 Index2;\r
  INT32 Index3;\r
  INT32 Avail;\r
\r
  //\r
  // make tree, calculate len[], return root\r
  //\r
  mN        = NParm;\r
  mFreq     = FreqParm;\r
  mLen      = LenParm;\r
  Avail     = mN;\r
  mHeapSize = 0;\r
  mHeap[1]  = 0;\r
  for (Index = 0; Index < mN; Index++) {\r
    mLen[Index] = 0;\r
    if (mFreq[Index]) {\r
      mHeapSize++;\r
      mHeap[mHeapSize] = (INT16) Index;\r
    }\r
  }\r
\r
  if (mHeapSize < 2) {\r
    CodeParm[mHeap[1]] = 0;\r
    return mHeap[1];\r
  }\r
\r
  for (Index = mHeapSize / 2; Index >= 1; Index--) {\r
    //\r
    // make priority queue\r
    //\r
    DownHeap (Index);\r
  }\r
\r
  mSortPtr = CodeParm;\r
  do {\r
    Index = mHeap[1];\r
    if (Index < mN) {\r
      *mSortPtr++ = (UINT16) Index;\r
    }\r
\r
    mHeap[1] = mHeap[mHeapSize--];\r
    DownHeap (1);\r
    Index2 = mHeap[1];\r
    if (Index2 < mN) {\r
      *mSortPtr++ = (UINT16) Index2;\r
    }\r
\r
    Index3        = Avail++;\r
    mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);\r
    mHeap[1]      = (INT16) Index3;\r
    DownHeap (1);\r
    mLeft[Index3]   = (UINT16) Index;\r
    mRight[Index3]  = (UINT16) Index2;\r
  } while (mHeapSize > 1);\r
\r
  mSortPtr = CodeParm;\r
  MakeLen (Index3);\r
  MakeCode (NParm, LenParm, CodeParm);\r
\r
  //\r
  // return root\r
  //\r
  return Index3;\r
}\r
\r
EFI_STATUS\r
GetFileContents (\r
  IN char    *InputFileName,\r
  OUT UINT8   *FileBuffer,\r
  OUT UINT32  *BufferLength\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Get the contents of file specified in InputFileName\r
  into FileBuffer.\r
\r
Arguments:\r
\r
  InputFileName  - Name of the input file.\r
\r
  FileBuffer     - Output buffer to contain data\r
\r
  BufferLength   - Actual length of the data\r
\r
Returns:\r
\r
  EFI_SUCCESS on successful return\r
  EFI_ABORTED if unable to open input file.\r
\r
--*/\r
{\r
  UINTN   Size;\r
  UINTN   FileSize;\r
  FILE    *InputFile;\r
\r
  Size = 0;\r
  //\r
  // Copy the file contents to the output buffer.\r
  //\r
  InputFile = fopen (LongFilePath (InputFileName), "rb");\r
    if (InputFile == NULL) {\r
      Error (NULL, 0, 0001, "Error opening file: %s", InputFileName);\r
      return EFI_ABORTED;\r
    }\r
\r
  fseek (InputFile, 0, SEEK_END);\r
  FileSize = ftell (InputFile);\r
  fseek (InputFile, 0, SEEK_SET);\r
    //\r
    // Now read the contents of the file into the buffer\r
    //\r
    if (FileSize > 0 && FileBuffer != NULL) {\r
      if (fread (FileBuffer, FileSize, 1, InputFile) != 1) {\r
        Error (NULL, 0, 0004, "Error reading contents of input file: %s", InputFileName);\r
        fclose (InputFile);\r
        return EFI_ABORTED;\r
      }\r
    }\r
\r
  fclose (InputFile);\r
  Size += (UINTN) FileSize;\r
  *BufferLength = Size;\r
\r
  if (FileBuffer != NULL) {\r
    return EFI_SUCCESS;\r
  } else {\r
    return EFI_BUFFER_TOO_SMALL;\r
  }\r
}\r
\r
VOID\r
Version (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Displays the standard utility information to SDTOUT\r
\r
Arguments:\r
\r
  None\r
\r
Returns:\r
\r
  None\r
\r
--*/\r
{\r
  fprintf (stdout, "%s Version %d.%d %s \n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION, __BUILD_VERSION);\r
}\r
\r
VOID\r
Usage (\r
  VOID\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Displays the utility usage syntax to STDOUT\r
\r
Arguments:\r
\r
  None\r
\r
Returns:\r
\r
  None\r
\r
--*/\r
{\r
  //\r
  // Summary usage\r
  //\r
  fprintf (stdout, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME);\r
\r
  //\r
  // Copyright declaration\r
  //\r
  fprintf (stdout, "Copyright (c) 2007 - 2018, Intel Corporation. All rights reserved.\n\n");\r
\r
  //\r
  // Details Option\r
  //\r
  fprintf (stdout, "Options:\n");\r
  fprintf (stdout, "  --uefi\n\\r
            Enable UefiCompress, use TianoCompress when without this option\n");\r
  fprintf (stdout, "  -o FileName, --output FileName\n\\r
            File will be created to store the output content.\n");\r
  fprintf (stdout, "  -v, --verbose\n\\r
           Turn on verbose output with informational messages.\n");\r
  fprintf (stdout, "  -q, --quiet\n\\r
           Disable all messages except key message and fatal error\n");\r
  fprintf (stdout, "  --debug [0-9]\n\\r
           Enable debug messages, at input debug level.\n");\r
  fprintf (stdout, "  --version\n\\r
           Show program's version number and exit.\n");\r
  fprintf (stdout, "  -h, --help\n\\r
           Show this help message and exit.\n");\r
}\r
\r
\r
int\r
main (\r
  int  argc,\r
  char *argv[]\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Main\r
\r
Arguments:\r
\r
  command line parameters\r
\r
Returns:\r
\r
  EFI_SUCCESS    Section header successfully generated and section concatenated.\r
  EFI_ABORTED    Could not generate the section\r
  EFI_OUT_OF_RESOURCES  No resource to complete the operation.\r
\r
--*/\r
{\r
  FILE       *OutputFile;\r
  char       *OutputFileName;\r
  char       *InputFileName;\r
  FILE       *InputFile;\r
  EFI_STATUS Status;\r
  UINT8      *FileBuffer;\r
  UINT8      *OutBuffer;\r
  UINT32     InputLength;\r
  UINT32     DstSize;\r
  SCRATCH_DATA      *Scratch;\r
  UINT8      *Src;\r
  UINT32     OrigSize;\r
  UINT32     CompSize;\r
\r
  SetUtilityName(UTILITY_NAME);\r
\r
  FileBuffer = NULL;\r
  Src = NULL;\r
  OutBuffer = NULL;\r
  Scratch   = NULL;\r
  OrigSize = 0;\r
  CompSize = 0;\r
  InputLength = 0;\r
  InputFileName = NULL;\r
  OutputFileName = NULL;\r
  InputFile = NULL;\r
  OutputFile = NULL;\r
  DstSize=0;\r
  DebugLevel = 0;\r
  DebugMode = FALSE;\r
\r
  //\r
  // Verify the correct number of arguments\r
  //\r
  if (argc == 1) {\r
    Error (NULL, 0, 1001, "Missing options", "No input options specified.");\r
    Usage();\r
    return 0;\r
  }\r
\r
  if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) {\r
    Usage();\r
    return 0;\r
  }\r
\r
  if ((strcmp(argv[1], "--version") == 0)) {\r
    Version();\r
    return 0;\r
  }\r
\r
  argc--;\r
  argv++;\r
  if (strcmp(argv[0],"-e") == 0) {\r
    //\r
    // encode the input file\r
    //\r
    ENCODE = TRUE;\r
    argc--;\r
    argv++;\r
  } else if (strcmp(argv[0], "-d") == 0) {\r
    //\r
    // decode the input file\r
    //\r
    DECODE = TRUE;\r
    argc--;\r
    argv++;\r
  } else {\r
    //\r
    // Error command line\r
    //\r
    Error (NULL, 0, 1003, "Invalid option value", "the options specified are not recognized.");\r
    Usage();\r
    return 1;\r
  }\r
\r
  while (argc > 0) {\r
    if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) {\r
      VerboseMode = TRUE;\r
      argc--;\r
      argv++;\r
      continue;\r
    }\r
\r
    if (stricmp(argv[0], "--uefi") == 0) {\r
      UEFIMODE = TRUE;\r
      argc--;\r
      argv++;\r
      continue;\r
    }\r
\r
    if (stricmp (argv[0], "--debug") == 0) {\r
      argc-=2;\r
      argv++;\r
      Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel);\r
      if (DebugLevel > 9) {\r
        Error (NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]);\r
        goto ERROR;\r
      }\r
      if (DebugLevel>=5 && DebugLevel <=9){\r
        DebugMode = TRUE;\r
      } else {\r
        DebugMode = FALSE;\r
      }\r
      argv++;\r
      continue;\r
    }\r
\r
    if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--quiet") == 0)) {\r
      QuietMode = TRUE;\r
      argc--;\r
      argv++;\r
      continue;\r
    }\r
\r
    if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) {\r
      if (argv[1] == NULL || argv[1][0] == '-') {\r
        Error (NULL, 0, 1003, "Invalid option value", "Output File name is missing for -o option");\r
        goto ERROR;\r
      }\r
      OutputFileName = argv[1];\r
      argc -=2;\r
      argv +=2;\r
      continue;\r
    }\r
\r
    if (argv[0][0]!='-') {\r
      InputFileName = argv[0];\r
      argc--;\r
      argv++;\r
      continue;\r
    }\r
\r
    Error (NULL, 0, 1000, "Unknown option", argv[0]);\r
    goto ERROR;\r
  }\r
\r
  if (InputFileName == NULL) {\r
    Error (NULL, 0, 1001, "Missing options", "No input files specified.");\r
    goto ERROR;\r
  }\r
\r
//\r
// All Parameters has been parsed, now set the message print level\r
//\r
  if (QuietMode) {\r
    SetPrintLevel(40);\r
  } else if (VerboseMode) {\r
    SetPrintLevel(15);\r
  } else if (DebugMode) {\r
    SetPrintLevel(DebugLevel);\r
  }\r
\r
  if (VerboseMode) {\r
    VerboseMsg("%s tool start.\n", UTILITY_NAME);\r
   }\r
  Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA));\r
  if (Scratch == NULL) {\r
    Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
    goto ERROR;\r
  }\r
\r
  InputFile = fopen (LongFilePath (InputFileName), "rb");\r
  if (InputFile == NULL) {\r
    Error (NULL, 0, 0001, "Error opening input file", InputFileName);\r
    goto ERROR;\r
  }\r
\r
  Status = GetFileContents(\r
            InputFileName,\r
            FileBuffer,\r
            &InputLength);\r
\r
  if (Status == EFI_BUFFER_TOO_SMALL) {\r
    FileBuffer = (UINT8 *) malloc (InputLength);\r
    if (FileBuffer == NULL) {\r
      Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
      goto ERROR;\r
    }\r
\r
    Status = GetFileContents (\r
              InputFileName,\r
              FileBuffer,\r
              &InputLength\r
              );\r
  }\r
\r
  if (EFI_ERROR(Status)) {\r
    Error (NULL, 0, 0004, "Error getting contents of file: %s", InputFileName);\r
    goto ERROR;\r
  }\r
\r
  if (OutputFileName == NULL) {\r
    OutputFileName = DEFAULT_OUTPUT_FILE;\r
  }\r
  OutputFile = fopen (LongFilePath (OutputFileName), "wb");\r
  if (OutputFile == NULL) {\r
    Error (NULL, 0, 0001, "Error opening output file for writing", OutputFileName);\r
    goto ERROR;\r
  }\r
\r
  if (ENCODE) {\r
  //\r
  // First call TianoCompress to get DstSize\r
  //\r
  if (DebugMode) {\r
    DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding", NULL);\r
  }\r
  if (UEFIMODE) {\r
    Status = EfiCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);\r
  } else {\r
    Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);\r
  }\r
\r
  if (Status == EFI_BUFFER_TOO_SMALL) {\r
    OutBuffer = (UINT8 *) malloc (DstSize);\r
    if (OutBuffer == NULL) {\r
      Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
      goto ERROR;\r
    }\r
  }\r
\r
  if (UEFIMODE) {\r
    Status = EfiCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);\r
  } else {\r
    Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);\r
  }\r
  if (Status != EFI_SUCCESS) {\r
    Error (NULL, 0, 0007, "Error compressing file", NULL);\r
    goto ERROR;\r
  }\r
\r
  if (OutBuffer == NULL) {\r
    Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
    goto ERROR;\r
  }\r
\r
  fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile);\r
  fclose(OutputFile);\r
  fclose(InputFile);\r
  free(Scratch);\r
  free(FileBuffer);\r
  free(OutBuffer);\r
\r
  if (DebugMode) {\r
    DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Successful!\n", NULL);\r
  }\r
  if (VerboseMode) {\r
    VerboseMsg("Encoding successful\n");\r
  }\r
  return 0;\r
  }\r
  else if (DECODE) {\r
  if (DebugMode) {\r
    DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding\n", NULL);\r
  }\r
\r
  if (UEFIMODE) {\r
    Status = Extract((VOID *)FileBuffer, InputLength, (VOID *)&OutBuffer, &DstSize, 1);\r
    if (Status != EFI_SUCCESS) {\r
      goto ERROR;\r
    }\r
    fwrite(OutBuffer, (size_t)(DstSize), 1, OutputFile);\r
  } else {\r
    if (InputLength < 8){\r
      Error (NULL, 0, 3000, "Invalid", "The input file %s is too small.", InputFileName);\r
      goto ERROR;\r
    }\r
    //\r
    // Get Compressed file original size\r
    //\r
    Src     = (UINT8 *)FileBuffer;\r
    OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);\r
    CompSize  = Src[0] + (Src[1] << 8) + (Src[2] <<16) + (Src[3] <<24);\r
\r
    //\r
    // Allocate OutputBuffer\r
    //\r
    if (InputLength < CompSize + 8 || (CompSize + 8) < 8) {\r
      Error (NULL, 0, 3000, "Invalid", "The input file %s data is invalid.", InputFileName);\r
      goto ERROR;\r
    }\r
    OutBuffer = (UINT8 *)malloc(OrigSize);\r
    if (OutBuffer == NULL) {\r
      Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");\r
      goto ERROR;\r
     }\r
\r
    Status = TDecompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2);\r
    if (Status != EFI_SUCCESS) {\r
      goto ERROR;\r
    }\r
    fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile);\r
  }\r
  fclose(OutputFile);\r
  fclose(InputFile);\r
  if (Scratch != NULL) {\r
    free(Scratch);\r
  }\r
  if (FileBuffer != NULL) {\r
    free(FileBuffer);\r
  }\r
  if (OutBuffer != NULL) {\r
    free(OutBuffer);\r
  }\r
\r
  if (DebugMode) {\r
    DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding successful!\n", NULL);\r
  }\r
\r
  if (VerboseMode) {\r
    VerboseMsg("Decoding successful\n");\r
  }\r
  return 0;\r
  }\r
\r
ERROR:\r
  if (DebugMode) {\r
    if (ENCODE) {\r
      DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Error\n", NULL);\r
    } else if (DECODE) {\r
      DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding Error\n", NULL);\r
    }\r
  }\r
  if (OutputFile != NULL) {\r
    fclose(OutputFile);\r
  }\r
  if (InputFile != NULL) {\r
    fclose (InputFile);\r
  }\r
  if (Scratch != NULL) {\r
    free(Scratch);\r
  }\r
  if (FileBuffer != NULL) {\r
    free(FileBuffer);\r
  }\r
  if (OutBuffer != NULL) {\r
    free(OutBuffer);\r
  }\r
\r
  if (VerboseMode) {\r
    VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ());\r
  }\r
  return GetUtilityStatus ();\r
}\r
\r
VOID\r
FillBuf (\r
  IN  SCRATCH_DATA  *Sd,\r
  IN  UINT16        NumOfBits\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.\r
\r
Arguments:\r
\r
  Sd        - The global scratch data\r
  NumOfBits  - The number of bits to shift and read.\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  Sd->mBitBuf = (UINT32) (((UINT64)Sd->mBitBuf) << NumOfBits);\r
\r
  while (NumOfBits > Sd->mBitCount) {\r
\r
    Sd->mBitBuf |= (UINT32) (((UINT64)Sd->mSubBitBuf) << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));\r
\r
    if (Sd->mCompSize > 0) {\r
      //\r
      // Get 1 byte into SubBitBuf\r
      //\r
      Sd->mCompSize--;\r
      Sd->mSubBitBuf  = 0;\r
      Sd->mSubBitBuf  = Sd->mSrcBase[Sd->mInBuf++];\r
      Sd->mBitCount   = 8;\r
\r
    } else {\r
      //\r
      // No more bits from the source, just pad zero bit.\r
      //\r
      Sd->mSubBitBuf  = 0;\r
      Sd->mBitCount   = 8;\r
\r
    }\r
  }\r
\r
  Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);\r
  Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;\r
}\r
\r
UINT32\r
GetBits (\r
  IN  SCRATCH_DATA  *Sd,\r
  IN  UINT16        NumOfBits\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent\r
  NumOfBits of bits from source. Returns NumOfBits of bits that are\r
  popped out.\r
\r
Arguments:\r
\r
  Sd            - The global scratch data.\r
  NumOfBits     - The number of bits to pop and read.\r
\r
Returns:\r
\r
  The bits that are popped out.\r
\r
--*/\r
{\r
  UINT32  OutBits;\r
\r
  OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));\r
\r
  FillBuf (Sd, NumOfBits);\r
\r
  return OutBits;\r
}\r
\r
UINT16\r
MakeTable (\r
  IN  SCRATCH_DATA  *Sd,\r
  IN  UINT16        NumOfChar,\r
  IN  UINT8         *BitLen,\r
  IN  UINT16        TableBits,\r
  OUT UINT16        *Table\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Creates Huffman Code mapping table according to code length array.\r
\r
Arguments:\r
\r
  Sd        - The global scratch data\r
  NumOfChar - Number of symbols in the symbol set\r
  BitLen    - Code length array\r
  TableBits - The width of the mapping table\r
  Table     - The table\r
\r
Returns:\r
\r
  0         - OK.\r
  BAD_TABLE - The table is corrupted.\r
\r
--*/\r
{\r
  UINT16  Count[17];\r
  UINT16  Weight[17];\r
  UINT16  Start[18];\r
  UINT16  *Pointer;\r
  UINT16  Index3;\r
  UINT16  Index;\r
  UINT16  Len;\r
  UINT16  Char;\r
  UINT16  JuBits;\r
  UINT16  Avail;\r
  UINT16  NextCode;\r
  UINT16  Mask;\r
  UINT16  WordOfStart;\r
  UINT16  WordOfCount;\r
  UINT16  MaxTableLength;\r
\r
  for (Index = 0; Index <= 16; Index++) {\r
    Count[Index] = 0;\r
  }\r
\r
  for (Index = 0; Index < NumOfChar; Index++) {\r
    if (BitLen[Index] > 16) {\r
      return (UINT16) BAD_TABLE;\r
    }\r
    Count[BitLen[Index]]++;\r
  }\r
\r
  Start[0] = 0;\r
  Start[1] = 0;\r
\r
  for (Index = 1; Index <= 16; Index++) {\r
    WordOfStart = Start[Index];\r
    WordOfCount = Count[Index];\r
    Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));\r
  }\r
\r
  if (Start[17] != 0) {\r
    //\r
    //(1U << 16)\r
    //\r
    return (UINT16) BAD_TABLE;\r
  }\r
\r
  JuBits = (UINT16) (16 - TableBits);\r
\r
  Weight[0] = 0;\r
  for (Index = 1; Index <= TableBits; Index++) {\r
    Start[Index] >>= JuBits;\r
    Weight[Index] = (UINT16) (1U << (TableBits - Index));\r
  }\r
\r
  while (Index <= 16) {\r
    Weight[Index] = (UINT16) (1U << (16 - Index));\r
    Index++;\r
  }\r
\r
  Index = (UINT16) (Start[TableBits + 1] >> JuBits);\r
\r
  if (Index != 0) {\r
    Index3 = (UINT16) (1U << TableBits);\r
    while (Index != Index3) {\r
      Table[Index++] = 0;\r
    }\r
  }\r
\r
  Avail = NumOfChar;\r
  Mask  = (UINT16) (1U << (15 - TableBits));\r
  MaxTableLength = (UINT16) (1U << TableBits);\r
\r
  for (Char = 0; Char < NumOfChar; Char++) {\r
\r
    Len = BitLen[Char];\r
    if (Len == 0 || Len >= 17) {\r
      continue;\r
    }\r
\r
    NextCode = (UINT16) (Start[Len] + Weight[Len]);\r
\r
    if (Len <= TableBits) {\r
\r
      if (Start[Len] >= NextCode || NextCode > MaxTableLength){\r
        return (UINT16) BAD_TABLE;\r
      }\r
\r
      for (Index = Start[Len]; Index < NextCode; Index++) {\r
        Table[Index] = Char;\r
      }\r
\r
    } else {\r
\r
      Index3  = Start[Len];\r
      Pointer = &Table[Index3 >> JuBits];\r
      Index   = (UINT16) (Len - TableBits);\r
\r
      while (Index != 0) {\r
        if (*Pointer == 0) {\r
          Sd->mRight[Avail]                     = Sd->mLeft[Avail] = 0;\r
          *Pointer = Avail++;\r
        }\r
\r
        if (Index3 & Mask) {\r
          Pointer = &Sd->mRight[*Pointer];\r
        } else {\r
          Pointer = &Sd->mLeft[*Pointer];\r
        }\r
\r
        Index3 <<= 1;\r
        Index--;\r
      }\r
\r
      *Pointer = Char;\r
\r
    }\r
\r
    Start[Len] = NextCode;\r
  }\r
  //\r
  // Succeeds\r
  //\r
  return 0;\r
}\r
\r
UINT32\r
DecodeP (\r
  IN  SCRATCH_DATA  *Sd\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Decodes a position value.\r
\r
Arguments:\r
\r
  Sd      - the global scratch data\r
\r
Returns:\r
\r
  The position value decoded.\r
\r
--*/\r
{\r
  UINT16  Val;\r
  UINT32  Mask;\r
  UINT32  Pos;\r
\r
  Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
\r
  if (Val >= MAXNP) {\r
    Mask = 1U << (BITBUFSIZ - 1 - 8);\r
\r
    do {\r
\r
      if (Sd->mBitBuf & Mask) {\r
        Val = Sd->mRight[Val];\r
      } else {\r
        Val = Sd->mLeft[Val];\r
      }\r
\r
      Mask >>= 1;\r
    } while (Val >= MAXNP);\r
  }\r
  //\r
  // Advance what we have read\r
  //\r
  FillBuf (Sd, Sd->mPTLen[Val]);\r
\r
  Pos = Val;\r
  if (Val > 1) {\r
    Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));\r
  }\r
\r
  return Pos;\r
}\r
\r
UINT16\r
ReadPTLen (\r
  IN  SCRATCH_DATA  *Sd,\r
  IN  UINT16        nn,\r
  IN  UINT16        nbit,\r
  IN  UINT16        Special\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Reads code lengths for the Extra Set or the Position Set\r
\r
Arguments:\r
\r
  Sd        - The global scratch data\r
  nn        - Number of symbols\r
  nbit      - Number of bits needed to represent nn\r
  Special   - The special symbol that needs to be taken care of\r
\r
Returns:\r
\r
  0         - OK.\r
  BAD_TABLE - Table is corrupted.\r
\r
--*/\r
{\r
  UINT16  Number;\r
  UINT16  CharC;\r
  volatile UINT16  Index;\r
  UINT32  Mask;\r
\r
  assert (nn <= NPT);\r
\r
  Number = (UINT16) GetBits (Sd, nbit);\r
\r
  if (Number == 0) {\r
    CharC = (UINT16) GetBits (Sd, nbit);\r
\r
    for (Index = 0; Index < 256; Index++) {\r
      Sd->mPTTable[Index] = CharC;\r
    }\r
\r
    for (Index = 0; Index < nn; Index++) {\r
      Sd->mPTLen[Index] = 0;\r
    }\r
\r
    return 0;\r
  }\r
\r
  Index = 0;\r
\r
  while (Index < Number) {\r
\r
    CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));\r
\r
    if (CharC == 7) {\r
      Mask = 1U << (BITBUFSIZ - 1 - 3);\r
      while (Mask & Sd->mBitBuf) {\r
        Mask >>= 1;\r
        CharC += 1;\r
      }\r
    }\r
\r
    FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));\r
\r
    Sd->mPTLen[Index++] = (UINT8) CharC;\r
\r
    if (Index == Special) {\r
      CharC = (UINT16) GetBits (Sd, 2);\r
      while ((INT16) (--CharC) >= 0) {\r
        Sd->mPTLen[Index++] = 0;\r
      }\r
    }\r
  }\r
\r
  while (Index < nn) {\r
    Sd->mPTLen[Index++] = 0;\r
  }\r
\r
  return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);\r
}\r
\r
VOID\r
ReadCLen (\r
  SCRATCH_DATA  *Sd\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Reads code lengths for Char&Len Set.\r
\r
Arguments:\r
\r
  Sd    - the global scratch data\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  UINT16  Number;\r
  UINT16  CharC;\r
  volatile UINT16  Index;\r
  UINT32  Mask;\r
\r
  Number = (UINT16) GetBits (Sd, CBIT);\r
\r
  if (Number == 0) {\r
    CharC = (UINT16) GetBits (Sd, CBIT);\r
\r
    for (Index = 0; Index < NC; Index++) {\r
      Sd->mCLen[Index] = 0;\r
    }\r
\r
    for (Index = 0; Index < 4096; Index++) {\r
      Sd->mCTable[Index] = CharC;\r
    }\r
\r
    return ;\r
  }\r
\r
  Index = 0;\r
  while (Index < Number) {\r
\r
    CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
    if (CharC >= NT) {\r
      Mask = 1U << (BITBUFSIZ - 1 - 8);\r
\r
      do {\r
\r
        if (Mask & Sd->mBitBuf) {\r
          CharC = Sd->mRight[CharC];\r
        } else {\r
          CharC = Sd->mLeft[CharC];\r
        }\r
\r
        Mask >>= 1;\r
\r
      } while (CharC >= NT);\r
    }\r
    //\r
    // Advance what we have read\r
    //\r
    FillBuf (Sd, Sd->mPTLen[CharC]);\r
\r
    if (CharC <= 2) {\r
\r
      if (CharC == 0) {\r
        CharC = 1;\r
      } else if (CharC == 1) {\r
        CharC = (UINT16) (GetBits (Sd, 4) + 3);\r
      } else if (CharC == 2) {\r
        CharC = (UINT16) (GetBits (Sd, CBIT) + 20);\r
      }\r
\r
      while ((INT16) (--CharC) >= 0) {\r
        Sd->mCLen[Index++] = 0;\r
      }\r
\r
    } else {\r
\r
      Sd->mCLen[Index++] = (UINT8) (CharC - 2);\r
\r
    }\r
  }\r
\r
  while (Index < NC) {\r
    Sd->mCLen[Index++] = 0;\r
  }\r
\r
  MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);\r
\r
  return ;\r
}\r
\r
UINT16\r
DecodeC (\r
  SCRATCH_DATA  *Sd\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Decode a character/length value.\r
\r
Arguments:\r
\r
  Sd    - The global scratch data.\r
\r
Returns:\r
\r
  The value decoded.\r
\r
--*/\r
{\r
  UINT16  Index2;\r
  UINT32  Mask;\r
\r
  if (Sd->mBlockSize == 0) {\r
    //\r
    // Starting a new block\r
    //\r
    Sd->mBlockSize    = (UINT16) GetBits (Sd, 16);\r
    Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);\r
    if (Sd->mBadTableFlag != 0) {\r
      return 0;\r
    }\r
\r
    ReadCLen (Sd);\r
\r
    Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));\r
    if (Sd->mBadTableFlag != 0) {\r
      return 0;\r
    }\r
  }\r
\r
  Sd->mBlockSize--;\r
  Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];\r
\r
  if (Index2 >= NC) {\r
    Mask = 1U << (BITBUFSIZ - 1 - 12);\r
\r
    do {\r
      if (Sd->mBitBuf & Mask) {\r
        Index2 = Sd->mRight[Index2];\r
      } else {\r
        Index2 = Sd->mLeft[Index2];\r
      }\r
\r
      Mask >>= 1;\r
    } while (Index2 >= NC);\r
  }\r
  //\r
  // Advance what we have read\r
  //\r
  FillBuf (Sd, Sd->mCLen[Index2]);\r
\r
  return Index2;\r
}\r
\r
VOID\r
Decode (\r
  SCRATCH_DATA  *Sd\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Decode the source data and put the resulting data into the destination buffer.\r
\r
Arguments:\r
\r
  Sd            - The global scratch data\r
\r
Returns: (VOID)\r
\r
 --*/\r
{\r
  UINT16  BytesRemain;\r
  UINT32  DataIdx;\r
  UINT16  CharC;\r
\r
  BytesRemain = (UINT16) (-1);\r
\r
  DataIdx     = 0;\r
\r
  for (;;) {\r
    CharC = DecodeC (Sd);\r
    if (Sd->mBadTableFlag != 0) {\r
      goto Done ;\r
    }\r
\r
    if (CharC < 256) {\r
      //\r
      // Process an Original character\r
      //\r
      if (Sd->mOutBuf >= Sd->mOrigSize) {\r
        goto Done ;\r
      } else {\r
        Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;\r
      }\r
\r
    } else {\r
      //\r
      // Process a Pointer\r
      //\r
      CharC       = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));\r
\r
      BytesRemain = CharC;\r
\r
      DataIdx     = Sd->mOutBuf - DecodeP (Sd) - 1;\r
\r
      BytesRemain--;\r
\r
      while ((INT16) (BytesRemain) >= 0) {\r
        if (Sd->mOutBuf >= Sd->mOrigSize) {\r
          goto Done ;\r
        }\r
        if (DataIdx >= Sd->mOrigSize) {\r
          Sd->mBadTableFlag = (UINT16) BAD_TABLE;\r
          goto Done ;\r
        }\r
        Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];\r
\r
        BytesRemain--;\r
      }\r
      //\r
      // Once mOutBuf is fully filled, directly return\r
      //\r
      if (Sd->mOutBuf >= Sd->mOrigSize) {\r
        goto Done ;\r
      }\r
    }\r
  }\r
\r
Done:\r
  return ;\r
}\r
\r
RETURN_STATUS\r
EFIAPI\r
TDecompress (\r
  IN VOID  *Source,\r
  IN OUT VOID    *Destination,\r
  IN OUT VOID    *Scratch,\r
  IN UINT32      Version\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  The internal implementation of Decompress().\r
\r
Arguments:\r
\r
  Source          - The source buffer containing the compressed data.\r
  Destination     - The destination buffer to store the decompressed data\r
  Scratch         - The buffer used internally by the decompress routine. This  buffer is needed to store intermediate data.\r
  Version         - 1 for EFI1.1 Decompress algorithm, 2 for Tiano Decompress algorithm\r
\r
Returns:\r
\r
  RETURN_SUCCESS           - Decompression is successful\r
  RETURN_INVALID_PARAMETER - The source data is corrupted\r
\r
--*/\r
{\r
  volatile UINT32  Index;\r
  UINT32           CompSize;\r
  UINT32           OrigSize;\r
  SCRATCH_DATA     *Sd;\r
  CONST UINT8      *Src;\r
  UINT8            *Dst;\r
\r
  //\r
  // Verify input is not NULL\r
  //\r
  assert(Source);\r
//  assert(Destination);\r
  assert(Scratch);\r
\r
  Src     = (UINT8 *)Source;\r
  Dst     = (UINT8 *)Destination;\r
\r
  Sd      = (SCRATCH_DATA *) Scratch;\r
  CompSize  = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);\r
  OrigSize  = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);\r
\r
  //\r
  // If compressed file size is 0, return\r
  //\r
  if (OrigSize == 0) {\r
    return RETURN_SUCCESS;\r
  }\r
\r
  Src = Src + 8;\r
\r
  for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {\r
    ((UINT8 *) Sd)[Index] = 0;\r
  }\r
  //\r
  // The length of the field 'Position Set Code Length Array Size' in Block Header.\r
  // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4\r
  // For Tiano de/compression algorithm(Version 2), mPBit = 5\r
  //\r
  switch (Version) {\r
    case 1 :\r
      Sd->mPBit = 4;\r
      break;\r
    case 2 :\r
      Sd->mPBit = 5;\r
      break;\r
    default:\r
      assert(FALSE);\r
  }\r
  Sd->mSrcBase  = (UINT8 *)Src;\r
  Sd->mDstBase  = Dst;\r
  Sd->mCompSize = CompSize;\r
  Sd->mOrigSize = OrigSize;\r
\r
  //\r
  // Fill the first BITBUFSIZ bits\r
  //\r
  FillBuf (Sd, BITBUFSIZ);\r
\r
  //\r
  // Decompress it\r
  //\r
\r
  Decode (Sd);\r
\r
  if (Sd->mBadTableFlag != 0) {\r
    //\r
    // Something wrong with the source\r
    //\r
    return RETURN_INVALID_PARAMETER;\r
  }\r
\r
  return RETURN_SUCCESS;\r
}\r
\r
\r