=/*++
Copyright (c) 2001-2002 Intel Corporation
Module Name:
Decompress.c
Abstract:
Decompressor.
--*/
#include "EfiCommon.h"
#define BITBUFSIZ 16
#define WNDBIT 13
#define WNDSIZ (1U << WNDBIT)
#define MAXMATCH 256
#define THRESHOLD 3
#define CODE_BIT 16
#define UINT8_MAX 0xff
#define BAD_TABLE -1
//
// C: Char&Len Set; P: Position Set; T: exTra Set
//
#define NC (0xff + MAXMATCH + 2 - THRESHOLD)
#define CBIT 9
#define NP (WNDBIT + 1)
#define NT (CODE_BIT + 3)
#define PBIT 4
#define TBIT 5
#if NT > NP
#define NPT NT
#else
#define NPT NP
#endif
typedef struct {
UINT8 *mSrcBase; //Starting address of compressed data
UINT8 *mDstBase; //Starting address of decompressed data
UINT16 mBytesRemain;
UINT16 mBitCount;
UINT16 mBitBuf;
UINT16 mSubBitBuf;
UINT16 mBufSiz;
UINT16 mBlockSize;
UINT32 mDataIdx;
UINT32 mCompSize;
UINT32 mOrigSize;
UINT32 mOutBuf;
UINT32 mInBuf;
UINT16 mBadTableFlag;
UINT8 mBuffer[WNDSIZ];
UINT16 mLeft[2 * NC - 1];
UINT16 mRight[2 * NC - 1];
UINT32 mBuf;
UINT8 mCLen[NC];
UINT8 mPTLen[NPT];
UINT16 mCTable[4096];
UINT16 mPTTable[256];
} SCRATCH_DATA;
//
// Function Prototypes
//
STATIC
VOID
FillBuf (
IN SCRATCH_DATA *Sd,
IN UINT16 NumOfBits
);
STATIC
VOID
Decode (
SCRATCH_DATA *Sd,
UINT16 NumOfBytes
);
//
// Functions
//
EFI_STATUS
EFIAPI
GetInfo (
IN EFI_DECOMPRESS_PROTOCOL *This,
IN VOID *Source,
IN UINT32 SrcSize,
OUT UINT32 *DstSize,
OUT UINT32 *ScratchSize
)
/*++
Routine Description:
The implementation of EFI_DECOMPRESS_PROTOCOL.GetInfo().
Arguments:
This - Protocol instance pointer.
Source - The source buffer containing the compressed data.
SrcSize - The size of source buffer
DstSize - The size of destination buffer.
ScratchSize - The size of scratch buffer.
Returns:
EFI_SUCCESS - The size of destination buffer and the size of scratch
buffer are successful retrieved.
EFI_INVALID_PARAMETER - The source data is corrupted
--*/
{
UINT8 *Src;
*ScratchSize = sizeof (SCRATCH_DATA);
Src = Source;
if (SrcSize < 8) {
return EFI_INVALID_PARAMETER;
}
*DstSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24);
return EFI_SUCCESS;
}
EFI_STATUS
EFIAPI
Decompress (
IN EFI_DECOMPRESS_PROTOCOL *This,
IN VOID *Source,
IN UINT32 SrcSize,
IN OUT VOID *Destination,
IN UINT32 DstSize,
IN OUT VOID *Scratch,
IN UINT32 ScratchSize
)
/*++
Routine Description:
The implementation of EFI_DECOMPRESS_PROTOCOL.Decompress().
Arguments:
This - The protocol instance.
Source - The source buffer containing the compressed data.
SrcSize - The size of the source buffer
Destination - The destination buffer to store the decompressed data
DstSize - The size of the destination buffer.
Scratch - The buffer used internally by the decompress routine. This
buffer is needed to store intermediate data.
ScratchSize - The size of scratch buffer.
Returns:
EFI_SUCCESS - Decompression is successful
EFI_INVALID_PARAMETER - The source data is corrupted
--*/
{
UINT32 Index;
UINT16 Count;
UINT32 CompSize;
UINT32 OrigSize;
UINT8 *Dst1;
EFI_STATUS Status;
SCRATCH_DATA *Sd;
UINT8 *Src;
UINT8 *Dst;
Status = EFI_SUCCESS;
Src = Source;
Dst = Destination;
Dst1 = Dst;
if (ScratchSize < sizeof (SCRATCH_DATA)) {
return EFI_INVALID_PARAMETER;
}
Sd = (SCRATCH_DATA *)Scratch;
if (SrcSize < 8) {
return EFI_INVALID_PARAMETER;
}
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 (SrcSize < CompSize + 8) {
return EFI_INVALID_PARAMETER;
}
Src = Src + 8;
for (Index = 0; Index < sizeof(SCRATCH_DATA); Index++) {
((UINT8*)Sd)[Index] = 0;
}
Sd->mBytesRemain = (UINT16)(-1);
Sd->mSrcBase = Src;
Sd->mDstBase = Dst;
Sd->mCompSize = CompSize;
Sd->mOrigSize = OrigSize;
//
// Fill the first two bytes
//
FillBuf(Sd, BITBUFSIZ);
while (Sd->mOrigSize > 0) {
Count = (UINT16) (WNDSIZ < Sd->mOrigSize? WNDSIZ: Sd->mOrigSize);
Decode (Sd, Count);
if (Sd->mBadTableFlag != 0) {
//
// Something wrong with the source
//
return EFI_INVALID_PARAMETER;
}
for (Index = 0; Index < Count; Index ++) {
if (Dst1 < Dst + DstSize) {
*Dst1++ = Sd->mBuffer[Index];
} else {
return EFI_INVALID_PARAMETER;
}
}
Sd->mOrigSize -= Count;
}
if (Sd->mBadTableFlag != 0) {
Status = EFI_INVALID_PARAMETER;
} else {
Status = EFI_SUCCESS;
}
return Status;
}
STATIC
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
NumOfBit - The number of bits to shift and read.
Returns: (VOID)
--*/
{
Sd->mBitBuf = (UINT16)(Sd->mBitBuf << NumOfBits);
while (NumOfBits > Sd->mBitCount) {
Sd->mBitBuf \|= (UINT16)(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 {
Sd->mSubBitBuf = 0;
Sd->mBitCount = 8;
}
}
Sd->mBitCount = (UINT16)(Sd->mBitCount - NumOfBits);
Sd->mBitBuf \|= Sd->mSubBitBuf >> Sd->mBitCount;
}
STATIC
UINT16
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.
--*/
{
UINT16 OutBits;
OutBits = (UINT16)(Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));
FillBuf (Sd, NumOfBits);
return OutBits;
}
STATIC
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 *p;
UINT16 k;
UINT16 i;
UINT16 Len;
UINT16 Char;
UINT16 JuBits;
UINT16 Avail;
UINT16 NextCode;
UINT16 Mask;
for (i = 1; i <= 16; i ++) {
Count[i] = 0;
}
for (i = 0; i < NumOfChar; i++) {
Count[BitLen[i]]++;
}
Start[1] = 0;
for (i = 1; i <= 16; i ++) {
Start[i + 1] = (UINT16)(Start[i] + (Count[i] << (16 - i)));
}
if (Start[17] != 0) {/*(1U << 16)*/
return (UINT16)BAD_TABLE;
}
JuBits = (UINT16)(16 - TableBits);
for (i = 1; i <= TableBits; i ++) {
Start[i] >>= JuBits;
Weight[i] = (UINT16)(1U << (TableBits - i));
}
while (i <= 16) {
Weight[i++] = (UINT16)(1U << (16 - i));
}
i = (UINT16)(Start[TableBits + 1] >> JuBits);
if (i != 0) {
k = (UINT16)(1U << TableBits);
while (i != k) {
Table[i++] = 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 (i = Start[Len]; i < NextCode; i ++) {
Table[i] = Char;
}
} else {
k = Start[Len];
p = &Table[k >> JuBits];
i = (UINT16)(Len - TableBits);
while (i != 0) {
if (*p == 0) {
Sd->mRight[Avail] = Sd->mLeft[Avail] = 0;
*p = Avail ++;
}
if (k & Mask) {
p = &Sd->mRight[*p];
} else {
p = &Sd->mLeft[*p];
}
k <<= 1;
i --;
}
*p = Char;
}
Start[Len] = NextCode;
}
//
// Succeeds
//
return 0;
}
STATIC
UINT16
DecodeP (
IN SCRATCH_DATA *Sd
)
/*++
Routine description:
Decodes a position value.
Arguments:
Sd - the global scratch data
Returns:
The position value decoded.
--*/
{
UINT16 Val;
UINT16 Mask;
Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
if (Val >= NP) {
Mask = 1U << (BITBUFSIZ - 1 - 8);
do {
if (Sd->mBitBuf & Mask) {
Val = Sd->mRight[Val];
} else {
Val = Sd->mLeft[Val];
}
Mask >>= 1;
} while (Val >= NP);
}
//
// Advance what we have read
//
FillBuf (Sd, Sd->mPTLen[Val]);
if (Val) {
Val = (UINT16)((1U << (Val - 1)) + GetBits (Sd, (UINT16)(Val - 1)));
}
return Val;
}
STATIC
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 n;
UINT16 c;
UINT16 i;
UINT16 Mask;
n = GetBits (Sd, nbit);
if (n == 0) {
c = GetBits (Sd, nbit);
for ( i = 0; i < 256; i ++) {
Sd->mPTTable[i] = c;
}
for ( i = 0; i < nn; i++) {
Sd->mPTLen[i] = 0;
}
return 0;
}
i = 0;
while (i < n) {
c = (UINT16)(Sd->mBitBuf >> (BITBUFSIZ - 3));
if (c == 7) {
Mask = 1U << (BITBUFSIZ - 1 - 3);
while (Mask & Sd->mBitBuf) {
Mask >>= 1;
c += 1;
}
}
FillBuf (Sd, (UINT16)((c < 7) ? 3 : c - 3));
Sd->mPTLen [i++] = (UINT8)c;
if (i == Special) {
c = GetBits (Sd, 2);
while ((INT16)(--c) >= 0) {
Sd->mPTLen[i++] = 0;
}
}
}
while (i < nn) {
Sd->mPTLen [i++] = 0;
}
return ( MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable) );
}
STATIC
VOID
ReadCLen (
SCRATCH_DATA *Sd
)
/*++
Routine Description:
Reads code lengths for Char&Len Set.
Arguments:
Sd - the global scratch data
Returns: (VOID)
--*/
{
UINT16 n;
UINT16 c;
UINT16 i;
UINT16 Mask;
n = GetBits(Sd, CBIT);
if (n == 0) {
c = GetBits(Sd, CBIT);
for (i = 0; i < NC; i ++) {
Sd->mCLen[i] = 0;
}
for (i = 0; i < 4096; i ++) {
Sd->mCTable[i] = c;
}
return;
}
i = 0;
while (i < n) {
c = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];
if (c >= NT) {
Mask = 1U << (BITBUFSIZ - 1 - 8);
do {
if (Mask & Sd->mBitBuf) {
c = Sd->mRight [c];
} else {
c = Sd->mLeft [c];
}
Mask >>= 1;
}while (c >= NT);
}
//
// Advance what we have read
//
FillBuf (Sd, Sd->mPTLen[c]);
if (c <= 2) {
if (c == 0) {
c = 1;
} else if (c == 1) {
c = (UINT16)(GetBits (Sd, 4) + 3);
} else if (c == 2) {
c = (UINT16)(GetBits (Sd, CBIT) + 20);
}
while ((INT16)(--c) >= 0) {
Sd->mCLen[i++] = 0;
}
} else {
Sd->mCLen[i++] = (UINT8)(c - 2);
}
}
while (i < NC) {
Sd->mCLen[i++] = 0;
}
MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable);
return;
}
STATIC
UINT16
DecodeC (
SCRATCH_DATA *Sd
)
/*++
Routine Description:
Decode a character/length value.
Arguments:
Sd - The global scratch data.
Returns:
The value decoded.
--*/
{
UINT16 j;
UINT16 Mask;
if (Sd->mBlockSize == 0) {
//
// Starting a new block
//
Sd->mBlockSize = GetBits(Sd, 16);
Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);
if (Sd->mBadTableFlag != 0) {
return 0;
}
ReadCLen (Sd);
Sd->mBadTableFlag = ReadPTLen (Sd, NP, PBIT, (UINT16)(-1));
if (Sd->mBadTableFlag != 0) {
return 0;
}
}
Sd->mBlockSize --;
j = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];
if (j >= NC) {
Mask = 1U << (BITBUFSIZ - 1 - 12);
do {
if (Sd->mBitBuf & Mask) {
j = Sd->mRight[j];
} else {
j = Sd->mLeft[j];
}
Mask >>= 1;
} while (j >= NC);
}
//
// Advance what we have read
//
FillBuf(Sd, Sd->mCLen[j]);
return j;
}
STATIC
VOID
Decode (
SCRATCH_DATA *Sd,
UINT16 NumOfBytes
)
/*++
Routine Description:
Decode NumOfBytes and put the resulting data at starting point of mBuffer.
The buffer is circular.
Arguments:
Sd - The global scratch data
NumOfBytes - Number of bytes to decode
Returns: (VOID)
--*/
{
UINT16 di;
UINT16 r;
UINT16 c;
r = 0;
di = 0;
Sd->mBytesRemain --;
while ((INT16)(Sd->mBytesRemain) >= 0) {
Sd->mBuffer[di++] = Sd->mBuffer[Sd->mDataIdx++];
if (Sd->mDataIdx >= WNDSIZ) {
Sd->mDataIdx -= WNDSIZ;
}
r ++;
if (r >= NumOfBytes) {
return;
}
Sd->mBytesRemain --;
}
for (;;) {
c = DecodeC (Sd);
if (Sd->mBadTableFlag != 0) {
return;
}
if (c < 256) {
//
// Process an Original character
//
Sd->mBuffer[di++] = (UINT8)c;
r ++;
if (di >= WNDSIZ) {
return;
}
} else {
//
// Process a Pointer
//
c = (UINT16)(c - (UINT8_MAX + 1 - THRESHOLD));
Sd->mBytesRemain = c;
Sd->mDataIdx = (r - DecodeP(Sd) - 1) & (WNDSIZ - 1); //Make circular
di = r;
Sd->mBytesRemain --;
while ((INT16)(Sd->mBytesRemain) >= 0) {
Sd->mBuffer[di++] = Sd->mBuffer[Sd->mDataIdx++];
if (Sd->mDataIdx >= WNDSIZ) {
Sd->mDataIdx -= WNDSIZ;
}
r ++;
if (di >= WNDSIZ) {
return;
}
Sd->mBytesRemain --;
}
}
return;
}