1.cpp

Lzw数据压缩算法的源代码

#include <WINDOWS.H>    
#include <STDIO.H>    
#include <MEMORY.H>    
#include <CRTDBG.H>    
   
#define _MAX_WINDOW_SIZE    65536    
   
class CCompress   
{   
public:   
    CCompress() {};   
    virtual ~CCompress() {};   
   
public:   
    virtual int Compress(BYTE* src, int srclen, BYTE* dest) = 0;   
    virtual BOOL Decompress(BYTE* src, int srclen, BYTE* dest) = 0;   
   
protected:   
   
    void CopyBitsInAByte(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits);   
    // 在一个字节范围内复制位流    
    void CopyBits(BYTE* memDest, int nDestPos, BYTE* memSrc, int nSrcPos, int nBits);   
    //复制内存中的位流    
    void InvertDWord(DWORD* pDW);   // 将DWORD值从高位字节到低位字节排列    
    void SetBit(BYTE* byte, int iBit, BYTE aBit); // 设置byte的第iBit位为aBit    
    BYTE GetBit(BYTE byte, int pos);    // 得到字节byte第pos位的值    
    void MovePos(int* piByte, int* piBit, int num);    
    // 将位指针*piByte(字节偏移), *piBit(字节内位偏移)后移num    
    int UpperLog2(int n);   // 取log2(n)的upper_bound    
    int LowerLog2(int n);   // 取log2(n)的upper_bound    
};   
   
class CCompressLZ77 : public CCompress   
{   
public:   
    CCompressLZ77();   
    virtual ~CCompressLZ77();   
public:   
   
    int Compress(BYTE* src, int srclen, BYTE* dest);    // 压缩一段字节流      
    BOOL Decompress(BYTE* src, int srclen, BYTE* dest);// 解压缩一段字节流    
   
protected:   
   
    BYTE* pWnd;   
    int nWndSize;   // 当前窗口的长度    
    struct STIDXNODE   
    {   
        WORD off;       // 在src中的偏移    
        WORD off2;      // 用于对应的2字节串为重复字节的节点    
                        // 指从 off 到 off2 都对应了该2字节串    
        WORD next;      // 在SortHeap中的指针    
    };     
    WORD SortTable[65536];  // 256 * 256 指向SortHeap中下标的指针    
    struct STIDXNODE* SortHeap;   
    int HeapPos;  // 当前分配位置    
    int CurByte, CurBit;   
   
protected:   
   
    void _OutCode(BYTE* dest, DWORD code, int bits, BOOL isGamma);  // 输出压缩码    
    BOOL _SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, int* len);   
    // 在滑动窗口中查找术语    
    inline int _GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset);   
    // 得到已经匹配了3个字节的窗口位置offset    
    inline void _ScrollWindow(int n);   
    inline void _InsertIndexItem(int off);// 向索引中添加一个2字节串    
    void _InitSortTable();// 初始化索引表，释放上次压缩用的空间    
   
};   
   
/**************************************************************************/   
   
void main(int argc, char* argv[])   
{      
    if (argc != 4)   
    {   
        printf("%d  ",argc);   
        puts("Usage: ");   
        printf("    Compress : %s c sourcefile destfile\n", argv[0]);   
        printf("  Decompress : %s d sourcefile destfile\n", argv[0]);   
        return;   
    }   
   
    BYTE soubuf[65536];   
    BYTE destbuf[65536 + 16];   
   
    FILE* in;   
    FILE* out;   
    in = fopen(argv[2], "rb");   
    if (in == NULL)   
    {   
        puts("Can't open source file");   
        return;   
    }   
    out = fopen(argv[3], "wb");   
    if (out == NULL)   
    {   
        puts("Can't open dest file");   
        fclose(in);   
        return;   
    }   
    fseek(in, 0, SEEK_END);   
    long soulen = ftell(in);   
    fseek(in, 0, SEEK_SET);   
   
    CCompressLZ77 cc;   
    WORD flag1, flag2;   
       
    if (argv[1][0] == 'c') // compress    
    {   
        int last = soulen, act;   
        while ( last > 0 )   
        {   
            act = min(65536, last);   
            fread(soubuf, act, 1, in);   
            last -= act;   
            if (act == 65536)           // out 65536 bytes                  
                flag1 = 0;         
            else                    // out last blocks    
                flag1 = act;   
            fwrite(&flag1, sizeof(WORD), 1, out);   
   
            int destlen = cc.Compress((BYTE*)soubuf, act, (BYTE*)destbuf);   
            if (destlen == 0)       // can't compress the block    
            {   
                flag2 = flag1;   
                fwrite(&flag2, sizeof(WORD), 1, out);   
                fwrite(soubuf, act, 1, out);   
            }   
            else   
            {   
                flag2 = (WORD)destlen;   
                fwrite(&flag2, sizeof(WORD), 1, out);                  
                fwrite(destbuf, destlen, 1, out);                  
            }   
        }   
    }   
    else if (argv[1][0] == 'd') // decompress    
    {   
        int last = soulen, act;   
        while (last > 0)   
        {   
            fread(&flag1, sizeof(WORD), 1, in);   
            fread(&flag2, sizeof(WORD), 1, in);   
            last -= 2 * sizeof(WORD);   
            if (flag1 == 0)   
                act = 65536;   
            else   
                act = flag1;   
            last-= flag2 ? (flag2) : act;   
   
            if (flag2 == flag1)   
            {   
                fread(soubuf, act, 1, in);                 
            }   
            else   
            {   
                fread(destbuf, flag2, 1, in);   
                if (!cc.Decompress((BYTE*)soubuf, act, (BYTE*)destbuf))   
                {   
                    puts("Decompress error");   
                    fclose(in);   
                    fclose(out);   
                    return;   
                }   
            }   
            fwrite((BYTE*)soubuf, act, 1, out);                
        }   
    }   
    else   
    {   
        puts("Usage: ");   
        printf("    Compress : %s c sourcefile destfile\n", argv[0]);   
        printf("  Decompress : %s d sourcefile destfile\n", argv[0]);          
    }   
   
    fclose(in);   
    fclose(out);   
}   
   
/********************************************************************/   
   
// 取log2(n)的upper_bound    
int CCompress::UpperLog2(int n)   
{   
    int i = 0;   
    if (n > 0)   
    {   
        int m = 1;   
        while(1)   
        {   
            if (m >= n)   
                return i;   
            m <<= 1;   
            i++;   
        }   
    }   
    else    
        return -1;   
}   
   
   
// 取log2(n)的lower_bound    
int CCompress::LowerLog2(int n)   
{   
    int i = 0;   
    if (n > 0)   
    {   
        int m = 1;   
        while(1)   
        {   
            if (m == n)   
                return i;   
            if (m > n)   
                return i - 1;   
            m <<= 1;   
            i++;   
        }   
    }   
    else    
        return -1;   
}   
   
// 将位指针*piByte(字节偏移), *piBit(字节内位偏移)后移num位    
void CCompress::MovePos(int* piByte, int* piBit, int num)   
{   
    num += (*piBit);   
    (*piByte) += num / 8;   
    (*piBit) = num % 8;   
}   
   
// 得到字节byte第pos位的值    
//      pos顺序为高位起从0记数（左起）    
BYTE CCompress::GetBit(BYTE byte, int pos)   
{   
    int j = 1;   
    j <<= 7 - pos;   
    if (byte & j)   
        return 1;   
    else    
        return 0;   
}   
   
// 设置byte的第iBit位为aBit    
//      iBit顺序为高位起从0记数（左起）    
void CCompress::SetBit(BYTE* byte, int iBit, BYTE aBit)   
{   
    if (aBit)   
        (*byte) |= (1 << (7 - iBit));   
    else   
        (*byte) &= ~(1 << (7 - iBit));   
}   
   
// 将DWORD值从高位字节到低位字节排列    
void CCompress::InvertDWord(DWORD* pDW)   
{   
    union UDWORD{ DWORD dw; BYTE b[4]; };   
    UDWORD* pUDW = (UDWORD*)pDW;   
    BYTE b;   
    b = pUDW->b[0];  pUDW->b[0] = pUDW->b[3]; pUDW->b[3] = b;   
    b = pUDW->b[1];  pUDW->b[1] = pUDW->b[2]; pUDW->b[2] = b;   
}   
   
// CopyBits : 复制内存中的位流    
//      memDest - 目标数据区    
//      nDestPos - 目标数据区第一个字节中的起始位    
//      memSrc - 源数据区    
//      nSrcPos - 源数据区第一个字节的中起始位    
//      nBits - 要复制的位数    
//  说明：    
//      起始位的表示约定为从字节的高位至低位（由左至右）    
//      依次为 0，1，... , 7    
//      要复制的两块数据区不能有重合    
void CCompress::CopyBits(BYTE* memDest, int nDestPos,    
              BYTE* memSrc, int nSrcPos, int nBits)   
{   
    int iByteDest = 0, iBitDest;   
    int iByteSrc = 0, iBitSrc = nSrcPos;   
   
    int nBitsToFill, nBitsCanFill;   
   
    while (nBits > 0)   
    {   
        // 计算要在目标区当前字节填充的位数    
        nBitsToFill = min(nBits, iByteDest ? 8 : 8 - nDestPos);   
        // 目标区当前字节要填充的起始位    
        iBitDest = iByteDest ? 0 : nDestPos;   
        // 计算可以一次从源数据区中复制的位数    
        nBitsCanFill = min(nBitsToFill, 8 - iBitSrc);   
        // 字节内复制    
        CopyBitsInAByte(memDest + iByteDest, iBitDest,    
            memSrc + iByteSrc, iBitSrc, nBitsCanFill);         
        // 如果还没有复制完 nBitsToFill 个    
        if (nBitsToFill > nBitsCanFill)   
        {   
            iByteSrc++; iBitSrc = 0; iBitDest += nBitsCanFill;   
            CopyBitsInAByte(memDest + iByteDest, iBitDest,    
                    memSrc + iByteSrc, iBitSrc,    
                    nBitsToFill - nBitsCanFill);   
            iBitSrc += nBitsToFill - nBitsCanFill;   
        }   
        else    
        {   
            iBitSrc += nBitsCanFill;   
            if (iBitSrc >= 8)   
            {   
                iByteSrc++; iBitSrc = 0;   
            }   
        }   
   
        nBits -= nBitsToFill;   // 已经填充了nBitsToFill位    
        iByteDest++;   
    }      
}   
   
// CopyBitsInAByte : 在一个字节范围内复制位流    
// 参数含义同 CopyBits 的参数    
// 说明：    
//      此函数由 CopyBits 调用，不做错误检查，即    
//      假定要复制的位都在一个字节范围内