From f215e02bf85f68d3a6106c2a1f4f7f063f819064 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 11 Apr 2024 10:17:27 +0200 Subject: Adding upstream version 7.0.14-dfsg. Signed-off-by: Daniel Baumann --- .../BaseTools/Source/C/TianoCompress/GNUmakefile | 15 + .../BaseTools/Source/C/TianoCompress/Makefile | 16 + .../BaseTools/Source/C/TianoCompress/Makefile.kmk | 45 + .../Source/C/TianoCompress/TianoCompress.c | 2795 ++++++++++++++++++++ .../Source/C/TianoCompress/TianoCompress.h | 431 +++ 5 files changed, 3302 insertions(+) create mode 100644 src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/GNUmakefile create mode 100644 src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/Makefile create mode 100644 src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/Makefile.kmk create mode 100644 src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/TianoCompress.c create mode 100644 src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/TianoCompress.h (limited to 'src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress') diff --git a/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/GNUmakefile b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/GNUmakefile new file mode 100644 index 00000000..6e0e25c1 --- /dev/null +++ b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/GNUmakefile @@ -0,0 +1,15 @@ +## @file +# GNU/Linux makefile for 'TianoCompress' module build. +# +# Copyright (c) 2007 - 2018, Intel Corporation. All rights reserved.
+# SPDX-License-Identifier: BSD-2-Clause-Patent +# +MAKEROOT ?= .. + +APPNAME = TianoCompress + +LIBS = -lCommon + +OBJECTS = TianoCompress.o + +include $(MAKEROOT)/Makefiles/app.makefile diff --git a/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/Makefile b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/Makefile new file mode 100644 index 00000000..46a250e7 --- /dev/null +++ b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/Makefile @@ -0,0 +1,16 @@ +## @file +# Windows makefile for 'TianoCompress' module build. +# +# Copyright (c) 2007 - 2010, Intel Corporation. All rights reserved.
+# SPDX-License-Identifier: BSD-2-Clause-Patent +# +!INCLUDE ..\Makefiles\ms.common + +APPNAME = TianoCompress + +LIBS = $(LIB_PATH)\Common.lib + +OBJECTS = TianoCompress.obj + +!INCLUDE ..\Makefiles\ms.app + diff --git a/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/Makefile.kmk b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/Makefile.kmk new file mode 100644 index 00000000..77e3e9d2 --- /dev/null +++ b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/Makefile.kmk @@ -0,0 +1,45 @@ +# $Id: Makefile.kmk $ +## @file +# Sub-makefile for the EFI TianoCompress build tool. +# + +# +# Copyright (C) 2013-2023 Oracle and/or its affiliates. +# +# This file is part of VirtualBox base platform packages, as +# available from https://www.virtualbox.org. +# +# This program is free software; you can redistribute it and/or +# modify it under the terms of the GNU General Public License +# as published by the Free Software Foundation, in version 3 of the +# License. +# +# This program is distributed in the hope that it will be useful, but +# WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +# General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, see . +# +# The contents of this file may alternatively be used under the terms +# of the Common Development and Distribution License Version 1.0 +# (CDDL), a copy of it is provided in the "COPYING.CDDL" file included +# in the VirtualBox distribution, in which case the provisions of the +# CDDL are applicable instead of those of the GPL. +# +# You may elect to license modified versions of this file under the +# terms and conditions of either the GPL or the CDDL or both. +# +# SPDX-License-Identifier: GPL-3.0-only OR CDDL-1.0 +# + +SUB_DEPTH = ../../../../../../../../.. +include $(KBUILD_PATH)/subheader.kmk + +BLDPROGS += TianoCompress +TianoCompress_TEMPLATE = VBoxEfiBldProg +TianoCompress_SOURCES = TianoCompress.c + +include $(FILE_KBUILD_SUB_FOOTER) + diff --git a/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/TianoCompress.c b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/TianoCompress.c new file mode 100644 index 00000000..8288b97d --- /dev/null +++ b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/TianoCompress.c @@ -0,0 +1,2795 @@ +/** @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) 2007 - 2018, Intel Corporation. All rights reserved.
+SPDX-License-Identifier: BSD-2-Clause-Patent + +**/ + +#include "Compress.h" +#include "Decompress.h" +#include "TianoCompress.h" +#include "EfiUtilityMsgs.h" +#include "ParseInf.h" +#include +#include "assert.h" + +// +// Macro Definitions +// +static BOOLEAN VerboseMode = FALSE; +static BOOLEAN QuietMode = FALSE; +#undef UINT8_MAX +#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) + +// +// 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 5 +//#define NT (CODE_BIT + 3) +//#define TBIT 5 +//#if NT > NP +//#define NPT NT +//#else +//#define NPT NP +//#endif + +// +// Global Variables +// +STATIC BOOLEAN ENCODE = FALSE; +STATIC BOOLEAN DECODE = FALSE; +STATIC BOOLEAN UEFIMODE = FALSE; +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; + +static UINT64 DebugLevel; +static BOOLEAN DebugMode; +// +// functions +// +EFI_STATUS +TianoCompress ( + IN UINT8 *SrcBuffer, + IN UINT32 SrcSize, + IN UINT8 *DstBuffer, + IN OUT UINT32 *DstSize + ) +/*++ + +Routine Description: + + The internal implementation of [Efi/Tiano]Compress(). + +Arguments: + + SrcBuffer - The buffer storing the source data + SrcSize - The size of source data + DstBuffer - The buffer to store the compressed data + + Version - The version of de/compression algorithm. + Version 1 for EFI 1.1 de/compression algorithm. + Version 2 for Tiano de/compression algorithm. + +Returns: + + EFI_BUFFER_TOO_SMALL - The DstBuffer is too small. In this case, + DstSize contains the size needed. + EFI_SUCCESS - Compression is successful. + EFI_OUT_OF_RESOURCES - No resource to complete function. + EFI_INVALID_PARAMETER - Parameter supplied is wrong. + +--*/ +{ + 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; + } +} + +STATIC +VOID +PutDword ( + IN UINT32 Data + ) +/*++ + +Routine Description: + + Put a dword to output stream + +Arguments: + + Data - the dword to put + +Returns: (VOID) + +--*/ +{ + 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); + } +} + +STATIC +EFI_STATUS +AllocateMemory ( + VOID + ) +/*++ + +Routine Description: + + Allocate memory spaces for data structures used in compression process + +Arguments: + VOID + +Returns: + + EFI_SUCCESS - Memory is allocated successfully + EFI_OUT_OF_RESOURCES - Allocation fails + +--*/ +{ + UINT32 Index; + + mText = malloc (WNDSIZ * 2 + MAXMATCH); + if (mText == NULL) { + Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!"); + return EFI_OUT_OF_RESOURCES; + } + 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)); + if (mLevel == NULL || mChildCount == NULL || mPosition == NULL || + mParent == NULL || mPrev == NULL || mNext == NULL) { + Error (NULL, 0, 4001, "Resource", "memory cannot be allocated!"); + return EFI_OUT_OF_RESOURCES; + } + + 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; +} + +VOID +FreeMemory ( + VOID + ) +/*++ + +Routine Description: + + Called when compression is completed to free memory previously allocated. + +Arguments: (VOID) + +Returns: (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 ; +} + +STATIC +VOID +InitSlide ( + VOID + ) +/*++ + +Routine Description: + + Initialize String Info Log data structures + +Arguments: (VOID) + +Returns: (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; + } +} + +STATIC +NODE +Child ( + IN NODE NodeQ, + IN UINT8 CharC + ) +/*++ + +Routine Description: + + Find child node given the parent node and the edge character + +Arguments: + + NodeQ - the parent node + CharC - the edge character + +Returns: + + The child node (NIL if not found) + +--*/ +{ + NODE NodeR; + + NodeR = mNext[HASH (NodeQ, CharC)]; + // + // sentinel + // + mParent[NIL] = NodeQ; + while (mParent[NodeR] != NodeQ) { + NodeR = mNext[NodeR]; + } + + return NodeR; +} + +STATIC +VOID +MakeChild ( + IN NODE Parent, + IN UINT8 CharC, + IN NODE Child + ) +/*++ + +Routine Description: + + Create a new child for a given parent node. + +Arguments: + + Parent - the parent node + CharC - the edge character + Child - the child node + +Returns: (VOID) + +--*/ +{ + 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]++; +} + +STATIC +VOID +Split ( + NODE Old + ) +/*++ + +Routine Description: + + Split a node. + +Arguments: + + Old - the node to split + +Returns: (VOID) + +--*/ +{ + 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); +} + +STATIC +VOID +InsertNode ( + VOID + ) +/*++ + +Routine Description: + + Insert string info for current position into the String Info Log + +Arguments: (VOID) + +Returns: (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. 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--; + 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; + +} + +STATIC +VOID +DeleteNode ( + VOID + ) +/*++ + +Routine Description: + + Delete outdated string info. (The Usage of PERC_FLAG + ensures a clean deletion) + +Arguments: (VOID) + +Returns: (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; +} + +STATIC +VOID +GetNextMatch ( + VOID + ) +/*++ + +Routine Description: + + Advance the current position (read in new data if needed). + Delete outdated string info. Find a match string for current position. + +Arguments: (VOID) + +Returns: (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 (); +} + +STATIC +EFI_STATUS +Encode ( + VOID + ) +/*++ + +Routine Description: + + The main controlling routine for compression process. + +Arguments: (VOID) + +Returns: + + EFI_SUCCESS - The compression is successful + EFI_OUT_0F_RESOURCES - Not enough memory for compression process + +--*/ +{ + 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; + } + } + } + + HufEncodeEnd (); + FreeMemory (); + return EFI_SUCCESS; +} + +STATIC +VOID +CountTFreq ( + VOID + ) +/*++ + +Routine Description: + + Count the frequencies for the Extra Set + +Arguments: (VOID) + +Returns: (VOID) + +--*/ +{ + INT32 Index; + INT32 Index3; + INT32 Number; + INT32 Count; + + for (Index = 0; Index < NT; Index++) { + mTFreq[Index] = 0; + } + + Number = NC; + while (Number > 0 && mCLen[Number - 1] == 0) { + Number--; + } + + Index = 0; + while (Index < Number) { + Index3 = mCLen[Index++]; + if (Index3 == 0) { + Count = 1; + while (Index < Number && mCLen[Index] == 0) { + Index++; + 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[Index3 + 2]++; + } + } +} + +STATIC +VOID +WritePTLen ( + IN INT32 Number, + IN INT32 nbit, + IN INT32 Special + ) +/*++ + +Routine Description: + + Outputs the code length array for the Extra Set or the Position Set. + +Arguments: + + Number - 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) + +--*/ +{ + INT32 Index; + INT32 Index3; + + while (Number > 0 && mPTLen[Number - 1] == 0) { + Number--; + } + + PutBits (nbit, Number); + Index = 0; + while (Index < Number) { + Index3 = mPTLen[Index++]; + if (Index3 <= 6) { + PutBits (3, Index3); + } else { + PutBits (Index3 - 3, (1U << (Index3 - 3)) - 2); + } + + if (Index == Special) { + while (Index < 6 && mPTLen[Index] == 0) { + Index++; + } + + PutBits (2, (Index - 3) & 3); + } + } +} + +STATIC +VOID +WriteCLen ( + VOID + ) +/*++ + +Routine Description: + + Outputs the code length array for Char&Length Set + +Arguments: (VOID) + +Returns: (VOID) + +--*/ +{ + INT32 Index; + INT32 Index3; + INT32 Number; + INT32 Count; + + Number = NC; + while (Number > 0 && mCLen[Number - 1] == 0) { + Number--; + } + + PutBits (CBIT, Number); + Index = 0; + while (Index < Number) { + Index3 = mCLen[Index++]; + if (Index3 == 0) { + Count = 1; + while (Index < Number && mCLen[Index] == 0) { + Index++; + Count++; + } + + if (Count <= 2) { + for (Index3 = 0; Index3 < Count; Index3++) { + 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[Index3 + 2], mPTCode[Index3 + 2]); + } + } +} + +STATIC +VOID +EncodeC ( + IN INT32 Value + ) +{ + PutBits (mCLen[Value], mCCode[Value]); +} + +STATIC +VOID +EncodeP ( + IN UINT32 Value + ) +{ + UINT32 Index; + UINT32 NodeQ; + + Index = 0; + NodeQ = Value; + while (NodeQ) { + NodeQ >>= 1; + Index++; + } + + PutBits (mPTLen[Index], mPTCode[Index]); + if (Index > 1) { + PutBits (Index - 1, Value & (0xFFFFFFFFU >> (32 - Index + 1))); + } +} + +STATIC +VOID +SendBlock ( + VOID + ) +/*++ + +Routine Description: + + Huffman code the block and output it. + +Arguments: + (VOID) + +Returns: + (VOID) + +--*/ +{ + UINT32 Index; + UINT32 Index2; + UINT32 Index3; + UINT32 Flags; + UINT32 Root; + UINT32 Pos; + UINT32 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 (Index = 0; Index < Size; Index++) { + if (Index % UINT8_BIT == 0) { + Flags = mBuf[Pos++]; + } else { + Flags <<= 1; + } + + if (Flags & (1U << (UINT8_BIT - 1))) { + EncodeC (mBuf[Pos++] + (1U << UINT8_BIT)); + Index3 = mBuf[Pos++]; + for (Index2 = 0; Index2 < 3; Index2++) { + Index3 <<= UINT8_BIT; + Index3 += mBuf[Pos++]; + } + + EncodeP (Index3); + } else { + EncodeC (mBuf[Pos++]); + } + } + + for (Index = 0; Index < NC; Index++) { + mCFreq[Index] = 0; + } + + for (Index = 0; Index < NP; Index++) { + mPFreq[Index] = 0; + } +} + +STATIC +VOID +Output ( + IN UINT32 CharC, + IN UINT32 Pos + ) +/*++ + +Routine Description: + + Outputs an Original Character or a Pointer + +Arguments: + + CharC - The original character or the 'String Length' element of a Pointer + Pos - The 'Position' field of a Pointer + +Returns: (VOID) + +--*/ +{ + STATIC UINT32 CPos; + + if ((mOutputMask >>= 1) == 0) { + mOutputMask = 1U << (UINT8_BIT - 1); + // + // Check the buffer overflow per outputing UINT8_BIT symbols + // which is an Original Character or a Pointer. The biggest + // symbol is a Pointer which occupies 5 bytes. + // + if (mOutputPos >= mBufSiz - 5 * UINT8_BIT) { + SendBlock (); + mOutputPos = 0; + } + + CPos = mOutputPos++; + mBuf[CPos] = 0; + } + + mBuf[mOutputPos++] = (UINT8) CharC; + mCFreq[CharC]++; + if (CharC >= (1U << UINT8_BIT)) { + mBuf[CPos] |= mOutputMask; + mBuf[mOutputPos++] = (UINT8) (Pos >> 24); + mBuf[mOutputPos++] = (UINT8) (Pos >> 16); + mBuf[mOutputPos++] = (UINT8) (Pos >> (UINT8_BIT)); + mBuf[mOutputPos++] = (UINT8) Pos; + CharC = 0; + while (Pos) { + Pos >>= 1; + CharC++; + } + + mPFreq[CharC]++; + } +} + +STATIC +VOID +HufEncodeStart ( + VOID + ) +{ + INT32 Index; + + for (Index = 0; Index < NC; Index++) { + mCFreq[Index] = 0; + } + + for (Index = 0; Index < NP; Index++) { + mPFreq[Index] = 0; + } + + mOutputPos = mOutputMask = 0; + InitPutBits (); + return ; +} + +STATIC +VOID +HufEncodeEnd ( + VOID + ) +{ + SendBlock (); + + // + // Flush remaining bits + // + PutBits (UINT8_BIT - 1, 0); + + return ; +} + +STATIC +VOID +MakeCrcTable ( + VOID + ) +{ + UINT32 Index; + UINT32 Index2; + UINT32 Temp; + + for (Index = 0; Index <= UINT8_MAX; Index++) { + Temp = Index; + for (Index2 = 0; Index2 < UINT8_BIT; Index2++) { + if (Temp & 1) { + Temp = (Temp >> 1) ^ CRCPOLY; + } else { + Temp >>= 1; + } + } + + mCrcTable[Index] = (UINT16) Temp; + } +} + +STATIC +VOID +PutBits ( + IN INT32 Number, + IN UINT32 Value + ) +/*++ + +Routine Description: + + Outputs rightmost n bits of x + +Arguments: + + Number - the rightmost n bits of the data is used + x - the data + +Returns: (VOID) + +--*/ +{ + UINT8 Temp; + + while (Number >= mBitCount) { + // + // Number -= mBitCount should never equal to 32 + // + Temp = (UINT8) (mSubBitBuf | (Value >> (Number -= mBitCount))); + + if (mDst < mDstUpperLimit) { + *mDst++ = Temp; + } + + mCompSize++; + mSubBitBuf = 0; + mBitCount = UINT8_BIT; + } + + mSubBitBuf |= Value << (mBitCount -= Number); +} + +STATIC +INT32 +FreadCrc ( + OUT UINT8 *Pointer, + IN INT32 Number + ) +/*++ + +Routine Description: + + Read in source data + +Arguments: + + Pointer - the buffer to hold the data + Number - number of bytes to read + +Returns: + + number of bytes actually read + +--*/ +{ + INT32 Index; + + for (Index = 0; mSrc < mSrcUpperLimit && Index < Number; Index++) { + *Pointer++ = *mSrc++; + } + + Number = Index; + + Pointer -= Number; + mOrigSize += Number; + + Index--; + while (Index >= 0) { + UPDATE_CRC (*Pointer++); + Index--; + } + + return Number; +} + +STATIC +VOID +InitPutBits ( + VOID + ) +{ + mBitCount = UINT8_BIT; + mSubBitBuf = 0; +} + +STATIC +VOID +CountLen ( + IN INT32 Index + ) +/*++ + +Routine Description: + + Count the number of each code length for a Huffman tree. + +Arguments: + + Index - the top node + +Returns: (VOID) + +--*/ +{ + STATIC INT32 Depth = 0; + + if (Index < mN) { + mLenCnt[(Depth < 16) ? Depth : 16]++; + } else { + Depth++; + CountLen (mLeft[Index]); + CountLen (mRight[Index]); + Depth--; + } +} + +STATIC +VOID +MakeLen ( + IN INT32 Root + ) +/*++ + +Routine Description: + + Create code length array for a Huffman tree + +Arguments: + + Root - the root of the tree + +Returns: + + VOID + +--*/ +{ + INT32 Index; + INT32 Index3; + UINT32 Cum; + + for (Index = 0; Index <= 16; Index++) { + mLenCnt[Index] = 0; + } + + CountLen (Root); + + // + // Adjust the length count array so that + // no code will be generated longer than its designated length + // + Cum = 0; + for (Index = 16; Index > 0; Index--) { + Cum += mLenCnt[Index] << (16 - Index); + } + + while (Cum != (1U << 16)) { + mLenCnt[16]--; + for (Index = 15; Index > 0; Index--) { + if (mLenCnt[Index] != 0) { + mLenCnt[Index]--; + mLenCnt[Index + 1] += 2; + break; + } + } + + Cum--; + } + + for (Index = 16; Index > 0; Index--) { + Index3 = mLenCnt[Index]; + Index3--; + while (Index3 >= 0) { + mLen[*mSortPtr++] = (UINT8) Index; + Index3--; + } + } +} + +STATIC +VOID +DownHeap ( + IN INT32 Index + ) +{ + INT32 Index2; + INT32 Index3; + + // + // priority queue: send Index-th entry down heap + // + Index3 = mHeap[Index]; + Index2 = 2 * Index; + while (Index2 <= mHeapSize) { + if (Index2 < mHeapSize && mFreq[mHeap[Index2]] > mFreq[mHeap[Index2 + 1]]) { + Index2++; + } + + if (mFreq[Index3] <= mFreq[mHeap[Index2]]) { + break; + } + + mHeap[Index] = mHeap[Index2]; + Index = Index2; + Index2 = 2 * Index; + } + + mHeap[Index] = (INT16) Index3; +} + +STATIC +VOID +MakeCode ( + IN INT32 Number, + IN UINT8 Len[ ], + OUT UINT16 Code[] + ) +/*++ + +Routine Description: + + Assign code to each symbol based on the code length array + +Arguments: + + Number - number of symbols + Len - the code length array + Code - stores codes for each symbol + +Returns: (VOID) + +--*/ +{ + INT32 Index; + UINT16 Start[18]; + + Start[1] = 0; + for (Index = 1; Index <= 16; Index++) { + Start[Index + 1] = (UINT16) ((Start[Index] + mLenCnt[Index]) << 1); + } + + for (Index = 0; Index < Number; Index++) { + Code[Index] = Start[Len[Index]]++; + } +} + +STATIC +INT32 +MakeTree ( + IN INT32 NParm, + IN UINT16 FreqParm[], + OUT UINT8 LenParm[ ], + OUT UINT16 CodeParm[] + ) +/*++ + +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 Index; + INT32 Index2; + INT32 Index3; + INT32 Avail; + + // + // make tree, calculate len[], return root + // + mN = NParm; + mFreq = FreqParm; + mLen = LenParm; + Avail = mN; + mHeapSize = 0; + mHeap[1] = 0; + for (Index = 0; Index < mN; Index++) { + mLen[Index] = 0; + if (mFreq[Index]) { + mHeapSize++; + mHeap[mHeapSize] = (INT16) Index; + } + } + + if (mHeapSize < 2) { + CodeParm[mHeap[1]] = 0; + return mHeap[1]; + } + + for (Index = mHeapSize / 2; Index >= 1; Index--) { + // + // make priority queue + // + DownHeap (Index); + } + + mSortPtr = CodeParm; + do { + Index = mHeap[1]; + if (Index < mN) { + *mSortPtr++ = (UINT16) Index; + } + + mHeap[1] = mHeap[mHeapSize--]; + DownHeap (1); + Index2 = mHeap[1]; + if (Index2 < mN) { + *mSortPtr++ = (UINT16) Index2; + } + + Index3 = Avail++; + mFreq[Index3] = (UINT16) (mFreq[Index] + mFreq[Index2]); + mHeap[1] = (INT16) Index3; + DownHeap (1); + mLeft[Index3] = (UINT16) Index; + mRight[Index3] = (UINT16) Index2; + } while (mHeapSize > 1); + + mSortPtr = CodeParm; + MakeLen (Index3); + MakeCode (NParm, LenParm, CodeParm); + + // + // return root + // + return Index3; +} + +EFI_STATUS +GetFileContents ( + IN char *InputFileName, + OUT UINT8 *FileBuffer, + OUT UINT32 *BufferLength + ) +/*++ + +Routine Description: + + Get the contents of file specified in InputFileName + into FileBuffer. + +Arguments: + + InputFileName - Name of the input file. + + FileBuffer - Output buffer to contain data + + BufferLength - Actual length of the data + +Returns: + + EFI_SUCCESS on successful return + EFI_ABORTED if unable to open input file. + +--*/ +{ + UINTN Size; + UINTN FileSize; + FILE *InputFile; + + Size = 0; + // + // Copy the file contents to the output buffer. + // + InputFile = fopen (LongFilePath (InputFileName), "rb"); + if (InputFile == NULL) { + Error (NULL, 0, 0001, "Error opening file: %s", InputFileName); + return EFI_ABORTED; + } + + fseek (InputFile, 0, SEEK_END); + FileSize = ftell (InputFile); + fseek (InputFile, 0, SEEK_SET); + // + // Now read the contents of the file into the buffer + // + if (FileSize > 0 && FileBuffer != NULL) { + if (fread (FileBuffer, FileSize, 1, InputFile) != 1) { + Error (NULL, 0, 0004, "Error reading contents of input file: %s", InputFileName); + fclose (InputFile); + return EFI_ABORTED; + } + } + + fclose (InputFile); + Size += (UINTN) FileSize; + *BufferLength = Size; + + if (FileBuffer != NULL) { + return EFI_SUCCESS; + } else { + return EFI_BUFFER_TOO_SMALL; + } +} + +VOID +Version ( + VOID + ) +/*++ + +Routine Description: + + Displays the standard utility information to SDTOUT + +Arguments: + + None + +Returns: + + None + +--*/ +{ + fprintf (stdout, "%s Version %d.%d %s \n", UTILITY_NAME, UTILITY_MAJOR_VERSION, UTILITY_MINOR_VERSION, __BUILD_VERSION); +} + +VOID +Usage ( + VOID + ) +/*++ + +Routine Description: + + Displays the utility usage syntax to STDOUT + +Arguments: + + None + +Returns: + + None + +--*/ +{ + // + // Summary usage + // + fprintf (stdout, "Usage: %s -e|-d [options] \n\n", UTILITY_NAME); + + // + // Copyright declaration + // + fprintf (stdout, "Copyright (c) 2007 - 2018, Intel Corporation. All rights reserved.\n\n"); + + // + // Details Option + // + fprintf (stdout, "Options:\n"); + fprintf (stdout, " --uefi\n\ + Enable UefiCompress, use TianoCompress when without this option\n"); + fprintf (stdout, " -o FileName, --output FileName\n\ + File will be created to store the output content.\n"); + fprintf (stdout, " -v, --verbose\n\ + Turn on verbose output with informational messages.\n"); + fprintf (stdout, " -q, --quiet\n\ + Disable all messages except key message and fatal error\n"); + fprintf (stdout, " --debug [0-9]\n\ + Enable debug messages, at input debug level.\n"); + fprintf (stdout, " --version\n\ + Show program's version number and exit.\n"); + fprintf (stdout, " -h, --help\n\ + Show this help message and exit.\n"); +} + + +int +main ( + int argc, + char *argv[] + ) +/*++ + +Routine Description: + + Main + +Arguments: + + command line parameters + +Returns: + + EFI_SUCCESS Section header successfully generated and section concatenated. + EFI_ABORTED Could not generate the section + EFI_OUT_OF_RESOURCES No resource to complete the operation. + +--*/ +{ + FILE *OutputFile; + char *OutputFileName; + char *InputFileName; + FILE *InputFile; + EFI_STATUS Status; + UINT8 *FileBuffer; + UINT8 *OutBuffer; + UINT32 InputLength; + UINT32 DstSize; + SCRATCH_DATA *Scratch; + UINT8 *Src; + UINT32 OrigSize; + UINT32 CompSize; + + SetUtilityName(UTILITY_NAME); + + FileBuffer = NULL; + Src = NULL; + OutBuffer = NULL; + Scratch = NULL; + OrigSize = 0; + CompSize = 0; + InputLength = 0; + InputFileName = NULL; + OutputFileName = NULL; + InputFile = NULL; + OutputFile = NULL; + DstSize=0; + DebugLevel = 0; + DebugMode = FALSE; + + // + // Verify the correct number of arguments + // + if (argc == 1) { + Error (NULL, 0, 1001, "Missing options", "No input options specified."); + Usage(); + return 0; + } + + if ((strcmp(argv[1], "-h") == 0) || (strcmp(argv[1], "--help") == 0)) { + Usage(); + return 0; + } + + if ((strcmp(argv[1], "--version") == 0)) { + Version(); + return 0; + } + + argc--; + argv++; + if (strcmp(argv[0],"-e") == 0) { + // + // encode the input file + // + ENCODE = TRUE; + argc--; + argv++; + } else if (strcmp(argv[0], "-d") == 0) { + // + // decode the input file + // + DECODE = TRUE; + argc--; + argv++; + } else { + // + // Error command line + // + Error (NULL, 0, 1003, "Invalid option value", "the options specified are not recognized."); + Usage(); + return 1; + } + + while (argc > 0) { + if ((strcmp(argv[0], "-v") == 0) || (stricmp(argv[0], "--verbose") == 0)) { + VerboseMode = TRUE; + argc--; + argv++; + continue; + } + + if (stricmp(argv[0], "--uefi") == 0) { + UEFIMODE = TRUE; + argc--; + argv++; + continue; + } + + if (stricmp (argv[0], "--debug") == 0) { + argc-=2; + argv++; + Status = AsciiStringToUint64(argv[0], FALSE, &DebugLevel); + if (DebugLevel > 9) { + Error (NULL, 0 ,2000, "Invalid parameter", "Unrecognized argument %s", argv[0]); + goto ERROR; + } + if (DebugLevel>=5 && DebugLevel <=9){ + DebugMode = TRUE; + } else { + DebugMode = FALSE; + } + argv++; + continue; + } + + if ((strcmp(argv[0], "-q") == 0) || (stricmp (argv[0], "--quiet") == 0)) { + QuietMode = TRUE; + argc--; + argv++; + continue; + } + + if ((strcmp(argv[0], "-o") == 0) || (stricmp (argv[0], "--output") == 0)) { + if (argv[1] == NULL || argv[1][0] == '-') { + Error (NULL, 0, 1003, "Invalid option value", "Output File name is missing for -o option"); + goto ERROR; + } + OutputFileName = argv[1]; + argc -=2; + argv +=2; + continue; + } + + if (argv[0][0]!='-') { + InputFileName = argv[0]; + argc--; + argv++; + continue; + } + + Error (NULL, 0, 1000, "Unknown option", argv[0]); + goto ERROR; + } + + if (InputFileName == NULL) { + Error (NULL, 0, 1001, "Missing options", "No input files specified."); + goto ERROR; + } + +// +// All Parameters has been parsed, now set the message print level +// + if (QuietMode) { + SetPrintLevel(40); + } else if (VerboseMode) { + SetPrintLevel(15); + } else if (DebugMode) { + SetPrintLevel(DebugLevel); + } + + if (VerboseMode) { + VerboseMsg("%s tool start.\n", UTILITY_NAME); + } + Scratch = (SCRATCH_DATA *)malloc(sizeof(SCRATCH_DATA)); + if (Scratch == NULL) { + Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!"); + goto ERROR; + } + + InputFile = fopen (LongFilePath (InputFileName), "rb"); + if (InputFile == NULL) { + Error (NULL, 0, 0001, "Error opening input file", InputFileName); + goto ERROR; + } + + Status = GetFileContents( + InputFileName, + FileBuffer, + &InputLength); + + if (Status == EFI_BUFFER_TOO_SMALL) { + FileBuffer = (UINT8 *) malloc (InputLength); + if (FileBuffer == NULL) { + Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!"); + goto ERROR; + } + + Status = GetFileContents ( + InputFileName, + FileBuffer, + &InputLength + ); + } + + if (EFI_ERROR(Status)) { + Error (NULL, 0, 0004, "Error getting contents of file: %s", InputFileName); + goto ERROR; + } + + if (OutputFileName == NULL) { + OutputFileName = DEFAULT_OUTPUT_FILE; + } + OutputFile = fopen (LongFilePath (OutputFileName), "wb"); + if (OutputFile == NULL) { + Error (NULL, 0, 0001, "Error opening output file for writing", OutputFileName); + goto ERROR; + } + + if (ENCODE) { + // + // First call TianoCompress to get DstSize + // + if (DebugMode) { + DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding", NULL); + } + if (UEFIMODE) { + Status = EfiCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize); + } else { + Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize); + } + + if (Status == EFI_BUFFER_TOO_SMALL) { + OutBuffer = (UINT8 *) malloc (DstSize); + if (OutBuffer == NULL) { + Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!"); + goto ERROR; + } + } + + if (UEFIMODE) { + Status = EfiCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize); + } else { + Status = TianoCompress ((UINT8 *)FileBuffer, InputLength, OutBuffer, &DstSize); + } + if (Status != EFI_SUCCESS) { + Error (NULL, 0, 0007, "Error compressing file", NULL); + goto ERROR; + } + + if (OutBuffer == NULL) { + Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!"); + goto ERROR; + } + + fwrite(OutBuffer,(size_t)DstSize, 1, OutputFile); + fclose(OutputFile); + fclose(InputFile); + free(Scratch); + free(FileBuffer); + free(OutBuffer); + + if (DebugMode) { + DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Successful!\n", NULL); + } + if (VerboseMode) { + VerboseMsg("Encoding successful\n"); + } + return 0; + } + else if (DECODE) { + if (DebugMode) { + DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding\n", NULL); + } + + if (UEFIMODE) { + Status = Extract((VOID *)FileBuffer, InputLength, (VOID *)&OutBuffer, &DstSize, 1); + if (Status != EFI_SUCCESS) { + goto ERROR; + } + fwrite(OutBuffer, (size_t)(DstSize), 1, OutputFile); + } else { + if (InputLength < 8){ + Error (NULL, 0, 3000, "Invalid", "The input file %s is too small.", InputFileName); + goto ERROR; + } + // + // Get Compressed file original size + // + Src = (UINT8 *)FileBuffer; + OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24); + CompSize = Src[0] + (Src[1] << 8) + (Src[2] <<16) + (Src[3] <<24); + + // + // Allocate OutputBuffer + // + if (InputLength < CompSize + 8 || (CompSize + 8) < 8) { + Error (NULL, 0, 3000, "Invalid", "The input file %s data is invalid.", InputFileName); + goto ERROR; + } + OutBuffer = (UINT8 *)malloc(OrigSize); + if (OutBuffer == NULL) { + Error (NULL, 0, 4001, "Resource:", "Memory cannot be allocated!"); + goto ERROR; + } + + Status = TDecompress((VOID *)FileBuffer, (VOID *)OutBuffer, (VOID *)Scratch, 2); + if (Status != EFI_SUCCESS) { + goto ERROR; + } + fwrite(OutBuffer, (size_t)(Scratch->mOrigSize), 1, OutputFile); + } + fclose(OutputFile); + fclose(InputFile); + if (Scratch != NULL) { + free(Scratch); + } + if (FileBuffer != NULL) { + free(FileBuffer); + } + if (OutBuffer != NULL) { + free(OutBuffer); + } + + if (DebugMode) { + DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding successful!\n", NULL); + } + + if (VerboseMode) { + VerboseMsg("Decoding successful\n"); + } + return 0; + } + +ERROR: + if (DebugMode) { + if (ENCODE) { + DebugMsg(UTILITY_NAME, 0, DebugLevel, "Encoding Error\n", NULL); + } else if (DECODE) { + DebugMsg(UTILITY_NAME, 0, DebugLevel, "Decoding Error\n", NULL); + } + } + if (OutputFile != NULL) { + fclose(OutputFile); + } + if (InputFile != NULL) { + fclose (InputFile); + } + if (Scratch != NULL) { + free(Scratch); + } + if (FileBuffer != NULL) { + free(FileBuffer); + } + if (OutBuffer != NULL) { + free(OutBuffer); + } + + if (VerboseMode) { + VerboseMsg("%s tool done with return code is 0x%x.\n", UTILITY_NAME, GetUtilityStatus ()); + } + return GetUtilityStatus (); +} + +VOID +FillBuf ( + IN SCRATCH_DATA *Sd, + IN UINT16 NumOfBits + ) +/*++ + +Routine Description: + + Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source. + +Arguments: + + Sd - The global scratch data + NumOfBits - The number of bits to shift and read. + +Returns: (VOID) + +--*/ +{ + Sd->mBitBuf = (UINT32) (((UINT64)Sd->mBitBuf) << NumOfBits); + + while (NumOfBits > Sd->mBitCount) { + + Sd->mBitBuf |= (UINT32) (((UINT64)Sd->mSubBitBuf) << (NumOfBits = (UINT16) (NumOfBits - Sd->mBitCount))); + + if (Sd->mCompSize > 0) { + // + // Get 1 byte into SubBitBuf + // + Sd->mCompSize--; + Sd->mSubBitBuf = 0; + Sd->mSubBitBuf = Sd->mSrcBase[Sd->mInBuf++]; + Sd->mBitCount = 8; + + } else { + // + // No more bits from the source, just pad zero bit. + // + Sd->mSubBitBuf = 0; + Sd->mBitCount = 8; + + } + } + + Sd->mBitCount = (UINT16) (Sd->mBitCount - NumOfBits); + Sd->mBitBuf |= Sd->mSubBitBuf >> Sd->mBitCount; +} + +UINT32 +GetBits ( + IN SCRATCH_DATA *Sd, + IN UINT16 NumOfBits + ) +/*++ + +Routine Description: + + Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent + NumOfBits of bits from source. Returns NumOfBits of bits that are + popped out. + +Arguments: + + Sd - The global scratch data. + NumOfBits - The number of bits to pop and read. + +Returns: + + The bits that are popped out. + +--*/ +{ + UINT32 OutBits; + + OutBits = (UINT32) (Sd->mBitBuf >> (BITBUFSIZ - NumOfBits)); + + FillBuf (Sd, NumOfBits); + + return OutBits; +} + +UINT16 +MakeTable ( + IN SCRATCH_DATA *Sd, + IN UINT16 NumOfChar, + IN UINT8 *BitLen, + IN UINT16 TableBits, + OUT UINT16 *Table + ) +/*++ + +Routine Description: + + Creates Huffman Code mapping table according to code length array. + +Arguments: + + Sd - The global scratch data + NumOfChar - Number of symbols in the symbol set + BitLen - Code length array + TableBits - The width of the mapping table + Table - The table + +Returns: + + 0 - OK. + BAD_TABLE - The table is corrupted. + +--*/ +{ + UINT16 Count[17]; + UINT16 Weight[17]; + UINT16 Start[18]; + UINT16 *Pointer; + UINT16 Index3; + UINT16 Index; + UINT16 Len; + UINT16 Char; + UINT16 JuBits; + UINT16 Avail; + UINT16 NextCode; + UINT16 Mask; + UINT16 WordOfStart; + UINT16 WordOfCount; + UINT16 MaxTableLength; + + for (Index = 0; Index <= 16; Index++) { + Count[Index] = 0; + } + + for (Index = 0; Index < NumOfChar; Index++) { + if (BitLen[Index] > 16) { + return (UINT16) BAD_TABLE; + } + Count[BitLen[Index]]++; + } + + Start[0] = 0; + Start[1] = 0; + + for (Index = 1; Index <= 16; Index++) { + WordOfStart = Start[Index]; + WordOfCount = Count[Index]; + Start[Index + 1] = (UINT16) (WordOfStart + (WordOfCount << (16 - Index))); + } + + if (Start[17] != 0) { + // + //(1U << 16) + // + return (UINT16) BAD_TABLE; + } + + JuBits = (UINT16) (16 - TableBits); + + Weight[0] = 0; + for (Index = 1; Index <= TableBits; Index++) { + Start[Index] >>= JuBits; + Weight[Index] = (UINT16) (1U << (TableBits - Index)); + } + + while (Index <= 16) { + Weight[Index] = (UINT16) (1U << (16 - Index)); + Index++; + } + + Index = (UINT16) (Start[TableBits + 1] >> JuBits); + + if (Index != 0) { + Index3 = (UINT16) (1U << TableBits); + while (Index != Index3) { + Table[Index++] = 0; + } + } + + Avail = NumOfChar; + Mask = (UINT16) (1U << (15 - TableBits)); + MaxTableLength = (UINT16) (1U << TableBits); + + for (Char = 0; Char < NumOfChar; Char++) { + + Len = BitLen[Char]; + if (Len == 0 || Len >= 17) { + continue; + } + + NextCode = (UINT16) (Start[Len] + Weight[Len]); + + if (Len <= TableBits) { + + if (Start[Len] >= NextCode || NextCode > MaxTableLength){ + return (UINT16) BAD_TABLE; + } + + for (Index = Start[Len]; Index < NextCode; Index++) { + Table[Index] = Char; + } + + } else { + + Index3 = Start[Len]; + Pointer = &Table[Index3 >> JuBits]; + Index = (UINT16) (Len - TableBits); + + while (Index != 0) { + if (*Pointer == 0) { + Sd->mRight[Avail] = Sd->mLeft[Avail] = 0; + *Pointer = Avail++; + } + + if (Index3 & Mask) { + Pointer = &Sd->mRight[*Pointer]; + } else { + Pointer = &Sd->mLeft[*Pointer]; + } + + Index3 <<= 1; + Index--; + } + + *Pointer = Char; + + } + + Start[Len] = NextCode; + } + // + // Succeeds + // + return 0; +} + +UINT32 +DecodeP ( + IN SCRATCH_DATA *Sd + ) +/*++ + +Routine Description: + + Decodes a position value. + +Arguments: + + Sd - the global scratch data + +Returns: + + The position value decoded. + +--*/ +{ + UINT16 Val; + UINT32 Mask; + UINT32 Pos; + + Val = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)]; + + if (Val >= MAXNP) { + Mask = 1U << (BITBUFSIZ - 1 - 8); + + do { + + if (Sd->mBitBuf & Mask) { + Val = Sd->mRight[Val]; + } else { + Val = Sd->mLeft[Val]; + } + + Mask >>= 1; + } while (Val >= MAXNP); + } + // + // Advance what we have read + // + FillBuf (Sd, Sd->mPTLen[Val]); + + Pos = Val; + if (Val > 1) { + Pos = (UINT32) ((1U << (Val - 1)) + GetBits (Sd, (UINT16) (Val - 1))); + } + + return Pos; +} + +UINT16 +ReadPTLen ( + IN SCRATCH_DATA *Sd, + IN UINT16 nn, + IN UINT16 nbit, + IN UINT16 Special + ) +/*++ + +Routine Description: + + Reads code lengths for the Extra Set or the Position Set + +Arguments: + + Sd - The global scratch data + nn - Number of symbols + nbit - Number of bits needed to represent nn + Special - The special symbol that needs to be taken care of + +Returns: + + 0 - OK. + BAD_TABLE - Table is corrupted. + +--*/ +{ + UINT16 Number; + UINT16 CharC; + volatile UINT16 Index; + UINT32 Mask; + + assert (nn <= NPT); + + Number = (UINT16) GetBits (Sd, nbit); + + if (Number == 0) { + CharC = (UINT16) GetBits (Sd, nbit); + + for (Index = 0; Index < 256; Index++) { + Sd->mPTTable[Index] = CharC; + } + + for (Index = 0; Index < nn; Index++) { + Sd->mPTLen[Index] = 0; + } + + return 0; + } + + Index = 0; + + while (Index < Number) { + + CharC = (UINT16) (Sd->mBitBuf >> (BITBUFSIZ - 3)); + + if (CharC == 7) { + Mask = 1U << (BITBUFSIZ - 1 - 3); + while (Mask & Sd->mBitBuf) { + Mask >>= 1; + CharC += 1; + } + } + + FillBuf (Sd, (UINT16) ((CharC < 7) ? 3 : CharC - 3)); + + Sd->mPTLen[Index++] = (UINT8) CharC; + + if (Index == Special) { + CharC = (UINT16) GetBits (Sd, 2); + while ((INT16) (--CharC) >= 0) { + Sd->mPTLen[Index++] = 0; + } + } + } + + while (Index < nn) { + Sd->mPTLen[Index++] = 0; + } + + return MakeTable (Sd, nn, Sd->mPTLen, 8, Sd->mPTTable); +} + +VOID +ReadCLen ( + SCRATCH_DATA *Sd + ) +/*++ + +Routine Description: + + Reads code lengths for Char&Len Set. + +Arguments: + + Sd - the global scratch data + +Returns: (VOID) + +--*/ +{ + UINT16 Number; + UINT16 CharC; + volatile UINT16 Index; + UINT32 Mask; + + Number = (UINT16) GetBits (Sd, CBIT); + + if (Number == 0) { + CharC = (UINT16) GetBits (Sd, CBIT); + + for (Index = 0; Index < NC; Index++) { + Sd->mCLen[Index] = 0; + } + + for (Index = 0; Index < 4096; Index++) { + Sd->mCTable[Index] = CharC; + } + + return ; + } + + Index = 0; + while (Index < Number) { + + CharC = Sd->mPTTable[Sd->mBitBuf >> (BITBUFSIZ - 8)]; + if (CharC >= NT) { + Mask = 1U << (BITBUFSIZ - 1 - 8); + + do { + + if (Mask & Sd->mBitBuf) { + CharC = Sd->mRight[CharC]; + } else { + CharC = Sd->mLeft[CharC]; + } + + Mask >>= 1; + + } while (CharC >= NT); + } + // + // Advance what we have read + // + FillBuf (Sd, Sd->mPTLen[CharC]); + + if (CharC <= 2) { + + if (CharC == 0) { + CharC = 1; + } else if (CharC == 1) { + CharC = (UINT16) (GetBits (Sd, 4) + 3); + } else if (CharC == 2) { + CharC = (UINT16) (GetBits (Sd, CBIT) + 20); + } + + while ((INT16) (--CharC) >= 0) { + Sd->mCLen[Index++] = 0; + } + + } else { + + Sd->mCLen[Index++] = (UINT8) (CharC - 2); + + } + } + + while (Index < NC) { + Sd->mCLen[Index++] = 0; + } + + MakeTable (Sd, NC, Sd->mCLen, 12, Sd->mCTable); + + return ; +} + +UINT16 +DecodeC ( + SCRATCH_DATA *Sd + ) +/*++ + +Routine Description: + + Decode a character/length value. + +Arguments: + + Sd - The global scratch data. + +Returns: + + The value decoded. + +--*/ +{ + UINT16 Index2; + UINT32 Mask; + + if (Sd->mBlockSize == 0) { + // + // Starting a new block + // + Sd->mBlockSize = (UINT16) GetBits (Sd, 16); + Sd->mBadTableFlag = ReadPTLen (Sd, NT, TBIT, 3); + if (Sd->mBadTableFlag != 0) { + return 0; + } + + ReadCLen (Sd); + + Sd->mBadTableFlag = ReadPTLen (Sd, MAXNP, Sd->mPBit, (UINT16) (-1)); + if (Sd->mBadTableFlag != 0) { + return 0; + } + } + + Sd->mBlockSize--; + Index2 = Sd->mCTable[Sd->mBitBuf >> (BITBUFSIZ - 12)]; + + if (Index2 >= NC) { + Mask = 1U << (BITBUFSIZ - 1 - 12); + + do { + if (Sd->mBitBuf & Mask) { + Index2 = Sd->mRight[Index2]; + } else { + Index2 = Sd->mLeft[Index2]; + } + + Mask >>= 1; + } while (Index2 >= NC); + } + // + // Advance what we have read + // + FillBuf (Sd, Sd->mCLen[Index2]); + + return Index2; +} + +VOID +Decode ( + SCRATCH_DATA *Sd + ) +/*++ + +Routine Description: + + Decode the source data and put the resulting data into the destination buffer. + +Arguments: + + Sd - The global scratch data + +Returns: (VOID) + + --*/ +{ + UINT16 BytesRemain; + UINT32 DataIdx; + UINT16 CharC; + + BytesRemain = (UINT16) (-1); + + DataIdx = 0; + + for (;;) { + CharC = DecodeC (Sd); + if (Sd->mBadTableFlag != 0) { + goto Done ; + } + + if (CharC < 256) { + // + // Process an Original character + // + if (Sd->mOutBuf >= Sd->mOrigSize) { + goto Done ; + } else { + Sd->mDstBase[Sd->mOutBuf++] = (UINT8) CharC; + } + + } else { + // + // Process a Pointer + // + CharC = (UINT16) (CharC - (UINT8_MAX + 1 - THRESHOLD)); + + BytesRemain = CharC; + + DataIdx = Sd->mOutBuf - DecodeP (Sd) - 1; + + BytesRemain--; + + while ((INT16) (BytesRemain) >= 0) { + if (Sd->mOutBuf >= Sd->mOrigSize) { + goto Done ; + } + if (DataIdx >= Sd->mOrigSize) { + Sd->mBadTableFlag = (UINT16) BAD_TABLE; + goto Done ; + } + Sd->mDstBase[Sd->mOutBuf++] = Sd->mDstBase[DataIdx++]; + + BytesRemain--; + } + // + // Once mOutBuf is fully filled, directly return + // + if (Sd->mOutBuf >= Sd->mOrigSize) { + goto Done ; + } + } + } + +Done: + return ; +} + +RETURN_STATUS +EFIAPI +TDecompress ( + IN VOID *Source, + IN OUT VOID *Destination, + IN OUT VOID *Scratch, + IN UINT32 Version + ) +/*++ + +Routine Description: + + The internal implementation of Decompress(). + +Arguments: + + Source - The source buffer containing the compressed data. + Destination - The destination buffer to store the decompressed data + Scratch - The buffer used internally by the decompress routine. This buffer is needed to store intermediate data. + Version - 1 for EFI1.1 Decompress algorithm, 2 for Tiano Decompress algorithm + +Returns: + + RETURN_SUCCESS - Decompression is successful + RETURN_INVALID_PARAMETER - The source data is corrupted + +--*/ +{ + volatile UINT32 Index; + UINT32 CompSize; + UINT32 OrigSize; + SCRATCH_DATA *Sd; + CONST UINT8 *Src; + UINT8 *Dst; + + // + // Verify input is not NULL + // + assert(Source); +// assert(Destination); + assert(Scratch); + + Src = (UINT8 *)Source; + Dst = (UINT8 *)Destination; + + Sd = (SCRATCH_DATA *) Scratch; + CompSize = Src[0] + (Src[1] << 8) + (Src[2] << 16) + (Src[3] << 24); + OrigSize = Src[4] + (Src[5] << 8) + (Src[6] << 16) + (Src[7] << 24); + + // + // If compressed file size is 0, return + // + if (OrigSize == 0) { + return RETURN_SUCCESS; + } + + Src = Src + 8; + + for (Index = 0; Index < sizeof (SCRATCH_DATA); Index++) { + ((UINT8 *) Sd)[Index] = 0; + } + // + // The length of the field 'Position Set Code Length Array Size' in Block Header. + // For EFI 1.1 de/compression algorithm(Version 1), mPBit = 4 + // For Tiano de/compression algorithm(Version 2), mPBit = 5 + // + switch (Version) { + case 1 : + Sd->mPBit = 4; + break; + case 2 : + Sd->mPBit = 5; + break; + default: + assert(FALSE); + } + Sd->mSrcBase = (UINT8 *)Src; + Sd->mDstBase = Dst; + Sd->mCompSize = CompSize; + Sd->mOrigSize = OrigSize; + + // + // Fill the first BITBUFSIZ bits + // + FillBuf (Sd, BITBUFSIZ); + + // + // Decompress it + // + + Decode (Sd); + + if (Sd->mBadTableFlag != 0) { + // + // Something wrong with the source + // + return RETURN_INVALID_PARAMETER; + } + + return RETURN_SUCCESS; +} + + diff --git a/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/TianoCompress.h b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/TianoCompress.h new file mode 100644 index 00000000..b4867b8f --- /dev/null +++ b/src/VBox/Devices/EFI/Firmware/BaseTools/Source/C/TianoCompress/TianoCompress.h @@ -0,0 +1,431 @@ +/** @file + Internal include file for Tiano Decompress Library. + + Copyright (c) 2006 - 2018, Intel Corporation. All rights reserved.
+ SPDX-License-Identifier: BSD-2-Clause-Patent + +**/ + +#ifndef __TIANO_DECOMPRESS_H__ +#define __TIANO_DECOMPRESS_H__ + +#include +#include +#include + + +// +// Decompression algorithm begins here +// +#define UTILITY_NAME "TianoCompress" +#define UTILITY_MAJOR_VERSION 0 +#define UTILITY_MINOR_VERSION 1 + +// +// Default output file name +// +#define DEFAULT_OUTPUT_FILE "file.tmp" + +#define BITBUFSIZ 32 +#define MAXMATCH 256 +#define THRESHOLD 3 +#define CODE_BIT 16 +#define BAD_TABLE - 1 + +typedef INT32 NODE; + +// +// C: Char&Len Set; P: Position Set; T: exTra Set +// +#define NC (0xff + MAXMATCH + 2 - THRESHOLD) +#define CBIT 9 +#define MAXPBIT 5 +#define TBIT 5 +#define MAXNP ((1U << MAXPBIT) - 1) +#define NT (CODE_BIT + 3) +#if NT > MAXNP +#define NPT NT +#else +#define NPT MAXNP +#endif + +typedef struct { + UINT8 *mSrcBase; // Starting address of compressed data + UINT8 *mDstBase; // Starting address of decompressed data + UINT32 mOutBuf; + UINT32 mInBuf; + + UINT16 mBitCount; + UINT32 mBitBuf; + UINT32 mSubBitBuf; + UINT16 mBlockSize; + UINT32 mCompSize; + UINT32 mOrigSize; + + UINT16 mBadTableFlag; + + UINT16 mLeft[2 * NC - 1]; + UINT16 mRight[2 * NC - 1]; + UINT8 mCLen[NC]; + UINT8 mPTLen[NPT]; + UINT16 mCTable[4096]; + UINT16 mPTTable[256]; + + // + // The length of the field 'Position Set Code Length Array Size' in Block Header. + // For EFI 1.1 de/compression algorithm, mPBit = 4 + // For Tiano de/compression algorithm, mPBit = 5 + // + UINT8 mPBit; +} SCRATCH_DATA; + +// +// Function Prototypes +// + +EFI_STATUS +GetFileContents ( + IN char *InputFileName, + OUT UINT8 *FileBuffer, + OUT UINT32 *BufferLength + ); + +STATIC +VOID +PutDword( + IN UINT32 Data + ); + +STATIC +EFI_STATUS +AllocateMemory ( + VOID + ); + +STATIC +VOID +FreeMemory ( + VOID + ); + +STATIC +VOID +InitSlide ( + VOID + ); + +STATIC +NODE +Child ( + IN NODE NodeQ, + IN UINT8 CharC + ); + +STATIC +VOID +MakeChild ( + IN NODE NodeQ, + IN UINT8 CharC, + IN NODE NodeR + ); + +STATIC +VOID +Split ( + IN NODE Old + ); + +STATIC +VOID +InsertNode ( + VOID + ); + +STATIC +VOID +DeleteNode ( + VOID + ); + +STATIC +VOID +GetNextMatch ( + VOID + ); + +STATIC +EFI_STATUS +Encode ( + VOID + ); + +STATIC +VOID +CountTFreq ( + VOID + ); + +STATIC +VOID +WritePTLen ( + IN INT32 Number, + IN INT32 nbit, + IN INT32 Special + ); + +STATIC +VOID +WriteCLen ( + VOID + ); + +STATIC +VOID +EncodeC ( + IN INT32 Value + ); + +STATIC +VOID +EncodeP ( + IN UINT32 Value + ); + +STATIC +VOID +SendBlock ( + VOID + ); + +STATIC +VOID +Output ( + IN UINT32 c, + IN UINT32 p + ); + +STATIC +VOID +HufEncodeStart ( + VOID + ); + +STATIC +VOID +HufEncodeEnd ( + VOID + ); + +STATIC +VOID +MakeCrcTable ( + VOID + ); + + +STATIC +VOID +PutBits ( + IN INT32 Number, + IN UINT32 Value + ); + +STATIC +INT32 +FreadCrc ( + OUT UINT8 *Pointer, + IN INT32 Number + ); + +STATIC +VOID +InitPutBits ( + VOID + ); + +STATIC +VOID +CountLen ( + IN INT32 Index + ); + +STATIC +VOID +MakeLen ( + IN INT32 Root + ); + +STATIC +VOID +DownHeap ( + IN INT32 Index + ); + +STATIC +VOID +MakeCode ( + IN INT32 Number, + IN UINT8 Len[ ], + OUT UINT16 Code[] + ); + +STATIC +INT32 +MakeTree ( + IN INT32 NParm, + IN UINT16 FreqParm[], + OUT UINT8 LenParm[ ], + OUT UINT16 CodeParm[] + ); + +/** + Read NumOfBit of bits from source into mBitBuf + + Shift mBitBuf NumOfBits left. Read in NumOfBits of bits from source. + + @param Sd The global scratch data + @param NumOfBits The number of bits to shift and read. + +**/ +VOID +FillBuf ( + IN SCRATCH_DATA *Sd, + IN UINT16 NumOfBits + ); + +/** + Get NumOfBits of bits out from mBitBuf + + Get NumOfBits of bits out from mBitBuf. Fill mBitBuf with subsequent + NumOfBits of bits from source. Returns NumOfBits of bits that are + popped out. + + @param Sd The global scratch data. + @param NumOfBits The number of bits to pop and read. + + @return The bits that are popped out. + +**/ +UINT32 +GetBits ( + IN SCRATCH_DATA *Sd, + IN UINT16 NumOfBits + ); + +/** + Creates Huffman Code mapping table according to code length array. + + Creates Huffman Code mapping table for Extra Set, Char&Len Set + and Position Set according to code length array. + + @param Sd The global scratch data + @param NumOfChar Number of symbols in the symbol set + @param BitLen Code length array + @param TableBits The width of the mapping table + @param Table The table + + @retval 0 OK. + @retval BAD_TABLE The table is corrupted. + +**/ +UINT16 +MakeTable ( + IN SCRATCH_DATA *Sd, + IN UINT16 NumOfChar, + IN UINT8 *BitLen, + IN UINT16 TableBits, + OUT UINT16 *Table + ); + +/** + Decodes a position value. + + Get a position value according to Position Huffman Table. + + @param Sd the global scratch data + + @return The position value decoded. + +**/ +UINT32 +DecodeP ( + IN SCRATCH_DATA *Sd + ); + +/** + Reads code lengths for the Extra Set or the Position Set. + + Read in the Extra Set or Position Set Length Array, then + generate the Huffman code mapping for them. + + @param Sd The global scratch data. + @param nn Number of symbols. + @param nbit Number of bits needed to represent nn. + @param Special The special symbol that needs to be taken care of. + + @retval 0 OK. + @retval BAD_TABLE Table is corrupted. + +**/ +UINT16 +ReadPTLen ( + IN SCRATCH_DATA *Sd, + IN UINT16 nn, + IN UINT16 nbit, + IN UINT16 Special + ); + +/** + Reads code lengths for Char&Len Set. + + Read in and decode the Char&Len Set Code Length Array, then + generate the Huffman Code mapping table for the Char&Len Set. + + @param Sd the global scratch data + +**/ +VOID +ReadCLen ( + SCRATCH_DATA *Sd + ); + +/** + Decode a character/length value. + + Read one value from mBitBuf, Get one code from mBitBuf. If it is at block boundary, generates + Huffman code mapping table for Extra Set, Code&Len Set and + Position Set. + + @param Sd The global scratch data. + + @return The value decoded. + +**/ +UINT16 +DecodeC ( + SCRATCH_DATA *Sd + ); + +/** + Decode the source data and put the resulting data into the destination buffer. + + Decode the source data and put the resulting data into the destination buffer. + + @param Sd The global scratch data + +**/ +VOID +Decode ( + SCRATCH_DATA *Sd + ); + +RETURN_STATUS +EFIAPI +TDecompress ( + IN VOID *Source, + IN OUT VOID *Destination, + IN OUT VOID *Scratch, + IN UINT32 Version + ); + +#endif -- cgit v1.2.3