diff options
Diffstat (limited to 'Platform/Intel/MinPlatformPkg/Library/CompressLib/CompressLib.c')
| -rw-r--r-- | Platform/Intel/MinPlatformPkg/Library/CompressLib/CompressLib.c | 1426 |
1 files changed, 1426 insertions, 0 deletions
diff --git a/Platform/Intel/MinPlatformPkg/Library/CompressLib/CompressLib.c b/Platform/Intel/MinPlatformPkg/Library/CompressLib/CompressLib.c new file mode 100644 index 0000000000..52ce2cde15 --- /dev/null +++ b/Platform/Intel/MinPlatformPkg/Library/CompressLib/CompressLib.c @@ -0,0 +1,1426 @@ +/** @file
+ Main file for compression routine.
+
+ 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.
+
+ Copyright (c) 2007 - 2014, Intel Corporation. All rights reserved.<BR>
+ 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.
+
+**/
+
+#include <Library/MemoryAllocationLib.h>
+#include <Library/BaseMemoryLib.h>
+#include <Library/DebugLib.h>
+#include <Uefi/UefiBaseType.h>
+
+#define SHELL_FREE_NON_NULL(Pointer) \
+ do { \
+ if ((Pointer) != NULL) { \
+ FreePool((Pointer)); \
+ (Pointer) = NULL; \
+ } \
+ } while(FALSE)
+
+
+
+//
+// Macro Definitions
+//
+typedef INT16 NODE;
+#define UINT8_MAX 0xff
+#define UINT8_BIT 8
+#define THRESHOLD 3
+#define INIT_CRC 0
+#define WNDBIT 13
+#define WNDSIZ (1U << WNDBIT)
+#define MAXMATCH 256
+#define BLKSIZ (1U << 14) // 16 * 1024U
+#define PERC_FLAG 0x8000U
+#define CODE_BIT 16
+#define NIL 0
+#define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
+#define HASH(LoopVar7, LoopVar5) ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)
+#define CRCPOLY 0xA001
+#define UPDATE_CRC(LoopVar5) mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 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
+//
+
+/**
+ Put a dword to output stream
+
+ @param[in] Data The dword to put.
+**/
+VOID
+EFIAPI
+PutDword(
+ IN UINT32 Data
+ );
+
+//
+// Global Variables
+//
+STATIC UINT8 *mSrc;
+STATIC UINT8 *mDst;
+STATIC UINT8 *mSrcUpperLimit;
+STATIC UINT8 *mDstUpperLimit;
+
+STATIC UINT8 *mLevel;
+STATIC UINT8 *mText;
+STATIC UINT8 *mChildCount;
+STATIC UINT8 *mBuf;
+STATIC UINT8 mCLen[NC];
+STATIC UINT8 mPTLen[NPT];
+STATIC UINT8 *mLen;
+STATIC INT16 mHeap[NC + 1];
+STATIC INT32 mRemainder;
+STATIC INT32 mMatchLen;
+STATIC INT32 mBitCount;
+STATIC INT32 mHeapSize;
+STATIC INT32 mTempInt32;
+STATIC UINT32 mBufSiz = 0;
+STATIC UINT32 mOutputPos;
+STATIC UINT32 mOutputMask;
+STATIC UINT32 mSubBitBuf;
+STATIC UINT32 mCrc;
+STATIC UINT32 mCompSize;
+STATIC UINT32 mOrigSize;
+
+STATIC UINT16 *mFreq;
+STATIC UINT16 *mSortPtr;
+STATIC UINT16 mLenCnt[17];
+STATIC UINT16 mLeft[2 * NC - 1];
+STATIC UINT16 mRight[2 * NC - 1];
+STATIC UINT16 mCrcTable[UINT8_MAX + 1];
+STATIC UINT16 mCFreq[2 * NC - 1];
+STATIC UINT16 mCCode[NC];
+STATIC UINT16 mPFreq[2 * NP - 1];
+STATIC UINT16 mPTCode[NPT];
+STATIC UINT16 mTFreq[2 * NT - 1];
+
+STATIC NODE mPos;
+STATIC NODE mMatchPos;
+STATIC NODE mAvail;
+STATIC NODE *mPosition;
+STATIC NODE *mParent;
+STATIC NODE *mPrev;
+STATIC NODE *mNext = NULL;
+INT32 mHuffmanDepth = 0;
+
+/**
+ Make a CRC table.
+
+**/
+VOID
+EFIAPI
+MakeCrcTable (
+ VOID
+ )
+{
+ UINT32 LoopVar1;
+
+ UINT32 LoopVar2;
+
+ UINT32 LoopVar4;
+
+ for (LoopVar1 = 0; LoopVar1 <= UINT8_MAX; LoopVar1++) {
+ LoopVar4 = LoopVar1;
+ for (LoopVar2 = 0; LoopVar2 < UINT8_BIT; LoopVar2++) {
+ if ((LoopVar4 & 1) != 0) {
+ LoopVar4 = (LoopVar4 >> 1) ^ CRCPOLY;
+ } else {
+ LoopVar4 >>= 1;
+ }
+ }
+
+ mCrcTable[LoopVar1] = (UINT16) LoopVar4;
+ }
+}
+
+/**
+ Put a dword to output stream
+
+ @param[in] Data The dword to put.
+**/
+VOID
+EFIAPI
+PutDword (
+ IN UINT32 Data
+ )
+{
+ 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);
+ }
+}
+
+/**
+ Allocate memory spaces for data structures used in compression process.
+
+ @retval EFI_SUCCESS Memory was allocated successfully.
+ @retval EFI_OUT_OF_RESOURCES A memory allocation failed.
+**/
+EFI_STATUS
+EFIAPI
+AllocateMemory (
+ VOID
+ )
+{
+ mText = AllocateZeroPool (WNDSIZ * 2 + MAXMATCH);
+ mLevel = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
+ mChildCount = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
+ mPosition = AllocateZeroPool ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
+ mParent = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mParent));
+ mPrev = AllocateZeroPool (WNDSIZ * 2 * sizeof (*mPrev));
+ mNext = AllocateZeroPool ((MAX_HASH_VAL + 1) * sizeof (*mNext));
+
+ mBufSiz = BLKSIZ;
+ mBuf = AllocateZeroPool (mBufSiz);
+ while (mBuf == NULL) {
+ mBufSiz = (mBufSiz / 10U) * 9U;
+ if (mBufSiz < 4 * 1024U) {
+ return EFI_OUT_OF_RESOURCES;
+ }
+
+ mBuf = AllocateZeroPool (mBufSiz);
+ }
+
+ mBuf[0] = 0;
+
+ return EFI_SUCCESS;
+}
+
+/**
+ Called when compression is completed to free memory previously allocated.
+
+**/
+VOID
+EFIAPI
+FreeMemory (
+ VOID
+ )
+{
+ SHELL_FREE_NON_NULL (mText);
+ SHELL_FREE_NON_NULL (mLevel);
+ SHELL_FREE_NON_NULL (mChildCount);
+ SHELL_FREE_NON_NULL (mPosition);
+ SHELL_FREE_NON_NULL (mParent);
+ SHELL_FREE_NON_NULL (mPrev);
+ SHELL_FREE_NON_NULL (mNext);
+ SHELL_FREE_NON_NULL (mBuf);
+}
+
+/**
+ Initialize String Info Log data structures.
+**/
+VOID
+EFIAPI
+InitSlide (
+ VOID
+ )
+{
+ NODE LoopVar1;
+
+ SetMem (mLevel + WNDSIZ, (UINT8_MAX + 1) * sizeof (UINT8), 1);
+ SetMem (mPosition + WNDSIZ, (UINT8_MAX + 1) * sizeof (NODE), 0);
+
+ SetMem (mParent + WNDSIZ, WNDSIZ * sizeof (NODE), 0);
+
+ mAvail = 1;
+ for (LoopVar1 = 1; LoopVar1 < WNDSIZ - 1; LoopVar1++) {
+ mNext[LoopVar1] = (NODE) (LoopVar1 + 1);
+ }
+
+ mNext[WNDSIZ - 1] = NIL;
+ SetMem (mNext + WNDSIZ * 2, (MAX_HASH_VAL - WNDSIZ * 2 + 1) * sizeof (NODE), 0);
+}
+
+/**
+ Find child node given the parent node and the edge character
+
+ @param[in] LoopVar6 The parent node.
+ @param[in] LoopVar5 The edge character.
+
+ @return The child node.
+ @retval NIL(Zero) No child could be found.
+
+**/
+NODE
+EFIAPI
+Child (
+ IN NODE LoopVar6,
+ IN UINT8 LoopVar5
+ )
+{
+ NODE LoopVar4;
+
+ LoopVar4 = mNext[HASH (LoopVar6, LoopVar5)];
+ mParent[NIL] = LoopVar6; /* sentinel */
+ while (mParent[LoopVar4] != LoopVar6) {
+ LoopVar4 = mNext[LoopVar4];
+ }
+
+ return LoopVar4;
+}
+
+/**
+ Create a new child for a given parent node.
+
+ @param[in] LoopVar6 The parent node.
+ @param[in] LoopVar5 The edge character.
+ @param[in] LoopVar4 The child node.
+**/
+VOID
+EFIAPI
+MakeChild (
+ IN NODE LoopVar6,
+ IN UINT8 LoopVar5,
+ IN NODE LoopVar4
+ )
+{
+ NODE LoopVar12;
+
+ NODE LoopVar10;
+
+ LoopVar12 = (NODE) HASH (LoopVar6, LoopVar5);
+ LoopVar10 = mNext[LoopVar12];
+ mNext[LoopVar12] = LoopVar4;
+ mNext[LoopVar4] = LoopVar10;
+ mPrev[LoopVar10] = LoopVar4;
+ mPrev[LoopVar4] = LoopVar12;
+ mParent[LoopVar4] = LoopVar6;
+ mChildCount[LoopVar6]++;
+}
+
+/**
+ Split a node.
+
+ @param[in] Old The node to split.
+**/
+VOID
+EFIAPI
+Split (
+ IN NODE Old
+ )
+{
+ NODE New;
+
+ NODE LoopVar10;
+
+ New = mAvail;
+ mAvail = mNext[New];
+ mChildCount[New] = 0;
+ LoopVar10 = mPrev[Old];
+ mPrev[New] = LoopVar10;
+ mNext[LoopVar10] = New;
+ LoopVar10 = mNext[Old];
+ mNext[New] = LoopVar10;
+ mPrev[LoopVar10] = New;
+ mParent[New] = mParent[Old];
+ mLevel[New] = (UINT8) mMatchLen;
+ mPosition[New] = mPos;
+ MakeChild (New, mText[mMatchPos + mMatchLen], Old);
+ MakeChild (New, mText[mPos + mMatchLen], mPos);
+}
+
+/**
+ Insert string info for current position into the String Info Log.
+
+**/
+VOID
+EFIAPI
+InsertNode (
+ VOID
+ )
+{
+ NODE LoopVar6;
+
+ NODE LoopVar4;
+
+ NODE LoopVar2;
+
+ NODE LoopVar10;
+ UINT8 LoopVar5;
+ UINT8 *TempString3;
+ UINT8 *TempString2;
+
+ 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--;
+ LoopVar4 = (NODE) ((mMatchPos + 1) | WNDSIZ);
+ LoopVar6 = mParent[LoopVar4];
+ while (LoopVar6 == NIL) {
+ LoopVar4 = mNext[LoopVar4];
+ LoopVar6 = mParent[LoopVar4];
+ }
+
+ while (mLevel[LoopVar6] >= mMatchLen) {
+ LoopVar4 = LoopVar6;
+ LoopVar6 = mParent[LoopVar6];
+ }
+
+ LoopVar10 = LoopVar6;
+ while (mPosition[LoopVar10] < 0) {
+ mPosition[LoopVar10] = mPos;
+ LoopVar10 = mParent[LoopVar10];
+ }
+
+ if (LoopVar10 < WNDSIZ) {
+ mPosition[LoopVar10] = (NODE) (mPos | PERC_FLAG);
+ }
+ } else {
+ //
+ // Locate the target tree
+ //
+ LoopVar6 = (NODE) (mText[mPos] + WNDSIZ);
+ LoopVar5 = mText[mPos + 1];
+ LoopVar4 = Child (LoopVar6, LoopVar5);
+ if (LoopVar4 == NIL) {
+ MakeChild (LoopVar6, LoopVar5, 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 (LoopVar4 >= WNDSIZ) {
+ LoopVar2 = MAXMATCH;
+ mMatchPos = LoopVar4;
+ } else {
+ LoopVar2 = mLevel[LoopVar4];
+ mMatchPos = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
+ }
+
+ if (mMatchPos >= mPos) {
+ mMatchPos -= WNDSIZ;
+ }
+
+ TempString3 = &mText[mPos + mMatchLen];
+ TempString2 = &mText[mMatchPos + mMatchLen];
+ while (mMatchLen < LoopVar2) {
+ if (*TempString3 != *TempString2) {
+ Split (LoopVar4);
+ return ;
+ }
+
+ mMatchLen++;
+ TempString3++;
+ TempString2++;
+ }
+
+ if (mMatchLen >= MAXMATCH) {
+ break;
+ }
+
+ mPosition[LoopVar4] = mPos;
+ LoopVar6 = LoopVar4;
+ LoopVar4 = Child (LoopVar6, *TempString3);
+ if (LoopVar4 == NIL) {
+ MakeChild (LoopVar6, *TempString3, mPos);
+ return ;
+ }
+
+ mMatchLen++;
+ }
+
+ LoopVar10 = mPrev[LoopVar4];
+ mPrev[mPos] = LoopVar10;
+ mNext[LoopVar10] = mPos;
+ LoopVar10 = mNext[LoopVar4];
+ mNext[mPos] = LoopVar10;
+ mPrev[LoopVar10] = mPos;
+ mParent[mPos] = LoopVar6;
+ mParent[LoopVar4] = NIL;
+
+ //
+ // Special usage of 'next'
+ //
+ mNext[LoopVar4] = mPos;
+
+}
+
+/**
+ Delete outdated string info. (The Usage of PERC_FLAG
+ ensures a clean deletion).
+
+**/
+VOID
+EFIAPI
+DeleteNode (
+ VOID
+ )
+{
+ NODE LoopVar6;
+
+ NODE LoopVar4;
+
+ NODE LoopVar11;
+
+ NODE LoopVar10;
+
+ NODE LoopVar9;
+
+ if (mParent[mPos] == NIL) {
+ return ;
+ }
+
+ LoopVar4 = mPrev[mPos];
+ LoopVar11 = mNext[mPos];
+ mNext[LoopVar4] = LoopVar11;
+ mPrev[LoopVar11] = LoopVar4;
+ LoopVar4 = mParent[mPos];
+ mParent[mPos] = NIL;
+ if (LoopVar4 >= WNDSIZ) {
+ return ;
+ }
+
+ mChildCount[LoopVar4]--;
+ if (mChildCount[LoopVar4] > 1) {
+ return ;
+ }
+
+ LoopVar10 = (NODE) (mPosition[LoopVar4] & ~PERC_FLAG);
+ if (LoopVar10 >= mPos) {
+ LoopVar10 -= WNDSIZ;
+ }
+
+ LoopVar11 = LoopVar10;
+ LoopVar6 = mParent[LoopVar4];
+ LoopVar9 = mPosition[LoopVar6];
+ while ((LoopVar9 & PERC_FLAG) != 0){
+ LoopVar9 &= ~PERC_FLAG;
+ if (LoopVar9 >= mPos) {
+ LoopVar9 -= WNDSIZ;
+ }
+
+ if (LoopVar9 > LoopVar11) {
+ LoopVar11 = LoopVar9;
+ }
+
+ mPosition[LoopVar6] = (NODE) (LoopVar11 | WNDSIZ);
+ LoopVar6 = mParent[LoopVar6];
+ LoopVar9 = mPosition[LoopVar6];
+ }
+
+ if (LoopVar6 < WNDSIZ) {
+ if (LoopVar9 >= mPos) {
+ LoopVar9 -= WNDSIZ;
+ }
+
+ if (LoopVar9 > LoopVar11) {
+ LoopVar11 = LoopVar9;
+ }
+
+ mPosition[LoopVar6] = (NODE) (LoopVar11 | WNDSIZ | PERC_FLAG);
+ }
+
+ LoopVar11 = Child (LoopVar4, mText[LoopVar10 + mLevel[LoopVar4]]);
+ LoopVar10 = mPrev[LoopVar11];
+ LoopVar9 = mNext[LoopVar11];
+ mNext[LoopVar10] = LoopVar9;
+ mPrev[LoopVar9] = LoopVar10;
+ LoopVar10 = mPrev[LoopVar4];
+ mNext[LoopVar10] = LoopVar11;
+ mPrev[LoopVar11] = LoopVar10;
+ LoopVar10 = mNext[LoopVar4];
+ mPrev[LoopVar10] = LoopVar11;
+ mNext[LoopVar11] = LoopVar10;
+ mParent[LoopVar11] = mParent[LoopVar4];
+ mParent[LoopVar4] = NIL;
+ mNext[LoopVar4] = mAvail;
+ mAvail = LoopVar4;
+}
+
+/**
+ Read in source data
+
+ @param[out] LoopVar7 The buffer to hold the data.
+ @param[in] LoopVar8 The number of bytes to read.
+
+ @return The number of bytes actually read.
+**/
+INT32
+EFIAPI
+FreadCrc (
+ OUT UINT8 *LoopVar7,
+ IN INT32 LoopVar8
+ )
+{
+ INT32 LoopVar1;
+
+ for (LoopVar1 = 0; mSrc < mSrcUpperLimit && LoopVar1 < LoopVar8; LoopVar1++) {
+ *LoopVar7++ = *mSrc++;
+ }
+
+ LoopVar8 = LoopVar1;
+
+ LoopVar7 -= LoopVar8;
+ mOrigSize += LoopVar8;
+ LoopVar1--;
+ while (LoopVar1 >= 0) {
+ UPDATE_CRC (*LoopVar7++);
+ LoopVar1--;
+ }
+
+ return LoopVar8;
+}
+
+/**
+ Advance the current position (read in new data if needed).
+ Delete outdated string info. Find a match string for current position.
+
+ @retval TRUE The operation was successful.
+ @retval FALSE The operation failed due to insufficient memory.
+**/
+BOOLEAN
+EFIAPI
+GetNextMatch (
+ VOID
+ )
+{
+ INT32 LoopVar8;
+ VOID *Temp;
+
+ mRemainder--;
+ mPos++;
+ if (mPos == WNDSIZ * 2) {
+ Temp = AllocateZeroPool (WNDSIZ + MAXMATCH);
+ if (Temp == NULL) {
+ return (FALSE);
+ }
+ CopyMem (Temp, &mText[WNDSIZ], WNDSIZ + MAXMATCH);
+ CopyMem (&mText[0], Temp, WNDSIZ + MAXMATCH);
+ FreePool (Temp);
+ LoopVar8 = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
+ mRemainder += LoopVar8;
+ mPos = WNDSIZ;
+ }
+
+ DeleteNode ();
+ InsertNode ();
+
+ return (TRUE);
+}
+
+/**
+ Send entry LoopVar1 down the queue.
+
+ @param[in] LoopVar1 The index of the item to move.
+**/
+VOID
+EFIAPI
+DownHeap (
+ IN INT32 i
+ )
+{
+ INT32 LoopVar1;
+
+ INT32 LoopVar2;
+
+ //
+ // priority queue: send i-th entry down heap
+ //
+ LoopVar2 = mHeap[i];
+ LoopVar1 = 2 * i;
+ while (LoopVar1 <= mHeapSize) {
+ if (LoopVar1 < mHeapSize && mFreq[mHeap[LoopVar1]] > mFreq[mHeap[LoopVar1 + 1]]) {
+ LoopVar1++;
+ }
+
+ if (mFreq[LoopVar2] <= mFreq[mHeap[LoopVar1]]) {
+ break;
+ }
+
+ mHeap[i] = mHeap[LoopVar1];
+ i = LoopVar1;
+ LoopVar1 = 2 * i;
+ }
+
+ mHeap[i] = (INT16) LoopVar2;
+}
+
+/**
+ Count the number of each code length for a Huffman tree.
+
+ @param[in] LoopVar1 The top node.
+**/
+VOID
+EFIAPI
+CountLen (
+ IN INT32 LoopVar1
+ )
+{
+ if (LoopVar1 < mTempInt32) {
+ mLenCnt[(mHuffmanDepth < 16) ? mHuffmanDepth : 16]++;
+ } else {
+ mHuffmanDepth++;
+ CountLen (mLeft[LoopVar1]);
+ CountLen (mRight[LoopVar1]);
+ mHuffmanDepth--;
+ }
+}
+
+/**
+ Create code length array for a Huffman tree.
+
+ @param[in] Root The root of the tree.
+**/
+VOID
+EFIAPI
+MakeLen (
+ IN INT32 Root
+ )
+{
+ INT32 LoopVar1;
+
+ INT32 LoopVar2;
+ UINT32 Cum;
+
+ for (LoopVar1 = 0; LoopVar1 <= 16; LoopVar1++) {
+ mLenCnt[LoopVar1] = 0;
+ }
+
+ CountLen (Root);
+
+ //
+ // Adjust the length count array so that
+ // no code will be generated longer than its designated length
+ //
+ Cum = 0;
+ for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
+ Cum += mLenCnt[LoopVar1] << (16 - LoopVar1);
+ }
+
+ while (Cum != (1U << 16)) {
+ mLenCnt[16]--;
+ for (LoopVar1 = 15; LoopVar1 > 0; LoopVar1--) {
+ if (mLenCnt[LoopVar1] != 0) {
+ mLenCnt[LoopVar1]--;
+ mLenCnt[LoopVar1 + 1] += 2;
+ break;
+ }
+ }
+
+ Cum--;
+ }
+
+ for (LoopVar1 = 16; LoopVar1 > 0; LoopVar1--) {
+ LoopVar2 = mLenCnt[LoopVar1];
+ LoopVar2--;
+ while (LoopVar2 >= 0) {
+ mLen[*mSortPtr++] = (UINT8) LoopVar1;
+ LoopVar2--;
+ }
+ }
+}
+
+/**
+ Assign code to each symbol based on the code length array.
+
+ @param[in] LoopVar8 The number of symbols.
+ @param[in] Len The code length array.
+ @param[out] Code The stores codes for each symbol.
+**/
+VOID
+EFIAPI
+MakeCode (
+ IN INT32 LoopVar8,
+ IN UINT8 Len[ ],
+ OUT UINT16 Code[ ]
+ )
+{
+ INT32 LoopVar1;
+ UINT16 Start[18];
+
+ Start[1] = 0;
+ for (LoopVar1 = 1; LoopVar1 <= 16; LoopVar1++) {
+ Start[LoopVar1 + 1] = (UINT16) ((Start[LoopVar1] + mLenCnt[LoopVar1]) << 1);
+ }
+
+ for (LoopVar1 = 0; LoopVar1 < LoopVar8; LoopVar1++) {
+ Code[LoopVar1] = Start[Len[LoopVar1]]++;
+ }
+}
+
+/**
+ Generates Huffman codes given a frequency distribution of symbols.
+
+ @param[in] NParm The number of symbols.
+ @param[in] FreqParm The frequency of each symbol.
+ @param[out] LenParm The code length for each symbol.
+ @param[out] CodeParm The code for each symbol.
+
+ @return The root of the Huffman tree.
+**/
+INT32
+EFIAPI
+MakeTree (
+ IN INT32 NParm,
+ IN UINT16 FreqParm[ ],
+ OUT UINT8 LenParm[ ],
+ OUT UINT16 CodeParm[ ]
+ )
+{
+ INT32 LoopVar1;
+
+ INT32 LoopVar2;
+
+ INT32 LoopVar3;
+
+ INT32 Avail;
+
+ //
+ // make tree, calculate len[], return root
+ //
+ mTempInt32 = NParm;
+ mFreq = FreqParm;
+ mLen = LenParm;
+ Avail = mTempInt32;
+ mHeapSize = 0;
+ mHeap[1] = 0;
+ for (LoopVar1 = 0; LoopVar1 < mTempInt32; LoopVar1++) {
+ mLen[LoopVar1] = 0;
+ if ((mFreq[LoopVar1]) != 0) {
+ mHeapSize++;
+ mHeap[mHeapSize] = (INT16) LoopVar1;
+ }
+ }
+
+ if (mHeapSize < 2) {
+ CodeParm[mHeap[1]] = 0;
+ return mHeap[1];
+ }
+
+ for (LoopVar1 = mHeapSize / 2; LoopVar1 >= 1; LoopVar1--) {
+ //
+ // make priority queue
+ //
+ DownHeap (LoopVar1);
+ }
+
+ mSortPtr = CodeParm;
+ do {
+ LoopVar1 = mHeap[1];
+ if (LoopVar1 < mTempInt32) {
+ *mSortPtr++ = (UINT16) LoopVar1;
+ }
+
+ mHeap[1] = mHeap[mHeapSize--];
+ DownHeap (1);
+ LoopVar2 = mHeap[1];
+ if (LoopVar2 < mTempInt32) {
+ *mSortPtr++ = (UINT16) LoopVar2;
+ }
+
+ LoopVar3 = Avail++;
+ mFreq[LoopVar3] = (UINT16) (mFreq[LoopVar1] + mFreq[LoopVar2]);
+ mHeap[1] = (INT16) LoopVar3;
+ DownHeap (1);
+ mLeft[LoopVar3] = (UINT16) LoopVar1;
+ mRight[LoopVar3] = (UINT16) LoopVar2;
+ } while (mHeapSize > 1);
+
+ mSortPtr = CodeParm;
+ MakeLen (LoopVar3);
+ MakeCode (NParm, LenParm, CodeParm);
+
+ //
+ // return root
+ //
+ return LoopVar3;
+}
+
+/**
+ Outputs rightmost LoopVar8 bits of x
+
+ @param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
+ @param[in] x The data.
+**/
+VOID
+EFIAPI
+PutBits (
+ IN INT32 LoopVar8,
+ IN UINT32 x
+ )
+{
+ UINT8 Temp;
+
+ if (LoopVar8 < mBitCount) {
+ mSubBitBuf |= x << (mBitCount -= LoopVar8);
+ } else {
+
+ Temp = (UINT8)(mSubBitBuf | (x >> (LoopVar8 -= mBitCount)));
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = Temp;
+ }
+ mCompSize++;
+
+ if (LoopVar8 < UINT8_BIT) {
+ mSubBitBuf = x << (mBitCount = UINT8_BIT - LoopVar8);
+ } else {
+
+ Temp = (UINT8)(x >> (LoopVar8 - UINT8_BIT));
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = Temp;
+ }
+ mCompSize++;
+
+ mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - LoopVar8);
+ }
+ }
+}
+
+/**
+ Encode a signed 32 bit number.
+
+ @param[in] LoopVar5 The number to encode.
+**/
+VOID
+EFIAPI
+EncodeC (
+ IN INT32 LoopVar5
+ )
+{
+ PutBits (mCLen[LoopVar5], mCCode[LoopVar5]);
+}
+
+/**
+ Encode a unsigned 32 bit number.
+
+ @param[in] LoopVar7 The number to encode.
+**/
+VOID
+EFIAPI
+EncodeP (
+ IN UINT32 LoopVar7
+ )
+{
+ UINT32 LoopVar5;
+
+ UINT32 LoopVar6;
+
+ LoopVar5 = 0;
+ LoopVar6 = LoopVar7;
+ while (LoopVar6 != 0) {
+ LoopVar6 >>= 1;
+ LoopVar5++;
+ }
+
+ PutBits (mPTLen[LoopVar5], mPTCode[LoopVar5]);
+ if (LoopVar5 > 1) {
+ PutBits(LoopVar5 - 1, LoopVar7 & (0xFFFFU >> (17 - LoopVar5)));
+ }
+}
+
+/**
+ Count the frequencies for the Extra Set.
+
+**/
+VOID
+EFIAPI
+CountTFreq (
+ VOID
+ )
+{
+ INT32 LoopVar1;
+
+ INT32 LoopVar3;
+
+ INT32 LoopVar8;
+
+ INT32 Count;
+
+ for (LoopVar1 = 0; LoopVar1 < NT; LoopVar1++) {
+ mTFreq[LoopVar1] = 0;
+ }
+
+ LoopVar8 = NC;
+ while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
+ LoopVar8--;
+ }
+
+ LoopVar1 = 0;
+ while (LoopVar1 < LoopVar8) {
+ LoopVar3 = mCLen[LoopVar1++];
+ if (LoopVar3 == 0) {
+ Count = 1;
+ while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
+ LoopVar1++;
+ 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 {
+ ASSERT((LoopVar3+2)<(2 * NT - 1));
+ mTFreq[LoopVar3 + 2]++;
+ }
+ }
+}
+
+/**
+ Outputs the code length array for the Extra Set or the Position Set.
+
+ @param[in] LoopVar8 The number of symbols.
+ @param[in] nbit The number of bits needed to represent 'LoopVar8'.
+ @param[in] Special The special symbol that needs to be take care of.
+
+**/
+VOID
+EFIAPI
+WritePTLen (
+ IN INT32 LoopVar8,
+ IN INT32 nbit,
+ IN INT32 Special
+ )
+{
+ INT32 LoopVar1;
+
+ INT32 LoopVar3;
+
+ while (LoopVar8 > 0 && mPTLen[LoopVar8 - 1] == 0) {
+ LoopVar8--;
+ }
+
+ PutBits (nbit, LoopVar8);
+ LoopVar1 = 0;
+ while (LoopVar1 < LoopVar8) {
+ LoopVar3 = mPTLen[LoopVar1++];
+ if (LoopVar3 <= 6) {
+ PutBits (3, LoopVar3);
+ } else {
+ PutBits (LoopVar3 - 3, (1U << (LoopVar3 - 3)) - 2);
+ }
+
+ if (LoopVar1 == Special) {
+ while (LoopVar1 < 6 && mPTLen[LoopVar1] == 0) {
+ LoopVar1++;
+ }
+
+ PutBits (2, (LoopVar1 - 3) & 3);
+ }
+ }
+}
+
+/**
+ Outputs the code length array for Char&Length Set.
+**/
+VOID
+EFIAPI
+WriteCLen (
+ VOID
+ )
+{
+ INT32 LoopVar1;
+
+ INT32 LoopVar3;
+
+ INT32 LoopVar8;
+
+ INT32 Count;
+
+ LoopVar8 = NC;
+ while (LoopVar8 > 0 && mCLen[LoopVar8 - 1] == 0) {
+ LoopVar8--;
+ }
+
+ PutBits (CBIT, LoopVar8);
+ LoopVar1 = 0;
+ while (LoopVar1 < LoopVar8) {
+ LoopVar3 = mCLen[LoopVar1++];
+ if (LoopVar3 == 0) {
+ Count = 1;
+ while (LoopVar1 < LoopVar8 && mCLen[LoopVar1] == 0) {
+ LoopVar1++;
+ Count++;
+ }
+
+ if (Count <= 2) {
+ for (LoopVar3 = 0; LoopVar3 < Count; LoopVar3++) {
+ 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 {
+ ASSERT((LoopVar3+2)<NPT);
+ PutBits (mPTLen[LoopVar3 + 2], mPTCode[LoopVar3 + 2]);
+ }
+ }
+}
+
+/**
+ Huffman code the block and output it.
+
+**/
+VOID
+EFIAPI
+SendBlock (
+ VOID
+ )
+{
+ UINT32 LoopVar1;
+
+ UINT32 LoopVar3;
+
+ UINT32 Flags;
+
+ UINT32 Root;
+
+ UINT32 Pos;
+
+ UINT32 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 (LoopVar1 = 0; LoopVar1 < Size; LoopVar1++) {
+ if (LoopVar1 % UINT8_BIT == 0) {
+ Flags = mBuf[Pos++];
+ } else {
+ Flags <<= 1;
+ }
+ if ((Flags & (1U << (UINT8_BIT - 1))) != 0){
+ EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
+ LoopVar3 = mBuf[Pos++] << UINT8_BIT;
+ LoopVar3 += mBuf[Pos++];
+
+ EncodeP (LoopVar3);
+ } else {
+ EncodeC (mBuf[Pos++]);
+ }
+ }
+
+ SetMem (mCFreq, NC * sizeof (UINT16), 0);
+ SetMem (mPFreq, NP * sizeof (UINT16), 0);
+}
+
+/**
+ Start the huffman encoding.
+
+**/
+VOID
+EFIAPI
+HufEncodeStart (
+ VOID
+ )
+{
+ SetMem (mCFreq, NC * sizeof (UINT16), 0);
+ SetMem (mPFreq, NP * sizeof (UINT16), 0);
+
+ mOutputPos = mOutputMask = 0;
+
+ mBitCount = UINT8_BIT;
+ mSubBitBuf = 0;
+}
+
+/**
+ Outputs an Original Character or a Pointer.
+
+ @param[in] LoopVar5 The original character or the 'String Length' element of
+ a Pointer.
+ @param[in] LoopVar7 The 'Position' field of a Pointer.
+**/
+VOID
+EFIAPI
+CompressOutput (
+ IN UINT32 LoopVar5,
+ IN UINT32 LoopVar7
+ )
+{
+ 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) LoopVar5;
+ mCFreq[LoopVar5]++;
+ if (LoopVar5 >= (1U << UINT8_BIT)) {
+ mBuf[CPos] = (UINT8)(mBuf[CPos]|mOutputMask);
+ mBuf[mOutputPos++] = (UINT8)(LoopVar7 >> UINT8_BIT);
+ mBuf[mOutputPos++] = (UINT8) LoopVar7;
+ LoopVar5 = 0;
+ while (LoopVar7!=0) {
+ LoopVar7 >>= 1;
+ LoopVar5++;
+ }
+ mPFreq[LoopVar5]++;
+ }
+}
+
+/**
+ End the huffman encoding.
+
+**/
+VOID
+EFIAPI
+HufEncodeEnd (
+ VOID
+ )
+{
+ SendBlock ();
+
+ //
+ // Flush remaining bits
+ //
+ PutBits (UINT8_BIT - 1, 0);
+}
+
+/**
+ The main controlling routine for compression process.
+
+ @retval EFI_SUCCESS The compression is successful.
+ @retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
+**/
+EFI_STATUS
+EFIAPI
+Encode (
+ VOID
+ )
+{
+ 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;
+ if (!GetNextMatch ()) {
+ Status = EFI_OUT_OF_RESOURCES;
+ }
+ 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
+ //
+ CompressOutput(mText[mPos - 1], 0);
+ } else {
+ //
+ // Outputting a pointer is beneficial enough, do it.
+ //
+
+ CompressOutput(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
+ (mPos - LastMatchPos - 2) & (WNDSIZ - 1));
+ LastMatchLen--;
+ while (LastMatchLen > 0) {
+ if (!GetNextMatch ()) {
+ Status = EFI_OUT_OF_RESOURCES;
+ }
+ LastMatchLen--;
+ }
+
+ if (mMatchLen > mRemainder) {
+ mMatchLen = mRemainder;
+ }
+ }
+ }
+
+ HufEncodeEnd ();
+ FreeMemory ();
+ return (Status);
+}
+
+/**
+ The compression routine.
+
+ @param[in] SrcBuffer The buffer containing the source data.
+ @param[in] SrcSize The number of bytes in SrcBuffer.
+ @param[in] DstBuffer The buffer to put the compressed image in.
+ @param[in, out] DstSize On input the size (in bytes) of DstBuffer, on
+ return the number of bytes placed in DstBuffer.
+
+ @retval EFI_SUCCESS The compression was sucessful.
+ @retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
+**/
+EFI_STATUS
+EFIAPI
+Compress (
+ IN VOID *SrcBuffer,
+ IN UINT64 SrcSize,
+ IN VOID *DstBuffer,
+ IN OUT UINT64 *DstSize
+ )
+{
+ EFI_STATUS Status;
+
+ //
+ // 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;
+ }
+
+}
+
|