#include "Compress.h"

#undef UINT8_MAX

typedef INT32 NODE;

#define UINT8_MAX 0xff

#define UINT8_BIT 8

#define THRESHOLD 3

#define INIT_CRC 0

#define WNDBIT 19

#define WNDSIZ (1U << WNDBIT)

#define MAXMATCH 256

#define BLKSIZ (1U << 14) // 16 * 1024U

#define PERC_FLAG 0x80000000U

#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)

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

#define CBIT 9

#define NP (WNDBIT + 1)

#define PBIT 5

#define NT (CODE_BIT + 3)

#define TBIT 5

#if NT > NP

#define NPT NT

#define NPT NP

PutDword(

IN UINT32 Data

);

AllocateMemory (

VOID

);

FreeMemory (

VOID

);

InitSlide (

VOID

);

Child (

IN NODE NodeQ,

IN UINT8 CharC

);

MakeChild (

);

Split (

IN NODE Old

);

InsertNode (

VOID

);

DeleteNode (

VOID

);

GetNextMatch (

VOID

);

Encode (

VOID

);

CountTFreq (

VOID

);

WritePTLen (

);

WriteCLen (

VOID

);

EncodeC (

IN INT32 Value

);

EncodeP (

IN UINT32 Value

);

SendBlock (

VOID

);

Output (

IN UINT32 c,

IN UINT32 p

);

HufEncodeStart (

VOID

);

HufEncodeEnd (

VOID

);

MakeCrcTable (

VOID

);

PutBits (

IN INT32 Number,

IN UINT32 Value

);

FreadCrc (

OUT UINT8 *Pointer,

IN INT32 Number

);

InitPutBits (

VOID

);

CountLen (

IN INT32 Index

);

MakeLen (

IN INT32 Root

);

DownHeap (

IN INT32 Index

);

MakeCode (

);

MakeTree (

);

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;

TianoCompress (

)

{

EFI_STATUS Status;

//

// 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;

}

}

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);

}

}

AllocateMemory (

VOID

)

{

UINT32 Index;

mText = malloc (WNDSIZ * 2 + MAXMATCH);

for (Index = 0; Index < WNDSIZ * 2 + MAXMATCH; Index++) {

mText[Index] = 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));

mBufSiz = BLKSIZ;

mBuf = malloc (mBufSiz);

while (mBuf == NULL) {

mBufSiz = (mBufSiz / 10U) * 9U;

if (mBufSiz < 4 * 1024U) {

return EFI_OUT_OF_RESOURCES;

}

mBuf = malloc (mBufSiz);

}

mBuf[0] = 0;

return EFI_SUCCESS;

}

FreeMemory (

VOID

)

{

if (mText != NULL) {

free (mText);

}

if (mLevel != NULL) {

free (mLevel);

}

if (mChildCount != NULL) {

free (mChildCount);

}

if (mPosition != NULL) {

free (mPosition);

}

if (mParent != NULL) {

free (mParent);

}

if (mPrev != NULL) {

free (mPrev);

}

if (mNext != NULL) {

free (mNext);

}

if (mBuf != NULL) {

free (mBuf);

}

return ;

}

InitSlide (

VOID

)

{

NODE Index;

for (Index = WNDSIZ; Index <= WNDSIZ + UINT8_MAX; Index++) {

mLevel[Index] = 1;

mPosition[Index] = NIL; /* sentinel */

}

for (Index = WNDSIZ; Index < WNDSIZ * 2; Index++) {

mParent[Index] = NIL;

}

mAvail = 1;

for (Index = 1; Index < WNDSIZ - 1; Index++) {

mNext[Index] = (NODE) (Index + 1);

}

mNext[WNDSIZ - 1] = NIL;

for (Index = WNDSIZ * 2; Index <= MAX_HASH_VAL; Index++) {

mNext[Index] = NIL;

}

}

Child (

IN NODE NodeQ,

IN UINT8 CharC

)

{

NODE NodeR;

NodeR = mNext[HASH (NodeQ, CharC)];

//

// sentinel

//

mParent[NIL] = NodeQ;

while (mParent[NodeR] != NodeQ) {

NodeR = mNext[NodeR];

}

return NodeR;

}

MakeChild (

)

{

NODE Node1;

NODE Node2;

Node1 = (NODE) HASH (Parent, CharC);

Node2 = mNext[Node1];

mNext[Node1] = Child;

mNext[Child] = Node2;

mPrev[Node2] = Child;

mPrev[Child] = Node1;

mParent[Child] = Parent;

mChildCount[Parent]++;

}

Split (

NODE Old

)

{

NODE New;

NODE TempNode;

New = mAvail;

mAvail = mNext[New];

mChildCount[New] = 0;

TempNode = mPrev[Old];

mPrev[New] = TempNode;

mNext[TempNode] = New;

TempNode = mNext[Old];

mNext[New] = TempNode;

mPrev[TempNode] = New;

mParent[New] = mParent[Old];

mLevel[New] = (UINT8) mMatchLen;

mPosition[New] = mPos;

MakeChild (New, mText[mMatchPos + mMatchLen], Old);

MakeChild (New, mText[mPos + mMatchLen], mPos);

}

InsertNode (

VOID

)

{

NODE NodeQ;

NODE NodeR;

NODE Index2;

NODE NodeT;

UINT8 CharC;

UINT8 *t1;

UINT8 *t2;

if (mMatchLen >= 4) {

//

// We have just got a long match, the target tree

// can be located by MatchPos + 1. Travese 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--;

NodeR = (NODE) ((mMatchPos + 1) | WNDSIZ);

NodeQ = mParent[NodeR];

while (NodeQ == NIL) {

NodeR = mNext[NodeR];

NodeQ = mParent[NodeR];

}

while (mLevel[NodeQ] >= mMatchLen) {

NodeR = NodeQ;

NodeQ = mParent[NodeQ];

}

NodeT = NodeQ;

while (mPosition[NodeT] < 0) {

mPosition[NodeT] = mPos;

NodeT = mParent[NodeT];

}

if (NodeT < WNDSIZ) {

mPosition[NodeT] = (NODE) (mPos | (UINT32) PERC_FLAG);

}

} else {

//

// Locate the target tree

//

NodeQ = (NODE) (mText[mPos] + WNDSIZ);

CharC = mText[mPos + 1];

NodeR = Child (NodeQ, CharC);

if (NodeR == NIL) {

MakeChild (NodeQ, CharC, 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 (NodeR >= WNDSIZ) {

Index2 = MAXMATCH;

mMatchPos = NodeR;

} else {

Index2 = mLevel[NodeR];

mMatchPos = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);

}

if (mMatchPos >= mPos) {

mMatchPos -= WNDSIZ;

}

t1 = &mText[mPos + mMatchLen];

t2 = &mText[mMatchPos + mMatchLen];

while (mMatchLen < Index2) {

if (*t1 != *t2) {

Split (NodeR);

return ;

}

mMatchLen++;

t1++;

t2++;

}

if (mMatchLen >= MAXMATCH) {

break;

}

mPosition[NodeR] = mPos;

NodeQ = NodeR;

NodeR = Child (NodeQ, *t1);

if (NodeR == NIL) {

MakeChild (NodeQ, *t1, mPos);

return ;

}

mMatchLen++;

}

NodeT = mPrev[NodeR];

mPrev[mPos] = NodeT;

mNext[NodeT] = mPos;

NodeT = mNext[NodeR];

mNext[mPos] = NodeT;

mPrev[NodeT] = mPos;

mParent[mPos] = NodeQ;

mParent[NodeR] = NIL;

//

// Special usage of 'next'

//

mNext[NodeR] = mPos;

}

DeleteNode (

VOID

)

{

NODE NodeQ;

NODE NodeR;

NODE NodeS;

NODE NodeT;

NODE NodeU;

if (mParent[mPos] == NIL) {

return ;

}

NodeR = mPrev[mPos];

NodeS = mNext[mPos];

mNext[NodeR] = NodeS;

mPrev[NodeS] = NodeR;

NodeR = mParent[mPos];

mParent[mPos] = NIL;

if (NodeR >= WNDSIZ) {

return ;

}

mChildCount[NodeR]--;

if (mChildCount[NodeR] > 1) {

return ;

}

NodeT = (NODE) (mPosition[NodeR] & (UINT32)~PERC_FLAG);

if (NodeT >= mPos) {

NodeT -= WNDSIZ;

}

NodeS = NodeT;

NodeQ = mParent[NodeR];

NodeU = mPosition[NodeQ];

while (NodeU & (UINT32) PERC_FLAG) {

NodeU &= (UINT32)~PERC_FLAG;

if (NodeU >= mPos) {

NodeU -= WNDSIZ;

}

if (NodeU > NodeS) {

NodeS = NodeU;

}

mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ);

NodeQ = mParent[NodeQ];

NodeU = mPosition[NodeQ];

}

if (NodeQ < WNDSIZ) {

if (NodeU >= mPos) {

NodeU -= WNDSIZ;

}

if (NodeU > NodeS) {

NodeS = NodeU;

}

mPosition[NodeQ] = (NODE) (NodeS | WNDSIZ | (UINT32) PERC_FLAG);

}

NodeS = Child (NodeR, mText[NodeT + mLevel[NodeR]]);

NodeT = mPrev[NodeS];

NodeU = mNext[NodeS];

mNext[NodeT] = NodeU;

mPrev[NodeU] = NodeT;

NodeT = mPrev[NodeR];

mNext[NodeT] = NodeS;

mPrev[NodeS] = NodeT;

NodeT = mNext[NodeR];

mPrev[NodeT] = NodeS;

mNext[NodeS] = NodeT;

mParent[NodeS] = mParent[NodeR];

mParent[NodeR] = NIL;

mNext[NodeR] = mAvail;

mAvail = NodeR;

}

GetNextMatch (

VOID

)

{

INT32 Number;

mRemainder--;

mPos++;

if (mPos == WNDSIZ * 2) {

memmove (&mText[0], &mText[WNDSIZ], WNDSIZ + MAXMATCH);

Number = FreadCrc (&mText[WNDSIZ + MAXMATCH], WNDSIZ);

mRemainder += Number;

mPos = WNDSIZ;

}

DeleteNode ();

InsertNode ();

}

Encode (

VOID

)

{

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 {

if (LastMatchLen == THRESHOLD) {

if (((mPos - LastMatchPos - 2) & (WNDSIZ - 1)) > (1U << 11)) {

Output (mText[mPos - 1], 0);

continue;

}

}

//

// Outputting a pointer is beneficial enough, do it.

//

Output (

LastMatchLen + (UINT8_MAX + 1 - THRESHOLD),

(mPos - LastMatchPos - 2) & (WNDSIZ - 1)

);

LastMatchLen--;

while (LastMatchLen > 0) {

GetNextMatch ();

LastMatchLen--;

}

if (mMatchLen > mRemainder) {

mMatchLen = mRemainder;

}

}

}