📄 lz77压缩算法(c语言版).mht
字号:
algorithm.<BR>*<BR>******************************************************=
***************/<BR><BR><BR>#include=20
<windows.h><BR>#include <conio.h><BR>#include=20
<stdio.h><BR>#include <assert.h><BR><BR>#define=20
OFFSET_CODING_LENGTH (10)<BR>#define =
MAX_WND_SIZE=20
1024<BR>//#define=20
MAX_WND_SIZE =20
(1<<OFFSET_CODING_LENGTH)<BR>#define =
OFFSET_MASK_CODE=20
(MAX_WND_SIZE-1)<BR><BR>const =
ULONG=20
m=3D3;<BR><BR><BR>UCHAR =20
__buffer1__[0x200000];<BR>UCHAR =20
=
__buffer2__[0x200000];<BR><BR><BR>///////////////////////////////////////=
/////////////////////////////////////////<BR><BR>void<BR>Write1ToBitStrea=
m(<BR> =20
PUCHAR pBuffer,<BR> ULONG =20
ulBitOffset<BR> )<BR>{<BR> ULONG =
=20
ulByteBoundary;<BR> ULONG =20
ulOffsetInByte;<BR><BR> ulByteBoundary =3D=20
ulBitOffset>>3 ;<BR> ulOffsetInByte =3D=20
ulBitOffset&7;<BR><BR> =
*(pBuffer+ulByteBoundary) |=3D=20
=
(1<<ulOffsetInByte);<BR>}<BR><BR>void<BR>Write0ToBitStream(<BR>&nbs=
p;=20
PUCHAR pBuffer,<BR> ULONG =20
ulBitOffset<BR> )<BR>{<BR> ULONG =
=20
ulByteBoundary;<BR> ULONG =20
ulOffsetInByte;<BR><BR> ulByteBoundary =3D=20
ulBitOffset>>3 ;<BR> ulOffsetInByte =3D=20
ulBitOffset&7;<BR><BR> =
*(pBuffer+ulByteBoundary)=20
&=3D=20
=
(~(1<<ulOffsetInByte));<BR>}<BR><BR>ULONG<BR>ReadBitFromBitStream(<=
BR> =20
PUCHAR pBuffer,<BR> ULONG =20
ulBitOffset<BR> )<BR>{<BR> ULONG =
=20
ulByteBoundary;<BR> ULONG =20
ulOffsetInByte;<BR><BR> ulByteBoundary =3D=20
ulBitOffset>>3 ;<BR> ulOffsetInByte =3D=20
ulBitOffset&7;<BR><BR> return=20
=
((*(PULONG)(pBuffer+ulByteBoundary))>>ulOffsetInByte)&1=20
;<BR>}<BR><BR><BR>ULONG WINAPI<BR>WriteGolombCode(<BR> =
ULONG x,<BR> PUCHAR=20
pBuffer,<BR> ULONG =
ulBitOffset<BR> =20
)<BR>{<BR> ULONG =
=20
q, r;<BR> int =
=20
i;<BR><BR> q =3D =
(x-1)>>m;<BR> r=20
=3D x-(q<<m)-1;<BR><BR> for(i=3D0; =
(ULONG)i<q; i++,=20
ulBitOffset++)<BR> {<BR> =20
Write1ToBitStream(pBuffer, ulBitOffset);<BR> =20
}<BR> Write0ToBitStream(pBuffer,=20
ulBitOffset);<BR> ulBitOffset++;<BR><BR> =20
for(i=3D0; i<m; i++, ulBitOffset++)<BR> =20
{<BR> if( (r>>i)&1 =
)<BR> {<BR> =
=20
Write1ToBitStream(pBuffer, =
ulBitOffset);<BR> =20
}<BR> =
else<BR> =20
{<BR> =20
Write0ToBitStream(pBuffer, ulBitOffset);<BR> =
=20
}<BR> }<BR><BR> return=20
m+q+1;<BR>}<BR><BR><BR>ULONG<BR>ReadGolombCode(<BR> =20
PULONG pulCodingLength,<BR> PUCHAR=20
pBuffer,<BR> ULONG =
ulBitOffset<BR> =20
)<BR>{<BR> ULONG q, r;<BR> =20
ULONG bit;<BR> int i;<BR><BR> =
for(q=3D0; ;q++)<BR> {<BR> =
=20
bit =3D (ULONG)ReadBitFromBitStream(pBuffer,=20
ulBitOffset);<BR> =
ulBitOffset++;<BR> =20
if( !bit )<BR> =20
{<BR> =
break;<BR> =20
}<BR> }<BR><BR><BR> =20
for(i=3D0, r=3D0; (ULONG)i<m; i++, =
ulBitOffset++)<BR> =20
{<BR> bit =3D=20
(ULONG)ReadBitFromBitStream(pBuffer, ulBitOffset);<BR> =
=20
bit <<=3D i;<BR> =
r |=3D=20
bit;<BR> }<BR><BR> *pulCodingLength =
=3D m + q=20
+ 1;<BR><BR> return=20
=
r+(q<<m)+1;<BR>}<BR><BR><BR>ULONG<BR>CompareStrings(<BR> =20
PUCHAR string1,<BR> PUCHAR=20
string2,<BR> ULONG length<BR> =
)<BR>{<BR> ULONG =
i;<BR> =20
PUCHAR p1, p2;<BR><BR> =
p1 =3D=20
string1;<BR> p2 =3D string2;<BR><BR> =
for(i=3D0;=20
i<length; i++)<BR> {<BR> =20
if( *p1=3D=3D*p2 )<BR> =
{<BR> =20
p1++;<BR> =
=20
p2++;<BR> =
}<BR> =20
else<BR> =
{<BR> =20
break;<BR> =
=20
}<BR> }<BR><BR> return=20
p1-string1;<BR>}<BR><BR><BR>void=20
WINAPI<BR>FindLongestSubstring(<BR> PUCHAR=20
pSourceString,<BR> PUCHAR =
pString,<BR> =20
ULONG ulSourceStringLength,<BR> =
PULONG=20
pulSubstringOffset,<BR> PULONG=20
pulSubstringLength<BR> )<BR>{<BR> =20
PUCHAR pSrc;<BR><BR> ULONG =
offset,=20
length;<BR><BR> ULONG =20
ulMaxLength;<BR><BR><BR> *pulSubstringOffset =3D =
offset =3D=20
0;<BR> *pulSubstringLength =3D 0;<BR><BR> =
if(=20
NULL=3D=3DpSourceString || NULL=3D=3DpString )<BR> =
{<BR> =20
return;<BR> }<BR><BR> =20
ulMaxLength =3D ulSourceStringLength;<BR> =
pSrc =3D=20
pSourceString;<BR><BR> while( ulMaxLength>0=20
)<BR> {<BR> length =3D =
CompareStrings(pSrc, pString, ulMaxLength);<BR><BR> =
=20
if( length>*pulSubstringLength )<BR> =
=20
{<BR> =20
*pulSubstringLength =3D length;<BR> =
=20
*pulSubstringOffset =3D offset;<BR> =
=20
}<BR><BR> pSrc++;<BR> =
=20
offset++;<BR> =20
ulMaxLength--;<BR> =20
=
}<BR>}<BR><BR><BR>/*<BR>void<BR>FindLongestSubstring(<BR> =20
PUCHAR pSourceString,<BR> PUCHAR=20
pString,<BR> ULONG =20
ulSourceStringLength,<BR> PULONG=20
pulSubstringOffset,<BR> PULONG=20
pulSubstringLength<BR> )<BR>{<BR> =20
PUCHAR pCurrentOffset;<BR> PUCHAR =
p1,=20
p2;<BR><BR> ULONG offset, =
length;<BR><BR> =20
pCurrentOffset =3D pSourceString;<BR><BR> =20
*pulSubstringOffset =3D offset =3D 0;<BR> =20
*pulSubstringLength =3D length =3D 0;<BR><BR> =
while(=20
pCurrentOffset<pSourceString+ulSourceStringLength =
)<BR> =20
{<BR> p1 =3D =
pCurrentOffset;<BR> =20
p2 =3D pString;<BR><BR><BR> =
=20
if( *p1=3D=3D*p2 )<BR> =
{<BR> =20
while(=20
p1<pSourceString+ulSourceStringLength && =
*p1=3D=3D*p2=20
)<BR> {<BR> =
=20
p1++;<BR> =
=20
p2++;<BR> =
=20
}<BR><BR> =
=20
length =3D p1 - pCurrentOffset;<BR> =
=20
}<BR> else<BR> =
=20
{<BR> length =
=3D=20
0;<BR> }<BR><BR> =
=20
if( length>*pulSubstringLength )<BR> =
=20
{<BR> =20
*pulSubstringLength =3D length;<BR> =
=20
*pulSubstringOffset =3D (ULONG)pCurrentOffset - =
(ULONG)pSourceString;<BR> =
}<BR><BR> =20
pCurrentOffset++;<BR> =20
}<BR>}<BR>*/<BR><BR><BR>void<BR>WriteBits(<BR> =20
PUCHAR pDataBuffer,<BR> ULONG =
ulOffsetToWrite,<BR> ULONG =
ulBits,<BR> =20
ULONG ulBitLength<BR> =
)<BR>{<BR> =20
ULONG ulDwordsOffset;<BR> ULONG =
=20
ulBitsOffset, ulBitsRemained;<BR><BR> =
ulDwordsOffset =3D=20
ulOffsetToWrite>>5;<BR> ulBitsOffset =3D=20
ulOffsetToWrite&31;<BR> ulBitsRemained =3D =
32 -=20
ulBitsOffset;<BR><BR> if( 0=3D=3DulBitsOffset =
)<BR> =20
{<BR> =20
*((PULONG)pDataBuffer+ulDwordsOffset) =3D =
ulBits;<BR> =20
}<BR> else if( =
ulBitsRemained>=3DulBitLength=20
)<BR> {<BR> =20
*((PULONG)pDataBuffer+ulDwordsOffset) |=3D=20
(ulBits<<ulBitsOffset);<BR> }<BR> =20
else<BR> {<BR> =20
*((PULONG)pDataBuffer+ulDwordsOffset) |=3D=20
(ulBits<<ulBitsOffset);<BR> =20
*((PULONG)pDataBuffer+ulDwordsOffset+1) =3D=20
ulBits>>ulBitsRemained;<BR> =20
}<BR>}<BR><BR>void<BR>ReadBits(<BR> PUCHAR =
pDataBuffer,<BR> ULONG =20
ulOffsetToRead,<BR> PULONG =
pulBits<BR> =20
)<BR>{<BR> ULONG =
ulDwordsOffset;<BR> =20
ULONG ulBitsOffset, ulBitsLength;<BR><BR> =
ulDwordsOffset =3D ulOffsetToRead>>5;<BR> =20
ulBitsOffset =3D ulOffsetToRead&31;<BR> =20
ulBitsLength =3D 32 - ulBitsOffset;<BR><BR><BR> =20
*pulBits =3D =
*((PULONG)pDataBuffer+ulDwordsOffset);<BR> =20
if( 0!=3DulBitsOffset )<BR> {<BR> =
=20
(*pulBits) >>=3D ulBitsOffset;<BR> =
=20
(*pulBits) |=3D=20
=
(*((PULONG)pDataBuffer+ulDwordsOffset+1))<<ulBitsLength;<BR> =
}<BR>}<BR><BR>void<BR>lz77compress(<BR> =
PUCHAR=20
pDataBuffer,<BR> ULONG =20
ulDataLength,<BR> PUCHAR =
pOutputBuffer,<BR> =20
PULONG pulNumberOfBits<BR> =
)<BR>{<BR> =20
LONG =
iSlideWindowPtr;<BR> =20
ULONG ulBytesCoded;<BR> =
ULONG=20
ulMaxlength;<BR> PUCHAR =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -