#ident "$Id: lzsc.c,v 1.1 1995/03/16 17:08:26 garyp Exp $"
/*****************************************************************************
 * Copyright (c) 1988-95 Digi International Inc., All Rights Reserved
 * 
 * This  software  contains  proprietary  and  confidential   information   of
 * Digi International  Inc.   By  accepting  transfer  of this copy, Recipient
 * agrees to retain this software in  confidence,  to  prevent  disclosure  to
 * others,  and  to make no  use of this software other than that for which it
 * was delivered.  This is an unpublished copyright work  Digi   International
 * Inc.    Except   as   permitted   by  federal  law,  17 USC 117, copying is
 * strictly prohibited.
 * 
 * Digi  International  Inc.  CONFIDENTIAL  -   (Digi    International    Inc.
 * Confidential  when   combined   with   the   aggregated  modules  for  this
 * product) OBJECT CODE ONLY SOURCE MATERIALS
 * 
 * (C) COPYRIGHT Digi International Inc. 1995
 * 
 * All Rights Reserved
 * 
 * US   Government   Users   Restricted   Rights   -   Use,   duplication   or
 * disclosure  restricted by GSA ADP Schedule Contract with Digi International
 * Inc.
 * 
 *****************************************************************************/

/*----------------------------------------------------------------------*/
/* LZS221-C Version 4.0							*/
/*----------------------------------------------------------------------*/
/*  LZSC.C - Compress data to Lzs(TM) tokens				*/
/*                                                                      */
/*  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!	*/
/*  !!                                                              !!	*/
/*  !!  NOTE:                                                       !!	*/
/*  !!  The contents of this document constitute                    !!	*/
/*  !!           CONFIDENTIAL INFORMATION                           !!	*/
/*  !!  		(C) Stac Electronics 1994.                  !!	*/
/*  !!					                            !!	*/
/*  !!      Including one or more U.S. Patents:			    !!	*/
/*  !!		No. 4701745, 5016009, 5126739 and 5146221 and       !!	*/
/*  !!                  other pending patents.               	    !!	*/
/*  !!                                                              !!	*/
/*  !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!	*/
/*									*/
/*----------------------------------------------------------------------*/
/*									*/
/* Copyright 1988-95 Stac Electronics, Carlsbad, California.		*/
/* All rights reserved.  This code is Stac confidential property, and	*/
/* the algorithms and methods used herein may not be disclosed to any 	*/
/* party without express written consent from Stac Electronics.         */
/*                                                                      */
/*----------------------------------------------------------------------*/
/* All Stac product names are trademarks or registered trademarks	*/
/* of Stac Electronics.							*/
/*----------------------------------------------------------------------*/
#include "types.h"
#include "lzs.h"    
#define MAX_BLOCK_SIZE_TYPE long
#define SIZEOF_tOrigByteIndex 4
#define MAX_BUFFR_SIZE_TYPE long
#if defined (LZS_FAST)
#define _FAST_
#define _Small_Blocks_
#define MAX_ORIG_INDEX OrigCnt
#undef LZS_SMALL_BUFFERS
#define LZS_SMALL_BUFFERS
#endif
#if defined (_BIG_CMPRS_BFR_)
#define MAX_ORIG_CNT_FAST 57343U
#else
#define _EARLY_OUT_ 1
#define MAX_ORIG_CNT_FAST 63487U
#endif
#define MAX_INDEX	~((tOrigByteIndex) 0)
#if !defined MAX_ORIG_INDEX
#define MAX_ORIG_INDEX \
		((flags & LZS_SOURCE_FLUSH) ? OrigCnt : MAX_INDEX)
#endif
#if defined (_Small_Blocks_)
#undef MAX_BLOCK_SIZE_TYPE
#undef SIZEOF_tOrigByteIndex
#define MAX_BLOCK_SIZE_TYPE 	short
#define SIZEOF_tOrigByteIndex 	2
#endif
#if defined (LZS_SMALL_BUFFERS)
#undef MAX_BUFFR_SIZE_TYPE
#define MAX_BUFFR_SIZE_TYPE 	short
#define MAX_BUFFER_SIZE 	0xFFFFU
#endif
typedef unsigned MAX_BUFFR_SIZE_TYPE tMaxBfrSz;
typedef unsigned MAX_BLOCK_SIZE_TYPE tOrigByteIndex;
#define FP_Off(fp) fp
#define dREG
#define pREG register
#define	MEM_COPY_S(pDest, pSrc, nbytes) (mem_copy_r (pDest, pSrc, nbytes))
#define	COPY_PREV_STRING(pDest, wOffset, nbytes) \
		copy_prev_string_r (pDest, wOffset, nbytes)
#define COPY_TO_STRING_END COPY_PREV_STRING
#define	MEM_SET_S(pDest, Char, nbytes) mem_set_r (pDest, Char, nbytes)
#define	INIT_HASH_TBL(pDest, pPattern, nbytes) \
		init_hash_tbl_r (pDest, pPattern, nbytes)
#define LARGE_STR 		25U
#define RAW_TKN_SZ 		9
#define KEY_LENGTH 		2
#define MAX_OFFSET 		0x7FFU
#define CMP_SIGNATURE 		0x4321U
#define SPAN_CMPRS_BFR 		0x80
#define SPLITTING_STRING	0x40
#define SPLITTING_UNIQUE_BYTE	0x20
#define SPLITTING_ENDS		0x10
#define SPAN_ORIG_BFR		0x08
#define ORIG_BLK_START		0x04
#define ENGN_SOURCE_EXHAUSTED 	LZS_SOURCE_EXHAUSTED
#define INIT_HASH		0x02
#define NOT_ORIG_BFR		0x04
#define HASH_TBL_ENTRIES  	2003U
#define HASH_TBL_EVEN 		(HASH_TBL_ENTRIES+1)
#define MAX_LOOK_AHEAD 		4U
#define DUM_DUM_SZ 		(2U*(MAX_OFFSET)+MAX_LOOK_AHEAD)
#if !defined (LZS_FAR)
#define LZS_FAR
#endif
struct Look4Match {
	unsigned long  Token;
	unsigned long  SaveBitStream;
	unsigned char LZS_FAR * pParsePt;
	tOrigByteIndex match_list[MAX_OFFSET+1];
	tOrigByteIndex hash_tbl[HASH_TBL_EVEN];
	unsigned char LZS_FAR * pStartUb;
	tOrigByteIndex ParseNdx;
	tOrigByteIndex StartNdx;
	tOrigByteIndex BeginAgain;
	tMaxBfrSz nUnqBytes;
	tMaxBfrSz StrLen;
	unsigned short OrigBytesSaved;
	unsigned short Ret_Code;
	unsigned short CmprsBytesSaved;
	unsigned short wBestOff;
	unsigned short TokenSz;
	unsigned short AvailBits;
	unsigned short Sign;
	unsigned char  BkState;
	unsigned char  EngnState;
#if !defined (_FAST_)
	unsigned char  	PriorOrigBytes[DUM_DUM_SZ];
#endif
};
#define MAX_OVERRUN 	16U
#define DUMDUM_SZ (2*(MAX_OFFSET+1) + MAX_OVERRUN)
struct RestartData {
	tMaxBfrSz	 	len;
	unsigned short 	bits2discard;
	unsigned short 	offset;
	unsigned short	Sign;
	unsigned char	engnState;
};
struct SaveData {
	unsigned char LZS_FAR * pTinyBfrBrk;
	unsigned char LZS_FAR * pExpBfrBase;
	unsigned short	CmpByteSaved;
	unsigned short 	ExpByteSaved;
	struct RestartData restart;
	unsigned char	fState;
#if !defined (_FAST_)
	unsigned char  	SaveCmpBytes[7];
	unsigned char  	SaveExpBytes[DUMDUM_SZ];
#endif
};
#define	LZS_STOPPED_AT_TOKEN	0x01
#define	LZS_STOPPED_GETTING_LEN	0x02
#define	SPANNING_CMPRS_BFRS 	0x04
#define	LZS_OVERRUNNN		0x08
#define	TINY_EXPAND_BFR		0x10
#define	LZS_EXPANDING_STR 	0x20
#define	SAVED_CMPRS_BYTES	0x40
#define	LZS_END_OF_CMPRS_DATA	0x80
#define ENGN_STOPPED_AT_TOKEN		LZS_STOPPED_AT_TOKEN
#define	ENGN_STOPPED_GETTING_LEN	LZS_STOPPED_GETTING_LEN
#define	ENGN_PARTIAL_TOKEN		0x04
#define	ENGN_OVERRUNNN 			LZS_OVERRUNNN
#define	ENGN_EXPANDING_STR 		LZS_EXPANDING_STR
#define	ENGN_NEW_BFR             	0x40
#define	ENGN_END_OF_CMPRS_DATA		LZS_END_OF_CMPRS_DATA
unsigned int LZS_FAR Expand_Lzs_drEngine(
	unsigned char LZS_FAR * LZS_FAR	*ppCmprsBfr,
	unsigned char LZS_FAR		*pCmprsBfrEnd,
	unsigned char LZS_FAR * LZS_FAR	*ppExpBfr,
	unsigned char LZS_FAR		*pExpBfrOverEnd,
	struct RestartData LZS_FAR 	*pRestartData
);
unsigned int LZS_FAR Expand_Null_Engine(
	unsigned char LZS_FAR * LZS_FAR *ppCmprsBfr,
	unsigned char LZS_FAR		*pCmprsBfrEnd,
	unsigned char LZS_FAR * LZS_FAR *ppExpBfr,
	unsigned char LZS_FAR		*pExpBfrOverEnd,
	struct RestartData LZS_FAR 	*pRestartData
);
unsigned int LZS_FAR Compress_Lzs_drEngine(
	unsigned char LZS_FAR * LZS_FAR *ppCmprsBfr,
	unsigned char LZS_FAR		*pCmprsBfrEnd,
	unsigned char LZS_FAR * LZS_FAR *ppOrigBfr,
	unsigned char LZS_FAR	   	*pOrigEnd,
	struct Look4Match LZS_FAR  	*pWrkSpace,
	unsigned short 			 wOption,
	unsigned short			 wSearchDepth
);
void LZS_FAR LZS_InitCompressionHistory(void LZS_FAR *history);
unsigned short LZS_FAR LZS_Compress(
	unsigned char LZS_FAR * LZS_FAR *source,
	unsigned char LZS_FAR * LZS_FAR *dest,
	unsigned long LZS_FAR     	*sourceCnt,
	unsigned long LZS_FAR     	*destCnt,
	void          LZS_FAR 		*history,
	unsigned short              	 flags,
	unsigned short              	 performance
);
#ifndef	_Lzs_Mem_R_H
#define	_Lzs_Mem_R_H
 	unsigned char LZS_FAR * LZS_FAR mem_copy_r (
		void LZS_FAR * pDestn,
		void LZS_FAR * pSource,
		unsigned short wNbytes
	);
	unsigned char LZS_FAR * LZS_FAR copy_prev_string_r (
		unsigned char LZS_FAR * pDestn,
		unsigned short 	wOffset,
		tMaxBfrSz 		Nbytes
	);
 	void LZS_FAR  init_hash_tbl_r (
		void LZS_FAR * pDestn,
		void LZS_FAR * pPattern,
		unsigned short wNbytes
	);
#endif
static char copyright[] =
	"Lzs221-C version 4.0F\nCopyright 1988-95 Stac Electronics,\nCarlsbad, California.\nAll rights reserved.";
unsigned short LZS_FAR LZS_SizeOfCompressionHistory(void)
{
	return (sizeof (struct Look4Match));
}
void LZS_FAR LZS_InitCompressionHistory(
	void LZS_FAR *history	
)
{
	struct Look4Match LZS_FAR *p_temp;  
	p_temp = history ;		    
	p_temp->OrigBytesSaved = 0;
	p_temp->Sign 	       = CMP_SIGNATURE;
	p_temp->BkState        = copyright[0];
	p_temp->BkState        = INIT_HASH;
	return;
}
unsigned short LZS_FAR	LZS_Compress(
	unsigned char LZS_FAR * LZS_FAR *source,    
	unsigned char LZS_FAR * LZS_FAR *dest,      
	unsigned long LZS_FAR	        *sourceCnt, 
	unsigned long LZS_FAR	        *destCnt,   
	void          LZS_FAR           *history,   
	unsigned short 		        flags,	    
	unsigned short		        performance 
)
{
	unsigned char LZS_FAR *pParse_Pt;  
					   
	unsigned char LZS_FAR *pOrig_End;  
	unsigned char LZS_FAR *pCmprs_Bfr; 
	unsigned char LZS_FAR *pCmprsEnd;  
	unsigned long 	       Bit_Stream; 
	tOrigByteIndex 	       start_ndx;  
					   
	struct Look4Match LZS_FAR *p_temp ;
#if !defined (_FAST_)
	tOrigByteIndex	       DeltaNdx;   
#endif
	tMaxBfrSz 	       OrigCnt; 
	unsigned short	       wDataReg;   
#if !defined (_FAST_)
	unsigned short	       wDataReg3;
#endif
	unsigned short	       wDataReg2;
	unsigned short	       ret_code;   
	unsigned int	       engn_ret;
	p_temp = history ;		   
	ret_code = 0;
	if (flags & (~(  LZS_SAVE_HISTORY
			 | LZS_SOURCE_FLUSH
			 | LZS_DEST_FLUSH
			 | LZS_PERFORMANCE_MODE_1
			 | LZS_PERFORMANCE_MODE_2 ) ))
	{
		printf("LZS Fail 1.1") ;
		return (LZS_INVALID);
	}
	if ( p_temp->Sign != CMP_SIGNATURE)
	{
		printf("LZS Fail 1.2") ;
		return (LZS_INVALID);
	}

	wDataReg2 = p_temp->BkState;
	pParse_Pt = *source;
#if defined (LZS_SMALL_BUFFERS)
	
	if ((*destCnt > MAX_BUFFER_SIZE) || (*sourceCnt > MAX_BUFFER_SIZE))
	{
		printf("LZS Fail 1.3") ;
		return (LZS_INVALID);
	}
#endif
	OrigCnt = (tMaxBfrSz) *sourceCnt;	
#if defined (_FAST_)
	if (LZS_SOURCE_FLUSH != (flags & (
					      LZS_SOURCE_FLUSH
					    | LZS_SAVE_HISTORY
					    | LZS_DEST_FLUSH   )))
	{
		printf("LZS Fail 1 flags =%x ",flags) ;
		return (LZS_INVALID);
	}
	if (OrigCnt > MAX_ORIG_CNT_FAST)
	{
		printf("LZS Fail 2") ;
		return (LZS_INVALID);
	}
#endif
	if ( (*destCnt < LZS_DEST_MIN) && (!(wDataReg2 & SPAN_ORIG_BFR)) )
	{
		printf("LZS Fail 3") ;
		return (LZS_INVALID) ;
	}
	pCmprs_Bfr = *dest;
	pCmprsEnd = (tMaxBfrSz)(*destCnt - 4) + pCmprs_Bfr;
#if !defined (_FAST_)
	if (flags & LZS_DEST_FLUSH)
		pCmprsEnd -= LZS_DEST_MIN - 4;
	if (wDataReg2 & (  SPAN_CMPRS_BFR
			 | SPLITTING_STRING
			 | SPLITTING_UNIQUE_BYTE
			 | SPLITTING_ENDS )) {
		p_temp->BkState &= ~(  SPAN_CMPRS_BFR
					 | SPLITTING_STRING
					 | SPLITTING_UNIQUE_BYTE
					 | SPLITTING_ENDS);
		Bit_Stream = p_temp->SaveBitStream;
		wDataReg2 &= SPLITTING_ENDS;
		wDataReg3 = !(wDataReg2) ? 0: ((p_temp->AvailBits+2) >> 3);
		for (wDataReg = p_temp->CmprsBytesSaved;
		     wDataReg > wDataReg3;
		     wDataReg--) {
			*pCmprs_Bfr = (unsigned char)(0xFF & (unsigned char)
				(Bit_Stream >> ((wDataReg-1)<<3)));
			pCmprs_Bfr++;
		}
		OrigCnt   = (tMaxBfrSz) p_temp->BeginAgain;
		pParse_Pt = p_temp->pParsePt;  
					       
		ret_code   = p_temp->Ret_Code;
		if (wDataReg2 & SPLITTING_ENDS)
			goto Recover_From_Splitting_Ends;
		goto Restart_Compressor;
	}
#endif
	p_temp->StartNdx = p_temp->ParseNdx;
	if (OrigCnt == 0) {
		ret_code |= LZS_SOURCE_EXHAUSTED;
		goto No_Action_Exit;
	}
	if (wDataReg2 & INIT_HASH) {
		start_ndx = p_temp->ParseNdx;
		
		
		if (start_ndx > (MAX_INDEX - MAX_ORIG_INDEX) ) {
			start_ndx = 0;
			p_temp->hash_tbl[0]
#if SIZEOF_tOrigByteIndex == 2
				= p_temp->hash_tbl[1]
#endif
				= 0;
			INIT_HASH_TBL(
			  &p_temp->hash_tbl[4/(sizeof (tOrigByteIndex))],
			  &p_temp->hash_tbl[0],
			  (HASH_TBL_EVEN * (sizeof(tOrigByteIndex))) - 4);
		}
		
		
		start_ndx += MAX_OFFSET+1u;
		p_temp->StartNdx =
		p_temp->ParseNdx = start_ndx;
		p_temp->OrigBytesSaved = 0;
		p_temp->BkState = 0;
		p_temp->SaveBitStream = 0;
		p_temp->AvailBits = 32;
	}
#if !defined (_FAST_)
	else if (wDataReg2 & SPAN_ORIG_BFR) {
		p_temp->BkState &= ~SPAN_ORIG_BFR;
Insert_In_Save_Bfr:
		p_temp->BkState |= NOT_ORIG_BFR;
		wDataReg  = p_temp->OrigBytesSaved;
		if ( (wDataReg > MAX_OFFSET) &&
			((wDataReg + OrigCnt) > DUM_DUM_SZ)){
			wDataReg -= MAX_OFFSET;
			MEM_COPY_S(&p_temp->PriorOrigBytes[0],
				   &p_temp->PriorOrigBytes[wDataReg],
				   MAX_OFFSET);
			wDataReg = MAX_OFFSET;
		}
		if (OrigCnt > (DUM_DUM_SZ - wDataReg))
			
			OrigCnt = (tMaxBfrSz)(DUM_DUM_SZ - wDataReg);
		MEM_COPY_S (&p_temp->PriorOrigBytes[wDataReg],
			    pParse_Pt, (unsigned short)OrigCnt);
		pParse_Pt = &p_temp->PriorOrigBytes[wDataReg];
		p_temp->OrigBytesSaved = wDataReg + (unsigned short)OrigCnt;
	}
#endif  
	p_temp->pStartUb = pParse_Pt;
#if !defined (_FAST_)
Resume_Compressing:
#endif
	p_temp->EngnState = ORIG_BLK_START;
Restart_Compressor:
	pOrig_End = pParse_Pt + OrigCnt;
	engn_ret = Compress_Lzs_drEngine(
			&pCmprs_Bfr, pCmprsEnd,
			&pParse_Pt,  pOrig_End,
			(struct Look4Match LZS_FAR *)history,
			flags, performance );
	if (engn_ret & (  SPLITTING_UNIQUE_BYTE
			| SPAN_CMPRS_BFR
			| SPLITTING_STRING ))
		goto Save_Cmprs_Info;
	if (engn_ret & SPAN_ORIG_BFR)
		goto Span_Orig_Bfr;
	if (!(ret_code & LZS_SOURCE_EXHAUSTED)) {
#if !defined (_FAST_)
		if (p_temp->BkState & NOT_ORIG_BFR) {
			
			p_temp->BkState &= ~NOT_ORIG_BFR;
			DeltaNdx = p_temp->ParseNdx - p_temp->StartNdx;
			wDataReg  = (unsigned short)(pParse_Pt
					- p_temp->pStartUb);
				
			pParse_Pt = *source + (tMaxBfrSz)DeltaNdx ;
			p_temp->pStartUb = pParse_Pt - wDataReg;
			OrigCnt = (tMaxBfrSz) *sourceCnt
					- (tMaxBfrSz)DeltaNdx;
			if (DeltaNdx >= MAX_OFFSET) {
				
				p_temp->OrigBytesSaved = 0;
				goto Resume_Compressing;
			}
			if (OrigCnt > 4)
				goto Insert_In_Save_Bfr;
		}
#endif	
		ret_code |= LZS_SOURCE_EXHAUSTED;
		p_temp->ParseNdx = p_temp->StartNdx + (tMaxBfrSz) *sourceCnt;
		
		pParse_Pt = *source + (tMaxBfrSz) *sourceCnt;
		OrigCnt   = 0;
		
		p_temp->wBestOff  = 0;
		p_temp->StrLen 	 = 2;
		if (!(flags & LZS_SOURCE_FLUSH)) {
			
			p_temp->BkState |= SPAN_ORIG_BFR;
			
			
			p_temp->wBestOff = MAX_OFFSET;
			p_temp->StrLen 	 = 200;
		}
		goto Restart_Compressor;
			
	}
	pParse_Pt = *source + (tMaxBfrSz) *sourceCnt;
	
	wDataReg  = 4 - ((p_temp->AvailBits+2) >> 3);
	if ((pCmprs_Bfr + wDataReg) > (pCmprsEnd + 4)) {
		engn_ret =  SPLITTING_ENDS;
		goto Save_Cmprs_Info;
	}
	Bit_Stream = p_temp->SaveBitStream;
#if !defined (_FAST_)
Out_EocdToken:
#endif
	pCmprsEnd = pCmprs_Bfr + wDataReg;
	wDataReg = 3*8;
	while (pCmprs_Bfr < pCmprsEnd) {
		*pCmprs_Bfr = (unsigned char)(0xFFU & (unsigned char)
			  (Bit_Stream >> wDataReg));
		pCmprs_Bfr++;
		wDataReg -= 8;
	};
#if !defined (_FAST_)
Recover_From_Splitting_Ends:
#endif
	
	
	
	
	
No_Action_Exit:
	ret_code |= LZS_FLUSHED;
	if (flags & LZS_SAVE_HISTORY) {
		p_temp->SaveBitStream = 0;
		p_temp->AvailBits     = 32;
		goto Span_Orig_Bfr;	
	}
	if (flags & LZS_SOURCE_FLUSH) {
		p_temp->BkState |= INIT_HASH;
	}
	goto Report_Results;
	
	
Span_Orig_Bfr:
#if !defined (_FAST_)
	p_temp->BkState |= SPAN_ORIG_BFR;
	if (p_temp->OrigBytesSaved == 0) {
		wDataReg = ((tOrigByteIndex) *sourceCnt < MAX_OFFSET) ?
				(unsigned short) *sourceCnt : MAX_OFFSET;
		MEM_COPY_S(&p_temp->PriorOrigBytes[0],
			   (*source + (tMaxBfrSz)*sourceCnt) - wDataReg,
			   wDataReg);
		
		p_temp->OrigBytesSaved  = wDataReg;
	}
	p_temp->ParseNdx = p_temp->StartNdx + *sourceCnt;
	pParse_Pt = *source + (tMaxBfrSz) *sourceCnt;
	
#endif
	goto Report_Results;
	
	
	
Save_Cmprs_Info:
	p_temp->BkState  |= engn_ret;
	p_temp->Ret_Code  = ret_code;
	p_temp->pParsePt  = pParse_Pt;
	p_temp->BeginAgain = (tOrigByteIndex)(pOrig_End - pParse_Pt);
	pParse_Pt = *source;
	ret_code = LZS_DEST_EXHAUSTED;
#if defined (_FAST_)
	p_temp->BkState |= INIT_HASH;	
#else
	if (flags & LZS_DEST_FLUSH) {
		Bit_Stream = p_temp->SaveBitStream;
#if LZS_BYTE_ORDER == LZS_LITTLE_END	
		    *(pCmprs_Bfr+3) = (unsigned char) Bit_Stream;
		    
		    Bit_Stream >>= 8;
		    *(pCmprs_Bfr+2) = (unsigned char) Bit_Stream;
		    Bit_Stream >>= 8;
		    *(pCmprs_Bfr+1) = (unsigned char) Bit_Stream;
		    Bit_Stream >>= 8;
		    *pCmprs_Bfr     = (unsigned char) Bit_Stream;
#else
		    * (unsigned long *) pCmprs_Bfr = Bit_Stream;
#endif
		pCmprs_Bfr += 4;
		p_temp->AvailBits = (32 - p_temp->AvailBits);
		Bit_Stream = (p_temp->AvailBits == 0) ? 0 :
			      p_temp->Token << p_temp->AvailBits;
		if (SPLITTING_STRING & engn_ret) {	
			wDataReg2 = (p_temp->StrLen < 14) ?
				  (unsigned short)p_temp->StrLen : 14;
			p_temp->AvailBits -= 4;
			Bit_Stream |= wDataReg2 << p_temp->AvailBits;
			pParse_Pt  -= p_temp->StrLen - wDataReg2;
		}
		
		p_temp->AvailBits -= 9;
		Bit_Stream |= 0x0180 << p_temp->AvailBits;
		wDataReg = 4 - (p_temp->AvailBits >> 3);
		p_temp->BkState = INIT_HASH;
		ret_code |= LZS_FLUSHED;
		goto Out_EocdToken;
	}
	Bit_Stream = p_temp->SaveBitStream;
	wDataReg2 = (p_temp->CmprsBytesSaved =
		(unsigned short)(pCmprs_Bfr - pCmprsEnd) );
	for (wDataReg = 3; wDataReg >= wDataReg2; wDataReg--) {
		*pCmprs_Bfr = (unsigned char)(Bit_Stream >> ((wDataReg)<<3));
		pCmprs_Bfr++;
	}
#endif	
Report_Results:
	*destCnt   -= (unsigned long)(FP_Off(pCmprs_Bfr) - FP_Off(*dest));
	*dest	    = pCmprs_Bfr;
	*sourceCnt -= (unsigned long)(FP_Off(pParse_Pt) - FP_Off(*source));
	*source   = pParse_Pt;
	return (ret_code);
}
#include "lzs.h"	
unsigned int LZS_FAR Compress_Lzs_drEngine(
	unsigned char LZS_FAR * LZS_FAR *ppCmprsBfr,
	unsigned char LZS_FAR	        *pCmprsEnd,
	unsigned char LZS_FAR * LZS_FAR *ppOrigBfr,
	unsigned char LZS_FAR	        *pOrigEnd,  
	struct Look4Match LZS_FAR       *pWrkSpace,
	unsigned short 		         flags,
	unsigned short		         performance
)
{
	unsigned long		 BitStream;	
						
	dREG unsigned long 	 token;		
						
	unsigned char LZS_FAR 	*pCmprsBfr;	
	pREG unsigned char LZS_FAR   *pParsePt; 
						
						
	unsigned char LZS_FAR 	*pStartUb;  	
	pREG unsigned char LZS_FAR  *pOrigStop; 
	unsigned char LZS_FAR 	*pDi;	 	
	unsigned char LZS_FAR 	*pSi;
	pREG tOrigByteIndex	 parse_ndx;	
						
	dREG tOrigByteIndex	 match_ndx; 	
	dREG tOrigByteIndex	 Delta2Match;  	
	tOrigByteIndex		 i_ndx;	 	
	dREG tMaxBfrSz	 	 wMatchLen; 	
	dREG tMaxBfrSz 		 BytePairsLeft; 
						
	dREG tMaxBfrSz 		 nUnqBytes;
	tMaxBfrSz 		 wBestLen;	
	unsigned short		 wBestOff;	
	unsigned short		 avail_bits;	
						
	dREG unsigned short	 wMatchTried;	
#if defined (LZS_ALIGNED)
	pREG unsigned short 	 wKeyBytes1_2;
#endif
	dREG unsigned short	 wToken_size;
	unsigned short 		 x_rem;
	unsigned short		 hashTblEntries;
	unsigned int		 stopped4;	
	hashTblEntries = HASH_TBL_ENTRIES;
	performance  &= 0xFF;		
	wMatchTried    = performance;	
	pCmprsBfr = pCmprsEnd;		
	pCmprsBfr = *ppCmprsBfr;
	pParsePt  = *ppOrigBfr;
	pOrigStop = ((pOrigEnd - pParsePt) < MAX_LOOK_AHEAD) ?
		pParsePt: pOrigEnd - MAX_LOOK_AHEAD;
	token     = pWrkSpace->Token;
	BitStream = pWrkSpace->SaveBitStream;
	pStartUb  = pWrkSpace->pStartUb;
	parse_ndx = pWrkSpace->ParseNdx;
	nUnqBytes = pWrkSpace->nUnqBytes;   	
						
	wBestLen    = pWrkSpace->StrLen;
	wBestOff    = pWrkSpace->wBestOff;
	wToken_size = pWrkSpace->TokenSz;
	avail_bits  = pWrkSpace->AvailBits;
	
	if (pWrkSpace->EngnState & ORIG_BLK_START)
		goto LookUpKey;
	
	if (pWrkSpace->EngnState & ENGN_SOURCE_EXHAUSTED)
		goto Encode;
	if (pWrkSpace->EngnState & SPLITTING_UNIQUE_BYTE)
		goto Recover_From_Cmprs_Bfr_Split_Unique_Byte;
	if (pWrkSpace->EngnState & SPAN_CMPRS_BFR)
		goto Recover_From_Cmprs_Bfr_Split;
	goto Recover_From_Cmprs_Bfr_Split_String;
	
Thats_All:
	stopped4 = ENGN_SOURCE_EXHAUSTED;
Save_Cmprs_State:
	*ppOrigBfr  = pParsePt;		
	*ppCmprsBfr = pCmprsBfr;
	pWrkSpace->Token         = token;     
					      
	pWrkSpace->SaveBitStream = BitStream;
	pWrkSpace->pStartUb      = pStartUb;
	pWrkSpace->ParseNdx      = parse_ndx;
	pWrkSpace->nUnqBytes     = nUnqBytes; 
					      
	pWrkSpace->StrLen    = wBestLen;
	pWrkSpace->wBestOff  = wBestOff;
	pWrkSpace->TokenSz   = wToken_size;
	pWrkSpace->AvailBits = avail_bits;
	pWrkSpace->EngnState = (unsigned char) stopped4;
	return (stopped4);
Reset_Match_Tried:
	wMatchTried = performance;
Try_Next_Byte:
	parse_ndx++; pParsePt++;
LookUpKey:
	if (pParsePt >= pOrigStop)
		goto Thats_All;
#if !defined (LZS_ALIGNED)
	    x_rem = ((*pParsePt << 7) | *(pParsePt+1)) % hashTblEntries;
	    
#else
	    wKeyBytes1_2 = *(unsigned short LZS_FAR *) pParsePt;
	    
	    x_rem = (wKeyBytes1_2 & 0x7FFF) % hashTblEntries;
#endif
	match_ndx = pWrkSpace->hash_tbl[x_rem];
	pWrkSpace->hash_tbl[x_rem] = parse_ndx;
	pWrkSpace->match_list[(((unsigned short) parse_ndx) & MAX_OFFSET)] =
		match_ndx;
	
	if ((Delta2Match = parse_ndx - match_ndx) > MAX_OFFSET)
		goto Try_Next_Byte;
#if !defined (LZS_ALIGNED)
	    pSi = pParsePt - (unsigned short) Delta2Match;
	    if ((* pSi    != * pParsePt)  ||
		(*(pSi+1) != *(pParsePt+1)) ){	
#else
	    if (*(unsigned short LZS_FAR *)
		(pParsePt - (unsigned short) Delta2Match) != wKeyBytes1_2) {
		
#endif
		if (wMatchTried == 0)
			goto Try_Next_Byte;
Validate_Index: 
		match_ndx = pWrkSpace->match_list[(((unsigned short)
			match_ndx) & MAX_OFFSET)];
		if ((Delta2Match = parse_ndx - match_ndx) > MAX_OFFSET)
			goto Reset_Match_Tried;
#if !defined (LZS_ALIGNED)
		    pSi = pParsePt - (unsigned short) Delta2Match;
		    if ((* pSi    != * pParsePt)   ||
			(*(pSi+1) != *(pParsePt+1)) ){
			
#else
		    if (*(unsigned short LZS_FAR *)(pParsePt - (unsigned short)
			Delta2Match) != wKeyBytes1_2) {
			
#endif
			wMatchTried--;
			if (wMatchTried == 0) goto Reset_Match_Tried;
				goto Validate_Index;
		}
	}
	wBestLen = KEY_LENGTH;		
	wBestOff = (unsigned short) Delta2Match;
	wMatchTried = performance;	
	goto MatchByte3;
NextNlist:	
	match_ndx = pWrkSpace->match_list[(((unsigned short)
		match_ndx) & MAX_OFFSET)];
	Delta2Match = parse_ndx - match_ndx;
	if ((wMatchTried == 0) || (Delta2Match > MAX_OFFSET))
		goto FoundString;
	wMatchTried--;
MatchByte3:
	pSi = pParsePt - (unsigned short) Delta2Match;
	if ( (*(pParsePt+2) != *(pSi+2)) ||
#if !defined (LZS_ALIGNED)
		(*(pParsePt+1) != *(pSi+1)) ||
		( *pParsePt    !=  *pSi   )
#else
		(wKeyBytes1_2  !=
		*(unsigned short LZS_FAR *) pSi   )
#endif
		) goto NextNlist;
	wBestLen++;	
	wBestOff = (unsigned short) Delta2Match;
	
	wMatchTried = performance;	
#if !defined (LZS_ALIGNED)
	    while (
	    (*((pParsePt - (unsigned short)Delta2Match)+3) != *(pParsePt+3)) ||
	    (*((pParsePt - (unsigned short)Delta2Match)+2) != *(pParsePt+2)) ||
	    (*((pParsePt - (unsigned short)Delta2Match)+1) != *(pParsePt+1)) ||
	    ( *(pParsePt - (unsigned short)Delta2Match)    != * pParsePt  )
		) {
#else
	    while (*(unsigned long LZS_FAR *)
		(pParsePt - (unsigned short) Delta2Match) !=
			*(unsigned long LZS_FAR *) pParsePt) {
		
#endif
Next4byteMatch:
		if (wMatchTried) {
			match_ndx = pWrkSpace->match_list[(((unsigned short)
				match_ndx) & MAX_OFFSET)];
			
			Delta2Match = parse_ndx - match_ndx;
			if (Delta2Match <= MAX_OFFSET) {
				wMatchTried--;
				continue;
			}
		}
		goto FoundString;
	}
	
	
	
	
	
	
	pSi = pParsePt + 4;
	pDi = pSi - (unsigned short) Delta2Match;
	if (* pSi == * pDi) {
		pSi++;	pDi++;
		BytePairsLeft = (tMaxBfrSz)((pOrigEnd - pSi) >> 1);
		if (BytePairsLeft > LARGE_STR)
			BytePairsLeft = LARGE_STR;
		while (BytePairsLeft) {
#if !defined (LZS_ALIGNED)
			if (* pSi    != * pDi)
				break;
			if (*(pSi+1) != *(pDi+1))  {
				pSi++;	
#else
			if (*(unsigned short LZS_FAR *)pSi !=
				*(unsigned short LZS_FAR *)pDi) {
				if (*(pSi) == *(pDi)) pSi++;
					
#endif
				break;
			}
			pSi += sizeof(unsigned short);
			pDi += sizeof(unsigned short);
			BytePairsLeft--;
		}
	}
	wMatchLen = (tMaxBfrSz)(pSi - pParsePt);
	if (wMatchLen > wBestLen) {
		wBestLen = wMatchLen;	
		wBestOff = (unsigned short) Delta2Match;
	}
	if (wMatchTried--)
		goto Next4byteMatch;
FoundString:
	
	if (flags & (LZS_PERFORMANCE_MODE_1 | LZS_PERFORMANCE_MODE_2)) {
		pSi = pDi = pParsePt + (wBestLen-1);
		i_ndx = parse_ndx;
		if (wBestLen > 2) {
			if ((flags & LZS_PERFORMANCE_MODE_2) && (wBestOff>1))
				 pSi = pParsePt+1;
			else i_ndx += (wBestLen-1) - 1;
		}
		do {
			i_ndx++;
#if !defined (LZS_ALIGNED)
			    
			    x_rem = ((*pSi << 7) | *(pSi+1)) % hashTblEntries;
#else
			    x_rem = ((*(unsigned short LZS_FAR *)pSi) & 0x7FFFU) %
				hashTblEntries;
#endif
			pWrkSpace->match_list[(((unsigned short) i_ndx) &
				MAX_OFFSET)] = pWrkSpace->hash_tbl[x_rem];
			pWrkSpace->hash_tbl[x_rem] = i_ndx;
			pSi++;
		} while (pDi >= pSi);
	}
	parse_ndx += wBestLen;	
	
	
	
	
Encode:
	if ((nUnqBytes = (tMaxBfrSz)(pParsePt - pStartUb)) != 0) {
		if (nUnqBytes & 0x0001) {     
			if (avail_bits > RAW_TKN_SZ) {
				avail_bits -= RAW_TKN_SZ;
				BitStream |= ((unsigned long) *pStartUb) <<
					avail_bits;
			}
			else  {
				token = (unsigned long) *pStartUb;
				avail_bits = RAW_TKN_SZ - avail_bits;
				BitStream  |= token >> avail_bits;
				
#if defined (_EARLY_OUT_)
				    
				    
				    if (pCmprsBfr > pCmprsEnd) {
					stopped4 =  SPLITTING_UNIQUE_BYTE;
					goto Save_Cmprs_State;
				}
#endif
#if LZS_BYTE_ORDER == LZS_LITTLE_END
				    
				    *(pCmprsBfr+3) = (unsigned char)BitStream;
				    
				    BitStream >>=  8;
				    *(pCmprsBfr+2) = (unsigned char)BitStream;
				    BitStream >>=  8;
				    *(pCmprsBfr+1) = (unsigned char)BitStream;
				    BitStream >>=  8;
				    *pCmprsBfr     = (unsigned char)BitStream;
				    
#else
				*(unsigned long *) pCmprsBfr = BitStream;
#endif
				pCmprsBfr += 4;
Recover_From_Cmprs_Bfr_Split_Unique_Byte:
				avail_bits = 32 - avail_bits;
				BitStream = token << avail_bits;
				    
				if (avail_bits == 32)
				    
				    
					BitStream = 0;
			}
			pStartUb++;
		}	
			
		for (nUnqBytes >>= 1; nUnqBytes > 0; nUnqBytes--) {
			if (avail_bits > 2*RAW_TKN_SZ){
				avail_bits -= 2*RAW_TKN_SZ;
				BitStream |= ( ( ((unsigned long) *pStartUb) <<
					RAW_TKN_SZ)
					 | *(pStartUb+1) ) << avail_bits;
			}
			else {
				token = (((unsigned long) *pStartUb) <<
					RAW_TKN_SZ)
					 | *(pStartUb+1);
				avail_bits  = 2*RAW_TKN_SZ - avail_bits;
				BitStream  |= token >> avail_bits;
				
#if defined (_EARLY_OUT_)
				    
				    
				if (FP_Off(pCmprsBfr) > FP_Off(pCmprsEnd)) {
					stopped4 = SPAN_CMPRS_BFR;
					goto Save_Cmprs_State;
				}
#endif
#if LZS_BYTE_ORDER == LZS_LITTLE_END
				    
				    *(pCmprsBfr+3) = (unsigned char) BitStream;
				    
				    BitStream >>=  8;
				    *(pCmprsBfr+2) = (unsigned char) BitStream;
				    BitStream >>=  8;
				    *(pCmprsBfr+1) = (unsigned char) BitStream;
				    BitStream >>=  8;
				    *pCmprsBfr     = (unsigned char) BitStream;
				    
#else
				    *(unsigned long *) pCmprsBfr = BitStream;
#endif
				pCmprsBfr += 4;
Recover_From_Cmprs_Bfr_Split:
				avail_bits = 32 - avail_bits;
				BitStream = token << avail_bits;
				if (avail_bits == 32)
					BitStream = 0;
					
					
			}
			pStartUb += 2;
		}       
	}	
	
	
	
	
	pStartUb = (pParsePt += wBestLen);
	if (wBestOff & 0xFF80U) {
		token = wBestOff | 0x1000;	
		wToken_size = 11+2;       	
	}
	else {
		token = wBestOff | 0x0180;	
		wToken_size = 7+2;		
	}
	if (wBestLen < 5) {
		token = (token << 2) | (wBestLen-2);	
		wToken_size += 2;
		
OutToken:
		if (avail_bits > wToken_size) {
			avail_bits -= wToken_size;
			BitStream |= token << avail_bits;
		}
		else {	
			avail_bits  = wToken_size - avail_bits;
			BitStream  |= token >> avail_bits;
			
#if defined (_EARLY_OUT_)
			    
			    
			    if ( FP_Off(pCmprsBfr) > FP_Off(pCmprsEnd) ) {
				stopped4 =  SPLITTING_STRING;
				goto Save_Cmprs_State;
			}
#endif
#if LZS_BYTE_ORDER == LZS_LITTLE_END
			    
			    *(pCmprsBfr+3) = (unsigned char) BitStream;
			    
			    BitStream >>=  8;
			    *(pCmprsBfr+2) = (unsigned char) BitStream;
			    BitStream >>=  8;
			    *(pCmprsBfr+1) = (unsigned char) BitStream;
			    BitStream >>=  8;
			    *pCmprsBfr     = (unsigned char) BitStream;
			    
#else
			    *(unsigned long *) pCmprsBfr = BitStream;
#endif
			pCmprsBfr += 4;
Recover_From_Cmprs_Bfr_Split_String:
			avail_bits = 32 - avail_bits;
			BitStream = token << avail_bits;
			if (avail_bits == 32)
				BitStream = 0;
				
				
		}
		if (wBestLen > 14) {	
			wToken_size = 0;
			token = 0;
			goto moreLongString;
		}
		wMatchTried = performance;	
		goto LookUpKey;
	}
	if (wBestLen < 8) {
		token = (token << 4) | (0x000C | (wBestLen-5));
			
		wToken_size += 4;
		goto OutToken;
	}
	wBestLen += (15-8);
	do {
		token = (token << 4) | 0x000F;
		wToken_size += 4;
		if (wToken_size > 28) {
#if defined (_FAST_)
			goto OutToken;
#else
			if (!(pWrkSpace->BkState & SPAN_ORIG_BFR))
				goto OutToken;
			stopped4 = SPAN_ORIG_BFR;
			goto Save_Cmprs_State;
#endif
		}
moreLongString:
		wBestLen -= 15;
	} while (wBestLen > 14);
	token = (token << 4) | wBestLen;
	wToken_size += 4;
	goto OutToken;
}
