📄 lzsc.c
字号:
* 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);
}
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -