compress.c

Next BIOS Source code : Extensible Firmware Interface

/*++

Copyright (c)  1999 - 2002 Intel Corporation. All rights reserved
This software and associated documentation (if any) is furnished
under a license and may only be used or copied in accordance
with the terms of the license. Except as permitted by such
license, no part of this software or documentation may be
reproduced, stored in a retrieval system, or transmitted in any
form or by any means without the express written consent of
Intel Corporation.

Module Name:

  Compress.c

Abstract:

  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.

Revision History:

  - OPSD code

    $Revision:   1.0  $
    $Date:   08 Apr 1996 12:40:28  $
    $Log:   P:\source\tools.bio\grfxlogo\src\compress.c_z  $

    Rev 1.0   08 Apr 1996 12:40:28   BWTRIPLE
    Initial revision.

  - Ported to EFI, March 2001

    Items modified: 
     1. replace native C data types with EFI data types
     2. reformat
     3. remove warnings using explicit data type casting
     4. change the interface: 
        standalone utility -> callable function (Compress ())
     5. refine comments
  
--*/

#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdarg.h>
#include <stdio.h>
#include "efi.h"
#include "Compress.h"

#define STATIC static

//
// Macro Definitions
//

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], mCTable[4096], mCCode[NC],
              mPFreq[2 * NP - 1], mPTCode[NPT], mTFreq[2 * NT - 1];

STATIC NODE   mPos, mMatchPos, mAvail, *mPosition, *mParent, *mPrev, *mNext = NULL;


//
// functions
//

EFI_STATUS
Compress (
  IN      UINT8   *SrcBuffer,
  IN      UINT32  SrcSize,
  IN      UINT8   *DstBuffer,
  IN OUT  UINT32  *DstSize
  )
/*++

Routine Description:

  The main compression routine.

Arguments:

  SrcBuffer   - The buffer storing the source data
  SrcSize     - The size of source data
  DstBuffer   - The buffer to store the compressed data
  DstSize     - On input, the size of DstBuffer; On output,
                the size of the actual compressed data.

Returns:

  EFI_BUFFER_TOO_SMALL  - The DstBuffer is too small. In this case,
                DstSize contains the size needed.
  EFI_SUCCESS           - Compression is successful.

--*/
{
  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;
  }

}

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 ()
/*++

Routine Description:

  Allocate memory spaces for data structures used in compression process
  
Argements: (VOID)

Returns:

  EFI_SUCCESS           - Memory is allocated successfully
  EFI_OUT_OF_RESOURCES  - Allocation fails

--*/
{
  UINT32      i;
  
  mText       = malloc (WNDSIZ * 2 + MAXMATCH);
  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));
  
  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;
}

VOID
FreeMemory ()
/*++

Routine Description:

  Called when compression is completed to free memory previously allocated.
  
Arguments: (VOID)

Returns: (VOID)

--*/
{
  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;
}


STATIC 
VOID 
InitSlide ()
/*++

Routine Description:

  Initialize String Info Log data structures
  
Arguments: (VOID)

Returns: (VOID)

--*/
{
  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;
  }  
}


STATIC 
NODE 
Child (
  IN NODE q, 
  IN UINT8 c
  )
/*++

Routine Description:

  Find child node given the parent node and the edge character
  
Arguments:

  q       - the parent node
  c       - the edge character
  
Returns:

  The child node (NIL if not found)  
  
--*/
{
  NODE r;
  
  r = mNext[HASH(q, c)];
  mParent[NIL] = q;  /* sentinel */
  while (mParent[r] != q) {
    r = mNext[r];
  }
  
  return r;
}

STATIC 
VOID 
MakeChild (
  IN NODE q, 
  IN UINT8 c, 
  IN NODE r
  )
/*++

Routine Description:

  Create a new child for a given parent node.
  
Arguments:

  q       - the parent node
  c       - the edge character
  r       - the child node
  
Returns: (VOID)

--*/
{
  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]++;
}

STATIC 
VOID 
Split (
  NODE Old
  )
/*++

Routine Description:

  Split a node.
  
Arguments:

  Old     - the node to split
  
Returns: (VOID)

--*/
{
  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);
}

STATIC 
VOID 
InsertNode ()
/*++

Routine Description:

  Insert string info for current position into the String Info Log
  
Arguments: (VOID)

Returns: (VOID)

--*/
{
  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. 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--;
    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;
  
}

STATIC 
VOID 
DeleteNode ()
/*++

Routine Description:

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

Returns: (VOID)

--*/
{
  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) {