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 

  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