LZO压缩算法

[ 13931 查看 / 53 回复 ]

  1. // CLZO.cpp : 定义 DLL 的初始化例程。
  2. //

  3. #include "stdafx.h"
  4. #include "CLZO.h"

  5. #ifdef _DEBUG
  6. #define new DEBUG_NEW
  7. #endif

  8. #include <stdio.h>
  9. #include <string.h>
  10. #include <stdlib.h>

  11. using namespace System;

  12. namespace TEST
  13. {
  14. typedef unsigned char byte;
  15. int _stdcall compress(byte *src, unsigned src_len, byte *dst);
  16. int _stdcall decompress(byte *src, unsigned src_len, byte *dst);

  17. // 新字符(<18): -3,匹配长度-1,匹配位置-1,保留位:新字符数
  18. // 新字符(>18):-18
  19. // 开始查找,如果没有匹配字符时,记录其位置
  20. // 直到找到匹配字符,开始输出记录的新字符
  21. // 然后 计算出匹配字符的长度与位置,
  22. // 并根据其区间输出其位置
  23. static unsigned _do_compress (byte *in, unsigned in_len, byte *out, unsigned *out_len)
  24. {
  25. static long wrkmem [16384L];
  26. register byte *ip;
  27. byte *op;
  28. byte *in_end = in + in_len;
  29. byte *ip_end = in + in_len -3;
  30. byte *ii; // 指向开始编码的位置
  31. byte **dict = (byte **)wrkmem;
  32. op = out;
  33. ip = in;
  34. ii = ip;
  35. ip += 4;
  36. for(;;)
  37. {
  38. register byte *m_pos;
  39. unsigned m_off;
  40. unsigned m_len;
  41. unsigned dindex; // hashkey(ip[0], ip[1], ip[2], ip[3])
  42. dindex = ((0x21*(((((((unsigned)(ip[3])<<6)^ip[2])<<5)^ip[1])<<5)^ip[0]))>>5) & 0x3fff;
  43. m_pos = dict [dindex];
  44. if(((unsigned)m_pos < (unsigned)in) ||
  45. (m_off = (unsigned)((unsigned)ip-(unsigned)m_pos) ) <= 0 ||
  46. m_off > 0xbfff) // 0xc000 48kb
  47. goto literal;
  48. if(m_off <= 0x0800 || m_pos[3] == ip[3]) // 回指长度小于2Kb
  49. goto try_match;


  50. dindex = (dindex & 0x7ff ) ^ 0x201f; // 处理冲突,第二次hash
  51. m_pos = dict[dindex];
  52. if((unsigned)(m_pos) < (unsigned)(in) ||
  53. (m_off = (unsigned)( (int)((unsigned)ip-(unsigned)m_pos))) <= 0 ||
  54. m_off > 0xbfff)
  55. goto literal;
  56. if (m_off <= 0x0800 || m_pos[3] == ip[3]) // 回指长度小于2Kb
  57. goto try_match; // 第三个字节相等
  58. goto literal;


  59. try_match: // m_pos[0],m_pos[1],m_pos[2]都匹配成功时,继续比较
  60. if(*(unsigned short*)m_pos == *(unsigned short*)ip && m_pos[2]== ip[2])
  61. goto match;

  62. literal: // 匹配不成功时,或者无记录
  63. dict[dindex] = ip; // 记录字符串为ip[0],ip[1],ip[2],ip[3]的地址
  64. ++ip;
  65. if (ip >= ip_end)
  66. break;
  67. continue;
  68. match: // 在得到匹配长度与位置之前,先输出未匹配的字符
  69. dict[dindex] = ip; // 更新,字符匹配时的位置(未编码)
  70. if(ip - ii > 0) // 存在新字符
  71. {
  72. register unsigned t = ip - ii; // t:新字符的数目(未匹配的)

  73. if (t <= 3) // 新字符数目<3时
  74. op[-2] |= (byte)t; // 对两个保留字元赋值
  75. else if(t <= 18) // 新字符数目<18时
  76. *op++ = (byte)(t - 3);
  77. else
  78. {
  79. register unsigned tt = t - 18;
  80. *op++ = 0;
  81. while(tt > 255) // 构建新位元组
  82. {
  83. tt -= 255;
  84. *op++ = 0;
  85. }
  86. *op++ = (byte)tt;
  87. }
  88. do
  89. {
  90. *op++ = *ii++; // ii指向开始匹配的位置(未编码)
  91. }while (--t > 0); // 输出 t个新字符
  92. }
  93. ip += 3; // 跳过与m_pos[0] m_pos[1] m_pos[2]的比较
  94. if(m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ ||
  95. m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++ )
  96. {
  97. --ip;
  98. m_len = ip - ii; // 得到重复长度<=8

  99. if(m_off <= 0x0800 ) // 回指长度小于2kb
  100. {
  101. --m_off; // m_off,与m_len在输出时都减1
  102. // m_off在第一位元组(byte)占三位,m_off&7 小于8
  103. *op++ = (byte)(((m_len - 1) << 5) | ((m_off & 7) << 2));
  104. *op++ = (byte)(m_off >> 3); // 去除已用的低3位
  105. }
  106. else
  107. if (m_off <= 0x4000 ) // 回指长度小于16kb
  108. {
  109. -- m_off;
  110. *op++ = (byte)(32 | (m_len - 2));
  111. goto m3_m4_offset;
  112. }
  113. else // 回指长度大于16时
  114. {
  115. m_off -= 0x4000;
  116. *op++ = (byte)(16 | ((m_off & 0x4000) >> 11) | (m_len - 2));
  117. goto m3_m4_offset;
  118. }
  119. }
  120. else // 重复长度大于8时
  121. {
  122. {
  123. byte *end = in_end;
  124. byte *m = m_pos + 9; // 从m_pos[9]开始比较
  125. while (ip < end && *m == *ip)
  126. m++, ip++;
  127. m_len = (ip - ii);
  128. }

  129. if(m_off <= 0x4000) // 回指长度小于16kb
  130. {
  131. --m_off;
  132. if (m_len <= 33) // 可用5bit表示时
  133. *op++ = (byte)(32 | (m_len - 2));
  134. else
  135. {
  136. m_len -= 33;
  137. *op++ = 32;
  138. goto m3_m4_len;
  139. }
  140. }
  141. else // 回指长度大于16kb ,小于48 kb
  142. {
  143. m_off -= 0x4000;
  144. if(m_len <= 9)
  145. *op++ = (byte)(16|((m_off & 0x4000) >> 11) | (m_len - 2));
  146. else
  147. {
  148. m_len -= 9;
  149. *op++ = (byte)(16 | ((m_off & 0x4000) >> 11));
  150. m3_m4_len:
  151. while (m_len > 255)
  152. {
  153. m_len -= 255;
  154. *op++ = 0;
  155. }
  156. *op++ = (byte)m_len;
  157. }
  158. }
  159. m3_m4_offset:
  160. *op++ = (byte)((m_off & 63) << 2);
  161. *op++ = (byte)(m_off >> 6);
  162. }
  163. ii = ip; // 下次匹配的开始位置
  164. if (ip >= ip_end)
  165. break;
  166. }
  167. *out_len = op - out;
  168. return (unsigned) (in_end - ii);
  169. }

  170. int _stdcall compress(byte *in, unsigned in_len, byte *out)
  171. {
  172. byte *op = out;
  173. unsigned t,out_len;
  174. if (in_len <= 13)
  175. t = in_len;
  176. else
  177. {
  178. t = _do_compress (in,in_len,op,&out_len);
  179. op += out_len;
  180. }
  181. if (t > 0) // t: 未编码的字符大小,即新字符的数目
  182. {
  183. byte *ii = (byte*)in + in_len - t; // 未编码的开始地址
  184. if (op == (byte*)out && t <= 238)
  185. *op++ = (byte) ( 17 + t );
  186. else
  187. if (t <= 3) // 新字符数目<3时
  188. op[-2] |= (byte)t ;
  189. else
  190. if (t <= 18) // 新字符数目<18 时
  191. *op++ = (byte)(t-3);
  192. else
  193. {
  194. unsigned tt = t - 18;
  195. *op++ = 0;
  196. while (tt > 255)
  197. {
  198. tt -= 255;
  199. *op++ = 0;
  200. }
  201. *op++ = (byte)tt;
  202. }
  203. do
  204. {
  205. *op++ = *ii++;
  206. }while (--t > 0); // 输出t个新字符
  207. }
  208. *op++ = 17; // 结束编码标志
  209. *op++ = 0;
  210. *op++ = 0;
  211. return (op - (byte*)out); // 返回编码后的长度
  212. }
  213. int _stdcall decompress(byte *in, unsigned in_len, byte *out)
  214. {
  215. register byte *op; // 输出临时缓存区
  216. register byte *ip;
  217. register unsigned t;
  218. register byte *m_pos;
  219. byte *ip_end = (byte*)in + in_len;
  220. op = out;
  221. ip = in;
  222. if(*ip > 17)
  223. {
  224. t = *ip++ - 17;
  225. if (t < 4)
  226. goto match_next;
  227. do *op++ = *ip++; while (--t > 0);
  228. goto first_literal_run;
  229. }
  230. for(;;)
  231. {
  232. t = *ip++; // 得到新字符的数目(t+3)
  233. if (t >= 16) // 新字符数目(t+3) > 18时
  234. goto match;
  235. if (t == 0) // 新字符数目大于18时
  236. {
  237. while (*ip == 0)
  238. {
  239. t += 255;
  240. ip++;
  241. }
  242. t += 15 + *ip++; // 得到具体新字符数目大小(t+3)
  243. }


  244. // 获取t新字符,每次以4个为单位
  245. * (unsigned *) op = * ( unsigned *) ip; // 获取sizeof(unsigned)个新字符
  246. op += 4;
  247. ip += 4;
  248. if (--t > 0) // 新字符数目:t+4-1 = t + 3,已处理了4个
  249. {
  250. if (t >= 4)
  251. {
  252. do
  253. {
  254. // 获取sizeof(unsigned)个新字符,即4个,以4个为单位
  255. * (unsigned * ) op = * ( unsigned * ) ip;
  256. op += 4;
  257. ip += 4;
  258. t -= 4;
  259. } while (t >= 4);
  260. if (t > 0) // 不足一个单位时,且t>0
  261. {
  262. do
  263. {
  264. *op++ = *ip++;
  265. }while (--t > 0);
  266. }
  267. }
  268. else
  269. {
  270. do
  271. {
  272. *op++ = *ip++;
  273. }while (--t > 0);
  274. }
  275. }
  276. first_literal_run:
  277. t = *ip++; // 判断是否是重复字符编码
  278. if (t >= 16) // 是重复字符编码
  279. goto match;
  280. m_pos = op - 0x0801;
  281. m_pos -= t >> 2;
  282. m_pos -= *ip++ << 2;
  283. *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
  284. goto match_done;
  285. for(;;)
  286. {
  287. match:
  288. // 根据第一单元组来判断其解压种类
  289. if (t >= 64) // 回指长度小于2Kb
  290. {
  291. // int match_len = (*ip++ << 3) | ((t >> 2) & 7) + 1;
  292. // m_pos= op -match_len; //得到匹配位置
  293. m_pos = op - 1; //
  294. m_pos -= (t >> 2) & 7; // 得到第一个位元组的distance
  295. m_pos -= *ip++ << 3; //得到匹配位置
  296. t = (t >> 5) - 1; // 得到第一个位元组的len - 1


  297. goto copy_match;
  298. }
  299. else if (t >= 32) // 回指长度大于2Kb < 16kb
  300. {
  301. t &= 31;
  302. if (t == 0)
  303. {
  304. while (*ip == 0)
  305. {
  306. t += 255;
  307. ip++;
  308. }
  309. t += 31 + *ip++;
  310. }
  311. m_pos = op - 1;
  312. m_pos -= (* ( unsigned short * ) ip) >> 2;
  313. ip += 2;
  314. }
  315. else if (t >= 16) // 回指长度大于16 Kb,或者结束标志
  316. {
  317. m_pos = op;
  318. m_pos -= (t & 8) << 11; // 获得第一个单元组的distance
  319. t &= 7; // 获取第一个单元组的len
  320. if (t == 0)
  321. {
  322. while (*ip == 0)
  323. {
  324. t += 255;
  325. ip++;
  326. }
  327. t += 7 + *ip++;
  328. }
  329. m_pos -= (* ( unsigned short *) ip) >> 2;
  330. ip += 2;
  331. if (m_pos == op) // 判断是否为结束标志
  332. goto eof_found;
  333. m_pos -= 0x4000;
  334. }
  335. else
  336. {
  337. m_pos = op - 1;
  338. m_pos -= t >> 2;
  339. m_pos -= *ip++ << 2;
  340. *op++ = *m_pos++; *op++ = *m_pos;
  341. goto match_done;
  342. }


  343. if (t >= 6 && (op - m_pos) >= 4)
  344. {
  345. * (unsigned *) op = * ( unsigned *) m_pos;
  346. op += 4;
  347. m_pos += 4;
  348. t -= 2;
  349. do
  350. {
  351. * (unsigned *) op = * ( unsigned *) m_pos;
  352. op += 4;
  353. m_pos += 4;
  354. t -= 4;
  355. }while (t >= 4);
  356. if (t > 0)
  357. do
  358. {
  359. *op++ = *m_pos++;
  360. }while (--t > 0);
  361. }
  362. else
  363. {
  364. copy_match:
  365. *op++ = *m_pos++; // 获得前两个匹配字符
  366. *op++ = *m_pos++;
  367. do
  368. {
  369. *op++ = *m_pos++;
  370. }while (--t > 0); // 获得剩余的匹配字符
  371. }
  372. match_done:
  373. t = ip[-2] & 3; // 获取保留位,当新字符数目<=3时
  374. if (t == 0) // 保留位未使用时,即新字符数目>3
  375. break;
  376. match_next:
  377. do
  378. {
  379. *op++ = *ip++;
  380. }while (--t > 0);
  381. t = *ip++; // 下一个匹配单元
  382. }
  383. }
  384. eof_found:
  385. if (ip != ip_end)
  386. return -1;
  387. return (op - (byte*)out); // 返回解码后的长度
  388. }


  389. void main()
  390. {
  391. byte srcBuf[100] = "1234567890abcdefg567890abcd", dstBuf[100]= "", srcBuf2[100] = "";
  392. int len;


  393. printf("%s\n", srcBuf);
  394. for(len=0; srcBuf[len]!='\0'; len++);

  395. len = compress(srcBuf, len, dstBuf);

  396. len=decompress(dstBuf, len, srcBuf2);
  397. printf("%s\n", srcBuf2);

  398. }

  399. public ref class A
  400. {

  401. public:
  402. int Compress(array<System::Byte>^ input,int len,array<System::Byte>^ output)
  403. {
  404. IntPtr pt1=System::Runtime::InteropServices::Marshal::AllocHGlobal(len);
  405. System::Runtime::InteropServices::Marshal::Copy(input,0,pt1,len);

  406. IntPtr pt2=System::Runtime::InteropServices::Marshal::AllocHGlobal(len*10);

  407. len= compress((byte*)pt1.ToInt32(),len,(byte*)pt2.ToInt32());
  408. System::Runtime::InteropServices::Marshal::Copy(pt2,output,0,len);
  409. return len;
  410. }

  411. int DeCompress(array<System::Byte>^ input,int len,array<System::Byte>^ output)
  412. {
  413. IntPtr pt1=System::Runtime::InteropServices::Marshal::AllocHGlobal(len);
  414. System::Runtime::InteropServices::Marshal::Copy(input,0,pt1,len);

  415. IntPtr pt2=System::Runtime::InteropServices::Marshal::AllocHGlobal(len*10);

  416. len= decompress((byte*)pt1.ToInt32(),len,(byte*)pt2.ToInt32());
  417. System::Runtime::InteropServices::Marshal::Copy(pt2,output,0,len);
  418. return len;
  419. }

  420. };
  421. }
复制代码
原创的免费软件 - LoopcVPN,DnsAcc,DNS加速器,百度相册助手
引用 TOP

惭愧!看不懂。。。
引用 TOP