+++ /dev/null
-/*++\r
-\r
-Copyright (c) 2006, 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
- TianoCompress.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 "Compress.h"\r
-\r
-//\r
-// Macro Definitions\r
-//\r
-typedef INT32 NODE;\r
-#define UINT8_MAX 0xff\r
-#define UINT8_BIT 8\r
-#define THRESHOLD 3\r
-#define INIT_CRC 0\r
-#define WNDBIT 19\r
-#define WNDSIZ (1U << WNDBIT)\r
-#define MAXMATCH 256\r
-#define BLKSIZ (1U << 14) // 16 * 1024U\r
-#define PERC_FLAG 0x80000000U\r
-#define CODE_BIT 16\r
-#define NIL 0\r
-#define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)\r
-#define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)\r
-#define CRCPOLY 0xA001\r
-#define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)\r
-\r
-//\r
-// C: the Char&Len Set; P: the Position Set; T: the exTra Set\r
-//\r
-#define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)\r
-#define CBIT 9\r
-#define NP (WNDBIT + 1)\r
-#define PBIT 5\r
-#define NT (CODE_BIT + 3)\r
-#define TBIT 5\r
-#if NT > NP\r
-#define NPT NT\r
-#else\r
-#define NPT NP\r
-#endif\r
-//\r
-// Function Prototypes\r
-//\r
-\r
-STATIC\r
-VOID\r
-PutDword(\r
- IN UINT32 Data\r
- );\r
-\r
-STATIC\r
-EFI_STATUS\r
-AllocateMemory (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-FreeMemory (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-InitSlide (\r
- VOID\r
- );\r
-\r
-STATIC\r
-NODE\r
-Child (\r
- IN NODE NodeQ,\r
- IN UINT8 CharC\r
- );\r
-\r
-STATIC\r
-VOID\r
-MakeChild (\r
- IN NODE NodeQ,\r
- IN UINT8 CharC,\r
- IN NODE NodeR\r
- );\r
-\r
-STATIC\r
-VOID\r
-Split (\r
- IN NODE Old\r
- );\r
-\r
-STATIC\r
-VOID\r
-InsertNode (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-DeleteNode (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-GetNextMatch (\r
- VOID\r
- );\r
-\r
-STATIC\r
-EFI_STATUS\r
-Encode (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-CountTFreq (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-WritePTLen (\r
- IN INT32 Number,\r
- IN INT32 nbit,\r
- IN INT32 Special\r
- );\r
-\r
-STATIC\r
-VOID\r
-WriteCLen (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-EncodeC (\r
- IN INT32 Value\r
- );\r
-\r
-STATIC\r
-VOID\r
-EncodeP (\r
- IN UINT32 Value\r
- );\r
-\r
-STATIC\r
-VOID\r
-SendBlock (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-Output (\r
- IN UINT32 c,\r
- IN UINT32 p\r
- );\r
-\r
-STATIC\r
-VOID\r
-HufEncodeStart (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-HufEncodeEnd (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-MakeCrcTable (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-PutBits (\r
- IN INT32 Number,\r
- IN UINT32 Value\r
- );\r
-\r
-STATIC\r
-INT32\r
-FreadCrc (\r
- OUT UINT8 *Pointer,\r
- IN INT32 Number\r
- );\r
-\r
-STATIC\r
-VOID\r
-InitPutBits (\r
- VOID\r
- );\r
-\r
-STATIC\r
-VOID\r
-CountLen (\r
- IN INT32 Index\r
- );\r
-\r
-STATIC\r
-VOID\r
-MakeLen (\r
- IN INT32 Root\r
- );\r
-\r
-STATIC\r
-VOID\r
-DownHeap (\r
- IN INT32 Index\r
- );\r
-\r
-STATIC\r
-VOID\r
-MakeCode (\r
- IN INT32 Number,\r
- IN UINT8 Len[ ],\r
- OUT UINT16 Code[]\r
- );\r
-\r
-STATIC\r
-INT32\r
-MakeTree (\r
- IN INT32 NParm,\r
- IN UINT16 FreqParm[],\r
- OUT UINT8 LenParm[ ],\r
- OUT UINT16 CodeParm[]\r
- );\r
-\r
-//\r
-// Global Variables\r
-//\r
-STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;\r
-\r
-STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;\r
-STATIC INT16 mHeap[NC + 1];\r
-STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;\r
-STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;\r
-STATIC UINT32 mCompSize, mOrigSize;\r
-\r
-STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],\r
- mCFreq[2 * NC - 1], 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
-TianoCompress (\r
- IN UINT8 *SrcBuffer,\r
- IN UINT32 SrcSize,\r
- IN UINT8 *DstBuffer,\r
- IN OUT UINT32 *DstSize\r
- )\r
-/*++\r
-\r
-Routine Description:\r
-\r
- The internal implementation of [Efi/Tiano]Compress().\r
-\r
-Arguments:\r
-\r
- SrcBuffer - The buffer storing the source data\r
- SrcSize - The size of source data\r
- DstBuffer - The buffer to store the compressed data\r
- DstSize - On input, the size of DstBuffer; On output,\r
- the size of the actual compressed data.\r
- Version - The version of de/compression algorithm.\r
- Version 1 for EFI 1.1 de/compression algorithm.\r
- Version 2 for Tiano de/compression algorithm.\r
-\r
-Returns:\r
-\r
- EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,\r
- DstSize contains the size needed.\r
- EFI_SUCCESS - Compression is successful.\r
- EFI_OUT_OF_RESOURCES - No resource to complete function.\r
- EFI_INVALID_PARAMETER - Parameter supplied is wrong.\r
-\r
---*/\r
-{\r
- EFI_STATUS Status;\r
-\r
- //\r
- // Initializations\r
- //\r
- mBufSiz = 0;\r
- mBuf = NULL;\r
- mText = NULL;\r
- mLevel = NULL;\r
- mChildCount = NULL;\r
- mPosition = NULL;\r
- mParent = NULL;\r
- mPrev = NULL;\r
- mNext = NULL;\r
-\r
- mSrc = SrcBuffer;\r
- mSrcUpperLimit = mSrc + SrcSize;\r
- mDst = DstBuffer;\r
- mDstUpperLimit = mDst +*DstSize;\r
-\r
- PutDword (0L);\r
- PutDword (0L);\r
-\r
- MakeCrcTable ();\r
-\r
- mOrigSize = mCompSize = 0;\r
- mCrc = INIT_CRC;\r
-\r
- //\r
- // Compress it\r
- //\r
- Status = Encode ();\r
- if (EFI_ERROR (Status)) {\r
- return EFI_OUT_OF_RESOURCES;\r
- }\r
- //\r
- // Null terminate the compressed data\r
- //\r
- if (mDst < mDstUpperLimit) {\r
- *mDst++ = 0;\r
- }\r
- //\r
- // Fill in compressed size and original size\r
- //\r
- mDst = DstBuffer;\r
- PutDword (mCompSize + 1);\r
- PutDword (mOrigSize);\r
-\r
- //\r
- // Return\r
- //\r
- if (mCompSize + 1 + 8 > *DstSize) {\r
- *DstSize = mCompSize + 1 + 8;\r
- return EFI_BUFFER_TOO_SMALL;\r
- } else {\r
- *DstSize = mCompSize + 1 + 8;\r
- return EFI_SUCCESS;\r
- }\r
-\r
-}\r
-\r
-STATIC\r
-VOID\r
-PutDword (\r
- IN UINT32 Data\r
- )\r
-/*++\r
-\r
-Routine Description:\r
-\r
- Put a dword to output stream\r
- \r
-Arguments:\r
-\r
- Data - the dword to put\r
- \r
-Returns: (VOID)\r
- \r
---*/\r
-{\r
- if (mDst < mDstUpperLimit) {\r
- *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);\r
- }\r
-\r
- if (mDst < mDstUpperLimit) {\r
- *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);\r
- }\r
-\r
- if (mDst < mDstUpperLimit) {\r
- *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);\r
- }\r
-\r
- if (mDst < mDstUpperLimit) {\r
- *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);\r
- }\r
-}\r
-\r
-STATIC\r
-EFI_STATUS\r
-AllocateMemory (\r
- VOID\r
- )\r
-/*++\r
-\r
-Routine Description:\r
-\r
- Allocate memory spaces for data structures used in compression process\r
- \r
-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