提供一段我用C++写的LZW压缩、解压算法的程序

qwernet

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.string = (char *)realloc(StrTable.string, 1);

                StrTable.string[0] = i;

                StrTable.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 = s.string;

        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.len == s.len)

                {

                        b = true;

                        for(j = 0; j < s.len; j ++)

                                if(StrTable.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;

}



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;

                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.string = NULL;

                StrTable.len = 0;

        }

}



LZWCoder::~LZWCoder()

{

        unsigned int i;

        for(i = 0; i < 4097; i ++)

                free(StrTable.string);

}


-----此内容被qwernet于2005-01-02,11:17:57编辑过

qwernet

在BCB下对几段几K大小的文章测试通过，可压缩到原来大小的30%-50%，压缩速率约100KB/s(P4 2.4C)，解压速率约1MB/s。未进行深一步的测试。

未在AVR的C语言平台测试过，不过估计应该作少少修改就可以用。适用于程序、数据、文本的压缩，不适用于声音、图像。



用法：



LZWCoder *Coder;

Coder = new LZWCoder();



然后用

Coder->Encode(char *src, unsigned int len, char *dest);

Coder->Decode(char *src, unsigned int *len, char *dest);

进行压缩或解压。Encode函数中，src是输入数据的指针，len是输入数据的长度，dest是输出数据的指针。函数返回输出数据的长度。Decode函数中各参数与Encode类似，但*len会返回解压过程使用了输入数据的字节数（一般等于压缩时输出数据的长度）。

使用时把要压缩的数据分成每段8K来处理，效果会比较好。
-----此内容被qwernet于2005-01-02,11:21:47编辑过

HJJourAVR

GIF图片就是用LZW压缩解压的吧？

制作GIF的专利明年就会过期了，可以随便用了。现在的GUN组织是不能用GIF的。

qwernet

LZW算法比较简单，我是按照这本书上写的算法来编程的。

qwernet

是的，GIF中用到LZW算法，因为GIF是无损压缩的，无损压缩算法里面LZW是比较出众的。但如果要追求大压缩率，还是需要JPEG的有损压缩算法。

mubo

好猛

！

avrboy

單片機攪這個恐怕不現實:

單這個 TStr StrTable[4097] 就花光芯片的ram了.

qwernet

当然是最好用ARM啦

用单片机即使不考虑RAM，速度也太慢了。

huchen520

怎么好象在c++里面没定义那个realloc()函数啊!我编译通不过啊1~

怎么解决啊?

tgl3721

mark