summaryrefslogtreecommitdiff
path: root/BaseTools/Source/C/Common/EfiCompress.c
diff options
context:
space:
mode:
Diffstat (limited to 'BaseTools/Source/C/Common/EfiCompress.c')
-rw-r--r--BaseTools/Source/C/Common/EfiCompress.c2814
1 files changed, 1407 insertions, 1407 deletions
diff --git a/BaseTools/Source/C/Common/EfiCompress.c b/BaseTools/Source/C/Common/EfiCompress.c
index 0db958b853..913bef7c8f 100644
--- a/BaseTools/Source/C/Common/EfiCompress.c
+++ b/BaseTools/Source/C/Common/EfiCompress.c
@@ -1,1407 +1,1407 @@
-/** @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
-and Huffman codings are applied to each Block.
-
-Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>
-SPDX-License-Identifier: BSD-2-Clause-Patent
-
-**/
-
-#include "Compress.h"
-
-
-//
-// Macro Definitions
-//
-
-#undef UINT8_MAX
-typedef INT16 NODE;
-#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 PERC_FLAG 0x8000U
-#define CODE_BIT 16
-#define NIL 0
-#define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
-#define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
-#define CRCPOLY 0xA001
-#define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
-
-//
-// C: the Char&Len Set; P: the Position Set; T: the exTra Set
-//
-
-#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
-#if NT > NP
- #define NPT NT
-#else
- #define NPT NP
-#endif
-
-//
-// Function Prototypes
-//
-
-STATIC
-VOID
-PutDword(
- IN UINT32 Data
- );
-
-STATIC
-EFI_STATUS
-AllocateMemory (
- );
-
-STATIC
-VOID
-FreeMemory (
- );
-
-STATIC
-VOID
-InitSlide (
- );
-
-STATIC
-NODE
-Child (
- IN NODE q,
- IN UINT8 c
- );
-
-STATIC
-VOID
-MakeChild (
- IN NODE q,
- IN UINT8 c,
- IN NODE r
- );
-
-STATIC
-VOID
-Split (
- IN NODE Old
- );
-
-STATIC
-VOID
-InsertNode (
- );
-
-STATIC
-VOID
-DeleteNode (
- );
-
-STATIC
-VOID
-GetNextMatch (
- );
-
-STATIC
-EFI_STATUS
-Encode (
- );
-
-STATIC
-VOID
-CountTFreq (
- );
-
-STATIC
-VOID
-WritePTLen (
- IN INT32 n,
- IN INT32 nbit,
- IN INT32 Special
- );
-
-STATIC
-VOID
-WriteCLen (
- );
-
-STATIC
-VOID
-EncodeC (
- IN INT32 c
- );
-
-STATIC
-VOID
-EncodeP (
- IN UINT32 p
- );
-
-STATIC
-VOID
-SendBlock (
- );
-
-STATIC
-VOID
-Output (
- IN UINT32 c,
- IN UINT32 p
- );
-
-STATIC
-VOID
-HufEncodeStart (
- );
-
-STATIC
-VOID
-HufEncodeEnd (
- );
-
-STATIC
-VOID
-MakeCrcTable (
- );
-
-STATIC
-VOID
-PutBits (
- IN INT32 n,
- IN UINT32 x
- );
-
-STATIC
-INT32
-FreadCrc (
- OUT UINT8 *p,
- IN INT32 n
- );
-
-STATIC
-VOID
-InitPutBits (
- );
-
-STATIC
-VOID
-CountLen (
- IN INT32 i
- );
-
-STATIC
-VOID
-MakeLen (
- IN INT32 Root
- );
-
-STATIC
-VOID
-DownHeap (
- IN INT32 i
- );
-
-STATIC
-VOID
-MakeCode (
- IN INT32 n,
- IN UINT8 Len[],
- OUT UINT16 Code[]
- );
-
-STATIC
-INT32
-MakeTree (
- IN INT32 NParm,
- IN UINT16 FreqParm[],
- OUT UINT8 LenParm[],
- OUT UINT16 CodeParm[]
- );
-
-
-//
-// Global Variables
-//
-
-STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
-
-STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
-STATIC INT16 mHeap[NC + 1];
-STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
-STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
-STATIC UINT32 mCompSize, mOrigSize;
-
-STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1],
- mCrcTable[UINT8_MAX + 1], mCFreq[2 * NC - 1],mCCode[NC],
- mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
-
-STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
-
-
-//
-// functions
-//
-
-/**
- The main compression routine.
-
- @param SrcBuffer The buffer storing the source data
- @param SrcSize The size of source data
- @param DstBuffer The buffer to store the compressed data
- @param DstSize On input, the size of DstBuffer; On output,
- the size of the actual compressed data.
-
- @retval EFI_BUFFER_TOO_SMALL The DstBuffer is too small. In this case,
- DstSize contains the size needed.
- @retval EFI_SUCCESS Compression is successful.
-
-**/
-EFI_STATUS
-EfiCompress (
- IN UINT8 *SrcBuffer,
- IN UINT32 SrcSize,
- IN UINT8 *DstBuffer,
- IN OUT UINT32 *DstSize
- )
-{
- EFI_STATUS Status = EFI_SUCCESS;
-
- //
- // Initializations
- //
- mBufSiz = 0;
- mBuf = NULL;
- mText = NULL;
- mLevel = NULL;
- mChildCount = NULL;
- mPosition = NULL;
- mParent = NULL;
- mPrev = NULL;
- mNext = NULL;
-
-
- mSrc = SrcBuffer;
- mSrcUpperLimit = mSrc + SrcSize;
- mDst = DstBuffer;
- mDstUpperLimit = mDst + *DstSize;
-
- 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
- //
- mDst = DstBuffer;
- PutDword(mCompSize+1);
- PutDword(mOrigSize);
-
- //
- // Return
- //
-
- if (mCompSize + 1 + 8 > *DstSize) {
- *DstSize = mCompSize + 1 + 8;
- return EFI_BUFFER_TOO_SMALL;
- } else {
- *DstSize = mCompSize + 1 + 8;
- return EFI_SUCCESS;
- }
-
-}
-
-/**
- Put a dword to output stream
-
- @param Data the dword to put
-**/
-STATIC
-VOID
-PutDword(
- IN UINT32 Data
- )
-{
- if (mDst < mDstUpperLimit) {
- *mDst++ = (UINT8)(((UINT8)(Data )) & 0xff);
- }
-
- if (mDst < mDstUpperLimit) {
- *mDst++ = (UINT8)(((UINT8)(Data >> 0x08)) & 0xff);
- }
-
- if (mDst < mDstUpperLimit) {
- *mDst++ = (UINT8)(((UINT8)(Data >> 0x10)) & 0xff);
- }
-
- if (mDst < mDstUpperLimit) {
- *mDst++ = (UINT8)(((UINT8)(Data >> 0x18)) & 0xff);
- }
-}
-
-/**
- Allocate memory spaces for data structures used in compression process
-
- @retval EFI_SUCCESS Memory is allocated successfully
- @retva; EFI_OUT_OF_RESOURCES Allocation fails
-**/
-STATIC
-EFI_STATUS
-AllocateMemory ()
-{
- UINT32 i;
-
- mText = malloc (WNDSIZ * 2 + MAXMATCH);
- if (mText == NULL) {
- return EFI_OUT_OF_RESOURCES;
- }
- for (i = 0 ; i < WNDSIZ * 2 + MAXMATCH; i ++) {
- mText[i] = 0;
- }
-
- mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mLevel));
- mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mChildCount));
- mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mPosition));
- mParent = malloc (WNDSIZ * 2 * sizeof(*mParent));
- mPrev = malloc (WNDSIZ * 2 * sizeof(*mPrev));
- mNext = malloc ((MAX_HASH_VAL + 1) * sizeof(*mNext));
- if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
- mParent == NULL || mPrev == NULL || mNext == NULL) {
- return EFI_OUT_OF_RESOURCES;
- }
-
- mBufSiz = 16 * 1024U;
- while ((mBuf = malloc(mBufSiz)) == NULL) {
- mBufSiz = (mBufSiz / 10U) * 9U;
- if (mBufSiz < 4 * 1024U) {
- return EFI_OUT_OF_RESOURCES;
- }
- }
- mBuf[0] = 0;
-
- return EFI_SUCCESS;
-}
-
-/**
- Called when compression is completed to free memory previously allocated.
-**/
-VOID
-FreeMemory ()
-{
- 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;
-}
-
-/**
- Initialize String Info Log data structures
-**/
-STATIC
-VOID
-InitSlide ()
-{
- NODE i;
-
- for (i = WNDSIZ; i <= WNDSIZ + UINT8_MAX; i++) {
- mLevel[i] = 1;
- mPosition[i] = NIL; /* sentinel */
- }
- 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;
- }
-}
-
-/**
- Find child node given the parent node and the edge character
-
- @param q the parent node
- @param c the edge character
-
- @return The child node (NIL if not found)
-**/
-STATIC
-NODE
-Child (
- IN NODE q,
- IN UINT8 c
- )
-{
- NODE r;
-
- r = mNext[HASH(q, c)];
- mParent[NIL] = q; /* sentinel */
- while (mParent[r] != q) {
- r = mNext[r];
- }
-
- return r;
-}
-
-/**
- Create a new child for a given parent node.
-
- @param q the parent node
- @param c the edge character
- @param r the child node
-**/
-STATIC
-VOID
-MakeChild (
- IN NODE q,
- IN UINT8 c,
- IN NODE r
- )
-{
- NODE h, t;
-
- h = (NODE)HASH(q, c);
- t = mNext[h];
- mNext[h] = r;
- mNext[r] = t;
- mPrev[t] = r;
- mPrev[r] = h;
- mParent[r] = q;
- mChildCount[q]++;
-}
-
-/**
- Split a node.
-
- @param Old the node to split
-**/
-STATIC
-VOID
-Split (
- NODE Old
- )
-{
- NODE New, t;
-
- New = mAvail;
- mAvail = mNext[New];
- mChildCount[New] = 0;
- t = mPrev[Old];
- mPrev[New] = t;
- mNext[t] = New;
- t = mNext[Old];
- mNext[New] = t;
- mPrev[t] = New;
- mParent[New] = mParent[Old];
- mLevel[New] = (UINT8)mMatchLen;
- mPosition[New] = mPos;
- MakeChild(New, mText[mMatchPos + mMatchLen], Old);
- MakeChild(New, mText[mPos + mMatchLen], mPos);
-}
-
-/**
- Insert string info for current position into the String Info Log
-**/
-STATIC
-VOID
-InsertNode ()
-{
- NODE q, r, j, t;
- UINT8 c, *t1, *t2;
-
- if (mMatchLen >= 4) {
-
- //
- // We have just got a long match, the target tree
- // can be located by MatchPos + 1. Traverse 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--;
- r = (INT16)((mMatchPos + 1) | WNDSIZ);
- while ((q = mParent[r]) == NIL) {
- r = mNext[r];
- }
- while (mLevel[q] >= mMatchLen) {
- r = q; q = mParent[q];
- }
- t = q;
- while (mPosition[t] < 0) {
- mPosition[t] = mPos;
- t = mParent[t];
- }
- 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) {
- MakeChild(q, c, mPos);
- 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 ( ; ; ) {
- if (r >= WNDSIZ) {
- j = MAXMATCH;
- mMatchPos = r;
- } else {
- j = mLevel[r];
- mMatchPos = (NODE)(mPosition[r] & ~PERC_FLAG);
- }
- if (mMatchPos >= mPos) {
- mMatchPos -= WNDSIZ;
- }
- t1 = &mText[mPos + mMatchLen];
- t2 = &mText[mMatchPos + mMatchLen];
- while (mMatchLen < j) {
- if (*t1 != *t2) {
- Split(r);
- return;
- }
- mMatchLen++;
- t1++;
- t2++;
- }
- if (mMatchLen >= MAXMATCH) {
- break;
- }
- mPosition[r] = mPos;
- q = r;
- if ((r = Child(q, *t1)) == NIL) {
- MakeChild(q, *t1, mPos);
- return;
- }
- mMatchLen++;
- }
- t = mPrev[r];
- mPrev[mPos] = t;
- mNext[t] = mPos;
- t = mNext[r];
- mNext[mPos] = t;
- mPrev[t] = mPos;
- mParent[mPos] = q;
- mParent[r] = NIL;
-
- //
- // Special usage of 'next'
- //
- mNext[r] = mPos;
-
-}
-
-/**
- Delete outdated string info. (The Usage of PERC_FLAG
- ensures a clean deletion)
-**/
-STATIC
-VOID
-DeleteNode ()
-{
- NODE q, r, s, t, u;
-
- if (mParent[mPos] == NIL) {
- return;
- }
-
- r = mPrev[mPos];
- s = mNext[mPos];
- mNext[r] = s;
- mPrev[s] = r;
- r = mParent[mPos];
- mParent[mPos] = NIL;
- if (r >= WNDSIZ || --mChildCount[r] > 1) {
- return;
- }
- t = (NODE)(mPosition[r] & ~PERC_FLAG);
- if (t >= mPos) {
- t -= WNDSIZ;
- }
- s = t;
- q = mParent[r];
- while ((u = mPosition[q]) & PERC_FLAG) {
- u &= ~PERC_FLAG;
- if (u >= mPos) {
- u -= WNDSIZ;
- }
- if (u > s) {
- s = u;
- }
- mPosition[q] = (INT16)(s | WNDSIZ);
- q = mParent[q];
- }
- if (q < WNDSIZ) {
- if (u >= mPos) {
- u -= WNDSIZ;
- }
- if (u > s) {
- s = u;
- }
- mPosition[q] = (INT16)(s | WNDSIZ | PERC_FLAG);
- }
- s = Child(r, mText[t + mLevel[r]]);
- t = mPrev[s];
- u = mNext[s];
- mNext[t] = u;
- mPrev[u] = t;
- t = mPrev[r];
- mNext[t] = s;
- mPrev[s] = t;
- t = mNext[r];
- mPrev[t] = s;
- mNext[s] = t;
- mParent[s] = mParent[r];
- mParent[r] = NIL;
- mNext[r] = mAvail;
- mAvail = r;
-}
-
-/**
- Advance the current position (read in new data if needed).
- Delete outdated string info. Find a match string for current position.
-**/
-STATIC
-VOID
-GetNextMatch ()
-{
- INT32 n;
-
- mRemainder--;
- if (++mPos == WNDSIZ * 2) {
- memmove(&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
- n = FreadCrc(&mText[WNDSIZ + MAXMATCH], WNDSIZ);
- mRemainder += n;
- mPos = WNDSIZ;
- }
- DeleteNode();
- InsertNode();
-}
-
-/**
- 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
-**/
-STATIC
-EFI_STATUS
-Encode ()
-{
- EFI_STATUS Status;
- INT32 LastMatchLen;
- NODE LastMatchPos;
-
- Status = AllocateMemory();
- if (EFI_ERROR(Status)) {
- FreeMemory();
- return Status;
- }
-
- InitSlide();
-
- HufEncodeStart();
-
- mRemainder = FreadCrc(&mText[WNDSIZ], WNDSIZ + MAXMATCH);
-
- mMatchLen = 0;
- mPos = WNDSIZ;
- InsertNode();
- if (mMatchLen > mRemainder) {
- mMatchLen = mRemainder;
- }
- while (mRemainder > 0) {
- LastMatchLen = mMatchLen;
- LastMatchPos = mMatchPos;
- GetNextMatch();
- 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) {
- GetNextMatch();
- }
- if (mMatchLen > mRemainder) {
- mMatchLen = mRemainder;
- }
- }
- }
-
- HufEncodeEnd();
- FreeMemory();
- return EFI_SUCCESS;
-}
-
-/**
- Count the frequencies for the Extra Set
-**/
-STATIC
-VOID
-CountTFreq ()
-{
- INT32 i, k, n, Count;
-
- for (i = 0; i < NT; i++) {
- mTFreq[i] = 0;
- }
- n = NC;
- while (n > 0 && mCLen[n - 1] == 0) {
- n--;
- }
- i = 0;
- while (i < n) {
- k = mCLen[i++];
- if (k == 0) {
- Count = 1;
- while (i < n && mCLen[i] == 0) {
- i++;
- Count++;
- }
- if (Count <= 2) {
- mTFreq[0] = (UINT16)(mTFreq[0] + Count);
- } else if (Count <= 18) {
- mTFreq[1]++;
- } else if (Count == 19) {
- mTFreq[0]++;
- mTFreq[1]++;
- } else {
- mTFreq[2]++;
- }
- } else {
- mTFreq[k + 2]++;
- }
- }
-}
-
-/**
- Outputs the code length array for the Extra Set or the Position Set.
-
- @param n the number of symbols
- @param nbit the number of bits needed to represent 'n'
- @param Special the special symbol that needs to be take care of
-**/
-STATIC
-VOID
-WritePTLen (
- IN INT32 n,
- IN INT32 nbit,
- IN INT32 Special
- )
-{
- INT32 i, k;
-
- while (n > 0 && mPTLen[n - 1] == 0) {
- n--;
- }
- PutBits(nbit, n);
- i = 0;
- while (i < n) {
- k = mPTLen[i++];
- if (k <= 6) {
- PutBits(3, k);
- } else {
- PutBits(k - 3, (1U << (k - 3)) - 2);
- }
- if (i == Special) {
- while (i < 6 && mPTLen[i] == 0) {
- i++;
- }
- PutBits(2, (i - 3) & 3);
- }
- }
-}
-
-/**
- Outputs the code length array for Char&Length Set
-**/
-STATIC
-VOID
-WriteCLen ()
-{
- INT32 i, k, n, Count;
-
- n = NC;
- while (n > 0 && mCLen[n - 1] == 0) {
- n--;
- }
- PutBits(CBIT, n);
- i = 0;
- while (i < n) {
- k = mCLen[i++];
- if (k == 0) {
- Count = 1;
- while (i < n && mCLen[i] == 0) {
- i++;
- Count++;
- }
- if (Count <= 2) {
- for (k = 0; k < Count; k++) {
- PutBits(mPTLen[0], mPTCode[0]);
- }
- } else if (Count <= 18) {
- PutBits(mPTLen[1], mPTCode[1]);
- PutBits(4, Count - 3);
- } else if (Count == 19) {
- PutBits(mPTLen[0], mPTCode[0]);
- PutBits(mPTLen[1], mPTCode[1]);
- PutBits(4, 15);
- } else {
- PutBits(mPTLen[2], mPTCode[2]);
- PutBits(CBIT, Count - 20);
- }
- } else {
- PutBits(mPTLen[k + 2], mPTCode[k + 2]);
- }
- }
-}
-
-STATIC
-VOID
-EncodeC (
- IN INT32 c
- )
-{
- PutBits(mCLen[c], mCCode[c]);
-}
-
-STATIC
-VOID
-EncodeP (
- IN UINT32 p
- )
-{
- UINT32 c, q;
-
- c = 0;
- q = p;
- while (q) {
- q >>= 1;
- c++;
- }
- PutBits(mPTLen[c], mPTCode[c]);
- if (c > 1) {
- PutBits(c - 1, p & (0xFFFFU >> (17 - c)));
- }
-}
-
-/**
- Huffman code the block and output it.
-**/
-STATIC
-VOID
-SendBlock ()
-{
- UINT32 i, k, Flags, Root, Pos, Size;
- Flags = 0;
-
- Root = MakeTree(NC, mCFreq, mCLen, mCCode);
- Size = mCFreq[Root];
- PutBits(16, Size);
- if (Root >= NC) {
- CountTFreq();
- Root = MakeTree(NT, mTFreq, mPTLen, mPTCode);
- if (Root >= NT) {
- WritePTLen(NT, TBIT, 3);
- } else {
- PutBits(TBIT, 0);
- PutBits(TBIT, Root);
- }
- WriteCLen();
- } else {
- PutBits(TBIT, 0);
- PutBits(TBIT, 0);
- PutBits(CBIT, 0);
- PutBits(CBIT, Root);
- }
- Root = MakeTree(NP, mPFreq, mPTLen, mPTCode);
- if (Root >= NP) {
- WritePTLen(NP, PBIT, -1);
- } else {
- PutBits(PBIT, 0);
- PutBits(PBIT, Root);
- }
- Pos = 0;
- for (i = 0; i < Size; i++) {
- if (i % UINT8_BIT == 0) {
- Flags = mBuf[Pos++];
- } else {
- Flags <<= 1;
- }
- if (Flags & (1U << (UINT8_BIT - 1))) {
- EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
- k = mBuf[Pos++] << UINT8_BIT;
- k += mBuf[Pos++];
- EncodeP(k);
- } else {
- EncodeC(mBuf[Pos++]);
- }
- }
- for (i = 0; i < NC; i++) {
- mCFreq[i] = 0;
- }
- for (i = 0; i < NP; i++) {
- mPFreq[i] = 0;
- }
-}
-
-/**
- Outputs an Original Character or a Pointer
-
- @param c The original character or the 'String Length' element of a Pointer
- @param p The 'Position' field of a Pointer
-**/
-STATIC
-VOID
-Output (
- IN UINT32 c,
- IN UINT32 p
- )
-{
- STATIC UINT32 CPos;
-
- if ((mOutputMask >>= 1) == 0) {
- mOutputMask = 1U << (UINT8_BIT - 1);
- if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
- SendBlock();
- mOutputPos = 0;
- }
- CPos = mOutputPos++;
- mBuf[CPos] = 0;
- }
- mBuf[mOutputPos++] = (UINT8) c;
- mCFreq[c]++;
- if (c >= (1U << UINT8_BIT)) {
- mBuf[CPos] |= mOutputMask;
- mBuf[mOutputPos++] = (UINT8)(p >> UINT8_BIT);
- mBuf[mOutputPos++] = (UINT8) p;
- c = 0;
- while (p) {
- p >>= 1;
- c++;
- }
- mPFreq[c]++;
- }
-}
-
-STATIC
-VOID
-HufEncodeStart ()
-{
- INT32 i;
-
- for (i = 0; i < NC; i++) {
- mCFreq[i] = 0;
- }
- for (i = 0; i < NP; i++) {
- mPFreq[i] = 0;
- }
- mOutputPos = mOutputMask = 0;
- InitPutBits();
- return;
-}
-
-STATIC
-VOID
-HufEncodeEnd ()
-{
- SendBlock();
-
- //
- // Flush remaining bits
- //
- PutBits(UINT8_BIT - 1, 0);
-
- return;
-}
-
-
-STATIC
-VOID
-MakeCrcTable ()
-{
- UINT32 i, j, r;
-
- for (i = 0; i <= UINT8_MAX; i++) {
- r = i;
- for (j = 0; j < UINT8_BIT; j++) {
- if (r & 1) {
- r = (r >> 1) ^ CRCPOLY;
- } else {
- r >>= 1;
- }
- }
- mCrcTable[i] = (UINT16)r;
- }
-}
-
-/**
- Outputs rightmost n bits of x
-
- @param n the rightmost n bits of the data is used
- @param x the data
-**/
-STATIC
-VOID
-PutBits (
- IN INT32 n,
- IN UINT32 x
- )
-{
- UINT8 Temp;
-
- if (n < mBitCount) {
- mSubBitBuf |= x << (mBitCount -= n);
- } else {
-
- Temp = (UINT8)(mSubBitBuf | (x >> (n -= mBitCount)));
- if (mDst < mDstUpperLimit) {
- *mDst++ = Temp;
- }
- mCompSize++;
-
- 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);
- }
- }
-}
-
-/**
- Read in source data
-
- @param p the buffer to hold the data
- @param n number of bytes to read
-
- @return number of bytes actually read
-**/
-STATIC
-INT32
-FreadCrc (
- OUT UINT8 *p,
- IN INT32 n
- )
-{
- INT32 i;
-
- for (i = 0; mSrc < mSrcUpperLimit && i < n; i++) {
- *p++ = *mSrc++;
- }
- n = i;
-
- p -= n;
- mOrigSize += n;
- while (--i >= 0) {
- UPDATE_CRC(*p++);
- }
- return n;
-}
-
-
-STATIC
-VOID
-InitPutBits ()
-{
- mBitCount = UINT8_BIT;
- mSubBitBuf = 0;
-}
-
-/**
- Count the number of each code length for a Huffman tree.
-
- @param i the top node
-**/
-STATIC
-VOID
-CountLen (
- IN INT32 i
- )
-{
- STATIC INT32 Depth = 0;
-
- if (i < mN) {
- mLenCnt[(Depth < 16) ? Depth : 16]++;
- } else {
- Depth++;
- CountLen(mLeft [i]);
- CountLen(mRight[i]);
- Depth--;
- }
-}
-
-/**
- Create code length array for a Huffman tree
-
- @param Root the root of the tree
-**/
-STATIC
-VOID
-MakeLen (
- IN INT32 Root
- )
-{
- INT32 i, k;
- UINT32 Cum;
-
- for (i = 0; i <= 16; i++) {
- 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);
- }
- while (Cum != (1U << 16)) {
- mLenCnt[16]--;
- for (i = 15; i > 0; i--) {
- if (mLenCnt[i] != 0) {
- mLenCnt[i]--;
- mLenCnt[i+1] += 2;
- break;
- }
- }
- Cum--;
- }
- for (i = 16; i > 0; i--) {
- k = mLenCnt[i];
- while (--k >= 0) {
- mLen[*mSortPtr++] = (UINT8)i;
- }
- }
-}
-
-STATIC
-VOID
-DownHeap (
- IN INT32 i
- )
-{
- INT32 j, k;
-
- //
- // 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]]) {
- j++;
- }
- if (mFreq[k] <= mFreq[mHeap[j]]) {
- break;
- }
- mHeap[i] = mHeap[j];
- i = j;
- }
- mHeap[i] = (INT16)k;
-}
-
-/**
- Assign code to each symbol based on the code length array
-
- @param n number of symbols
- @param Len the code length array
- @param Code stores codes for each symbol
-**/
-STATIC
-VOID
-MakeCode (
- IN INT32 n,
- IN UINT8 Len[],
- OUT UINT16 Code[]
- )
-{
- INT32 i;
- UINT16 Start[18];
-
- Start[1] = 0;
- for (i = 1; i <= 16; i++) {
- Start[i + 1] = (UINT16)((Start[i] + mLenCnt[i]) << 1);
- }
- for (i = 0; i < n; i++) {
- Code[i] = Start[Len[i]]++;
- }
-}
-
-/**
- Generates Huffman codes given a frequency distribution of symbols
-
- @param NParm number of symbols
- @param FreqParm frequency of each symbol
- @param LenParm code length for each symbol
- @param CodeParm code for each symbol
-
- @return Root of the Huffman tree.
-**/
-STATIC
-INT32
-MakeTree (
- IN INT32 NParm,
- IN UINT16 FreqParm[],
- OUT UINT8 LenParm[],
- OUT UINT16 CodeParm[]
- )
-{
- INT32 i, j, k, Avail;
-
- //
- // make tree, calculate len[], return root
- //
-
- mN = NParm;
- mFreq = FreqParm;
- mLen = LenParm;
- Avail = mN;
- mHeapSize = 0;
- mHeap[1] = 0;
- for (i = 0; i < mN; i++) {
- 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
- //
- DownHeap(i);
- }
- mSortPtr = CodeParm;
- do {
- i = mHeap[1];
- if (i < mN) {
- *mSortPtr++ = (UINT16)i;
- }
- mHeap[1] = mHeap[mHeapSize--];
- DownHeap(1);
- j = mHeap[1];
- if (j < mN) {
- *mSortPtr++ = (UINT16)j;
- }
- k = Avail++;
- mFreq[k] = (UINT16)(mFreq[i] + mFreq[j]);
- mHeap[1] = (INT16)k;
- DownHeap(1);
- mLeft[k] = (UINT16)i;
- mRight[k] = (UINT16)j;
- } while (mHeapSize > 1);
-
- mSortPtr = CodeParm;
- MakeLen(k);
- MakeCode(NParm, LenParm, CodeParm);
-
- //
- // return root
- //
- return k;
-}
-
+/** @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
+and Huffman codings are applied to each Block.
+
+Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.<BR>
+SPDX-License-Identifier: BSD-2-Clause-Patent
+
+**/
+
+#include "Compress.h"
+
+
+//
+// Macro Definitions
+//
+
+#undef UINT8_MAX
+typedef INT16 NODE;
+#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 PERC_FLAG 0x8000U
+#define CODE_BIT 16
+#define NIL 0
+#define MAX_HASH_VAL (3 * WNDSIZ + (WNDSIZ / 512 + 1) * UINT8_MAX)
+#define HASH(p, c) ((p) + ((c) << (WNDBIT - 9)) + WNDSIZ * 2)
+#define CRCPOLY 0xA001
+#define UPDATE_CRC(c) mCrc = mCrcTable[(mCrc ^ (c)) & 0xFF] ^ (mCrc >> UINT8_BIT)
+
+//
+// C: the Char&Len Set; P: the Position Set; T: the exTra Set
+//
+
+#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
+#if NT > NP
+ #define NPT NT
+#else
+ #define NPT NP
+#endif
+
+//
+// Function Prototypes
+//
+
+STATIC
+VOID
+PutDword(
+ IN UINT32 Data
+ );
+
+STATIC
+EFI_STATUS
+AllocateMemory (
+ );
+
+STATIC
+VOID
+FreeMemory (
+ );
+
+STATIC
+VOID
+InitSlide (
+ );
+
+STATIC
+NODE
+Child (
+ IN NODE q,
+ IN UINT8 c
+ );
+
+STATIC
+VOID
+MakeChild (
+ IN NODE q,
+ IN UINT8 c,
+ IN NODE r
+ );
+
+STATIC
+VOID
+Split (
+ IN NODE Old
+ );
+
+STATIC
+VOID
+InsertNode (
+ );
+
+STATIC
+VOID
+DeleteNode (
+ );
+
+STATIC
+VOID
+GetNextMatch (
+ );
+
+STATIC
+EFI_STATUS
+Encode (
+ );
+
+STATIC
+VOID
+CountTFreq (
+ );
+
+STATIC
+VOID
+WritePTLen (
+ IN INT32 n,
+ IN INT32 nbit,
+ IN INT32 Special
+ );
+
+STATIC
+VOID
+WriteCLen (
+ );
+
+STATIC
+VOID
+EncodeC (
+ IN INT32 c
+ );
+
+STATIC
+VOID
+EncodeP (
+ IN UINT32 p
+ );
+
+STATIC
+VOID
+SendBlock (
+ );
+
+STATIC
+VOID
+Output (
+ IN UINT32 c,
+ IN UINT32 p
+ );
+
+STATIC
+VOID
+HufEncodeStart (
+ );
+
+STATIC
+VOID
+HufEncodeEnd (
+ );
+
+STATIC
+VOID
+MakeCrcTable (
+ );
+
+STATIC
+VOID
+PutBits (
+ IN INT32 n,
+ IN UINT32 x
+ );
+
+STATIC
+INT32
+FreadCrc (
+ OUT UINT8 *p,
+ IN INT32 n
+ );
+
+STATIC
+VOID
+InitPutBits (
+ );
+
+STATIC
+VOID
+CountLen (
+ IN INT32 i
+ );
+
+STATIC
+VOID
+MakeLen (
+ IN INT32 Root
+ );
+
+STATIC
+VOID
+DownHeap (
+ IN INT32 i
+ );
+
+STATIC
+VOID
+MakeCode (
+ IN INT32 n,
+ IN UINT8 Len[],
+ OUT UINT16 Code[]
+ );
+
+STATIC
+INT32
+MakeTree (
+ IN INT32 NParm,
+ IN UINT16 FreqParm[],
+ OUT UINT8 LenParm[],
+ OUT UINT16 CodeParm[]
+ );
+
+
+//
+// Global Variables
+//
+
+STATIC UINT8 *mSrc, *mDst, *mSrcUpperLimit, *mDstUpperLimit;
+
+STATIC UINT8 *mLevel, *mText, *mChildCount, *mBuf, mCLen[NC], mPTLen[NPT], *mLen;
+STATIC INT16 mHeap[NC + 1];
+STATIC INT32 mRemainder, mMatchLen, mBitCount, mHeapSize, mN;
+STATIC UINT32 mBufSiz = 0, mOutputPos, mOutputMask, mSubBitBuf, mCrc;
+STATIC UINT32 mCompSize, mOrigSize;
+
+STATIC UINT16 *mFreq, *mSortPtr, mLenCnt[17], mLeft[2 * NC - 1], mRight[2 * NC - 1],
+ mCrcTable[UINT8_MAX + 1], mCFreq[2 * NC - 1],mCCode[NC],
+ mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];
+
+STATIC NODE mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;
+
+
+//
+// functions
+//
+
+/**
+ The main compression routine.
+
+ @param SrcBuffer The buffer storing the source data
+ @param SrcSize The size of source data
+ @param DstBuffer The buffer to store the compressed data
+ @param DstSize On input, the size of DstBuffer; On output,
+ the size of the actual compressed data.
+
+ @retval EFI_BUFFER_TOO_SMALL The DstBuffer is too small. In this case,
+ DstSize contains the size needed.
+ @retval EFI_SUCCESS Compression is successful.
+
+**/
+EFI_STATUS
+EfiCompress (
+ IN UINT8 *SrcBuffer,
+ IN UINT32 SrcSize,
+ IN UINT8 *DstBuffer,
+ IN OUT UINT32 *DstSize
+ )
+{
+ EFI_STATUS Status = EFI_SUCCESS;
+
+ //
+ // Initializations
+ //
+ mBufSiz = 0;
+ mBuf = NULL;
+ mText = NULL;
+ mLevel = NULL;
+ mChildCount = NULL;
+ mPosition = NULL;
+ mParent = NULL;
+ mPrev = NULL;
+ mNext = NULL;
+
+
+ mSrc = SrcBuffer;
+ mSrcUpperLimit = mSrc + SrcSize;
+ mDst = DstBuffer;
+ mDstUpperLimit = mDst + *DstSize;
+
+ 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
+ //
+ mDst = DstBuffer;
+ PutDword(mCompSize+1);
+ PutDword(mOrigSize);
+
+ //
+ // Return
+ //
+
+ if (mCompSize + 1 + 8 > *DstSize) {
+ *DstSize = mCompSize + 1 + 8;
+ return EFI_BUFFER_TOO_SMALL;
+ } else {
+ *DstSize = mCompSize + 1 + 8;
+ return EFI_SUCCESS;
+ }
+
+}
+
+/**
+ Put a dword to output stream
+
+ @param Data the dword to put
+**/
+STATIC
+VOID
+PutDword(
+ IN UINT32 Data
+ )
+{
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = (UINT8)(((UINT8)(Data )) & 0xff);
+ }
+
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = (UINT8)(((UINT8)(Data >> 0x08)) & 0xff);
+ }
+
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = (UINT8)(((UINT8)(Data >> 0x10)) & 0xff);
+ }
+
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = (UINT8)(((UINT8)(Data >> 0x18)) & 0xff);
+ }
+}
+
+/**
+ Allocate memory spaces for data structures used in compression process
+
+ @retval EFI_SUCCESS Memory is allocated successfully
+ @retva; EFI_OUT_OF_RESOURCES Allocation fails
+**/
+STATIC
+EFI_STATUS
+AllocateMemory ()
+{
+ UINT32 i;
+
+ mText = malloc (WNDSIZ * 2 + MAXMATCH);
+ if (mText == NULL) {
+ return EFI_OUT_OF_RESOURCES;
+ }
+ for (i = 0 ; i < WNDSIZ * 2 + MAXMATCH; i ++) {
+ mText[i] = 0;
+ }
+
+ mLevel = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mLevel));
+ mChildCount = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mChildCount));
+ mPosition = malloc ((WNDSIZ + UINT8_MAX + 1) * sizeof(*mPosition));
+ mParent = malloc (WNDSIZ * 2 * sizeof(*mParent));
+ mPrev = malloc (WNDSIZ * 2 * sizeof(*mPrev));
+ mNext = malloc ((MAX_HASH_VAL + 1) * sizeof(*mNext));
+ if (mLevel == NULL || mChildCount == NULL || mPosition == NULL ||
+ mParent == NULL || mPrev == NULL || mNext == NULL) {
+ return EFI_OUT_OF_RESOURCES;
+ }
+
+ mBufSiz = 16 * 1024U;
+ while ((mBuf = malloc(mBufSiz)) == NULL) {
+ mBufSiz = (mBufSiz / 10U) * 9U;
+ if (mBufSiz < 4 * 1024U) {
+ return EFI_OUT_OF_RESOURCES;
+ }
+ }
+ mBuf[0] = 0;
+
+ return EFI_SUCCESS;
+}
+
+/**
+ Called when compression is completed to free memory previously allocated.
+**/
+VOID
+FreeMemory ()
+{
+ 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;
+}
+
+/**
+ Initialize String Info Log data structures
+**/
+STATIC
+VOID
+InitSlide ()
+{
+ NODE i;
+
+ for (i = WNDSIZ; i <= WNDSIZ + UINT8_MAX; i++) {
+ mLevel[i] = 1;
+ mPosition[i] = NIL; /* sentinel */
+ }
+ 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;
+ }
+}
+
+/**
+ Find child node given the parent node and the edge character
+
+ @param q the parent node
+ @param c the edge character
+
+ @return The child node (NIL if not found)
+**/
+STATIC
+NODE
+Child (
+ IN NODE q,
+ IN UINT8 c
+ )
+{
+ NODE r;
+
+ r = mNext[HASH(q, c)];
+ mParent[NIL] = q; /* sentinel */
+ while (mParent[r] != q) {
+ r = mNext[r];
+ }
+
+ return r;
+}
+
+/**
+ Create a new child for a given parent node.
+
+ @param q the parent node
+ @param c the edge character
+ @param r the child node
+**/
+STATIC
+VOID
+MakeChild (
+ IN NODE q,
+ IN UINT8 c,
+ IN NODE r
+ )
+{
+ NODE h, t;
+
+ h = (NODE)HASH(q, c);
+ t = mNext[h];
+ mNext[h] = r;
+ mNext[r] = t;
+ mPrev[t] = r;
+ mPrev[r] = h;
+ mParent[r] = q;
+ mChildCount[q]++;
+}
+
+/**
+ Split a node.
+
+ @param Old the node to split
+**/
+STATIC
+VOID
+Split (
+ NODE Old
+ )
+{
+ NODE New, t;
+
+ New = mAvail;
+ mAvail = mNext[New];
+ mChildCount[New] = 0;
+ t = mPrev[Old];
+ mPrev[New] = t;
+ mNext[t] = New;
+ t = mNext[Old];
+ mNext[New] = t;
+ mPrev[t] = New;
+ mParent[New] = mParent[Old];
+ mLevel[New] = (UINT8)mMatchLen;
+ mPosition[New] = mPos;
+ MakeChild(New, mText[mMatchPos + mMatchLen], Old);
+ MakeChild(New, mText[mPos + mMatchLen], mPos);
+}
+
+/**
+ Insert string info for current position into the String Info Log
+**/
+STATIC
+VOID
+InsertNode ()
+{
+ NODE q, r, j, t;
+ UINT8 c, *t1, *t2;
+
+ if (mMatchLen >= 4) {
+
+ //
+ // We have just got a long match, the target tree
+ // can be located by MatchPos + 1. Traverse 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--;
+ r = (INT16)((mMatchPos + 1) | WNDSIZ);
+ while ((q = mParent[r]) == NIL) {
+ r = mNext[r];
+ }
+ while (mLevel[q] >= mMatchLen) {
+ r = q; q = mParent[q];
+ }
+ t = q;
+ while (mPosition[t] < 0) {
+ mPosition[t] = mPos;
+ t = mParent[t];
+ }
+ 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) {
+ MakeChild(q, c, mPos);
+ 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 ( ; ; ) {
+ if (r >= WNDSIZ) {
+ j = MAXMATCH;
+ mMatchPos = r;
+ } else {
+ j = mLevel[r];
+ mMatchPos = (NODE)(mPosition[r] & ~PERC_FLAG);
+ }
+ if (mMatchPos >= mPos) {
+ mMatchPos -= WNDSIZ;
+ }
+ t1 = &mText[mPos + mMatchLen];
+ t2 = &mText[mMatchPos + mMatchLen];
+ while (mMatchLen < j) {
+ if (*t1 != *t2) {
+ Split(r);
+ return;
+ }
+ mMatchLen++;
+ t1++;
+ t2++;
+ }
+ if (mMatchLen >= MAXMATCH) {
+ break;
+ }
+ mPosition[r] = mPos;
+ q = r;
+ if ((r = Child(q, *t1)) == NIL) {
+ MakeChild(q, *t1, mPos);
+ return;
+ }
+ mMatchLen++;
+ }
+ t = mPrev[r];
+ mPrev[mPos] = t;
+ mNext[t] = mPos;
+ t = mNext[r];
+ mNext[mPos] = t;
+ mPrev[t] = mPos;
+ mParent[mPos] = q;
+ mParent[r] = NIL;
+
+ //
+ // Special usage of 'next'
+ //
+ mNext[r] = mPos;
+
+}
+
+/**
+ Delete outdated string info. (The Usage of PERC_FLAG
+ ensures a clean deletion)
+**/
+STATIC
+VOID
+DeleteNode ()
+{
+ NODE q, r, s, t, u;
+
+ if (mParent[mPos] == NIL) {
+ return;
+ }
+
+ r = mPrev[mPos];
+ s = mNext[mPos];
+ mNext[r] = s;
+ mPrev[s] = r;
+ r = mParent[mPos];
+ mParent[mPos] = NIL;
+ if (r >= WNDSIZ || --mChildCount[r] > 1) {
+ return;
+ }
+ t = (NODE)(mPosition[r] & ~PERC_FLAG);
+ if (t >= mPos) {
+ t -= WNDSIZ;
+ }
+ s = t;
+ q = mParent[r];
+ while ((u = mPosition[q]) & PERC_FLAG) {
+ u &= ~PERC_FLAG;
+ if (u >= mPos) {
+ u -= WNDSIZ;
+ }
+ if (u > s) {
+ s = u;
+ }
+ mPosition[q] = (INT16)(s | WNDSIZ);
+ q = mParent[q];
+ }
+ if (q < WNDSIZ) {
+ if (u >= mPos) {
+ u -= WNDSIZ;
+ }
+ if (u > s) {
+ s = u;
+ }
+ mPosition[q] = (INT16)(s | WNDSIZ | PERC_FLAG);
+ }
+ s = Child(r, mText[t + mLevel[r]]);
+ t = mPrev[s];
+ u = mNext[s];
+ mNext[t] = u;
+ mPrev[u] = t;
+ t = mPrev[r];
+ mNext[t] = s;
+ mPrev[s] = t;
+ t = mNext[r];
+ mPrev[t] = s;
+ mNext[s] = t;
+ mParent[s] = mParent[r];
+ mParent[r] = NIL;
+ mNext[r] = mAvail;
+ mAvail = r;
+}
+
+/**
+ Advance the current position (read in new data if needed).
+ Delete outdated string info. Find a match string for current position.
+**/
+STATIC
+VOID
+GetNextMatch ()
+{
+ INT32 n;
+
+ mRemainder--;
+ if (++mPos == WNDSIZ * 2) {
+ memmove(&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);
+ n = FreadCrc(&mText[WNDSIZ + MAXMATCH], WNDSIZ);
+ mRemainder += n;
+ mPos = WNDSIZ;
+ }
+ DeleteNode();
+ InsertNode();
+}
+
+/**
+ 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
+**/
+STATIC
+EFI_STATUS
+Encode ()
+{
+ EFI_STATUS Status;
+ INT32 LastMatchLen;
+ NODE LastMatchPos;
+
+ Status = AllocateMemory();
+ if (EFI_ERROR(Status)) {
+ FreeMemory();
+ return Status;
+ }
+
+ InitSlide();
+
+ HufEncodeStart();
+
+ mRemainder = FreadCrc(&mText[WNDSIZ], WNDSIZ + MAXMATCH);
+
+ mMatchLen = 0;
+ mPos = WNDSIZ;
+ InsertNode();
+ if (mMatchLen > mRemainder) {
+ mMatchLen = mRemainder;
+ }
+ while (mRemainder > 0) {
+ LastMatchLen = mMatchLen;
+ LastMatchPos = mMatchPos;
+ GetNextMatch();
+ 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) {
+ GetNextMatch();
+ }
+ if (mMatchLen > mRemainder) {
+ mMatchLen = mRemainder;
+ }
+ }
+ }
+
+ HufEncodeEnd();
+ FreeMemory();
+ return EFI_SUCCESS;
+}
+
+/**
+ Count the frequencies for the Extra Set
+**/
+STATIC
+VOID
+CountTFreq ()
+{
+ INT32 i, k, n, Count;
+
+ for (i = 0; i < NT; i++) {
+ mTFreq[i] = 0;
+ }
+ n = NC;
+ while (n > 0 && mCLen[n - 1] == 0) {
+ n--;
+ }
+ i = 0;
+ while (i < n) {
+ k = mCLen[i++];
+ if (k == 0) {
+ Count = 1;
+ while (i < n && mCLen[i] == 0) {
+ i++;
+ Count++;
+ }
+ if (Count <= 2) {
+ mTFreq[0] = (UINT16)(mTFreq[0] + Count);
+ } else if (Count <= 18) {
+ mTFreq[1]++;
+ } else if (Count == 19) {
+ mTFreq[0]++;
+ mTFreq[1]++;
+ } else {
+ mTFreq[2]++;
+ }
+ } else {
+ mTFreq[k + 2]++;
+ }
+ }
+}
+
+/**
+ Outputs the code length array for the Extra Set or the Position Set.
+
+ @param n the number of symbols
+ @param nbit the number of bits needed to represent 'n'
+ @param Special the special symbol that needs to be take care of
+**/
+STATIC
+VOID
+WritePTLen (
+ IN INT32 n,
+ IN INT32 nbit,
+ IN INT32 Special
+ )
+{
+ INT32 i, k;
+
+ while (n > 0 && mPTLen[n - 1] == 0) {
+ n--;
+ }
+ PutBits(nbit, n);
+ i = 0;
+ while (i < n) {
+ k = mPTLen[i++];
+ if (k <= 6) {
+ PutBits(3, k);
+ } else {
+ PutBits(k - 3, (1U << (k - 3)) - 2);
+ }
+ if (i == Special) {
+ while (i < 6 && mPTLen[i] == 0) {
+ i++;
+ }
+ PutBits(2, (i - 3) & 3);
+ }
+ }
+}
+
+/**
+ Outputs the code length array for Char&Length Set
+**/
+STATIC
+VOID
+WriteCLen ()
+{
+ INT32 i, k, n, Count;
+
+ n = NC;
+ while (n > 0 && mCLen[n - 1] == 0) {
+ n--;
+ }
+ PutBits(CBIT, n);
+ i = 0;
+ while (i < n) {
+ k = mCLen[i++];
+ if (k == 0) {
+ Count = 1;
+ while (i < n && mCLen[i] == 0) {
+ i++;
+ Count++;
+ }
+ if (Count <= 2) {
+ for (k = 0; k < Count; k++) {
+ PutBits(mPTLen[0], mPTCode[0]);
+ }
+ } else if (Count <= 18) {
+ PutBits(mPTLen[1], mPTCode[1]);
+ PutBits(4, Count - 3);
+ } else if (Count == 19) {
+ PutBits(mPTLen[0], mPTCode[0]);
+ PutBits(mPTLen[1], mPTCode[1]);
+ PutBits(4, 15);
+ } else {
+ PutBits(mPTLen[2], mPTCode[2]);
+ PutBits(CBIT, Count - 20);
+ }
+ } else {
+ PutBits(mPTLen[k + 2], mPTCode[k + 2]);
+ }
+ }
+}
+
+STATIC
+VOID
+EncodeC (
+ IN INT32 c
+ )
+{
+ PutBits(mCLen[c], mCCode[c]);
+}
+
+STATIC
+VOID
+EncodeP (
+ IN UINT32 p
+ )
+{
+ UINT32 c, q;
+
+ c = 0;
+ q = p;
+ while (q) {
+ q >>= 1;
+ c++;
+ }
+ PutBits(mPTLen[c], mPTCode[c]);
+ if (c > 1) {
+ PutBits(c - 1, p & (0xFFFFU >> (17 - c)));
+ }
+}
+
+/**
+ Huffman code the block and output it.
+**/
+STATIC
+VOID
+SendBlock ()
+{
+ UINT32 i, k, Flags, Root, Pos, Size;
+ Flags = 0;
+
+ Root = MakeTree(NC, mCFreq, mCLen, mCCode);
+ Size = mCFreq[Root];
+ PutBits(16, Size);
+ if (Root >= NC) {
+ CountTFreq();
+ Root = MakeTree(NT, mTFreq, mPTLen, mPTCode);
+ if (Root >= NT) {
+ WritePTLen(NT, TBIT, 3);
+ } else {
+ PutBits(TBIT, 0);
+ PutBits(TBIT, Root);
+ }
+ WriteCLen();
+ } else {
+ PutBits(TBIT, 0);
+ PutBits(TBIT, 0);
+ PutBits(CBIT, 0);
+ PutBits(CBIT, Root);
+ }
+ Root = MakeTree(NP, mPFreq, mPTLen, mPTCode);
+ if (Root >= NP) {
+ WritePTLen(NP, PBIT, -1);
+ } else {
+ PutBits(PBIT, 0);
+ PutBits(PBIT, Root);
+ }
+ Pos = 0;
+ for (i = 0; i < Size; i++) {
+ if (i % UINT8_BIT == 0) {
+ Flags = mBuf[Pos++];
+ } else {
+ Flags <<= 1;
+ }
+ if (Flags & (1U << (UINT8_BIT - 1))) {
+ EncodeC(mBuf[Pos++] + (1U << UINT8_BIT));
+ k = mBuf[Pos++] << UINT8_BIT;
+ k += mBuf[Pos++];
+ EncodeP(k);
+ } else {
+ EncodeC(mBuf[Pos++]);
+ }
+ }
+ for (i = 0; i < NC; i++) {
+ mCFreq[i] = 0;
+ }
+ for (i = 0; i < NP; i++) {
+ mPFreq[i] = 0;
+ }
+}
+
+/**
+ Outputs an Original Character or a Pointer
+
+ @param c The original character or the 'String Length' element of a Pointer
+ @param p The 'Position' field of a Pointer
+**/
+STATIC
+VOID
+Output (
+ IN UINT32 c,
+ IN UINT32 p
+ )
+{
+ STATIC UINT32 CPos;
+
+ if ((mOutputMask >>= 1) == 0) {
+ mOutputMask = 1U << (UINT8_BIT - 1);
+ if (mOutputPos >= mBufSiz - 3 * UINT8_BIT) {
+ SendBlock();
+ mOutputPos = 0;
+ }
+ CPos = mOutputPos++;
+ mBuf[CPos] = 0;
+ }
+ mBuf[mOutputPos++] = (UINT8) c;
+ mCFreq[c]++;
+ if (c >= (1U << UINT8_BIT)) {
+ mBuf[CPos] |= mOutputMask;
+ mBuf[mOutputPos++] = (UINT8)(p >> UINT8_BIT);
+ mBuf[mOutputPos++] = (UINT8) p;
+ c = 0;
+ while (p) {
+ p >>= 1;
+ c++;
+ }
+ mPFreq[c]++;
+ }
+}
+
+STATIC
+VOID
+HufEncodeStart ()
+{
+ INT32 i;
+
+ for (i = 0; i < NC; i++) {
+ mCFreq[i] = 0;
+ }
+ for (i = 0; i < NP; i++) {
+ mPFreq[i] = 0;
+ }
+ mOutputPos = mOutputMask = 0;
+ InitPutBits();
+ return;
+}
+
+STATIC
+VOID
+HufEncodeEnd ()
+{
+ SendBlock();
+
+ //
+ // Flush remaining bits
+ //
+ PutBits(UINT8_BIT - 1, 0);
+
+ return;
+}
+
+
+STATIC
+VOID
+MakeCrcTable ()
+{
+ UINT32 i, j, r;
+
+ for (i = 0; i <= UINT8_MAX; i++) {
+ r = i;
+ for (j = 0; j < UINT8_BIT; j++) {
+ if (r & 1) {
+ r = (r >> 1) ^ CRCPOLY;
+ } else {
+ r >>= 1;
+ }
+ }
+ mCrcTable[i] = (UINT16)r;
+ }
+}
+
+/**
+ Outputs rightmost n bits of x
+
+ @param n the rightmost n bits of the data is used
+ @param x the data
+**/
+STATIC
+VOID
+PutBits (
+ IN INT32 n,
+ IN UINT32 x
+ )
+{
+ UINT8 Temp;
+
+ if (n < mBitCount) {
+ mSubBitBuf |= x << (mBitCount -= n);
+ } else {
+
+ Temp = (UINT8)(mSubBitBuf | (x >> (n -= mBitCount)));
+ if (mDst < mDstUpperLimit) {
+ *mDst++ = Temp;
+ }
+ mCompSize++;
+
+ 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);
+ }
+ }
+}
+
+/**
+ Read in source data
+
+ @param p the buffer to hold the data
+ @param n number of bytes to read
+
+ @return number of bytes actually read
+**/
+STATIC
+INT32
+FreadCrc (
+ OUT UINT8 *p,
+ IN INT32 n
+ )
+{
+ INT32 i;
+
+ for (i = 0; mSrc < mSrcUpperLimit && i < n; i++) {
+ *p++ = *mSrc++;
+ }
+ n = i;
+
+ p -= n;
+ mOrigSize += n;
+ while (--i >= 0) {
+ UPDATE_CRC(*p++);
+ }
+ return n;
+}
+
+
+STATIC
+VOID
+InitPutBits ()
+{
+ mBitCount = UINT8_BIT;
+ mSubBitBuf = 0;
+}
+
+/**
+ Count the number of each code length for a Huffman tree.
+
+ @param i the top node
+**/
+STATIC
+VOID
+CountLen (
+ IN INT32 i
+ )
+{
+ STATIC INT32 Depth = 0;
+
+ if (i < mN) {
+ mLenCnt[(Depth < 16) ? Depth : 16]++;
+ } else {
+ Depth++;
+ CountLen(mLeft [i]);
+ CountLen(mRight[i]);
+ Depth--;
+ }
+}
+
+/**
+ Create code length array for a Huffman tree
+
+ @param Root the root of the tree
+**/
+STATIC
+VOID
+MakeLen (
+ IN INT32 Root
+ )
+{
+ INT32 i, k;
+ UINT32 Cum;
+
+ for (i = 0; i <= 16; i++) {
+ 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);
+ }
+ while (Cum != (1U << 16)) {
+ mLenCnt[16]--;
+ for (i = 15; i > 0; i--) {
+ if (mLenCnt[i] != 0) {
+ mLenCnt[i]--;
+ mLenCnt[i+1] += 2;
+ break;
+ }
+ }
+ Cum--;
+ }
+ for (i = 16; i > 0; i--) {
+ k = mLenCnt[i];
+ while (--k >= 0) {
+ mLen[*mSortPtr++] = (UINT8)i;
+ }
+ }
+}
+
+STATIC
+VOID
+DownHeap (
+ IN INT32 i
+ )
+{
+ INT32 j, k;
+
+ //
+ // 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]]) {
+ j++;
+ }
+ if (mFreq[k] <= mFreq[mHeap[j]]) {
+ break;
+ }
+ mHeap[i] = mHeap[j];
+ i = j;
+ }
+ mHeap[i] = (INT16)k;
+}
+
+/**
+ Assign code to each symbol based on the code length array
+
+ @param n number of symbols
+ @param Len the code length array
+ @param Code stores codes for each symbol
+**/
+STATIC
+VOID
+MakeCode (
+ IN INT32 n,
+ IN UINT8 Len[],
+ OUT UINT16 Code[]
+ )
+{
+ INT32 i;
+ UINT16 Start[18];
+
+ Start[1] = 0;
+ for (i = 1; i <= 16; i++) {
+ Start[i + 1] = (UINT16)((Start[i] + mLenCnt[i]) << 1);
+ }
+ for (i = 0; i < n; i++) {
+ Code[i] = Start[Len[i]]++;
+ }
+}
+
+/**
+ Generates Huffman codes given a frequency distribution of symbols
+
+ @param NParm number of symbols
+ @param FreqParm frequency of each symbol
+ @param LenParm code length for each symbol
+ @param CodeParm code for each symbol
+
+ @return Root of the Huffman tree.
+**/
+STATIC
+INT32
+MakeTree (
+ IN INT32 NParm,
+ IN UINT16 FreqParm[],
+ OUT UINT8 LenParm[],
+ OUT UINT16 CodeParm[]
+ )
+{
+ INT32 i, j, k, Avail;
+
+ //
+ // make tree, calculate len[], return root
+ //
+
+ mN = NParm;
+ mFreq = FreqParm;
+ mLen = LenParm;
+ Avail = mN;
+ mHeapSize = 0;
+ mHeap[1] = 0;
+ for (i = 0; i < mN; i++) {
+ 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
+ //
+ DownHeap(i);
+ }
+ mSortPtr = CodeParm;
+ do {
+ i = mHeap[1];
+ if (i < mN) {
+ *mSortPtr++ = (UINT16)i;
+ }
+ mHeap[1] = mHeap[mHeapSize--];
+ DownHeap(1);
+ j = mHeap[1];
+ if (j < mN) {
+ *mSortPtr++ = (UINT16)j;
+ }
+ k = Avail++;
+ mFreq[k] = (UINT16)(mFreq[i] + mFreq[j]);
+ mHeap[1] = (INT16)k;
+ DownHeap(1);
+ mLeft[k] = (UINT16)i;
+ mRight[k] = (UINT16)j;
+ } while (mHeapSize > 1);
+
+ mSortPtr = CodeParm;
+ MakeLen(k);
+ MakeCode(NParm, LenParm, CodeParm);
+
+ //
+ // return root
+ //
+ return k;
+}
+
generated by cgit v1.2.3 (git 2.39.0) at 2026-09-14 02:54:09 +0300