lzss.c

一个加密库代码

/*
 * Copyright 1997-2005 Markus Hahn 
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); 
 * you may not use this file except in compliance with the License. 
 * You may obtain a copy of the License at 
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "cpkernel.h"
#include "LZSS.h"

#include <stdlib.h>
#include <memory.h>

// i/o exception codes
#define LZSS_EOB         257    // end of buffer
#define LZSS_EOD         258    // end of data


// some compressor constants
#define LZSS_N          4096    // size of ring buffer
#define LZSS_F            18    // upper limit for match_length
#define LZSS_THRESHOLD     2    // encode string into position and length
                                // if match_length is greater than this
#define LZSS_NIL      LZSS_N    // index for root of binary search trees



struct LZSSCTX 
{
  // state freeze for compression
  BYTEBOOL blSaveDone;
  int nSaveI, nSaveR, nSaveC, nSaveLen, nSaveS;
  int nSaveLastMatchLength, nSaveCodeBufPtr;
  WORD8 bSaveMask;
  WORD8 saveCode_buf[17];
  // state freeze for decompression (additional necessary data)
  int nSaveJ, nSaveK;
  WORD16 wSaveFlags;
  // the interrupt point code
  WORD16 wInterruptPoint;

  // general runtime stuff
  WORD8 text_buf[LZSS_N + LZSS_F - 1];      // ring buffer of size N, with
                                            // extra F-1 bytes to facilitate
                                            // string comparison
  int nMatchPosition, nMatchLength;   // of longest match.
  // these are set by the insertNode() procedure.
  int lson[LZSS_N + 1];     // left & right children & parents
  int rson[LZSS_N + 257];   // these constitute binary search trees
  int dad[LZSS_N + 1];
  // for readByte() and writeByte()
  WORD32 lSourceSize;
  WORD32 lDrainSize;
  WORD32 lBytesRead;
  WORD32 lBytesWritten;
  WORD8* pDataSource;
  WORD8* pDataDrain;
  // End Of Data (stream)
  BYTEBOOL blEOD;
};




PLZSSCTX CRYPTPAK_API LZSS_Create() 
{
#ifdef KERNEL_COMPILE
	return (PLZSSCTX)ExAllocatePool( NonPagedPool, sizeof(LZSSCTX)  );
#else
	return (PLZSSCTX) malloc(sizeof(LZSSCTX));
#endif
}


void CRYPTPAK_API LZSS_Destroy
  (PLZSSCTX pCtx) 
{
#ifdef KERNEL_COMPILE
	if (pCtx) ExFreePool( pCtx );
#else
	if (pCtx) free(pCtx);
#endif

}




// internal (de)compression routines...


// initialize trees
static void initTree(PLZSSCTX pCtx) 
{
    int nI;

    // for nI = 0 to LZSS_N - 1, rson[nI] and lson[nI] will be the right and
    // left children of node nI.  These nodes need not be initialized.
    // Also, dad[nI] is the parent of node nI.  These are initialized to
    // LZSS_NIL (= LZSS_N), which stands for 'not used.'
    // For nI = 0 to 255, rson[LZSS_N + nI + 1] is the root of the tree
    // for strings that begin with character nI.  These are initialized
    // to LZSS_NIL.  Note there are 256 trees.
    for (nI = LZSS_N + 1; nI <= (LZSS_N + 256); nI++) 
      pCtx->rson[nI] = LZSS_NIL;
    for (nI = 0; nI < LZSS_N; nI++) 
      pCtx->dad[nI] = LZSS_NIL;
}



// inserts a mode into tree
void insertNode
  (PLZSSCTX pCtx, 
   int nR) 
{
  // copy some context members to local members to
  // increase the execution speed
  WORD8* text_buf = pCtx->text_buf;
  int* lson = pCtx->lson;
  int* rson = pCtx->rson;
  int* dad = pCtx->dad;
  int nMatchPosition = pCtx->nMatchPosition;
  int nMatchLength = 0;

  // local variables
  WORD8* pKey = &text_buf[nR];
  int nI;
  int nP = LZSS_N + 1 + pKey[0];
  int nCmp = 1;

  // (Inserts string of length LZSS_F, text_buf[nR..nR + LZSS_F - 1], into one
  // of the trees (text_buf[nR]'th tree) and returns the longest-match position
  // and length via the global variables nMatchPosition and nMatchLength. If 
  // nMatchLength = F, then removes the old node in favor of the new one,
  // because the old one will be deleted sooner. Note nR plays double role, as
  // tree node and position in buffer.)

  lson[nR] = rson[nR] = LZSS_NIL;
  for (;;)
  {
    if (nCmp >= 0) 
    {
      if (rson[nP] != LZSS_NIL) 
        nP = rson[nP];
      else 
      {
        rson[nP] = nR;
        dad[nR] = nP;
        pCtx->nMatchPosition = nMatchPosition;
        pCtx->nMatchLength = nMatchLength;
        return;
      }
    }
    else 
    {
      if (lson[nP] != LZSS_NIL) 
        nP = lson[nP];
      else 
      {
        lson[nP] = nR;
        dad[nR] = nP;
        pCtx->nMatchPosition = nMatchPosition;
        pCtx->nMatchLength = nMatchLength;
        return;
      }
    }
    for (nI = 1; nI < LZSS_F; nI++) 
    {
      if ((nCmp = pKey[nI] - text_buf[nP + nI]) != 0)  break;
    }
    if (nI > nMatchLength) 
    {
      nMatchPosition = nP;
      if ((nMatchLength = nI) >= LZSS_F) break;
    }
  }
  dad[nR] = dad[nP];
  lson[nR] = lson[nP];
  rson[nR] = rson[nP];
  dad[lson[nP]] = nR;
  dad[rson[nP]] = nR;
  if (rson[dad[nP]] == nP) rson[dad[nP]] = nR;
  else                     lson[dad[nP]] = nR;
  dad[nP] = LZSS_NIL; // remove nP

  pCtx->nMatchPosition = nMatchPosition;
  pCtx->nMatchLength = nMatchLength;
}



// deletes node p from tree
void deleteNode(PLZSSCTX pCtx, int nP) {

  // copy some context members to local members to
  // to increase the execution speed
  int* lson = pCtx->lson;
  int* rson = pCtx->rson;
  int* dad = pCtx->dad;

  // local variable
  int nQ;

  // start...
  if (dad[nP] == LZSS_NIL) return;  // not in tree
  if (rson[nP] == LZSS_NIL) 
    nQ = lson[nP];
  else 
  {
    if (lson[nP] == LZSS_NIL)
      nQ = rson[nP];
    else 
    {
      nQ = lson[nP];
      if (rson[nQ] != LZSS_NIL) 
      {
        do 
        {
          nQ = rson[nQ];
        } 
        while (rson[nQ] != LZSS_NIL);

        rson[dad[nQ]] = lson[nQ];
        dad[lson[nQ]] = dad[nQ];
        lson[nQ] = lson[nP];
        dad[lson[nP]] = nQ;
      }
      rson[nQ] = rson[nP];
      dad[rson[nP]] = nQ;
    }
  }
  dad[nQ] = dad[nP];
  if (rson[dad[nP]] == nP) rson[dad[nP]] = nQ;
  else                     lson[dad[nP]] = nQ;
  dad[nP] = LZSS_NIL;
}



// internal stream i/o routines...


// reads a byte from the input buffer and checks if the 
// buffer run out of data
WORD16 readByte
  (PLZSSCTX pCtx) 
{
  // enough bytes?
  if (pCtx->lBytesRead < pCtx->lSourceSize)
    // return the actual byte in the buffer
    return pCtx->pDataSource[pCtx->lBytesRead++];
  if (pCtx->blEOD) 
    return LZSS_EOD; // end of data
  else 
    return LZSS_EOB; // end of buffer, but we'll be back
}




// writes a byte to the output buffer, used for compression,
// does no range check because compressed data won't be much
// larger (in the worst case) than the original data (and an
// additional check will cost too much overhead)
void cWriteByte
  (PLZSSCTX pCtx, 
   WORD8 bVal) 
{
  // just write the byte to the output buffer
  pCtx->pDataDrain[pCtx->lBytesWritten++] = bVal;
}



// writes a byte to the output buffer and checks if the buffer
// is full, used for decompression (because just a hundred of
// compressed bytes might create millions of original bytes)
BYTEBOOL dWriteByte
  (PLZSSCTX pCtx, 
   WORD8 bVal) 
{
  // enough free space?
  if (pCtx->lBytesWritten < pCtx->lDrainSize) 
  {
    pCtx->pDataDrain[pCtx->lBytesWritten++] = bVal;
    return BOOL_TRUE;
  }
  return BOOL_FALSE;
}



// macro to save the local variables in a context, used in LZSS_Compress()
#define COMPRESS_SAVE_LOCAL_VAR pCtx->blSaveDone = blDone;                     \
                                pCtx->nSaveI = nI;                             \
                                pCtx->nSaveC = nC;                             \
                                pCtx->nSaveLen = nLen;                         \
                                pCtx->nSaveR = nR;                             \
                                pCtx->nSaveS = nS;                             \
                                pCtx->nSaveLastMatchLength = nLastMatchLength; \
                                pCtx->nSaveCodeBufPtr = nCodeBufPtr;           \
                                pCtx->bSaveMask = bMask;                       \
                                memcpy(pCtx->saveCode_buf, code_buf, 17);



WORD32 CRYPTPAK_API LZSS_Compress
  (PLZSSCTX pCtx, 
   const void* pSource, 
   void* pTarget, 
   WORD32 lNumOfBytes, 
   WORD8 bCondition) 
{
  BYTEBOOL blDone;
  int nI, nC, nLen, nR, nS, nLastMatchLength, nCodeBufPtr;
  WORD8 bMask;
  WORD8 code_buf[17];
  WORD16 wTemp;  // (this variable must not be saved)

  // first setup the i/o pointers and the counters
  pCtx->pDataSource = (WORD8*) pSource;
  pCtx->pDataDrain = (WORD8*) pTarget;
  pCtx->lSourceSize = lNumOfBytes;
  pCtx->lBytesRead = 0;
  pCtx->lBytesWritten = 0;
  
  // end of data stream?
  if ((bCondition & LZSS_STOP) == LZSS_STOP) pCtx->blEOD = BOOL_TRUE;
  else pCtx->blEOD = BOOL_FALSE;

  // must we first launch the compression engine?
  if ((bCondition & LZSS_START) == LZSS_START)
  {
	  // (populate state things, otherwise the debug version will fail because
	  //  of assumed missing initialization)
	  nC = nLen = nR = nS = 0;
	  nLastMatchLength = nCodeBufPtr = 0;
	  goto ENTRYPOINT1;
  }