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


/*

+*****************************************************************************
*
* Function Name:	HashTableNeedsRefresh
*
* Function:         MACRO: Returns TRUE if hash table needs refreshing
*
* Arguments:        None.
*
* Globals Used:     historyPointer
*
* Return:           TRUE if the hashTable need to refreshed, FALSE otherwise.
*
* Globals Altered:  None.
*
* Error Handling:	None.
*
* Algorithms:		See the function RefreshOldHashEntries.  Essentially the
*					has table is refreshed whenever the historyPointer equals
*					0 or 0x80000000.
*
* Notes:
*
-****************************************************************************/

#define HashTableNeedsRefresh() ((context->sr.sc.historyPointer & BOUNDARY_BETWEEN_HALVES) == 0)


/*

+*****************************************************************************
*
* Function Name:	CurrentStringExtends
*
* Function:         MACRO: Returns TRUE if current string extends
*
* Arguments:        None.
*
* Globals Used:     currentByte
*					c_history
*					matchIndex
*					stringLength
*
* Return:           TRUE if the next byte of the current match string equals
*					currentByte (the last byte read in), FALSE otherwise.
*
* Globals Altered:  None.
*
* Error Handling:	None.
*
* Algorithms:
*
* Notes:
*
-****************************************************************************/

#define CurrentStringExtends() 	(context->sp->c_history [ (PGPUInt16) \
								(( (PGPUInt32) context->sr.sc.matchIndex \
								+ context->sr.sc.stringLength + context->sr.sc.RLE_Length) \
								& (PGPUInt32) HISTORY_MASK)] == context->sr.sc.currentByte)


/*

*****************************************************************************
*
*						 Variable Declarations
*
****************************************************************************/

/* Copyright */

static char copyright[] =   "LZS221-PPP version 3.01\nCopyright 1988-93 hi/fn, San Diego, California.\nAll rights reserved.";

/*

Global variables put in LZSContext:

	scratchRamType	LZS_FAR *	sp ;
	scratchRamType			 	sr ;

*/

static lengthTableEntryType	lengthTable[24] =	/* look up table used to encode	*/
{										/* string lengths */
	{ 0x0,	0 },	/* not used		*/
	{ 0x0,	0 },	/* not used		*/
	{ 0x0,	2 },	/* length = 2	*/
	{ 0x1,	2 },	/* length = 3	*/
	{ 0x2,	2 },	/* length = 4	*/
	{ 0xC,	4 },	/* length = 5	*/
	{ 0xD,	4 },	/* length = 6	*/
	{ 0xE,	4 },	/* length = 7	*/
	{ 0xF0,	8 },	/* length = 8	*/
	{ 0xF1,	8 },	/* length = 9	*/
	{ 0xF2,	8 },	/* length = 10	*/
	{ 0xF3,	8 },	/* length = 11	*/
	{ 0xF4,	8 },	/* length = 12	*/
	{ 0xF5,	8 },	/* length = 13	*/
	{ 0xF6,	8 },	/* length = 14	*/
	{ 0xF7,	8 },	/* length = 15	*/
	{ 0xF8,	8 },	/* length = 16	*/
	{ 0xF9,	8 },	/* length = 17	*/
	{ 0xFA,	8 },	/* length = 18	*/
	{ 0xFB,	8 },	/* length = 19	*/
	{ 0xFC,	8 },	/* length = 20	*/
	{ 0xFD,	8 },	/* length = 21	*/
	{ 0xFE,	8 }		/* length = 22	*/
	};


/*

Global variables put in LZSContext:

	PGPUInt16	performanceMode;

*/

/* Performance mode hash decision table */

/*	Performance mode:	PM=0	PM=1	PM=2	   Event */

static PGPUInt16	okToHash[5][3]=	{
						{TRUE,	TRUE,	TRUE},	/* Put a raw byte			*/
						{TRUE,	TRUE,	TRUE},	/* Started a new string		*/
						{FALSE,	FALSE,	TRUE},	/* Extended a string		*/
						{FALSE,	FALSE,	TRUE},	/* Found a longer match		*/
						{FALSE,	TRUE,	TRUE}	/* Ended a string			*/
						};


/* Enumerated event values used with the hash decision table */

enum	{
		PUT_RAW_BYTE,
		STARTED_STRING,
		EXTENDED_STRING,
		FOUND_LONGER_MATCH,
		ENDED_STRING
		};

/*

Global variables put in LZSContext:

	PGPUInt16	event;

*/


/* decompression states */

enum
	{
	RAW_OR_COMPRESSED,
	PUTTING_RAW_BYTE,
	GETTING_OFFSET_TYPE,
	GETTING_OFFSET,
	LENGTH_DIBIT_1,
	LENGTH_DIBIT_2,
	LENGTH_NIBBLE_2,
	PUT_RLE_DATA,
	RLE_BITS
	};

/*

*****************************************************************************
*
*						 Function Prototypes
*
****************************************************************************/

static void InitCompressVars(LZSContextRef context);

static void RefreshOldHashEntries(LZSContextRef context);

static void PutBits(LZSContextRef context);

static void PutEndMark(LZSContextRef context);

static void InitHashTable
			(
			PGPUInt32 LZS_FAR *		hashTablePtr,
			PGPUInt32				initalValue
			);

static void PutCompressedString(
							   LZSContextRef	context,
							   PGPUInt16		rawStringOffset,
							   PGPUInt32		rawStringLength
							   );

static void InitDecompressVars(LZSContextRef context);

static boolean GetABit(LZSContextRef context);

static boolean GetBits(LZSContextRef context);

static void PutOutput(LZSContextRef context, PGPUInt8 c);


PGPUInt32 LZS_GetContextSize(void)
{
	return sizeof(LZSContext);
}


/*

+*****************************************************************************
*
* Function Name:	InitCompressVars
*
* Function:         Initialize compression variables
*
* Arguments:        None.
*
* Globals Used:     None.
*
* Return:           None.
*
* Globals Altered:  context->sr.sc.compressedSomeData
*					context->sr.sc.currentBytePair
*					context->sr.sc.destBufferFull
*					context->sr.sc.matchStringOffset
*					context->sr.sc.nextFreeBit
*					context->sr.sc.outputByte
*					context->sr.sc.stringLength
*
* Error Handling:	None.
*
* Algorithms:
*
* Notes:			The history pointers, history indicies, and hash table
*					are NOT initialized by this function.
*
-****************************************************************************/

static void InitCompressVars(LZSContextRef context)
	{

	/*
	Local Data Declarations:
	*/

	/*
	Body of function:
	*/

	context->sr.sc.nextFreeBit			= 8;

	context->sr.sc.outputByte			= 0;

	context->sr.sc.matchStringOffset		=
	context->sr.sc.currentBytePair		= 0;

	context->sr.sc.stringLength			=
	context->sr.sc.RLE_Length			= 0;

	context->sr.sc.compressedSomeData	=
	context->sr.sc.stringOutputStarted	= FALSE; /* used by PutCompressedString */

	return;

	}	/* InitCompressVars */

/*

+*****************************************************************************
*
* Function Name:	LZS_InitHistory
*
* Function:         Initialize compression scratch area
*
* Arguments:        None.
*
* Globals Used:     None.
*
* Return:           None.
*
* Globals Altered:
*
*	compress variables:
*
*					compressedSomeData
*					currentBytePair
*					historyPointer
*					historyPointerMinus1
*					matchStringOffset
*					nextFreeBit
*					outputByte
*					destBufferFull
*					stringLength
*
*	decompress variables:
*
*					bitAlign
*					decompressingAString
*					decompressInitialized
*					hashTable
*					histEndOfCompression
*					historyIdx
*					lastByteOfCompressedInput
*					length
*					offset
*
* Error Handling:	None.
*
* Algorithms:
*
* Notes:
*
-****************************************************************************/

void LZS_FAR	LZS_InitHistory(LZSContextRef context, void LZS_FAR	*scratch)
	{

	/*
	Local Data Declarations:
	*/

	/*
	Body of function:
	*/

#if LZS_DEBUG
	if (LZS_HISTORY_SIZE != sizeof(context->sr))
		{
		printf(
			  "The value of LZS_HISTORY_SIZE is incorrect it should be %d!\n",
			  sizeof(context->sr)
			  );
		exit (-1);
		}
#endif

	context->sp = (scratchRamType LZS_FAR *) scratch;

	/* compression vars */

	context->sr.sc = context->sp->sc ;					/* Make local copy of vars		*/
	context->sr.sc.historyPointer		= 0xFFFFFFFFL;					/* -1	*/
	context->sr.sc.historyPointerMinus1  = context->sr.sc.historyPointer - 1;
	context->sr.sc.destBufferFull		= FALSE;
	InitCompressVars(context);
	InitHashTable(context->sp->hashTable, INVALID_FOR_1ST_HALF);
	context->sp->sc = context->sr.sc;						/* Copy locals back over globals */

	/* decompression stuff */

	context->sr.sd = context->sp->sd ;					/* Make local copy of vars */
	context->sr.sd.historyIdx = 0; /* start over at beginning of decompress history */
	InitDecompressVars(context);
	context->sp->sd = context->sr.sd ;					/* Copy locals back over globals */

	return;

	}	/* LZS_InitHistory */

/*

+*****************************************************************************
*
* Function Name:	InitHashTable
*
* Function:         Initializes the hash table
*
* Arguments:        hashTablePtr	- Address of hash table to be initialized
*					initialValue	- Initial value for hash table entries
*
* Globals Used:     None.
*
* Return:           None.
*
* Globals Altered:  None.
*
* Error Handling:	None.
*
* Algorithms:
*
* Notes:			Fills hash table with initial value.
*
-****************************************************************************/

static void InitHashTable
			(
			PGPUInt32 LZS_FAR *		hashTablePtr,
			PGPUInt32				initalValue
			)
	{

	/*
	Local Data Declarations:
	*/

	PGPUInt16	i;

	/*
	Body of function:
	*/

	for (i = 0; i < HASH_TABLE_SIZE; i++)

		*hashTablePtr++ = initalValue;

	return;

	}	/* InitHashTable */

/*

+*****************************************************************************
*
* Function Name:	RefreshOldHashEntries
*
* Function:         Makes sure old hash table entries look old
*
* Arguments:        None.
*
* Globals Used:     hashTable
*					historyPointer
*
* Return:           None.
*
* Globals Altered:  hashTable
*
* Error Handling:	None
*
* Algorithms:		The values of history pointer range from 0 to 0xFFFFFFFF.
*					This range is divided into two sub-ranges, the first half,
*					0 thru 0x7FFFFFFF inclusive, and the second half including
*					0x80000000 thru 0xFFFFFFFF.  As the transition from the
*					first half to the second half is made old hash entries are
*					filled with a value from the first half to guarentee that
*					they will be invalid throughout the second half.  The
*					complementary process happens on the transition from the
*					second half back to the first half.
*
* Notes:			Since the hashTable contains 32 bit history pointer values
*					this refresh only takes place once for every 2 gigabytes
*					of raw data input to the compress function.
*
-****************************************************************************/

static void RefreshOldHashEntries(LZSContextRef context)
	{

	/*
	Local Data Declarations:
	*/

	register	PGPUInt16			i;
				PGPUInt32 LZS_FAR *	invalidationPtr;
				PGPUInt32			invalidationValue;


	/*
	Body of function:
	*/

	invalidationValue = INVALID_FOR_1ST_HALF;		/* assume first half	*/
	if (context->sr.sc.historyPointer != 0)					/* which half ?			*/
		invalidationValue = INVALID_FOR_2ND_HALF;	/* second half			*/

	invalidationPtr = context->sp->hashTable;				/* for every table entry*/
	for (i = 0; i < HASH_TABLE_SIZE; i++, invalidationPtr++)

		/* if the entry is old (minus 2 accounts for currentBytePair */
		if (context->sr.sc.historyPointer - *invalidationPtr > HISTORY_SIZE - 2)

			*invalidationPtr = invalidationValue;	/* invalidate old entry */

	return;

	}	/* RefreshOldHashEntries */

/*

+*****************************************************************************
*
* Function Name:	PutBits
*
* Function:         Outputs bits of compressed data
*
* Arguments:        None.
*
* Globals Used:     bitPattern
*					nextFreeBit
*					numberOfBits
*					outputByte
*					outputDataCount
*					outputDataHandle
*
* Return:           None.
*
* Globals Altered:  destBufferFull
*					outputByte
*					nextFreeBit
*					outputDataHandle
*					outputDataCount
*					outputByte
*					bitPattern
*					numberOfBits
*
* Error Handling:	The global destBufferFull is set to TRUE if the
*					destination buffer count is exhausted.  It is set to OK
*					otherwise.
*
* Algorithms:		Basically input comes from the variables bitPattern and
*					numberOfBits.  bitPattern contains the right aligned
*					compressed bit pattern to output.  Number of bits contains
*					the nubmer of bits to output from bitPattern.  The
*					new bit pattern is or'd left justified into outputByte
*					starting at nextFreeBit.  The values of nextFreeBit range
*					from 8 (msb) to 1 (lsb).  When the value of nextFreeBit
*					reaches 0 outputByte is written to the destination buffer
*					and nextFreeBit is reset to 8.
*
* Notes:			OutputByte and nextFree bit are globals whose state is
*					preserved across calls.  After all of the source data
*					has been compressed a call to PutEndMark will assure that
*					any remaining data held held in output byte is flushed to
*					buffer.
*
-****************************************************************************/

static void	PutBits(LZSContextRef context)
	{

	/*
	Local Data Declarations:
	*/

	register	PGPInt16		shiftCount;

	/*
	Body of function:
	*/

	if (context->sr.sc.outputDataCount == 0)	/* watch for full output buffer			*/
		context->sr.sc.destBufferFull = TRUE;/* initialized to OK by LZS_InitHistory */

	if ((shiftCount = context->sr.sc.numberOfBits - context->sr.sc.nextFreeBit) > 0)
		{
		context->sr.sc.outputByte |= (context->sr.sc.bitPattern >> shiftCount);
		context->sr.sc.nextFreeBit = 8;
		*context->sr.sc.outputDataHandle++ = context->sr.sc.outputByte;
		--context->sr.sc.outputDataCount;
		context->sr.sc.outputByte = 0;

		context->sr.sc.bitPattern &= ((1 << shiftCount) - 1);
		context->sr.sc.numberOfBits = shiftCount;
		PutBits(context);
		}

	else if (shiftCount < 0)
		{
		context->sr.sc.outputByte |= (context->sr.sc.bitPattern << -shiftCount);
		context->sr.sc.nextFreeBit -= context->sr.sc.numberOfBits;
		}

	else /* (shiftCount == 0) */
		{
		context->sr.sc.outputByte |= context->sr.sc.bitPattern;
		context->sr.sc.nextFreeBit = 8;
		*context->sr.sc.outputDataHandle++ = context->sr.sc.outputByte;
		--context->sr.sc.outputDataCount;
		context->sr.sc.outputByte = 0;
		}

	return;

	}	/* PutBits */

/*

+*****************************************************************************
*
* Function Name:	PutEndMark
*
* Function:         Outputs an end of compressed data mark
*
* Arguments:        None.
*
* Globals Used:     See PutBits.
*
* Return:           None.
*
* Globals Altered:  See 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:			Calling this functions forces all data that has been
*					compressed to be flushed to the destination buffer.
*
-****************************************************************************/

static void PutEndMark(LZSContextRef context)
	{

	/*
	Local Data Declarations:
	*/

	/*
	Body of function:
	*/

	/*----------------------------------------*/
	/* output the end of compressed data mark */
	/*----------------------------------------*/

	PutBitsMac(0x180, 9);

	/*------------------------------------*/
	/* flush any remaining bits to buffer */
	/*------------------------------------*/

	if (context->sr.sc.nextFreeBit != 8)
		{
		*context->sr.sc.outputDataHandle++ = context->sr.sc.outputByte;
		--context->sr.sc.outputDataCount;

		if (context->sr.sc.outputDataCount == 0)		/* watch for full output buffer */
			{
			context->sr.sc.destBufferFull = TRUE;	/* initialized to OK by			*/
			}								/* LZS_InitHistory				*/
		}

	context->sr.sc.nextFreeBit	= 8;
	context->sr.sc.outputByte	= 0;

	return;

	}	/* PutEndMark */

/*

+*****************************************************************************
*
* Function Name:	PutCompressedString
*
* Function:			Output a compressed string of data
*
* Arguments:        rawStringOffset	- Offset of compressed string
*					rawStringLength	- Length of compressed string
* Globals Used:     See PutBits.
*
* Return:           None.
*
* Globals Altered:  stringLength	- The current string length is set to 0
*									  at the end of this routine.  This is
*									  used as the indication that there is
*									  no current string.
*
*					See PutBits for complete list of altered globals.
*
* Error Handling:	The global destBufferFull is set to TRUE if the
*					destination buffer count is exhausted.  It is set to OK
*					otherwise.
*
* Algorithms:
*
* Notes:			Read note above about stringLength!
*
-****************************************************************************/

static void	PutCompressedString(
							   LZSContextRef	context,
							   PGPUInt16		rawStringOffset,
							   PGPUInt32		rawStringLength
							   )

	{

	/*
	Local Data Declarations:
	*/


	/*
	Body of function:
	*/

	if (context->sr.sc.stringOutputStarted == FALSE)
		{
		/*----------------*/
		/* 7 bit offset ? */
		/*----------------*/
		if (rawStringOffset < 128)
			{
			PutBitsMac(0x180 | rawStringOffset, 9);
			}
				/*-----------------*/
		else	/* 11 bit offset ? */
				/*-----------------*/
			{
			PutBitsMac(0x1000 | rawStringOffset, 13);
			}
		}

	/*--------------------------------------------------------------*/
	/* take care of any run length encoded portion of string length */
	/*--------------------------------------------------------------*/
	if (rawStringLength >= MIN_RLE_LENGTH)
		{
		PutBitsMac(RLE_UNIT_LENGTH, BITS_PER_RLE_UNIT);
		rawStringLength  -= RLE_UNIT_LENGTH;
		context->sr.sc.RLE_Length += RLE_UNIT_LENGTH;
		context->sr.sc.stringOutputStarted = TRUE;
		}

	else
		{
		/*--------------------------------------------*/
		/* look up the remainder of the string length */
		/*--------------------------------------------*/
		PutBitsMac(
				  lengthTable[(PGPUInt16) rawStringLength].pattern,
				  lengthTable[(PGPUInt16) rawStringLength].size
				  );

		/*----------------------------*/
		/* no current string any more */
		/*----------------------------*/
		context->sr.sc.stringOutputStarted = FALSE;
		context->sr.sc.stringLength = 0;
		context->sr.sc.RLE_Length   = 0;
		context->event = ENDED_STRING;
		}
	return;

	}	/* PutCompressedString */

/*

+*****************************************************************************
*
* Function Name:	PerformFlush
*
* Function:         Flush all compressed data & write EOCD mark
*
* Arguments:
* Globals Used:
* Hardware Inputs:
*
* Return:
* Globals Altered:
* Hardware Outputs:
*
* Error Handling:
*
* Algorithms/Structures:
*
* Notes:
*
-****************************************************************************/

static void PerformFlush(LZSContextRef context, PGPUInt16	flags)
	{

	/*
	Local Data Declarations:
	*/

	/*
	Body of function:
	*/

	/*--------------------------*/
	/* Flush any remaining data */
	/*--------------------------*/
	if (context->sr.sc.compressedSomeData == TRUE)
		{
		if (context->sr.sc.stringLength == 0)
			{
			PutARawByte(context->sr.sc.currentByte);
			}
		else
			PutCompressedString(context, context->sr.sc.matchStringOffset, context->sr.sc.stringLength);
		}

	PutEndMark(context);

	if ((flags & LZS_NO_CLEAR) == FALSE)
		{
		/*-----------------------------*/
		/* Invalidate old hash entries */
		/*-----------------------------*/
		if (0 - context->sr.sc.historyPointer >= HISTORY_SIZE)
			InitHashTable(context->sp->hashTable, INVALID_FOR_1ST_HALF);

		else if (0x80000000L - context->sr.sc.historyPointer >= HISTORY_SIZE)
			InitHashTable(context->sp->hashTable, INVALID_FOR_2ND_HALF);

		context->sr.sc.historyPointer		+= HISTORY_SIZE;
		context->sr.sc.historyPointerMinus1	+= HISTORY_SIZE;

		InitCompressVars(context);
		}
	/*---------------------------------------*/
	/* Forget old data. Reprime w/ next byte */
	/*---------------------------------------*/
	context->sr.sc.compressedSomeData = FALSE;

	return;

	}	/* PerformFlush */

/*

+*****************************************************************************
*
* Function Name:	LZS_Compress
*
* Function:         compress a buffer full of data
*
* Arguments:        sourceHandle	- pointer to pointer to source buffer
*					destHandle		- pointer to pointer to destination buffer
*					sourceCount		- pointer to size in bytes of data in
*									   source buffer.
*					destCount		- pointer to size in bytes of destination
*									   buffer.
*
* Globals Used:     compressedSomeData
*					currentByte
*					currentBytePair
*					currentStringIndex
*					hashTable
*					c_history
*					historyPointer
*					historyPointerMinus1
*					inputDataCount
*					inputDataHandle
*					matchIndex
*					matchStringOffset
*					outputDataCount
*					outputDataHandle
*					searchCount
*					stringLength
*					stringList
*
*
* Return:           None.
*
* Globals Altered:  bytePairOffset
*					compressedSomeData
*					currentByte
*					currentBytePair
*					currentStringIndex
*					firstMatchOffset
*					hashAddress
*					hashTable
*					c_history
*					historyPointer
*					historyPointerMinus1
*					inputDataCount
*					inputDataHandle
*					matchIndex
*					matchStringOffset
*					outputDataCount
*					outputDataHandle
*					rematchOffset
*					searchCount
*					searchCount
*					stringLength
*					stringList
*
* Error Handling:	Terminates if either source or destination counts are
*					exhausted.
*
* Algorithms:		Hash incoming byte pairs.  Store the current history
*					pointer in the hashTable.  Store offsets to previous hash
*					entries in stringList (hash buckets).  Search stringList
*					for matches to current byte pair.
*
* Pseudo-code:
*
* BEGIN
* {
* if there is data to compress and room to put it
* 	{
* 	initialize data;
* 	get a byte to prime the pump;
* 	while still data to compress and room to put it;
* 		{
* 		advance history and related vars;
* 		see if hash table needs to be refreshed;
* 		get another byte, update history, and string list;
* 		if offset to last hashed string greater than history size;
* 			stringList for current byte pair = 0;
* 		else
* 			{
* 			update string list with current byte pair offset;
* 			if not currently extending a string;
* 				search string list for current byte pair match;
* 			}
* 		update hash table with current byte pair information;
* 		if not currently extending a string
* 			if current byte pair match found
* 				start a new string;
* 			else
* 				output a raw byte;
* 		else
* 			{
* 			if current byte pair definitely not contained in history
* 				output current string;
* 			else
* 				{
* 				if string has reached maximum length
* 					output current string;
* 
* 				else if current match continues
* 					extend the current string;
* 
* 				else if the current string is long enough
* 					output current string;
*
* 				else
* 					{
* 					search for a longer match;
* 					if a longer match found
* 						extend the current string;
* 					else
* 						output current string;
* 					}
*
* 				if current string was output
* 					{
* 					search string list for current byte pair match;
* 					if match for current byte pair found
* 						start new string;
* 					}
* 				}
* 			}
* 		}
* 	}
* 	if the output buffer is full
* 		{
* 		flush any remaining data;
* 		put an end mark
* 		}
* }
* END
* 
* Notes:
*
-****************************************************************************/

PGPUInt16 LZS_FAR	LZS_Compress(
					LZSContextRef			 context,
					PGPUInt8	LZS_HANDLE	 sourceHandle,
					PGPUInt8	LZS_HANDLE	 destHandle,
					PGPUInt32	LZS_FAR		*sourceCount,
					PGPUInt32	LZS_FAR		*destCount,
					void		LZS_FAR		*scratch,
					PGPUInt16				 flags,
					PGPUInt16				 performance
					)
	{

	/*--------------------------*/
	/* Local Data Declarations: */
	/*--------------------------*/

	register	PGPUInt16	ii;
	register	boolean	foundLongerMatch;
				PGPUInt16	testIndex;
				PGPUInt16	returnValue = 0;

	/*--------------------------*/
	/* Body of function:        */
	/*--------------------------*/

#if LZS_TARGET == LZS_INTEL_86

	/*--------------------------------------------------------------------*/
	/* Validate source and destination counts on Intel X86 platforms.     */
	/* This is necessary because far pointers are used not huge pointers. */
	/*--------------------------------------------------------------------*/

	if ((*sourceCount > 0xFFFF) || (*destCount > 0xFFFF))
		{
		return (LZS_INVALID);
		}
#endif

	/*---------------------------------------*/
	/* initialize global pointers and counts */
	/*---------------------------------------*/
#if LZS_DEBUG
			event = 0xFFFF;
#endif

	/*----------------------------------------------------------------*/
	/* Make local copy of most vars to avoid speed hit of indirection */
	/*----------------------------------------------------------------*/

	context->sp = (scratchRamType LZS_FAR *) scratch;
	context->sr.sc = context->sp->sc ;

	context->sr.sc.inputDataHandle	= *sourceHandle;
	context->sr.sc.inputDataCount	= *sourceCount;
	context->sr.sc.outputDataHandle	= *destHandle;
	context->sr.sc.outputDataCount	= *destCount;
	context->sr.sc.destBufferFull	= FALSE;
	
	/*-----------------------------*/
	/* Extract performance mode.	*/	
	context->performanceMode = LZS_PERF_MASK & flags;
	
	/* Validate it.				*/
	if (context->performanceMode > LZS_PERF_MODE_2)
		{
		/* If invalid use mode 2.		*/
		context->performanceMode = LZS_PERF_MODE_2;
		}
	context->performanceMode >>= 3;		 /* Convert to array index for	*/
										 /* use with okToHash array.	*/

	if (*destCount <= LZS_DEST_MIN)
										/*---------------------------------*/
		returnValue = LZS_INVALID;		/* Don't do anything just return ! */
										/*---------------------------------*/
	  /*-------------------------------*/
	  /* and *destCount > LZS_DEST_MIN */
	  /*-------------------------------*/
	else if (context->sr.sc.inputDataCount != 0)
		{
		/*------------------------------------------------*/
		/* Provide for a cushion at the	end of the buffer */
		/*------------------------------------------------*/

		context->sr.sc.outputDataCount -= LZS_DEST_MIN;

		/*-------------------------*/
		/* if very first time thru */
		/*-------------------------*/
		if (context->sr.sc.compressedSomeData == FALSE)
			{
			/*-----------*/
			/*  GetAByte */
			/*-----------*/
			context->sr.sc.currentByte = *context->sr.sc.inputDataHandle++;
			--context->sr.sc.inputDataCount;
			/*----------------------------------------*/
			/* increment history pointer and indicies */
			/*----------------------------------------*/
			++context->sr.sc.historyPointer;
			++context->sr.sc.historyPointerMinus1;
			context->sr.sc.historyIndexMinus1 = (PGPUInt16) context->sr.sc.historyPointerMinus1
									  & HISTORY_MASK;
			/*------------------------------------*/
			/* update history and currentBytePair */
			/*------------------------------------*/
			context->sp->c_history [ (PGPUInt16) 
				context->sr.sc.historyPointer & HISTORY_MASK ] = context->sr.sc.currentByte;
			context->sr.sc.currentBytePair = (context->sr.sc.currentBytePair << 8)
								  +  context->sr.sc.currentByte;
			context->sr.sc.compressedSomeData = TRUE;
			}
		/*-----------------------------*/
		/* while buffers not exhausted */
		/*-----------------------------*/
		while ((context->sr.sc.inputDataCount != 0)
		&&    (context->sr.sc.destBufferFull == FALSE))
			{
			/*----------------------------------------*/
			/* increment history pointer and indicies */
			/*----------------------------------------*/
			++context->sr.sc.historyPointer;
			++context->sr.sc.historyPointerMinus1;
			context->sr.sc.historyIndexMinus1 = (PGPUInt16) context->sr.sc.historyPointerMinus1
									  & HISTORY_MASK;
			/*---------------------------------------*/
			/* Invalidate old pointers in hash table */
			/*---------------------------------------*/
			if (HashTableNeedsRefresh())
				RefreshOldHashEntries(context);
			/*-------------------------------------------------*/
			/*  GetAByte, update history and current byte pair */
			/*-------------------------------------------------*/
			context->sp->c_history [ (PGPUInt16) context->sr.sc.historyPointer & HISTORY_MASK ]
				= context->sr.sc.currentByte
				= *context->sr.sc.inputDataHandle++;

			context->sr.sc.currentBytePair = (context->sr.sc.currentBytePair << 8)
								  + context->sr.sc.currentByte;
			--context->sr.sc.inputDataCount;
			/*-----------------------------------*/
			/* update hash table and string list */
			/*-----------------------------------*/
			context->sr.sc.hashAddress = context->sp->hashTable
							  + GetHashFor(context->sr.sc.currentBytePair);

			/*--------------------------------------------------------*/
			/* has a previous byte pair been found with the same hash */
			/*--------------------------------------------------------*/
			if ((context->sr.sc.bytePairOffset = context->sr.sc.historyPointerMinus1
									  - *context->sr.sc.hashAddress)
									  > HISTORY_SIZE - 2)
				{
				/*----------------------------------*/
				/* no, mark the string list as empty */
				/*----------------------------------*/
				context->sp->stringList[context->sr.sc.historyIndexMinus1] = 0;
				if (context->sr.sc.stringLength != 0)
					{
					/*---------------------------------*/
					/* if currently extending a string */
					/*---------------------------------*/
					PutCompressedString(
									   context,
									   context->sr.sc.matchStringOffset,
									   context->sr.sc.stringLength
									   );
					}
				else
					{
					PutARawByte(context->sr.sc.currentBytePair >> 8);
					}
				}
					/*----------------------------------*/
			else	/* yes, a previous byte pair exists */
					/*----------------------------------*/
				{
				context->sp->stringList[context->sr.sc.historyIndexMinus1] =
					(PGPUInt16) context->sr.sc.bytePairOffset;

				/*------------------------------*/
				/* currently extending a string */
				/*------------------------------*/
				if (context->sr.sc.stringLength != 0)
					{
					if (CurrentStringExtends()
					&& ((context->sr.sc.stringLength + context->sr.sc.RLE_Length)
						 < (PGPUInt32) MAX_STRING_LENGTH))
						{
						++context->sr.sc.stringLength;
						context->event = EXTENDED_STRING;
						if (context->sr.sc.stringOutputStarted)
							{
							/*---------------------------------------------*/
							/* if string long enough to output next nibble */
							/*---------------------------------------------*/
							if (context->sr.sc.stringLength >= MIN_RLE_LENGTH)
								{
								/*--------------------*/
								/* output next nibble */
								/*--------------------*/
								PutBitsMac(
										  RLE_UNIT_LENGTH,
										  BITS_PER_RLE_UNIT
										  );
								context->sr.sc.stringLength -= RLE_UNIT_LENGTH;
								context->sr.sc.RLE_Length   += RLE_UNIT_LENGTH;
								}
							}
						/*-----------------------------------------------*/
						/* else if string is long enough to start output */
						/*-----------------------------------------------*/
						else if (context->sr.sc.stringLength >= MIN_RLE_LENGTH)
							{
							/*---------------------*/
							/* start string output */
							/*---------------------*/
							if (context->sr.sc.matchStringOffset < 128)
								{
								/*--------------*/
								/* 7 bit offset */
								/*--------------*/
								PutBitsMac(
										  0x180 | context->sr.sc.matchStringOffset,
										  9
										  );
								}
							else
								{
								/*---------------*/
								/* 11 bit offset */
								/*---------------*/
								PutBitsMac(
										  0x1000 | context->sr.sc.matchStringOffset,
										  13
										  );
								}
							/*---------------------------*/
							/* start Run Length Encoding */
							/*---------------------------*/
							PutBitsMac(RLE_UNIT_LENGTH, BITS_PER_RLE_UNIT);
							context->sr.sc.stringLength		 -= RLE_UNIT_LENGTH;
							context->sr.sc.RLE_Length	     += RLE_UNIT_LENGTH;
							context->sr.sc.stringOutputStarted = TRUE;
							}
						}
					else if (context->sr.sc.stringOutputStarted)
						{
						/*--------------------------------------------*/
						/* finish string output                       */
						/* look up the remainder of the string length */
						/*--------------------------------------------*/
						PutBitsMac(
						  lengthTable[(PGPUInt16) context->sr.sc.stringLength].pattern,
						  lengthTable[(PGPUInt16) context->sr.sc.stringLength].size
								  );
						context->sr.sc.stringLength = 0;
						context->sr.sc.RLE_Length	= 0;
						context->sr.sc.stringOutputStarted = FALSE;
						context->event = ENDED_STRING;
						}
					else if (context->sr.sc.stringLength >= REMATCH_SIZE_LIMIT)
						{
						/*---------------------------------------*/
						/* else if current string is long enough */
						/*---------------------------------------*/
						PutCompressedString( context,
											 context->sr.sc.matchStringOffset,
											 context->sr.sc.stringLength);
						}
					else
						{
						/*---------------------------*/
						/* search for a longer match */
						/*---------------------------*/
						foundLongerMatch = FALSE;
						context->sr.sc.rematchOffset = context->sr.sc.matchStringOffset;

						while ((context->sp->stringList[context->sr.sc.matchIndex] != 0)
						&& (foundLongerMatch == FALSE)
						&& (context->sr.sc.searchCount < performance)
						&& (context->sr.sc.rematchOffset < (PGPUInt16) (HISTORY_SIZE -
											 context->sr.sc.stringLength)))
						/*--------------------------------------------------*/
						/* RLE_Length does not need to be include in the	*/
						/* final condition above since rematching is not	*/
						/* allowed once Run Length Encoded string output	*/
						/* has begun. This also applies to next "if" below.	*/
						/*--------------------------------------------------*/
							{
							context->sr.sc.rematchOffset +=
								context->sp->stringList[context->sr.sc.matchIndex];
							++context->sr.sc.searchCount;
							if (context->sr.sc.rematchOffset < (PGPUInt16) (HISTORY_SIZE
												    - context->sr.sc.stringLength))
								{
								context->sr.sc.matchIndex = context->sr.sc.matchIndex
										   - context->sp->stringList[context->sr.sc.matchIndex]
										   & HISTORY_MASK;

								/*-----------------*/
								/* compare strings */
								/*-----------------*/
								if (context->sp->c_history[ context->sr.sc.matchIndex ]
								== context->sp->c_history[ context->sr.sc.currentStringIndex ])
									{
									foundLongerMatch = TRUE;
								/*------------------------------------------*/
								/* If the first bytes match then the hash	*/
								/* guarantees that the second bytes match	*/
								/* as well so we can skip ahead to the 3rd	*/
								/* byte for the rest of the comparison.		*/
								/* If the hash were unique the comparison	*/
								/* can start immediately with the 3rd bytes.*/
								/*------------------------------------------*/
									for (
										ii = 2,
										testIndex = (context->sr.sc.matchIndex+2)
												  & HISTORY_MASK;

										ii <= (PGPUInt16) context->sr.sc.stringLength;

										ii++,
										testIndex = ++testIndex & HISTORY_MASK
										)
										{
										if (context->sp->c_history[testIndex] !=
											context->sp->c_history[(context->sr.sc.currentStringIndex+ii)
																& HISTORY_MASK ])
											{
											foundLongerMatch = FALSE;
											break;
											}
										}
									}
								}
							}
						if (foundLongerMatch)
							{
							context->sr.sc.matchStringOffset = context->sr.sc.rematchOffset;
							++context->sr.sc.stringLength;
							context->event = FOUND_LONGER_MATCH;
							}
						else
							{
							/*---------------*/
							/* end of string */
							/*---------------*/
							PutCompressedString( context,
												 context->sr.sc.matchStringOffset,
												 context->sr.sc.stringLength );
							}
						}
					}
				/*------------------------------------------------------*/
				/* If the hash is non-unique then the string list must 	*/
				/* be searched here rather than assuming that the first	*/
				/* item in the string list is a match.					*/
				/*------------------------------------------------------*/
				else
					{
					/*------------------------------------*/
					/* not currently extending a string */
					/*------------------------------------*/
					context->sr.sc.firstMatchOffset = (PGPUInt16) context->sr.sc.bytePairOffset;
					context->sr.sc.searchCount = 0;

					do
						{
						context->sr.sc.matchIndex = (PGPUInt16)(context->sr.sc.historyPointerMinus1
										 - context->sr.sc.firstMatchOffset
										 & HISTORY_MASK);

						if (context->sp->c_history[context->sr.sc.matchIndex]
							 == (PGPUInt8) (context->sr.sc.currentBytePair >> 8))
							{
							/*----------------------*/
							/* set stringLength = 2 */
							/*----------------------*/
							StartNewString();
							break;
							}
						else
							{
							context->sr.sc.firstMatchOffset +=
								context->sp->stringList[context->sr.sc.matchIndex];
							++context->sr.sc.searchCount;
							}
						}
					while ((context->sp->stringList[context->sr.sc.matchIndex] != 0)
						&& (context->sr.sc.searchCount < performance)
						&& (context->sr.sc.firstMatchOffset < HISTORY_SIZE - 2));

					if (context->sr.sc.stringLength == 0)
						{
						PutARawByte(context->sr.sc.currentBytePair >> 8);
						}
					}
				}
			
#if LZS_DEBUG
			if (event == 0xFFFF)
				{
				printf("\n\nInvalid event value!!!\n");
				exit(3);
				}
#endif

			if (okToHash[context->event][context->performanceMode])
				{
				*context->sr.sc.hashAddress = context->sr.sc.historyPointerMinus1;
				}
#if LZS_DEBUG
			event = 0xFFFF;
#endif
			}
		/*---------------------------*/
		/* Process Termination Flags */
		/*---------------------------*/
		if (context->sr.sc.inputDataCount == 0)
			{
			returnValue = LZS_SOURCE_EXHAUSTED;
			if (flags & LZS_SOURCE_FLUSH)
				{
				PerformFlush(context, flags);
				returnValue |= LZS_FLUSHED;
				}
			}
		if ((context->sr.sc.outputDataCount == 0) || (context->sr.sc.destBufferFull))
			{
			if ( !(returnValue & LZS_SOURCE_EXHAUSTED) )
				{
				returnValue = LZS_DEST_EXHAUSTED;
				if (flags & LZS_DEST_FLUSH)
					{
					PerformFlush(context, flags);
					returnValue |= LZS_FLUSHED;
					}
				}
			else
				{
				returnValue |= LZS_SOURCE_DEST_EXHAUSTED;
				if ((!(flags & LZS_SOURCE_FLUSH)) && (flags & LZS_DEST_FLUSH))
					{
					PerformFlush(context, flags);
					returnValue |= LZS_FLUSHED;
					}
				}
			}
		/*-----------------------------------------------*/
		/* Remove cushion from end of destination buffer */
		/*-----------------------------------------------*/

		context->sr.sc.outputDataCount += LZS_DEST_MIN;
		}
			/*----------------------------------------------------------*/
	else	/* *destCount > LZS_DEST_MIN and context->sr.sc.inputDataCount == 0	*/
			/*----------------------------------------------------------*/
		{
		returnValue = LZS_SOURCE_EXHAUSTED;
		if (flags & LZS_SOURCE_FLUSH)
			{
			PerformFlush(context, flags);
			returnValue |= LZS_FLUSHED;
			}
		}

	/*----------------------------------------*/
	/* Update external vars with local values */
	/*----------------------------------------*/

	context->sp->sc = context->sr.sc;
	*sourceHandle	= context->sr.sc.inputDataHandle ;
	*sourceCount	= context->sr.sc.inputDataCount ;
	*destHandle		= context->sr.sc.outputDataHandle ;
	*destCount		= context->sr.sc.outputDataCount ;

	return (returnValue);
	}

	/*---------------------*/
	/* End of LZS_Compress */
	/*---------------------*/

/*

+*****************************************************************************
*
* Function Name:	InitDecompressVars
*
* Function:         Initialize decompression variables
*
* Arguments:        None.
* Globals Used:     None.
*
* Return:           None.
*
* Globals Altered:  context->sr.sd.historyIdx
*					context->sr.sd.bitAlign
*					context->sr.sd.getBitsCount
*					context->sr.sd.offset
*					context->sr.sd.getBitsResult
*					context->sr.sd.lastByteOfCompressedInput
*					context->sr.sd.sourceBits
*					context->sr.sd.length
*					context->sr.sd.decompressingAString
*					context->sr.sd.decompressState
*					context->sr.sd.decompressInitialized
*
* Error Handling:	None.
*
* Algorithms:
*
* Notes:
*
-****************************************************************************/

static void InitDecompressVars(LZSContextRef context)
	{

	/*
	Local Data Declarations:
	*/

	/*
	Body of function:
	*/

	context->sr.sd.historyIdx &= HISTORY_MASK; /* make sure history index is valid */
	context->sr.sd.bitAlign					= 
	context->sr.sd.getBitsCount				= 
	context->sr.sd.offset					= 0;	/* Offset into history */
	context->sr.sd.getBitsResult				= 
	context->sr.sd.lastByteOfCompressedInput	=
	context->sr.sd.sourceBits				= 0;
	context->sr.sd.length					= 0;	/* Length of pattern in history */
	context->sr.sd.decompressingAString		= FALSE;
	context->sr.sd.decompressState			= RAW_OR_COMPRESSED;
	context->sr.sd.decompressInitialized		= TRUE;

	return;
	}	/* InitDecompressVars */

/*

+*****************************************************************************
*
* Function Name:	GetABit
*
* Description:		Get one bit from input file
*
* Arguments:		None.
*
* Globals Used:		bitAlign
*					inputDataCount
*					inputDataHandle
*					lastByteOfCompressedInput
*
* Return:			Returns an unsigned short containing the right adjusted
*					number of bits requested.
*
* Globals Altered:	bitAlign
*					inputDataCount
*					inputDataHandle
*					lastByteOfCompressedInput
*
* Error Handling:	Returns 0 if the input buffer has been exhausted.
*					(i.e. inputDataCount == 0)
*
* Algorithms:
*
* Notes:			bitAlign keeps track of last bit used from input stream.
*					lastByteOfCompressedInput contains any unused bits from
*					the last byte read from the input buffer.
*
-****************************************************************************/

static boolean GetABit(LZSContextRef context)
	{
	if ((context->sr.sd.inputDataCount == 0) && (context->sr.sd.bitAlign == 0))
		context->sr.sd.getBitsResult = NOT_OK;
	else
		{
		context->sr.sd.getBitsResult = OK;
		/*--------------------------------------------------*/
		/* Do we need to read another byte from input file? */
		/*--------------------------------------------------*/
		if (context->sr.sd.bitAlign == 0)
			{
			/* Read the next byte from input file */
			context->sr.sd.lastByteOfCompressedInput = *context->sr.sd.inputDataHandle++;
			--context->sr.sd.inputDataCount;
			context->sr.sd.bitAlign = 7;

			/*--------------------------------------*/
			/* Store the result in the return value */
			/*--------------------------------------*/
			context->sr.sd.sourceBits
				= ((char) context->sr.sd.lastByteOfCompressedInput < 0) ? 1 : 0;


			/*--------------------------------------------------------*/
			/* Clear all bits that have already been used from 'byte' */
			/*--------------------------------------------------------*/
			context->sr.sd.lastByteOfCompressedInput &= ((PGPUInt8) 0x7F);
			}
		else
			{
			/*--------------------------------------*/
			/* Store the result in the return value */
			/*--------------------------------------*/
			context->sr.sd.sourceBits =
				(context->sr.sd.lastByteOfCompressedInput >> (context->sr.sd.bitAlign - 1));

			/*---------------------------------------------------------*/
			/* Update # of bits not yet used from the current byte     */
			/*---------------------------------------------------------*/
			--context->sr.sd.bitAlign;

			/*--------------------------------------------------------*/
			/* Clear all bits that have already been used from 'byte' */
			/*--------------------------------------------------------*/
			context->sr.sd.lastByteOfCompressedInput &=
				((PGPUInt8)0xFF >> (8 - context->sr.sd.bitAlign));
			}
		}

	return (context->sr.sd.getBitsResult);

	}	/* GetABit */

/*

+*****************************************************************************
*
* Function Name:	GetBits
*
* Description:		Get n bits from input file
*
* Arguments:		Passed via globals listed below.
*
* Globals Used:		bitAlign
*					getBitsCount
*					inputDataCount
*					inputDataHandle
*					lastByteOfCompressedInput
*
* Return:			Returns an unsigned short containing the right adjusted
*					number of bits requested.
*
* Globals Altered:	bitAlign
*					inputDataCount
*					inputDataHandle
*					lastByteOfCompressedInput
*
* Error Handling:	Returns 0 if the input buffer has been exhausted.
*					(i.e. inputDataCount == 0)
*
* Algorithms:
*
* Notes:			bitAlign keeps track of last bit used from input stream.
*					lastByteOfCompressedInput contains any unused bits from
*					the last byte read from the input buffer.
*
-****************************************************************************/

static boolean GetBits(LZSContextRef context)
	{
	/*--------------------*/
	/* Local Declarations */
	/*--------------------*/

	PGPUInt16	temp;
	PGPInt16	x;

	/*-------------------*/
	/* Body of Function */
	/*-------------------*/

	/*--------------------------------------------------------------------*/
	/* Clear the return value to zero if previous operation not suspended */
	/*--------------------------------------------------------------------*/

	if (context->sr.sd.getBitsResult == OK)
		context->sr.sd.sourceBits = 0;
	else
		context->sr.sd.getBitsResult = OK;
		
	/*-------------------------*/
	/* Get 'getBitsCount' bits */
	/*-------------------------*/
	while ((context->sr.sd.getBitsCount > 0) && (context->sr.sd.getBitsResult == OK))
		{
		if ((context->sr.sd.inputDataCount == 0) && (context->sr.sd.bitAlign == 0))
			context->sr.sd.getBitsResult = NOT_OK;
		else
			{
			/*--------------------------------------------------*/
			/* Do we need to read another byte from input file? */
			/*--------------------------------------------------*/
			if (context->sr.sd.bitAlign == 0)
				{
				/* Read the next byte from input file */
				context->sr.sd.lastByteOfCompressedInput = *context->sr.sd.inputDataHandle++;
				--context->sr.sd.inputDataCount;
				context->sr.sd.bitAlign = 8;
				}

			/*-----------------------------------*/
			/* Arrange the bits properly in temp */
			/*-----------------------------------*/
			temp = context->sr.sd.lastByteOfCompressedInput;
			if ((x = context->sr.sd.getBitsCount - context->sr.sd.bitAlign) > 0)
				temp <<= x;
			else
				temp >>= -x;

			/*--------------------------------------*/
			/* Store the result in the return value */
			/*--------------------------------------*/
			context->sr.sd.sourceBits |= temp;

			/*---------------------------------------------------------*/
			/* Update count of # of bits yet to get, and also update the
				 value of # of bits not yet used from the current byte */
			/*---------------------------------------------------------*/
			x = min(min(8, context->sr.sd.getBitsCount), context->sr.sd.bitAlign);
			context->sr.sd.getBitsCount -= x;
			context->sr.sd.bitAlign -= x;

			/*--------------------------------------------------------*/
			/* Clear all bits that have already been used from 'byte' */
			/*--------------------------------------------------------*/
			context->sr.sd.lastByteOfCompressedInput &=
				((PGPUInt8)0xFF >> (8 - context->sr.sd.bitAlign));
			}
		}

	return (context->sr.sd.getBitsResult);

	}	/* GetBits */
/*

+*****************************************************************************
*
* Function Name:	PutOutput
*
* Description:		Output byte to decompressed data buffer & update history
*
* Arguments:		c	- character to write to decompressed data buffer
*
* Globals Used:		historyIdx
*					outputDataCount
*					outputDataHandle
*
* Return:			None.
*
* Globals Altered:	d_history
*					historyIdx
*					outputDataCount
*					outputDataHandle
*
* Error Handling:	Writes no data if the decompressed buffer data count
*					has been exhausted
*
* Algorithms:
*
* Notes:
*
-****************************************************************************/

static void PutOutput(LZSContextRef context, PGPUInt8 c)
	{
	/*--------------------*/
	/* Local Declarations */
	/*--------------------*/

	/*------------------*/
	/* Body of Function */
	/*------------------*/

	/*-------------------------------------*/
	/* put the byte into the output buffer */
	/*-------------------------------------*/
	if (context->sr.sd.outputDataCount != 0)
		{
		*context->sr.sd.outputDataHandle++ = c;
		--context->sr.sd.outputDataCount;

		/*----------------*/
		/* Update history */
		/*----------------*/
		context->sp->d_history[context->sr.sd.historyIdx++] = (PGPUInt8)c;
		context->sr.sd.historyIdx &= HISTORY_MASK;
		}
	}	/* PutOutput */
/*

+*****************************************************************************
*
* Function Name:	LZS_Decompress
*
* Description:		Decompress a buffer full of data
*
* Arguments:        sourceHandle	- pointer to pointer to source buffer
*					destHandle		- pointer to pointer to destination buffer
*					sourceCount		- pointer to size in bytes of data in
*									   source buffer.
*					destCount		- pointer to size in bytes of destination
*									   buffer.
*
* Globals Used:		decompressingAString
*					decompressInitialized
*					d_history
*					historyIdx
*					lastByteOfComrpessedInput
*					length
*					offset
*
* Return:			None.
*
* Globals Altered:	decompressingAString
*					d_history
*					inputDataCount
*					inputDataHandle
*					length
*					offset
*					outputDataCount
*					outputDataHandle
*
* Error Handling:	Terminates if either source or destination counts are
*					exhausted.
*
* Algorithms:
*
* Notes:			Parses compressed data as specified by QIC-122 standard
*
-****************************************************************************/

PGPUInt16 LZS_FAR	LZS_Decompress(
							  LZSContextRef				context,
							  PGPUInt8		LZS_HANDLE 	sourceHandle,
							  PGPUInt8		LZS_HANDLE 	destHandle,
							  PGPUInt32		LZS_FAR		*sourceCount,
							  PGPUInt32		LZS_FAR		*destCount,
							  void			LZS_FAR		*scratch,
							  PGPUInt16			   		flags
							  )
{
	/*--------------------*/
	/* Local Declarations */
	/*--------------------*/

	boolean		hitEndOfCompression	= FALSE;
	PGPUInt16		returnValue = 0;

	/*------------------*/
	/* Body of Function */
	/*------------------*/

#if LZS_TARGET == LZS_INTEL_86

	/*--------------------------------------------------------------------*/
	/* Validate source and destination counts on Intel X86 platforms.     */
	/* This is necessary because far pointers are used not huge pointers. */
	/*--------------------------------------------------------------------*/

	if ((*sourceCount > 0xFFFF) || (*destCount > 0xFFFF))
		{
		return (LZS_INVALID);
		}
#endif

	/*---------------------------------------*/
	/* initialize global pointers and counts */
	/*---------------------------------------*/

	context->sp = (scratchRamType LZS_FAR *) scratch;
	context->sr.sd = context->sp->sd ;
	context->sr.sd.inputDataHandle	= *sourceHandle;
	context->sr.sd.inputDataCount  	= *sourceCount;
	context->sr.sd.outputDataHandle	= *destHandle;
	context->sr.sd.outputDataCount	= *destCount;

	if (flags & LZS_RESET)
		{
		InitDecompressVars(context);
		}

	if ((context->sr.sd.inputDataCount != 0) && (context->sr.sd.outputDataCount != 0))
		{
		/*---------------------------*/
		/* Start processing the data */
		/*---------------------------*/
		while ((context->sr.sd.outputDataCount != 0)
			&& ((context->sr.sd.inputDataCount != 0) || (context->sr.sd.bitAlign != 0))
			&& (hitEndOfCompression == FALSE))
			{
			if (context->sr.sd.decompressingAString)
				{
				while ((context->sr.sd.outputDataCount != 0) && (context->sr.sd.length > 0))
						{
						context->sr.sd.offset &= HISTORY_MASK;
						PutOutput(context, context->sp->d_history[context->sr.sd.offset++]);
						--context->sr.sd.length;
						}
				if (context->sr.sd.length == 0)
					context->sr.sd.decompressingAString = FALSE;
					context->sr.sd.decompressState = RAW_OR_COMPRESSED;
				}

			/*--------------------------------------------*/
			/* Check if next pattern is raw or compressed */
			/*--------------------------------------------*/
			else
				{
				/*----------------------*/
				/* if (GetBits(1) == 0) */
				/*----------------------*/
switch (context->sr.sd.decompressState)
	{
case RAW_OR_COMPRESSED:

				GetABit(context);
				if (context->sr.sd.sourceBits == 0)
					{
					/*---------------------*/
					/* Output the raw byte */
					/*---------------------*/
					/*------------------------*/
					/* PutOutput(GetBits(8)); */
					/*------------------------*/
					context->sr.sd.getBitsCount = 8;
					context->sr.sd.decompressState = PUTTING_RAW_BYTE;

case PUTTING_RAW_BYTE:
					GetBits(context);
					if (context->sr.sd.getBitsResult == OK)
						{
						PutOutput(context, (PGPUInt8) context->sr.sd.sourceBits);
						context->sr.sd.decompressState = RAW_OR_COMPRESSED;
						}
					}
				else
					{
					/*------------------------*/
					/* Pattern is compressed  */
					/* Get 7 or 11-bit offset */
					/*------------------------*/

					/* context->sr.sd.offset = GetBits(GetBits(1) ? 7 : 11); */

					context->sr.sd.decompressState = GETTING_OFFSET_TYPE;

case GETTING_OFFSET_TYPE:
					GetABit(context);
					if (context->sr.sd.getBitsResult == OK)
						{
						context->sr.sd.getBitsCount = context->sr.sd.sourceBits ? 7 : 11;
						context->sr.sd.decompressState = GETTING_OFFSET;
case GETTING_OFFSET:
						GetBits(context);
						if (context->sr.sd.getBitsResult == OK)
							{
							context->sr.sd.offset = context->sr.sd.sourceBits;

							/*-------------------------------------*/
							/* Check for End-of-Compression Marker */
							/*-------------------------------------*/
							if (context->sr.sd.offset == 0)
								hitEndOfCompression = TRUE;
							else
								{
								/*-----------------------------------*/
								/* its a string						 */
								/* convert offset to a history index */
								/*-----------------------------------*/
								context->sr.sd.offset = context->sr.sd.historyIdx
											 - context->sr.sd.offset;
								/*----------------------------------*/
								/* Get length of compressed pattern */
								/*----------------------------------*/
								/* context->sr.sd.length = 2 + GetBits(2); */
								context->sr.sd.getBitsCount = 2;
								context->sr.sd.decompressState = LENGTH_DIBIT_1;
case LENGTH_DIBIT_1:
								GetBits(context);
								if (context->sr.sd.getBitsResult == OK)
									{
									context->sr.sd.length = 2 + context->sr.sd.sourceBits;
									if (context->sr.sd.length == 5)
										{
										/* context->sr.sd.length += GetBits(2); */
										context->sr.sd.getBitsCount = 2;
										context->sr.sd.decompressState =LENGTH_DIBIT_2;
case LENGTH_DIBIT_2:
										GetBits(context);
										if (context->sr.sd.getBitsResult == OK)
											{
											context->sr.sd.length += context->sr.sd.sourceBits;
											if (context->sr.sd.length == 8)
												{
												/*--------------------------*/
												/* get next 4 bits of length*/
												/*--------------------------*/
												context->sr.sd.getBitsCount = 4;
												context->sr.sd.decompressState = LENGTH_NIBBLE_2;
case LENGTH_NIBBLE_2:
												GetBits(context);
												if (context->sr.sd.getBitsResult ==OK)
													{
													context->sr.sd.length += context->sr.sd.sourceBits;
													if (context->sr.sd.length == MIN_RLE_LENGTH)
														{
														do
															{
case PUT_RLE_DATA:
															while ((context->sr.sd.outputDataCount != 0)
															&&	  (context->sr.sd.length > 0))
																{
																context->sr.sd.offset &= HISTORY_MASK;
																PutOutput(context, context->sp->d_history[context->sr.sd.offset++]);
																--context->sr.sd.length;
																}
															if (context->sr.sd.outputDataCount == 0)
																{
																context->sr.sd.decompressState = PUT_RLE_DATA;
																break;
																}
															else
																{
																/*-----------------------------*/
 																/* GetBits(BITS_PER_RLE_UNIT); */
																/*-----------------------------*/
																context->sr.sd.getBitsCount = BITS_PER_RLE_UNIT;
																context->sr.sd.decompressState = RLE_BITS;
case RLE_BITS:
																GetBits(context);
																if (context->sr.sd.getBitsResult ==OK)
																	context->sr.sd.length += context->sr.sd.sourceBits;
																else
																	break;
																}
															} while (context->sr.sd.sourceBits == RLE_UNIT_LENGTH);
														}
													}
												}
											}
										}
									}
								if ((context->sr.sd.getBitsResult == OK)
								&& (context->sr.sd.decompressState != PUT_RLE_DATA))
									{
									/*-------------------------*/
									/* Output from the history */
									/*-------------------------*/
									context->sr.sd.decompressingAString = TRUE;
									}
								}
							}
						}
					}
	} /*----- end of switch statement ---------*/
				}
			}
		/*------------------------------------------------*/
		/* if ran out of source while outputting a string */
		/*------------------------------------------------*/
		if (context->sr.sd.decompressingAString)
			{
			while ((context->sr.sd.outputDataCount != 0) && (context->sr.sd.length > 0))
					{
					context->sr.sd.offset &= HISTORY_MASK;
					PutOutput(context, context->sp->d_history[context->sr.sd.offset++]);
					--context->sr.sd.length;
					}
			if (context->sr.sd.length == 0)
				context->sr.sd.decompressingAString = FALSE;
				context->sr.sd.decompressState = RAW_OR_COMPRESSED;
			}
		}

	/*------------------------*/
	/* Construct return value */
	/*------------------------*/

	if (hitEndOfCompression)
		{
		InitDecompressVars(context);
		returnValue |= LZS_END_MARKER;
		}

	if (context->sr.sd.inputDataCount == 0) /* Note bitAlign != 0 not distinguished! */
		{
		returnValue |= LZS_SOURCE_EXHAUSTED;
		}

	if (context->sr.sd.outputDataCount == 0)
		{
		returnValue |= LZS_DEST_EXHAUSTED;
		}

	context->sp->sd = context->sr.sd ;
	*sourceHandle	= context->sr.sd.inputDataHandle ;
	*sourceCount	= context->sr.sd.inputDataCount ;
	*destHandle		= context->sr.sd.outputDataHandle ;
	*destCount		= context->sr.sd.outputDataCount ;

	return (returnValue);

	}	/* LZS_Decompress */

/****************************************************************************
*							End - of - File									*
****************************************************************************/

