📄 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 <crbinc/mempool.h>
#include <crbinc/lbitio.h>
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
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -