#include <Uefi.h>
#include <Library/MemoryAllocationLib.h>
#include <Library/BaseMemoryLib.h>
#include <Library/DebugLib.h>
#include <Library/ShellLib.h>
#include "Compress.h"

Macros
#define	UINT8_MAX 0xff

#define	UINT8_BIT 8

#define	THRESHOLD 3

#define	INIT_CRC 0

#define	WNDBIT 13

#define	WNDSIZ (1U << WNDBIT)

#define	MAXMATCH 256

#define	BLKSIZ (1U << 14)

#define	PERC_FLAG 0x8000U

#define	CODE_BIT 16

#define	NIL 0

#define	MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)

#define	HASH(LoopVar7, LoopVar5) ((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)

#define	CRCPOLY 0xA001

#define	UPDATE_CRC(LoopVar5) mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)

#define	NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)

#define	CBIT 9

#define	NP (WNDBIT + 1)

#define	PBIT 4

#define	NT (CODE_BIT + 3)

#define	TBIT 5

#define	NPT NT

Typedefs
typedef INT16	NODE

Functions
VOID	PutDword (IN UINT32 Data)

VOID	MakeCrcTable (VOID)

EFI_STATUS	AllocateMemory (VOID)

VOID	FreeMemory (VOID)

VOID	InitSlide (VOID)

NODE	Child (IN NODE LoopVar6, IN UINT8 LoopVar5)

VOID	MakeChild (IN NODE LoopVar6, IN UINT8 LoopVar5, IN NODE LoopVar4)

VOID	Split (IN NODE Old)

VOID	InsertNode (VOID)

VOID	DeleteNode (VOID)

INT32	FreadCrc (OUT UINT8 *LoopVar7, IN INT32 LoopVar8)

BOOLEAN	GetNextMatch (VOID)

VOID	DownHeap (IN INT32 i)

VOID	CountLen (IN INT32 LoopVar1)

VOID	MakeLen (IN INT32 Root)

VOID	MakeCode (IN INT32 LoopVar8, IN UINT8 Len[], OUT UINT16 Code[])

INT32	MakeTree (IN INT32 NParm, IN UINT16 FreqParm[], OUT UINT8 LenParm[], OUT UINT16 CodeParm[])

VOID	PutBits (IN INT32 LoopVar8, IN UINT32 x)

VOID	EncodeC (IN INT32 LoopVar5)

VOID	EncodeP (IN UINT32 LoopVar7)

VOID	CountTFreq (VOID)

VOID	WritePTLen (IN INT32 LoopVar8, IN INT32 nbit, IN INT32 Special)

VOID	WriteCLen (VOID)

VOID	SendBlock (VOID)

VOID	HufEncodeStart (VOID)

VOID	CompressOutput (IN UINT32 LoopVar5, IN UINT32 LoopVar7)

VOID	HufEncodeEnd (VOID)

EFI_STATUS	Encode (VOID)

EFI_STATUS	Compress (IN VOID SrcBuffer, IN UINT64 SrcSize, IN VOID DstBuffer, IN OUT UINT64 *DstSize)

Variables
STATIC UINT8 *	mSrc

STATIC UINT8 *	mDst

STATIC UINT8 *	mSrcUpperLimit

STATIC UINT8 *	mDstUpperLimit

STATIC UINT8 *	mLevel

STATIC UINT8 *	mText

STATIC UINT8 *	mChildCount

STATIC UINT8 *	mBuf

STATIC UINT8	mCLen [NC]

STATIC UINT8	mPTLen [NPT]

STATIC UINT8 *	mLen

STATIC INT16	mHeap [NC+1]

STATIC INT32	mRemainder

STATIC INT32	mMatchLen

STATIC INT32	mBitCount

STATIC INT32	mHeapSize

STATIC INT32	mTempInt32

STATIC UINT32	mBufSiz = 0

STATIC UINT32	mOutputPos

STATIC UINT32	mOutputMask

STATIC UINT32	mSubBitBuf

STATIC UINT32	mCrc

STATIC UINT32	mCompSize

STATIC UINT32	mOrigSize

STATIC UINT16 *	mFreq

STATIC UINT16 *	mSortPtr

STATIC UINT16	mLenCnt [17]

STATIC UINT16	mLeft [2 *NC - 1]

STATIC UINT16	mRight [2 *NC - 1]

STATIC UINT16	mCrcTable [UINT8_MAX+1]

STATIC UINT16	mCFreq [2 *NC - 1]

STATIC UINT16	mCCode [NC]

STATIC UINT16	mPFreq [2 *NP - 1]

STATIC UINT16	mPTCode [NPT]

STATIC UINT16	mTFreq [2 *NT - 1]

STATIC NODE	mPos

STATIC NODE	mMatchPos

STATIC NODE	mAvail

STATIC NODE *	mPosition

STATIC NODE *	mParent

STATIC NODE *	mPrev

STATIC NODE *	mNext = NULL

INT32	mHuffmanDepth = 0

Detailed Description

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 - 2018, Intel Corporation. All rights reserved.
SPDX-License-Identifier: BSD-2-Clause-Patent

Definition in file Compress.c.

Macro Definition Documentation

◆ BLKSIZ

#define BLKSIZ (1U << 14)

Definition at line 33 of file Compress.c.

◆ CBIT

#define CBIT 9

Definition at line 46 of file Compress.c.

◆ CODE_BIT

#define CODE_BIT 16

Definition at line 35 of file Compress.c.

◆ CRCPOLY

#define CRCPOLY 0xA001

Definition at line 39 of file Compress.c.

◆ HASH

#define HASH	(	LoopVar7,
		LoopVar5
	)	((LoopVar7) + ((LoopVar5) << (WNDBIT - 9)) + WNDSIZ * 2)

Definition at line 38 of file Compress.c.

◆ INIT_CRC

#define INIT_CRC 0

Definition at line 29 of file Compress.c.

◆ MAX_HASH_VAL

#define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)

Definition at line 37 of file Compress.c.

◆ MAXMATCH

#define MAXMATCH 256

Definition at line 32 of file Compress.c.

◆ NC

#define NC (UINT8_MAX + MAXMATCH + 2 - THRESHOLD)

Definition at line 45 of file Compress.c.

◆ NIL

#define NIL 0

Definition at line 36 of file Compress.c.

◆ NP

#define NP (WNDBIT + 1)

Definition at line 47 of file Compress.c.

◆ NPT

#define NPT NT

Definition at line 52 of file Compress.c.

◆ NT

#define NT (CODE_BIT + 3)

Definition at line 49 of file Compress.c.

◆ PBIT

#define PBIT 4

Definition at line 48 of file Compress.c.

◆ PERC_FLAG

#define PERC_FLAG 0x8000U

Definition at line 34 of file Compress.c.

◆ TBIT

#define TBIT 5

Definition at line 50 of file Compress.c.

◆ THRESHOLD

#define THRESHOLD 3

Definition at line 28 of file Compress.c.

◆ UINT8_BIT

#define UINT8_BIT 8

Definition at line 27 of file Compress.c.

◆ UINT8_MAX

#define UINT8_MAX 0xff

Definition at line 26 of file Compress.c.

◆ UPDATE_CRC

#define UPDATE_CRC ( LoopVar5 ) mCrc = mCrcTable[(mCrc ^ (LoopVar5)) & 0xFF] ^ (mCrc >> UINT8_BIT)

Definition at line 40 of file Compress.c.

◆ WNDBIT

#define WNDBIT 13

Definition at line 30 of file Compress.c.

◆ WNDSIZ

#define WNDSIZ (1U << WNDBIT)

Definition at line 31 of file Compress.c.

Typedef Documentation

◆ NODE

typedef INT16 NODE

Definition at line 25 of file Compress.c.

Function Documentation

◆ AllocateMemory()

EFI_STATUS AllocateMemory ( VOID )

Allocate memory spaces for data structures used in compression process.

Return values

EFI_SUCCESS	Memory was allocated successfully.
EFI_OUT_OF_RESOURCES	A memory allocation failed.

Definition at line 183 of file Compress.c.

◆ Child()

NODE Child	(	IN NODE	LoopVar6,
		IN UINT8	LoopVar5
	)

Find child node given the parent node and the edge character

Parameters

[in]	LoopVar6	The parent node.
[in]	LoopVar5	The edge character.

Returns: The child node.

Return values

NIL(Zero) No child could be found.

Definition at line 265 of file Compress.c.

◆ Compress()

EFI_STATUS Compress	(	IN VOID *	SrcBuffer,
		IN UINT64	SrcSize,
		IN VOID *	DstBuffer,
		IN OUT UINT64 *	DstSize
	)

The compression routine.

Parameters

[in]	SrcBuffer	The buffer containing the source data.
[in]	SrcSize	Number of bytes in SrcBuffer.
[in]	DstBuffer	The buffer to put the compressed image in.
[in,out]	DstSize	On input the size (in bytes) of DstBuffer, on return the number of bytes placed in DstBuffer.

Return values

EFI_SUCCESS	The compression was successful.
EFI_BUFFER_TOO_SMALL	The buffer was too small. DstSize is required.

Definition at line 1324 of file Compress.c.

◆ CompressOutput()

VOID CompressOutput	(	IN UINT32	LoopVar5,
		IN UINT32	LoopVar7
	)

Outputs an Original Character or a Pointer.

Parameters

[in]	LoopVar5	The original character or the 'String Length' element of a Pointer.
[in]	LoopVar7	The 'Position' field of a Pointer.

Definition at line 1180 of file Compress.c.

◆ CountLen()

VOID CountLen ( IN INT32 LoopVar1 )

Count the number of each code length for a Huffman tree.

Parameters

[in] LoopVar1 The top node.

Definition at line 669 of file Compress.c.

◆ CountTFreq()

VOID CountTFreq ( VOID )

Count the frequencies for the Extra Set.

Definition at line 934 of file Compress.c.

◆ DeleteNode()

VOID DeleteNode ( VOID )

Delete outdated string info. (The Usage of PERC_FLAG ensures a clean deletion).

Definition at line 472 of file Compress.c.

◆ DownHeap()

VOID DownHeap ( IN INT32 i )

Send entry LoopVar1 down the queue.

Parameters

[in] LoopVar1 The index of the item to move.

Definition at line 633 of file Compress.c.

◆ Encode()

EFI_STATUS Encode ( VOID )

The main controlling routine for compression process.

Return values

EFI_SUCCESS	The compression is successful.
EFI_OUT_0F_RESOURCES	Not enough memory for compression process.

Definition at line 1238 of file Compress.c.

◆ EncodeC()

VOID EncodeC ( IN INT32 LoopVar5 )

Encode a signed 32 bit number.

Parameters

[in] LoopVar5 The number to encode.

Definition at line 895 of file Compress.c.

◆ EncodeP()

VOID EncodeP ( IN UINT32 LoopVar7 )

Encode a unsigned 32 bit number.

Parameters

[in] LoopVar7 The number to encode.

Definition at line 908 of file Compress.c.

◆ FreadCrc()

INT32 FreadCrc	(	OUT UINT8 *	LoopVar7,
		IN INT32	LoopVar8
	)

Read in source data

Parameters

[out]	LoopVar7	The buffer to hold the data.
[in]	LoopVar8	The number of bytes to read.

Returns: The number of bytes actually read.

Definition at line 566 of file Compress.c.

◆ FreeMemory()

VOID FreeMemory ( VOID )

Called when compression is completed to free memory previously allocated.

Definition at line 216 of file Compress.c.

◆ GetNextMatch()

BOOLEAN GetNextMatch ( VOID )

Advance the current position (read in new data if needed). Delete outdated string info. Find a match string for current position.

Return values

TRUE	The operation was successful.
FALSE	The operation failed due to insufficient memory.

Definition at line 598 of file Compress.c.

◆ HufEncodeEnd()

VOID HufEncodeEnd ( VOID )

End the huffman encoding.

Definition at line 1219 of file Compress.c.

◆ HufEncodeStart()

VOID HufEncodeStart ( VOID )

Start the huffman encoding.

Definition at line 1159 of file Compress.c.

◆ InitSlide()

VOID InitSlide ( VOID )

Initialize String Info Log data structures.

Definition at line 234 of file Compress.c.

◆ InsertNode()

VOID InsertNode ( VOID )

Insert string info for current position into the String Info Log.

Definition at line 344 of file Compress.c.

◆ MakeChild()

VOID MakeChild	(	IN NODE	LoopVar6,
		IN UINT8	LoopVar5,
		IN NODE	LoopVar4
	)

Create a new child for a given parent node.

Parameters

[in]	LoopVar6	The parent node.
[in]	LoopVar5	The edge character.
[in]	LoopVar4	The child node.

Definition at line 289 of file Compress.c.

◆ MakeCode()

VOID MakeCode	(	IN INT32	LoopVar8,
		IN UINT8	Len[],
		OUT UINT16	Code[]
	)

Assign code to each symbol based on the code length array.

Parameters

[in]	LoopVar8	The number of symbols.
[in]	Len	The code length array.
[out]	Code	The stores codes for each symbol.

Definition at line 744 of file Compress.c.

◆ MakeCrcTable()

VOID MakeCrcTable ( VOID )

Make a CRC table.

Definition at line 125 of file Compress.c.

◆ MakeLen()

VOID MakeLen ( IN INT32 Root )

Create code length array for a Huffman tree.

Parameters

[in] Root The root of the tree.

Definition at line 689 of file Compress.c.

◆ MakeTree()

INT32 MakeTree	(	IN INT32	NParm,
		IN UINT16	FreqParm[],
		OUT UINT8	LenParm[],
		OUT UINT16	CodeParm[]
	)

Generates Huffman codes given a frequency distribution of symbols.

Parameters

[in]	NParm	The number of symbols.
[in]	FreqParm	The frequency of each symbol.
[out]	LenParm	The code length for each symbol.
[out]	CodeParm	The code for each symbol.

Returns: The root of the Huffman tree.

Definition at line 774 of file Compress.c.

◆ PutBits()

VOID PutBits	(	IN INT32	LoopVar8,
		IN UINT32	x
	)

Outputs rightmost LoopVar8 bits of x

Parameters

[in]	LoopVar8	The rightmost LoopVar8 bits of the data is used.
[in]	x	The data.

Definition at line 857 of file Compress.c.

◆ PutDword()

VOID PutDword ( IN UINT32 Data )

Put a dword to output stream

Parameters

[in] Data The dword to put.

Definition at line 155 of file Compress.c.

◆ SendBlock()

VOID SendBlock ( VOID )

Huffman code the block and output it.

Definition at line 1084 of file Compress.c.

◆ Split()

VOID Split ( IN NODE Old )

Split a node.

Parameters

[in] Old The node to split.

Definition at line 315 of file Compress.c.

◆ WriteCLen()

VOID WriteCLen ( VOID )

Outputs the code length array for Char&Length Set.

Definition at line 1029 of file Compress.c.

◆ WritePTLen()

VOID WritePTLen	(	IN INT32	LoopVar8,
		IN INT32	nbit,
		IN INT32	Special
	)

Outputs the code length array for the Extra Set or the Position Set.

Parameters

[in]	LoopVar8	The number of symbols.
[in]	nbit	The number of bits needed to represent 'LoopVar8'.
[in]	Special	The special symbol that needs to be take care of.

Definition at line 991 of file Compress.c.

Variable Documentation

◆ mAvail

STATIC NODE mAvail

Definition at line 113 of file Compress.c.

◆ mBitCount

STATIC INT32 mBitCount

Definition at line 88 of file Compress.c.

◆ mBuf

STATIC UINT8* mBuf

Definition at line 81 of file Compress.c.

◆ mBufSiz

STATIC UINT32 mBufSiz = 0

Definition at line 91 of file Compress.c.

◆ mCCode

STATIC UINT16 mCCode[NC]

Definition at line 106 of file Compress.c.

◆ mCFreq

STATIC UINT16 mCFreq[2 *NC - 1]

Definition at line 105 of file Compress.c.

◆ mChildCount

STATIC UINT8* mChildCount

Definition at line 80 of file Compress.c.

◆ mCLen

STATIC UINT8 mCLen[NC]

Definition at line 82 of file Compress.c.

◆ mCompSize

STATIC UINT32 mCompSize

Definition at line 96 of file Compress.c.

◆ mCrc

STATIC UINT32 mCrc

Definition at line 95 of file Compress.c.

◆ mCrcTable

STATIC UINT16 mCrcTable[UINT8_MAX+1]

Definition at line 104 of file Compress.c.

◆ mDst

STATIC UINT8* mDst

Definition at line 74 of file Compress.c.

◆ mDstUpperLimit

STATIC UINT8* mDstUpperLimit

Definition at line 76 of file Compress.c.

◆ mFreq

STATIC UINT16* mFreq

Definition at line 99 of file Compress.c.

◆ mHeap

STATIC INT16 mHeap[NC+1]

Definition at line 85 of file Compress.c.

◆ mHeapSize

STATIC INT32 mHeapSize

Definition at line 89 of file Compress.c.

◆ mHuffmanDepth

INT32 mHuffmanDepth = 0

Definition at line 118 of file Compress.c.

◆ mLeft

STATIC UINT16 mLeft[2 *NC - 1]

Definition at line 102 of file Compress.c.

◆ mLen

STATIC UINT8* mLen

Definition at line 84 of file Compress.c.

◆ mLenCnt

STATIC UINT16 mLenCnt[17]

Definition at line 101 of file Compress.c.

◆ mLevel

STATIC UINT8* mLevel

Definition at line 78 of file Compress.c.

◆ mMatchLen

STATIC INT32 mMatchLen

Definition at line 87 of file Compress.c.

◆ mMatchPos

STATIC NODE mMatchPos

Definition at line 112 of file Compress.c.

◆ mNext

STATIC NODE* mNext = NULL

Definition at line 117 of file Compress.c.

◆ mOrigSize

STATIC UINT32 mOrigSize

Definition at line 97 of file Compress.c.

◆ mOutputMask

STATIC UINT32 mOutputMask

Definition at line 93 of file Compress.c.

◆ mOutputPos

STATIC UINT32 mOutputPos

Definition at line 92 of file Compress.c.

◆ mParent

STATIC NODE* mParent

Definition at line 115 of file Compress.c.

◆ mPFreq

STATIC UINT16 mPFreq[2 *NP - 1]

Definition at line 107 of file Compress.c.

◆ mPos

STATIC NODE mPos

Definition at line 111 of file Compress.c.

◆ mPosition

STATIC NODE* mPosition

Definition at line 114 of file Compress.c.

◆ mPrev

STATIC NODE* mPrev

Definition at line 116 of file Compress.c.

◆ mPTCode

STATIC UINT16 mPTCode[NPT]

Definition at line 108 of file Compress.c.

◆ mPTLen

STATIC UINT8 mPTLen[NPT]

Definition at line 83 of file Compress.c.

◆ mRemainder

STATIC INT32 mRemainder

Definition at line 86 of file Compress.c.

◆ mRight

STATIC UINT16 mRight[2 *NC - 1]

Definition at line 103 of file Compress.c.

◆ mSortPtr

STATIC UINT16* mSortPtr

Definition at line 100 of file Compress.c.

◆ mSrc

STATIC UINT8* mSrc

Definition at line 73 of file Compress.c.

◆ mSrcUpperLimit

STATIC UINT8* mSrcUpperLimit

Definition at line 75 of file Compress.c.

◆ mSubBitBuf

STATIC UINT32 mSubBitBuf

Definition at line 94 of file Compress.c.

◆ mTempInt32

STATIC INT32 mTempInt32

Definition at line 90 of file Compress.c.

◆ mText

STATIC UINT8* mText

Definition at line 79 of file Compress.c.

◆ mTFreq

STATIC UINT16 mTFreq[2 *NT - 1]

Definition at line 109 of file Compress.c.

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ BLKSIZ

◆ CBIT

◆ CODE_BIT

◆ CRCPOLY

◆ HASH

◆ INIT_CRC

◆ MAX_HASH_VAL

◆ MAXMATCH

◆ NC

◆ NIL

◆ NP

◆ NPT

◆ NT

◆ PBIT

◆ PERC_FLAG

◆ TBIT

◆ THRESHOLD

◆ UINT8_BIT

◆ UINT8_MAX

◆ UPDATE_CRC

◆ WNDBIT

◆ WNDSIZ

Typedef Documentation

◆ NODE

Function Documentation

◆ AllocateMemory()

◆ Child()

◆ Compress()

◆ CompressOutput()

◆ CountLen()

◆ CountTFreq()

◆ DeleteNode()

◆ DownHeap()

◆ Encode()

◆ EncodeC()

◆ EncodeP()

◆ FreadCrc()

◆ FreeMemory()

◆ GetNextMatch()

◆ HufEncodeEnd()

◆ HufEncodeStart()

◆ InitSlide()

◆ InsertNode()

◆ MakeChild()

◆ MakeCode()

◆ MakeCrcTable()

◆ MakeLen()

◆ MakeTree()

◆ PutBits()

◆ PutDword()

◆ SendBlock()

◆ Split()

◆ WriteCLen()

◆ WritePTLen()

Variable Documentation

◆ mAvail

◆ mBitCount

◆ mBuf

◆ mBufSiz

◆ mCCode

◆ mCFreq

◆ mChildCount

◆ mCLen

◆ mCompSize

◆ mCrc

◆ mCrcTable

◆ mDst

◆ mDstUpperLimit

◆ mFreq

◆ mHeap

◆ mHeapSize

◆ mHuffmanDepth

◆ mLeft

◆ mLen