这个压缩流是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) 阅读(2716)
评论(5) 编辑 收藏 引用 所属分类:
C++