war.c

压缩解压算法LZ77算法有许多派生算法(这里面包括 LZSS算法)。它们的算法原理上基本都相同

class LZWCoder 
{
private: 
        struct TStr 
        { 
                char *string; 
                unsigned int len; 
        }; 
        TStr StrTable[4097]; 
        unsigned int ItemPt; 
        unsigned int BytePt; 
        unsigned char BitPt; 
        unsigned char Bit[8]; 
        unsigned char Bits; 
        unsigned int OutBytes; 
        void InitStrTable(); 
        void CopyStr(TStr *d, TStr s); 
        void StrJoinChar(TStr *s, char c); 
        unsigned int InStrTable(TStr s); 
        void AddTableEntry(TStr s); 
        void WriteCode(char *dest, unsigned int b); 
        unsigned int GetNextCode(char *src); 
        void StrFromCode(TStr *s, unsigned int c); 
        void WriteString(char *dest, TStr s); 
public: 
        unsigned int Encode(char *src, unsigned int len, char *dest); 
        unsigned int Decode(char *src, unsigned int *len, char *dest); 
        LZWCoder(); 
        ~LZWCoder(); 
}; 

void LZWCoder::InitStrTable() 
{ 
        unsigned int i; 
        for(i = 0; i < 256; i ++) 
        { 
                StrTable[i].string = (char *)realloc(StrTable[i].string, 1); 
                StrTable[i].string[0] = i; 
                StrTable[i].len = 1; 
        } 
        StrTable[256].string = NULL; 
        StrTable[256].len = 0; 
        StrTable[257].string = NULL; 
        StrTable[257].len = 0; 
        ItemPt = 257; 
        Bits = 9; 
} 

void LZWCoder::CopyStr(TStr *d, TStr s) 
{ 
        unsigned int i; 
        d->string = (char *)realloc(d->string, s.len); 
        for(i = 0; i < s.len; i ++) 
                d->string[i] = s.string[i]; 
        d->len = s.len; 
} 

void LZWCoder::StrJoinChar(TStr *s, char c) 
{ 
        s->string = (char *)realloc(s->string, s->len + 1); 
        s->string[s->len ++] = c; 
} 

unsigned int LZWCoder::InStrTable(TStr s) 
{ 
        unsigned int i,j; 
        bool b; 
        for(i = 0; i <= ItemPt; i ++) 
        { 
                if(StrTable[i].len == s.len) 
                { 
                        b = true; 
                        for(j = 0; j < s.len; j ++) 
                                if(StrTable[i].string[j] != s.string[j]) 
                                { 
                                        b = false; 
                                        break; 
                                } 
                        if(b) return i; 
                } 
        } 
        return 65535; 
} 

void LZWCoder::AddTableEntry(TStr s) 
{ 
        CopyStr(&StrTable[++ItemPt], s); 
} 

void LZWCoder::WriteCode(char *dest, unsigned int b) 
{ 
        unsigned char i; 
        for(i = 0; i < Bits; i++) 
        { 
                Bit[BitPt ++] = (b & (1 << (Bits - i - 1))) != 0; 
                if(BitPt == 8) 
                { 
                        BitPt = 0; 
                        dest[BytePt ++] = (Bit[0] << 7) 
                                        + (Bit[1] << 6) 
                                        + (Bit[2] << 5) 
                                        + (Bit[3] << 4) 
                                        + (Bit[4] << 3) 
                                        + (Bit[5] << 2) 
                                        + (Bit[6] << 1) 
                                        + Bit[7]; 
                } 
        } 
} 

unsigned int LZWCoder::GetNextCode(char *src) 
{ 
        unsigned char i; 
        unsigned int c = 0; 
        for(i = 0; i < Bits; i ++) 
        { 
                c = (c << 1) + ((src[BytePt] & (1 << (8 - (BitPt ++) - 1))) != 0); 
                if(BitPt == 8) 
                { 
                        BitPt = 0; 
                        BytePt ++; 
                } 
        } 
        return c; 
} 

void LZWCoder::StrFromCode(TStr *s, unsigned int c) 
{ 
        CopyStr(s, StrTable[c]); 
} 

void LZWCoder::WriteString(char *dest, TStr s) 
{ 
        unsigned int i; 
        for(i = 0; i < s.len; i++) 
                dest[OutBytes ++] = s.string[i]; 
} 

unsigned int LZWCoder::Encode(char *src, unsigned int len, char *dest) 
{ 
        TStr Omega, t; 
        char k; 
        unsigned int i; 
        unsigned int p; 
        BytePt = 0; 
        BitPt = 0; 
        InitStrTable(); 
        WriteCode(dest, 256); 
        Omega.string = NULL; 
        Omega.len = 0; 
        t.string = NULL; 
        t.len = 0; 
        for(i = 0; i < len; i ++) 
        { 
                k = src[i]; 
                CopyStr(&t, Omega); 
                StrJoinChar(&t, k); 
                if(InStrTable(t) != 65535) 
                        CopyStr(&Omega, t); 
                else 
                { 
                        WriteCode(dest, InStrTable(Omega)); 
                        AddTableEntry(t); 
                        switch(ItemPt) 
                        { 
                                case 512: Bits = 10; break; 
                                case 1024: Bits = 11; break; 
                                case 2048: Bits = 12; break; 
                                case 4096: WriteCode(dest, 256); InitStrTable(); 
                        } 
                        Omega.string = (char *)realloc(Omega.string, 1); 
                        Omega.string[0] = k; 
                        Omega.len = 1; 
                } 
        } 
        WriteCode(dest, InStrTable(Omega)); 
        WriteCode(dest, 257); 
        Bits = 7; 
        WriteCode(dest, 0); 
        free(Omega.string); 
        free(t.string); 
        return BytePt; 
} 

unsigned int LZWCoder::Decode(char *src, unsigned int *len, char *dest) 
{ 
        unsigned int code, oldcode; 
        TStr t, s; 
        BytePt = 0; 
        BitPt = 0; 
        OutBytes = 0; 
        t.string = NULL; 
        t.len = 0; 
        s.string = NULL; 
        s.len = 0; 
        InitStrTable(); 
        while((code = GetNextCode(src)) != 257) 
        {
                if(code == 256) 
                { 
                        InitStrTable(); 
                        code = GetNextCode(src); 
                        if(code == 257) break; 
                        StrFromCode(&s, code); 
                        WriteString(dest, s); 
                        oldcode = code; 
                } 
                else 
                { 
                        if(code <= ItemPt) 
                        { 
                                StrFromCode(&s, code); 
                                WriteString(dest, s); 
                                StrFromCode(&t, oldcode); 
                                StrJoinChar(&t, s.string[0]); 
                                AddTableEntry(t); 
                                switch(ItemPt) 
                                { 
                                        case 511: Bits = 10; break; 
                                        case 1023: Bits = 11; break; 
                                        case 2047: Bits = 12; break; 
                                } 
                                oldcode = code; 
                        } 
                        else 
                        { 
                                StrFromCode(&s, oldcode); 
                                StrJoinChar(&s, s.string[0]); 
                                WriteString(dest, s); 
                                AddTableEntry(s); 
                                switch(ItemPt) 
                                { 
                                        case 511: Bits = 10; break; 
                                        case 1023: Bits = 11; break; 
                                        case 2047: Bits = 12; break; 
                                } 
                                oldcode = code; 
                        } 
                } 
        }
        free(t.string); 
        free(s.string); 
        *len = BytePt + (BitPt != 0); 
        return OutBytes; 
} 

LZWCoder::LZWCoder() 
{ 
        unsigned int i; 
        for(i = 0; i < 4097; i ++) 
        { 
                StrTable[i].string = NULL; 
                StrTable[i].len = 0; 
        } 
} 

LZWCoder::~LZWCoder() 
{ 
        unsigned int i; 
        for(i = 0; i < 4097; i ++) 
                free(StrTable[i].string); 
}