[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
This program and the accompanying materials\r
are licensed and made available under the terms and conditions of the BSD License\r
which accompanies this distribution.  The full text of the license may be found at\r
http://opensource.org/licenses/bsd-license.php\r
\r
THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\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
Argements:\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. 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
    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 ouput 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
      for (Index = Start[Len]; Index < NextCode; Index++) {\r
        if (Index >= MaxTableLength) {\r
          return (UINT16) BAD_TABLE;\r
        }\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
  }\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 algoruthm, 2 for Tiano Decompress algorithm\r
\r
Returns:\r
\r
  RETURN_SUCCESS           - Decompression is successfull\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