Enable EFIv1 compression in bmpbklk_utility.

utility/eficompress.c

+/*
+
+Copyright (c) 2006, Intel Corporation
+All rights reserved. This program and the accompanying materials
+are licensed and made available under the terms and conditions of the BSD License
+which accompanies this distribution.  The full text of the license may be found at
+http://opensource.org/licenses/bsd-license.php
+
+THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
+WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+
+Module Name:
+
+  EfiCompress.c
+
+Abstract:
+
+  Compression routine. The compression algorithm is a mixture of
+  LZ77 and Huffman coding. LZ77 transforms the source data into a
+  sequence of Original Characters and Pointers to repeated strings.
+  This sequence is further divided into Blocks and Huffman codings
+  are applied to each Block.
+
+--*/
+
+#include <errno.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+#include "eficompress.h"
+
+
+//
+// Macro Definitions
+//
+
+typedef INT16             NODE;
+#define UINT8_BIT         8
+#define THRESHOLD         3
+#define INIT_CRC          0
+#define WNDBIT            13
+#define WNDSIZ            (1U << WNDBIT)
+#define MAXMATCH          256
+#define PERC_FLAG         0x8000U
+#define CODE_BIT          16
+#define NIL               0
+#define MAX_HASH_VAL      (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
+#define HASH(p, c)        ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
+#define CRCPOLY           0xA001
+#define UPDATE_CRC(c)     mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
+
+//
+// C: the Char&Len Set; P: the Position Set; T: the exTra Set
+//
+
+#define NC                (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
+#define CBIT              9
+#define NP                (WNDBIT + 1)
+#define PBIT              4
+#define NT                (CODE_BIT + 3)
+#define TBIT              5
+#if NT > NP
+  #define                 NPT NT
+#else
+  #define                 NPT NP
+#endif
+
+//
+// Function Prototypes
+//
+
+STATIC
+VOID
+PutDword(
+  IN UINT32 Data
+  );
+
+STATIC
+EFI_STATUS
+AllocateMemory (
+  );
+
+STATIC
+VOID
+FreeMemory (
+  );
+
+STATIC
+VOID
+InitSlide (
+  );
+
+STATIC
+NODE
+Child (
+  IN NODE q,
+  IN UINT8 c
+  );
+
+STATIC
+VOID
+MakeChild (
+  IN NODE q,
+  IN UINT8 c,
+  IN NODE r
+  );
+
+STATIC
+VOID
+Split (
+  IN NODE Old
+  );
+
+STATIC
+VOID
+InsertNode (
+  );
+
+STATIC
+VOID
+DeleteNode (
+  );
+
+STATIC
+VOID
+GetNextMatch (
+  );
+
+STATIC
+EFI_STATUS
+Encode (
+  );
+
+STATIC
+VOID
+CountTFreq (
+  );
+
+STATIC
+VOID
+WritePTLen (
+  IN INT32 n,
+  IN INT32 nbit,
+  IN INT32 Special
+  );
+
+STATIC
+VOID
+WriteCLen (
+  );
+
+STATIC
+VOID
+EncodeC (
+  IN INT32 c
+  );
+
+STATIC
+VOID
+EncodeP (
+  IN UINT32 p
+  );
+
+STATIC
+VOID
+SendBlock (
+  );
+
+STATIC
+VOID
+Output (
+  IN UINT32 c,
+  IN UINT32 p
+  );
+
+STATIC
+VOID
+HufEncodeStart (
+  );
+
+STATIC
+VOID
+HufEncodeEnd (
+  );
+
+STATIC
+VOID
+MakeCrcTable (
+  );
+
+STATIC
+VOID
+PutBits (
+  IN INT32 n,
+  IN UINT32 x
+  );
+
+STATIC
+INT32
+FreadCrc (
+  OUT UINT8 *p,
+  IN  INT32 n
+  );
+
+STATIC
+VOID
+InitPutBits (
+  );
+
+STATIC
+VOID
+CountLen (
+  IN INT32 i
+  );
+
+STATIC
+VOID
+MakeLen (
+  IN INT32 Root
+  );
+
+STATIC
+VOID
+DownHeap (
+  IN INT32 i
+  );
+
+STATIC
+VOID
+MakeCode (
+  IN  INT32 n,
+  IN  UINT8 Len[],
+  OUT UINT16 Code[]
+  );
+
+STATIC
+INT32
+MakeTree (
+  IN  INT32   NParm,
+  IN  UINT16  FreqParm[],
+  OUT UINT8   LenParm[],
+  OUT UINT16  CodeParm[]
+  );
+
+
+//
+//  Global Variables
+//
+
+STATIC UINT8  *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
+
+STATIC UINT8  *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
+STATIC INT16  mHeap[NC + 1];
+STATIC INT32  mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
+STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
+STATIC UINT32 mCompSize, mOrigSize;
+
+STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1],
+              mCrcTable[UINT8_MAX + 1], mCFreq[2 * NC - 1], mCCode[NC],
+              mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
+
+STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
+
+
+//
+// functions
+//
+
+EFI_STATUS
+EfiCompress (
+  IN      UINT8   *SrcBuffer,
+  IN      UINT32  SrcSize,
+  IN      UINT8   *DstBuffer,
+  IN OUT  UINT32  *DstSize
+  )
+/*++
+
+Routine Description:
+
+  The main compression routine.
+
+Arguments:
+
+  SrcBuffer   - The buffer storing the source data
+  SrcSize     - The size of source data
+  DstBuffer   - The buffer to store the compressed data
+  DstSize     - On input, the size of DstBuffer; On output,
+                the size of the actual compressed data.
+
+Returns:
+
+  EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,
+                DstSize contains the size needed.
+  EFI_SUCCESS           - Compression is successful.
+
+--*/
+{
+  EFI_STATUS Status = EFI_SUCCESS;
+
+  //
+  // Initializations
+  //
+  mBufSiz = 0;
+  mBuf = NULL;
+  mText       = NULL;
+  mLevel      = NULL;
+  mChildCount = NULL;
+  mPosition   = NULL;
+  mParent     = NULL;
+  mPrev       = NULL;
+  mNext       = NULL;
+
+
+  mSrc = SrcBuffer;
+  mSrcUpperLimit = mSrc + SrcSize;
+  mDst = DstBuffer;
+  mDstUpperLimit = mDst + *DstSize;
+
+  PutDword(0L);
+  PutDword(0L);
+
+  MakeCrcTable ();
+
+  mOrigSize = mCompSize = 0;
+  mCrc = INIT_CRC;
+
+  //
+  // Compress it
+  //
+
+  Status = Encode();
+  if (EFI_ERROR (Status)) {
+    return EFI_OUT_OF_RESOURCES;
+  }
+
+  //
+  // Null terminate the compressed data
+  //
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = 0;
+  }
+
+  //
+  // Fill in compressed size and original size
+  //
+  mDst = DstBuffer;
+  PutDword(mCompSize+1);
+  PutDword(mOrigSize);
+
+  //
+  // Return
+  //
+
+  if (mCompSize + 1 + 8 > *DstSize) {
+    *DstSize = mCompSize + 1 + 8;
+    return EFI_BUFFER_TOO_SMALL;
+  } else {
+    *DstSize = mCompSize + 1 + 8;
+    return EFI_SUCCESS;
+  }
+
+}
+
+STATIC
+VOID
+PutDword(
+  IN UINT32 Data
+  )
+/*++
+
+Routine Description:
+
+  Put a dword to output stream
+
+Arguments:
+
+  Data    - the dword to put
+
+Returns: (VOID)
+
+--*/
+{
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = (UINT8)(((UINT8)(Data        )) & 0xff);
+  }
+
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = (UINT8)(((UINT8)(Data >> 0x08)) & 0xff);
+  }
+
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = (UINT8)(((UINT8)(Data >> 0x10)) & 0xff);
+  }
+
+  if (mDst < mDstUpperLimit) {
+    *mDst++ = (UINT8)(((UINT8)(Data >> 0x18)) & 0xff);
+  }
+}
+
+STATIC
+EFI_STATUS
+AllocateMemory ()
+/*++
+
+Routine Description:
+
+  Allocate memory spaces for data structures used in compression process
+
+Argements: (VOID)
+
+Returns:
+
+  EFI_SUCCESS           - Memory is allocated successfully
+  EFI_OUT_OF_RESOURCES  - Allocation fails
+
+--*/
+{
+  UINT32      i;
+
+  mText       = malloc (WNDSIZ * 2 + MAXMATCH);
+  for (i = 0 ; i < WNDSIZ * 2 + MAXMATCH; i ++) {
+    mText[i] = 0;
+  }
+
+  mLevel      = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mLevel));
+  mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mChildCount));
+  mPosition   = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mPosition));
+  mParent     = malloc (WNDSIZ * 2 * sizeof(*mParent));
+  mPrev       = malloc (WNDSIZ * 2 * sizeof(*mPrev));
+  mNext       = malloc ((MAX_HASH_VAL + 1) * sizeof(*mNext));
+
+  mBufSiz = 16 * 1024U;
+  while ((mBuf = malloc(mBufSiz)) == NULL) {
+    mBufSiz = (mBufSiz / 10U) * 9U;
+    if (mBufSiz < 4 * 1024U) {
+      return EFI_OUT_OF_RESOURCES;
+    }
+  }
+  mBuf[0] = 0;
+
+  return EFI_SUCCESS;
+}
+
+VOID
+FreeMemory ()
+/*++
+
+Routine Description:
+
+  Called when compression is completed to free memory previously allocated.
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  if (mText) {
+    free (mText);
+  }
+
+  if (mLevel) {
+    free (mLevel);
+  }
+
+  if (mChildCount) {
+    free (mChildCount);
+  }
+
+  if (mPosition) {
+    free (mPosition);
+  }
+
+  if (mParent) {
+    free (mParent);
+  }
+
+  if (mPrev) {
+    free (mPrev);
+  }
+
+  if (mNext) {
+    free (mNext);
+  }
+
+  if (mBuf) {
+    free (mBuf);
+  }
+
+  return;
+}
+
+
+STATIC
+VOID
+InitSlide ()
+/*++
+
+Routine Description:
+
+  Initialize String Info Log data structures
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  NODE i;
+
+  for (i = WNDSIZ; i <= WNDSIZ + UINT8_MAX; i++) {
+    mLevel[i] = 1;
+    mPosition[i] = NIL;  /* sentinel */
+  }
+  for (i = WNDSIZ; i < WNDSIZ * 2; i++) {
+    mParent[i] = NIL;
+  }
+  mAvail = 1;
+  for (i = 1; i < WNDSIZ - 1; i++) {
+    mNext[i] = (NODE)(i + 1);
+  }
+
+  mNext[WNDSIZ - 1] = NIL;
+  for (i = WNDSIZ * 2; i <= MAX_HASH_VAL; i++) {
+    mNext[i] = NIL;
+  }
+}
+
+
+STATIC
+NODE
+Child (
+  IN NODE q,
+  IN UINT8 c
+  )
+/*++
+
+Routine Description:
+
+  Find child node given the parent node and the edge character
+
+Arguments:
+
+  q       - the parent node
+  c       - the edge character
+
+Returns:
+
+  The child node (NIL if not found)
+
+--*/
+{
+  NODE r;
+
+  r = mNext[HASH(q, c)];
+  mParent[NIL] = q;  /* sentinel */
+  while (mParent[r] != q) {
+    r = mNext[r];
+  }
+
+  return r;
+}
+
+STATIC
+VOID
+MakeChild (
+  IN NODE q,
+  IN UINT8 c,
+  IN NODE r
+  )
+/*++
+
+Routine Description:
+
+  Create a new child for a given parent node.
+
+Arguments:
+
+  q       - the parent node
+  c       - the edge character
+  r       - the child node
+
+Returns: (VOID)
+
+--*/
+{
+  NODE h, t;
+
+  h = (NODE)HASH(q, c);
+  t = mNext[h];
+  mNext[h] = r;
+  mNext[r] = t;
+  mPrev[t] = r;
+  mPrev[r] = h;
+  mParent[r] = q;
+  mChildCount[q]++;
+}
+
+STATIC
+VOID
+Split (
+  NODE Old
+  )
+/*++
+
+Routine Description:
+
+  Split a node.
+
+Arguments:
+
+  Old     - the node to split
+
+Returns: (VOID)
+
+--*/
+{
+  NODE New, t;
+
+  New = mAvail;
+  mAvail = mNext[New];
+  mChildCount[New] = 0;
+  t = mPrev[Old];
+  mPrev[New] = t;
+  mNext[t] = New;
+  t = mNext[Old];
+  mNext[New] = t;
+  mPrev[t] = New;
+  mParent[New] = mParent[Old];
+  mLevel[New] = (UINT8)mMatchLen;
+  mPosition[New] = mPos;
+  MakeChild(New, mText[mMatchPos + mMatchLen], Old);
+  MakeChild(New, mText[mPos + mMatchLen], mPos);
+}
+
+STATIC
+VOID
+InsertNode ()
+/*++
+
+Routine Description:
+
+  Insert string info for current position into the String Info Log
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  NODE q, r, j, t;
+  UINT8 c, *t1, *t2;
+
+  if (mMatchLen >= 4) {
+
+    //
+    // We have just got a long match, the target tree
+    // can be located by MatchPos + 1. Travese the tree
+    // from bottom up to get to a proper starting point.
+    // The usage of PERC_FLAG ensures proper node deletion
+    // in DeleteNode() later.
+    //
+
+    mMatchLen--;
+    r = (INT16)((mMatchPos + 1) | WNDSIZ);
+    while ((q = mParent[r]) == NIL) {
+      r = mNext[r];
+    }
+    while (mLevel[q] >= mMatchLen) {
+      r = q;  q = mParent[q];
+    }
+    t = q;
+    while (mPosition[t] < 0) {
+      mPosition[t] = mPos;
+      t = mParent[t];
+    }
+    if (t < WNDSIZ) {
+      mPosition[t] = (NODE)(mPos | PERC_FLAG);
+    }
+  } else {
+
+    //
+    // Locate the target tree
+    //
+
+    q = (INT16)(mText[mPos] + WNDSIZ);
+    c = mText[mPos + 1];
+    if ((r = Child(q, c)) == NIL) {
+      MakeChild(q, c, mPos);
+      mMatchLen = 1;
+      return;
+    }
+    mMatchLen = 2;
+  }
+
+  //
+  // Traverse down the tree to find a match.
+  // Update Position value along the route.
+  // Node split or creation is involved.
+  //
+
+  for ( ; ; ) {
+    if (r >= WNDSIZ) {
+      j = MAXMATCH;
+      mMatchPos = r;
+    } else {
+      j = mLevel[r];
+      mMatchPos = (NODE)(mPosition[r] & ~PERC_FLAG);
+    }
+    if (mMatchPos >= mPos) {
+      mMatchPos -= WNDSIZ;
+    }
+    t1 = &mText[mPos + mMatchLen];
+    t2 = &mText[mMatchPos + mMatchLen];
+    while (mMatchLen < j) {
+      if (*t1 != *t2) {
+        Split(r);
+        return;
+      }
+      mMatchLen++;
+      t1++;
+      t2++;
+    }
+    if (mMatchLen >= MAXMATCH) {
+      break;
+    }
+    mPosition[r] = mPos;
+    q = r;
+    if ((r = Child(q, *t1)) == NIL) {
+      MakeChild(q, *t1, mPos);
+      return;
+    }
+    mMatchLen++;
+  }
+  t = mPrev[r];
+  mPrev[mPos] = t;
+  mNext[t] = mPos;
+  t = mNext[r];
+  mNext[mPos] = t;
+  mPrev[t] = mPos;
+  mParent[mPos] = q;
+  mParent[r] = NIL;
+
+  //
+  // Special usage of 'next'
+  //
+  mNext[r] = mPos;
+
+}
+
+STATIC
+VOID
+DeleteNode ()
+/*++
+
+Routine Description:
+
+  Delete outdated string info. (The Usage of PERC_FLAG
+  ensures a clean deletion)
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  NODE q, r, s, t, u;
+
+  if (mParent[mPos] == NIL) {
+    return;
+  }
+
+  r = mPrev[mPos];
+  s = mNext[mPos];
+  mNext[r] = s;
+  mPrev[s] = r;
+  r = mParent[mPos];
+  mParent[mPos] = NIL;
+  if (r >= WNDSIZ || --mChildCount[r] > 1) {
+    return;
+  }
+  t = (NODE)(mPosition[r] & ~PERC_FLAG);
+  if (t >= mPos) {
+    t -= WNDSIZ;
+  }
+  s = t;
+  q = mParent[r];
+  while ((u = mPosition[q]) & PERC_FLAG) {
+    u &= ~PERC_FLAG;
+    if (u >= mPos) {
+      u -= WNDSIZ;
+    }
+    if (u > s) {
+      s = u;
+    }
+    mPosition[q] = (INT16)(s | WNDSIZ);
+    q = mParent[q];
+  }
+  if (q < WNDSIZ) {
+    if (u >= mPos) {
+      u -= WNDSIZ;
+    }
+    if (u > s) {
+      s = u;
+    }
+    mPosition[q] = (INT16)(s | WNDSIZ | PERC_FLAG);
+  }
+  s = Child(r, mText[t + mLevel[r]]);
+  t = mPrev[s];
+  u = mNext[s];
+  mNext[t] = u;
+  mPrev[u] = t;
+  t = mPrev[r];
+  mNext[t] = s;
+  mPrev[s] = t;
+  t = mNext[r];
+  mPrev[t] = s;
+  mNext[s] = t;
+  mParent[s] = mParent[r];
+  mParent[r] = NIL;
+  mNext[r] = mAvail;
+  mAvail = r;
+}
+
+STATIC
+VOID
+GetNextMatch ()
+/*++
+
+Routine Description:
+
+  Advance the current position (read in new data if needed).
+  Delete outdated string info. Find a match string for current position.
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  INT32 n;
+
+  mRemainder--;
+  if (++mPos == WNDSIZ * 2) {
+    memmove(&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
+    n = FreadCrc(&mText[WNDSIZ + MAXMATCH], WNDSIZ);
+    mRemainder += n;
+    mPos = WNDSIZ;
+  }
+  DeleteNode();
+  InsertNode();
+}
+
+STATIC
+EFI_STATUS
+Encode ()
+/*++
+
+Routine Description:
+
+  The main controlling routine for compression process.
+
+Arguments: (VOID)
+
+Returns:
+
+  EFI_SUCCESS           - The compression is successful
+  EFI_OUT_0F_RESOURCES  - Not enough memory for compression process
+
+--*/
+{
+  EFI_STATUS  Status;
+  INT32       LastMatchLen;
+  NODE        LastMatchPos;
+
+  Status = AllocateMemory();
+  if (EFI_ERROR(Status)) {
+    FreeMemory();
+    return Status;
+  }
+
+  InitSlide();
+
+  HufEncodeStart();
+
+  mRemainder = FreadCrc(&mText[WNDSIZ], WNDSIZ + MAXMATCH);
+
+  mMatchLen = 0;
+  mPos = WNDSIZ;
+  InsertNode();
+  if (mMatchLen > mRemainder) {
+    mMatchLen = mRemainder;
+  }
+  while (mRemainder > 0) {
+    LastMatchLen = mMatchLen;
+    LastMatchPos = mMatchPos;
+    GetNextMatch();
+    if (mMatchLen > mRemainder) {
+      mMatchLen = mRemainder;
+    }
+
+    if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
+
+      //
+      // Not enough benefits are gained by outputting a pointer,
+      // so just output the original character
+      //
+
+      Output(mText[mPos - 1], 0);
+    } else {
+
+      //
+      // Outputting a pointer is beneficial enough, do it.
+      //
+
+      Output(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
+             (mPos - LastMatchPos - 2) & (WNDSIZ - 1));
+      while (--LastMatchLen > 0) {
+        GetNextMatch();
+      }
+      if (mMatchLen > mRemainder) {
+        mMatchLen = mRemainder;
+      }
+    }
+  }
+
+  HufEncodeEnd();
+  FreeMemory();
+  return EFI_SUCCESS;
+}
+
+STATIC
+VOID
+CountTFreq ()
+/*++
+
+Routine Description:
+
+  Count the frequencies for the Extra Set
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  INT32 i, k, n, Count;
+
+  for (i = 0; i < NT; i++) {
+    mTFreq[i] = 0;
+  }
+  n = NC;
+  while (n > 0 && mCLen[n - 1] == 0) {
+    n--;
+  }
+  i = 0;
+  while (i < n) {
+    k = mCLen[i++];
+    if (k == 0) {
+      Count = 1;
+      while (i < n && mCLen[i] == 0) {
+        i++;
+        Count++;
+      }
+      if (Count <= 2) {
+        mTFreq[0] = (UINT16)(mTFreq[0] + Count);
+      } else if (Count <= 18) {
+        mTFreq[1]++;
+      } else if (Count == 19) {
+        mTFreq[0]++;
+        mTFreq[1]++;
+      } else {
+        mTFreq[2]++;
+      }
+    } else {
+      mTFreq[k + 2]++;
+    }
+  }
+}
+
+STATIC
+VOID
+WritePTLen (
+  IN INT32 n,
+  IN INT32 nbit,
+  IN INT32 Special
+  )
+/*++
+
+Routine Description:
+
+  Outputs the code length array for the Extra Set or the Position Set.
+
+Arguments:
+
+  n       - the number of symbols
+  nbit    - the number of bits needed to represent 'n'
+  Special - the special symbol that needs to be take care of
+
+Returns: (VOID)
+
+--*/
+{
+  INT32 i, k;
+
+  while (n > 0 && mPTLen[n - 1] == 0) {
+    n--;
+  }
+  PutBits(nbit, n);
+  i = 0;
+  while (i < n) {
+    k = mPTLen[i++];
+    if (k <= 6) {
+      PutBits(3, k);
+    } else {
+      PutBits(k - 3, (1U << (k - 3)) - 2);
+    }
+    if (i == Special) {
+      while (i < 6 && mPTLen[i] == 0) {
+        i++;
+      }
+      PutBits(2, (i - 3) & 3);
+    }
+  }
+}
+
+STATIC
+VOID
+WriteCLen ()
+/*++
+
+Routine Description:
+
+  Outputs the code length array for Char&Length Set
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  INT32 i, k, n, Count;
+
+  n = NC;
+  while (n > 0 && mCLen[n - 1] == 0) {
+    n--;
+  }
+  PutBits(CBIT, n);
+  i = 0;
+  while (i < n) {
+    k = mCLen[i++];
+    if (k == 0) {
+      Count = 1;
+      while (i < n && mCLen[i] == 0) {
+        i++;
+        Count++;
+      }
+      if (Count <= 2) {
+        for (k = 0; k < Count; k++) {
+          PutBits(mPTLen[0], mPTCode[0]);
+        }
+      } else if (Count <= 18) {
+        PutBits(mPTLen[1], mPTCode[1]);
+        PutBits(4, Count - 3);
+      } else if (Count == 19) {
+        PutBits(mPTLen[0], mPTCode[0]);
+        PutBits(mPTLen[1], mPTCode[1]);
+        PutBits(4, 15);
+      } else {
+        PutBits(mPTLen[2], mPTCode[2]);
+        PutBits(CBIT, Count - 20);
+      }
+    } else {
+      PutBits(mPTLen[k + 2], mPTCode[k + 2]);
+    }
+  }
+}
+
+STATIC
+VOID
+EncodeC (
+  IN INT32 c
+  )
+{
+  PutBits(mCLen[c], mCCode[c]);
+}
+
+STATIC
+VOID
+EncodeP (
+  IN UINT32 p
+  )
+{
+  UINT32 c, q;
+
+  c = 0;
+  q = p;
+  while (q) {
+    q >>= 1;
+    c++;
+  }
+  PutBits(mPTLen[c], mPTCode[c]);
+  if (c > 1) {
+    PutBits(c - 1, p & (0xFFFFU >> (17 - c)));
+  }
+}
+
+STATIC
+VOID
+SendBlock ()
+/*++
+
+Routine Description:
+
+  Huffman code the block and output it.
+
+Argument: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+  UINT32 i, k, Flags, Root, Pos, Size;
+  Flags = 0;
+
+  Root = MakeTree(NC, mCFreq, mCLen, mCCode);
+  Size = mCFreq[Root];
+  PutBits(16, Size);
+  if (Root >= NC) {
+    CountTFreq();
+    Root = MakeTree(NT, mTFreq, mPTLen, mPTCode);
+    if (Root >= NT) {
+      WritePTLen(NT, TBIT, 3);
+    } else {
+      PutBits(TBIT, 0);
+      PutBits(TBIT, Root);
+    }
+    WriteCLen();
+  } else {
+    PutBits(TBIT, 0);
+    PutBits(TBIT, 0);
+    PutBits(CBIT, 0);
+    PutBits(CBIT, Root);
+  }
+  Root = MakeTree(NP, mPFreq, mPTLen, mPTCode);
+  if (Root >= NP) {
+    WritePTLen(NP, PBIT, -1);
+  } else {
+    PutBits(PBIT, 0);
+    PutBits(PBIT, Root);
+  }
+  Pos = 0;
+  for (i = 0; i < Size; i++) {
+    if (i % UINT8_BIT == 0) {
+      Flags = mBuf[Pos++];
+    } else {
+      Flags <<= 1;
+    }
+    if (Flags & (1U << (UINT8_BIT - 1))) {
+      EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
+      k = mBuf[Pos++] << UINT8_BIT;
+      k += mBuf[Pos++];
+      EncodeP(k);
+    } else {
+      EncodeC(mBuf[Pos++]);
+    }
+  }
+  for (i = 0; i < NC; i++) {
+    mCFreq[i] = 0;
+  }
+  for (i = 0; i < NP; i++) {
+    mPFreq[i] = 0;
+  }
+}
+
+
+STATIC
+VOID
+Output (
+  IN UINT32 c,
+  IN UINT32 p
+  )
+/*++
+
+Routine Description:
+
+  Outputs an Original Character or a Pointer
+
+Arguments:
+
+  c     - The original character or the 'String Length' element of a Pointer
+  p     - The 'Position' field of a Pointer
+
+Returns: (VOID)
+
+--*/
+{
+  STATIC UINT32 CPos;
+
+  if ((mOutputMask >>= 1) == 0) {
+    mOutputMask = 1U << (UINT8_BIT - 1);
+    if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
+      SendBlock();
+      mOutputPos = 0;
+    }
+    CPos = mOutputPos++;
+    mBuf[CPos] = 0;
+  }
+  mBuf[mOutputPos++] = (UINT8) c;
+  mCFreq[c]++;
+  if (c >= (1U << UINT8_BIT)) {
+    mBuf[CPos] |= mOutputMask;
+    mBuf[mOutputPos++] = (UINT8)(p >> UINT8_BIT);
+    mBuf[mOutputPos++] = (UINT8) p;
+    c = 0;
+    while (p) {
+      p >>= 1;
+      c++;
+    }
+    mPFreq[c]++;
+  }
+}
+
+STATIC
+VOID
+HufEncodeStart ()
+{
+  INT32 i;
+
+  for (i = 0; i < NC; i++) {
+    mCFreq[i] = 0;
+  }
+  for (i = 0; i < NP; i++) {
+    mPFreq[i] = 0;
+  }
+  mOutputPos = mOutputMask = 0;
+  InitPutBits();
+  return;
+}
+
+STATIC
+VOID
+HufEncodeEnd ()
+{
+  SendBlock();
+
+  //
+  // Flush remaining bits
+  //
+  PutBits(UINT8_BIT - 1, 0);
+
+  return;
+}
+
+
+STATIC
+VOID
+MakeCrcTable ()
+{
+  UINT32 i, j, r;
+
+  for (i = 0; i <= UINT8_MAX; i++) {
+    r = i;
+    for (j = 0; j < UINT8_BIT; j++) {
+      if (r & 1) {
+        r = (r >> 1) ^ CRCPOLY;
+      } else {
+        r >>= 1;
+      }
+    }
+    mCrcTable[i] = (UINT16)r;
+  }
+}
+
+STATIC
+VOID
+PutBits (
+  IN INT32 n,
+  IN UINT32 x
+  )
+/*++
+
+Routine Description:
+
+  Outputs rightmost n bits of x
+
+Argments:
+
+  n   - the rightmost n bits of the data is used
+  x   - the data
+
+Returns: (VOID)
+
+--*/
+{
+  UINT8 Temp;
+
+  if (n < mBitCount) {
+    mSubBitBuf |= x << (mBitCount -= n);
+  } else {
+
+    Temp = (UINT8)(mSubBitBuf | (x >> (n -= mBitCount)));
+    if (mDst < mDstUpperLimit) {
+      *mDst++ = Temp;
+    }
+    mCompSize++;
+
+    if (n < UINT8_BIT) {
+      mSubBitBuf = x << (mBitCount = UINT8_BIT - n);
+    } else {
+
+      Temp = (UINT8)(x >> (n - UINT8_BIT));
+      if (mDst < mDstUpperLimit) {
+        *mDst++ = Temp;
+      }
+      mCompSize++;
+
+      mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - n);
+    }
+  }
+}
+
+STATIC
+INT32
+FreadCrc (
+  OUT UINT8 *p,
+  IN  INT32 n
+  )
+/*++
+
+Routine Description:
+
+  Read in source data
+
+Arguments:
+
+  p   - the buffer to hold the data
+  n   - number of bytes to read
+
+Returns:
+
+  number of bytes actually read
+
+--*/
+{
+  INT32 i;
+
+  for (i = 0; mSrc < mSrcUpperLimit && i < n; i++) {
+    *p++ = *mSrc++;
+  }
+  n = i;
+
+  p -= n;
+  mOrigSize += n;
+  while (--i >= 0) {
+    UPDATE_CRC(*p++);
+  }
+  return n;
+}
+
+
+STATIC
+VOID
+InitPutBits ()
+{
+  mBitCount = UINT8_BIT;
+  mSubBitBuf = 0;
+}
+
+STATIC
+VOID
+CountLen (
+  IN INT32 i
+  )
+/*++
+
+Routine Description:
+
+  Count the number of each code length for a Huffman tree.
+
+Arguments:
+
+  i   - the top node
+
+Returns: (VOID)
+
+--*/
+{
+  STATIC INT32 Depth = 0;
+
+  if (i < mN) {
+    mLenCnt[(Depth < 16) ? Depth : 16]++;
+  } else {
+    Depth++;
+    CountLen(mLeft [i]);
+    CountLen(mRight[i]);
+    Depth--;
+  }
+}
+
+STATIC
+VOID
+MakeLen (
+  IN INT32 Root
+  )
+/*++
+
+Routine Description:
+
+  Create code length array for a Huffman tree
+
+Arguments:
+
+  Root   - the root of the tree
+
+--*/
+{
+  INT32 i, k;
+  UINT32 Cum;
+
+  for (i = 0; i <= 16; i++) {
+    mLenCnt[i] = 0;
+  }
+  CountLen(Root);
+
+  //
+  // Adjust the length count array so that
+  // no code will be generated longer than its designated length
+  //
+
+  Cum = 0;
+  for (i = 16; i > 0; i--) {
+    Cum += mLenCnt[i] << (16 - i);
+  }
+  while (Cum != (1U << 16)) {
+    mLenCnt[16]--;
+    for (i = 15; i > 0; i--) {
+      if (mLenCnt[i] != 0) {
+        mLenCnt[i]--;
+        mLenCnt[i+1] += 2;
+        break;
+      }
+    }
+    Cum--;
+  }
+  for (i = 16; i > 0; i--) {
+    k = mLenCnt[i];
+    while (--k >= 0) {
+      mLen[*mSortPtr++] = (UINT8)i;
+    }
+  }
+}
+
+STATIC
+VOID
+DownHeap (
+  IN INT32 i
+  )
+{
+  INT32 j, k;
+
+  //
+  // priority queue: send i-th entry down heap
+  //
+
+  k = mHeap[i];
+  while ((j = 2 * i) <= mHeapSize) {
+    if (j < mHeapSize && mFreq[mHeap[j]] > mFreq[mHeap[j + 1]]) {
+      j++;
+    }
+    if (mFreq[k] <= mFreq[mHeap[j]]) {
+      break;
+    }
+    mHeap[i] = mHeap[j];
+    i = j;
+  }
+  mHeap[i] = (INT16)k;
+}
+
+STATIC
+VOID
+MakeCode (
+  IN  INT32 n,
+  IN  UINT8 Len[],
+  OUT UINT16 Code[]
+  )
+/*++
+
+Routine Description:
+
+  Assign code to each symbol based on the code length array
+
+Arguments:
+
+  n     - number of symbols
+  Len   - the code length array
+  Code  - stores codes for each symbol
+
+Returns: (VOID)
+
+--*/
+{
+  INT32    i;
+  UINT16   Start[18];
+
+  Start[1] = 0;
+  for (i = 1; i <= 16; i++) {
+    Start[i + 1] = (UINT16)((Start[i] + mLenCnt[i]) << 1);
+  }
+  for (i = 0; i < n; i++) {
+    Code[i] = Start[Len[i]]++;
+  }
+}
+
+STATIC
+INT32
+MakeTree (
+  IN  INT32   NParm,
+  IN  UINT16  FreqParm[],
+  OUT UINT8   LenParm[],
+  OUT UINT16  CodeParm[]
+  )
+/*++
+
+Routine Description:
+
+  Generates Huffman codes given a frequency distribution of symbols
+
+Arguments:
+
+  NParm    - number of symbols
+  FreqParm - frequency of each symbol
+  LenParm  - code length for each symbol
+  CodeParm - code for each symbol
+
+Returns:
+
+  Root of the Huffman tree.
+
+--*/
+{
+  INT32 i, j, k, Avail;
+
+  //
+  // make tree, calculate len[], return root
+  //
+
+  mN = NParm;
+  mFreq = FreqParm;
+  mLen = LenParm;
+  Avail = mN;
+  mHeapSize = 0;
+  mHeap[1] = 0;
+  for (i = 0; i < mN; i++) {
+    mLen[i] = 0;
+    if (mFreq[i]) {
+      mHeap[++mHeapSize] = (INT16)i;
+    }
+  }
+  if (mHeapSize < 2) {
+    CodeParm[mHeap[1]] = 0;
+    return mHeap[1];
+  }
+  for (i = mHeapSize / 2; i >= 1; i--) {
+
+    //
+    // make priority queue
+    //
+    DownHeap(i);
+  }
+  mSortPtr = CodeParm;
+  do {
+    i = mHeap[1];
+    if (i < mN) {
+      *mSortPtr++ = (UINT16)i;
+    }
+    mHeap[1] = mHeap[mHeapSize--];
+    DownHeap(1);
+    j = mHeap[1];
+    if (j < mN) {
+      *mSortPtr++ = (UINT16)j;
+    }
+    k = Avail++;
+    mFreq[k] = (UINT16)(mFreq[i] + mFreq[j]);
+    mHeap[1] = (INT16)k;
+    DownHeap(1);
+    mLeft[k] = (UINT16)i;
+    mRight[k] = (UINT16)j;
+  } while (mHeapSize > 1);
+
+  mSortPtr = CodeParm;
+  MakeLen(k);
+  MakeCode(NParm, LenParm, CodeParm);
+
+  //
+  // return root
+  //
+  return k;
+}