+++ /dev/null
-/*\r
-\r
-Copyright (c) 2006, Intel Corporation. All rights reserved.<BR>\r
-This program and the accompanying materials \r
-are licensed and made available under the terms and conditions of the BSD License \r
-which accompanies this distribution. The full text of the license may be found at \r
-http://opensource.org/licenses/bsd-license.php \r
- \r
-THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, \r
-WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED. \r
-\r
-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 <stdlib.h>\r
-#include <string.h>\r
-#include "TianoCommon.h"\r
-#include "Compress.h"\r
-\r
-\r
-//\r
-// Macro Definitions\r
-//\r
-\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], mCTable[4096], 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
-Argements: (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
- 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
- \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. 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
- \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
-Argments:\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
projects / mirror_edk2.git / blobdiff