1.cpp

Lzw数据压缩算法的源代码

void CCompress::CopyBitsInAByte(BYTE* memDest, int nDestPos,    
              BYTE* memSrc, int nSrcPos, int nBits)   
{   
    BYTE b1, b2;   
    b1 = *memSrc;   
    b1 <<= nSrcPos; b1 >>= 8 - nBits;   // 将不用复制的位清0    
    b1 <<= 8 - nBits - nDestPos;      // 将源和目的字节对齐    
    *memDest |= b1;     // 复制值为1的位    
    b2 = 0xff; b2 <<= 8 - nDestPos;       // 将不用复制的位置1    
    b1 |= b2;   
    b2 = 0xff; b2 >>= nDestPos + nBits;   
    b1 |= b2;   
    *memDest &= b1;     // 复制值为0的位    
}   
   
   
CCompressLZ77::CCompressLZ77()   
{      
    SortHeap = new struct STIDXNODE[_MAX_WINDOW_SIZE];   
}   
   
CCompressLZ77::~CCompressLZ77()   
{   
    delete[] SortHeap;   
}   
   
// 初始化索引表，释放上次压缩用的空间    
void CCompressLZ77::_InitSortTable()   
{   
    memset(SortTable, 0, sizeof(WORD) * 65536);   
    nWndSize = 0;   
    HeapPos = 1;   
}   
   
// 向索引中添加一个2字节串    
void CCompressLZ77::_InsertIndexItem(int off)   
{   
    WORD q;   
    BYTE ch1, ch2;   
    ch1 = pWnd[off]; ch2 = pWnd[off + 1];      
       
    if (ch1 != ch2)   
    {   
        // 新建节点    
        q = HeapPos;   
        HeapPos++;   
        SortHeap[q].off = off;   
        SortHeap[q].next = SortTable[ch1 * 256 + ch2];   
        SortTable[ch1 * 256 + ch2] = q;   
    }   
    else   
    {   
        // 对重复2字节串    
        // 因为没有虚拟偏移也没有删除操作，只要比较第一个节点    
        // 是否和 off 相连接即可    
        q = SortTable[ch1 * 256 + ch2];   
        if (q != 0 && off == SortHeap[q].off2 + 1)   
        {          
            // 节点合并    
            SortHeap[q].off2 = off;   
        }          
        else   
        {   
            // 新建节点    
            q = HeapPos;   
            HeapPos++;   
            SortHeap[q].off = off;   
            SortHeap[q].off2 = off;   
            SortHeap[q].next = SortTable[ch1 * 256 + ch2];   
            SortTable[ch1 * 256 + ch2] = q;   
        }   
    }   
}   
   
//////////////////////////////////////////    
// 将窗口向右滑动n个字节    
void CCompressLZ77::_ScrollWindow(int n)   
{      
    for (int i = 0; i < n; i++)   
    {          
        nWndSize++;        
        if (nWndSize > 1)               
            _InsertIndexItem(nWndSize - 2);   
    }   
}   
   
///////////////////////////////////////////////////////////    
// 得到已经匹配了2个字节的窗口位置offset    
// 共能匹配多少个字节    
int CCompressLZ77::_GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset)   
{   
    int i = 2; // 已经匹配了2个字节    
    int maxsame = min(srclen - nSeekStart, nWndSize - offset);   
    while (i < maxsame   
            && src[nSeekStart + i] == pWnd[offset + i])   
        i++;   
    _ASSERT(nSeekStart + i <= srclen && offset + i <= nWndSize);   
    return i;   
}   
   
///////////////////////////////////////////////////////////    
// 在滑动窗口中查找术语    
// nSeekStart - 从何处开始匹配    
// offset, len - 用于接收结果，表示在滑动窗口内的偏移和长度    
// 返回值- 是否查到长度为2或2以上的匹配字节串    
BOOL CCompressLZ77::_SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, int* len)   
{      
    int j, m, n;   
   
    if (nSeekStart < srclen - 1)   
    {   
        BYTE ch1, ch2;   
        ch1 = src[nSeekStart]; ch2 = src[nSeekStart + 1];   
        WORD p;   
        p = SortTable[ch1 * 256 + ch2];   
        if (p != 0)   
        {   
            m = 2; n = SortHeap[p].off;   
            while (p != 0)   
            {   
                j = _GetSameLen(src, srclen,    
                    nSeekStart, SortHeap[p].off);   
                if ( j > m )   
                {    
                    m = j;    
                    n = SortHeap[p].off;   
                }              
                p = SortHeap[p].next;   
            }      
            (*offset) = n;    
            (*len) = m;   
            return TRUE;           
        }      
    }   
    return FALSE;   
}   
   
////////////////////////////////////////    
// 输出压缩码    
// code - 要输出的数    
// bits - 要输出的位数(对isGamma=TRUE时无效)    
// isGamma - 是否输出为γ编码    
void CCompressLZ77::_OutCode(BYTE* dest, DWORD code, int bits, BOOL isGamma)   
{      
    if ( isGamma )   
    {   
        BYTE* pb;   
        DWORD out;   
        // 计算输出位数    
        int GammaCode = (int)code - 1;   
        int q = LowerLog2(GammaCode);   
        if (q > 0)   
        {   
            out = 0xffff;   
            pb = (BYTE*)&out;   
            // 输出q个1    
            CopyBits(dest + CurByte, CurBit, pb, 0, q);   
            MovePos(&CurByte, &CurBit, q);   
        }   
        // 输出一个0    
        out = 0;   
        pb = (BYTE*)&out;          
        CopyBits(dest + CurByte, CurBit, pb + 3, 7, 1);   
        MovePos(&CurByte, &CurBit, 1);   
        if (q > 0)   
        {   
            // 输出余数, q位    
            int sh = 1;   
            sh <<= q;   
            out = GammaCode - sh;   
            pb = (BYTE*)&out;   
            InvertDWord(&out);   
            CopyBits(dest + CurByte, CurBit,    
                pb + (32 - q) / 8, (32 - q) % 8, q);   
            MovePos(&CurByte, &CurBit, q);   
        }   
    }   
    else    
    {   
        DWORD dw = (DWORD)code;   
        BYTE* pb = (BYTE*)&dw;   
        InvertDWord(&dw);   
        CopyBits(dest + CurByte, CurBit,    
                pb + (32 - bits) / 8, (32 - bits) % 8, bits);   
        MovePos(&CurByte, &CurBit, bits);   
    }   
}   
   
/////////////////////////////////////////////    
// 压缩一段字节流    
// src - 源数据区    
// srclen - 源数据区字节长度    
// dest - 压缩数据区，调用前分配srclen+5字节内存    
// 返回值 > 0 压缩数据长度    
// 返回值 = 0 数据无法压缩    
// 返回值 < 0 压缩中异常错误    
int CCompressLZ77::Compress(BYTE* src, int srclen, BYTE* dest)   
{   
    int i;   
    CurByte = 0; CurBit = 0;       
    int off, len;   
   
    if (srclen > 65536)    
        return -1;   
   
    pWnd = src;   
    _InitSortTable();   
    for (i = 0; i < srclen; i++)   
    {          
        if (CurByte >= srclen)   
            return 0;   
        if (_SeekPhase(src, srclen, i, &off, &len))   
        {              
            // 输出匹配术语 flag(1bit) + len(γ编码) + offset(最大16bit)    
            _OutCode(dest, 1, 1, FALSE);   
            _OutCode(dest, len, 0, TRUE);   
   
            // 在窗口不满64k大小时，不需要16位存储偏移    
            _OutCode(dest, off, UpperLog2(nWndSize), FALSE);   
                           
            _ScrollWindow(len);   
            i += len - 1;   
        }   
        else   
        {   
            // 输出单个非匹配字符 0(1bit) + char(8bit)    
            _OutCode(dest, 0, 1, FALSE);   
            _OutCode(dest, (DWORD)(src[i]), 8, FALSE);   
            _ScrollWindow(1);   
        }   
    }   
    int destlen = CurByte + ((CurBit) ? 1 : 0);   
    if (destlen >= srclen)   
        return 0;   
    return destlen;   
}   
   
   
/////////////////////////////////////////////    
// 解压缩一段字节流    
// src - 接收原始数据的内存区    
// srclen - 源数据区字节长度    
// dest - 压缩数据区    
// 返回值 - 成功与否    
BOOL CCompressLZ77::Decompress(BYTE* src, int srclen, BYTE* dest)   
{   
    int i;   
    CurByte = 0; CurBit = 0;   
    pWnd = src;     // 初始化窗口    
    nWndSize = 0;   
   
    if (srclen > 65536)    
        return FALSE;   
       
    for (i = 0; i < srclen; i++)   
    {          
        BYTE b = GetBit(dest[CurByte], CurBit);   
        MovePos(&CurByte, &CurBit, 1);   
        if (b == 0) // 单个字符    
        {   
            CopyBits(src + i, 0, dest + CurByte, CurBit, 8);   
            MovePos(&CurByte, &CurBit, 8);   
            nWndSize++;   
        }   
        else        // 窗口内的术语    
        {   
            int q = -1;   
            while (b != 0)   
            {   
                q++;   
                b = GetBit(dest[CurByte], CurBit);   
                MovePos(&CurByte, &CurBit, 1);                 
            }   
            int len, off;   
            DWORD dw = 0;   
            BYTE* pb;   
            if (q > 0)   
            {                  
                pb = (BYTE*)&dw;   
                CopyBits(pb + (32 - q) / 8, (32 - q) % 8, dest + CurByte, CurBit, q);   
                MovePos(&CurByte, &CurBit, q);   
                InvertDWord(&dw);   
                len = 1;   
                len <<= q;   
                len += dw;   
                len += 1;   
            }   
            else   
                len = 2;   
   
            // 在窗口不满64k大小时，不需要16位存储偏移    
            dw = 0;   
            pb = (BYTE*)&dw;   
            int bits = UpperLog2(nWndSize);   
            CopyBits(pb + (32 - bits) / 8, (32 - bits) % 8, dest + CurByte, CurBit, bits);   
            MovePos(&CurByte, &CurBit, bits);   
            InvertDWord(&dw);   
            off = (int)dw;   
            // 输出术语    
            for (int j = 0; j < len; j++)   
            {   
                _ASSERT(i + j <  srclen);   
                _ASSERT(off + j <  _MAX_WINDOW_SIZE);   
                   
                src[i + j] = pWnd[off + j];   
            }   
            nWndSize += len;   
            i += len - 1;   
        }   
        // 滑动窗口    
        if (nWndSize > _MAX_WINDOW_SIZE)   
        {   
            pWnd += nWndSize - _MAX_WINDOW_SIZE;   
            nWndSize = _MAX_WINDOW_SIZE;               
        }   
    }   
   
    return TRUE;   
}