www.pudn.com > LZ77.rar > LZ77.cpp

#include "stdafx.h" 
#include "lz77.h" 
#include  
#include  
#include  
 
const ULONG     m=3; 
 
UCHAR   __buffer1__[0x200000]; 
UCHAR   __buffer2__[0x200000]; 
void 
Write1ToBitStream( 
   PUCHAR  pBuffer, 
   ULONG   ulBitOffset 
   ) 
{ 
   ULONG   ulByteBoundary; 
   ULONG   ulOffsetInByte; 
 
   ulByteBoundary = ulBitOffset>>3 ; 
   ulOffsetInByte = ulBitOffset&7; 
 
   *(pBuffer+ulByteBoundary) |= (1<>3 ; 
   ulOffsetInByte = ulBitOffset&7; 
 
   *(pBuffer+ulByteBoundary) &= (~(1<>3 ; 
   ulOffsetInByte = ulBitOffset&7; 
 
   return ((*(PULONG)(pBuffer+ulByteBoundary))>>ulOffsetInByte)&1 ; 
} 
 
 
ULONG WINAPI 
WriteGolombCode( 
   ULONG   x, 
   PUCHAR  pBuffer, 
   ULONG   ulBitOffset 
   ) 
{ 
   ULONG           q, r; 
   int             i; 
 
   q = (x-1)>>m; 
   r = x-(q<>i)&1 ) 
       { 
           Write1ToBitStream(pBuffer, ulBitOffset); 
       } 
       else 
       { 
           Write0ToBitStream(pBuffer, ulBitOffset); 
       } 
   } 
 
   return m+q+1; 
} 
 
 
ULONG 
ReadGolombCode( 
   PULONG  pulCodingLength, 
   PUCHAR  pBuffer, 
   ULONG   ulBitOffset 
   ) 
{ 
   ULONG   q, r; 
   ULONG   bit; 
   int i; 
 
   for(q=0; ;q++) 
   { 
       bit = (ULONG)ReadBitFromBitStream(pBuffer, ulBitOffset); 
       ulBitOffset++; 
       if( !bit ) 
       { 
           break; 
       } 
   } 
 
 
   for(i=0, r=0; (ULONG)i0 ) 
   { 
       length = CompareStrings(pSrc, pString, ulMaxLength); 
 
       if( length>*pulSubstringLength ) 
       { 
           *pulSubstringLength = length; 
           *pulSubstringOffset = offset; 
       } 
 
       pSrc++; 
       offset++; 
       ulMaxLength--; 
   } 
} 
 
void 
WriteBits( 
   PUCHAR  pDataBuffer, 
   ULONG   ulOffsetToWrite, 
   ULONG   ulBits, 
   ULONG   ulBitLength 
   ) 
{ 
   ULONG   ulDwordsOffset; 
   ULONG   ulBitsOffset, ulBitsRemained; 
 
   ulDwordsOffset = ulOffsetToWrite>>5; 
   ulBitsOffset = ulOffsetToWrite&31; 
   ulBitsRemained = 32 - ulBitsOffset; 
 
   if( 0==ulBitsOffset ) 
   { 
       *((PULONG)pDataBuffer+ulDwordsOffset) = ulBits; 
   } 
   else if( ulBitsRemained>=ulBitLength ) 
   { 
       *((PULONG)pDataBuffer+ulDwordsOffset) |= (ulBits<>ulBitsRemained; 
   } 
} 
 
void 
ReadBits( 
   PUCHAR  pDataBuffer, 
   ULONG   ulOffsetToRead, 
   PULONG  pulBits 
   ) 
{ 
   ULONG   ulDwordsOffset; 
   ULONG   ulBitsOffset, ulBitsLength; 
 
   ulDwordsOffset = ulOffsetToRead>>5; 
   ulBitsOffset = ulOffsetToRead&31; 
   ulBitsLength = 32 - ulBitsOffset; 
 
 
   *pulBits = *((PULONG)pDataBuffer+ulDwordsOffset); 
   if( 0!=ulBitsOffset ) 
   { 
       (*pulBits) >>= ulBitsOffset; 
       (*pulBits) |= (*((PULONG)pDataBuffer+ulDwordsOffset+1))<=0 ) 
       { 
           pSlideWindowPtr = pDataBuffer+iSlideWindowPtr; 
           ulMaxlength = MAX_WND_SIZE; 
 
       } 
       else if( iSlideWindowPtr>=-MAX_WND_SIZE ) 
       { 
           pSlideWindowPtr = pDataBuffer; 
           ulMaxlength = MAX_WND_SIZE + iSlideWindowPtr; 
       } 
       else 
       { 
           pSlideWindowPtr = NULL; 
           ulMaxlength = 0; 
       } 
 
       pUnprocessedDataPtr = pDataBuffer + ulBytesCoded; 
       if( ulMaxlength>ulDataLength-ulBytesCoded ) 
       { 
           ulMaxlength = ulDataLength-ulBytesCoded; 
       } 
 
       FindLongestSubstring( 
           pSlideWindowPtr, 
           pUnprocessedDataPtr, 
           ulMaxlength, 
           &offset, 
           &length 
           ); 
 
       assert( length<=MAX_WND_SIZE ); 
       assert( offset1) 
       { 
 
           Write1ToBitStream(pOutputBuffer, ulBitOffset); 
           ulBitOffset++; 
 
           for(i=0; i>i)&1 ) 
               { 
                   Write1ToBitStream(pOutputBuffer, ulBitOffset); 
               } 
               else 
               { 
                   Write0ToBitStream(pOutputBuffer, ulBitOffset); 
               } 
           } 
 
           ulCodingLength = WriteGolombCode(length, pOutputBuffer, ulBitOffset); 
 
           ulBitOffset += ulCodingLength; 
           iSlideWindowPtr += length; 
           ulBytesCoded += length; 
 
       } 
       else 
       { 
           Write0ToBitStream(pOutputBuffer, ulBitOffset); 
           ulBitOffset++; 
 
           cc = (*pUnprocessedDataPtr); 
           for(i=0; i<8; i++, ulBitOffset++) 
           { 
               if( (cc>>i)&1 ) 
               { 
                   Write1ToBitStream(pOutputBuffer, ulBitOffset); 
               } 
               else 
               { 
                   Write0ToBitStream(pOutputBuffer, ulBitOffset); 
               } 
           } 
 
           iSlideWindowPtr++; 
           ulBytesCoded++; 
       } 
 
   } 
 
   if( ulBytesCoded!=ulDataLength ) 
   { 
       assert(ulBytesCoded==ulDataLength); 
   } 
 
   *pulNumberOfBits = ulBitOffset; 
 
} 
 
void lz77decompress( 
   PUCHAR  pDataBuffer, 
   ULONG   ulNumberOfBits, 
   PUCHAR  pOutputBuffer, 
   PULONG  pulNumberOfBytes 
   ) 
{ 
   LONG        iSlideWindowPtr; 
   PUCHAR      pSlideWindowPtr; 
 
   ULONG   length, offset; 
   ULONG   bit; 
   UCHAR   cc; 
   int     i; 
 
   ULONG   ulBytesDecoded; 
   ULONG   ulBitOffset; 
 
   ULONG   ulCodingLength; 
   PUCHAR  pWrite; 
 
   iSlideWindowPtr = -MAX_WND_SIZE; 
   pWrite = (PUCHAR)pOutputBuffer; 
   ulBitOffset = 0; 
   ulBytesDecoded = 0; 
 
 
   while( ulBitOffset=0 ) 
           { 
               pSlideWindowPtr = pOutputBuffer + iSlideWindowPtr; 
 
           } 
           else if( iSlideWindowPtr>=-MAX_WND_SIZE ) 
           { 
               pSlideWindowPtr = pOutputBuffer; 
           } 
           else 
           { 
               pSlideWindowPtr = NULL; 
           } 
 
 
           for(i=0, offset=0; iMAX_WND_SIZE ) 
           { 
               assert(length<=MAX_WND_SIZE); 
           } 
           ulBitOffset += ulCodingLength; 
 
           RtlMoveMemory(pWrite, pSlideWindowPtr+offset, length); 
           pWrite+=length; 
           iSlideWindowPtr+=length; 
           ulBytesDecoded+=length; 
       } 
       else 
       { 
           for(i=0, cc=0; i<8 ; i++, ulBitOffset++) 
           { 
               bit = ReadBitFromBitStream(pDataBuffer, ulBitOffset); 
               cc |= ((UCHAR)bit<>3); 
 
		fp1=fopen(savepath, "wb+"); 
		if( !fp1 ) 
		{ 
			if( fp ) 
			{ 
				fclose(fp); 
			} 
			return -1; 
		} 
		int len; 
		BYTE extlen; 
		char ext[10]; 
		GetFileExt(filename,len,ext); 
		extlen=(BYTE)len; 
		fwrite(&extlen,1,sizeof(BYTE),fp1); 
		fwrite(ext,1,extlen,fp1); 
		fwrite(&ulNumberOfBits,1,sizeof(ULONG),fp1); 
		fwrite(__buffer2__, 1, ulFileCompressedSize, fp1); 
		fclose(fp1); 
	} 
	else 
	{ 
		BYTE extlen; 
		char ext[10]; 
		fread(&extlen,1,sizeof(BYTE),fp); 
		fread(ext,1,(int)extlen*sizeof(char),fp); 
		fread(&ulNumberOfBits,1,sizeof(ULONG),fp); 
		fread(__buffer2__,1,fsize,fp); 
		lz77decompress(__buffer2__, ulNumberOfBits, __buffer1__, &ulFileDecompressedSize); 
		fp1=fopen(savepath, "wb+"); 
		if( !fp1 ) 
		{ 
			if( fp ) 
			{ 
				fclose(fp); 
			} 
			return -1; 
		} 
		fwrite(__buffer1__, 1, ulFileDecompressedSize, fp1); 
		fclose(fp1); 
	} 
	fclose(fp); 
    return 0; 
} 
void GetFileExt(LPTSTR lpszFileName,int &cExtLen,char *szFileExt) 
{ 
	CString temp(lpszFileName); 
	int pos=temp.ReverseFind('.')+1; 
	cExtLen=(temp.GetLength()-pos); 
	strcpy(szFileExt,temp.Right(cExtLen).GetBuffer(0)); 
}