diff options
Diffstat (limited to 'BaseTools/Source/C/TianoCompress/TianoCompress.c')
-rw-r--r-- | BaseTools/Source/C/TianoCompress/TianoCompress.c | 2719 |
1 files changed, 2719 insertions, 0 deletions
diff --git a/BaseTools/Source/C/TianoCompress/TianoCompress.c b/BaseTools/Source/C/TianoCompress/TianoCompress.c new file mode 100644 index 0000000000..b3ce640fde --- /dev/null +++ b/BaseTools/Source/C/TianoCompress/TianoCompress.c @@ -0,0 +1,2719 @@ +/** @file
+
+Copyright (c) 2007 - 2008, Intel Corporation
+All rights reserved. This program and the accompanying materials
+are licensed and made available under the terms and conditions of the BSD License
+which accompanies this distribution. The full text of the license may be found at
+http://opensource.org/licenses/bsd-license.php
+
+THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
+WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+
+Module Name:
+
+ TianoCompress.c
+
+Abstract:
+
+ Compression routine. The compression algorithm is a mixture of
+ LZ77 and Huffman coding. LZ77 transforms the source data into a
+ sequence of Original Characters and Pointers to repeated strings.
+ This sequence is further divided into Blocks and Huffman codings
+ are applied to each Block.
+
+**/
+
+#include "Compress.h"
+#include "TianoCompress.h"
+#include "EfiUtilityMsgs.h"
+#include "ParseInf.h"
+#include <stdio.h>
+#include "assert.h"
+
+//
+// Macro Definitions
+//
+static BOOLEAN VerboseMode = FALSE;
+static BOOLEAN QuietMode = FALSE;
+#undef UINT8_MAX
+#define UINT8_MAX 0xff
+#define UINT8_BIT 8
+#define THRESHOLD 3
+#define INIT_CRC 0
+#define WNDBIT 19
+#define WNDSIZ (1U << WNDBIT)
+#define MAXMATCH 256
+#define BLKSIZ (1U << 14) // 16 * 1024U
+#define PERC_FLAG 0x80000000U
+#define CODE_BIT 16
+#define NIL 0
+#define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
+#define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
+#define CRCPOLY 0xA001
+#define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
+
+//
+// C: the Char&Len Set; P: the Position Set; T: the exTra Set
+//
+//#define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)
+#define CBIT 9
+#define NP (WNDBIT + 1)
+#define PBIT 5
+//#define NT (CODE_BIT + 3)
+//#define TBIT 5
+//#if NT > NP
+//#define NPT NT
+//#else
+//#define NPT NP
+//#endif
+
+//
+// Global Variables
+//
+STATIC BOOLEAN ENCODE = FALSE;
+STATIC BOOLEAN DECODE = FALSE;
+STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
+STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
+STATIC INT16 mHeap[NC + 1];
+STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
+STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
+STATIC UINT32 mCompSize, mOrigSize;
+
+STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1], mCrcTable[UINT8_MAX + 1],
+ mCFreq[2 * NC - 1], mCCode[NC], mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
+
+STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
+
+static UINTN DebugLevel;
+static BOOLEAN DebugMode;
+//
+// functions
+//
+EFI_STATUS
+TianoCompress (
+ IN UINT8 *SrcBuffer,
+ IN UINT32 SrcSize,
+ IN UINT8 *DstBuffer,
+ IN OUT UINT32 *DstSize
+ )
+/*++
+
+Routine Description:
+
+ The internal implementation of [Efi/Tiano]Compress().
+
+Arguments:
+
+ SrcBuffer - The buffer storing the source data
+ SrcSize - The size of source data
+ DstBuffer - The buffer to store the compressed data
+
+ Version - The version of de/compression algorithm.
+ Version 1 for EFI 1.1 de/compression algorithm.
+ Version 2 for Tiano de/compression algorithm.
+
+Returns:
+
+ EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
+ DstSize contains the size needed.
+ EFI_SUCCESS - Compression is successful.
+ EFI_OUT_OF_RESOURCES - No resource to complete function.
+ EFI_INVALID_PARAMETER - Parameter supplied is wrong.
+
+--*/
+{
+ 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;
+ }
+ return EFI_SUCCESS;
+}
+
+STATIC
+VOID
+PutDword (
+ IN UINT32 Data
+ )
+/*++
+
+Routine Description:
+
+ Put a dword to output stream
+
+Arguments:
+
+ Data - the dword to put
+
+Returns: (VOID)
+
+--*/
+{
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = (UINT8) (((UINT8) (Data)) & 0xff);
+ }
+
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = (UINT8) (((UINT8) (Data >> 0x08)) & 0xff);
+ }
+
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = (UINT8) (((UINT8) (Data >> 0x10)) & 0xff);
+ }
+
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = (UINT8) (((UINT8) (Data >> 0x18)) & 0xff);
+ }
+}
+
+STATIC
+EFI_STATUS
+AllocateMemory (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Allocate memory spaces for data structures used in compression process
+
+Argements:
+ VOID
+
+Returns:
+
+ EFI_SUCCESS - Memory is allocated successfully
+ EFI_OUT_OF_RESOURCES - Allocation fails
+
+--*/
+{
+ UINT32 Index;
+
+ mText = malloc (WNDSIZ * 2 + MAXMATCH);
+ for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {
+ mText[Index] = 0;
+ }
+
+ mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mLevel));
+ mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mChildCount));
+ mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof (*mPosition));
+ mParent = malloc (WNDSIZ * 2 * sizeof (*mParent));
+ mPrev = malloc (WNDSIZ * 2 * sizeof (*mPrev));
+ mNext = malloc ((MAX_HASH_VAL + 1) * sizeof (*mNext));
+
+ mBufSiz = BLKSIZ;
+ mBuf = malloc (mBufSiz);
+ while (mBuf == NULL) {
+ mBufSiz = (mBufSiz / 10U) * 9U;
+ if (mBufSiz < 4 * 1024U) {
+ return EFI_OUT_OF_RESOURCES;
+ }
+
+ mBuf = malloc (mBufSiz);
+ }
+
+ mBuf[0] = 0;
+
+ return EFI_SUCCESS;
+}
+
+VOID
+FreeMemory (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Called when compression is completed to free memory previously allocated.
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+ if (mText != NULL) {
+ free (mText);
+ }
+
+ if (mLevel != NULL) {
+ free (mLevel);
+ }
+
+ if (mChildCount != NULL) {
+ free (mChildCount);
+ }
+
+ if (mPosition != NULL) {
+ free (mPosition);
+ }
+
+ if (mParent != NULL) {
+ free (mParent);
+ }
+
+ if (mPrev != NULL) {
+ free (mPrev);
+ }
+
+ if (mNext != NULL) {
+ free (mNext);
+ }
+
+ if (mBuf != NULL) {
+ free (mBuf);
+ }
+
+ return ;
+}
+
+STATIC
+VOID
+InitSlide (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Initialize String Info Log data structures
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+ NODE Index;
+
+ for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {
+ mLevel[Index] = 1;
+ mPosition[Index] = NIL; // sentinel
+ }
+
+ for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {
+ mParent[Index] = NIL;
+ }
+
+ mAvail = 1;
+ for (Index = 1; Index < WNDSIZ - 1; Index++) {
+ mNext[Index] = (NODE) (Index + 1);
+ }
+
+ mNext[WNDSIZ - 1] = NIL;
+ for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {
+ mNext[Index] = NIL;
+ }
+}
+
+STATIC
+NODE
+Child (
+ IN NODE NodeQ,
+ IN UINT8 CharC
+ )
+/*++
+
+Routine Description:
+
+ Find child node given the parent node and the edge character
+
+Arguments:
+
+ NodeQ - the parent node
+ CharC - the edge character
+
+Returns:
+
+ The child node (NIL if not found)
+
+--*/
+{
+ NODE NodeR;
+
+ NodeR = mNext[HASH (NodeQ, CharC)];
+ //
+ // sentinel
+ //
+ mParent[NIL] = NodeQ;
+ while (mParent[NodeR] != NodeQ) {
+ NodeR = mNext[NodeR];
+ }
+
+ return NodeR;
+}
+
+STATIC
+VOID
+MakeChild (
+ IN NODE Parent,
+ IN UINT8 CharC,
+ IN NODE Child
+ )
+/*++
+
+Routine Description:
+
+ Create a new child for a given parent node.
+
+Arguments:
+
+ Parent - the parent node
+ CharC - the edge character
+ Child - the child node
+
+Returns: (VOID)
+
+--*/
+{
+ NODE Node1;
+ NODE Node2;
+
+ Node1 = (NODE) HASH (Parent, CharC);
+ Node2 = mNext[Node1];
+ mNext[Node1] = Child;
+ mNext[Child] = Node2;
+ mPrev[Node2] = Child;
+ mPrev[Child] = Node1;
+ mParent[Child] = Parent;
+ mChildCount[Parent]++;
+}
+
+STATIC
+VOID
+Split (
+ NODE Old
+ )
+/*++
+
+Routine Description:
+
+ Split a node.
+
+Arguments:
+
+ Old - the node to split
+
+Returns: (VOID)
+
+--*/
+{
+ NODE New;
+ NODE TempNode;
+
+ New = mAvail;
+ mAvail = mNext[New];
+ mChildCount[New] = 0;
+ TempNode = mPrev[Old];
+ mPrev[New] = TempNode;
+ mNext[TempNode] = New;
+ TempNode = mNext[Old];
+ mNext[New] = TempNode;
+ mPrev[TempNode] = New;
+ mParent[New] = mParent[Old];
+ mLevel[New] = (UINT8) mMatchLen;
+ mPosition[New] = mPos;
+ MakeChild (New, mText[mMatchPos + mMatchLen], Old);
+ MakeChild (New, mText[mPos + mMatchLen], mPos);
+}
+
+STATIC
+VOID
+InsertNode (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Insert string info for current position into the String Info Log
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+ NODE NodeQ;
+ NODE NodeR;
+ NODE Index2;
+ NODE NodeT;
+ UINT8 CharC;
+ UINT8 *t1;
+ UINT8 *t2;
+
+ if (mMatchLen >= 4) {
+ //
+ // We have just got a long match, the target tree
+ // can be located by MatchPos + 1. Travese the tree
+ // from bottom up to get to a proper starting point.
+ // The usage of PERC_FLAG ensures proper node deletion
+ // in DeleteNode() later.
+ //
+ mMatchLen--;
+ NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);
+ NodeQ = mParent[NodeR];
+ while (NodeQ == NIL) {
+ NodeR = mNext[NodeR];
+ NodeQ = mParent[NodeR];
+ }
+
+ while (mLevel[NodeQ] >= mMatchLen) {
+ NodeR = NodeQ;
+ NodeQ = mParent[NodeQ];
+ }
+
+ NodeT = NodeQ;
+ while (mPosition[NodeT] < 0) {
+ mPosition[NodeT] = mPos;
+ NodeT = mParent[NodeT];
+ }
+
+ if (NodeT < WNDSIZ) {
+ mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);
+ }
+ } else {
+ //
+ // Locate the target tree
+ //
+ NodeQ = (NODE) (mText[mPos] + WNDSIZ);
+ CharC = mText[mPos + 1];
+ NodeR = Child (NodeQ, CharC);
+ if (NodeR == NIL) {
+ MakeChild (NodeQ, CharC, 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 (NodeR >= WNDSIZ) {
+ Index2 = MAXMATCH;
+ mMatchPos = NodeR;
+ } else {
+ Index2 = mLevel[NodeR];
+ mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
+ }
+
+ if (mMatchPos >= mPos) {
+ mMatchPos -= WNDSIZ;
+ }
+
+ t1 = &mText[mPos + mMatchLen];
+ t2 = &mText[mMatchPos + mMatchLen];
+ while (mMatchLen < Index2) {
+ if (*t1 != *t2) {
+ Split (NodeR);
+ return ;
+ }
+
+ mMatchLen++;
+ t1++;
+ t2++;
+ }
+
+ if (mMatchLen >= MAXMATCH) {
+ break;
+ }
+
+ mPosition[NodeR] = mPos;
+ NodeQ = NodeR;
+ NodeR = Child (NodeQ, *t1);
+ if (NodeR == NIL) {
+ MakeChild (NodeQ, *t1, mPos);
+ return ;
+ }
+
+ mMatchLen++;
+ }
+
+ NodeT = mPrev[NodeR];
+ mPrev[mPos] = NodeT;
+ mNext[NodeT] = mPos;
+ NodeT = mNext[NodeR];
+ mNext[mPos] = NodeT;
+ mPrev[NodeT] = mPos;
+ mParent[mPos] = NodeQ;
+ mParent[NodeR] = NIL;
+
+ //
+ // Special usage of 'next'
+ //
+ mNext[NodeR] = mPos;
+
+}
+
+STATIC
+VOID
+DeleteNode (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Delete outdated string info. (The Usage of PERC_FLAG
+ ensures a clean deletion)
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+ NODE NodeQ;
+ NODE NodeR;
+ NODE NodeS;
+ NODE NodeT;
+ NODE NodeU;
+
+ if (mParent[mPos] == NIL) {
+ return ;
+ }
+
+ NodeR = mPrev[mPos];
+ NodeS = mNext[mPos];
+ mNext[NodeR] = NodeS;
+ mPrev[NodeS] = NodeR;
+ NodeR = mParent[mPos];
+ mParent[mPos] = NIL;
+ if (NodeR >= WNDSIZ) {
+ return ;
+ }
+
+ mChildCount[NodeR]--;
+ if (mChildCount[NodeR] > 1) {
+ return ;
+ }
+
+ NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);
+ if (NodeT >= mPos) {
+ NodeT -= WNDSIZ;
+ }
+
+ NodeS = NodeT;
+ NodeQ = mParent[NodeR];
+ NodeU = mPosition[NodeQ];
+ while (NodeU & (UINT32) PERC_FLAG) {
+ NodeU &= (UINT32)~PERC_FLAG;
+ if (NodeU >= mPos) {
+ NodeU -= WNDSIZ;
+ }
+
+ if (NodeU > NodeS) {
+ NodeS = NodeU;
+ }
+
+ mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ);
+ NodeQ = mParent[NodeQ];
+ NodeU = mPosition[NodeQ];
+ }
+
+ if (NodeQ < WNDSIZ) {
+ if (NodeU >= mPos) {
+ NodeU -= WNDSIZ;
+ }
+
+ if (NodeU > NodeS) {
+ NodeS = NodeU;
+ }
+
+ mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);
+ }
+
+ NodeS = Child (NodeR, mText[NodeT + mLevel[NodeR]]);
+ NodeT = mPrev[NodeS];
+ NodeU = mNext[NodeS];
+ mNext[NodeT] = NodeU;
+ mPrev[NodeU] = NodeT;
+ NodeT = mPrev[NodeR];
+ mNext[NodeT] = NodeS;
+ mPrev[NodeS] = NodeT;
+ NodeT = mNext[NodeR];
+ mPrev[NodeT] = NodeS;
+ mNext[NodeS] = NodeT;
+ mParent[NodeS] = mParent[NodeR];
+ mParent[NodeR] = NIL;
+ mNext[NodeR] = mAvail;
+ mAvail = NodeR;
+}
+
+STATIC
+VOID
+GetNextMatch (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Advance the current position (read in new data if needed).
+ Delete outdated string info. Find a match string for current position.
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+ INT32 Number;
+
+ mRemainder--;
+ mPos++;
+ if (mPos == WNDSIZ * 2) {
+ memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
+ Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);
+ mRemainder += Number;
+ mPos = WNDSIZ;
+ }
+
+ DeleteNode ();
+ InsertNode ();
+}
+
+STATIC
+EFI_STATUS
+Encode (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ The main controlling routine for compression process.
+
+Arguments: (VOID)
+
+Returns:
+
+ EFI_SUCCESS - The compression is successful
+ EFI_OUT_0F_RESOURCES - Not enough memory for compression process
+
+--*/
+{
+ EFI_STATUS Status;
+ INT32 LastMatchLen;
+ NODE LastMatchPos;
+
+ Status = AllocateMemory ();
+ if (EFI_ERROR (Status)) {
+ FreeMemory ();
+ return Status;
+ }
+
+ InitSlide ();
+
+ HufEncodeStart ();
+
+ mRemainder = FreadCrc (&mText[WNDSIZ], WNDSIZ + MAXMATCH);
+
+ mMatchLen = 0;
+ mPos = WNDSIZ;
+ InsertNode ();
+ if (mMatchLen > mRemainder) {
+ mMatchLen = mRemainder;
+ }
+
+ while (mRemainder > 0) {
+ LastMatchLen = mMatchLen;
+ LastMatchPos = mMatchPos;
+ GetNextMatch ();
+ if (mMatchLen > mRemainder) {
+ mMatchLen = mRemainder;
+ }
+
+ if (mMatchLen > LastMatchLen || LastMatchLen < THRESHOLD) {
+ //
+ // Not enough benefits are gained by outputting a pointer,
+ // so just output the original character
+ //
+ Output (mText[mPos - 1], 0);
+
+ } else {
+
+ if (LastMatchLen == THRESHOLD) {
+ if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {
+ Output (mText[mPos - 1], 0);
+ continue;
+ }
+ }
+ //
+ // Outputting a pointer is beneficial enough, do it.
+ //
+ Output (
+ LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
+ (mPos - LastMatchPos - 2) & (WNDSIZ - 1)
+ );
+ LastMatchLen--;
+ while (LastMatchLen > 0) {
+ GetNextMatch ();
+ LastMatchLen--;
+ }
+
+ if (mMatchLen > mRemainder) {
+ mMatchLen = mRemainder;
+ }
+ }
+ }
+
+ HufEncodeEnd ();
+ FreeMemory ();
+ return EFI_SUCCESS;
+}
+
+STATIC
+VOID
+CountTFreq (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Count the frequencies for the Extra Set
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+ INT32 Index;
+ INT32 Index3;
+ INT32 Number;
+ INT32 Count;
+
+ for (Index = 0; Index < NT; Index++) {
+ mTFreq[Index] = 0;
+ }
+
+ Number = NC;
+ while (Number > 0 && mCLen[Number - 1] == 0) {
+ Number--;
+ }
+
+ Index = 0;
+ while (Index < Number) {
+ Index3 = mCLen[Index++];
+ if (Index3 == 0) {
+ Count = 1;
+ while (Index < Number && mCLen[Index] == 0) {
+ Index++;
+ Count++;
+ }
+
+ if (Count <= 2) {
+ mTFreq[0] = (UINT16) (mTFreq[0] + Count);
+ } else if (Count <= 18) {
+ mTFreq[1]++;
+ } else if (Count == 19) {
+ mTFreq[0]++;
+ mTFreq[1]++;
+ } else {
+ mTFreq[2]++;
+ }
+ } else {
+ mTFreq[Index3 + 2]++;
+ }
+ }
+}
+
+STATIC
+VOID
+WritePTLen (
+ IN INT32 Number,
+ IN INT32 nbit,
+ IN INT32 Special
+ )
+/*++
+
+Routine Description:
+
+ Outputs the code length array for the Extra Set or the Position Set.
+
+Arguments:
+
+ Number - the number of symbols
+ nbit - the number of bits needed to represent 'n'
+ Special - the special symbol that needs to be take care of
+
+Returns: (VOID)
+
+--*/
+{
+ INT32 Index;
+ INT32 Index3;
+
+ while (Number > 0 && mPTLen[Number - 1] == 0) {
+ Number--;
+ }
+
+ PutBits (nbit, Number);
+ Index = 0;
+ while (Index < Number) {
+ Index3 = mPTLen[Index++];
+ if (Index3 <= 6) {
+ PutBits (3, Index3);
+ } else {
+ PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2);
+ }
+
+ if (Index == Special) {
+ while (Index < 6 && mPTLen[Index] == 0) {
+ Index++;
+ }
+
+ PutBits (2, (Index - 3) & 3);
+ }
+ }
+}
+
+STATIC
+VOID
+WriteCLen (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Outputs the code length array for Char&Length Set
+
+Arguments: (VOID)
+
+Returns: (VOID)
+
+--*/
+{
+ INT32 Index;
+ INT32 Index3;
+ INT32 Number;
+ INT32 Count;
+
+ Number = NC;
+ while (Number > 0 && mCLen[Number - 1] == 0) {
+ Number--;
+ }
+
+ PutBits (CBIT, Number);
+ Index = 0;
+ while (Index < Number) {
+ Index3 = mCLen[Index++];
+ if (Index3 == 0) {
+ Count = 1;
+ while (Index < Number && mCLen[Index] == 0) {
+ Index++;
+ Count++;
+ }
+
+ if (Count <= 2) {
+ for (Index3 = 0; Index3 < Count; Index3++) {
+ PutBits (mPTLen[0], mPTCode[0]);
+ }
+ } else if (Count <= 18) {
+ PutBits (mPTLen[1], mPTCode[1]);
+ PutBits (4, Count - 3);
+ } else if (Count == 19) {
+ PutBits (mPTLen[0], mPTCode[0]);
+ PutBits (mPTLen[1], mPTCode[1]);
+ PutBits (4, 15);
+ } else {
+ PutBits (mPTLen[2], mPTCode[2]);
+ PutBits (CBIT, Count - 20);
+ }
+ } else {
+ PutBits (mPTLen[Index3 + 2], mPTCode[Index3 + 2]);
+ }
+ }
+}
+
+STATIC
+VOID
+EncodeC (
+ IN INT32 Value
+ )
+{
+ PutBits (mCLen[Value], mCCode[Value]);
+}
+
+STATIC
+VOID
+EncodeP (
+ IN UINT32 Value
+ )
+{
+ UINT32 Index;
+ UINT32 NodeQ;
+
+ Index = 0;
+ NodeQ = Value;
+ while (NodeQ) {
+ NodeQ >>= 1;
+ Index++;
+ }
+
+ PutBits (mPTLen[Index], mPTCode[Index]);
+ if (Index > 1) {
+ PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1)));
+ }
+}
+
+STATIC
+VOID
+SendBlock (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Huffman code the block and output it.
+
+Arguments:
+ (VOID)
+
+Returns:
+ (VOID)
+
+--*/
+{
+ UINT32 Index;
+ UINT32 Index2;
+ UINT32 Index3;
+ 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 (Index = 0; Index < Size; Index++) {
+ if (Index % UINT8_BIT == 0) {
+ Flags = mBuf[Pos++];
+ } else {
+ Flags <<= 1;
+ }
+
+ if (Flags & (1U << (UINT8_BIT - 1))) {
+ EncodeC (mBuf[Pos++] + (1U << UINT8_BIT));
+ Index3 = mBuf[Pos++];
+ for (Index2 = 0; Index2 < 3; Index2++) {
+ Index3 <<= UINT8_BIT;
+ Index3 += mBuf[Pos++];
+ }
+
+ EncodeP (Index3);
+ } else {
+ EncodeC (mBuf[Pos++]);
+ }
+ }
+
+ for (Index = 0; Index < NC; Index++) {
+ mCFreq[Index] = 0;
+ }
+
+ for (Index = 0; Index < NP; Index++) {
+ mPFreq[Index] = 0;
+ }
+}
+
+STATIC
+VOID
+Output (
+ IN UINT32 CharC,
+ IN UINT32 Pos
+ )
+/*++
+
+Routine Description:
+
+ Outputs an Original Character or a Pointer
+
+Arguments:
+
+ CharC - The original character or the 'String Length' element of a Pointer
+ Pos - The 'Position' field of a Pointer
+
+Returns: (VOID)
+
+--*/
+{
+ STATIC UINT32 CPos;
+
+ if ((mOutputMask >>= 1) == 0) {
+ mOutputMask = 1U << (UINT8_BIT - 1);
+ //
+ // Check the buffer overflow per outputing UINT8_BIT symbols
+ // which is an Original Character or a Pointer. The biggest
+ // symbol is a Pointer which occupies 5 bytes.
+ //
+ if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) {
+ SendBlock ();
+ mOutputPos = 0;
+ }
+
+ CPos = mOutputPos++;
+ mBuf[CPos] = 0;
+ }
+
+ mBuf[mOutputPos++] = (UINT8) CharC;
+ mCFreq[CharC]++;
+ if (CharC >= (1U << UINT8_BIT)) {
+ mBuf[CPos] |= mOutputMask;
+ mBuf[mOutputPos++] = (UINT8) (Pos >> 24);
+ mBuf[mOutputPos++] = (UINT8) (Pos >> 16);
+ mBuf[mOutputPos++] = (UINT8) (Pos >> (UINT8_BIT));
+ mBuf[mOutputPos++] = (UINT8) Pos;
+ CharC = 0;
+ while (Pos) {
+ Pos >>= 1;
+ CharC++;
+ }
+
+ mPFreq[CharC]++;
+ }
+}
+
+STATIC
+VOID
+HufEncodeStart (
+ VOID
+ )
+{
+ INT32 Index;
+
+ for (Index = 0; Index < NC; Index++) {
+ mCFreq[Index] = 0;
+ }
+
+ for (Index = 0; Index < NP; Index++) {
+ mPFreq[Index] = 0;
+ }
+
+ mOutputPos = mOutputMask = 0;
+ InitPutBits ();
+ return ;
+}
+
+STATIC
+VOID
+HufEncodeEnd (
+ VOID
+ )
+{
+ SendBlock ();
+
+ //
+ // Flush remaining bits
+ //
+ PutBits (UINT8_BIT - 1, 0);
+
+ return ;
+}
+
+STATIC
+VOID
+MakeCrcTable (
+ VOID
+ )
+{
+ UINT32 Index;
+ UINT32 Index2;
+ UINT32 Temp;
+
+ for (Index = 0; Index <= UINT8_MAX; Index++) {
+ Temp = Index;
+ for (Index2 = 0; Index2 < UINT8_BIT; Index2++) {
+ if (Temp & 1) {
+ Temp = (Temp >> 1) ^ CRCPOLY;
+ } else {
+ Temp >>= 1;
+ }
+ }
+
+ mCrcTable[Index] = (UINT16) Temp;
+ }
+}
+
+STATIC
+VOID
+PutBits (
+ IN INT32 Number,
+ IN UINT32 Value
+ )
+/*++
+
+Routine Description:
+
+ Outputs rightmost n bits of x
+
+Arguments:
+
+ Number - the rightmost n bits of the data is used
+ x - the data
+
+Returns: (VOID)
+
+--*/
+{
+ UINT8 Temp;
+
+ while (Number >= mBitCount) {
+ //
+ // Number -= mBitCount should never equal to 32
+ //
+ Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount)));
+
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = Temp;
+ }
+
+ mCompSize++;
+ mSubBitBuf = 0;
+ mBitCount = UINT8_BIT;
+ }
+
+ mSubBitBuf |= Value << (mBitCount -= Number);
+}
+
+STATIC
+INT32
+FreadCrc (
+ OUT UINT8 *Pointer,
+ IN INT32 Number
+ )
+/*++
+
+Routine Description:
+
+ Read in source data
+
+Arguments:
+
+ Pointer - the buffer to hold the data
+ Number - number of bytes to read
+
+Returns:
+
+ number of bytes actually read
+
+--*/
+{
+ INT32 Index;
+
+ for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) {
+ *Pointer++ = *mSrc++;
+ }
+
+ Number = Index;
+
+ Pointer -= Number;
+ mOrigSize += Number;
+
+ Index--;
+ while (Index >= 0) {
+ UPDATE_CRC (*Pointer++);
+ Index--;
+ }
+
+ return Number;
+}
+
+STATIC
+VOID
+InitPutBits (
+ VOID
+ )
+{
+ mBitCount = UINT8_BIT;
+ mSubBitBuf = 0;
+}
+
+STATIC
+VOID
+CountLen (
+ IN INT32 Index
+ )
+/*++
+
+Routine Description:
+
+ Count the number of each code length for a Huffman tree.
+
+Arguments:
+
+ Index - the top node
+
+Returns: (VOID)
+
+--*/
+{
+ STATIC INT32 Depth = 0;
+
+ if (Index < mN) {
+ mLenCnt[(Depth < 16) ? Depth : 16]++;
+ } else {
+ Depth++;
+ CountLen (mLeft[Index]);
+ CountLen (mRight[Index]);
+ Depth--;
+ }
+}
+
+STATIC
+VOID
+MakeLen (
+ IN INT32 Root
+ )
+/*++
+
+Routine Description:
+
+ Create code length array for a Huffman tree
+
+Arguments:
+
+ Root - the root of the tree
+
+Returns:
+
+ VOID
+
+--*/
+{
+ INT32 Index;
+ INT32 Index3;
+ UINT32 Cum;
+
+ for (Index = 0; Index <= 16; Index++) {
+ mLenCnt[Index] = 0;
+ }
+
+ CountLen (Root);
+
+ //
+ // Adjust the length count array so that
+ // no code will be generated longer than its designated length
+ //
+ Cum = 0;
+ for (Index = 16; Index > 0; Index--) {
+ Cum += mLenCnt[Index] << (16 - Index);
+ }
+
+ while (Cum != (1U << 16)) {
+ mLenCnt[16]--;
+ for (Index = 15; Index > 0; Index--) {
+ if (mLenCnt[Index] != 0) {
+ mLenCnt[Index]--;
+ mLenCnt[Index + 1] += 2;
+ break;
+ }
+ }
+
+ Cum--;
+ }
+
+ for (Index = 16; Index > 0; Index--) {
+ Index3 = mLenCnt[Index];
+ Index3--;
+ while (Index3 >= 0) {
+ mLen[*mSortPtr++] = (UINT8) Index;
+ Index3--;
+ }
+ }
+}
+
+STATIC
+VOID
+DownHeap (
+ IN INT32 Index
+ )
+{
+ INT32 Index2;
+ INT32 Index3;
+
+ //
+ // priority queue: send Index-th entry down heap
+ //
+ Index3 = mHeap[Index];
+ Index2 = 2 * Index;
+ while (Index2 <= mHeapSize) {
+ if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) {
+ Index2++;
+ }
+
+ if (mFreq[Index3] <= mFreq[mHeap[Index2]]) {
+ break;
+ }
+
+ mHeap[Index] = mHeap[Index2];
+ Index = Index2;
+ Index2 = 2 * Index;
+ }
+
+ mHeap[Index] = (INT16) Index3;
+}
+
+STATIC
+VOID
+MakeCode (
+ IN INT32 Number,
+ IN UINT8 Len[ ],
+ OUT UINT16 Code[]
+ )
+/*++
+
+Routine Description:
+
+ Assign code to each symbol based on the code length array
+
+Arguments:
+
+ Number - number of symbols
+ Len - the code length array
+ Code - stores codes for each symbol
+
+Returns: (VOID)
+
+--*/
+{
+ INT32 Index;
+ UINT16 Start[18];
+
+ Start[1] = 0;
+ for (Index = 1; Index <= 16; Index++) {
+ Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1);
+ }
+
+ for (Index = 0; Index < Number; Index++) {
+ Code[Index] = Start[Len[Index]]++;
+ }
+}
+
+STATIC
+INT32
+MakeTree (
+ IN INT32 NParm,
+ IN UINT16 FreqParm[],
+ OUT UINT8 LenParm[ ],
+ OUT UINT16 CodeParm[]
+ )
+/*++
+
+Routine Description:
+
+ Generates Huffman codes given a frequency distribution of symbols
+
+Arguments:
+
+ NParm - number of symbols
+ FreqParm - frequency of each symbol
+ LenParm - code length for each symbol
+ CodeParm - code for each symbol
+
+Returns:
+
+ Root of the Huffman tree.
+
+--*/
+{
+ INT32 Index;
+ INT32 Index2;
+ INT32 Index3;
+ INT32 Avail;
+
+ //
+ // make tree, calculate len[], return root
+ //
+ mN = NParm;
+ mFreq = FreqParm;
+ mLen = LenParm;
+ Avail = mN;
+ mHeapSize = 0;
+ mHeap[1] = 0;
+ for (Index = 0; Index < mN; Index++) {
+ mLen[Index] = 0;
+ if (mFreq[Index]) {
+ mHeapSize++;
+ mHeap[mHeapSize] = (INT16) Index;
+ }
+ }
+
+ if (mHeapSize < 2) {
+ CodeParm[mHeap[1]] = 0;
+ return mHeap[1];
+ }
+
+ for (Index = mHeapSize / 2; Index >= 1; Index--) {
+ //
+ // make priority queue
+ //
+ DownHeap (Index);
+ }
+
+ mSortPtr = CodeParm;
+ do {
+ Index = mHeap[1];
+ if (Index < mN) {
+ *mSortPtr++ = (UINT16) Index;
+ }
+
+ mHeap[1] = mHeap[mHeapSize--];
+ DownHeap (1);
+ Index2 = mHeap[1];
+ if (Index2 < mN) {
+ *mSortPtr++ = (UINT16) Index2;
+ }
+
+ Index3 = Avail++;
+ mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]);
+ mHeap[1] = (INT16) Index3;
+ DownHeap (1);
+ mLeft[Index3] = (UINT16) Index;
+ mRight[Index3] = (UINT16) Index2;
+ } while (mHeapSize > 1);
+
+ mSortPtr = CodeParm;
+ MakeLen (Index3);
+ MakeCode (NParm, LenParm, CodeParm);
+
+ //
+ // return root
+ //
+ return Index3;
+}
+
+EFI_STATUS
+GetFileContents (
+ IN char *InputFileName,
+ OUT UINT8 *FileBuffer,
+ OUT UINT32 *BufferLength
+ )
+/*++
+
+Routine Description:
+
+ Get the contents of file specified in InputFileName
+ into FileBuffer.
+
+Arguments:
+
+ InputFileName - Name of the input file.
+
+ FileBuffer - Output buffer to contain data
+
+ BufferLength - Actual length of the data
+
+Returns:
+
+ EFI_SUCCESS on successful return
+ EFI_ABORTED if unable to open input file.
+
+--*/
+{
+ UINTN Size;
+ UINTN FileSize;
+ FILE *InputFile;
+
+ Size = 0;
+ //
+ // Copy the file contents to the output buffer.
+ //
+ InputFile = fopen (InputFileName, "rb");
+ if (InputFile == NULL) {
+ Error (NULL, 0, 0001, "Error opening file: %s", InputFileName);
+ return EFI_ABORTED;
+ }
+
+ fseek (InputFile, 0, SEEK_END);
+ FileSize = ftell (InputFile);
+ fseek (InputFile, 0, SEEK_SET);
+ //
+ // Now read the contents of the file into the buffer
+ //
+ if (FileSize > 0 && FileBuffer != NULL) {
+ if (fread (FileBuffer, FileSize, 1, InputFile) != 1) {
+ Error (NULL, 0, 0004, "Error reading contents of input file: %s", InputFileName);
+ fclose (InputFile);
+ return EFI_ABORTED;
+ }
+ }
+
+ fclose (InputFile);
+ Size += (UINTN) FileSize;
+ *BufferLength = Size;
+
+ if (FileBuffer != NULL) {
+ return EFI_SUCCESS;
+ } else {
+ return EFI_BUFFER_TOO_SMALL;
+ }
+}
+
+VOID
+Version (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Displays the standard utility information to SDTOUT
+
+Arguments:
+
+ None
+
+Returns:
+
+ None
+
+--*/
+{
+ fprintf (stdout, "%s Version %d.%d\n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION);
+}
+
+VOID
+Usage (
+ VOID
+ )
+/*++
+
+Routine Description:
+
+ Displays the utility usage syntax to STDOUT
+
+Arguments:
+
+ None
+
+Returns:
+
+ None
+
+--*/
+{
+ //
+ // Summary usage
+ //
+ fprintf (stdout, "Usage: %s -e|-d [options] <input_file>\n\n", UTILITY_NAME);
+
+ //
+ // Copyright declaration
+ //
+ fprintf (stdout, "Copyright (c) 2007, Intel Corporation. All rights reserved.\n\n");
+
+ //
+ // Details Option
+ //
+ fprintf (stdout, "Options:\n");
+ fprintf (stdout, " -o FileName, --output FileName\n\
+ File will be created to store the ouput content.\n");
+ fprintf (stdout, " -v, --verbose\n\
+ Turn on verbose output with informational messages.\n");
+ fprintf (stdout, " -q, --quiet\n\
+ Disable all messages except key message and fatal error\n");
+ fprintf (stdout, " --debug [0-9]\n\
+ Enable debug messages, at input debug level.\n");
+ fprintf (stdout, " --version\n\
+ Show program's version number and exit.\n");
+ fprintf (stdout, " -h, --help\n\
+ Show this help message and exit.\n");
+}
+
+
+int
+main (
+ int argc,
+ char *argv[]
+ )
+/*++
+
+Routine Description:
+
+ Main
+
+Arguments:
+
+ command line parameters
+
+Returns:
+
+ EFI_SUCCESS Section header successfully generated and section concatenated.
+ EFI_ABORTED Could not generate the section
+ EFI_OUT_OF_RESOURCES No resource to complete the operation.
+
+--*/
+{
+ FILE *OutputFile;
+ char *OutputFileName;
+ char *InputFileName;
+ FILE *InputFile;
+ EFI_STATUS Status;
+ UINT8 *FileBuffer;
+ UINT8 *OutBuffer;
+ UINT32 InputLength;
+ UINT32 DstSize;
+ SCRATCH_DATA *Scratch;
+ UINT8 *Src;
+ UINT32 OrigSize;
+
+ SetUtilityName(UTILITY_NAME);
+
+ FileBuffer = NULL;
+ Src = NULL;
+ OutBuffer = NULL;
+ Scratch = NULL;
+ OrigSize = 0;
+ InputLength = 0;
+ InputFileName = NULL;
+ OutputFileName = NULL;
+ DstSize=0;
+ DebugLevel = 0;
+ DebugMode = FALSE;
+
+ //
+ // Verify the correct number of arguments
+ //
+ if (argc == 1) {
+ Error (NULL, 0, 1001, "Missing options", "No input options specified.");
+ Usage();
+ return 0;
+ }
+
+ if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) {
+ Usage();
+ return 0;
+ }
+
+ if ((strcmp(argv[1], "--version") == 0)) {
+ Version();
+ return 0;
+ }
+
+ argc--;
+ argv++;
+ if (strcmp(argv[0],"-e") == 0) {
+ //
+ // encode the input file
+ //
+ ENCODE = TRUE;
+ argc--;
+ argv++;
+ } else if (strcmp(argv[0], "-d") == 0) {
+ //
+ // decode the input file
+ //
+ DECODE = TRUE;
+ argc--;
+ argv++;
+ } else {
+ //
+ // Error command line
+ //
+ Error (NULL, 0, 1003, "Invalid option value", "the options specified are not recognized.");
+ Usage();
+ return 1;
+ }
+
+ while (argc > 0) {
+ if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) {
+ VerboseMode = TRUE;
+ argc--;
+ argv++;
+ continue;
+ }
+
+ if (stricmp (argv[0], "--debug") == 0) {
+ argc-=2;
+ argv++;
+ Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel);
+ if (DebugLevel > 9) {
+ Error (NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]);
+ goto ERROR;
+ }
+ if (DebugLevel>=5 && DebugLevel <=9){
+ DebugMode = TRUE;
+ } else {
+ DebugMode = FALSE;
+ }
+ argv++;
+ continue;
+ }
+
+ if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--quiet") == 0)) {
+ QuietMode = TRUE;
+ argc--;
+ argv++;
+ continue;
+ }
+
+ if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) {
+ if (argv[1] == NULL || argv[1][0] == '-') {
+ Error (NULL, 0, 1003, "Invalid option value", "Output File name is missing for -o option");
+ goto ERROR;
+ }
+ OutputFileName = argv[1];
+ argc -=2;
+ argv +=2;
+ continue;
+ }
+
+ if (argv[0][0]!='-') {
+ InputFileName = argv[0];
+ argc--;
+ argv++;
+ continue;
+ }
+
+ Error (NULL, 0, 1000, "Unknown option", argv[0]);
+ goto ERROR;
+ }
+
+ if (InputFileName == NULL) {
+ Error (NULL, 0, 1001, "Missing options", "No input files specified.");
+ goto ERROR;
+ }
+
+//
+// All Parameters has been parsed, now set the message print level
+//
+ if (QuietMode) {
+ SetPrintLevel(40);
+ } else if (VerboseMode) {
+ SetPrintLevel(15);
+ } else if (DebugMode) {
+ SetPrintLevel(DebugLevel);
+ }
+
+ if (VerboseMode) {
+ VerboseMsg("%s tool start.\n", UTILITY_NAME);
+ }
+ Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA));
+ if (Scratch == NULL) {
+ Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
+ goto ERROR;
+ }
+
+ InputFile = fopen (InputFileName, "rb");
+ if (InputFile == NULL) {
+ Error (NULL, 0, 0001, "Error opening input file", InputFileName);
+ goto ERROR;
+ }
+
+ Status = GetFileContents(
+ InputFileName,
+ FileBuffer,
+ &InputLength);
+
+ if (Status == EFI_BUFFER_TOO_SMALL) {
+ FileBuffer = (UINT8 *) malloc (InputLength);
+ if (FileBuffer == NULL) {
+ Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
+ return 1;
+ }
+
+ Status = GetFileContents (
+ InputFileName,
+ FileBuffer,
+ &InputLength
+ );
+ }
+
+ if (EFI_ERROR(Status)) {
+ free(FileBuffer);
+ return 1;
+ }
+
+ if (OutputFileName != NULL) {
+ OutputFile = fopen (OutputFileName, "wb");
+ if (OutputFile == NULL) {
+ Error (NULL, 0, 0001, "Error opening output file for writing", OutputFileName);
+ if (InputFile != NULL) {
+ fclose (InputFile);
+ }
+ goto ERROR;
+ }
+ } else {
+ OutputFileName = DEFAULT_OUTPUT_FILE;
+ OutputFile = fopen (OutputFileName, "wb");
+ }
+
+ if (ENCODE) {
+ //
+ // First call TianoCompress to get DstSize
+ //
+ if (DebugMode) {
+ DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding", NULL);
+ }
+ Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
+
+ if (Status == EFI_BUFFER_TOO_SMALL) {
+ OutBuffer = (UINT8 *) malloc (DstSize);
+ if (OutBuffer == NULL) {
+ Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
+ goto ERROR;
+ }
+ }
+ Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize);
+ if (Status != EFI_SUCCESS) {
+ Error (NULL, 0, 0007, "Error compressing file", NULL);
+ goto ERROR;
+ }
+
+ fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile);
+ free(Scratch);
+ free(FileBuffer);
+ free(OutBuffer);
+
+ if (DebugMode) {
+ DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Successful!\n", NULL);
+ }
+ if (VerboseMode) {
+ VerboseMsg("Encoding successful\n");
+ }
+ return 0;
+ }
+ else if (DECODE) {
+ if (DebugMode) {
+ DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding\n", NULL);
+ }
+ //
+ // Get Compressed file original size
+ //
+ Src = (UINT8 *)FileBuffer;
+ OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
+
+ //
+ // Allocate OutputBuffer
+ //
+ OutBuffer = (UINT8 *)malloc(OrigSize);
+ if (OutBuffer == NULL) {
+ Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!");
+ goto ERROR;
+ }
+
+ Status = Decompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2);
+ if (Status != EFI_SUCCESS) {
+ goto ERROR;
+ }
+
+ fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile);
+ free(Scratch);
+ free(FileBuffer);
+ free(OutBuffer);
+
+ if (DebugMode) {
+ DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding successful!\n", NULL);
+ }
+
+ if (VerboseMode) {
+ VerboseMsg("Decoding successful\n");
+ }
+ return 0;
+ }
+
+ERROR:
+ if (DebugMode) {
+ if (ENCODE) {
+ DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Error\n", NULL);
+ } else if (DECODE) {
+ DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding Error\n", NULL);
+ }
+ }
+ if (Scratch != NULL) {
+ free(Scratch);
+ }
+ if (FileBuffer != NULL) {
+ free(FileBuffer);
+ }
+ if (OutBuffer != NULL) {
+ free(OutBuffer);
+ }
+
+ if (VerboseMode) {
+ VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ());
+ }
+ return GetUtilityStatus ();
+}
+
+VOID
+FillBuf (
+ IN SCRATCH_DATA *Sd,
+ IN UINT16 NumOfBits
+ )
+/*++
+
+Routine Description:
+
+ Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.
+
+Arguments:
+
+ Sd - The global scratch data
+ NumOfBits - The number of bits to shift and read.
+
+Returns: (VOID)
+
+--*/
+{
+ Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);
+
+ while (NumOfBits > Sd->mBitCount) {
+
+ Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));
+
+ if (Sd->mCompSize > 0) {
+ //
+ // Get 1 byte into SubBitBuf
+ //
+ Sd->mCompSize--;
+ Sd->mSubBitBuf = 0;
+ Sd->mSubBitBuf = Sd->mSrcBase[Sd->mInBuf++];
+ Sd->mBitCount = 8;
+
+ } else {
+ //
+ // No more bits from the source, just pad zero bit.
+ //
+ Sd->mSubBitBuf = 0;
+ Sd->mBitCount = 8;
+
+ }
+ }
+
+ Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);
+ Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;
+}
+
+UINT32
+GetBits (
+ IN SCRATCH_DATA *Sd,
+ IN UINT16 NumOfBits
+ )
+/*++
+
+Routine Description:
+
+ Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent
+ NumOfBits of bits from source. Returns NumOfBits of bits that are
+ popped out.
+
+Arguments:
+
+ Sd - The global scratch data.
+ NumOfBits - The number of bits to pop and read.
+
+Returns:
+
+ The bits that are popped out.
+
+--*/
+{
+ UINT32 OutBits;
+
+ OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
+
+ FillBuf (Sd, NumOfBits);
+
+ return OutBits;
+}
+
+UINT16
+MakeTable (
+ IN SCRATCH_DATA *Sd,
+ IN UINT16 NumOfChar,
+ IN UINT8 *BitLen,
+ IN UINT16 TableBits,
+ OUT UINT16 *Table
+ )
+/*++
+
+Routine Description:
+
+ Creates Huffman Code mapping table according to code length array.
+
+Arguments:
+
+ Sd - The global scratch data
+ NumOfChar - Number of symbols in the symbol set
+ BitLen - Code length array
+ TableBits - The width of the mapping table
+ Table - The table
+
+Returns:
+
+ 0 - OK.
+ BAD_TABLE - The table is corrupted.
+
+--*/
+{
+ UINT16 Count[17];
+ UINT16 Weight[17];
+ UINT16 Start[18];
+ UINT16 *Pointer;
+ UINT16 Index3;
+ volatile UINT16 Index;
+ UINT16 Len;
+ UINT16 Char;
+ UINT16 JuBits;
+ UINT16 Avail;
+ UINT16 NextCode;
+ UINT16 Mask;
+ UINT16 WordOfStart;
+ UINT16 WordOfCount;
+
+ for (Index = 1; Index <= 16; Index++) {
+ Count[Index] = 0;
+ }
+
+ for (Index = 0; Index < NumOfChar; Index++) {
+ Count[BitLen[Index]]++;
+ }
+
+ Start[1] = 0;
+
+ for (Index = 1; Index <= 16; Index++) {
+ WordOfStart = Start[Index];
+ WordOfCount = Count[Index];
+ Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));
+ }
+
+ if (Start[17] != 0) {
+ //
+ //(1U << 16)
+ //
+ return (UINT16) BAD_TABLE;
+ }
+
+ JuBits = (UINT16) (16 - TableBits);
+
+ for (Index = 1; Index <= TableBits; Index++) {
+ Start[Index] >>= JuBits;
+ Weight[Index] = (UINT16) (1U << (TableBits - Index));
+ }
+
+ while (Index <= 16) {
+ Weight[Index] = (UINT16) (1U << (16 - Index));
+ Index++;
+ }
+
+ Index = (UINT16) (Start[TableBits + 1] >> JuBits);
+
+ if (Index != 0) {
+ Index3 = (UINT16) (1U << TableBits);
+ while (Index != Index3) {
+ Table[Index++] = 0;
+ }
+ }
+
+ Avail = NumOfChar;
+ Mask = (UINT16) (1U << (15 - TableBits));
+
+ for (Char = 0; Char < NumOfChar; Char++) {
+
+ Len = BitLen[Char];
+ if (Len == 0) {
+ continue;
+ }
+
+ NextCode = (UINT16) (Start[Len] + Weight[Len]);
+
+ if (Len <= TableBits) {
+
+ for (Index = Start[Len]; Index < NextCode; Index++) {
+ Table[Index] = Char;
+ }
+
+ } else {
+
+ Index3 = Start[Len];
+ Pointer = &Table[Index3 >> JuBits];
+ Index = (UINT16) (Len - TableBits);
+
+ while (Index != 0) {
+ if (*Pointer == 0) {
+ Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
+ *Pointer = Avail++;
+ }
+
+ if (Index3 & Mask) {
+ Pointer = &Sd->mRight[*Pointer];
+ } else {
+ Pointer = &Sd->mLeft[*Pointer];
+ }
+
+ Index3 <<= 1;
+ Index--;
+ }
+
+ *Pointer = Char;
+
+ }
+
+ Start[Len] = NextCode;
+ }
+ //
+ // Succeeds
+ //
+ return 0;
+}
+
+UINT32
+DecodeP (
+ IN SCRATCH_DATA *Sd
+ )
+/*++
+
+Routine Description:
+
+ Decodes a position value.
+
+Arguments:
+
+ Sd - the global scratch data
+
+Returns:
+
+ The position value decoded.
+
+--*/
+{
+ UINT16 Val;
+ UINT32 Mask;
+ UINT32 Pos;
+
+ Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
+
+ if (Val >= MAXNP) {
+ Mask = 1U << (BITBUFSIZ - 1 - 8);
+
+ do {
+
+ if (Sd->mBitBuf & Mask) {
+ Val = Sd->mRight[Val];
+ } else {
+ Val = Sd->mLeft[Val];
+ }
+
+ Mask >>= 1;
+ } while (Val >= MAXNP);
+ }
+ //
+ // Advance what we have read
+ //
+ FillBuf (Sd, Sd->mPTLen[Val]);
+
+ Pos = Val;
+ if (Val > 1) {
+ Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1)));
+ }
+
+ return Pos;
+}
+
+UINT16
+ReadPTLen (
+ IN SCRATCH_DATA *Sd,
+ IN UINT16 nn,
+ IN UINT16 nbit,
+ IN UINT16 Special
+ )
+/*++
+
+Routine Description:
+
+ Reads code lengths for the Extra Set or the Position Set
+
+Arguments:
+
+ Sd - The global scratch data
+ nn - Number of symbols
+ nbit - Number of bits needed to represent nn
+ Special - The special symbol that needs to be taken care of
+
+Returns:
+
+ 0 - OK.
+ BAD_TABLE - Table is corrupted.
+
+--*/
+{
+ UINT16 Number;
+ UINT16 CharC;
+ volatile UINT16 Index;
+ UINT32 Mask;
+
+ Number = (UINT16) GetBits (Sd, nbit);
+
+ if (Number == 0) {
+ CharC = (UINT16) GetBits (Sd, nbit);
+
+ for (Index = 0; Index < 256; Index++) {
+ Sd->mPTTable[Index] = CharC;
+ }
+
+ for (Index = 0; Index < nn; Index++) {
+ Sd->mPTLen[Index] = 0;
+ }
+
+ return 0;
+ }
+
+ Index = 0;
+
+ while (Index < Number) {
+
+ CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));
+
+ if (CharC == 7) {
+ Mask = 1U << (BITBUFSIZ - 1 - 3);
+ while (Mask & Sd->mBitBuf) {
+ Mask >>= 1;
+ CharC += 1;
+ }
+ }
+
+ FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));
+
+ Sd->mPTLen[Index++] = (UINT8) CharC;
+
+ if (Index == Special) {
+ CharC = (UINT16) GetBits (Sd, 2);
+ while ((INT16) (--CharC) >= 0) {
+ Sd->mPTLen[Index++] = 0;
+ }
+ }
+ }
+
+ while (Index < nn) {
+ Sd->mPTLen[Index++] = 0;
+ }
+
+ return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);
+}
+
+VOID
+ReadCLen (
+ SCRATCH_DATA *Sd
+ )
+/*++
+
+Routine Description:
+
+ Reads code lengths for Char&Len Set.
+
+Arguments:
+
+ Sd - the global scratch data
+
+Returns: (VOID)
+
+--*/
+{
+ UINT16 Number;
+ UINT16 CharC;
+ volatile UINT16 Index;
+ UINT32 Mask;
+
+ Number = (UINT16) GetBits (Sd, CBIT);
+
+ if (Number == 0) {
+ CharC = (UINT16) GetBits (Sd, CBIT);
+
+ for (Index = 0; Index < NC; Index++) {
+ Sd->mCLen[Index] = 0;
+ }
+
+ for (Index = 0; Index < 4096; Index++) {
+ Sd->mCTable[Index] = CharC;
+ }
+
+ return ;
+ }
+
+ Index = 0;
+ while (Index < Number) {
+
+ CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
+ if (CharC >= NT) {
+ Mask = 1U << (BITBUFSIZ - 1 - 8);
+
+ do {
+
+ if (Mask & Sd->mBitBuf) {
+ CharC = Sd->mRight[CharC];
+ } else {
+ CharC = Sd->mLeft[CharC];
+ }
+
+ Mask >>= 1;
+
+ } while (CharC >= NT);
+ }
+ //
+ // Advance what we have read
+ //
+ FillBuf (Sd, Sd->mPTLen[CharC]);
+
+ if (CharC <= 2) {
+
+ if (CharC == 0) {
+ CharC = 1;
+ } else if (CharC == 1) {
+ CharC = (UINT16) (GetBits (Sd, 4) + 3);
+ } else if (CharC == 2) {
+ CharC = (UINT16) (GetBits (Sd, CBIT) + 20);
+ }
+
+ while ((INT16) (--CharC) >= 0) {
+ Sd->mCLen[Index++] = 0;
+ }
+
+ } else {
+
+ Sd->mCLen[Index++] = (UINT8) (CharC - 2);
+
+ }
+ }
+
+ while (Index < NC) {
+ Sd->mCLen[Index++] = 0;
+ }
+
+ MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
+
+ return ;
+}
+
+UINT16
+DecodeC (
+ SCRATCH_DATA *Sd
+ )
+/*++
+
+Routine Description:
+
+ Decode a character/length value.
+
+Arguments:
+
+ Sd - The global scratch data.
+
+Returns:
+
+ The value decoded.
+
+--*/
+{
+ UINT16 Index2;
+ UINT32 Mask;
+
+ if (Sd->mBlockSize == 0) {
+ //
+ // Starting a new block
+ //
+ Sd->mBlockSize = (UINT16) GetBits (Sd, 16);
+ Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
+ if (Sd->mBadTableFlag != 0) {
+ return 0;
+ }
+
+ ReadCLen (Sd);
+
+ Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));
+ if (Sd->mBadTableFlag != 0) {
+ return 0;
+ }
+ }
+
+ Sd->mBlockSize--;
+ Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
+
+ if (Index2 >= NC) {
+ Mask = 1U << (BITBUFSIZ - 1 - 12);
+
+ do {
+ if (Sd->mBitBuf & Mask) {
+ Index2 = Sd->mRight[Index2];
+ } else {
+ Index2 = Sd->mLeft[Index2];
+ }
+
+ Mask >>= 1;
+ } while (Index2 >= NC);
+ }
+ //
+ // Advance what we have read
+ //
+ FillBuf (Sd, Sd->mCLen[Index2]);
+
+ return Index2;
+}
+
+VOID
+Decode (
+ SCRATCH_DATA *Sd
+ )
+/*++
+
+Routine Description:
+
+ Decode the source data and put the resulting data into the destination buffer.
+
+Arguments:
+
+ Sd - The global scratch data
+
+Returns: (VOID)
+
+ --*/
+{
+ UINT16 BytesRemain;
+ UINT32 DataIdx;
+ UINT16 CharC;
+
+ BytesRemain = (UINT16) (-1);
+
+ DataIdx = 0;
+
+ for (;;) {
+ CharC = DecodeC (Sd);
+ if (Sd->mBadTableFlag != 0) {
+ goto Done ;
+ }
+
+ if (CharC < 256) {
+ //
+ // Process an Original character
+ //
+ if (Sd->mOutBuf >= Sd->mOrigSize) {
+ goto Done ;
+ } else {
+ Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;
+ }
+
+ } else {
+ //
+ // Process a Pointer
+ //
+ CharC = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));
+
+ BytesRemain = CharC;
+
+ DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;
+
+ BytesRemain--;
+ while ((INT16) (BytesRemain) >= 0) {
+ Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];
+ if (Sd->mOutBuf >= Sd->mOrigSize) {
+ goto Done ;
+ }
+
+ BytesRemain--;
+ }
+ }
+ }
+
+Done:
+ return ;
+}
+
+RETURN_STATUS
+EFIAPI
+Decompress (
+ IN VOID *Source,
+ IN OUT VOID *Destination,
+ IN OUT VOID *Scratch,
+ IN UINT32 Version
+ )
+/*++
+
+Routine Description:
+
+ The internal implementation of Decompress().
+
+Arguments:
+
+ Source - The source buffer containing the compressed data.
+ Destination - The destination buffer to store the decompressed data
+ Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.
+ Version - 1 for EFI1.1 Decompress algoruthm, 2 for Tiano Decompress algorithm
+
+Returns:
+
+ RETURN_SUCCESS - Decompression is successfull
+ RETURN_INVALID_PARAMETER - The source data is corrupted
+
+--*/
+{
+ volatile UINT32 Index;
+ UINT32 CompSize;
+ UINT32 OrigSize;
+ SCRATCH_DATA *Sd;
+ CONST UINT8 *Src;
+ UINT8 *Dst;
+
+ //
+ // Verify input is not NULL
+ //
+ assert(Source);
+// assert(Destination);
+ assert(Scratch);
+
+ Src = (UINT8 *)Source;
+ Dst = (UINT8 *)Destination;
+
+ Sd = (SCRATCH_DATA *) Scratch;
+ CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24);
+ OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
+
+ //
+ // If compressed file size is 0, return
+ //
+ if (OrigSize == 0) {
+ return RETURN_SUCCESS;
+ }
+
+ Src = Src + 8;
+
+ for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) {
+ ((UINT8 *) Sd)[Index] = 0;
+ }
+ //
+ // The length of the field 'Position Set Code Length Array Size' in Block Header.
+ // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4
+ // For Tiano de/compression algorithm(Version 2), mPBit = 5
+ //
+ switch (Version) {
+ case 1 :
+ Sd->mPBit = 4;
+ break;
+ case 2 :
+ Sd->mPBit = 5;
+ break;
+ default:
+ assert(FALSE);
+ }
+ Sd->mSrcBase = (UINT8 *)Src;
+ Sd->mDstBase = Dst;
+ Sd->mCompSize = CompSize;
+ Sd->mOrigSize = OrigSize;
+
+ //
+ // Fill the first BITBUFSIZ bits
+ //
+ FillBuf (Sd, BITBUFSIZ);
+
+ //
+ // Decompress it
+ //
+
+ Decode (Sd);
+
+ if (Sd->mBadTableFlag != 0) {
+ //
+ // Something wrong with the source
+ //
+ return RETURN_INVALID_PARAMETER;
+ }
+
+ return RETURN_SUCCESS;
+}
+
+
|