TKYQuickPack(快速壓縮類), TKYQuickUnpack(快速解壓縮類), 源碼如下:
KYQuickPack.h 文件
1 // =======================================
2 // Unit : 快速壓縮/解壓縮單元 (KYQuickPack.h)
3 // Version: 3.0.0.0 (build 2011.03.18)
4 // Author : Kyee Ye
5 // Email : kyee_ye(at)126.com
6 // Copyright (C) Kyee workroom
7 // =======================================
8
9 #ifndef _KYQuickPack_H_
10 #define _KYQuickPack_H_
11
12 #include "KYPackObj.h"
13
14 // KYLib 2.0 開始使用 KYLib 命名空間
15 namespace KYLib
16 {
17
18 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
19
20 /* TKYQuickPack - 快速壓縮類(基于LZRW壓縮算法) */
21
22 class TKYQuickPack: public TKYCustomPack
23 {
24 public:
25 TKYQuickPack();
26 virtual ~TKYQuickPack();
27
28 // 屬性
29 bool IsPacking() const { return FIsPacking; } // default: false
30
31 // 重置
32 virtual void Reset();
33
34 // 壓縮緩沖區
35 // 1. ABuffer 存放 ASize 字節的待壓縮數據
36 // 2. ADest 存放壓縮后的數據, 緩沖區尺寸至少為 ASize
37 // 3. 若返回值 > 0 表示壓縮后數據的尺寸
38 // 4. 若返回值為 0 表示壓縮失敗, 即待壓縮數據無法再壓縮
39 // 5. 若返回值為 -1 表示參數不合法
40 // 6. 若返回值為 -2 表示壓縮失敗, 原因是正在壓縮
41 virtual long Pack(const char* ABuffer, char* ADest, long ASize);
42
43 private:
44 void DoCopy(const char* ABuffer, long ASize);
45 bool DoMatch(Byte* APos, Byte* AEnd, Word& AOffset, Byte& ADepth);
46
47 private:
48 Word FHash[4096]; // 哈希表
49 char FContext[4096]; // 壓縮數據的上下文
50 Longword FLastSize; // 上一次 pack 結束后的尺寸
51 bool FIsPacking; // 判斷是否正在壓縮
52 bool FIsOverflow; // 判斷上下文列表是否溢出
53 };
54
55 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
56
57 /* TKYQuickUnpack - 快速解壓縮類(基于LZRW壓縮算法) */
58
59 class TKYQuickUnpack: public TKYCustomUnpack
60 {
61 public:
62 TKYQuickUnpack();
63 virtual ~TKYQuickUnpack();
64
65 // 屬性
66 bool IsUnpacking() const { return FIsUnpacking; }// default: false
67
68 // 重置
69 virtual void Reset();
70
71 // 解壓縮緩沖區
72 // 1. 若 AIsPacked 為 false 表示數據未壓縮, 即為解壓縮的上下文相關性而操作,
73 // 但不會拷貝數據到 ADest, 并返回值為 0
74 // 2. ABuffer 存放 ASize 字節的已壓縮數據
75 // 3. ADest 存放解壓縮后的數據, ADestSize >= ASize
76 // 4. 若返回值 > 0 表示解壓縮后數據的尺寸
77 // 5. 若返回值為 0 表示解壓縮失敗, 可能 ADestSize 太小或數據未壓縮
78 // 6. 若返回值為 -1 表示參數不合法
79 // 7. 若返回值為 -2 表示解壓縮失敗, 原因是數據已損壞
80 // 8. 若返回值為 -3 表示解壓縮失敗, 原因是正在解壓縮
81 virtual long Unpack(const char* ABuffer, long ASize,
82 char* ADest, long ADestSize,
83 bool AIsPacked = true);
84
85 private:
86 void DoCopy(const char* ABuffer, long ASize);
87 bool DoInsert(char* &APos, Word AOffset, Byte ADepth);
88
89 private:
90 char FContext[4096]; // 已解壓的上下文
91 Longword FLastSize; // 上一次 unpack 結束后的尺寸
92 bool FIsOverflow; // 判斷上下文列表是否溢出
93 bool FIsUnpacking; // 判斷是否正在解壓縮
94 };
95
96 }
97
98 #endif
99
KYQuickPack.cpp 文件:
1 // =======================================
2 // Unit : 快速壓縮/解壓縮單元 (KYQuickPack.cpp)
3 // Version: 3.0.0.0 (build 2011.03.18)
4 // Author : Kyee Ye
5 // Email : kyee_ye(at)126.com
6 // Copyright (C) Kyee workroom
7 // =======================================
8
9 #include "KYQuickPack.h"
10
11 // KYLib 2.0 開始使用 KYLib 命名空間
12 namespace KYLib
13 {
14
15 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
16
17 /* 常量定義 */
18
19 // 常量
20 #define Max_Depth 18 // 最大匹配深度
21 #define Max_Offset 4096 // 最大偏移量
22 #define Mask_Index 0x7FFF // 索引的掩碼
23 #define Mask_Hash 0x0FFF // 哈希的掩碼
24 #define Hash_RandomGene 45673 // 哈希的隨機因子必須是素數,
25 // 且除以 4096 的商和余數也是素數
26
27 // 布爾位值
28 static const Byte Bits_Bool[8] = {0x80, 0x40, 0x20, 0x10,
29 0x08, 0x04, 0x02, 0x01};
30
31 // 取 Word 的高 8 位字節
32 static inline Byte HiByte(Word AValue)
33 {
34 return (Byte)(AValue >> 8);
35 }
36
37 // 取 Word 的低 8 位字節
38 static inline Byte LoByte(Word AValue)
39 {
40 return (Byte)AValue;
41 }
42
43 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
44
45 /* TKYQuickPack - 快速壓縮類(基于LZRW壓縮算法) */
46
47 // ---------------- 構造函數和析構函數 ----------------
48 // 構造函數
49 TKYQuickPack::TKYQuickPack()
50 {
51 // 清空
52 FIsPacking = false;
53 Reset();
54 }
55
56 // 析構函數
57 TKYQuickPack::~TKYQuickPack()
58 {
59 }
60
61 // ---------------- 私有函數 ----------------
62 // 拷貝上下文
63 void TKYQuickPack::DoCopy(const char* ABuffer, long ASize)
64 {
65 // 初始化
66 long intSize;
67 char* pDest = (char*)FContext;
68 char* pPos = (char*)ABuffer;
69 char* pEnd = pPos + ASize;
70
71 // 檢查尺寸
72 if (ASize >= Max_Offset)
73 memcpy(pDest, pEnd - Max_Offset, Max_Offset);
74 else if ((FLastSize >= Max_Offset) || FIsOverflow)
75 {
76 intSize = Max_Offset - ASize;
77 memmove(pDest, pDest + ASize, intSize);
78 memcpy(pDest + intSize, pPos, ASize);
79 }
80 else if (FLastSize + ASize > Max_Offset)
81 {
82 intSize = Max_Offset - ASize;
83 memmove(pDest, pDest + (FLastSize - intSize), intSize);
84 memcpy(pDest + intSize, pPos, ASize);
85 }
86 else
87 memcpy(pDest + FLastSize, pPos, ASize);
88
89 // 修改最后尺寸
90 FSize = FLastSize + ASize;
91 FIsOverflow = FIsOverflow || (FSize < FLastSize);
92 FLastSize = FSize;
93 }
94
95 // 索引項匹配
96 bool TKYQuickPack::DoMatch(Byte* APos, Byte* AEnd, Word& AOffset, Byte& ADepth)
97 {
98 // 初始化
99 bool result = false;
100 Word wIndex, wHash, wValue;
101
102 // 計算 Hash 值
103 wHash = ((Word)APos[0] << 8) ^ ((Word)APos[1] << 4) ^ (Word)APos[2];
104 wHash = ((wHash * Hash_RandomGene) >> 4) & Mask_Hash;
105 wValue = FHash[wHash];
106 wIndex = (Word)FSize & Mask_Index;
107 AOffset = (wIndex - wValue) & Mask_Index;
108 FHash[wHash]= wIndex;
109
110 // 判斷偏移量是否有效
111 if ((wValue <= Mask_Index) && (AOffset < Max_Offset) && (AOffset != 0))
112 {
113 // 初始化
114 Word wDepth = (Word)Min(AEnd - APos, Max_Depth);
115 Byte* pPos = APos;
116 Byte* pEnd = APos + wDepth;
117 Byte* pDest;
118
119 // 檢查是否超出上下文
120 if (FSize - FLastSize >= AOffset)
121 {
122 pDest = APos - AOffset;
123 while ((pPos < pEnd) && (*pPos == *pDest))
124 {
125 pPos++;
126 pDest++;
127 }
128 }
129 else
130 {
131 // 初始化
132 Word wSize = (Word)(FSize - FLastSize); // (FSize - FLastSize < AOffset)
133 Word wFront = AOffset - wSize;
134
135 // 計算起始位置
136 pDest = (Byte*)FContext;
137 if ((FLastSize >= Max_Offset) || FIsOverflow)
138 pDest += Max_Offset - wFront;
139 else
140 pDest += FLastSize - wFront;
141
142 // 判斷是否分二部分比較
143 if (wFront < wDepth)
144 {
145 // 初始化
146 Byte* pDestEnd = pDest + wFront;
147
148 // 前半部分比較
149 while ((pDest < pDestEnd) && (*pPos == *pDest))
150 {
151 pPos++;
152 pDest++;
153 }
154
155 // 判斷是否需要繼續匹配
156 if (pDest == pDestEnd)
157 {
158 pDest = APos - wSize;
159 while ((pPos < pEnd) && (*pPos == *pDest))
160 {
161 pPos++;
162 pDest++;
163 }
164 }
165 }
166 else
167 while ((pPos < pEnd) && (*pPos == *pDest))
168 {
169 pPos++;
170 pDest++;
171 }
172 }
173
174 // 檢查匹配長度
175 ADepth = (Byte)(pPos - APos);
176 result = (ADepth >= 3);
177 }
178
179 // 返回結果
180 return result;
181 }
182
183 // ---------------- 保護函數 ----------------
184
185 // ---------------- 公有函數 ----------------
186 // 重置
187 void TKYQuickPack::Reset()
188 {
189 if (!FIsPacking)
190 {
191 // 置空
192 FSize = 0;
193 FLastSize = 0;
194 FIsOverflow = false;
195
196 // 初始化哈希表
197 memset(FHash, -1, sizeof(FHash));
198 }
199 }
200
201 // 壓縮緩沖區
202 // 1. ABuffer 存放 ASize 字節的待壓縮數據
203 // 2. ADest 存放壓縮后的數據, 緩沖區尺寸至少為 ASize
204 // 3. 若返回值 > 0 表示壓縮后數據的尺寸
205 // 4. 若返回值為 0 表示壓縮失敗, 即待壓縮數據無法再壓縮
206 // 5. 若返回值為 -1 表示參數不合法
207 // 6. 若返回值為 -2 表示壓縮失敗, 原因是正在壓縮
208 long TKYQuickPack::Pack(const char* ABuffer, char* ADest, long ASize)
209 {
210 // 檢查是否正在壓縮
211 if (FIsPacking)
212 return -2;
213
214 // 置壓縮狀態
215 FIsPacking = true;
216
217 // 初始化
218 long result = 0;
219
220 // 檢查參數
221 if ((ASize <= 0) || (ABuffer == NULL) || (ADest == NULL))
222 result = -1;
223 else
224 {
225 try
226 {
227 // 初始化
228 Word wSize, wOffset;
229 Byte* pSame;
230 Byte* pLast;
231 Byte* pPos = (Byte*)ABuffer;
232 Byte* pEnd = pPos + ASize - 2;
233 Byte* pBuffEnd = pPos + ASize;
234 Byte* pFlag = (Byte*)ADest;
235 Byte* pDest = pFlag + 1;
236 Byte* pDestEnd = pFlag + ASize;
237 Byte byteDepth= 0;
238 Byte byteFlag = 0;
239 Byte byteBit = 0;
240 bool boolOver = false;
241
242 // 循環匹配
243 while (pPos < pBuffEnd)
244 {
245 // 檢查標志位是否已滿
246 if (byteBit == 8)
247 {
248 *pFlag = byteFlag;
249 pFlag = pDest++;
250 byteBit = 0;
251 byteFlag = 0;
252 }
253
254 // 檢查是否相同數據
255 pLast = Min(pBuffEnd, pPos + Max_Offset + 8);
256 pSame = pPos + 1;
257 while ((pSame < pLast) && (*pSame == *pPos))
258 pSame++;
259
260 // 檢查相同數據尺寸是否大于等于 8
261 wSize = pSame - pPos - 1;
262 if (wSize >= 8)
263 {
264 if (pDest < pDestEnd - 4)
265 {
266 wSize -= 8;
267 *(pDest++) = 0;
268 *(pDest++) = HiByte(wSize);
269 *(pDest++) = LoByte(wSize);
270 *(pDest++) = *pPos;
271 byteFlag |= Bits_Bool[byteBit];
272 FSize += wSize + 9;
273 pPos = pSame;
274 }
275 else
276 {
277 boolOver = true;
278 break;
279 }
280 }
281 else if ((pPos < pEnd) && DoMatch(pPos, pBuffEnd, wOffset, byteDepth))
282 {
283 if (pDest < pDestEnd - 2)
284 {
285 wOffset = (wOffset << 4) + (byteDepth - 3);
286 *(pDest++) = HiByte(wOffset);
287 *(pDest++) = LoByte(wOffset);
288 byteFlag |= Bits_Bool[byteBit];
289 FSize += byteDepth;
290 pPos += byteDepth;
291 }
292 else
293 {
294 boolOver = true;
295 break;
296 }
297 }
298 else if (pDest < pDestEnd)
299 {
300 *(pDest++) = *(pPos++);
301 FSize++;
302 }
303 else
304 {
305 boolOver = true;
306 break;
307 }
308
309 // 位數加 1
310 byteBit++;
311 }
312
313 // 檢查是否溢出
314 if (!boolOver && (pDest < pDestEnd))
315 {
316 *pFlag = byteFlag;
317 result = pDest - (Byte*)ADest;
318 }
319 }
320 catch (
) {}
321
322 // 拷貝上下文
323 DoCopy(ABuffer, ASize);
324 }
325
326 // 返回結果
327 FIsPacking = false;
328 return result;
329 }
330
331 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
332
333 /* TKYQuickUnpack - 快速解壓縮類(基于LZRW壓縮算法) */
334
335 // ---------------- 構造函數和析構函數 ----------------
336 // 構造函數
337 TKYQuickUnpack::TKYQuickUnpack()
338 {
339 // 初始化
340 FSize = 0;
341 FLastSize = 0;
342 FIsOverflow = false;
343 FIsUnpacking = false;
344 }
345
346 // 析構函數
347 TKYQuickUnpack::~TKYQuickUnpack()
348 {
349 }
350
351 // ---------------- 私有函數 ----------------
352 // 拷貝上下文
353 void TKYQuickUnpack::DoCopy(const char* ABuffer, long ASize)
354 {
355 // 初始化
356 long intSize;
357 char* pDest = (char*)FContext;
358 char* pPos = (char*)ABuffer;
359 char* pEnd = pPos + ASize;
360
361 // 檢查尺寸
362 if (ASize >= Max_Offset)
363 memcpy(pDest, pEnd - Max_Offset, Max_Offset);
364 else if ((FLastSize >= Max_Offset) || FIsOverflow)
365 {
366 intSize = Max_Offset - ASize;
367 memmove(pDest, pDest + ASize, intSize);
368 memcpy(pDest + intSize, pPos, ASize);
369 }
370 else if (FLastSize + ASize > Max_Offset)
371 {
372 intSize = Max_Offset - ASize;
373 memmove(pDest, pDest + (FLastSize - intSize), intSize);
374 memcpy(pDest + intSize, pPos, ASize);
375 }
376 else
377 memcpy(pDest + FLastSize, pPos, ASize);
378
379 // 修改最后尺寸
380 FSize = FLastSize + ASize;
381 FIsOverflow = FIsOverflow || (FSize < FLastSize);
382 FLastSize = FSize;
383 }
384
385 // 插入指定偏移量的數據
386 bool TKYQuickUnpack::DoInsert(char* &APos, Word AOffset, Byte ADepth)
387 {
388 // 初始化
389 bool result = true;
390 char* pEnd = APos + ADepth;
391 char* pDest;
392
393 // 檢查是否屬于當前數據段
394 if (FSize - FLastSize >= AOffset)
395 {
396 pDest = APos - AOffset;
397 for (; APos < pEnd; APos++, pDest++)
398 *APos = *pDest;
399 }
400 else
401 {
402 // 初始化
403 Word wSize = (Word)(FSize - FLastSize);
404 Word wFront = AOffset - wSize;
405
406 // 計算起始位置
407 pDest = FContext;
408 if ((FLastSize >= Max_Offset) || FIsOverflow)
409 pDest += Max_Offset - wFront;
410 else if (wFront <= FLastSize)
411 pDest += FLastSize - wFront;
412 else
413 result = false;
414
415 // 判斷偏移量是否合法
416 if (result)
417 {
418 // 判斷是否分二部分拷貝
419 if (wFront < ADepth)
420 {
421 // 初始化
422 char* pDestEnd = pDest + wFront;
423 char* pBegin = APos - wSize;
424
425 // 拷貝前半部
426 for (; pDest < pDestEnd; APos++, pDest++)
427 *APos = *pDest;
428
429 // 后半部的開始
430 pDest = pBegin;
431 }
432
433 // 拷貝后半部
434 for (; APos < pEnd; APos++, pDest++)
435 *APos = *pDest;
436 }
437 }
438
439 // 返回結果
440 return result;
441 }
442
443 // ---------------- 保護函數 ----------------
444
445 // ---------------- 公有函數 ----------------
446 // 重置
447 void TKYQuickUnpack::Reset()
448 {
449 if (!FIsUnpacking)
450 {
451 FSize = 0;
452 FLastSize = 0;
453 FIsOverflow = false;
454 }
455 }
456
457 // 解壓縮緩沖區
458 // 1. 若 AIsPacked 為 false 表示數據未壓縮, 即為解壓縮的上下文相關性而操作,
459 // 但不會拷貝數據到 ADest, 并返回值為 0
460 // 2. ABuffer 存放 ASize 字節的已壓縮數據
461 // 3. ADest 存放解壓縮后的數據, ADestSize >= ASize
462 // 4. 若返回值 > 0 表示解壓縮后數據的尺寸
463 // 5. 若返回值為 0 表示解壓縮失敗, 可能 ADestSize 太小或數據未壓縮
464 // 6. 若返回值為 -1 表示參數不合法
465 // 7. 若返回值為 -2 表示解壓縮失敗, 原因是數據已損壞
466 // 8. 若返回值為 -3 表示解壓縮失敗, 原因是正在解壓縮
467 long TKYQuickUnpack::Unpack(const char* ABuffer, long ASize,
468 char* ADest, long ADestSize, bool AIsPacked)
469 {
470 // 檢查是否正在壓縮
471 if (FIsUnpacking)
472 return -3;
473
474 // 置壓縮狀態
475 FIsUnpacking = true;
476
477 // 初始化
478 long result = -1;
479
480 // 檢查參數
481 if ((ABuffer == NULL) || (ASize <= 0))
482 ;
483 else if (!AIsPacked)
484 {
485 DoCopy(ABuffer, ASize);
486 result = 0;
487 }
488 else if ((ADestSize >= ASize) && (ADest != NULL))
489 {
490 // 初始化
491 result = -2;
492
493 // 操作
494 try
495 {
496 // 初始化
497 char charSame;
498 Byte byteFlag, byteDepth;
499 Word wSize, wOffset;
500 char* pLast;
501 char* pDest = ADest;
502 char* pDestEnd = ADest + ADestSize;
503 Byte* pPos = (Byte*)ABuffer;
504 Byte* pEnd = pPos + ASize - 2;
505 Byte* pBuffEnd = pPos + ASize;
506 Byte byteBit = 8;
507 bool boolOver = false;
508 bool boolError = false;
509
510 // 循環匹配
511 while (pPos < pBuffEnd)
512 {
513 // 檢查標志位是否已滿
514 if (byteBit == 8)
515 {
516 byteFlag = *pPos;
517 byteBit = 0;
518
519 // 檢查是否錯誤
520 if (++pPos >= pBuffEnd)
521 {
522 boolError = true;
523 break;
524 }
525 }
526
527 // 判斷是否壓縮
528 if ((byteFlag & Bits_Bool[byteBit]) != 0)
529 {
530 if (pPos <= pEnd)
531 {
532 // 取偏移量
533 wOffset = ((Word)pPos[0] << 4) + (pPos[1] >> 4);
534 pPos++;
535
536 // 判斷是否為匹配串
537 if (wOffset != 0)
538 {
539 byteDepth = (*(pPos++) & 0x0F) + 3;
540 if (pDest + byteDepth > pDestEnd)
541 {
542 boolOver = true;
543 break;
544 }
545 else if (DoInsert(pDest, wOffset, byteDepth))
546 FSize += byteDepth;
547 else
548 {
549 boolError = true;
550 break;
551 }
552 }
553 else if (pPos < pEnd)
554 {
555 // 取相同尺寸及字符
556 wSize = ((Word)pPos[0] << 8) + pPos[1] + 9;
557 pLast = pDest + wSize;
558 charSame = (char)pPos[2];
559 pPos += 3;
560
561 // 檢查是否溢出
562 if (pLast > pDestEnd)
563 {
564 boolOver = true;
565 break;
566 }
567 else
568 {
569 FSize += wSize;
570 for (; pDest < pLast; pDest++)
571 *pDest = charSame;
572 }
573 }
574 else
575 {
576 boolError = true;
577 break;
578 }
579 }
580 else
581 {
582 boolError = true;
583 break;
584 }
585 }
586 else if (pDest < pDestEnd)
587 {
588 *(pDest++) = (char)*(pPos++);
589 FSize++;
590 }
591 else
592 {
593 boolOver = true;
594 break;
595 }
596
597 // 位數加 1
598 byteBit++;
599 }
600
601 // 判斷是否溢出
602 if (boolOver)
603 result = 0;
604 else if (!boolError)
605 result = pDest - ADest;
606 }
607 catch () {}
608
609 // 判斷是否成功
610 if (result > 0)
611 DoCopy(ADest, result);
612 else
613 FSize = FLastSize;
614 }
615
616 // 返回結果
617 FIsUnpacking = false;
618 return result;
619 }
620
621 }
622
posted on 2011-05-22 12:24
Kyee Ye 閱讀(1098)
評論(0) 編輯 收藏 引用 所屬分類:
C++類庫KYLib 、
源碼