huffa.c

傅立叶变换和小波变换是图像压缩的重要工具。该代大戏是利用小波变换进行图像压缩。

/* #define DEBUG */

#include <crblib/inc.h>
#include <crblib/strutil.h>
#include <crblib/fileutil.h>
#include <crblib/memutil.h>
#include <crblib/lbitio.h>
#include <crblib/huffman2.h>
#include <crblib/codeutil.h>
#include <crblib/runtrans.h>
#include <crblib/huffa.h> /* for type defines */

#include <malloc.h>
#include <assert.h>

#ifdef _MSC_VER
#pragma warning(disable : 4018)
#endif

#ifdef _DEBUG
#undef assert
#define assert(x)	if( ! (x) ) __asm{ int 03 } else
#endif

/*** protos **/

#define CleanUp(exitmess) { HuffExitMess = exitmess; goto EndOfFunc; }

long MaxIn(long *Array,long Len); /* find max utility */

bool HuffArray(ubyte *RawArray,ulong RawLen,
		 ubyte *HuffArray,ulong * HuffArrayLenPtr,int Type);

bool O0HuffArray(ubyte *RawArray,ulong RawLen,
		 ubyte *HuffArray,ulong * HuffArrayLenPtr,bool CompressFlag);

bool O0HuffArrayNoBlock(ubyte *RawArray,ulong RawLen,
							 ubyte *HuffArray,ulong * HuffArrayLenPtr,bool CompressFlag);

bool O0HuffArrayBII_RT(ubyte *rawArray,ulong rawLen,struct LBitIOInfo * BII,bool cFlag);
bool O0HuffArrayBII(ubyte *RawArray,ulong RawLen,struct LBitIOInfo * BII,bool CompressFlag);
bool O0HuffArrayBII_block(ubyte *RawArray,ulong RawLen,struct LBitIOInfo * BII,bool CompressFlag);
bool O0HuffArrayBII_noblock(ubyte *RawArray,ulong RawLen,struct LBitIOInfo * BII,bool CompressFlag);

bool O1HuffArray(ubyte *RawArray,ulong RawLen,
							 ubyte *HuffArray,ulong * HuffArrayLenPtr,bool CompressFlag);

/*********************** choose order 0 or 1 or raw ***********/

bool HuffArray(ubyte *RawArray,ulong RawLen,
		 ubyte *HuffArray,ulong * HuffArrayLenPtr,int Type)
{
char * HuffExitMess = 0;

if ( RawLen == 0 ) return true;

if ( Type == HUFFA_TYPE_BEST )
	{
	ubyte *TypePtr;
	ulong BestLen,CurLen;

	TypePtr = HuffArray++;

	Type = HUFFA_TYPE_NONE;
	BestLen = RawLen;

	if ( ! O0HuffArray(RawArray,RawLen,HuffArray,&CurLen,TRUE) ) return(0);

	if ( CurLen < BestLen ) { BestLen = CurLen; Type = HUFFA_TYPE_O0; }

	if ( ! O0HuffArrayNoBlock(RawArray,RawLen,HuffArray,&CurLen,TRUE) ) return(0);

	if ( CurLen < BestLen ) { BestLen = CurLen; Type = HUFFA_TYPE_O0NB; }

	if ( ! O1HuffArray(RawArray,RawLen,HuffArray,&CurLen,TRUE) ) return(0);
	
	if ( CurLen < BestLen ) { BestLen = CurLen; Type = HUFFA_TYPE_O1; }

	if ( Type == HUFFA_TYPE_O1 ) { } /* done */
	else if ( Type == HUFFA_TYPE_O0 )
		{
		if ( ! O0HuffArray(RawArray,RawLen,HuffArray,&CurLen,1) ) return(0);
		}
	else if ( Type == HUFFA_TYPE_NONE )
		{
		memcpy(HuffArray,RawArray,RawLen);
		CurLen = RawLen;
		}

	*TypePtr = Type;
	*HuffArrayLenPtr = CurLen+1;
	}
else
	{
	bool success=FALSE,CompressFlag;

	if ( Type == HUFFA_TYPE_DEC )
		CompressFlag = FALSE;
	else
		CompressFlag = TRUE;

	if ( CompressFlag )
		*HuffArray++ = Type;
	else
		Type = *HuffArray++;

	switch(Type)
		{
		case HUFFA_TYPE_O1:
			success = O1HuffArray(RawArray,RawLen,HuffArray,HuffArrayLenPtr,CompressFlag);
			break;
		case HUFFA_TYPE_O0:
			success = O0HuffArray(RawArray,RawLen,HuffArray,HuffArrayLenPtr,CompressFlag);
			break;
		case HUFFA_TYPE_O0NB:
			success = O0HuffArrayNoBlock(RawArray,RawLen,HuffArray,HuffArrayLenPtr,CompressFlag);
			break;
		case HUFFA_TYPE_NONE:
			if ( CompressFlag )
				{
				memcpy(HuffArray,RawArray,RawLen);
				*HuffArrayLenPtr = RawLen;
				}
			else
				memcpy(RawArray,HuffArray,RawLen);
			success = TRUE;
			break;
		default:
			CleanUp("Got invalid type flag");
			break;	
		}

	if ( CompressFlag )
		*HuffArrayLenPtr = (*HuffArrayLenPtr) + 1;
	
	return(success);
	}

EndOfFunc:

if ( HuffExitMess )
  {
  errputs(HuffExitMess);
  return(FALSE);
  }
else
  {
  return(TRUE);
  }
}

/************** Order 0 ******************/

#define HUFF_MINLEN 8

bool O0HuffArray(ubyte *RawArray,ulong RawLen,
							 ubyte *HuffArray,ulong * HuffArrayLenPtr,bool CompressFlag)
{
struct LBitIOInfo * BII;
bool ret;

if ( RawLen == 0 ) return true;

if ( (BII = LBitIO_Init(HuffArray)) == NULL )
	{ errputs("LBitIO_Init failed!"); return(0); }

if ( ! CompressFlag )
	{
	LBitIO_InitRead(BII);
	ret = O0HuffArrayBII(RawArray,RawLen,BII,CompressFlag);
	}
else
	{
	ret = O0HuffArrayBII(RawArray,RawLen,BII,CompressFlag);
	*HuffArrayLenPtr = LBitIO_FlushWrite(BII);
	}

LBitIO_CleanUp(BII);

return(ret);
}

bool O0HuffArrayNoBlock(ubyte *RawArray,ulong RawLen,
							 ubyte *HuffArray,ulong * HuffArrayLenPtr,bool CompressFlag)
{
struct LBitIOInfo * BII;
bool ret;

if ( RawLen == 0 ) return true;

if ( (BII = LBitIO_Init(HuffArray)) == NULL )
	{ errputs("LBitIO_Init failed!"); return(0); }

if ( ! CompressFlag )
	{
	LBitIO_InitRead(BII);
	ret = O0HuffArrayBII_noblock(RawArray,RawLen,BII,CompressFlag);
	}
else
	{
	ret = O0HuffArrayBII_noblock(RawArray,RawLen,BII,CompressFlag);
	*HuffArrayLenPtr = LBitIO_FlushWrite(BII);
	}

LBitIO_CleanUp(BII);

return(ret);
}

/** kind of a cheezy way to do the _RT **/

bool O0HuffArrayBII_RT(ubyte *rawArray,ulong rawLen,struct LBitIOInfo * BII,bool cFlag)
{
ubyte *runArray;
ulong runLen;
bool ret;

	if ( (runArray = malloc(rawLen + (rawLen>>3) + 1024)) == NULL )
		return false;

	if ( cFlag ) {
		runLen = doRunTransform(rawArray,rawLen,runArray);
		if ( runLen < rawLen ) {
			LBitIO_WriteBit(BII,1);
			cu_putExpanding_bii(runLen,BII,14,4);
			ret = O0HuffArrayBII(runArray,runLen,BII,cFlag);
		} else {
			LBitIO_WriteBit(BII,0);
			ret = O0HuffArrayBII(rawArray,rawLen,BII,cFlag);
		}
	} else {
		bool doRT;
		LBitIO_ReadBit(BII,doRT);
		if ( doRT ) {
			runLen = cu_getExpanding_bii(BII,14,4);
			ret = O0HuffArrayBII(runArray,runLen,BII,cFlag);
			unRunTransform(rawArray,rawLen,runArray);
		} else {
			ret = O0HuffArrayBII(rawArray,rawLen,BII,cFlag);
		}
	}

	free(runArray);

return ret;
}

#define DOBLOCK_MINLEN 1024
#define DOBLOCK_DIVISOR 4

bool O0HuffArrayBII(ubyte *RawArray,ulong RawLen,struct LBitIOInfo * BII,bool CompressFlag)
{

if ( RawLen == 0 ) return true;

if ( RawLen < DOBLOCK_MINLEN )
	{
	return( O0HuffArrayBII_noblock(RawArray,RawLen,BII,CompressFlag) );
	}
else
	{
	bool doblock=0;

	if ( CompressFlag )
		{
		long MaxCount,i;
		long * CharCounts = NULL;

		if ( (CharCounts = malloc(256*sizeof(long))) == NULL )
			{ errputs("AllocMem failed!"); return(0); }

		MemClear(CharCounts,256*sizeof(long));
		for(i=0;i<RawLen;i++) CharCounts[RawArray[i]] ++;
		MaxCount = CharCounts[MaxIn(CharCounts,256)];
		free(CharCounts);

		if ( (MaxCount*DOBLOCK_DIVISOR) >= RawLen ) doblock = 1;
		else doblock = 0;
		}

	if ( CompressFlag )	{	LBitIO_WriteBit(BII,doblock);	}
	else { LBitIO_ReadBit(BII,doblock); }

	if ( doblock ) return( O0HuffArrayBII_block(RawArray,RawLen,BII,CompressFlag) );
	else return( O0HuffArrayBII_noblock(RawArray,RawLen,BII,CompressFlag) );
	}

return(0);
}

/** this is the core routine of it all, the only one that
		actually does huffman: **/

bool O0HuffArrayBII_noblock(ubyte *RawArray,ulong RawLen,struct LBitIOInfo * BII,bool CompressFlag)
{
struct Huff2Info * HI = NULL;
long * CharCounts = NULL;
char * HuffExitMess = NULL;

if ( RawLen == 0 ) return true;

#ifdef DEBUG
if ( CompressFlag )
	{
	LBitIO_WriteBits(BII,0xD,5);
	}
else
	{
	int test;
	LBitIO_ReadBits(BII,test,5);
	if ( test != 0xD ) { errputs("o0noblock:init:didn't get tag"); return(0); }
	}
#endif

if ( RawLen < HUFF_MINLEN )
	{
	if ( CompressFlag )
		{
		while(RawLen--)
			{
			LBitIO_WriteBits(BII,*RawArray,8); RawArray++;
			}
		}
	else
		{
		while(RawLen--)
			{
			LBitIO_ReadBits(BII,*RawArray,8); RawArray++;
			}
		}
	return(1);
	}

if ( (HI = Huff2_Init(256,BII,HUFF2_SORT_RADIX)) == NULL )
	CleanUp("Huff2_Init failed!");

if ( ! CompressFlag )
	{
	Huff2_UnPackCodeLens(HI);
	Huff2_BuildFastDecodeTable(HI);
	Huff2_FastDecodeArray_Ubyte(HI,RawArray,RawLen);
  }
else //Encode
	{
	long i;

	if ( (CharCounts = malloc(256*sizeof(long))) == NULL )
		CleanUp("AllocMem failed!");

	MemClear(CharCounts,256*sizeof(long));
	for(i=0;i<RawLen;i++) CharCounts[RawArray[i]] ++;

	Huff2_ScaleCounts(HI,CharCounts,256);
	Huff2_BuildCodeLens(HI,CharCounts);
	Huff2_PackCodeLens(HI);
	Huff2_BuildEncodeTable(HI);

	Huff2_EncodeC_Macro_Init(HI);
	for(i=0;i<RawLen;i++)
		{
		Huff2_EncodeC_Macro(HI,RawArray[i]);
		}
	Huff2_EncodeC_Macro_Done(HI);

  }

CleanUp(NULL);

EndOfFunc:

#ifdef DEBUG
if ( CompressFlag )
	{
	LBitIO_WriteBits(BII,0xD,5);
	}
else
	{
	int test;
	LBitIO_ReadBits(BII,test,5);
	if ( test != 0xD ) { errputs("O0noblock:EOF:didn't get tag"); }
	}
#endif

smartfree(CharCounts);
if ( HI ) Huff2_CleanUp(HI);

if ( HuffExitMess )
  {
  errputs(HuffExitMess);
  return(FALSE);
  }
else
  {
  return(TRUE);
  }
}

bool O0HuffArrayBII_block(ubyte *RawArray,ulong RawLen,struct LBitIOInfo * BII,bool CompressFlag)
{
long * CharCounts = NULL;
char * HuffExitMess = NULL;
ubyte * BlockArray = NULL;
ubyte * LitArray = NULL;
ulong BlockLen,NumLits;
ubyte MPS0,MPS1,MPS2;

if ( RawLen == 0 ) return true;

BlockLen = ((RawLen-1)/4) + 1;
if ( (BlockArray = malloc(BlockLen)) == NULL )
	CleanUp("block malloc failed");

if ( ! CompressFlag )
	{