/** @file
Main file for compression routine.
Compression routine. The compression algorithm is a mixture of
LZ77 and Huffman coding. LZ77 transforms the source data into a
sequence of Original Characters and Pointers to repeated strings.
This sequence is further divided into Blocks and Huffman codings
are applied to each Block.
Copyright (c) 2007 - 2011, 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.
**/
#include <Library/MemoryAllocationLib.h>
#include <Library/BaseMemoryLib.h>
#include <Library/DebugLib.h>
#include <ShellBase.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
//
/**
Put a dword to output stream
@param[in] Data The dword to put.
**/
);
//
// Global Variables
//
/**
Make a CRC table.
**/
)
{
if ((LoopVar4 & 1) != 0) {
} else {
LoopVar4 >>= 1;
}
}
}
}
/**
Put a dword to output stream
@param[in] Data The dword to put.
**/
PutDword (
)
{
if (mDst < mDstUpperLimit) {
}
if (mDst < mDstUpperLimit) {
}
if (mDst < mDstUpperLimit) {
}
if (mDst < mDstUpperLimit) {
}
}
/**
Allocate memory spaces for data structures used in compression process.
@retval EFI_SUCCESS Memory was allocated successfully.
@retval EFI_OUT_OF_RESOURCES A memory allocation failed.
**/
)
{
return EFI_OUT_OF_RESOURCES;
}
}
mBuf[0] = 0;
return EFI_SUCCESS;
}
/**
Called when compression is completed to free memory previously allocated.
**/
)
{
}
/**
Initialize String Info Log data structures.
**/
)
{
mAvail = 1;
}
}
/**
Find child node given the parent node and the edge character
@param[in] LoopVar6 The parent node.
@param[in] LoopVar5 The edge character.
@return The child node.
@retval NIL(Zero) No child could be found.
**/
Child (
)
{
}
return LoopVar4;
}
/**
Create a new child for a given parent node.
@param[in] LoopVar6 The parent node.
@param[in] LoopVar5 The edge character.
@param[in] LoopVar4 The child node.
**/
)
{
mChildCount[LoopVar6]++;
}
/**
Split a node.
@param[in] Old The node to split.
**/
Split (
)
{
mChildCount[New] = 0;
}
/**
Insert string info for current position into the String Info Log.
**/
)
{
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--;
}
}
}
}
} 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 (;;) {
} else {
}
}
if (*TempString3 != *TempString2) {
return ;
}
mMatchLen++;
TempString3++;
TempString2++;
}
break;
}
return ;
}
mMatchLen++;
}
//
// Special usage of 'next'
//
}
/**
Delete outdated string info. (The Usage of PERC_FLAG
ensures a clean deletion).
**/
)
{
return ;
}
return ;
}
mChildCount[LoopVar4]--;
return ;
}
}
}
}
}
}
}
}
}
/**
Read in source data
@param[out] LoopVar7 The buffer to hold the data.
@param[in] LoopVar8 The number of bytes to read.
@return The number of bytes actually read.
**/
FreadCrc (
)
{
}
LoopVar1--;
while (LoopVar1 >= 0) {
UPDATE_CRC (*LoopVar7++);
LoopVar1--;
}
return LoopVar8;
}
/**
Advance the current position (read in new data if needed).
Delete outdated string info. Find a match string for current position.
@retval TRUE The operation was successful.
@retval FALSE The operation failed due to insufficient memory.
**/
)
{
mRemainder--;
mPos++;
return (FALSE);
}
mRemainder += LoopVar8;
}
DeleteNode ();
InsertNode ();
return (TRUE);
}
/**
Send entry LoopVar1 down the queue.
@param[in] LoopVar1 The index of the item to move.
**/
DownHeap (
)
{
//
// priority queue: send i-th entry down heap
//
LoopVar1 = 2 * i;
LoopVar1++;
}
break;
}
i = LoopVar1;
LoopVar1 = 2 * i;
}
}
/**
Count the number of each code length for a Huffman tree.
@param[in] LoopVar1 The top node.
**/
CountLen (
)
{
if (LoopVar1 < mTempInt32) {
} else {
}
}
/**
Create code length array for a Huffman tree.
@param[in] Root The root of the tree.
**/
MakeLen (
)
{
}
//
// Adjust the length count array so that
// no code will be generated longer than its designated length
//
Cum = 0;
}
mLenCnt[16]--;
break;
}
}
Cum--;
}
LoopVar2--;
while (LoopVar2 >= 0) {
LoopVar2--;
}
}
}
/**
Assign code to each symbol based on the code length array.
@param[in] LoopVar8 The number of symbols.
@param[in] Len The code length array.
@param[out] Code The stores codes for each symbol.
**/
MakeCode (
)
{
Start[1] = 0;
}
}
}
/**
Generates Huffman codes given a frequency distribution of symbols.
@param[in] NParm The number of symbols.
@param[in] FreqParm The frequency of each symbol.
@param[out] LenParm The code length for each symbol.
@param[out] CodeParm The code for each symbol.
@return The root of the Huffman tree.
**/
MakeTree (
)
{
//
// make tree, calculate len[], return root
//
mTempInt32 = NParm;
Avail = mTempInt32;
mHeapSize = 0;
mHeap[1] = 0;
mHeapSize++;
}
}
if (mHeapSize < 2) {
return mHeap[1];
}
//
// make priority queue
//
}
do {
if (LoopVar1 < mTempInt32) {
}
DownHeap (1);
if (LoopVar2 < mTempInt32) {
}
DownHeap (1);
} while (mHeapSize > 1);
//
// return root
//
return LoopVar3;
}
/**
Outputs rightmost LoopVar8 bits of x
@param[in] LoopVar8 The rightmost LoopVar8 bits of the data is used.
@param[in] x The data.
**/
PutBits (
)
{
} else {
if (mDst < mDstUpperLimit) {
}
mCompSize++;
} else {
if (mDst < mDstUpperLimit) {
}
mCompSize++;
}
}
}
/**
Encode a signed 32 bit number.
@param[in] LoopVar5 The number to encode.
**/
EncodeC (
)
{
}
/**
Encode a unsigned 32 bit number.
@param[in] LoopVar7 The number to encode.
**/
EncodeP (
)
{
LoopVar5 = 0;
while (LoopVar6 != 0) {
LoopVar6 >>= 1;
LoopVar5++;
}
if (LoopVar5 > 1) {
}
}
/**
Count the frequencies for the Extra Set.
**/
)
{
}
LoopVar8--;
}
LoopVar1 = 0;
if (LoopVar3 == 0) {
Count = 1;
LoopVar1++;
Count++;
}
if (Count <= 2) {
} else if (Count <= 18) {
mTFreq[1]++;
} else if (Count == 19) {
mTFreq[0]++;
mTFreq[1]++;
} else {
mTFreq[2]++;
}
} else {
}
}
}
/**
Outputs the code length array for the Extra Set or the Position Set.
@param[in] LoopVar8 The number of symbols.
@param[in] nbit The number of bits needed to represent 'LoopVar8'.
@param[in] Special The special symbol that needs to be take care of.
**/
)
{
LoopVar8--;
}
LoopVar1 = 0;
if (LoopVar3 <= 6) {
} else {
}
LoopVar1++;
}
}
}
}
/**
Outputs the code length array for Char&Length Set.
**/
)
{
LoopVar8--;
}
LoopVar1 = 0;
if (LoopVar3 == 0) {
Count = 1;
LoopVar1++;
Count++;
}
if (Count <= 2) {
}
} else if (Count <= 18) {
} else if (Count == 19) {
} else {
}
} else {
}
}
}
/**
Huffman code the block and output it.
**/
)
{
Flags = 0;
CountTFreq ();
} else {
}
WriteCLen ();
} else {
}
} else {
}
Pos = 0;
} else {
Flags <<= 1;
}
} else {
}
}
}
/**
Start the huffman encoding.
**/
)
{
mOutputPos = mOutputMask = 0;
mSubBitBuf = 0;
}
/**
Outputs an Original Character or a Pointer.
@param[in] LoopVar5 The original character or the 'String Length' element of
a Pointer.
@param[in] LoopVar7 The 'Position' field of a Pointer.
**/
)
{
if ((mOutputMask >>= 1) == 0) {
SendBlock ();
mOutputPos = 0;
}
CPos = mOutputPos++;
}
LoopVar5 = 0;
while (LoopVar7!=0) {
LoopVar7 >>= 1;
LoopVar5++;
}
}
}
/**
End the huffman encoding.
**/
)
{
SendBlock ();
//
// Flush remaining bits
//
}
/**
The main controlling routine for compression process.
@retval EFI_SUCCESS The compression is successful.
@retval EFI_OUT_0F_RESOURCES Not enough memory for compression process.
**/
Encode (
)
{
Status = AllocateMemory ();
FreeMemory ();
return Status;
}
InitSlide ();
HufEncodeStart ();
mMatchLen = 0;
InsertNode ();
if (mMatchLen > mRemainder) {
}
while (mRemainder > 0) {
if (!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.
//
LastMatchLen--;
while (LastMatchLen > 0) {
if (!GetNextMatch ()) {
}
LastMatchLen--;
}
if (mMatchLen > mRemainder) {
}
}
}
HufEncodeEnd ();
FreeMemory ();
return (Status);
}
/**
The compression routine.
@param[in] SrcBuffer The buffer containing the source data.
@param[in] SrcSize The number of bytes in SrcBuffer.
@param[in] DstBuffer The buffer to put the compressed image in.
@param[in, out] DstSize On input the size (in bytes) of DstBuffer, on
return the number of bytes placed in DstBuffer.
@retval EFI_SUCCESS The compression was sucessful.
@retval EFI_BUFFER_TOO_SMALL The buffer was too small. DstSize is required.
**/
Compress (
)
{
//
// 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;
}
}