LOOPC软件工作室

首页 » 技术文章 » 代码编程 » LZO压缩算法
admin - 2010/4/19 23:30:00
  1. // CLZO.cpp : 定义 DLL 的初始化例程。
  2. //

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

  7. #ifdef _DEBUG
  8. #define new DEBUG_NEW
  9. #endif

  11. #include <stdio.h>
  12. #include <string.h>
  13. #include <stdlib.h>

  15. using namespace System;

  17. namespace TEST
  18. {
  19. typedef unsigned char byte;
  20. int _stdcall compress(byte *src, unsigned src_len, byte *dst);
  21. int _stdcall decompress(byte *src, unsigned src_len, byte *dst);

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


  58. dindex = (dindex & 0x7ff ) ^ 0x201f; // 处理冲突,第二次hash
  59. m_pos = dict[dindex];
  60. if((unsigned)(m_pos) < (unsigned)(in) ||
  61. (m_off = (unsigned)( (int)((unsigned)ip-(unsigned)m_pos))) <= 0 ||
  62. m_off > 0xbfff)
  63. goto literal;
  64. if (m_off <= 0x0800 || m_pos[3] == ip[3]) // 回指长度小于2Kb
  65. goto try_match; // 第三个字节相等
  66. goto literal;


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

  73. literal: // 匹配不成功时,或者无记录
  74. dict[dindex] = ip; // 记录字符串为ip[0],ip[1],ip[2],ip[3]的地址
  75. ++ip;
  76. if (ip >= ip_end)
  77. break;
  78. continue;
  79. match: // 在得到匹配长度与位置之前,先输出未匹配的字符
  80. dict[dindex] = ip; // 更新，字符匹配时的位置(未编码)
  81. if(ip - ii > 0) // 存在新字符
  82. {
  83. register unsigned t = ip - ii; // t:新字符的数目(未匹配的)

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

  112. if(m_off <= 0x0800 ) // 回指长度小于2kb
  113. {
  114. --m_off; // m_off,与m_len在输出时都减1
  115. // m_off在第一位元组(byte)占三位,m_off&7 小于8
  116. *op++ = (byte)(((m_len - 1) << 5) | ((m_off & 7) << 2));
  117. *op++ = (byte)(m_off >> 3); // 去除已用的低3位
  118. }
  119. else
  120. if (m_off <= 0x4000 ) // 回指长度小于16kb
  121. {
  122. -- m_off;
  123. *op++ = (byte)(32 | (m_len - 2));
  124. goto m3_m4_offset;
  125. }
  126. else // 回指长度大于16时
  127. {
  128. m_off -= 0x4000;
  129. *op++ = (byte)(16 | ((m_off & 0x4000) >> 11) | (m_len - 2));
  130. goto m3_m4_offset;
  131. }
  132. }
  133. else // 重复长度大于8时
  134. {
  135. {
  136. byte *end = in_end;
  137. byte *m = m_pos + 9; // 从m_pos[9]开始比较
  138. while (ip < end && *m == *ip)
  139. m++, ip++;
  140. m_len = (ip - ii);
  141. }

  143. if(m_off <= 0x4000) // 回指长度小于16kb
  144. {
  145. --m_off;
  146. if (m_len <= 33) // 可用5bit表示时
  147. *op++ = (byte)(32 | (m_len - 2));
  148. else
  149. {
  150. m_len -= 33;
  151. *op++ = 32;
  152. goto m3_m4_len;
  153. }
  154. }
  155. else // 回指长度大于16kb ,小于48 kb
  156. {
  157. m_off -= 0x4000;
  158. if(m_len <= 9)
  159. *op++ = (byte)(16|((m_off & 0x4000) >> 11) | (m_len - 2));
  160. else
  161. {
  162. m_len -= 9;
  163. *op++ = (byte)(16 | ((m_off & 0x4000) >> 11));
  164. m3_m4_len:
  165. while (m_len > 255)
  166. {
  167. m_len -= 255;
  168. *op++ = 0;
  169. }
  170. *op++ = (byte)m_len;
  171. }
  172. }
  173. m3_m4_offset:
  174. *op++ = (byte)((m_off & 63) << 2);
  175. *op++ = (byte)(m_off >> 6);
  176. }
  177. ii = ip; // 下次匹配的开始位置
  178. if (ip >= ip_end)
  179. break;
  180. }
  181. *out_len = op - out;
  182. return (unsigned) (in_end - ii);
  183. }

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


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


  316. goto copy_match;
  317. }
  318. else if (t >= 32) // 回指长度大于2Kb < 16kb
  319. {
  320. t &= 31;
  321. if (t == 0)
  322. {
  323. while (*ip == 0)
  324. {
  325. t += 255;
  326. ip++;
  327. }
  328. t += 31 + *ip++;
  329. }
  330. m_pos = op - 1;
  331. m_pos -= (* ( unsigned short * ) ip) >> 2;
  332. ip += 2;
  333. }
  334. else if (t >= 16) // 回指长度大于16 Kb,或者结束标志
  335. {
  336. m_pos = op;
  337. m_pos -= (t & 8) << 11; // 获得第一个单元组的distance
  338. t &= 7; // 获取第一个单元组的len
  339. if (t == 0)
  340. {
  341. while (*ip == 0)
  342. {
  343. t += 255;
  344. ip++;
  345. }
  346. t += 7 + *ip++;
  347. }
  348. m_pos -= (* ( unsigned short *) ip) >> 2;
  349. ip += 2;
  350. if (m_pos == op) // 判断是否为结束标志
  351. goto eof_found;
  352. m_pos -= 0x4000;
  353. }
  354. else
  355. {
  356. m_pos = op - 1;
  357. m_pos -= t >> 2;
  358. m_pos -= *ip++ << 2;
  359. *op++ = *m_pos++; *op++ = *m_pos;
  360. goto match_done;
  361. }


  364. if (t >= 6 && (op - m_pos) >= 4)
  365. {
  366. * (unsigned *) op = * ( unsigned *) m_pos;
  367. op += 4;
  368. m_pos += 4;
  369. t -= 2;
  370. do
  371. {
  372. * (unsigned *) op = * ( unsigned *) m_pos;
  373. op += 4;
  374. m_pos += 4;
  375. t -= 4;
  376. }while (t >= 4);
  377. if (t > 0)
  378. do
  379. {
  380. *op++ = *m_pos++;
  381. }while (--t > 0);
  382. }
  383. else
  384. {
  385. copy_match:
  386. *op++ = *m_pos++; // 获得前两个匹配字符
  387. *op++ = *m_pos++;
  388. do
  389. {
  390. *op++ = *m_pos++;
  391. }while (--t > 0); // 获得剩余的匹配字符
  392. }
  393. match_done:
  394. t = ip[-2] & 3; // 获取保留位,当新字符数目<=3时
  395. if (t == 0) // 保留位未使用时,即新字符数目>3
  396. break;
  397. match_next:
  398. do
  399. {
  400. *op++ = *ip++;
  401. }while (--t > 0);
  402. t = *ip++; // 下一个匹配单元
  403. }
  404. }
  405. eof_found:
  406. if (ip != ip_end)
  407. return -1;
  408. return (op - (byte*)out); // 返回解码后的长度
  409. }


  412. void main()
  413. {
  414. byte srcBuf[100] = "1234567890abcdefg567890abcd", dstBuf[100]= "", srcBuf2[100] = "";
  415. int len;


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

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

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

  426. }

  428. public ref class A
  429. {

  431. public:
  432. int Compress(array<System::Byte>^ input,int len,array<System::Byte>^ output)
  433. {
  434. IntPtr pt1=System::Runtime::InteropServices::Marshal::AllocHGlobal(len);
  435. System::Runtime::InteropServices::Marshal::Copy(input,0,pt1,len);

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

  439. len= compress((byte*)pt1.ToInt32(),len,(byte*)pt2.ToInt32());
  440. System::Runtime::InteropServices::Marshal::Copy(pt2,output,0,len);
  441. return len;
  442. }

  444. int DeCompress(array<System::Byte>^ input,int len,array<System::Byte>^ output)
  445. {
  446. IntPtr pt1=System::Runtime::InteropServices::Marshal::AllocHGlobal(len);
  447. System::Runtime::InteropServices::Marshal::Copy(input,0,pt1,len);

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

  451. len= decompress((byte*)pt1.ToInt32(),len,(byte*)pt2.ToInt32());
  452. System::Runtime::InteropServices::Marshal::Copy(pt2,output,0,len);
  453. return len;
  454. }

  456. };
  457. }
复制代码
波塞冬 - 2011/4/3 18:18:00
惭愧！:-|看不懂。。。
12
查看完整版本: LZO压缩算法
Powered by Discuz!NT Archiver 3.0.0 2001-2024 Comsenz Inc.