--- /dev/null
+/*++\r
+\r
+Copyright (c) 2004, Intel Corporation \r
+All rights reserved. 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
+Module Name:\r
+\r
+ EfiCompress.c\r
+\r
+Abstract:\r
+\r
+ Compression routine. The compression algorithm is a mixture of\r
+ LZ77 and Huffman coding. LZ77 transforms the source data into a\r
+ sequence of Original Characters and Pointers to repeated strings.\r
+ This sequence is further divided into Blocks and Huffman codings\r
+ are applied to each Block.\r
+\r
+--*/\r
+\r
+#include "EfiCompress.h"\r
+\r
+//\r
+// Macro Definitions\r
+//\r
+typedef INT32 NODE;\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
+STATIC VOID PutDword(IN UINT32 Data);\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], mCTable[4096], 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
+Compress (\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
+ EFI_OUT_OF_RESOURCES - No resource to complete function.\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
+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
+ 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
+\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
+ 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
projects / mirror_edk2.git / blobdiff