lzari.cpp 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693
  1. /**************************************************************
  2. LZARI.C -- A Data Compression Program
  3. (tab = 4 spaces)
  4. ***************************************************************
  5. 4/7/1989 Haruhiko Okumura
  6. Use, distribute, and modify this program freely.
  7. Please send me your improved versions.
  8. PC-VAN SCIENCE
  9. NIFTY-Serve PAF01022
  10. CompuServe 74050,1022
  11. **************************************************************/
  12. /********************************************************************
  13. lzari.cpp -- A Data Compression Class
  14. created: 2004/10/04
  15. created: 4:10:2004 16:44
  16. file base: lzari
  17. file ext: cpp
  18. author: 阙荣文 (querw@sina.com)
  19. purpose: 如上所述,lzari.c提供了lzari压缩算法的实现,基于lzari.c我把它
  20. 做成了一个c++类方便使用
  21. *********************************************************************/
  22. #include "stdafx.h"
  23. //#include <stdio.h>
  24. //#include <stdlib.h>
  25. //#include <string.h>
  26. //#include <ctype.h>
  27. #include "Lzari.h"
  28. LZARI::LZARI()
  29. {
  30. infile = NULL;
  31. outfile = NULL;
  32. textsize = 0;
  33. codesize = 0;
  34. printcount = 0;
  35. low = 0;
  36. high = Q4;
  37. value = 0;
  38. shifts = 0;/* counts for magnifying low and high around Q2 */
  39. m_bMem = FALSE;
  40. m_pInBuffer = NULL;
  41. m_nInLength = 0;
  42. m_nInCur = 0;
  43. //m_pOutBuffer = NULL;
  44. m_nOutLength = 0;
  45. // m_nOutCur = 0;
  46. buffer_putbit = 0;
  47. mask_putbit = 128;
  48. buffer_getbit = 0;
  49. mask_getbit = 0;
  50. }
  51. LZARI::~LZARI()
  52. {
  53. Release();
  54. }
  55. void LZARI::Error(char *message)
  56. {
  57. #ifdef _OUTPUT_STATUS
  58. printf("\n%s\n", message);
  59. #endif
  60. //exit(EXIT_FAILURE);
  61. int e = 1;
  62. throw e;
  63. }
  64. void LZARI::PutBit(int bit) /* Output one bit (bit = 0,1) */
  65. {
  66. if (bit) buffer_putbit |= mask_putbit;
  67. if ((mask_putbit >>= 1) == 0)
  68. {
  69. if (!m_bMem)
  70. {
  71. if (putc(buffer_putbit, outfile) == EOF) Error("Write Error");
  72. }
  73. else
  74. {
  75. //if (m_nOutCur == m_nOutLength) Error("Write Error");
  76. //m_pOutBuffer[m_nOutCur++] = buffer;
  77. m_OutBuffer.push_back(buffer_putbit);
  78. //m_nOutCur++;
  79. }
  80. buffer_putbit = 0;
  81. mask_putbit = 128;
  82. codesize++;
  83. }
  84. }
  85. void LZARI::FlushBitBuffer(void) /* Send remaining bits */
  86. {
  87. int i;
  88. for (i = 0; i < 7; i++) PutBit(0);
  89. }
  90. int LZARI::GetBit(void) /* Get one bit (0 or 1) */
  91. {
  92. if ((mask_getbit >>= 1) == 0)
  93. {
  94. if (!m_bMem)
  95. buffer_getbit = getc(infile);
  96. else
  97. buffer_getbit = m_pInBuffer[m_nInCur++];
  98. mask_getbit = 128;
  99. }
  100. return ((buffer_getbit & mask_getbit) != 0);
  101. }
  102. /********** LZSS with multiple binary trees **********/
  103. void LZARI::InitTree(void) /* Initialize trees */
  104. {
  105. int i;
  106. /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  107. left children of node i. These nodes need not be initialized.
  108. Also, dad[i] is the parent of node i. These are initialized to
  109. NIL (= N), which stands for 'not used.'
  110. For i = 0 to 255, rson[N + i + 1] is the root of the tree
  111. for strings that begin with character i. These are initialized
  112. to NIL. Note there are 256 trees. */
  113. for (i = N + 1; i <= N + 256; i++) rson[i] = NIL; /* root */
  114. for (i = 0; i < N; i++) dad[i] = NIL; /* node */
  115. }
  116. void LZARI::InsertNode(int r)
  117. /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  118. trees (text_buf[r]'th tree) and returns the longest-match position
  119. and length via the global variables match_position and match_length.
  120. If match_length = F, then removes the old node in favor of the new
  121. one, because the old one will be deleted sooner.
  122. Note r plays double role, as tree node and position in buffer. */
  123. {
  124. int i, p, cmp, temp;
  125. unsigned char *key;
  126. cmp = 1; key = &text_buf[r]; p = N + 1 + key[0];
  127. rson[r] = lson[r] = NIL; match_length = 0;
  128. for ( ; ; )
  129. {
  130. if (cmp >= 0)
  131. {
  132. if (rson[p] != NIL) p = rson[p];
  133. else { rson[p] = r; dad[r] = p; return; }
  134. } else
  135. {
  136. if (lson[p] != NIL) p = lson[p];
  137. else { lson[p] = r; dad[r] = p; return; }
  138. }
  139. for (i = 1; i < F; i++)
  140. if ((cmp = key[i] - text_buf[p + i]) != 0) break;
  141. if (i > THRESHOLD)
  142. {
  143. if (i > match_length)
  144. {
  145. match_position = (r - p) & (N - 1);
  146. if ((match_length = i) >= F) break;
  147. } else if (i == match_length)
  148. {
  149. if ((temp = (r - p) & (N - 1)) < match_position)
  150. match_position = temp;
  151. }
  152. }
  153. }
  154. dad[r] = dad[p]; lson[r] = lson[p]; rson[r] = rson[p];
  155. dad[lson[p]] = r; dad[rson[p]] = r;
  156. if (rson[dad[p]] == p) rson[dad[p]] = r;
  157. else lson[dad[p]] = r;
  158. dad[p] = NIL; /* remove p */
  159. }
  160. void LZARI::DeleteNode(int p) /* Delete node p from tree */
  161. {
  162. int q;
  163. if (dad[p] == NIL) return; /* not in tree */
  164. if (rson[p] == NIL) q = lson[p];
  165. else if (lson[p] == NIL) q = rson[p];
  166. else
  167. {
  168. q = lson[p];
  169. if (rson[q] != NIL)
  170. {
  171. do { q = rson[q]; } while (rson[q] != NIL);
  172. rson[dad[q]] = lson[q]; dad[lson[q]] = dad[q];
  173. lson[q] = lson[p]; dad[lson[p]] = q;
  174. }
  175. rson[q] = rson[p]; dad[rson[p]] = q;
  176. }
  177. dad[q] = dad[p];
  178. if (rson[dad[p]] == p) rson[dad[p]] = q;
  179. else lson[dad[p]] = q;
  180. dad[p] = NIL;
  181. }
  182. /********** Arithmetic Compression **********/
  183. /* If you are not familiar with arithmetic compression, you should read
  184. I. E. Witten, R. M. Neal, and J. G. Cleary,
  185. Communications of the ACM, Vol. 30, pp. 520-540 (1987),
  186. from which much have been borrowed. */
  187. /* character code = 0, 1, ..., N_CHAR - 1 */
  188. void LZARI::StartModel(void) /* Initialize model */
  189. {
  190. int ch, sym, i;
  191. sym_cum[N_CHAR] = 0;
  192. for (sym = N_CHAR; sym >= 1; sym--)
  193. {
  194. ch = sym - 1;
  195. char_to_sym[ch] = sym; sym_to_char[sym] = ch;
  196. sym_freq[sym] = 1;
  197. sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
  198. }
  199. sym_freq[0] = 0; /* sentinel (!= sym_freq[1]) */
  200. position_cum[N] = 0;
  201. for (i = N; i >= 1; i--)
  202. position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
  203. /* empirical distribution function (quite tentative) */
  204. /* Please devise a better mechanism! */
  205. }
  206. void LZARI::UpdateModel(int sym)
  207. {
  208. int i, c, ch_i, ch_sym;
  209. if (sym_cum[0] >= MAX_CUM)
  210. {
  211. c = 0;
  212. for (i = N_CHAR; i > 0; i--)
  213. {
  214. sym_cum[i] = c;
  215. c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
  216. }
  217. sym_cum[0] = c;
  218. }
  219. for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
  220. if (i < sym)
  221. {
  222. ch_i = sym_to_char[i]; ch_sym = sym_to_char[sym];
  223. sym_to_char[i] = ch_sym; sym_to_char[sym] = ch_i;
  224. char_to_sym[ch_i] = sym; char_to_sym[ch_sym] = i;
  225. }
  226. sym_freq[i]++;
  227. while (--i >= 0) sym_cum[i]++;
  228. }
  229. void LZARI::Output(int bit) /* Output 1 bit, followed by its complements */
  230. {
  231. PutBit(bit);
  232. for ( ; shifts > 0; shifts--) PutBit(! bit);
  233. }
  234. void LZARI::EncodeChar(int ch)
  235. {
  236. int sym;
  237. unsigned long int range;
  238. sym = char_to_sym[ch];
  239. range = high - low;
  240. high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  241. low += (range * sym_cum[sym ]) / sym_cum[0];
  242. for ( ; ; )
  243. {
  244. if (high <= Q2) Output(0);
  245. else if (low >= Q2)
  246. {
  247. Output(1); low -= Q2; high -= Q2;
  248. }
  249. else if (low >= Q1 && high <= Q3)
  250. {
  251. shifts++; low -= Q1; high -= Q1;
  252. }
  253. else break;
  254. low += low;
  255. high += high;
  256. }
  257. UpdateModel(sym);
  258. }
  259. void LZARI::EncodePosition(int position)
  260. {
  261. unsigned long int range;
  262. range = high - low;
  263. high = low + (range * position_cum[position ]) / position_cum[0];
  264. low += (range * position_cum[position + 1]) / position_cum[0];
  265. for ( ; ; )
  266. {
  267. if (high <= Q2) Output(0);
  268. else if (low >= Q2)
  269. {
  270. Output(1); low -= Q2; high -= Q2;
  271. }
  272. else if (low >= Q1 && high <= Q3)
  273. {
  274. shifts++; low -= Q1; high -= Q1;
  275. }
  276. else break;
  277. low += low;
  278. high += high;
  279. }
  280. }
  281. void LZARI::EncodeEnd(void)
  282. {
  283. shifts++;
  284. if (low < Q1) Output(0); else Output(1);
  285. FlushBitBuffer(); /* flush bits remaining in buffer */
  286. }
  287. int LZARI::BinarySearchSym(unsigned int x)
  288. /* 1 if x >= sym_cum[1],
  289. N_CHAR if sym_cum[N_CHAR] > x,
  290. i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
  291. {
  292. int i, j, k;
  293. i = 1; j = N_CHAR;
  294. while (i < j)
  295. {
  296. k = (i + j) / 2;
  297. if (sym_cum[k] > x) i = k + 1; else j = k;
  298. }
  299. return i;
  300. }
  301. int LZARI::BinarySearchPos(unsigned int x)
  302. /* 0 if x >= position_cum[1],
  303. N - 1 if position_cum[N] > x,
  304. i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
  305. {
  306. int i, j, k;
  307. i = 1; j = N;
  308. while (i < j)
  309. {
  310. k = (i + j) / 2;
  311. if (position_cum[k] > x) i = k + 1; else j = k;
  312. }
  313. return i - 1;
  314. }
  315. void LZARI::StartDecode(void)
  316. {
  317. int i;
  318. for (i = 0; i < M + 2; i++)
  319. value = 2 * value + GetBit();
  320. }
  321. int LZARI::DecodeChar(void)
  322. {
  323. int sym, ch;
  324. unsigned long int range;
  325. range = high - low;
  326. sym = BinarySearchSym((unsigned int)
  327. (((value - low + 1) * sym_cum[0] - 1) / range));
  328. high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  329. low += (range * sym_cum[sym ]) / sym_cum[0];
  330. for ( ; ; ) {
  331. if (low >= Q2) {
  332. value -= Q2; low -= Q2; high -= Q2;
  333. } else if (low >= Q1 && high <= Q3) {
  334. value -= Q1; low -= Q1; high -= Q1;
  335. } else if (high > Q2) break;
  336. low += low; high += high;
  337. value = 2 * value + GetBit();
  338. }
  339. ch = sym_to_char[sym];
  340. UpdateModel(sym);
  341. return ch;
  342. }
  343. int LZARI::DecodePosition(void)
  344. {
  345. int position;
  346. unsigned long int range;
  347. range = high - low;
  348. position = BinarySearchPos((unsigned int)
  349. (((value - low + 1) * position_cum[0] - 1) / range));
  350. high = low + (range * position_cum[position ]) / position_cum[0];
  351. low += (range * position_cum[position + 1]) / position_cum[0];
  352. for ( ; ; ) {
  353. if (low >= Q2) {
  354. value -= Q2; low -= Q2; high -= Q2;
  355. } else if (low >= Q1 && high <= Q3) {
  356. value -= Q1; low -= Q1; high -= Q1;
  357. } else if (high > Q2) break;
  358. low += low; high += high;
  359. value = 2 * value + GetBit();
  360. }
  361. return position;
  362. }
  363. /********** Encode and Decode **********/
  364. void LZARI::Encode(void)
  365. {
  366. int i, c, len, r, s, last_match_length;
  367. if(!m_bMem)
  368. {
  369. fseek(infile, 0L, SEEK_END);
  370. textsize = ftell(infile);
  371. if (fwrite(&textsize, sizeof textsize, 1, outfile) < 1)
  372. Error("Write Error"); /* output size of text */
  373. codesize += sizeof textsize;
  374. if (textsize == 0) return;
  375. rewind(infile);
  376. textsize = 0;
  377. }
  378. else
  379. {
  380. textsize = m_nInLength;
  381. m_OutBuffer.resize(sizeof textsize);
  382. memcpy(&m_OutBuffer[0],&textsize,sizeof textsize);
  383. //m_nOutCur += sizeof textsize;
  384. codesize += sizeof textsize;
  385. if(textsize == 0) return;
  386. m_nInCur = 0;
  387. textsize = 0;
  388. }
  389. StartModel();
  390. InitTree();
  391. s = 0; r = N - F;
  392. for (i = s; i < r; i++) text_buf[i] = ' ';
  393. if(!m_bMem)
  394. for (len = 0; len < F && (c = getc(infile)) != EOF; len++) text_buf[r + len] = c;
  395. else
  396. for (len = 0; len < F && m_nInCur < m_nInLength ; len++)
  397. {
  398. c = m_pInBuffer[m_nInCur++];
  399. text_buf[r + len] = c;
  400. }
  401. textsize = len;
  402. for (i = 1; i <= F; i++) InsertNode(r - i);
  403. InsertNode(r);
  404. do {
  405. if (match_length > len) match_length = len;
  406. if (match_length <= THRESHOLD)
  407. {
  408. match_length = 1; EncodeChar(text_buf[r]);
  409. }
  410. else
  411. {
  412. EncodeChar(255 - THRESHOLD + match_length);
  413. EncodePosition(match_position - 1);
  414. }
  415. last_match_length = match_length;
  416. if(!m_bMem)
  417. {
  418. for (i = 0; i < last_match_length && (c = getc(infile)) != EOF; i++)
  419. {
  420. DeleteNode(s); text_buf[s] = c;
  421. if (s < F - 1) text_buf[s + N] = c;
  422. s = (s + 1) & (N - 1);
  423. r = (r + 1) & (N - 1);
  424. InsertNode(r);
  425. }
  426. }
  427. else
  428. {
  429. for (i = 0; i < last_match_length && m_nInCur < m_nInLength ; i++)
  430. {
  431. c = m_pInBuffer[m_nInCur++];
  432. DeleteNode(s);
  433. text_buf[s] = c;
  434. if (s < F - 1) text_buf[s + N] = c;
  435. s = (s + 1) & (N - 1);
  436. r = (r + 1) & (N - 1);
  437. InsertNode(r);
  438. }
  439. }
  440. if ((textsize += i) > printcount)
  441. {
  442. #ifdef _OUTPUT_STATUS
  443. printf("%12ld\r", textsize);
  444. #endif
  445. printcount += 1024;
  446. }
  447. while (i++ < last_match_length)
  448. {
  449. DeleteNode(s);
  450. s = (s + 1) & (N - 1);
  451. r = (r + 1) & (N - 1);
  452. if (--len) InsertNode(r);
  453. }
  454. } while (len > 0);
  455. EncodeEnd();
  456. #ifdef _OUTPUT_STATUS
  457. printf("In : %lu bytes\n", textsize);
  458. printf("Out: %lu bytes\n", codesize);
  459. printf("Out/In: %.3f\n", (double)codesize / textsize);
  460. #endif
  461. }
  462. void LZARI::Decode(void)
  463. {
  464. int i, j, k, r, c;
  465. unsigned long int count;
  466. if (!m_bMem)
  467. {
  468. if (fread(&textsize, sizeof textsize, 1, infile) < 1)
  469. Error("Read Error"); /* read size of text */
  470. }
  471. else
  472. {
  473. if(m_nInLength < sizeof textsize)
  474. Error("Read Error");
  475. memcpy(&textsize,m_pInBuffer + m_nInCur,sizeof textsize);
  476. //m_OutBuffer.reserve(textsize);
  477. m_nOutLength = textsize;
  478. //m_nOutCur = 0;
  479. m_nInCur += sizeof textsize;
  480. }
  481. if (textsize == 0) return;
  482. StartDecode();
  483. StartModel();
  484. for (i = 0; i < N - F; i++) text_buf[i] = ' ';
  485. r = N - F;
  486. for (count = 0; count < textsize; )
  487. {
  488. c = DecodeChar();
  489. if (c < 256)
  490. {
  491. if(!m_bMem)
  492. putc(c, outfile);
  493. else
  494. {
  495. //m_OutBuffer[m_nOutCur++] = c;
  496. m_OutBuffer.push_back(c);
  497. //m_nOutCur++;
  498. }
  499. text_buf[r++] = c;
  500. r &= (N - 1);
  501. count++;
  502. }
  503. else
  504. {
  505. i = (r - DecodePosition() - 1) & (N - 1);
  506. j = c - 255 + THRESHOLD;
  507. for (k = 0; k < j; k++)
  508. {
  509. c = text_buf[(i + k) & (N - 1)];
  510. if(!m_bMem)
  511. putc(c, outfile);
  512. else
  513. {
  514. // m_pOutBuffer[m_nOutCur++] = c;
  515. m_OutBuffer.push_back(c);
  516. //m_nOutCur ++;
  517. }
  518. text_buf[r++] = c;
  519. r &= (N - 1);
  520. count++;
  521. }
  522. }
  523. if (count > printcount)
  524. {
  525. #ifdef _OUTPUT_STATUS
  526. printf("%12lu\r", count);
  527. #endif
  528. printcount += 1024;
  529. }
  530. }
  531. #ifdef _OUTPUT_STATUS
  532. printf("%12lu\n", count);
  533. #endif
  534. }
  535. void LZARI::Compress(const char *lpszInfile,const char *lpszOutfile)
  536. {
  537. m_bMem = FALSE;
  538. infile = fopen(lpszInfile,"rb");
  539. outfile = fopen(lpszOutfile,"wb");
  540. if(infile && outfile)
  541. {
  542. Encode();
  543. fclose(infile);
  544. fclose(outfile);
  545. infile = NULL;
  546. outfile = NULL;
  547. }
  548. }
  549. void LZARI::UnCompress(const char *lpszInfile,const char *lpszOutfile)
  550. {
  551. m_bMem = FALSE;
  552. infile = fopen(lpszInfile,"rb");
  553. outfile = fopen(lpszOutfile,"wb");
  554. if(infile && outfile)
  555. {
  556. Decode();
  557. fclose(infile);
  558. fclose(outfile);
  559. infile = NULL;
  560. outfile = NULL;
  561. }
  562. }
  563. void LZARI::Compress(const BYTE *pInBuffer,int nInLength,const BYTE *&pOutBuffer ,int &nOutLength)
  564. {
  565. m_pInBuffer = pInBuffer;
  566. m_nInLength = nInLength;
  567. m_nInCur = 0;
  568. // m_nOutCur = 0;
  569. m_bMem = TRUE;
  570. Encode();
  571. pOutBuffer = &m_OutBuffer[0];
  572. nOutLength = m_OutBuffer.size();
  573. }
  574. void LZARI::Release()
  575. {
  576. if(!m_OutBuffer.empty())
  577. {
  578. infile = NULL;
  579. outfile = NULL;
  580. textsize = 0;
  581. codesize = 0;
  582. printcount = 0;
  583. low = 0;
  584. high = Q4;
  585. value = 0;
  586. shifts = 0;
  587. m_bMem = FALSE;
  588. m_pInBuffer = NULL;
  589. m_nInLength = 0;
  590. m_nInCur = 0;
  591. m_OutBuffer.clear();
  592. m_nOutLength = 0;
  593. buffer_putbit = 0;
  594. mask_putbit = 128;
  595. buffer_getbit = 0;
  596. mask_getbit = 0;
  597. }
  598. }
  599. void LZARI::UnCompress(const BYTE *pInBuffer,int nInLength,const BYTE *&pOutBuffer ,int &nOutLength)
  600. {
  601. m_pInBuffer = pInBuffer;
  602. m_nInLength = nInLength;
  603. m_nInCur = 0;
  604. m_bMem = TRUE;
  605. Decode();
  606. pOutBuffer = &m_OutBuffer[0];
  607. nOutLength = m_OutBuffer.size();
  608. m_OutBuffer.push_back(0);
  609. }