当前位置: 首页 >> 程序设计 >> LZ77源码阅读笔记

LZ77源码阅读笔记

作者：来源：louisking.cublog.cn 发表时间：2008-01-08 浏览次数：字号：大 中 小

然后看写入Bit的操作WriteBits，用来在指定的Buff偏移位置写入一串bits：

void
WriteBits(
   PUCHAR pDataBuffer,
   ULONG   ulOffsetToWrite,
   ULONG   ulBits,
   ULONG   ulBitLength
   )
{
   ULONG   ulDwordsOffset;
   ULONG   ulBitsOffset, ulBitsRemained;

   ulDwordsOffset = ulOffsetToWrite>>5;
   ulBitsOffset = ulOffsetToWrite&31;
   ulBitsRemained = 32 - ulBitsOffset;

   if( 0==ulBitsOffset )
   {
       *((PULONG)pDataBuffer+ulDwordsOffset) = ulBits;
   }
   else if( ulBitsRemained>=ulBitLength )
   {
       *((PULONG)pDataBuffer+ulDwordsOffset) |= (ulBits<<ulBitsOffset);
   }
   else
   {
       *((PULONG)pDataBuffer+ulDwordsOffset) |= (ulBits<<ulBitsOffset);
       *((PULONG)pDataBuffer+ulDwordsOffset+1) = ulBits>>ulBitsRemained;
   }
}

下面就是LZ77压缩的主体函数：

void
lz77compress(
   PUCHAR pDataBuffer,
   ULONG   ulDataLength,
   PUCHAR pOutputBuffer,
   PULONG pulNumberOfBits
   )
{
   LONG        iSlideWindowPtr;
   ULONG       ulBytesCoded;
   ULONG       ulMaxlength;
   PUCHAR      pSlideWindowPtr;
   PUCHAR      pUnprocessedDataPtr;

   ULONG   offset;
   ULONG   length;
   ULONG   ulCodingLength;

   ULONG   ulBitOffset;
   UCHAR   cc;

   int     i;

//滑动窗口的初始长度是-MAX_WND_SIZE，因为现在还没有字符被编码，所以滑动窗口的最右端就是编码字串的最前端。

   iSlideWindowPtr = -MAX_WND_SIZE;
   pSlideWindowPtr = NULL;
   ulBitOffset = 0;
   ulBytesCoded = 0;

   while( ulBytesCoded<ulDataLength )
   {

//当iSildeWindowPtr>=0时，已编码的字串长度已经大于等于滑动窗的长度
       if( iSlideWindowPtr>=0 )
       {
           pSlideWindowPtr = pDataBuffer+iSlideWindowPtr;
           ulMaxlength = MAX_WND_SIZE;

       }
       else if( iSlideWindowPtr>=-MAX_WND_SIZE )
       {
           pSlideWindowPtr = pDataBuffer;
           ulMaxlength = MAX_WND_SIZE + iSlideWindowPtr;
       }
       else
       {
           pSlideWindowPtr = NULL;
           ulMaxlength = 0;
       }

       pUnprocessedDataPtr = pDataBuffer + ulBytesCoded;
       if( ulMaxlength>ulDataLength-ulBytesCoded )
       {
           ulMaxlength = ulDataLength-ulBytesCoded;
       }

//在已编码的串中搜索待编码字串的最长组合，并记录长度、偏移

       FindLongestSubstring(
           pSlideWindowPtr,
           pUnprocessedDataPtr,
           ulMaxlength,
           &offset,
           &length
           );

       assert( length<=MAX_WND_SIZE );
       assert( offset<MAX_WND_SIZE );

       if(length>1)
       {

//如果匹配长度大于1，将首位置1，然后写入偏移的位置，因为搜索窗口长度是10位的，所以这个偏移按照10位的2进制编码写入。最后写入Golomb编码。

           Write1ToBitStream(pOutputBuffer, ulBitOffset);
           ulBitOffset++;

           for(i=0; i<OFFSET_CODING_LENGTH; i++, ulBitOffset++)
           {
               if( (offset>>i)&1 )
               {
                   Write1ToBitStream(pOutputBuffer, ulBitOffset);
               }
               else
               {
                   Write0ToBitStream(pOutputBuffer, ulBitOffset);
               }
           }

           ulCodingLength = WriteGolombCode(length, pOutputBuffer, ulBitOffset);

           ulBitOffset += ulCodingLength;
           iSlideWindowPtr += length;
           ulBytesCoded += length;

       }
       else
       {

//如果匹配长度小于等于1，将首位置0，然后写入对应字符的8位2进制编码
           Write0ToBitStream(pOutputBuffer, ulBitOffset);
           ulBitOffset++;

           cc = (*pUnprocessedDataPtr);
           for(i=0; i<8; i++, ulBitOffset++)
           {
               if( (cc>>i)&1 )
               {
                   Write1ToBitStream(pOutputBuffer, ulBitOffset);
               }
               else
               {
                   Write0ToBitStream(pOutputBuffer, ulBitOffset);
               }
           }

           iSlideWindowPtr++;
           ulBytesCoded++;
       }

   }

   if( ulBytesCoded!=ulDataLength )
   {
       assert(ulBytesCoded==ulDataLength);
   }

   *pulNumberOfBits = ulBitOffset;

}