/** @file | |
Copyright (c) 2007 - 2010, 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. | |
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 UINT64 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; | |
} | |
} | |
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 %s \n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION, __BUILD_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 - 2010, 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; | |
} | |