这份代码跟
上一次相比，修正了以下部分：
1、可修改的Window Size。压缩流会把Window Size写进去，解压流能够自动获取。
2、发现冗余的地方，每一个标记的压缩块节省了一位。
3、如果用户一次性写入的字节不够多则会缓存起来，上一版本则是直接压缩完。这样会丢失某些原本可以压缩的数据，因此修正。
这次修改主要用于缩小压缩后的数据的尺寸。
头文件：
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 ：Canonical Huffman压缩流
12 函数：
13 *******************************************************************************/
14 #ifndef VL_COMPRESSION
15 #define VL_COMPRESSION
16
17 #include "VL_Stream.h"
18 #include "VL_DataAccess.h"
19
20 namespace vl
21 {
22 namespace stream
23 {
24 using namespace collection;
25
26 /*********************************************************************************************************
27 压缩流
28 *********************************************************************************************************/
29
30 class VL_CompressedStream : public VL_Base , public IVL_Stream
31 {
32 public:
33 enum VLE_OpenMode
34 {
35 vomRead,
36 vomWrite,
37 };
38
39 class Compressor : public IVL_Interface
40 {
41 public:
42 virtual void SetStream(IVL_Stream* Stream)=0;
43 virtual VInt Write(VPointer Data , VInt ByteCount)=0;
44 };
45
46 class Decompressor : public IVL_Interface
47 {
48 public:
49 virtual void SetStream(IVL_Stream* Stream)=0;
50 virtual VInt Read(VPointer Data , VInt ByteCount)=0;
51 };
52 protected:
53 IVL_Stream* FStream;
54 VBool FOwned;
55 VLE_OpenMode FMode;
56 VSize FPosition;
57 Compressor* FCompressor;
58 Decompressor* FDecompressor;
59
60 VBuffer FPeekBuffer;
61 VInt FPeekBufferSize;
62 VInt FAvailablePeekSize;
63
64 void Init(IVL_Stream* Stream , VBool Owned , Compressor* aCompressor);
65 void Init(IVL_Stream* Stream , VBool Owned , Decompressor* aDecompressor);
66
67 VL_CompressedStream();
68 public:
69 ~VL_CompressedStream();
70
71 VBool CanRead();
72 VBool CanPeek();
73 VBool CanWrite();
74 VBool CanClose();
75 VBool CanSeek();
76 VBool CanGrow();
77 VInt Read(VPointer Data , VInt ByteCount);
78 VInt Peek(VPointer Data , VInt ByteCount);
79 VInt Write(VPointer Data , VInt ByteCount);
80 void Close();
81 VBool IsAvailable();
82 VSize Position();
83 VSize Size();
84 VSize MaxWriteSize();
85 void SeekFromBegin(VSize Offset);
86 void SeekFromEnd(VSize Offset);
87 void Seek(VSize Offset);
88 VBool IsEnd();
89 };
90
91 class VL_LZ77Stream : public VL_CompressedStream
92 {
93 public:
94 enum VLE_WindowMode
95 {
96 vwm128=7,
97 vwm256,
98 vwm512,
99 vwm1024,
100 vwm2048,
101 vwmAuto=0,
102 vwmMin=vwm128,
103 vwmMax=vwm2048
104
105 };
106
107 VL_LZ77Stream(IVL_Stream* Stream , VLE_OpenMode OpenMode , VLE_WindowMode WindowMode=vwmAuto , VBool Owned=false);
108 };
109
110 /*********************************************************************************************************
111 LZ77压缩算法
112
113 第一个字节：window level, window size = 2 ^ window level
114 压缩块描述：
115 [0:wild][A:byte count-1][data]
116 [1:encoded][A:byte count-1][B:index]
117 A : 0 - (WindowSize-1)
118 B : 0 - (WindowSize-1)
119 *********************************************************************************************************/
120
121 namespace LZ77Algorithms
122 {
123 class AlgorithmBase : public VL_Base
124 {
125 protected:
126
127 VInt WindowSize;
128 VInt MaxBlockSize;
129 VInt DoubleMaxBlockSize;
130 VInt ByteCountBitCount;
131 VInt ByteIndexBitCount;
132
133 VBuffer FWindow; /*滑动窗口，尺寸=WindowSize*3*/
134 VSize FPosition; /*当前位置*/
135 VInt FUsedWindowSize; /*窗口有效数据大小*/
136 VSize FWindowStartPosition; /*窗口的起始位置*/
137
138 AlgorithmBase(VInt WindowSizeLevel); /*窗口尺寸为2的WindowSizeLevel次方*/
139 ~AlgorithmBase();
140 };
141
142 class Compressor : public AlgorithmBase , public VL_CompressedStream::Compressor
143 {
144 protected:
145 VL_BitWriter* FBitWriter;
146 VInt FUsedFullWindowSize; /*缓冲区有效数据大小*/
147
148 VInt CompressAndWrite(VInt ByteCount);
149 public:
150 Compressor(VInt WindowSizeLevel);
151 ~Compressor();
152
153 void SetStream(IVL_Stream* Stream);
154 VInt Write(VPointer Data , VInt ByteCount);
155 };
156
157 class Decompressor : public AlgorithmBase , public VL_CompressedStream::Decompressor
158 {
159 protected:
160 VL_BitReader* FReader;
161
162 VInt DecompressBlock();
163 public:
164 Decompressor(VInt WindowSizeLevel);
165 ~Decompressor();
166
167 void SetStream(IVL_Stream* Stream);
168 VInt Read(VPointer Data , VInt ByteCount);
169 };
170
171 }
172 }
173 }
174
175 #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 FPeekBuffer=0;
39 FPeekBufferSize=0;
40 FAvailablePeekSize=0;
41 }
42
43 VL_CompressedStream::~VL_CompressedStream()
44 {
45 Close();
46 }
47
48 VBool VL_CompressedStream::CanRead()
49 {
50 return IsAvailable() && (FMode==vomRead) && FStream->CanRead();
51 }
52
53 VBool VL_CompressedStream::CanPeek()
54 {
55 return IsAvailable() && (FMode==vomRead) && FStream->CanRead();
56 }
57
58 VBool VL_CompressedStream::CanWrite()
59 {
60 return IsAvailable() && (FMode==vomWrite) && FStream->CanWrite();
61 }
62
63 VBool VL_CompressedStream::CanClose()
64 {
65 return IsAvailable() && FStream->CanClose();
66 }
67
68 VBool VL_CompressedStream::CanSeek()
69 {
70 return false;
71 }
72
73 VBool VL_CompressedStream::CanGrow()
74 {
75 return CanWrite();
76 }
77
78 VInt VL_CompressedStream::Read(VPointer Data , VInt ByteCount)
79 {
80 if(CanRead())
81 {
82 if(!FAvailablePeekSize)
83 {
84 ByteCount=FDecompressor->Read(Data,ByteCount);
85 FPosition+=ByteCount;
86 return ByteCount;
87 }
88 else if(FAvailablePeekSize>=ByteCount)
89 {
90 memcpy(Data,FPeekBuffer,ByteCount);
91 FAvailablePeekSize-=ByteCount;
92 memmove(FPeekBuffer,FPeekBuffer+ByteCount,FAvailablePeekSize);
93 FPosition+=ByteCount;
94 return ByteCount;
95 }
96 else
97 {
98 VBuffer DataBuffer=(VBuffer)Data;
99 memcpy(DataBuffer,FPeekBuffer,FAvailablePeekSize);
100 ByteCount=FAvailablePeekSize+FDecompressor->Read(DataBuffer+FAvailablePeekSize,ByteCount-FAvailablePeekSize);
101 FAvailablePeekSize=0;
102 FPosition+=ByteCount;
103 return ByteCount;
104 }
105 }
106 else
107 {
108 return -1;
109 }
110 }
111
112 VInt VL_CompressedStream::Peek(VPointer Data , VInt ByteCount)
113 {
114 if(CanPeek())
115 {
116 VInt ExtendSize=ByteCount-FAvailablePeekSize;
117 if(ExtendSize>0)
118 {
119 if(FPeekBufferSize<ByteCount)
120 {
121 VBuffer NewPeekBuffer=new VByte[ByteCount];
122 if(FPeekBuffer)
123 {
124 memcpy(NewPeekBuffer,FPeekBuffer,FAvailablePeekSize);
125 delete[] FPeekBuffer;
126 }
127 FPeekBuffer=NewPeekBuffer;
128 FPeekBufferSize=ByteCount;
129 }
130 FAvailablePeekSize+=FDecompressor->Read(FPeekBuffer+FAvailablePeekSize,ExtendSize);
131 }
132 if(FAvailablePeekSize<ByteCount)
133 {
134 ByteCount=FAvailablePeekSize;
135 }
136 memcpy(Data,FPeekBuffer,ByteCount);
137 return ByteCount;
138 }
139 else
140 {
141 return -1;
142 }
143 }
144
145 VInt VL_CompressedStream::Write(VPointer Data , VInt ByteCount)
146 {
147 if(CanWrite())
148 {
149 ByteCount=FCompressor->Write(Data,ByteCount);
150 FPosition+=ByteCount;
151 return ByteCount;
152 }
153 else
154 {
155 return -1;
156 }
157 }
158
159 void VL_CompressedStream::Close()
160 {
161 if(FCompressor)
162 {
163 delete FCompressor;
164 FCompressor=0;
165 }
166 if(FDecompressor)
167 {
168 delete FDecompressor;
169 FDecompressor=0;
170 }
171 if(FPeekBuffer)
172 {
173 delete[] FPeekBuffer;
174 FPeekBuffer=0;
175 }
176 if(FStream)
177 {
178 if(FOwned)
179 {
180 FStream->Close();
181 delete FStream;
182 FOwned=false;
183 }
184 FStream=0;
185 }
186 }
187
188 VBool VL_CompressedStream::IsAvailable()
189 {
190 return FStream && FStream->IsAvailable();
191 }
192
193 VSize VL_CompressedStream::Position()
194 {
195 return IsAvailable()?FPosition:-1;
196 }
197
198 VSize VL_CompressedStream::Size()
199 {
200 return -1;
201 }
202
203 VSize VL_CompressedStream::MaxWriteSize()
204 {
205 return -1;
206 }
207
208 void VL_CompressedStream::SeekFromBegin(VSize Offset)
209 {
210 }
211
212 void VL_CompressedStream::SeekFromEnd(VSize Offset)
213 {
214 }
215
216 void VL_CompressedStream::Seek(VSize Offset)
217 {
218 }
219
220 VBool VL_CompressedStream::IsEnd()
221 {
222 return IsAvailable()?FStream->IsEnd():true;
223 }
224
225 /*********************************************************************************************************
226 VL_LZ77Stream
227 *********************************************************************************************************/
228
229 VL_LZ77Stream::VL_LZ77Stream(IVL_Stream* Stream , VLE_OpenMode OpenMode , VLE_WindowMode WindowMode , VBool Owned)
230 {
231 switch(OpenMode)
232 {
233 case vomRead:
234 if(WindowMode==vwmAuto)
235 {
236 VByte BitCount=0;
237 if(Stream->Read(&BitCount,sizeof(BitCount))==sizeof(BitCount))
238 {
239 if(BitCount>=vwmMin && BitCount<=vwmMax)
240 {
241 Init(Stream,Owned,new LZ77Algorithms::Decompressor(BitCount));
242 }
243 }
244 }
245 break;
246 case vomWrite:
247 if(WindowMode==vwmAuto)
248 {
249 WindowMode=vwm1024;
250 }
251 if(WindowMode>=vwmMin && WindowMode<=vwmMax)
252 {
253 VByte BitCount=(VByte)WindowMode;
254 Stream->Write(&BitCount,sizeof(BitCount));
255 Init(Stream,Owned,new LZ77Algorithms::Compressor(WindowMode));
256 }
257 break;
258 }
259 }
260
261 /*********************************************************************************************************
262 LZ77Algorithms::AlgorithmBase
263 *********************************************************************************************************/
264
265 namespace LZ77Algorithms
266 {
267
268 AlgorithmBase::AlgorithmBase(VInt WindowSizeLevel)
269 {
270 WindowSize=1<<WindowSizeLevel;
271 MaxBlockSize=WindowSize;
272 DoubleMaxBlockSize=MaxBlockSize*2;
273 ByteCountBitCount=WindowSizeLevel;
274 ByteIndexBitCount=WindowSizeLevel;
275
276 FWindow=new VByte[WindowSize*3];
277 FPosition=0;
278 FUsedWindowSize=0;
279 FWindowStartPosition=0;
280 }
281
282 AlgorithmBase::~AlgorithmBase()
283 {
284 delete[] FWindow;
285 }
286
287 /*********************************************************************************************************
288 LZ77Algorithms::Compressor
289 *********************************************************************************************************/
290
291 struct CompressionRecord
292 {
293 VBool Compressed;
294 VInt Start;
295 VInt Size;
296 };
297
298 // 2 <= compressed size <= extended size
299 CompressionRecord TestCompression(VBuffer Window , VInt WindowSize , VInt ExtendedSize)
300 {
301 CompressionRecord Record;
302 Record.Compressed=false;
303 Record.Start=0;
304 Record.Size=1;
305 for(VInt i=0;i<WindowSize;i++)
306 {
307 VBuffer Read1=Window+i;
308 VBuffer Read2=Window+WindowSize;
309 VInt CurrentSize=0;
310 while(CurrentSize<ExtendedSize && *Read1++==*Read2++)
311 {
312 CurrentSize++;
313 }
314 if(CurrentSize>Record.Size)
315 {
316 Record.Compressed=true;
317 Record.Start=i;
318 Record.Size=CurrentSize;
319 if(CurrentSize==ExtendedSize)
320 {
321 break;
322 }
323 }
324 }
325 return Record;
326 }
327
328 // 1 <= byte count <= window size
329 // 0 <= compressed index < window size
330 // 2 <= compressed size <= window size
331 // 1 <= uncompressed size <= window size
332 VInt Compressor::CompressAndWrite(VInt ByteCount)
333 {
334 VInt SelectedStart=-1;
335 VInt EncodedLength=-1;
336 if(ByteCount>DoubleMaxBlockSize)
337 {
338 ByteCount=DoubleMaxBlockSize;
339 }
340
341 VInt UncompressedBlockSize=0;
342 VInt CompressedBlockStart=0;
343 VInt CompressedBlockSize=0;
344 VInt MaxUncompressedSize=MaxBlockSize<ByteCount?MaxBlockSize:ByteCount;
345 while(UncompressedBlockSize<MaxUncompressedSize)
346 {
347 VInt ExtendedSize=ByteCount-UncompressedBlockSize;
348 if(ExtendedSize>MaxBlockSize)
349 {
350 ExtendedSize=MaxBlockSize;
351 }
352
353 VBuffer VirtualWindow=FWindow;
354 VInt VirtualWindowSize=FUsedWindowSize+UncompressedBlockSize;
355 if(VirtualWindowSize>WindowSize)
356 {
357 VirtualWindow+=VirtualWindowSize-WindowSize;
358 VirtualWindowSize=WindowSize;
359 }
360
361 CompressionRecord Record=TestCompression(VirtualWindow,VirtualWindowSize,ExtendedSize);
362 if(Record.Compressed)
363 {
364 CompressedBlockStart=Record.Start;
365 CompressedBlockSize=Record.Size;
366 break;
367 }
368 else
369 {
370 UncompressedBlockSize++;
371 }
372 }
373
374 if(UncompressedBlockSize)
375 {
376 FBitWriter->WriteBit(false);
377 FBitWriter->WriteNumber(UncompressedBlockSize-1,ByteCountBitCount);
378 for(VInt i=0;i<UncompressedBlockSize;i++)
379 {
380 FBitWriter->WriteNumber(FWindow[FUsedWindowSize+i],8);
381 }
382 FPosition+=UncompressedBlockSize;
383 }
384 if(CompressedBlockSize)
385 {
386 FBitWriter->WriteBit(true);
387 FBitWriter->WriteNumber(CompressedBlockSize-1,ByteCountBitCount);
388 FBitWriter->WriteNumber(CompressedBlockStart,ByteIndexBitCount);
389 FPosition+=CompressedBlockSize;
390 }
391
392 ByteCount=UncompressedBlockSize+CompressedBlockSize;
393 FUsedWindowSize+=ByteCount;
394 if(FUsedWindowSize>WindowSize)
395 {
396 VInt Remain=FUsedWindowSize-WindowSize;
397 VInt CopySize=FUsedFullWindowSize-Remain;
398
399 memmove(FWindow,FWindow+Remain,CopySize);
400 FUsedWindowSize=WindowSize;
401 FWindowStartPosition+=Remain;
402 FUsedFullWindowSize=CopySize;
403 }
404 return ByteCount;
405 }
406
407 Compressor::Compressor(VInt WindowSizeLevel):AlgorithmBase(WindowSizeLevel)
408 {
409 FBitWriter=0;
410 FUsedFullWindowSize=0;
411 }
412
413 Compressor::~Compressor()
414 {
415 while(FUsedFullWindowSize>FUsedWindowSize)
416 {
417 VInt Size=CompressAndWrite(FUsedFullWindowSize-FUsedWindowSize);
418 if(Size==0)
419 {
420 break;
421 }
422 }
423 SetStream(0);
424 }
425
426 void Compressor::SetStream(IVL_Stream* Stream)
427 {
428 if(FBitWriter)
429 {
430 delete FBitWriter;
431 FBitWriter=0;
432 }
433 if(Stream)
434 {
435 FBitWriter=new VL_BitWriter(Stream,false);
436 }
437 }
438
439 VInt Compressor::Write(VPointer Data , VInt ByteCount)
440 {
441 VInt WrittenCount=0;
442 VBuffer DataBuffer=(VBuffer)Data;
443 while(WrittenCount<ByteCount)
444 {
445 VInt CopySize=WindowSize*3-FUsedFullWindowSize;
446 if(CopySize)
447 {
448 VInt DataSize=ByteCount-WrittenCount;
449 if(CopySize>DataSize)
450 {
451 CopySize=DataSize;
452 }
453 memcpy(FWindow+FUsedFullWindowSize,DataBuffer,CopySize);
454 DataBuffer+=CopySize;
455 FUsedFullWindowSize+=CopySize;
456 WrittenCount+=CopySize;
457 }
458
459 VInt Size=CompressAndWrite(FUsedFullWindowSize-FUsedWindowSize);
460 if(Size==0)
461 {
462 break;
463 }
464 }
465 return WrittenCount;
466 }
467
468 /*********************************************************************************************************
469 LZ77Algorithms::Decompressor
470 *********************************************************************************************************/
471
472 VInt Decompressor::DecompressBlock()
473 {
474 VBool BlockCompressed=false;
475 VUInt BlockSize=0;
476 if(!FReader->ReadBit(BlockCompressed))
477 {
478 return 0;
479 }
480 if(!FReader->ReadNumber(BlockSize,ByteCountBitCount))
481 {
482 return 0;
483 }
484 BlockSize++;
485 if(BlockCompressed)
486 {
487 VUInt BlockStart=0;
488 if(!FReader->ReadNumber(BlockStart,ByteIndexBitCount))
489 {
490 return 0;
491 }
492 VBuffer Dest=FWindow+FUsedWindowSize;
493 VBuffer Src=FWindow+BlockStart;
494 VInt Counter=BlockSize;
495 while(Counter--)
496 {
497 *Dest++=*Src++;
498 }
499 }
500 else
501 {
502 VUInt ByteContent=0;
503 VBuffer WriteEntry=FWindow+FUsedWindowSize;
504 VInt Counter=BlockSize;
505 while(Counter--)
506 {
507 if(!FReader->ReadNumber(ByteContent,8))
508 {
509 return 0;
510 }
511 *WriteEntry++=(VByte)ByteContent;
512 }
513 }
514 FUsedWindowSize+=BlockSize;
515 if(FUsedWindowSize>WindowSize)
516 {
517 VInt MoveSize=FUsedWindowSize-WindowSize;
518 memmove(FWindow,FWindow+MoveSize,WindowSize);
519 FUsedWindowSize=WindowSize;
520 FWindowStartPosition+=MoveSize;
521 }
522 return BlockSize;
523 }
524
525 Decompressor::Decompressor(VInt WindowSizeLevel):AlgorithmBase(WindowSizeLevel)
526 {
527 FReader=0;
528 }
529
530 Decompressor::~Decompressor()
531 {
532 SetStream(0);
533 }
534
535 void Decompressor::SetStream(IVL_Stream* Stream)
536 {
537 if(FReader)
538 {
539 delete FReader;
540 FReader=0;
541 }
542 if(Stream)
543 {
544 FReader=new VL_BitReader(Stream,false);
545 }
546 }
547
548 VInt Decompressor::Read(VPointer Data , VInt ByteCount)
549 {
550 VBuffer Buffer=(VBuffer)Data;
551 VInt WrittenCount=0;
552 while(WrittenCount<ByteCount)
553 {
554 if(FWindowStartPosition+FUsedWindowSize==FPosition)
555 {
556 if(DecompressBlock()==0)
557 {
558 break;
559 }
560 }
561
562 VInt NeedCount=ByteCount-WrittenCount;
563 VInt AllowSize=(VInt)(FWindowStartPosition+FUsedWindowSize-FPosition);
564 VInt ReadSize=NeedCount<AllowSize?NeedCount:AllowSize;
565 if(ReadSize)
566 {
567 memcpy(Buffer,FWindow+(FPosition-FWindowStartPosition),ReadSize);
568 WrittenCount+=ReadSize;
569 Buffer+=ReadSize;
570 FPosition+=ReadSize;
571 }
572 else
573 {
574 break;
575 }
576 }
577 return WrittenCount;
578 }
579
580 }
581
582 }
583 }
posted on 2009-01-06 23:35
陈梓瀚(vczh) 阅读(3000)
评论(6) 编辑 收藏 引用 所属分类:
C++