lzsc.c

vc环境下的pgp源码

/*------------------------------------------------------------------------------*/
/* LZS221-PPP Version 3.01 Release                                              */
/*------------------------------------------------------------------------------*/
/* LZSC.C                                                                       */
/*  Compressor and Decompressor functions.                                      */
/*------------------------------------------------------------------------------*/
/* hi/fn (R), LZS (R)                                                           */
/* (c) 1988-1993, hi/fn                                                         */
/* Includes one or more U.S. Patents:                                           */
/*   No. 4701745, 5016009, 5126739, 5146221, and 5414425.                       */
/*   Other patents pending                                                      */
/*------------------------------------------------------------------------------*/
/* Engineering Sequence Number                                                  */
/*  3001                                                                        */
/*------------------------------------------------------------------------------*/

/* $Id: LZSC.C,v 1.4 1999/01/18 21:45:58 dgal Exp $	*/

/*
******************************************************************************
*
*						 Included Files
*
*****************************************************************************/

/* Debug switch */

#define		LZS_DEBUG	0		/* 0 = Debug off, 1 = Debug on */

#include	"lzsc.h"

/*

****************************************************************************
*
* Block Name:        Shorthand declarations
*
* Functional Block:  LZS221-PPP
*
* Special Notes:
*
*****************************************************************************/

/* Other constant definitions */

#define		boolean		PGPUInt16
#define		TRUE		1
#define		FALSE		0
#define		OK			TRUE
#define		NOT_OK		FALSE


/*

****************************************************************************
*
* Block Name:        Symbolic Constants
*
* Functional Block:  LZS221-PPP
*
* Special Notes:
*
*****************************************************************************/

/* Various Compression Constants */

#define	HISTORY_SIZE			2048
#define	HISTORY_MASK			(HISTORY_SIZE - 1)

#define	MAX_STRING_LENGTH		0xFFFFFFFFL
#define	MIN_RLE_LENGTH			23   /* Min string length for RLE encoding	*/
#define	BITS_PER_RLE_UNIT		4	 /* # bits in each unit of RLE length	*/
#define	RLE_UNIT_LENGTH			((1 << BITS_PER_RLE_UNIT) - 1)
									 /* # bytes input for each unit of RLE	*/
									 /* encoded output */
									 /* to start */


/* Hash Table related */

#define	HASH_TABLE_SIZE			4096
#define	BOUNDARY_BETWEEN_HALVES	0x7FFFFFFFL	/* history pointer test mask	*/
#define	INVALID_FOR_1ST_HALF	0xC0000000L	/* history pointer value		*/
#define	INVALID_FOR_2ND_HALF	0x40000000L	/* history pointer value		*/


/*

****************************************************************************
*
* Block Name:        Performance tuning parameters
*
* Functional Block:  LZS221-PPP
*
* Special Notes:     SEARCH_COUNT_LIMIT specifies the maximun number of 
*					 attempts to find a longer string that starts with the
*					 current byte pair being processed.  The range of valid
*					 values for SEARCH_COUNT_LIMIT is 0 to 2044.
*
*					 REMATCH_SIZE_LIMIT specifies the compressed string length
*					 which is "good enough".  Once a string of this length
*					 has been found no attempt will be made to find a longer
*					 string.  The range of valid values for REMATCH_SIZE_LIMIT
*					 is 2 to 23.
*
*					 For both of these parameters lowering the parameter
*					 increases speed and decreases compression.  Increasing
*                    either or both parameters decreases the speed and raises
*					 the compression.
*
*					 Note that SEARCH_COUNT_LIMIT was replaced by the
*					 performance parameter to LZS_Compress starting with
*					 version 3.0 of this code.
*
*****************************************************************************/


#define	SEARCH_COUNT_LIMIT		8	/* Max attempted hash bucket searches	*/
#define	REMATCH_SIZE_LIMIT		8	/* String size limit on hash searches	*/


/*

******************************************************************************
*
* Block Name:        Scratch RAM structure(s)
*
* Functional Block:
*
* Special Notes:
*
*****************************************************************************/

typedef struct
	{
	PGPUInt8 LZS_FAR *	inputDataHandle ; /* global pointer into source buffer	*/
	PGPUInt32			inputDataCount  ; /* global bytes left in source buffer */
	PGPUInt8 LZS_FAR *	outputDataHandle; /* global pointer into dest buffer	*/
	PGPUInt32			outputDataCount ; /* global bytes left in dest buffer	*/

						/* Compress function variables */

	PGPUInt32		historyPointer;
	PGPUInt32		historyPointerMinus1;
	PGPUInt16		historyIndexMinus1;

	PGPUInt8		currentByte;				/* last byte read in		*/
	PGPUInt8		dummy1;			/* This preserves the size of the struct	*/
								/* when a word aligned machine is used (68K)*/
	PGPUInt16		currentBytePair;			/* last two bytes read in	*/

	PGPUInt32		stringLength;				/* current string length,	*/
											/* not including RLE_Length.*/

						/* !!! Note that stringLength == 0 means !!! */
						/* !!! that there is no	current string	 !!! */

	PGPUInt32		RLE_Length;		/* Amount of string that is RLE encoded		*/
								/* Note total string length = stringLength	*/
								/* + RLE_Length for recently hashed byte	*/
								/* pairs.									*/

	PGPUInt16		matchIndex;			/* index into history of current		*/
									/* match string							*/

	PGPUInt32 LZS_FAR	* hashAddress;	/* pointer into hash table				*/
	PGPUInt32		bytePairOffset;		/* offset to last byte pair w/ same		*/
									/* hash as currentBytePair				*/

	PGPUInt16		matchStringOffset;	/* offset to current match string		*/
	PGPUInt16		currentStringIndex;	/* history index of current match string*/

	PGPUInt16		firstMatchOffset;  /* offset to 1st match of currentBytePair*/
	PGPUInt16		rematchOffset;	/* possible currentBytePair rematch offset	*/
	PGPUInt16		searchCount;	/* depth of stringList (hash bucket) search	*/
	boolean		compressedSomeData;	/* first pass thru compress flag		*/


/* NOTE: PutBits VARS MUST BE GLOBAL FOR CURRENT RECURSIVE CODING OF PutBits*/

						/* PutBits Input Vars */

	PGPUInt16		bitPattern;		/* right justified bit pattern to output	*/
	PGPInt16		numberOfBits;	/* number of bits in pattern to output		*/

						/* PutBits state vars */

	PGPUInt8		outputByte;		/* current partial byte not yet output		*/
	PGPUInt8		dummy2;			/* This preserves the size of the struct	*/
								/* when a word aligned machine is used (68K)*/
	PGPInt16		nextFreeBit;	/* next available bit position in outputByte*/
								/* 1 relative from the right.				*/

						/* PutBits return value */

	boolean		destBufferFull;

						/* PutCompressedString variables */

	boolean		stringOutputStarted;

	} CscratchRamType;

/*--------------------------------------------------------------------------*/

typedef struct
	{
	PGPUInt8 LZS_FAR *	inputDataHandle ; /* global pointer into source buffer	*/
	PGPUInt32			inputDataCount  ; /* global bytes left in source buffer */
	PGPUInt8 LZS_FAR *	outputDataHandle; /* global pointer into dest buffer	*/
	PGPUInt32			outputDataCount ; /* global bytes left in dest buffer	*/

	PGPUInt16		historyIdx;					/* current index into history	*/
	PGPUInt16		lastByteOfCompressedInput;	/* unused bits from last read	*/
											/* byte of compressed input	*/

	PGPUInt16		decompressState;
	boolean		decompressInitialized;		/* global state flag	*/

	PGPInt16		getBitsCount;	/* Number of bits to get from source buffer	*/
	PGPUInt16		sourceBits;		/* Holds the return value					*/
	PGPUInt16		getBitsResult;	/* Holds the return value					*/
	PGPInt16		bitAlign;		/* number of bits not yet used from	last	*/
								/* read byte of compressed input			*/

	PGPInt16		offset;			/* Offset of current string into history	*/
	PGPUInt32		length;			/* Length of current string					*/

	boolean		decompressingAString;		/* global state flag	*/
	}
		DscratchRamType;

/*--------------------------------------------------------------------------*/

typedef struct
	{
	PGPUInt8	c_history[HISTORY_SIZE];	/* compression history				*/

	PGPUInt16	stringList[HISTORY_SIZE];	/* Hash buckets containing linked	*/
										/* list of relative offsets to		*/
										/* similarly hashed byte pairs		*/

	PGPUInt32	hashTable[HASH_TABLE_SIZE]; /* contains historyPointer values	*/

	CscratchRamType	sc ;

	PGPUInt8	d_history[HISTORY_SIZE];	/* decompression history			*/

	DscratchRamType	sd ;

	PGPUInt8	reserved[64];				/* room for future growth			*/
	}
		scratchRamType ;

#if LZS_DEBUG
#include	"stdio.h"
#include	"stdlib.h"
#endif

/*
*****************************************************************************
*
*						 Other Structure and Union Definitions
*
****************************************************************************/

/* Context structure: replaces global variables */

struct LZSContext
{
	scratchRamType	LZS_FAR *	sp ;	/* pointer to the scratch RAM */
	scratchRamType			 	sr ;	/* copy of the scratch RAM */
	PGPUInt16					performanceMode;
	PGPUInt16					event;
};


typedef	struct lengthTableEntryStruct
	{
	PGPUInt16	pattern;
	PGPInt16	size;
	}
		lengthTableEntryType;


/*

*****************************************************************************
*
*						 Macro Definitions
*
****************************************************************************/

/* min() is not available with some compilers */

/* #ifndef min(a,b) */

#ifndef min

#define min(a,b)    (((a) < (b)) ? (a) : (b))

#endif

/*

+*****************************************************************************
*
* Function Name:	GetHashFor
*
* Function:         MACRO: Hashes a byte pair
*
* Arguments:        diByte	- byte pair to be hashed.
*
* Globals Used:     None.
*
* Return:           12 bit hashed value for the 16 bit byte pair.
*
* Globals Altered:  None.
*
* Error Handling:	None.
*
* Algorithms:		If x and y represent the each byte of the sixteen bit byte
*					pair then this function is defined as follows:
*
*						Hash(x,y) = (x >> 4) ^ y;
*
* Notes:			Note that the hash is non-unique in that sixteen bit
*				    values are hashed into 12 bit values so duplications are
*					certain to occur.  Testing this particular function
*					several others on a large mixed data set showed that it
*					did an excellent job of distributing the encountered
*					values evenly amoung the has buckets.
*
*					This has function also has the following property:
*
*						if Hash(x,y) = Hash(a,b), and if x = a then y = b.
*
*					This means that only one byte in a hashed pair needs to
*					be tested to guarentee uniqueness.  The compress function
*					makes use of this fact to speed its search thru the
*					stringList (hash buckets).
*
-****************************************************************************/

#define GetHashFor(diByte) ((((diByte) & 0xFF00) >> 4) ^ ((diByte) & 0x00FF))


/*

+*****************************************************************************
*
* Function Name:	PutBitsMac
*
* Function:         Macro for calling the PutBits function
*
* Arguments:        bits	- Right aligned compressed data bit pattern to
*							   output
*					count	- Number of bits of compressed data to output
*
* Globals Used:     See the function PutBits.
*
* Return:           None.
*
* Globals Altered:  bitPattern		- set to bits
*					numberOfBits	- set to count;
*					See the function PutBits.
*
* Error Handling:	The global destBufferFull is set to TRUE if the
*					destination buffer count is exhausted.  It is set to OK
*					otherwise.
*
* Algorithms:
*
* Notes:			This macro exists to save time passing arguments to the
*					PutBits function.
*
*
*
-****************************************************************************/

#define PutBitsMac(bits,count) 	context->sr.sc.bitPattern=(bits); \
								context->sr.sc.numberOfBits=(count); \
								PutBits(context)


/*

+*****************************************************************************
*
* Function Name:	PutARawByte
*
* Function:         MACRO: Output a raw byte
*
* Arguments:        rawByte	- Right aligned raw byte value to output.
*
* Globals Used:     See the function PutBits.
*
* Return:           None.
*
* Globals Altered:  See the function PutBits.
*
* Error Handling:	The global destBufferFull is set to TRUE if the
*					destination buffer count is exhausted.  It is set to OK
*					otherwise.
*
* Algorithms:
*
* Notes:
*
-****************************************************************************/

#define	PutARawByte(rawByte)	PutBitsMac((rawByte),9); \
								context->event = PUT_RAW_BYTE


/*

+*****************************************************************************
*
* Function Name:	StartNewString
*
* Function:         Start a new string with currentBytePair
*
* Arguments:        None.
*
* Globals Used:     firstMatchOffset
*					historyIndexMinus1
*
* Return:           None.
*
* Globals Altered:  currentStringIndex
*					matchStringOffset
*					stringLength
*
* Error Handling:	None.
*
* Algorithms:
*
* Notes:			This macro tidys up use of inline code for speed.
*
-****************************************************************************/

#define	StartNewString() context->sr.sc.stringLength = 2; \
						 context->sr.sc.currentStringIndex=context->sr.sc.historyIndexMinus1; \
						 context->sr.sc.matchStringOffset = context->sr.sc.firstMatchOffset; \
						 context->event = STARTED_STRING


/*

+*****************************************************************************