随笔-341  评论-2670  文章-0  trackbacks-0
    这个压缩流是Vczh Library++ 2.0庞大的流与控制器系统的其中一个部分。我准备将其改造成可调大小的,并且打算添加LZW与Huffman压缩解压算法。以下是用C++实现的代码。

    头文件:
  1 /*******************************************************************************
  2 Vczh Library++ 2.0
  3 数据结构::压缩流
  4 开发者:陈梓瀚
  5 
  6 接口:
  7 类:
  8   VL_CompressedStream                    :压缩流
  9   VL_LZ77Stream                            :LZ77压缩流
 10   VL_LZWStream                            :LZW压缩流
 11   VL_HuffmanStream                        :Adaptive/Canonical Huffman压缩流
 12 函数:
 13 *******************************************************************************/
 14 #ifndef VL_COMPRESSION
 15 #define VL_COMPRESSION
 16 
 17 #include "VL_Stream.h"
 18 
 19 namespace vl
 20 {
 21     namespace stream
 22     {
 23         using namespace collection;
 24 
 25 /*********************************************************************************************************
 26 压缩流
 27 *********************************************************************************************************/
 28 
 29         class VL_CompressedStream : public VL_Base , public IVL_Stream
 30         {
 31         public:
 32             enum VLE_OpenMode
 33             {
 34                 vomRead,
 35                 vomWrite,
 36             };
 37 
 38             class Compressor : public IVL_Interface
 39             {
 40             public:
 41                 virtual void            SetStream(IVL_Stream* Stream)=0;
 42                 virtual VInt            Write(VPointer Data , VInt ByteCount)=0;
 43             };
 44 
 45             class Decompressor : public IVL_Interface
 46             {
 47             public:
 48                 virtual void            SetStream(IVL_Stream* Stream)=0;
 49                 virtual VInt            Read(VPointer Data , VInt ByteCount)=0;
 50                 virtual VL_Base*        CopyStatus()=0;
 51                 virtual void            ReplaceStatus(VL_Base* Status)=0;
 52                 virtual void            FreeStatus(VL_Base* Status)=0;
 53             };
 54         protected:
 55             IVL_Stream*                    FStream;
 56             VBool                        FOwned;
 57             VLE_OpenMode                FMode;
 58             VSize                        FPosition;
 59             Compressor*                    FCompressor;
 60             Decompressor*                FDecompressor;
 61 
 62             void                        Init(IVL_Stream* Stream , VBool Owned , Compressor* aCompressor);
 63             void                        Init(IVL_Stream* Stream , VBool Owned , Decompressor* aDecompressor);
 64 
 65             VL_CompressedStream();
 66         public:
 67             ~VL_CompressedStream();
 68 
 69             VBool                        CanRead();
 70             VBool                        CanPeek();
 71             VBool                        CanWrite();
 72             VBool                        CanClose();
 73             VBool                        CanSeek();
 74             VBool                        CanGrow();
 75             VInt                        Read(VPointer Data , VInt ByteCount);
 76             VInt                        Peek(VPointer Data , VInt ByteCount);
 77             VInt                        Write(VPointer Data , VInt ByteCount);
 78             void                        Close();
 79             VBool                        IsAvailable();
 80             VSize                        Position();
 81             VSize                        Size();
 82             VSize                        MaxWriteSize();
 83             void                        SeekFromBegin(VSize Offset);
 84             void                        SeekFromEnd(VSize Offset);
 85             void                        Seek(VSize Offset);
 86             VBool                        IsEnd();
 87         };
 88 
 89         class VL_LZ77Stream : public VL_CompressedStream
 90         {
 91         public:
 92             VL_LZ77Stream(IVL_Stream* Stream , VLE_OpenMode Mode , VBool Owned=false);
 93         };
 94 
 95 /*********************************************************************************************************
 96 LZ77压缩算法 [0:wide,1:encoded][0-127:byte count-1][index/data]
 97 *********************************************************************************************************/
 98 
 99         namespace LZ77Algorithms
100         {
101             class AlgorithmBase : public VL_Base
102             {
103             protected:
104                 static const VInt            WindowSize=128;
105                 static const VInt            MaxBlockSize=128;
106 
107                 VByte                        FWindow[WindowSize*3];        /*滑动窗口*/
108                 VSize                        FPosition;                    /*当前位置*/
109                 VInt                        FUsedWindowSize;            /*窗口有效数据大小*/
110                 VSize                        FWindowStartPosition;        /*窗口的起始位置*/
111 
112                 AlgorithmBase();
113             };
114 
115             class Compressor : public AlgorithmBase , public VL_CompressedStream::Compressor
116             {
117             protected:
118                 IVL_Stream*                    FStream;
119 
120             protected:
121                 VInt WriteUncompressedHeader(VBuffer Data , VInt ByteCount);
122                 VInt CompressAndWrite(VBuffer Data , VInt ByteCount);
123             public:
124                 Compressor();
125 
126                 void SetStream(IVL_Stream* Stream);
127                 VInt Write(VPointer Data , VInt ByteCount);
128             };
129 
130             class Decompressor : public AlgorithmBase , public VL_CompressedStream::Decompressor
131             {
132             protected:
133                 class Status : public VL_Base
134                 {
135                 protected:
136                     VByte                    OldWindow[WindowSize*3];
137                     VSize                    OldPosition;
138                     VInt                    OldUsedWindowSize;
139                     VSize                    OldWindowStartPosition;
140                 public:
141                     Status(Decompressor* aDecompressor);
142                     void Apply(Decompressor* aDecompressor);
143                 };
144             protected:
145                 IVL_Stream*                    FStream;
146 
147                 VInt DecompressBlock();
148             public:
149                 Decompressor();
150 
151                 void SetStream(IVL_Stream* Stream);
152                 VInt Read(VPointer Data , VInt ByteCount);
153                 VL_Base* CopyStatus();
154                 void ReplaceStatus(VL_Base* Status);
155                 void FreeStatus(VL_Base* Status);
156             };
157 
158         }
159     }
160 }
161 
162 #endif

    实现文件:
  1 #include "VL_Compression.h"
  2 
  3 namespace vl
  4 {
  5     namespace stream
  6     {
  7 
  8 /*********************************************************************************************************
  9 VL_CompressedStream
 10 *********************************************************************************************************/
 11 
 12         void VL_CompressedStream::Init(IVL_Stream* Stream , VBool Owned , Compressor* aCompressor)
 13         {
 14             FStream=Stream;
 15             FOwned=Owned;
 16             FMode=vomWrite;
 17             FCompressor=aCompressor;
 18             FCompressor->SetStream(FStream);
 19             FDecompressor=0;
 20         }
 21 
 22         void VL_CompressedStream::Init(IVL_Stream* Stream , VBool Owned , Decompressor* aDecompressor)
 23         {
 24             FStream=Stream;
 25             FOwned=Owned;
 26             FMode=vomRead;
 27             FCompressor=0;
 28             FDecompressor=aDecompressor;
 29             FDecompressor->SetStream(FStream);
 30         }
 31 
 32         VL_CompressedStream::VL_CompressedStream()
 33         {
 34             FStream=0;
 35             FOwned=false;
 36             FPosition=0;
 37         }
 38 
 39         VL_CompressedStream::~VL_CompressedStream()
 40         {
 41             Close();
 42             if(FCompressor)delete FCompressor;
 43             if(FDecompressor)delete FDecompressor;
 44         }
 45 
 46         VBool VL_CompressedStream::CanRead()
 47         {
 48             return IsAvailable() && (FMode==vomRead) && FStream->CanRead();
 49         }
 50 
 51         VBool VL_CompressedStream::CanPeek()
 52         {
 53             return IsAvailable() && (FMode==vomRead) && FStream->CanRead() && FStream->CanSeek();
 54         }
 55 
 56         VBool VL_CompressedStream::CanWrite()
 57         {
 58             return IsAvailable() && (FMode==vomWrite) && FStream->CanWrite();
 59         }
 60 
 61         VBool VL_CompressedStream::CanClose()
 62         {
 63             return IsAvailable() && FStream->CanClose();
 64         }
 65 
 66         VBool VL_CompressedStream::CanSeek()
 67         {
 68             return false;
 69         }
 70 
 71         VBool VL_CompressedStream::CanGrow()
 72         {
 73             return CanWrite();
 74         }
 75 
 76         VInt VL_CompressedStream::Read(VPointer Data , VInt ByteCount)
 77         {
 78             if(CanRead())
 79             {
 80                 ByteCount=FDecompressor->Read(Data,ByteCount);
 81                 FPosition+=ByteCount;
 82                 return ByteCount;
 83             }
 84             else
 85             {
 86                 return -1;
 87             }
 88         }
 89 
 90         VInt VL_CompressedStream::Peek(VPointer Data , VInt ByteCount)
 91         {
 92             if(CanPeek())
 93             {
 94                 VL_Base* Status=FDecompressor->CopyStatus();
 95                 VSize OldPosition=FPosition;
 96                 VSize OldStreamPosition=FStream->Position();
 97 
 98                 ByteCount=Read(Data,ByteCount);
 99 
100                 FStream->SeekFromBegin(OldStreamPosition);
101                 FPosition=OldPosition;
102                 FDecompressor->ReplaceStatus(Status);
103                 FDecompressor->FreeStatus(Status);
104 
105                 return ByteCount;
106             }
107             else
108             {
109                 return -1;
110             }
111         }
112 
113         VInt VL_CompressedStream::Write(VPointer Data , VInt ByteCount)
114         {
115             if(CanWrite())
116             {
117                 ByteCount=FCompressor->Write(Data,ByteCount);
118                 FPosition+=ByteCount;
119                 return ByteCount;
120             }
121             else
122             {
123                 return -1;
124             }
125         }
126 
127         void VL_CompressedStream::Close()
128         {
129             if(FStream)
130             {
131                 if(FOwned)
132                 {
133                     FStream->Close();
134                     delete FStream;
135                 }
136                 FStream=0;
137             }
138         }
139 
140         VBool VL_CompressedStream::IsAvailable()
141         {
142             return FStream && FStream->IsAvailable();
143         }
144 
145         VSize VL_CompressedStream::Position()
146         {
147             return IsAvailable()?FPosition:-1;
148         }
149 
150         VSize VL_CompressedStream::Size()
151         {
152             return -1;
153         }
154 
155         VSize VL_CompressedStream::MaxWriteSize()
156         {
157             return -1;
158         }
159 
160         void VL_CompressedStream::SeekFromBegin(VSize Offset)
161         {
162         }
163 
164         void VL_CompressedStream::SeekFromEnd(VSize Offset)
165         {
166         }
167 
168         void VL_CompressedStream::Seek(VSize Offset)
169         {
170         }
171 
172         VBool VL_CompressedStream::IsEnd()
173         {
174             return IsAvailable()?FStream->IsEnd():true;
175         }
176 
177 /*********************************************************************************************************
178 VL_LZ77Stream
179 *********************************************************************************************************/
180 
181         VL_LZ77Stream::VL_LZ77Stream(IVL_Stream* Stream , VLE_OpenMode Mode , VBool Owned)
182         {
183             switch(Mode)
184             {
185             case vomRead:
186                 Init(Stream,Owned,new LZ77Algorithms::Decompressor());
187                 break;
188             case vomWrite:
189                 Init(Stream,Owned,new LZ77Algorithms::Compressor());
190                 break;
191             }
192         }
193 
194 /*********************************************************************************************************
195 LZ77Algorithms::AlgorithmBase
196 *********************************************************************************************************/
197 
198         namespace LZ77Algorithms
199         {
200 
201             AlgorithmBase::AlgorithmBase()
202             {
203                 FPosition=0;
204                 FUsedWindowSize=0;
205                 FWindowStartPosition=0;
206             }
207 
208 /*********************************************************************************************************
209 LZ77Algorithms::Compressor
210 *********************************************************************************************************/
211 
212             struct CompressionRecord
213             {
214                 VBool Compressed;
215                 VInt Start;
216                 VInt Size;
217             };
218 
219             CompressionRecord TestCompression(VBuffer Window , VInt WindowSize , VInt ExtendedSize)
220             {
221                 CompressionRecord Record;
222                 Record.Compressed=false;
223                 Record.Start=0;
224                 Record.Size=1;
225                 for(VInt i=0;i<WindowSize;i++)
226                 {
227                     VBuffer Read1=Window+i;
228                     VBuffer Read2=Window+WindowSize;
229                     VInt CurrentSize=0;
230                     while(CurrentSize<ExtendedSize && *Read1++==*Read2++)
231                     {
232                         CurrentSize++;
233                     }
234                     if(CurrentSize>Record.Size)
235                     {
236                         Record.Compressed=true;
237                         Record.Start=i;
238                         Record.Size=CurrentSize;
239                         if(CurrentSize==ExtendedSize)
240                         {
241                             break;
242                         }
243                     }
244                 }
245                 return Record;
246             }
247 
248             VInt Compressor::WriteUncompressedHeader(VBuffer Data , VInt ByteCount)
249             {
250                 VInt UnusedWindowSize=WindowSize-FUsedWindowSize;
251                 if(UnusedWindowSize)
252                 {
253                     if(ByteCount>UnusedWindowSize)
254                     {
255                         ByteCount=UnusedWindowSize;
256                     }
257                     memcpy(FWindow+FUsedWindowSize,Data,ByteCount);
258                     FStream->Write(Data,ByteCount);
259                     FUsedWindowSize+=ByteCount;
260                     FPosition+=ByteCount;
261                     return ByteCount;
262                 }
263                 else
264                 {
265                     return 0;
266                 }
267             }
268 
269             VInt Compressor::CompressAndWrite(VBuffer Data , VInt ByteCount)
270             {
271                 VInt SelectedStart=-1;
272                 VInt EncodedLength=-1;
273                 if(ByteCount>MaxBlockSize*2)
274                 {
275                     ByteCount=MaxBlockSize*2;
276                 }
277                 memcpy(FWindow+WindowSize,Data,ByteCount);
278 
279                 VInt UncompressedBlockSize=0;
280                 VInt CompressedBlockStart=0;
281                 VInt CompressedBlockSize=0;
282                 VInt MaxUncompressedSize=MaxBlockSize<ByteCount?MaxBlockSize:ByteCount;
283                 while(UncompressedBlockSize<MaxUncompressedSize)
284                 {
285                     VInt ExtendedSize=ByteCount-UncompressedBlockSize;
286                     if(ExtendedSize>MaxBlockSize)
287                     {
288                         ExtendedSize=MaxBlockSize;
289                     }
290                     CompressionRecord Record=TestCompression(FWindow+UncompressedBlockSize,WindowSize,ExtendedSize);
291                     if(Record.Compressed)
292                     {
293                         CompressedBlockStart=Record.Start;
294                         CompressedBlockSize=Record.Size;
295                         break;
296                     }
297                     else
298                     {
299                         UncompressedBlockSize++;
300                     }
301                 }
302 
303                 if(UncompressedBlockSize)
304                 {
305                     VByte Block=(VByte)(UncompressedBlockSize-1);
306                     FStream->Write(&Block,sizeof(Block));
307                     FStream->Write(Data,UncompressedBlockSize);
308                     FPosition+=UncompressedBlockSize;
309                 }
310                 if(CompressedBlockSize)
311                 {
312                     VByte Block[2];
313                     Block[0]=((VByte)(CompressedBlockSize-1)) | 0x80;
314                     Block[1]=(VByte)CompressedBlockStart;
315                     FStream->Write(&Block,sizeof(Block));
316                     FPosition+=CompressedBlockSize;
317                 }
318 
319                 ByteCount=UncompressedBlockSize+CompressedBlockSize;
320                 memmove(FWindow,FWindow+ByteCount,WindowSize);
321                 FWindowStartPosition+=ByteCount;
322                 return ByteCount;
323             }
324 
325             Compressor::Compressor()
326             {
327                 FStream=0;
328             }
329 
330             void Compressor::SetStream(IVL_Stream* Stream)
331             {
332                 FStream=Stream;
333             }
334 
335             VInt Compressor::Write(VPointer Data , VInt ByteCount)
336             {
337                 VBuffer Buffer=(VBuffer)Data;
338                 VInt WrittenCount=0;
339                 {
340                     VInt Size=WriteUncompressedHeader(Buffer,ByteCount);
341                     Buffer+=Size;
342                     WrittenCount+=Size;
343                 }
344                 while(WrittenCount<ByteCount)
345                 {
346                     VInt Size=CompressAndWrite(Buffer,ByteCount-WrittenCount);
347                     if(Size==0)
348                     {
349                         break;
350                     }
351                     Buffer+=Size;
352                     WrittenCount+=Size;
353                 }
354                 return WrittenCount;
355             }
356 
357 /*********************************************************************************************************
358 LZ77Algorithms::Decompressor
359 *********************************************************************************************************/
360 
361             Decompressor::Status::Status(Decompressor* aDecompressor)
362             {
363                 OldPosition=aDecompressor->FPosition;
364                 OldUsedWindowSize=aDecompressor->FUsedWindowSize;
365                 OldWindowStartPosition=aDecompressor->FWindowStartPosition;
366                 memcpy(&OldWindow,&aDecompressor->FWindow,sizeof(OldWindow));
367             }
368 
369             void Decompressor::Status::Apply(Decompressor* aDecompressor)
370             {
371                 aDecompressor->FPosition=OldPosition;
372                 aDecompressor->FUsedWindowSize=OldUsedWindowSize;
373                 aDecompressor->FWindowStartPosition=OldWindowStartPosition;
374                 memcpy(&aDecompressor->FWindow,&OldWindow,sizeof(OldWindow));
375             }
376 
377             VInt Decompressor::DecompressBlock()
378             {
379                 VByte BlockHeader;
380                 if(FStream->Read(&BlockHeader,sizeof(BlockHeader))!=sizeof(BlockHeader))
381                 {
382                     return 0;
383                 }
384                 VByte BlockSize=(BlockHeader & 0x7F)+1;
385                 if(BlockHeader & 0x80)
386                 {
387                     VByte BlockStart;
388                     if(FStream->Read(&BlockStart,sizeof(BlockStart))!=sizeof(BlockStart))
389                     {
390                         return 0;
391                     }
392                     VBuffer Dest=FWindow+WindowSize;
393                     VBuffer Src=FWindow+BlockStart;
394                     for(VInt i=0;i<BlockSize;i++)
395                     {
396                         *Dest++=*Src++;
397                     }
398                 }
399                 else
400                 {
401                     if(FStream->Read(FWindow+WindowSize,BlockSize)!=BlockSize)
402                     {
403                         return 0;
404                     }
405                 }
406                 memmove(FWindow,FWindow+BlockSize,WindowSize);
407                 FWindowStartPosition+=BlockSize;
408                 return BlockSize;
409             }
410 
411             Decompressor::Decompressor()
412             {
413                 FStream=0;
414             }
415 
416             void Decompressor::SetStream(IVL_Stream* Stream)
417             {
418                 FStream=Stream;
419             }
420 
421             VInt Decompressor::Read(VPointer Data , VInt ByteCount)
422             {
423                 if(!FWindowStartPosition && !FUsedWindowSize)
424                 {
425                     FUsedWindowSize=FStream->Read(FWindow,WindowSize);
426                 }
427                 VBuffer Buffer=(VBuffer)Data;
428                 VInt WrittenCount=0;
429                 while(WrittenCount<ByteCount)
430                 {
431                     if(FWindowStartPosition+FUsedWindowSize==FPosition && FUsedWindowSize==WindowSize)
432                     {
433                         if(DecompressBlock()==0)
434                         {
435                             break;
436                         }
437                     }
438 
439                     VInt NeedCount=ByteCount-WrittenCount;
440                     VInt AllowSize=(VInt)(FWindowStartPosition+FUsedWindowSize-FPosition);
441                     VInt ReadSize=NeedCount<AllowSize?NeedCount:AllowSize;
442                     if(ReadSize)
443                     {
444                         memcpy(Buffer,FWindow+(FPosition-FWindowStartPosition),ReadSize);
445                         WrittenCount+=ReadSize;
446                         Buffer+=ReadSize;
447                         FPosition+=ReadSize;
448                     }
449                     else
450                     {
451                         break;
452                     }
453                 }
454                 return WrittenCount;
455             }
456 
457             VL_Base* Decompressor::CopyStatus()
458             {
459                 return new Status(this);
460             }
461 
462             void Decompressor::ReplaceStatus(VL_Base* Status)
463             {
464                 dynamic_cast<Decompressor::Status*>(Status)->Apply(this);
465             }
466 
467             void Decompressor::FreeStatus(VL_Base* Status)
468             {
469                 delete Status;
470             }
471 
472         }
473 
474     }
475 }
posted on 2009-01-05 09:47 陈梓瀚(vczh) 阅读(2686) 评论(5)  编辑 收藏 引用 所属分类: C++

评论:
# re: 实现了一个128长度窗口大小的LZ77压缩解压算法 2009-01-05 18:34 | 空明流转
轮子美

我就用用

iostreams就完事了。。。。  回复  更多评论
  
# re: 实现了一个128长度窗口大小的LZ77压缩解压算法 2009-01-06 18:30 | 星绽紫辉
我是菜鸟,没时间看代码,冒昧问一句:你那个“128长度窗口大小”和压缩解压文件有什么关系?  回复  更多评论
  
# re: 实现了一个128长度窗口大小的LZ77压缩解压算法 2009-01-06 19:59 | 陈梓瀚(vczh)
这是LZ77算法的一个参数。LZ77只能压缩窗口内重复的内容。  回复  更多评论
  
# re: 实现了一个128长度窗口大小的LZ77压缩解压算法 2010-11-14 20:03 | Husiwa
你好,请问这个压缩的模块在 3.0中去除了吗?
我看了下源文件中貌似没有这些文件  回复  更多评论
  
# re: 实现了一个128长度窗口大小的LZ77压缩解压算法 2010-11-15 04:30 | 陈梓瀚(vczh)
@Husiwa
嗯,因为我整个重写了,还来不及写到那里。2.0还留着在博客上,你还是可以找到的哈。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理