开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 压缩解压 > 查看源码
Lz77.h
资源名称：solitude.rar　[点击查看]
上传用户：szqxhk
上传日期：2010-02-15
资源大小：54k
文件大小：5k
源码类别：

压缩解压

开发平台：

Visual C++

Lz77.h：源码内容
  1. //////////////////////////////
  2. // LZ77.h
  3. //////////////////////////////
  5. // 使用在自己的堆中分配索引节点，不滑动窗口
  6. // 每次最多压缩 65536 字节数据
  7. // 的优化版本
  9. #ifndef _WIX_LZ77_COMPRESS_HEADER_001_
  10. #define _WIX_LZ77_COMPRESS_HEADER_001_
  12. // 滑动窗口的字节大小
  13. #define _MAX_WINDOW_SIZE 65536
  15. class CCompress
  16. {
  17. public:
  18. CCompress() {};
  19. virtual ~CCompress() {};
  21. public:
  22. virtual int Compress(BYTE* src, int srclen, BYTE* dest) = 0;
  23. virtual BOOL Decompress(BYTE* src, int srclen, BYTE* dest) = 0;
  25. protected:
  26. // tools 
  28. /////////////////////////////////////////////////////////
  29. // CopyBitsInAByte : 在一个字节范围内复制位流
  30. // 参数含义同 CopyBits 的参数
  31. // 说明：
  32. // 此函数由 CopyBits 调用，不做错误检查，即
  33. // 假定要复制的位都在一个字节范围内
  34. void CopyBitsInAByte(BYTE* memDest, int nDestPos, 
  35.   BYTE* memSrc, int nSrcPos, int nBits);
  37. ////////////////////////////////////////////////////////
  38. // CopyBits : 复制内存中的位流
  39. // memDest - 目标数据区
  40. // nDestPos - 目标数据区第一个字节中的起始位
  41. // memSrc - 源数据区
  42. // nSrcPos - 源数据区第一个字节的中起始位
  43. // nBits - 要复制的位数
  44. // 说明：
  45. // 起始位的表示约定为从字节的高位至低位（由左至右）
  46. // 依次为 0，1，... , 7
  47. // 要复制的两块数据区不能有重合
  48. void CopyBits(BYTE* memDest, int nDestPos, 
  49.   BYTE* memSrc, int nSrcPos, int nBits);
  51. //////////////////////////////////////////////////////////////
  52. // 将DWORD值从高位字节到低位字节排列
  53. void InvertDWord(DWORD* pDW);
  55. /////////////////////////////////////////////////////////////
  56. // 设置byte的第iBit位为aBit
  57. // iBit顺序为高位起从0记数（左起）
  58. void SetBit(BYTE* byte, int iBit, BYTE aBit);
  60. ////////////////////////////////////////////////////////////
  61. // 得到字节byte第pos位的值
  62. // pos顺序为高位起从0记数（左起）
  63. BYTE GetBit(BYTE byte, int pos);
  65. ////////////////////////////////////////////////////////////
  66. // 将位指针*piByte(字节偏移), *piBit(字节内位偏移)后移num位
  67. void MovePos(int* piByte, int* piBit, int num);
  69. /////////////////////////////////////////////////////////
  70. // 取log2(n)的upper_bound
  71. int UpperLog2(int n);
  73. /////////////////////////////////////////////////////////
  74. // 取log2(n)的lower_bound
  75. int LowerLog2(int n);
  76. };
  78. class CCompressLZ77 : public CCompress
  79. {
  80. public:
  81. CCompressLZ77();
  82. virtual ~CCompressLZ77();
  83. public:
  84. /////////////////////////////////////////////
  85. // 压缩一段字节流
  86. // src - 源数据区
  87. // srclen - 源数据区字节长度, srclen <= 65536
  88. // dest - 压缩数据区，调用前分配srclen字节内存
  89. // 返回值 > 0 压缩数据长度
  90. // 返回值 = 0 数据无法压缩
  91. // 返回值 < 0 压缩中异常错误
  92. int Compress(BYTE* src, int srclen, BYTE* dest);
  94. /////////////////////////////////////////////
  95. // 解压缩一段字节流
  96. // src - 接收原始数据的内存区, srclen <= 65536
  97. // srclen - 源数据区字节长度
  98. // dest - 压缩数据区
  99. // 返回值 - 成功与否
  100. BOOL Decompress(BYTE* src, int srclen, BYTE* dest);
  102. protected:
  104. BYTE* pWnd;
  105. // 窗口大小最大为 64k ，并且不做滑动
  106. // 每次最多只压缩 64k 数据，这样可以方便从文件中间开始解压
  107. // 当前窗口的长度
  108. int nWndSize;
  110. // 对滑动窗口中每一个2字节串排序
  111. // 排序是为了进行快速术语匹配
  112. // 排序的方法是用一个64k大小的指针数组
  113. // 数组下标依次对应每一个2字节串：(00 00) (00 01) ... (01 00) (01 01) ...
  114. // 每一个指针指向一个链表，链表中的节点为该2字节串的每一个出现位置
  115. struct STIDXNODE
  116. {
  117. WORD off; // 在src中的偏移
  118. WORD off2; // 用于对应的2字节串为重复字节的节点
  119. // 指从 off 到 off2 都对应了该2字节串
  120. WORD next; // 在SortHeap中的指针
  121. };
  123. WORD SortTable[65536];  // 256 * 256 指向SortHeap中下标的指针
  125. // 因为窗口不滑动，没有删除节点的操作，所以
  126. // 节点可以在SortHeap 中连续分配
  127. struct STIDXNODE* SortHeap;
  128. int HeapPos; // 当前分配位置
  130. // 当前输出位置(字节偏移及位偏移)
  131. int CurByte, CurBit;
  133. protected:
  134. ////////////////////////////////////////
  135. // 输出压缩码
  136. // code - 要输出的数
  137. // bits - 要输出的位数(对isGamma=TRUE时无效)
  138. // isGamma - 是否输出为γ编码
  139. void _OutCode(BYTE* dest, DWORD code, int bits, BOOL isGamma);
  141. ///////////////////////////////////////////////////////////
  142. // 在滑动窗口中查找术语
  143. // nSeekStart - 从何处开始匹配
  144. // offset, len - 用于接收结果，表示在滑动窗口内的偏移和长度
  145. // 返回值- 是否查到长度为3或3以上的匹配字节串
  146. BOOL _SeekPhase(BYTE* src, int srclen, int nSeekStart, int* offset, int* len);
  148. ///////////////////////////////////////////////////////////
  149. // 得到已经匹配了3个字节的窗口位置offset
  150. // 共能匹配多少个字节
  151. inline int _GetSameLen(BYTE* src, int srclen, int nSeekStart, int offset);
  153. //////////////////////////////////////////
  154. // 将窗口向右滑动n个字节
  155. inline void _ScrollWindow(int n);
  157. // 向索引中添加一个2字节串
  158. inline void _InsertIndexItem(int off);
  160. // 初始化索引表，释放上次压缩用的空间
  161. void _InitSortTable();
  162. };
  166. #endif // _WIX_LZW_COMPRESS_HEADER_001_