/** @file
Copyright (c) 2006 - 2008, 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
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:
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"
//
// Macro Definitions
//
#define INIT_CRC 0
#define NIL 0
//
// C: the Char&Len Set; P: the Position Set; T: the exTra Set
//
#else
#endif
//
// Function Prototypes
//
);
);
);
);
Child (
);
);
Split (
);
);
);
);
Encode (
);
);
);
);
EncodeC (
);
EncodeP (
);
);
Output (
);
);
);
);
PutBits (
);
FreadCrc (
);
);
CountLen (
);
MakeLen (
);
DownHeap (
);
MakeCode (
);
MakeTree (
);
//
// Global Variables
//
//
// functions
//
)
/*++
Routine Description:
The main compression routine.
Arguments:
SrcBuffer - The buffer storing the source data
SrcSize - The size of source data
DstBuffer - The buffer to store the compressed data
DstSize - On input, the size of DstBuffer; On output,
the size of the actual compressed data.
Returns:
EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case,
DstSize contains the size needed.
EFI_SUCCESS - Compression is successful.
--*/
{
//
// Initializations
//
mBufSiz = 0;
mChildCount = NULL;
PutDword(0L);
PutDword(0L);
MakeCrcTable ();
//
// Compress it
//
return EFI_OUT_OF_RESOURCES;
}
//
// Null terminate the compressed data
//
if (mDst < mDstUpperLimit) {
*mDst++ = 0;
}
//
// Fill in compressed size and original size
//
//
// Return
//
return EFI_BUFFER_TOO_SMALL;
} else {
return EFI_SUCCESS;
}
}
)
/*++
Routine Description:
Put a dword to output stream
Arguments:
Data - the dword to put
Returns: (VOID)
--*/
{
if (mDst < mDstUpperLimit) {
}
if (mDst < mDstUpperLimit) {
}
if (mDst < mDstUpperLimit) {
}
if (mDst < mDstUpperLimit) {
}
}
/*++
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 i;
mText[i] = 0;
}
return EFI_OUT_OF_RESOURCES;
}
}
mBuf[0] = 0;
return EFI_SUCCESS;
}
FreeMemory ()
/*++
Routine Description:
Called when compression is completed to free memory previously allocated.
Arguments: (VOID)
Returns: (VOID)
--*/
{
if (mText) {
}
if (mLevel) {
}
if (mChildCount) {
free (mChildCount);
}
if (mPosition) {
}
if (mParent) {
}
if (mPrev) {
}
if (mNext) {
}
if (mBuf) {
}
return;
}
InitSlide ()
/*++
Routine Description:
Initialize String Info Log data structures
Arguments: (VOID)
Returns: (VOID)
--*/
{
NODE i;
mLevel[i] = 1;
}
}
mAvail = 1;
}
}
}
Child (
)
/*++
Routine Description:
Find child node given the parent node and the edge character
Arguments:
q - the parent node
c - the edge character
Returns:
The child node (NIL if not found)
--*/
{
NODE r;
while (mParent[r] != q) {
r = mNext[r];
}
return r;
}
)
/*++
Routine Description:
Create a new child for a given parent node.
Arguments:
q - the parent node
c - the edge character
r - the child node
Returns: (VOID)
--*/
{
NODE h, t;
t = mNext[h];
mNext[h] = r;
mNext[r] = t;
mPrev[t] = r;
mPrev[r] = h;
mParent[r] = q;
mChildCount[q]++;
}
Split (
)
/*++
Routine Description:
Split a node.
Arguments:
Old - the node to split
Returns: (VOID)
--*/
{
mChildCount[New] = 0;
}
InsertNode ()
/*++
Routine Description:
Insert string info for current position into the String Info Log
Arguments: (VOID)
Returns: (VOID)
--*/
{
NODE q, r, j, t;
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--;
r = mNext[r];
}
r = q; q = mParent[q];
}
t = q;
while (mPosition[t] < 0) {
t = mParent[t];
}
if (t < WNDSIZ) {
}
} else {
//
// Locate the target tree
//
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 (r >= WNDSIZ) {
j = MAXMATCH;
mMatchPos = r;
} else {
j = mLevel[r];
}
}
while (mMatchLen < j) {
Split(r);
return;
}
mMatchLen++;
t1++;
t2++;
}
break;
}
q = r;
return;
}
mMatchLen++;
}
t = mPrev[r];
t = mNext[r];
//
// Special usage of 'next'
//
}
DeleteNode ()
/*++
Routine Description:
Delete outdated string info. (The Usage of PERC_FLAG
ensures a clean deletion)
Arguments: (VOID)
Returns: (VOID)
--*/
{
NODE q, r, s, t, u;
return;
}
mNext[r] = s;
mPrev[s] = r;
return;
}
if (t >= mPos) {
t -= WNDSIZ;
}
s = t;
q = mParent[r];
u &= ~PERC_FLAG;
if (u >= mPos) {
u -= WNDSIZ;
}
if (u > s) {
s = u;
}
q = mParent[q];
}
if (q < WNDSIZ) {
if (u >= mPos) {
u -= WNDSIZ;
}
if (u > s) {
s = u;
}
}
t = mPrev[s];
u = mNext[s];
mNext[t] = u;
mPrev[u] = t;
t = mPrev[r];
mNext[t] = s;
mPrev[s] = t;
t = mNext[r];
mPrev[t] = s;
mNext[s] = t;
mAvail = r;
}
GetNextMatch ()
/*++
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 n;
mRemainder--;
mRemainder += n;
}
DeleteNode();
InsertNode();
}
Encode ()
/*++
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
--*/
{
Status = AllocateMemory();
FreeMemory();
return Status;
}
InitSlide();
mMatchLen = 0;
InsertNode();
if (mMatchLen > mRemainder) {
}
while (mRemainder > 0) {
GetNextMatch();
if (mMatchLen > mRemainder) {
}
//
// Not enough benefits are gained by outputting a pointer,
// so just output the original character
//
} else {
//
// Outputting a pointer is beneficial enough, do it.
//
while (--LastMatchLen > 0) {
GetNextMatch();
}
if (mMatchLen > mRemainder) {
}
}
}
HufEncodeEnd();
FreeMemory();
return EFI_SUCCESS;
}
CountTFreq ()
/*++
Routine Description:
Count the frequencies for the Extra Set
Arguments: (VOID)
Returns: (VOID)
--*/
{
for (i = 0; i < NT; i++) {
mTFreq[i] = 0;
}
n = NC;
while (n > 0 && mCLen[n - 1] == 0) {
n--;
}
i = 0;
while (i < n) {
k = mCLen[i++];
if (k == 0) {
Count = 1;
while (i < n && mCLen[i] == 0) {
i++;
Count++;
}
if (Count <= 2) {
} else if (Count <= 18) {
mTFreq[1]++;
} else if (Count == 19) {
mTFreq[0]++;
mTFreq[1]++;
} else {
mTFreq[2]++;
}
} else {
mTFreq[k + 2]++;
}
}
}
)
/*++
Routine Description:
Outputs the code length array for the Extra Set or the Position Set.
Arguments:
n - 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 i, k;
while (n > 0 && mPTLen[n - 1] == 0) {
n--;
}
i = 0;
while (i < n) {
k = mPTLen[i++];
if (k <= 6) {
PutBits(3, k);
} else {
}
if (i == Special) {
while (i < 6 && mPTLen[i] == 0) {
i++;
}
}
}
}
WriteCLen ()
/*++
Routine Description:
Outputs the code length array for Char&Length Set
Arguments: (VOID)
Returns: (VOID)
--*/
{
n = NC;
while (n > 0 && mCLen[n - 1] == 0) {
n--;
}
i = 0;
while (i < n) {
k = mCLen[i++];
if (k == 0) {
Count = 1;
while (i < n && mCLen[i] == 0) {
i++;
Count++;
}
if (Count <= 2) {
for (k = 0; k < Count; k++) {
}
} else if (Count <= 18) {
} else if (Count == 19) {
} else {
}
} else {
}
}
}
EncodeC (
)
{
}
EncodeP (
)
{
UINT32 c, q;
c = 0;
q = p;
while (q) {
q >>= 1;
c++;
}
if (c > 1) {
}
}
SendBlock ()
/*++
Routine Description:
Huffman code the block and output it.
Argument: (VOID)
Returns: (VOID)
--*/
{
Flags = 0;
CountTFreq();
} else {
}
WriteCLen();
} else {
}
} else {
}
Pos = 0;
for (i = 0; i < Size; i++) {
if (i % UINT8_BIT == 0) {
} else {
Flags <<= 1;
}
EncodeP(k);
} else {
}
}
for (i = 0; i < NC; i++) {
mCFreq[i] = 0;
}
for (i = 0; i < NP; i++) {
mPFreq[i] = 0;
}
}
Output (
)
/*++
Routine Description:
Outputs an Original Character or a Pointer
Arguments:
c - The original character or the 'String Length' element of a Pointer
p - The 'Position' field of a Pointer
Returns: (VOID)
--*/
{
if ((mOutputMask >>= 1) == 0) {
SendBlock();
mOutputPos = 0;
}
CPos = mOutputPos++;
}
mCFreq[c]++;
if (c >= (1U << UINT8_BIT)) {
c = 0;
while (p) {
p >>= 1;
c++;
}
mPFreq[c]++;
}
}
{
INT32 i;
for (i = 0; i < NC; i++) {
mCFreq[i] = 0;
}
for (i = 0; i < NP; i++) {
mPFreq[i] = 0;
}
mOutputPos = mOutputMask = 0;
InitPutBits();
return;
}
HufEncodeEnd ()
{
SendBlock();
//
// Flush remaining bits
//
return;
}
MakeCrcTable ()
{
UINT32 i, j, r;
for (i = 0; i <= UINT8_MAX; i++) {
r = i;
for (j = 0; j < UINT8_BIT; j++) {
if (r & 1) {
r = (r >> 1) ^ CRCPOLY;
} else {
r >>= 1;
}
}
}
}
PutBits (
)
/*++
Routine Description:
Outputs rightmost n bits of x
Argments:
n - the rightmost n bits of the data is used
x - the data
Returns: (VOID)
--*/
{
if (n < mBitCount) {
mSubBitBuf |= x << (mBitCount -= n);
} else {
if (mDst < mDstUpperLimit) {
}
mCompSize++;
if (n < UINT8_BIT) {
} else {
if (mDst < mDstUpperLimit) {
}
mCompSize++;
}
}
}
FreadCrc (
)
/*++
Routine Description:
Read in source data
Arguments:
p - the buffer to hold the data
n - number of bytes to read
Returns:
number of bytes actually read
--*/
{
INT32 i;
for (i = 0; mSrc < mSrcUpperLimit && i < n; i++) {
*p++ = *mSrc++;
}
n = i;
p -= n;
mOrigSize += n;
while (--i >= 0) {
UPDATE_CRC(*p++);
}
return n;
}
InitPutBits ()
{
mSubBitBuf = 0;
}
CountLen (
)
/*++
Routine Description:
Count the number of each code length for a Huffman tree.
Arguments:
i - the top node
Returns: (VOID)
--*/
{
if (i < mN) {
} else {
Depth++;
Depth--;
}
}
MakeLen (
)
/*++
Routine Description:
Create code length array for a Huffman tree
Arguments:
Root - the root of the tree
--*/
{
INT32 i, k;
for (i = 0; i <= 16; i++) {
mLenCnt[i] = 0;
}
//
// Adjust the length count array so that
// no code will be generated longer than its designated length
//
Cum = 0;
for (i = 16; i > 0; i--) {
}
mLenCnt[16]--;
for (i = 15; i > 0; i--) {
if (mLenCnt[i] != 0) {
mLenCnt[i]--;
break;
}
}
Cum--;
}
for (i = 16; i > 0; i--) {
k = mLenCnt[i];
while (--k >= 0) {
}
}
}
DownHeap (
)
{
INT32 j, k;
//
// priority queue: send i-th entry down heap
//
k = mHeap[i];
while ((j = 2 * i) <= mHeapSize) {
j++;
}
break;
}
i = j;
}
}
MakeCode (
)
/*++
Routine Description:
Assign code to each symbol based on the code length array
Arguments:
n - number of symbols
Len - the code length array
Code - stores codes for each symbol
Returns: (VOID)
--*/
{
INT32 i;
Start[1] = 0;
for (i = 1; i <= 16; i++) {
}
for (i = 0; i < n; i++) {
}
}
MakeTree (
)
/*++
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.
--*/
{
//
// make tree, calculate len[], return root
//
mHeapSize = 0;
mHeap[1] = 0;
for (i = 0; i < mN; i++) {
mLen[i] = 0;
if (mFreq[i]) {
}
}
if (mHeapSize < 2) {
return mHeap[1];
}
//
// make priority queue
//
DownHeap(i);
}
do {
i = mHeap[1];
if (i < mN) {
}
DownHeap(1);
j = mHeap[1];
if (j < mN) {
}
k = Avail++;
DownHeap(1);
} while (mHeapSize > 1);
MakeLen(k);
//
// return root
//
return k;
}