\r
**/\r
\r
-//\r
-// Decompression algorithm begins here\r
-//\r
-#define BITBUFSIZ 32\r
-#define MAXMATCH 256\r
-#define THRESHOLD 3\r
-#define CODE_BIT 16\r
-#define BAD_TABLE - 1\r
-\r
-//\r
-// C: Char&Len Set; P: Position Set; T: exTra Set\r
-//\r
-#define NC (0xff + MAXMATCH + 2 - THRESHOLD)\r
-#define CBIT 9\r
-#define MAXPBIT 5\r
-#define TBIT 5\r
-#define MAXNP ((1U << MAXPBIT) - 1)\r
-#define NT (CODE_BIT + 3)\r
-#if NT > MAXNP\r
-#define NPT NT\r
-#else\r
-#define NPT MAXNP\r
-#endif\r
-\r
-typedef struct {\r
- UINT8 *mSrcBase; ///< Starting address of compressed data\r
- UINT8 *mDstBase; ///< Starting address of decompressed data\r
- UINT32 mOutBuf;\r
- UINT32 mInBuf;\r
-\r
- UINT16 mBitCount;\r
- UINT32 mBitBuf;\r
- UINT32 mSubBitBuf;\r
- UINT16 mBlockSize;\r
- UINT32 mCompSize;\r
- UINT32 mOrigSize;\r
-\r
- UINT16 mBadTableFlag;\r
-\r
- UINT16 mLeft[2 * NC - 1];\r
- UINT16 mRight[2 * NC - 1];\r
- UINT8 mCLen[NC];\r
- UINT8 mPTLen[NPT];\r
- UINT16 mCTable[4096];\r
- UINT16 mPTTable[256];\r
-\r
- ///\r
- /// The length of the field 'Position Set Code Length Array Size' in Block Header.\r
- /// For EFI 1.1 de/compression algorithm, mPBit = 4\r
- /// For Tiano de/compression algorithm, mPBit = 5\r
- ///\r
- UINT8 mPBit;\r
-} SCRATCH_DATA;\r
+#include "BaseUefiDecompressLibInternals.h"\r
\r
/**\r
+ Read NumOfBit of bits from source into mBitBuf\r
+\r
Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source.\r
\r
- @param Sd The global scratch data\r
+ @param Sd The global scratch data\r
@param NumOfBits The number of bits to shift and read.\r
\r
**/\r
IN UINT16 NumOfBits\r
)\r
{\r
+ //\r
+ // Left shift NumOfBits of bits in advance\r
+ //\r
Sd->mBitBuf = (UINT32) (Sd->mBitBuf << NumOfBits);\r
\r
+ //\r
+ // Copy data needed in bytes into mSbuBitBuf\r
+ //\r
while (NumOfBits > Sd->mBitCount) {\r
\r
Sd->mBitBuf |= (UINT32) (Sd->mSubBitBuf << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount)));\r
// Get 1 byte into SubBitBuf\r
//\r
Sd->mCompSize--;\r
- Sd->mSubBitBuf = 0;\r
Sd->mSubBitBuf = Sd->mSrcBase[Sd->mInBuf++];\r
Sd->mBitCount = 8;\r
\r
}\r
}\r
\r
+ //\r
+ // Caculate additional bit count read to update mBitCount\r
+ //\r
Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits);\r
+ \r
+ //\r
+ // Copy NumOfBits of bits from mSubBitBuf into mBitBuf\r
+ //\r
Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount;\r
}\r
\r
/**\r
+ Get NumOfBits of bits out from mBitBuf\r
+\r
Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent \r
NumOfBits of bits from source. Returns NumOfBits of bits that are \r
popped out.\r
\r
- @param Sd The global scratch data.\r
+ @param Sd The global scratch data.\r
@param NumOfBits The number of bits to pop and read.\r
\r
@return The bits that are popped out.\r
{\r
UINT32 OutBits;\r
\r
+ //\r
+ // Pop NumOfBits of Bits from Left\r
+ // \r
OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits));\r
\r
+ //\r
+ // Fill up mBitBuf from source\r
+ //\r
FillBuf (Sd, NumOfBits);\r
\r
return OutBits;\r
/**\r
Creates Huffman Code mapping table according to code length array.\r
\r
- @param Sd The global scratch data\r
+ Creates Huffman Code mapping table for Extra Set, Char&Len Set \r
+ and Position Set according to code length array.\r
+\r
+ @param Sd The global scratch data\r
@param NumOfChar Number of symbols in the symbol set\r
- @param BitLen Code length array\r
+ @param BitLen Code length array\r
@param TableBits The width of the mapping table\r
- @param Table The table\r
+ @param Table The table\r
\r
@retval 0 OK.\r
@retval BAD_TABLE The table is corrupted.\r
UINT16 Avail;\r
UINT16 NextCode;\r
UINT16 Mask;\r
+ UINT16 WordOfStart;\r
+ UINT16 WordOfCount;\r
+\r
\r
for (Index = 1; Index <= 16; Index++) {\r
Count[Index] = 0;\r
Start[1] = 0;\r
\r
for (Index = 1; Index <= 16; Index++) {\r
- Start[Index + 1] = (UINT16) (Start[Index] + (Count[Index] << (16 - Index)));\r
+ WordOfStart = Start[Index];\r
+ WordOfCount = Count[Index];\r
+ Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index)));\r
}\r
\r
if (Start[17] != 0) {\r
/**\r
Decodes a position value.\r
\r
+ Get a position value according to Position Huffman Table.\r
+ \r
@param Sd the global scratch data\r
\r
@return The position value decoded.\r
/**\r
Reads code lengths for the Extra Set or the Position Set.\r
\r
- @param Sd The global scratch data.\r
- @param nn Number of symbols.\r
- @param nbit Number of bits needed to represent nn.\r
+ Read in the Extra Set or Pointion Set Length Arrary, then\r
+ generate the Huffman code mapping for them.\r
+\r
+ @param Sd The global scratch data.\r
+ @param nn Number of symbols.\r
+ @param nbit Number of bits needed to represent nn.\r
@param Special The special symbol that needs to be taken care of.\r
\r
@retval 0 OK.\r
volatile UINT16 Index;\r
UINT32 Mask;\r
\r
+ //\r
+ // Read Extra Set Code Length Array size \r
+ //\r
Number = (UINT16) GetBits (Sd, nbit);\r
\r
if (Number == 0) {\r
+ //\r
+ // This represents only Huffman code used\r
+ //\r
CharC = (UINT16) GetBits (Sd, nbit);\r
\r
for (Index = 0; Index < 256; Index++) {\r
\r
CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3));\r
\r
+ //\r
+ // If a code length is less than 7, then it is encoded as a 3-bit\r
+ // value. Or it is encoded as a series of "1"s followed by a \r
+ // terminating "0". The number of "1"s = Code length - 4.\r
+ //\r
if (CharC == 7) {\r
Mask = 1U << (BITBUFSIZ - 1 - 3);\r
while (Mask & Sd->mBitBuf) {\r
CharC += 1;\r
}\r
}\r
-\r
+ \r
FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3));\r
\r
Sd->mPTLen[Index++] = (UINT8) CharC;\r
-\r
+ \r
+ //\r
+ // For Code&Len Set, \r
+ // After the third length of the code length concatenation,\r
+ // a 2-bit value is used to indicated the number of consecutive \r
+ // zero lengths after the third length.\r
+ //\r
if (Index == Special) {\r
CharC = (UINT16) GetBits (Sd, 2);\r
while ((INT16) (--CharC) >= 0) {\r
while (Index < nn) {\r
Sd->mPTLen[Index++] = 0;\r
}\r
-\r
+ \r
return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable);\r
}\r
\r
/**\r
Reads code lengths for Char&Len Set.\r
+ \r
+ Read in and decode the Char&Len Set Code Length Array, then\r
+ generate the Huffman Code mapping table for the Char&Len Set.\r
\r
@param Sd the global scratch data\r
\r
SCRATCH_DATA *Sd\r
)\r
{\r
- UINT16 Number;\r
- UINT16 CharC;\r
+ UINT16 Number;\r
+ UINT16 CharC;\r
volatile UINT16 Index;\r
- UINT32 Mask;\r
+ UINT32 Mask;\r
\r
Number = (UINT16) GetBits (Sd, CBIT);\r
\r
if (Number == 0) {\r
+ //\r
+ // This represents only Huffman code used\r
+ //\r
CharC = (UINT16) GetBits (Sd, CBIT);\r
\r
for (Index = 0; Index < NC; Index++) {\r
\r
Index = 0;\r
while (Index < Number) {\r
-\r
CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)];\r
if (CharC >= NT) {\r
Mask = 1U << (BITBUFSIZ - 1 - 8);\r
\r
/**\r
Decode a character/length value.\r
+ \r
+ Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates\r
+ Huffman code mapping table for Extra Set, Code&Len Set and\r
+ Position Set.\r
\r
@param Sd The global scratch data.\r
\r
if (Sd->mBlockSize == 0) {\r
//\r
// Starting a new block\r
- //\r
+ // Read BlockSize from block header\r
+ // \r
Sd->mBlockSize = (UINT16) GetBits (Sd, 16);\r
+\r
+ //\r
+ // Read in the Extra Set Code Length Arrary,\r
+ // Generate the Huffman code mapping table for Extra Set.\r
+ //\r
Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3);\r
if (Sd->mBadTableFlag != 0) {\r
return 0;\r
}\r
\r
+ //\r
+ // Read in and decode the Char&Len Set Code Length Arrary,\r
+ // Generate the Huffman code mapping table for Char&Len Set.\r
+ //\r
ReadCLen (Sd);\r
\r
+ //\r
+ // Read in the Position Set Code Length Arrary, \r
+ // Generate the Huffman code mapping table for the Position Set.\r
+ //\r
Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1));\r
if (Sd->mBadTableFlag != 0) {\r
return 0;\r
}\r
}\r
\r
+ //\r
+ // Get one code according to Code&Set Huffman Table\r
+ //\r
Sd->mBlockSize--;\r
Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)];\r
\r
/**\r
Decode the source data and put the resulting data into the destination buffer.\r
\r
+ Decode the source data and put the resulting data into the destination buffer.\r
+ \r
@param Sd The global scratch data\r
\r
**/\r
DataIdx = 0;\r
\r
for (;;) {\r
+ //\r
+ // Get one code from mBitBuf\r
+ // \r
CharC = DecodeC (Sd);\r
if (Sd->mBadTableFlag != 0) {\r
- return ;\r
+ goto Done;\r
}\r
\r
if (CharC < 256) {\r
// Process an Original character\r
//\r
if (Sd->mOutBuf >= Sd->mOrigSize) {\r
- return ;\r
+ goto Done;\r
} else {\r
+ //\r
+ // Write orignal character into mDstBase\r
+ //\r
Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC;\r
}\r
\r
// Process a Pointer\r
//\r
CharC = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD));\r
-\r
+ \r
+ //\r
+ // Get string length\r
+ //\r
BytesRemain = CharC;\r
\r
+ //\r
+ // Locate string position\r
+ //\r
DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1;\r
\r
+ //\r
+ // Write BytesRemain of bytes into mDstBase\r
+ //\r
BytesRemain--;\r
while ((INT16) (BytesRemain) >= 0) {\r
Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++];\r
if (Sd->mOutBuf >= Sd->mOrigSize) {\r
- return ;\r
+ goto Done;\r
}\r
\r
BytesRemain--;\r
}\r
}\r
\r
+Done:\r
return ;\r
}\r
\r
/**\r
- The internal implementation of *_DECOMPRESS_PROTOCOL.GetInfo().\r
-\r
- @param Source The source buffer containing the compressed data.\r
- @param SourceSize The size of source buffer\r
- @param DestinationSize The size of destination buffer.\r
- @param ScratchSize The size of scratch buffer.\r
-\r
- @retval RETURN_SUCCESS The size of destination buffer and the size of scratch buffer are successull retrieved.\r
+ Retrieves the size of the uncompressed buffer and the size of the scratch buffer.\r
+\r
+ Retrieves the size of the uncompressed buffer and the temporary scratch buffer \r
+ required to decompress the buffer specified by Source and SourceSize.\r
+ If the size of the uncompressed buffer or the size of the scratch buffer cannot\r
+ be determined from the compressed data specified by Source and SourceData, \r
+ then RETURN_INVALID_PARAMETER is returned. Otherwise, the size of the uncompressed\r
+ buffer is returned in DestinationSize, the size of the scratch buffer is returned\r
+ in ScratchSize, and RETURN_SUCCESS is returned.\r
+ This function does not have scratch buffer available to perform a thorough \r
+ checking of the validity of the source data. It just retrieves the "Original Size"\r
+ field from the beginning bytes of the source data and output it as DestinationSize.\r
+ And ScratchSize is specific to the decompression implementation.\r
+\r
+ If Source is NULL, then ASSERT().\r
+ If DestinationSize is NULL, then ASSERT().\r
+ If ScratchSize is NULL, then ASSERT().\r
+\r
+ @param Source The source buffer containing the compressed data.\r
+ @param SourceSize The size, in bytes, of the source buffer.\r
+ @param DestinationSize A pointer to the size, in bytes, of the uncompressed buffer\r
+ that will be generated when the compressed buffer specified\r
+ by Source and SourceSize is decompressed..\r
+ @param ScratchSize A pointer to the size, in bytes, of the scratch buffer that\r
+ is required to decompress the compressed buffer specified \r
+ by Source and SourceSize.\r
+\r
+ @retval RETURN_SUCCESS The size of destination buffer and the size of scratch \r
+ buffer are successull retrieved.\r
@retval RETURN_INVALID_PARAMETER The source data is corrupted\r
\r
**/\r
}\r
\r
/**\r
- The internal implementation of *_DECOMPRESS_PROTOCOL.Decompress().\r
-\r
- @param Source The source buffer containing the compressed data.\r
+ Decompresses a compressed source buffer.\r
+\r
+ This function is designed so that the decompression algorithm can be implemented\r
+ without using any memory services. As a result, this function is not allowed to\r
+ call any memory allocation services in its implementation. It is the caller's r\r
+ esponsibility to allocate and free the Destination and Scratch buffers.\r
+ If the compressed source data specified by Source is sucessfully decompressed \r
+ into Destination, then RETURN_SUCCESS is returned. If the compressed source data \r
+ specified by Source is not in a valid compressed data format,\r
+ then RETURN_INVALID_PARAMETER is returned.\r
+\r
+ If Source is NULL, then ASSERT().\r
+ If Destination is NULL, then ASSERT().\r
+ If the required scratch buffer size > 0 and Scratch is NULL, then ASSERT().\r
+\r
+ @param Source The source buffer containing the compressed data.\r
@param Destination The destination buffer to store the decompressed data\r
- @param Scratch The buffer used internally by the decompress routine. This buffer is needed to store intermediate data.\r
-\r
+ @param Scratch A temporary scratch buffer that is used to perform the decompression.\r
+ This is an optional parameter that may be NULL if the \r
+ required scratch buffer size is 0.\r
+ \r
@retval RETURN_SUCCESS Decompression is successfull\r
@retval RETURN_INVALID_PARAMETER The source data is corrupted\r
\r
Sd->mPBit = 4;\r
Sd->mSrcBase = (UINT8 *)Src;\r
Sd->mDstBase = Dst;\r
+ //\r
+ // CompSize and OrigSize are caculated in bytes\r
+ //\r
Sd->mCompSize = CompSize;\r
Sd->mOrigSize = OrigSize;\r
\r
projects / mirror_edk2.git / blobdiff