hippack.cpp

My (so called) HiP compression algorithm as console mode utility. It s a hybrid of Lempel-Ziv 77 a

					if ( Match.wSize < 4 )
						goto EncodeAsLiteral;
					dwSizeDec = 2;
				}
				else
				{
					if ( Match.wSize < 3 )
						goto EncodeAsLiteral;
					dwSizeDec = 1;
				}

				if ( cbDone > HP_BASE3_WIN )
					cbitBase = HP_BASE3;
				if ( cbDone > HP_BASE2_WIN )
					cbitBase = HP_BASE2;
				if ( cbDone > HP_BASE2_WIN )
					cbitBase = HP_BASE2;
				if ( cbDone > HP_BASE1_WIN )
					cbitBase = HP_BASE1;
				else 
					cbitBase = HP_INITAL_BASE;

				//
				// encode normal reference
				//

				ret  = writer->WriteBit( 1 );
				ret &= writer->WriteBit( 1 );

				/*
				if ( Match.wSize <= 5 )
					Match.dwRelOff -= ((1 << HP_SHORTREF_PTR_BIT_COUNT)+1);
				else
					Match.dwRelOff -= HP_NORMALREF_BASE;
				*/

				ret &= GammaEncodeDistance( writer, Match.dwRelOff - HP_NORMALREF_BASE, cbitBase );
//				ret &= writer->WriteBits( Match.dwRelOff - HP_NORMALREF_BASE, 13 );

				// encode size
				ret &= GammaEncodeLength( writer, Match.wSize - dwSizeDec ); // [Min2Match = 3] - 1 -> 2 (lowest for gamma encoding)
//				plhtItem = (*phuff)[ Match.wSize ];
//				ret &= writer->WriteBits( plhtItem->dwSequence, plhtItem->bySequLen );  

				_ASSERT( ret );

				cNormalRefs++;
			}
			cbDone += Match.wSize;
		}
		else
		{
EncodeAsLiteral:
			// print literal
			ret  = writer->WriteBit( HP_LITERAL_PREFIX );

			plhtItem = (*phuff)[ BUFF[cbDone] ];
			ret &= writer->WriteBits( plhtItem->dwSequence, plhtItem->bySequLen );
//			ret &= writer->WriteByte( BUFF[cbDone] );

			// adapt the Huffman tree
			phuff->m_dwOccurr[ BUFF[cbDone] ]++;
			dwHuffIteration++;
			if ( dwHuffIteration % HP_HUFF_ADAPT_ITERATION == 0 )
				phuff->GenerateWithOccurrences();

			_ASSERT( ret );

			cbDone++;
		}

		// increase the number of compressed items
		dwcItem++;
	}

#ifdef VERBOSE_PLEASE
	printf( "[  Short references: %u ]\n", cShortRefs );
	printf( "[  Normal references: %u ]\n" , cNormalRefs );
#endif

	writer->FinishWriting();

	//
	// handle output variables
	//
	*pdwcbBlock   = writer->GetWrittenByteCount() + cbHuffTree + cbHdr;
	*ppCompBlock  = pAlloc;

	bRet          = TRUE;

	//
	// tidy up
	//
TidyUp:
	if ( writer )
		delete writer;
	if ( phuff )
		delete phuff ;
//	if ( pLenHuff )
//		delete pLenHuff;
	if ( m_pbyValidHEntries )
		delete m_pbyValidHEntries;
	if ( m_pHistory )
		delete m_pHistory;

	return bRet; // OK
}

//
// Purpose:
//   Stamps the decompressed data block into a buffer
//   and returns its pointer and size
//
// Returns:
//   FALSE - not enough memory
//
BOOL HipPack::PerformDecompression( OUT void** ppCompBlock, OUT DWORD* pdwcbBlock )
{
	BYTE*           p, *pAlloc;
	DWORD           dwcbMax, cbOut, cbRef, dwDelta;
	BYTE            byChar;
	PByteReader     reader;
	LiteralHuffTree tree;
	PHIP_HEADER     pHdr;

	//
	// allocate enough memory
	//
	FreeOutBuff();
	pHdr    = (PHIP_HEADER)m_pBuff;
	dwcbMax = pHdr->cbUncompressed;
	pAlloc  = p = (PBYTE)malloc( dwcbMax );
	if ( !p )
		return FALSE; // ERR

#define BUFF ((PBYTE)m_pBuff)

	//
	// get Huffman table
	//
	DWORD cbHuffTbl;
//	cbHuffTbl = tree.RipEmittedTree(
//		BUFF + sizeof(HIP_HEADER), m_cbBuff - sizeof(HIP_HEADER) );

	tree.GenerateAdaptiveModel();
	cbHuffTbl = 0;

	//
	// Decompress !
	//
	cbOut                 = 0;
	reader                = new ByteReader(
		MakePtr( PVOID, m_pBuff, sizeof(HIP_HEADER) + cbHuffTbl ),
		m_cbBuff - sizeof(HIP_HEADER) + cbHuffTbl );
	DWORD dwHuffIteration = 0;
	while( cbOut < dwcbMax )
	{
//		if ( cbOut == 0x3b4a )
//			__asm NOP

		// firstly we read the indicator bit
		switch( reader->ReadBit() )
		{
		case HP_LITERAL_PREFIX:
			//
			// grab a literal from the compressed buffer
			//
			byChar = (BYTE)tree.QueryLiteralByBitSequence( reader );
			*p = byChar;

			// adapt the Huffman tree
			tree.m_dwOccurr[ byChar ]++;
			dwHuffIteration++;
			if ( dwHuffIteration % HP_HUFF_ADAPT_ITERATION == 0 )
				tree.GenerateWithOccurrences();

			++p;
			++cbOut;
			break;

		case HP_PTRSIZE_PREFIX:
			//
			// grab a ptr/size pair from the compressed buffer
			//
			switch( reader->ReadBit() )
			{
			case 0: // short ref
				dwDelta = reader->ReadBits( HP_SHORTREF_PTR_BIT_COUNT );
				if ( dwDelta == 0 )
				{
					//
					// decode a literal block
					//
					DWORD cb = GammaDecodeLength( reader ) - 2 + HP_MIN_LITERALS_IN_BLOCK;
					for ( UINT i = 0; i < cb; i++ )
					{
						BYTE by = reader->ReadByte();
						p[i] = by;
					}
					cbRef    = cb;
				}
				else
				{
					//
					// decode usual short reference
					//
                    cbRef   = reader->ReadBits( 2 ) + 2;				
				}
				break;

			case 1: // normal ref
				DWORD cbitBase;
				if ( cbOut > HP_BASE3_WIN )
					cbitBase = HP_BASE3;
				if ( cbOut > HP_BASE2_WIN )
					cbitBase = HP_BASE2;
				if ( cbOut > HP_BASE1_WIN )
					cbitBase = HP_BASE1;
				else 
					cbitBase = HP_INITAL_BASE;

				dwDelta = GammaDecodeDistance( reader, cbitBase ) + HP_NORMALREF_BASE;

				DWORD dwSizeInc;
				if ( dwDelta >= HP_NREF_SIZE_DEC_INDEX4 )
					dwSizeInc = 4;
				else if ( dwDelta >= HP_NREF_SIZE_DEC_INDEX3 )
					dwSizeInc = 3;
				else if ( dwDelta >= HP_NREF_SIZE_DEC_INDEX2 )
					dwSizeInc = 2;
				else
					dwSizeInc = 1;
                cbRef   = GammaDecodeLength( reader ) + dwSizeInc;
				break;
			}

			// paste the referenced bytes a P
			if ( dwDelta != 0 )
                MyMemCpy( p, (void*)((DWORD)p - dwDelta), cbRef );
			// adjust vars
			p      += cbRef;
			cbOut  += cbRef;
			break;
		}
	}

	//
	// check CRC32
	//
	DWORD dwCurCRC = CRC32::Generate( pAlloc, cbOut );
	if ( dwCurCRC != pHdr->CRC )
		printf( "!! INVALID CRC32 !!\n" );
	else
		printf( "-> CRC32 is correct...\n" );

	//
	// handle output variables
	//
	*pdwcbBlock   = cbOut;
	*ppCompBlock  = pAlloc;

	//
	// tidy up
	//
	delete reader;

	if ( m_pbyValidHEntries )
		delete [] m_pbyValidHEntries;

	return TRUE; // OK
}

//
// Purpose:
//   Returns the number of bits the specified value eats
//
// Remarks:
//   value = 0 -> 0 is returned
//
DWORD HipPack::GetBitCount( DWORD value )
{
	DWORD dwc = 0;

	while( value != 0)
	{
		++dwc;
		value >>= 1;
	}

	return dwc;
}

//
// Purpose:
//   Gamma encode a delta
//
// Remarks:
//   The delta is devided into base and high bits. The base, consisting 
//   out of 8 bit, is always emitted. Does the delta value need for
//   than 8 bit, then the rest bits, beginning at the 9th, are encoded
//   via Gamma Encoding.
//
BOOL HipPack::GammaEncodeDistance( PByteWriter writer, DWORD dwDistance, DWORD dwcBaseBits )
{
	DWORD dwBase = dwDistance & ((1 << dwcBaseBits)-1); // wipe the high value
	DWORD dwRest = dwDistance >> dwcBaseBits;

	dwRest += 2;

	if ( !GammaEncodeLength( writer, dwRest ) )
		return FALSE; // ERR
	writer->WriteBits( dwBase, dwcBaseBits );

	return TRUE; // OK
}

//
// Remarks:
//   Gamma encoding with the most significant bit omitted
//
BOOL HipPack::GammaEncodeLength( PByteWriter writer, DWORD dwLength )
{
	if ( dwLength <= 1 )
		return FALSE; // ERR

	DWORD cBits = GetBitCount( dwLength );

	dwLength = _rotr(
		dwLength,
		--cBits ); // don't handle the first bit
	BOOL bFirst = TRUE;
	while( cBits-- )
	{
		dwLength = _rotl( dwLength, 1 );
		if ( bFirst )
			bFirst = FALSE;
		else
            writer->WriteBit( 1 );
		writer->WriteBit( dwLength & 1 );
	}
	writer->WriteBit( 0 ); // stamp terminating bit

	return TRUE; // OK
}

//
// Purpose:
//   Decode Gamma encoded delta
//
DWORD HipPack::GammaDecodeDistance( PByteReader reader, DWORD dwcBaseBits )
{
	DWORD dwValue = GammaDecodeLength( reader ) - 2;

    dwValue <<= dwcBaseBits; 
	dwValue  |= reader->ReadBits( dwcBaseBits );

	return dwValue;
}

//
// Purpose:
//   Decode gamma encoded length
//
DWORD HipPack::GammaDecodeLength( PByteReader reader )
{
	DWORD  dwValue = 1; // MSB always 1

	do
	{
		dwValue <<= 1;
		dwValue  |= reader->ReadBit();
	}
	while( reader->ReadBit() != 0);

	return dwValue;
}

//
// Returns:
//   The address of the callback that was set before
//
hpCompressCallback HipPack::SetCallback( hpCompressCallback proc )
{
	hpCompressCallback  procOldCB = m_Callback;

	m_Callback = proc;

	return procOldCB;
}

//
// Purpose:
//   Returns the number of equal bytes following after each
//   other
//
DWORD HipPack::GetByteChainLength( PBYTE pby, DWORD cbMaxData )
{
	DWORD  cb = 1;
	BYTE   by = *pby++;

	while ( cb < cbMaxData && *pby == by )
	{
		cb++;
		pby++;
	}

	return cb;
}

//
// Remarks:
//   Because the memcpy runtime function performs special operations
//   when pSrc + cb > pDest - the memory regions overlap - we hold it
//   simply - thus working - and do a REP MOVSB by hand
//
void HipPack::MyMemCpy( void* pDest, const void* pSrc, DWORD cb )
{
	__asm
	{
		mov     esi, pSrc
		mov     edi, pDest
		mov     ecx, cb
		rep     movsb
	}
	return;
}

//
// Purpose:
//   Stops the compression progress what makes
//   return HipPack::PerformCompression in an error
//
void HipPack::InterruptCompression()
{
	m_bStopRun = TRUE;

	return;
}

#undef BUFF