www.pudn.com > huffman2 > huffman2.h
#ifndef HUFFMAN2_H #define HUFFMAN2_H /* * Modular Static Huffman Routines * * These routines do no file IO. They write to and from a LLBitIO structure. * this structure must be independently allocated and freed * * You are responsible for calling * LBitIO_FlushWrite(HI->BII); * yourself. It is no longer done in EncodeCDone * * You must also call * LBitIO_InitRead(HI->BII); * yourself before doing any reads. It is no longer done in DecodeCInit * * * Notez: * Huff2_BuildCodeLens changes the values in the CharCounts table! * */ /* * notez : you must PackCodeLens BEFORE BuildEncodeTable * in order to set Min & Max CodeLen * if you don't PackCodeLens, call SetMinMaxCodeLen */ /* * * return values for BuildCodeLens : * 1 = all ok * 0 = error * -1 = GotNumSymbols < 2 , don't do Huffman ! * */ /* * WARNING : * * do not call Huff2_BuildFastDecodeTable & * Huff2_BuildDecodeTable both on the same Huff2Info ! * * they use the same memory space, and they use it differently! * * you will crash when Huff2_CleanUp is called ! * */ #include#include struct Huff2CodeNode { uword Char; uword Count; struct Huff2CodeNode * Up; struct Huff2CodeNode * Down; }; #define HUFF2_CODE_BRANCH 0xFFFF #define FD_MAXCHARSMADE 4 #define FD_MAXCHARSMADE_SUBONE 3 /* see ' !<>! ' marker */ struct Huff2Info { long NumSymbols; struct LBitIOInfo * BII; long MinCodeLen,MaxCodeLen; ulong * CodePrefixByLen; long * NumCodesOfLen; long * CodeLenTable; void * EnDe_codeTable; long EnDe_codeTableLen; /* FastDecode buffer */ long NumCharsWaiting; uword CharsWaiting[FD_MAXCHARSMADE_SUBONE]; /* BuildCodeLen stuff */ struct Huff2CodeNode * NodeBase; struct Huff2CodeNode ** NodeWork; struct Huff2CodeNode ** MadeNodeWork; struct Huff2CodeNode * CodeNodeHunk; long CodeNodeHunkI; ulong * StackArray; long SortType; void * SortWork; long MaxCharCount; }; struct FastDecodeItem { ubyte NumBitsUsed; ubyte NumCharsMade; uword CharsMade[FD_MAXCHARSMADE]; }; #define HUFF2_SORT_NONE 1 // data must be pre-sorted ! #define HUFF2_SORT_RADIX 2 #define HUFF2_SORT_QSORT 3 //protos: extern struct Huff2Info * Huff2_Init(long NumSymbols,struct LBitIOInfo * BII,long SortType); extern void Huff2_CleanUp(struct Huff2Info *HI); extern void Huff2_GetMaxCharCount(struct Huff2Info *HI,long * CharCounts); extern void Huff2_ScaleCounts(struct Huff2Info *HI,long * CharCounts,long MaxVal); extern bool Huff2_BuildCodeLens(struct Huff2Info *HI,long *CharCounts); extern long Huff2_BuildEncodeTable(struct Huff2Info *HI); extern bool Huff2_BuildDecodeTable(struct Huff2Info *HI); extern bool Huff2_BuildFastDecodeTable(struct Huff2Info *HI); extern void Huff2_EncodeC(struct Huff2Info *HI,uword C); extern uword Huff2_DecodeC(struct Huff2Info *HI); extern uword Huff2_FastDecodeC(struct Huff2Info *HI); extern bool Huff2_FastDecodeArray_Ubyte(struct Huff2Info *HI,ubyte * Array,long ArrayLen); extern void Huff2_SetMinMaxCodeLen(struct Huff2Info *HI); extern void Huff2_PackCodeLens(struct Huff2Info *HI); extern void Huff2_UnPackCodeLens(struct Huff2Info *HI); extern void Huff2_PackCodeLens_Delta(struct Huff2Info *HI,long * LastCodeLens); extern void Huff2_UnPackCodeLens_Delta(struct Huff2Info *HI,long * LastCodeLens); /* * macros for faster operation * */ /********** EncodeC macros ************/ #define Huff2_EncodeC_Macro_Init(HI) \ { \ register ulong * CharToCodeTable; \ register long * CodeLenTable; \ register struct LBitIOInfo * BII; \ register ulong CurCode; \ register long CurCodeLen; \ BII = HI->BII; \ CodeLenTable = HI->CodeLenTable; \ CharToCodeTable = (ulong *)HI->EnDe_codeTable; \ /* end Huff2_EncodeC_Macro_Init */ #define Huff2_EncodeC_Macro_Done(HI) \ } \ /* end Huff2_EncodeC_Macro_Done */ #define Huff2_EncodeC_Macro(HI,Symbol) \ CurCode = CharToCodeTable[Symbol]; \ CurCodeLen = CodeLenTable[Symbol]; \ LBitIO_WriteBits(BII,CurCode,CurCodeLen); \ /* end Huff2_EncodeC_Macro */ /********** end EncodeC macros ************/ /********** DecodeC macros ************/ #define Huff2_DecodeC_Macro_Init(HI) \ { \ register struct LBitIOInfo * BII; \ register ulong CurCode; \ long NumSymbols; \ uword * DecodeTable; \ ulong * CodePrefixByLen; \ ulong PackedCode; \ long CurCodeLen,MinCodeLen; \ bool bit; \ \ BII = HI->BII; \ NumSymbols = HI->NumSymbols; \ DecodeTable = (uword *) HI->EnDe_codeTable; \ CodePrefixByLen = HI->CodePrefixByLen; \ MinCodeLen = HI->MinCodeLen; \ /* end Huff2_DecodeC_Macro_Init */ #define Huff2_DecodeC_Macro_Done(HI) \ } \ /* end Huff2_DecodeC_Macro_Done */ #define Huff2_DecodeC_Macro(HI,Symbol) \ CurCodeLen = MinCodeLen; \ LBitIO_ReadBits(BII,CurCode,CurCodeLen); \ PackedCode = CurCode; \ \ while( DecodeTable[PackedCode] != CurCodeLen ) \ { \ CurCode += CurCode; \ LBitIO_ReadBit(BII,bit); \ CurCode += bit; \ CurCodeLen++; \ \ PackedCode = CurCode - CodePrefixByLen[CurCodeLen]; \ } \ \ Symbol = DecodeTable[PackedCode+NumSymbols]; \ /* end Huff2_DecodeC_Macro */ /********** end DecodeC macros ************/ /********** FastDecodeC macros ************/ #define Huff2_FastDecodeC_Macro_Init(HI) \ { \ register ulong PeekedCode; \ register struct LBitIOInfo * BII; \ register struct FastDecodeItem * FastDecodeTable; \ long NumCharsMade; \ uword * CharsMade; \ long NumSymbols; \ long NumCharsWaiting; \ uword CharsWaiting[FD_MAXCHARSMADE_SUBONE]; \ uword * DecodeTable; \ ulong * CodePrefixByLen; \ ulong CurCode,PackedCode; \ long CurCodeLen; \ bool bit; \ \ NumCharsWaiting = 0; \ BII = HI->BII; \ NumSymbols = HI->NumSymbols; \ FastDecodeTable = (struct FastDecodeItem *) ( ((char *)HI->EnDe_codeTable) + 2*NumSymbols*sizeof(uword) );\ DecodeTable = (uword *)HI->EnDe_codeTable; \ CodePrefixByLen = HI->CodePrefixByLen; \ /* end Huff2_FastDecodeC_Macro_Init */ #define Huff2_FastDecodeC_Macro_Done(HI) \ } \ /* end Huff2_FastDecodeC_Macro_Done */ #define Huff2_FastDecodeC_Macro(HI,Symbol) \ if ( NumCharsWaiting > 0 ) \ { \ NumCharsWaiting--; \ Symbol = CharsWaiting[NumCharsWaiting]; \ } \ else \ { \ LBitIO_PeekBits(BII,PeekedCode,8); \ \ NumCharsMade = FastDecodeTable[PeekedCode].NumCharsMade; \ if ( NumCharsMade > 0 ) \ { \ CharsMade = FastDecodeTable[PeekedCode].CharsMade; \ CurCodeLen = FastDecodeTable[PeekedCode].NumBitsUsed; \ LBitIO_SkipBits(BII,CurCodeLen); \ NumCharsWaiting = NumCharsMade - 1; \ switch ( NumCharsWaiting ) \ { \ case 0: \ break; \ case 1: \ CharsWaiting[0] = CharsMade[1]; \ break; \ case 2: \ CharsWaiting[1] = CharsMade[1]; \ CharsWaiting[0] = CharsMade[2]; \ break; \ case 3: \ CharsWaiting[2] = CharsMade[1]; \ CharsWaiting[1] = CharsMade[2]; \ CharsWaiting[0] = CharsMade[3]; \ break; \ } \ Symbol = CharsMade[0]; \ } \ else /* use old decode method, can read 9 bits automatically */ \ { \ CurCodeLen = 8; \ CurCode = PeekedCode; \ LBitIO_SkipBits(BII,8); \ PackedCode = CurCode - CodePrefixByLen[CurCodeLen]; \ \ while( DecodeTable[PackedCode] != CurCodeLen ) \ { \ CurCode += CurCode; \ LBitIO_ReadBit(BII,bit); \ CurCode += bit; \ CurCodeLen++; \ \ PackedCode = CurCode - CodePrefixByLen[CurCodeLen]; \ } \ \ Symbol = DecodeTable[PackedCode+NumSymbols]; \ } \ \ } \ /* end Huff2_FastDecodeC_Macro */ /********** end FastDecodeC macros ************/ #endif // HUFFMAN2_H