/** @file
Compression routine. The compression algorithm is a mixture of LZ77 and Huffman
coding. LZ77 transforms the source data into a sequence of Original Characters
and Pointers to repeated strings.
This sequence is further divided into Blocks and Huffman codings are applied to
each Block.
Copyright (c) 2007 - 2014, Intel Corporation. All rights reserved.<BR>
This program and the accompanying materials
are licensed and made available under the terms and conditions of the BSD License
which accompanies this distribution. The full text of the license may be found at
http://opensource.org/licenses/bsd-license.php
THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
**/
#include "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 (LongFilePath (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 - 2014, 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 (LongFilePath (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 (LongFilePath (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 (LongFilePath (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;
}