BaseTools: Replace BSD License with BSD+Patent License

[mirror_edk2.git] / BaseTools / Source / C / Common / 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. This sequence is further divided into Blocks\r
and Huffman codings are applied to each Block.\r
\r
Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>\r
SPDX-License-Identifier: BSD-2-Clause-Patent\r
\r
**/\r
\r
#include "Compress.h"\r
\r
//\r
// Macro Definitions\r
//\r
#undef  UINT8_MAX\r
typedef INT32 NODE;\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
// Function Prototypes\r
//\r
\r
STATIC\r
VOID\r
PutDword(\r
  IN UINT32 Data\r
  );\r
\r
STATIC\r
EFI_STATUS\r
AllocateMemory (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
FreeMemory (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
InitSlide (\r
  VOID\r
  );\r
\r
STATIC\r
NODE\r
Child (\r
  IN NODE   NodeQ,\r
  IN UINT8  CharC\r
  );\r
\r
STATIC\r
VOID\r
MakeChild (\r
  IN NODE  NodeQ,\r
  IN UINT8 CharC,\r
  IN NODE  NodeR\r
  );\r
\r
STATIC\r
VOID\r
Split (\r
  IN NODE Old\r
  );\r
\r
STATIC\r
VOID\r
InsertNode (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
DeleteNode (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
GetNextMatch (\r
  VOID\r
  );\r
\r
STATIC\r
EFI_STATUS\r
Encode (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
CountTFreq (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
WritePTLen (\r
  IN INT32 Number,\r
  IN INT32 nbit,\r
  IN INT32 Special\r
  );\r
\r
STATIC\r
VOID\r
WriteCLen (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
EncodeC (\r
  IN INT32 Value\r
  );\r
\r
STATIC\r
VOID\r
EncodeP (\r
  IN UINT32 Value\r
  );\r
\r
STATIC\r
VOID\r
SendBlock (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
Output (\r
  IN UINT32 c,\r
  IN UINT32 p\r
  );\r
\r
STATIC\r
VOID\r
HufEncodeStart (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
HufEncodeEnd (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
MakeCrcTable (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
PutBits (\r
  IN INT32  Number,\r
  IN UINT32 Value\r
  );\r
\r
STATIC\r
INT32\r
FreadCrc (\r
  OUT UINT8 *Pointer,\r
  IN  INT32 Number\r
  );\r
\r
STATIC\r
VOID\r
InitPutBits (\r
  VOID\r
  );\r
\r
STATIC\r
VOID\r
CountLen (\r
  IN INT32 Index\r
  );\r
\r
STATIC\r
VOID\r
MakeLen (\r
  IN INT32 Root\r
  );\r
\r
STATIC\r
VOID\r
DownHeap (\r
  IN INT32 Index\r
  );\r
\r
STATIC\r
VOID\r
MakeCode (\r
  IN  INT32       Number,\r
  IN  UINT8 Len[  ],\r
  OUT UINT16 Code[]\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
//  Global Variables\r
//\r
STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;\r
\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
//\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
  DstSize     - On input, the size of DstBuffer; On output,\r
                the size of the actual compressed data.\r
  Version     - The version of de/compression algorithm.\r
                Version 1 for UEFI 2.0 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
  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
  // Null terminate the compressed data\r
  //\r
  if (mDst < mDstUpperLimit) {\r
    *mDst++ = 0;\r
  }\r
  //\r
  // Fill in compressed size and original size\r
  //\r
  mDst = DstBuffer;\r
  PutDword (mCompSize + 1);\r
  PutDword (mOrigSize);\r
\r
  //\r
  // Return\r
  //\r
  if (mCompSize + 1 + 8 > *DstSize) {\r
    *DstSize = mCompSize + 1 + 8;\r
    return EFI_BUFFER_TOO_SMALL;\r
  } else {\r
    *DstSize = mCompSize + 1 + 8;\r
    return EFI_SUCCESS;\r
  }\r
\r
}\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
    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
    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
  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
    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
  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