BaseTools: Replace BSD License with BSD+Patent License

[mirror_edk2.git] / BaseTools / Source / C / Common / EfiCompress.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
//\r
// Macro Definitions\r
//\r
\r
#undef UINT8_MAX\r
typedef INT16             NODE;\r
#define UINT8_MAX         0xff\r
#define UINT8_BIT         8\r
#define THRESHOLD         3\r
#define INIT_CRC          0\r
#define WNDBIT            13\r
#define WNDSIZ            (1U << WNDBIT)\r
#define MAXMATCH          256\r
#define PERC_FLAG         0x8000U\r
#define CODE_BIT          16\r
#define NIL               0\r
#define MAX_HASH_VAL      (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)\r
#define HASH(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
\r
#define NC                (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)\r
#define CBIT              9\r
#define NP                (WNDBIT + 1)\r
#define PBIT              4\r
#define NT                (CODE_BIT + 3)\r
#define TBIT              5\r
#if NT > NP\r
  #define                 NPT NT\r
#else\r
  #define                 NPT NP\r
#endif\r
\r
//\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
  );\r
\r
STATIC\r
VOID\r
FreeMemory (\r
  );\r
\r
STATIC\r
VOID\r
InitSlide (\r
  );\r
\r
STATIC\r
NODE\r
Child (\r
  IN NODE q,\r
  IN UINT8 c\r
  );\r
\r
STATIC\r
VOID\r
MakeChild (\r
  IN NODE q,\r
  IN UINT8 c,\r
  IN NODE r\r
  );\r
\r
STATIC\r
VOID\r
Split (\r
  IN NODE Old\r
  );\r
\r
STATIC\r
VOID\r
InsertNode (\r
  );\r
\r
STATIC\r
VOID\r
DeleteNode (\r
  );\r
\r
STATIC\r
VOID\r
GetNextMatch (\r
  );\r
\r
STATIC\r
EFI_STATUS\r
Encode (\r
  );\r
\r
STATIC\r
VOID\r
CountTFreq (\r
  );\r
\r
STATIC\r
VOID\r
WritePTLen (\r
  IN INT32 n,\r
  IN INT32 nbit,\r
  IN INT32 Special\r
  );\r
\r
STATIC\r
VOID\r
WriteCLen (\r
  );\r
\r
STATIC\r
VOID\r
EncodeC (\r
  IN INT32 c\r
  );\r
\r
STATIC\r
VOID\r
EncodeP (\r
  IN UINT32 p\r
  );\r
\r
STATIC\r
VOID\r
SendBlock (\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
  );\r
\r
STATIC\r
VOID\r
HufEncodeEnd (\r
  );\r
\r
STATIC\r
VOID\r
MakeCrcTable (\r
  );\r
\r
STATIC\r
VOID\r
PutBits (\r
  IN INT32 n,\r
  IN UINT32 x\r
  );\r
\r
STATIC\r
INT32\r
FreadCrc (\r
  OUT UINT8 *p,\r
  IN  INT32 n\r
  );\r
\r
STATIC\r
VOID\r
InitPutBits (\r
  );\r
\r
STATIC\r
VOID\r
CountLen (\r
  IN INT32 i\r
  );\r
\r
STATIC\r
VOID\r
MakeLen (\r
  IN INT32 Root\r
  );\r
\r
STATIC\r
VOID\r
DownHeap (\r
  IN INT32 i\r
  );\r
\r
STATIC\r
VOID\r
MakeCode (\r
  IN  INT32 n,\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
//\r
//  Global Variables\r
//\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],\r
              mCrcTable[UINT8_MAX + 1], mCFreq[2 * NC - 1],mCCode[NC],\r
              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
//\r
// functions\r
//\r
\r
EFI_STATUS\r
EfiCompress (\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 main compression routine.\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
\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
\r
--*/\r
{\r
  EFI_STATUS Status = EFI_SUCCESS;\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
\r
  Status = Encode();\r
  if (EFI_ERROR (Status)) {\r
    return EFI_OUT_OF_RESOURCES;\r
  }\r
\r
  //\r
  // Null terminate the compressed data\r
  //\r
  if (mDst < mDstUpperLimit) {\r
    *mDst++ = 0;\r
  }\r
\r
  //\r
  // Fill in compressed size and original size\r
  //\r
  mDst = DstBuffer;\r
  PutDword(mCompSize+1);\r
  PutDword(mOrigSize);\r
\r
  //\r
  // Return\r
  //\r
\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
/*++\r
\r
Routine Description:\r
\r
  Allocate memory spaces for data structures used in compression process\r
\r
Arguments: (VOID)\r
\r
Returns:\r
\r
  EFI_SUCCESS           - Memory is allocated successfully\r
  EFI_OUT_OF_RESOURCES  - Allocation fails\r
\r
--*/\r
{\r
  UINT32      i;\r
\r
  mText       = malloc (WNDSIZ * 2 + MAXMATCH);\r
  if (mText == NULL) {\r
    return EFI_OUT_OF_RESOURCES;\r
  }\r
  for (i = 0 ; i < WNDSIZ * 2 + MAXMATCH; i ++) {\r
    mText[i] = 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 = 16 * 1024U;\r
  while ((mBuf = malloc(mBufSiz)) == NULL) {\r
    mBufSiz = (mBufSiz / 10U) * 9U;\r
    if (mBufSiz < 4 * 1024U) {\r
      return EFI_OUT_OF_RESOURCES;\r
    }\r
  }\r
  mBuf[0] = 0;\r
\r
  return EFI_SUCCESS;\r
}\r
\r
VOID\r
FreeMemory ()\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) {\r
    free (mText);\r
  }\r
\r
  if (mLevel) {\r
    free (mLevel);\r
  }\r
\r
  if (mChildCount) {\r
    free (mChildCount);\r
  }\r
\r
  if (mPosition) {\r
    free (mPosition);\r
  }\r
\r
  if (mParent) {\r
    free (mParent);\r
  }\r
\r
  if (mPrev) {\r
    free (mPrev);\r
  }\r
\r
  if (mNext) {\r
    free (mNext);\r
  }\r
\r
  if (mBuf) {\r
    free (mBuf);\r
  }\r
\r
  return;\r
}\r
\r
\r
STATIC\r
VOID\r
InitSlide ()\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 i;\r
\r
  for (i = WNDSIZ; i <= WNDSIZ + UINT8_MAX; i++) {\r
    mLevel[i] = 1;\r
    mPosition[i] = NIL;  /* sentinel */\r
  }\r
  for (i = WNDSIZ; i < WNDSIZ * 2; i++) {\r
    mParent[i] = NIL;\r
  }\r
  mAvail = 1;\r
  for (i = 1; i < WNDSIZ - 1; i++) {\r
    mNext[i] = (NODE)(i + 1);\r
  }\r
\r
  mNext[WNDSIZ - 1] = NIL;\r
  for (i = WNDSIZ * 2; i <= MAX_HASH_VAL; i++) {\r
    mNext[i] = NIL;\r
  }\r
}\r
\r
\r
STATIC\r
NODE\r
Child (\r
  IN NODE q,\r
  IN UINT8 c\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Find child node given the parent node and the edge character\r
\r
Arguments:\r
\r
  q       - the parent node\r
  c       - the edge character\r
\r
Returns:\r
\r
  The child node (NIL if not found)\r
\r
--*/\r
{\r
  NODE r;\r
\r
  r = mNext[HASH(q, c)];\r
  mParent[NIL] = q;  /* sentinel */\r
  while (mParent[r] != q) {\r
    r = mNext[r];\r
  }\r
\r
  return r;\r
}\r
\r
STATIC\r
VOID\r
MakeChild (\r
  IN NODE q,\r
  IN UINT8 c,\r
  IN NODE r\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Create a new child for a given parent node.\r
\r
Arguments:\r
\r
  q       - the parent node\r
  c       - the edge character\r
  r       - the child node\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  NODE h, t;\r
\r
  h = (NODE)HASH(q, c);\r
  t = mNext[h];\r
  mNext[h] = r;\r
  mNext[r] = t;\r
  mPrev[t] = r;\r
  mPrev[r] = h;\r
  mParent[r] = q;\r
  mChildCount[q]++;\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, t;\r
\r
  New = mAvail;\r
  mAvail = mNext[New];\r
  mChildCount[New] = 0;\r
  t = mPrev[Old];\r
  mPrev[New] = t;\r
  mNext[t] = New;\r
  t = mNext[Old];\r
  mNext[New] = t;\r
  mPrev[t] = 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
/*++\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 q, r, j, t;\r
  UINT8 c, *t1, *t2;\r
\r
  if (mMatchLen >= 4) {\r
\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
\r
    mMatchLen--;\r
    r = (INT16)((mMatchPos + 1) | WNDSIZ);\r
    while ((q = mParent[r]) == NIL) {\r
      r = mNext[r];\r
    }\r
    while (mLevel[q] >= mMatchLen) {\r
      r = q;  q = mParent[q];\r
    }\r
    t = q;\r
    while (mPosition[t] < 0) {\r
      mPosition[t] = mPos;\r
      t = mParent[t];\r
    }\r
    if (t < WNDSIZ) {\r
      mPosition[t] = (NODE)(mPos | PERC_FLAG);\r
    }\r
  } else {\r
\r
    //\r
    // Locate the target tree\r
    //\r
\r
    q = (INT16)(mText[mPos] + WNDSIZ);\r
    c = mText[mPos + 1];\r
    if ((r = Child(q, c)) == NIL) {\r
      MakeChild(q, c, mPos);\r
      mMatchLen = 1;\r
      return;\r
    }\r
    mMatchLen = 2;\r
  }\r
\r
  //\r
  // Traverse down the tree to find a match.\r
  // Update Position value along the route.\r
  // Node split or creation is involved.\r
  //\r
\r
  for ( ; ; ) {\r
    if (r >= WNDSIZ) {\r
      j = MAXMATCH;\r
      mMatchPos = r;\r
    } else {\r
      j = mLevel[r];\r
      mMatchPos = (NODE)(mPosition[r] & ~PERC_FLAG);\r
    }\r
    if (mMatchPos >= mPos) {\r
      mMatchPos -= WNDSIZ;\r
    }\r
    t1 = &mText[mPos + mMatchLen];\r
    t2 = &mText[mMatchPos + mMatchLen];\r
    while (mMatchLen < j) {\r
      if (*t1 != *t2) {\r
        Split(r);\r
        return;\r
      }\r
      mMatchLen++;\r
      t1++;\r
      t2++;\r
    }\r
    if (mMatchLen >= MAXMATCH) {\r
      break;\r
    }\r
    mPosition[r] = mPos;\r
    q = r;\r
    if ((r = Child(q, *t1)) == NIL) {\r
      MakeChild(q, *t1, mPos);\r
      return;\r
    }\r
    mMatchLen++;\r
  }\r
  t = mPrev[r];\r
  mPrev[mPos] = t;\r
  mNext[t] = mPos;\r
  t = mNext[r];\r
  mNext[mPos] = t;\r
  mPrev[t] = mPos;\r
  mParent[mPos] = q;\r
  mParent[r] = NIL;\r
\r
  //\r
  // Special usage of 'next'\r
  //\r
  mNext[r] = mPos;\r
\r
}\r
\r
STATIC\r
VOID\r
DeleteNode ()\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 q, r, s, t, u;\r
\r
  if (mParent[mPos] == NIL) {\r
    return;\r
  }\r
\r
  r = mPrev[mPos];\r
  s = mNext[mPos];\r
  mNext[r] = s;\r
  mPrev[s] = r;\r
  r = mParent[mPos];\r
  mParent[mPos] = NIL;\r
  if (r >= WNDSIZ || --mChildCount[r] > 1) {\r
    return;\r
  }\r
  t = (NODE)(mPosition[r] & ~PERC_FLAG);\r
  if (t >= mPos) {\r
    t -= WNDSIZ;\r
  }\r
  s = t;\r
  q = mParent[r];\r
  while ((u = mPosition[q]) & PERC_FLAG) {\r
    u &= ~PERC_FLAG;\r
    if (u >= mPos) {\r
      u -= WNDSIZ;\r
    }\r
    if (u > s) {\r
      s = u;\r
    }\r
    mPosition[q] = (INT16)(s | WNDSIZ);\r
    q = mParent[q];\r
  }\r
  if (q < WNDSIZ) {\r
    if (u >= mPos) {\r
      u -= WNDSIZ;\r
    }\r
    if (u > s) {\r
      s = u;\r
    }\r
    mPosition[q] = (INT16)(s | WNDSIZ | PERC_FLAG);\r
  }\r
  s = Child(r, mText[t + mLevel[r]]);\r
  t = mPrev[s];\r
  u = mNext[s];\r
  mNext[t] = u;\r
  mPrev[u] = t;\r
  t = mPrev[r];\r
  mNext[t] = s;\r
  mPrev[s] = t;\r
  t = mNext[r];\r
  mPrev[t] = s;\r
  mNext[s] = t;\r
  mParent[s] = mParent[r];\r
  mParent[r] = NIL;\r
  mNext[r] = mAvail;\r
  mAvail = r;\r
}\r
\r
STATIC\r
VOID\r
GetNextMatch ()\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 n;\r
\r
  mRemainder--;\r
  if (++mPos == WNDSIZ * 2) {\r
    memmove(&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);\r
    n = FreadCrc(&mText[WNDSIZ + MAXMATCH], WNDSIZ);\r
    mRemainder += n;\r
    mPos = WNDSIZ;\r
  }\r
  DeleteNode();\r
  InsertNode();\r
}\r
\r
STATIC\r
EFI_STATUS\r
Encode ()\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
  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
      //\r
      // Not enough benefits are gained by outputting a pointer,\r
      // so just output the original character\r
      //\r
\r
      Output(mText[mPos - 1], 0);\r
    } else {\r
\r
      //\r
      // Outputting a pointer is beneficial enough, do it.\r
      //\r
\r
      Output(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),\r
             (mPos - LastMatchPos - 2) & (WNDSIZ - 1));\r
      while (--LastMatchLen > 0) {\r
        GetNextMatch();\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
/*++\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 i, k, n, Count;\r
\r
  for (i = 0; i < NT; i++) {\r
    mTFreq[i] = 0;\r
  }\r
  n = NC;\r
  while (n > 0 && mCLen[n - 1] == 0) {\r
    n--;\r
  }\r
  i = 0;\r
  while (i < n) {\r
    k = mCLen[i++];\r
    if (k == 0) {\r
      Count = 1;\r
      while (i < n && mCLen[i] == 0) {\r
        i++;\r
        Count++;\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[k + 2]++;\r
    }\r
  }\r
}\r
\r
STATIC\r
VOID\r
WritePTLen (\r
  IN INT32 n,\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
  n       - 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 i, k;\r
\r
  while (n > 0 && mPTLen[n - 1] == 0) {\r
    n--;\r
  }\r
  PutBits(nbit, n);\r
  i = 0;\r
  while (i < n) {\r
    k = mPTLen[i++];\r
    if (k <= 6) {\r
      PutBits(3, k);\r
    } else {\r
      PutBits(k - 3, (1U << (k - 3)) - 2);\r
    }\r
    if (i == Special) {\r
      while (i < 6 && mPTLen[i] == 0) {\r
        i++;\r
      }\r
      PutBits(2, (i - 3) & 3);\r
    }\r
  }\r
}\r
\r
STATIC\r
VOID\r
WriteCLen ()\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 i, k, n, Count;\r
\r
  n = NC;\r
  while (n > 0 && mCLen[n - 1] == 0) {\r
    n--;\r
  }\r
  PutBits(CBIT, n);\r
  i = 0;\r
  while (i < n) {\r
    k = mCLen[i++];\r
    if (k == 0) {\r
      Count = 1;\r
      while (i < n && mCLen[i] == 0) {\r
        i++;\r
        Count++;\r
      }\r
      if (Count <= 2) {\r
        for (k = 0; k < Count; k++) {\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[k + 2], mPTCode[k + 2]);\r
    }\r
  }\r
}\r
\r
STATIC\r
VOID\r
EncodeC (\r
  IN INT32 c\r
  )\r
{\r
  PutBits(mCLen[c], mCCode[c]);\r
}\r
\r
STATIC\r
VOID\r
EncodeP (\r
  IN UINT32 p\r
  )\r
{\r
  UINT32 c, q;\r
\r
  c = 0;\r
  q = p;\r
  while (q) {\r
    q >>= 1;\r
    c++;\r
  }\r
  PutBits(mPTLen[c], mPTCode[c]);\r
  if (c > 1) {\r
    PutBits(c - 1, p & (0xFFFFU >> (17 - c)));\r
  }\r
}\r
\r
STATIC\r
VOID\r
SendBlock ()\r
/*++\r
\r
Routine Description:\r
\r
  Huffman code the block and output it.\r
\r
Argument: (VOID)\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  UINT32 i, k, Flags, Root, Pos, 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
    WriteCLen();\r
  } else {\r
    PutBits(TBIT, 0);\r
    PutBits(TBIT, 0);\r
    PutBits(CBIT, 0);\r
    PutBits(CBIT, Root);\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
  Pos = 0;\r
  for (i = 0; i < Size; i++) {\r
    if (i % UINT8_BIT == 0) {\r
      Flags = mBuf[Pos++];\r
    } else {\r
      Flags <<= 1;\r
    }\r
    if (Flags & (1U << (UINT8_BIT - 1))) {\r
      EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));\r
      k = mBuf[Pos++] << UINT8_BIT;\r
      k += mBuf[Pos++];\r
      EncodeP(k);\r
    } else {\r
      EncodeC(mBuf[Pos++]);\r
    }\r
  }\r
  for (i = 0; i < NC; i++) {\r
    mCFreq[i] = 0;\r
  }\r
  for (i = 0; i < NP; i++) {\r
    mPFreq[i] = 0;\r
  }\r
}\r
\r
\r
STATIC\r
VOID\r
Output (\r
  IN UINT32 c,\r
  IN UINT32 p\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Outputs an Original Character or a Pointer\r
\r
Arguments:\r
\r
  c     - The original character or the 'String Length' element of a Pointer\r
  p     - 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
    if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {\r
      SendBlock();\r
      mOutputPos = 0;\r
    }\r
    CPos = mOutputPos++;\r
    mBuf[CPos] = 0;\r
  }\r
  mBuf[mOutputPos++] = (UINT8) c;\r
  mCFreq[c]++;\r
  if (c >= (1U << UINT8_BIT)) {\r
    mBuf[CPos] |= mOutputMask;\r
    mBuf[mOutputPos++] = (UINT8)(p >> UINT8_BIT);\r
    mBuf[mOutputPos++] = (UINT8) p;\r
    c = 0;\r
    while (p) {\r
      p >>= 1;\r
      c++;\r
    }\r
    mPFreq[c]++;\r
  }\r
}\r
\r
STATIC\r
VOID\r
HufEncodeStart ()\r
{\r
  INT32 i;\r
\r
  for (i = 0; i < NC; i++) {\r
    mCFreq[i] = 0;\r
  }\r
  for (i = 0; i < NP; i++) {\r
    mPFreq[i] = 0;\r
  }\r
  mOutputPos = mOutputMask = 0;\r
  InitPutBits();\r
  return;\r
}\r
\r
STATIC\r
VOID\r
HufEncodeEnd ()\r
{\r
  SendBlock();\r
\r
  //\r
  // Flush remaining bits\r
  //\r
  PutBits(UINT8_BIT - 1, 0);\r
\r
  return;\r
}\r
\r
\r
STATIC\r
VOID\r
MakeCrcTable ()\r
{\r
  UINT32 i, j, r;\r
\r
  for (i = 0; i <= UINT8_MAX; i++) {\r
    r = i;\r
    for (j = 0; j < UINT8_BIT; j++) {\r
      if (r & 1) {\r
        r = (r >> 1) ^ CRCPOLY;\r
      } else {\r
        r >>= 1;\r
      }\r
    }\r
    mCrcTable[i] = (UINT16)r;\r
  }\r
}\r
\r
STATIC\r
VOID\r
PutBits (\r
  IN INT32 n,\r
  IN UINT32 x\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Outputs rightmost n bits of x\r
\r
Arguments:\r
\r
  n   - 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
  if (n < mBitCount) {\r
    mSubBitBuf |= x << (mBitCount -= n);\r
  } else {\r
\r
    Temp = (UINT8)(mSubBitBuf | (x >> (n -= mBitCount)));\r
    if (mDst < mDstUpperLimit) {\r
      *mDst++ = Temp;\r
    }\r
    mCompSize++;\r
\r
    if (n < UINT8_BIT) {\r
      mSubBitBuf = x << (mBitCount = UINT8_BIT - n);\r
    } else {\r
\r
      Temp = (UINT8)(x >> (n - UINT8_BIT));\r
      if (mDst < mDstUpperLimit) {\r
        *mDst++ = Temp;\r
      }\r
      mCompSize++;\r
\r
      mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - n);\r
    }\r
  }\r
}\r
\r
STATIC\r
INT32\r
FreadCrc (\r
  OUT UINT8 *p,\r
  IN  INT32 n\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Read in source data\r
\r
Arguments:\r
\r
  p   - the buffer to hold the data\r
  n   - number of bytes to read\r
\r
Returns:\r
\r
  number of bytes actually read\r
\r
--*/\r
{\r
  INT32 i;\r
\r
  for (i = 0; mSrc < mSrcUpperLimit && i < n; i++) {\r
    *p++ = *mSrc++;\r
  }\r
  n = i;\r
\r
  p -= n;\r
  mOrigSize += n;\r
  while (--i >= 0) {\r
    UPDATE_CRC(*p++);\r
  }\r
  return n;\r
}\r
\r
\r
STATIC\r
VOID\r
InitPutBits ()\r
{\r
  mBitCount = UINT8_BIT;\r
  mSubBitBuf = 0;\r
}\r
\r
STATIC\r
VOID\r
CountLen (\r
  IN INT32 i\r
  )\r
/*++\r
\r
Routine Description:\r
\r
  Count the number of each code length for a Huffman tree.\r
\r
Arguments:\r
\r
  i   - the top node\r
\r
Returns: (VOID)\r
\r
--*/\r
{\r
  STATIC INT32 Depth = 0;\r
\r
  if (i < mN) {\r
    mLenCnt[(Depth < 16) ? Depth : 16]++;\r
  } else {\r
    Depth++;\r
    CountLen(mLeft [i]);\r
    CountLen(mRight[i]);\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
--*/\r
{\r
  INT32 i, k;\r
  UINT32 Cum;\r
\r
  for (i = 0; i <= 16; i++) {\r
    mLenCnt[i] = 0;\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
\r
  Cum = 0;\r
  for (i = 16; i > 0; i--) {\r
    Cum += mLenCnt[i] << (16 - i);\r
  }\r
  while (Cum != (1U << 16)) {\r
    mLenCnt[16]--;\r
    for (i = 15; i > 0; i--) {\r
      if (mLenCnt[i] != 0) {\r
        mLenCnt[i]--;\r
        mLenCnt[i+1] += 2;\r
        break;\r
      }\r
    }\r
    Cum--;\r
  }\r
  for (i = 16; i > 0; i--) {\r
    k = mLenCnt[i];\r
    while (--k >= 0) {\r
      mLen[*mSortPtr++] = (UINT8)i;\r
    }\r
  }\r
}\r
\r
STATIC\r
VOID\r
DownHeap (\r
  IN INT32 i\r
  )\r
{\r
  INT32 j, k;\r
\r
  //\r
  // priority queue: send i-th entry down heap\r
  //\r
\r
  k = mHeap[i];\r
  while ((j = 2 * i) <= mHeapSize) {\r
    if (j < mHeapSize && mFreq[mHeap[j]] > mFreq[mHeap[j + 1]]) {\r
      j++;\r
    }\r
    if (mFreq[k] <= mFreq[mHeap[j]]) {\r
      break;\r
    }\r
    mHeap[i] = mHeap[j];\r
    i = j;\r
  }\r
  mHeap[i] = (INT16)k;\r
}\r
\r
STATIC\r
VOID\r
MakeCode (\r
  IN  INT32 n,\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
  n     - 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    i;\r
  UINT16   Start[18];\r
\r
  Start[1] = 0;\r
  for (i = 1; i <= 16; i++) {\r
    Start[i + 1] = (UINT16)((Start[i] + mLenCnt[i]) << 1);\r
  }\r
  for (i = 0; i < n; i++) {\r
    Code[i] = Start[Len[i]]++;\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 i, j, k, Avail;\r
\r
  //\r
  // make tree, calculate len[], return root\r
  //\r
\r
  mN = NParm;\r
  mFreq = FreqParm;\r
  mLen = LenParm;\r
  Avail = mN;\r
  mHeapSize = 0;\r
  mHeap[1] = 0;\r
  for (i = 0; i < mN; i++) {\r
    mLen[i] = 0;\r
    if (mFreq[i]) {\r
      mHeap[++mHeapSize] = (INT16)i;\r
    }\r
  }\r
  if (mHeapSize < 2) {\r
    CodeParm[mHeap[1]] = 0;\r
    return mHeap[1];\r
  }\r
  for (i = mHeapSize / 2; i >= 1; i--) {\r
\r
    //\r
    // make priority queue\r
    //\r
    DownHeap(i);\r
  }\r
  mSortPtr = CodeParm;\r
  do {\r
    i = mHeap[1];\r
    if (i < mN) {\r
      *mSortPtr++ = (UINT16)i;\r
    }\r
    mHeap[1] = mHeap[mHeapSize--];\r
    DownHeap(1);\r
    j = mHeap[1];\r
    if (j < mN) {\r
      *mSortPtr++ = (UINT16)j;\r
    }\r
    k = Avail++;\r
    mFreq[k] = (UINT16)(mFreq[i] + mFreq[j]);\r
    mHeap[1] = (INT16)k;\r
    DownHeap(1);\r
    mLeft[k] = (UINT16)i;\r
    mRight[k] = (UINT16)j;\r
  } while (mHeapSize > 1);\r
\r
  mSortPtr = CodeParm;\r
  MakeLen(k);\r
  MakeCode(NParm, LenParm, CodeParm);\r
\r
  //\r
  // return root\r
  //\r
  return k;\r
}\r
\r