X-Git-Url: https://git.proxmox.com/?p=mirror_edk2.git;a=blobdiff_plain;f=BaseTools%2FSource%2FC%2FCommon%2FEfiCompress.c;h=33d4c5eec1e763d2bcf98326fe0c9e82a3c121a7;hp=b225fee913bec3369eb4f92cd5137b36a85a59fd;hb=f7496d717357b9af78414d19679b073403812340;hpb=39456d00f36e04b7e7efb208f350f4e83b6c3531
diff --git a/BaseTools/Source/C/Common/EfiCompress.c b/BaseTools/Source/C/Common/EfiCompress.c
index b225fee913..33d4c5eec1 100644
--- a/BaseTools/Source/C/Common/EfiCompress.c
+++ b/BaseTools/Source/C/Common/EfiCompress.c
@@ -1,17 +1,17 @@
/** @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
+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) 2006 - 2014, Intel Corporation. All rights reserved.
-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.
+
+Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.
+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.
**/
@@ -60,13 +60,13 @@ typedef INT16 NODE;
//
STATIC
-VOID
+VOID
PutDword(
IN UINT32 Data
);
STATIC
-EFI_STATUS
+EFI_STATUS
AllocateMemory (
);
@@ -75,160 +75,160 @@ VOID
FreeMemory (
);
-STATIC
-VOID
+STATIC
+VOID
InitSlide (
);
-STATIC
-NODE
+STATIC
+NODE
Child (
- IN NODE q,
+ IN NODE q,
IN UINT8 c
);
-STATIC
-VOID
+STATIC
+VOID
MakeChild (
- IN NODE q,
- IN UINT8 c,
+ IN NODE q,
+ IN UINT8 c,
IN NODE r
);
-
-STATIC
-VOID
+
+STATIC
+VOID
Split (
IN NODE Old
);
-STATIC
-VOID
+STATIC
+VOID
InsertNode (
);
-
-STATIC
-VOID
+
+STATIC
+VOID
DeleteNode (
);
-STATIC
-VOID
+STATIC
+VOID
GetNextMatch (
);
-
-STATIC
-EFI_STATUS
+
+STATIC
+EFI_STATUS
Encode (
);
-STATIC
-VOID
+STATIC
+VOID
CountTFreq (
);
-STATIC
-VOID
+STATIC
+VOID
WritePTLen (
- IN INT32 n,
- IN INT32 nbit,
+ IN INT32 n,
+ IN INT32 nbit,
IN INT32 Special
);
-STATIC
-VOID
+STATIC
+VOID
WriteCLen (
);
-
-STATIC
-VOID
+
+STATIC
+VOID
EncodeC (
IN INT32 c
);
-STATIC
-VOID
+STATIC
+VOID
EncodeP (
IN UINT32 p
);
-STATIC
-VOID
+STATIC
+VOID
SendBlock (
);
-
-STATIC
-VOID
+
+STATIC
+VOID
Output (
- IN UINT32 c,
+ IN UINT32 c,
IN UINT32 p
);
-STATIC
-VOID
+STATIC
+VOID
HufEncodeStart (
);
-
-STATIC
-VOID
+
+STATIC
+VOID
HufEncodeEnd (
);
-
-STATIC
-VOID
+
+STATIC
+VOID
MakeCrcTable (
);
-
-STATIC
-VOID
+
+STATIC
+VOID
PutBits (
- IN INT32 n,
+ IN INT32 n,
IN UINT32 x
);
-
-STATIC
-INT32
+
+STATIC
+INT32
FreadCrc (
- OUT UINT8 *p,
+ OUT UINT8 *p,
IN INT32 n
);
-
-STATIC
-VOID
+
+STATIC
+VOID
InitPutBits (
);
-
-STATIC
-VOID
+
+STATIC
+VOID
CountLen (
IN INT32 i
);
-STATIC
-VOID
+STATIC
+VOID
MakeLen (
IN INT32 Root
);
-
-STATIC
-VOID
+
+STATIC
+VOID
DownHeap (
IN INT32 i
);
-STATIC
-VOID
+STATIC
+VOID
MakeCode (
- IN INT32 n,
- IN UINT8 Len[],
+ IN INT32 n,
+ IN UINT8 Len[],
OUT UINT16 Code[]
);
-
-STATIC
-INT32
+
+STATIC
+INT32
MakeTree (
- IN INT32 NParm,
- IN UINT16 FreqParm[],
- OUT UINT8 LenParm[],
+ IN INT32 NParm,
+ IN UINT16 FreqParm[],
+ OUT UINT8 LenParm[],
OUT UINT16 CodeParm[]
);
@@ -286,7 +286,7 @@ Returns:
--*/
{
EFI_STATUS Status = EFI_SUCCESS;
-
+
//
// Initializations
//
@@ -300,7 +300,7 @@ Returns:
mPrev = NULL;
mNext = NULL;
-
+
mSrc = SrcBuffer;
mSrcUpperLimit = mSrc + SrcSize;
mDst = DstBuffer;
@@ -308,28 +308,28 @@ Returns:
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
//
@@ -340,7 +340,7 @@ Returns:
//
// Return
//
-
+
if (mCompSize + 1 + 8 > *DstSize) {
*DstSize = mCompSize + 1 + 8;
return EFI_BUFFER_TOO_SMALL;
@@ -351,8 +351,8 @@ Returns:
}
-STATIC
-VOID
+STATIC
+VOID
PutDword(
IN UINT32 Data
)
@@ -361,13 +361,13 @@ PutDword(
Routine Description:
Put a dword to output stream
-
+
Arguments:
Data - the dword to put
-
+
Returns: (VOID)
-
+
--*/
{
if (mDst < mDstUpperLimit) {
@@ -395,7 +395,7 @@ AllocateMemory ()
Routine Description:
Allocate memory spaces for data structures used in compression process
-
+
Argements: (VOID)
Returns:
@@ -406,7 +406,7 @@ Returns:
--*/
{
UINT32 i;
-
+
mText = malloc (WNDSIZ * 2 + MAXMATCH);
if (mText == NULL) {
return EFI_OUT_OF_RESOURCES;
@@ -425,7 +425,7 @@ Returns:
mParent == NULL || mPrev == NULL || mNext == NULL) {
return EFI_OUT_OF_RESOURCES;
}
-
+
mBufSiz = 16 * 1024U;
while ((mBuf = malloc(mBufSiz)) == NULL) {
mBufSiz = (mBufSiz / 10U) * 9U;
@@ -434,7 +434,7 @@ Returns:
}
}
mBuf[0] = 0;
-
+
return EFI_SUCCESS;
}
@@ -445,7 +445,7 @@ FreeMemory ()
Routine Description:
Called when compression is completed to free memory previously allocated.
-
+
Arguments: (VOID)
Returns: (VOID)
@@ -455,48 +455,48 @@ Returns: (VOID)
if (mText) {
free (mText);
}
-
+
if (mLevel) {
free (mLevel);
}
-
+
if (mChildCount) {
free (mChildCount);
}
-
+
if (mPosition) {
free (mPosition);
}
-
+
if (mParent) {
free (mParent);
}
-
+
if (mPrev) {
free (mPrev);
}
-
+
if (mNext) {
free (mNext);
}
-
+
if (mBuf) {
free (mBuf);
- }
+ }
return;
}
-STATIC
-VOID
+STATIC
+VOID
InitSlide ()
/*++
Routine Description:
Initialize String Info Log data structures
-
+
Arguments: (VOID)
Returns: (VOID)
@@ -511,23 +511,23 @@ Returns: (VOID)
}
for (i = WNDSIZ; i < WNDSIZ * 2; i++) {
mParent[i] = NIL;
- }
+ }
mAvail = 1;
for (i = 1; i < WNDSIZ - 1; i++) {
mNext[i] = (NODE)(i + 1);
}
-
+
mNext[WNDSIZ - 1] = NIL;
for (i = WNDSIZ * 2; i <= MAX_HASH_VAL; i++) {
mNext[i] = NIL;
- }
+ }
}
-STATIC
-NODE
+STATIC
+NODE
Child (
- IN NODE q,
+ IN NODE q,
IN UINT8 c
)
/*++
@@ -535,34 +535,34 @@ 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)
-
+ The child node (NIL if not found)
+
--*/
{
NODE r;
-
+
r = mNext[HASH(q, c)];
mParent[NIL] = q; /* sentinel */
while (mParent[r] != q) {
r = mNext[r];
}
-
+
return r;
}
-STATIC
-VOID
+STATIC
+VOID
MakeChild (
- IN NODE q,
- IN UINT8 c,
+ IN NODE q,
+ IN UINT8 c,
IN NODE r
)
/*++
@@ -570,19 +570,19 @@ MakeChild (
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;
-
+
h = (NODE)HASH(q, c);
t = mNext[h];
mNext[h] = r;
@@ -593,8 +593,8 @@ Returns: (VOID)
mChildCount[q]++;
}
-STATIC
-VOID
+STATIC
+VOID
Split (
NODE Old
)
@@ -603,11 +603,11 @@ Split (
Routine Description:
Split a node.
-
+
Arguments:
Old - the node to split
-
+
Returns: (VOID)
--*/
@@ -630,15 +630,15 @@ Returns: (VOID)
MakeChild(New, mText[mPos + mMatchLen], mPos);
}
-STATIC
-VOID
+STATIC
+VOID
InsertNode ()
/*++
Routine Description:
Insert string info for current position into the String Info Log
-
+
Arguments: (VOID)
Returns: (VOID)
@@ -649,7 +649,7 @@ Returns: (VOID)
UINT8 c, *t1, *t2;
if (mMatchLen >= 4) {
-
+
//
// We have just got a long match, the target tree
// can be located by MatchPos + 1. Travese the tree
@@ -657,7 +657,7 @@ Returns: (VOID)
// The usage of PERC_FLAG ensures proper node deletion
// in DeleteNode() later.
//
-
+
mMatchLen--;
r = (INT16)((mMatchPos + 1) | WNDSIZ);
while ((q = mParent[r]) == NIL) {
@@ -673,13 +673,13 @@ Returns: (VOID)
}
if (t < WNDSIZ) {
mPosition[t] = (NODE)(mPos | PERC_FLAG);
- }
+ }
} else {
-
+
//
// Locate the target tree
//
-
+
q = (INT16)(mText[mPos] + WNDSIZ);
c = mText[mPos + 1];
if ((r = Child(q, c)) == NIL) {
@@ -689,13 +689,13 @@ Returns: (VOID)
}
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;
@@ -706,7 +706,7 @@ Returns: (VOID)
}
if (mMatchPos >= mPos) {
mMatchPos -= WNDSIZ;
- }
+ }
t1 = &mText[mPos + mMatchLen];
t2 = &mText[mMatchPos + mMatchLen];
while (mMatchLen < j) {
@@ -737,16 +737,16 @@ Returns: (VOID)
mPrev[t] = mPos;
mParent[mPos] = q;
mParent[r] = NIL;
-
+
//
// Special usage of 'next'
//
mNext[r] = mPos;
-
+
}
-STATIC
-VOID
+STATIC
+VOID
DeleteNode ()
/*++
@@ -754,7 +754,7 @@ Routine Description:
Delete outdated string info. (The Usage of PERC_FLAG
ensures a clean deletion)
-
+
Arguments: (VOID)
Returns: (VOID)
@@ -766,7 +766,7 @@ Returns: (VOID)
if (mParent[mPos] == NIL) {
return;
}
-
+
r = mPrev[mPos];
s = mNext[mPos];
mNext[r] = s;
@@ -819,8 +819,8 @@ Returns: (VOID)
mAvail = r;
}
-STATIC
-VOID
+STATIC
+VOID
GetNextMatch ()
/*++
@@ -860,7 +860,7 @@ Routine Description:
Arguments: (VOID)
Returns:
-
+
EFI_SUCCESS - The compression is successful
EFI_OUT_0F_RESOURCES - Not enough memory for compression process
@@ -877,11 +877,11 @@ Returns:
}
InitSlide();
-
+
HufEncodeStart();
mRemainder = FreadCrc(&mText[WNDSIZ], WNDSIZ + MAXMATCH);
-
+
mMatchLen = 0;
mPos = WNDSIZ;
InsertNode();
@@ -895,21 +895,21 @@ Returns:
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 {
-
+
//
// Outputting a pointer is beneficial enough, do it.
//
-
+
Output(LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),
(mPos - LastMatchPos - 2) & (WNDSIZ - 1));
while (--LastMatchLen > 0) {
@@ -920,21 +920,21 @@ Returns:
}
}
}
-
+
HufEncodeEnd();
FreeMemory();
return EFI_SUCCESS;
}
-STATIC
-VOID
+STATIC
+VOID
CountTFreq ()
/*++
Routine Description:
Count the frequencies for the Extra Set
-
+
Arguments: (VOID)
Returns: (VOID)
@@ -975,11 +975,11 @@ Returns: (VOID)
}
}
-STATIC
-VOID
+STATIC
+VOID
WritePTLen (
- IN INT32 n,
- IN INT32 nbit,
+ IN INT32 n,
+ IN INT32 nbit,
IN INT32 Special
)
/*++
@@ -987,13 +987,13 @@ WritePTLen (
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)
--*/
@@ -1021,15 +1021,15 @@ Returns: (VOID)
}
}
-STATIC
-VOID
+STATIC
+VOID
WriteCLen ()
/*++
Routine Description:
Outputs the code length array for Char&Length Set
-
+
Arguments: (VOID)
Returns: (VOID)
@@ -1073,8 +1073,8 @@ Returns: (VOID)
}
}
-STATIC
-VOID
+STATIC
+VOID
EncodeC (
IN INT32 c
)
@@ -1082,8 +1082,8 @@ EncodeC (
PutBits(mCLen[c], mCCode[c]);
}
-STATIC
-VOID
+STATIC
+VOID
EncodeP (
IN UINT32 p
)
@@ -1102,15 +1102,15 @@ EncodeP (
}
}
-STATIC
-VOID
+STATIC
+VOID
SendBlock ()
/*++
Routine Description:
Huffman code the block and output it.
-
+
Argument: (VOID)
Returns: (VOID)
@@ -1171,10 +1171,10 @@ Returns: (VOID)
}
-STATIC
-VOID
+STATIC
+VOID
Output (
- IN UINT32 c,
+ IN UINT32 c,
IN UINT32 p
)
/*++
@@ -1200,7 +1200,7 @@ Returns: (VOID)
SendBlock();
mOutputPos = 0;
}
- CPos = mOutputPos++;
+ CPos = mOutputPos++;
mBuf[CPos] = 0;
}
mBuf[mOutputPos++] = (UINT8) c;
@@ -1235,23 +1235,23 @@ HufEncodeStart ()
return;
}
-STATIC
-VOID
+STATIC
+VOID
HufEncodeEnd ()
{
SendBlock();
-
+
//
// Flush remaining bits
//
PutBits(UINT8_BIT - 1, 0);
-
+
return;
}
-STATIC
-VOID
+STATIC
+VOID
MakeCrcTable ()
{
UINT32 i, j, r;
@@ -1265,14 +1265,14 @@ MakeCrcTable ()
r >>= 1;
}
}
- mCrcTable[i] = (UINT16)r;
+ mCrcTable[i] = (UINT16)r;
}
}
-STATIC
-VOID
+STATIC
+VOID
PutBits (
- IN INT32 n,
+ IN INT32 n,
IN UINT32 x
)
/*++
@@ -1284,18 +1284,18 @@ Routine Description:
Argments:
n - the rightmost n bits of the data is used
- x - the data
+ x - the data
Returns: (VOID)
--*/
{
- UINT8 Temp;
-
+ UINT8 Temp;
+
if (n < mBitCount) {
mSubBitBuf |= x << (mBitCount -= n);
} else {
-
+
Temp = (UINT8)(mSubBitBuf | (x >> (n -= mBitCount)));
if (mDst < mDstUpperLimit) {
*mDst++ = Temp;
@@ -1305,22 +1305,22 @@ Returns: (VOID)
if (n < UINT8_BIT) {
mSubBitBuf = x << (mBitCount = UINT8_BIT - n);
} else {
-
+
Temp = (UINT8)(x >> (n - UINT8_BIT));
if (mDst < mDstUpperLimit) {
*mDst++ = Temp;
}
mCompSize++;
-
+
mSubBitBuf = x << (mBitCount = 2 * UINT8_BIT - n);
}
}
}
-STATIC
-INT32
+STATIC
+INT32
FreadCrc (
- OUT UINT8 *p,
+ OUT UINT8 *p,
IN INT32 n
)
/*++
@@ -1328,7 +1328,7 @@ FreadCrc (
Routine Description:
Read in source data
-
+
Arguments:
p - the buffer to hold the data
@@ -1337,7 +1337,7 @@ Arguments:
Returns:
number of bytes actually read
-
+
--*/
{
INT32 i;
@@ -1356,16 +1356,16 @@ Returns:
}
-STATIC
-VOID
+STATIC
+VOID
InitPutBits ()
{
- mBitCount = UINT8_BIT;
+ mBitCount = UINT8_BIT;
mSubBitBuf = 0;
}
-STATIC
-VOID
+STATIC
+VOID
CountLen (
IN INT32 i
)
@@ -1374,11 +1374,11 @@ CountLen (
Routine Description:
Count the number of each code length for a Huffman tree.
-
+
Arguments:
i - the top node
-
+
Returns: (VOID)
--*/
@@ -1395,8 +1395,8 @@ Returns: (VOID)
}
}
-STATIC
-VOID
+STATIC
+VOID
MakeLen (
IN INT32 Root
)
@@ -1405,7 +1405,7 @@ MakeLen (
Routine Description:
Create code length array for a Huffman tree
-
+
Arguments:
Root - the root of the tree
@@ -1419,12 +1419,12 @@ Arguments:
mLenCnt[i] = 0;
}
CountLen(Root);
-
+
//
// 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--) {
Cum += mLenCnt[i] << (16 - i);
@@ -1448,8 +1448,8 @@ Arguments:
}
}
-STATIC
-VOID
+STATIC
+VOID
DownHeap (
IN INT32 i
)
@@ -1459,7 +1459,7 @@ DownHeap (
//
// priority queue: send i-th entry down heap
//
-
+
k = mHeap[i];
while ((j = 2 * i) <= mHeapSize) {
if (j < mHeapSize && mFreq[mHeap[j]] > mFreq[mHeap[j + 1]]) {
@@ -1474,11 +1474,11 @@ DownHeap (
mHeap[i] = (INT16)k;
}
-STATIC
-VOID
+STATIC
+VOID
MakeCode (
- IN INT32 n,
- IN UINT8 Len[],
+ IN INT32 n,
+ IN UINT8 Len[],
OUT UINT16 Code[]
)
/*++
@@ -1486,7 +1486,7 @@ MakeCode (
Routine Description:
Assign code to each symbol based on the code length array
-
+
Arguments:
n - number of symbols
@@ -1509,12 +1509,12 @@ Returns: (VOID)
}
}
-STATIC
-INT32
+STATIC
+INT32
MakeTree (
- IN INT32 NParm,
- IN UINT16 FreqParm[],
- OUT UINT8 LenParm[],
+ IN INT32 NParm,
+ IN UINT16 FreqParm[],
+ OUT UINT8 LenParm[],
OUT UINT16 CodeParm[]
)
/*++
@@ -1522,22 +1522,22 @@ 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.
-
+
--*/
{
INT32 i, j, k, Avail;
-
+
//
// make tree, calculate len[], return root
//
@@ -1552,16 +1552,16 @@ Returns:
mLen[i] = 0;
if (mFreq[i]) {
mHeap[++mHeapSize] = (INT16)i;
- }
+ }
}
if (mHeapSize < 2) {
CodeParm[mHeap[1]] = 0;
return mHeap[1];
}
for (i = mHeapSize / 2; i >= 1; i--) {
-
+
//
- // make priority queue
+ // make priority queue
//
DownHeap(i);
}
@@ -1584,11 +1584,11 @@ Returns:
mLeft[k] = (UINT16)i;
mRight[k] = (UINT16)j;
} while (mHeapSize > 1);
-
+
mSortPtr = CodeParm;
MakeLen(k);
MakeCode(NParm, LenParm, CodeParm);
-
+
//
// return root
//