compr_lzari.c 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259
  1. /*
  2. * JFFS2 -- Journalling Flash File System, Version 2.
  3. *
  4. * Copyright (C) 2004 Patrik Kluba,
  5. * University of Szeged, Hungary
  6. *
  7. * For licensing information, see the file 'LICENCE' in the
  8. * jffs2 directory.
  9. *
  10. * $Id: compr_lzari.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
  11. *
  12. */
  13. /*
  14. Lempel-Ziv-Arithmetic coding compression module for jffs2
  15. Based on the LZARI source included in LDS (lossless datacompression sources)
  16. */
  17. /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
  18. /*
  19. Original copyright follows:
  20. **************************************************************
  21. LZARI.C -- A Data Compression Program
  22. (tab = 4 spaces)
  23. **************************************************************
  24. 4/7/1989 Haruhiko Okumura
  25. Use, distribute, and modify this program freely.
  26. Please send me your improved versions.
  27. PC-VAN SCIENCE
  28. NIFTY-Serve PAF01022
  29. CompuServe 74050,1022
  30. **************************************************************
  31. LZARI.C (c)1989 by Haruyasu Yoshizaki, Haruhiko Okumura, and Kenji Rikitake.
  32. All rights reserved. Permission granted for non-commercial use.
  33. */
  34. /*
  35. 2004-02-18 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
  36. Removed unused variables and fixed no return value
  37. 2004-02-16 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
  38. Initial release
  39. */
  40. #include <config.h>
  41. #include <linux/stddef.h>
  42. #include <jffs2/jffs2.h>
  43. #define N 4096 /* size of ring buffer */
  44. #define F 60 /* upper limit for match_length */
  45. #define THRESHOLD 2 /* encode string into position and length
  46. if match_length is greater than this */
  47. #define NIL N /* index for root of binary search trees */
  48. static unsigned char
  49. text_buf[N + F - 1]; /* ring buffer of size N,
  50. with extra F-1 bytes to facilitate string comparison */
  51. /********** Arithmetic Compression **********/
  52. /* If you are not familiar with arithmetic compression, you should read
  53. I. E. Witten, R. M. Neal, and J. G. Cleary,
  54. Communications of the ACM, Vol. 30, pp. 520-540 (1987),
  55. from which much have been borrowed. */
  56. #define M 15
  57. /* Q1 (= 2 to the M) must be sufficiently large, but not so
  58. large as the unsigned long 4 * Q1 * (Q1 - 1) overflows. */
  59. #define Q1 (1UL << M)
  60. #define Q2 (2 * Q1)
  61. #define Q3 (3 * Q1)
  62. #define Q4 (4 * Q1)
  63. #define MAX_CUM (Q1 - 1)
  64. #define N_CHAR (256 - THRESHOLD + F)
  65. /* character code = 0, 1, ..., N_CHAR - 1 */
  66. static unsigned long char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
  67. static unsigned long
  68. sym_freq[N_CHAR + 1], /* frequency for symbols */
  69. sym_cum[N_CHAR + 1], /* cumulative freq for symbols */
  70. position_cum[N + 1]; /* cumulative freq for positions */
  71. static void StartModel(void) /* Initialize model */
  72. {
  73. unsigned long ch, sym, i;
  74. sym_cum[N_CHAR] = 0;
  75. for (sym = N_CHAR; sym >= 1; sym--) {
  76. ch = sym - 1;
  77. char_to_sym[ch] = sym; sym_to_char[sym] = ch;
  78. sym_freq[sym] = 1;
  79. sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
  80. }
  81. sym_freq[0] = 0; /* sentinel (!= sym_freq[1]) */
  82. position_cum[N] = 0;
  83. for (i = N; i >= 1; i--)
  84. position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
  85. /* empirical distribution function (quite tentative) */
  86. /* Please devise a better mechanism! */
  87. }
  88. static void UpdateModel(unsigned long sym)
  89. {
  90. unsigned long c, ch_i, ch_sym;
  91. unsigned long i;
  92. if (sym_cum[0] >= MAX_CUM) {
  93. c = 0;
  94. for (i = N_CHAR; i > 0; i--) {
  95. sym_cum[i] = c;
  96. c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
  97. }
  98. sym_cum[0] = c;
  99. }
  100. for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
  101. if (i < sym) {
  102. ch_i = sym_to_char[i]; ch_sym = sym_to_char[sym];
  103. sym_to_char[i] = ch_sym; sym_to_char[sym] = ch_i;
  104. char_to_sym[ch_i] = sym; char_to_sym[ch_sym] = i;
  105. }
  106. sym_freq[i]++;
  107. while (--i > 0) sym_cum[i]++;
  108. sym_cum[0]++;
  109. }
  110. static unsigned long BinarySearchSym(unsigned long x)
  111. /* 1 if x >= sym_cum[1],
  112. N_CHAR if sym_cum[N_CHAR] > x,
  113. i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
  114. {
  115. unsigned long i, j, k;
  116. i = 1; j = N_CHAR;
  117. while (i < j) {
  118. k = (i + j) / 2;
  119. if (sym_cum[k] > x) i = k + 1; else j = k;
  120. }
  121. return i;
  122. }
  123. unsigned long BinarySearchPos(unsigned long x)
  124. /* 0 if x >= position_cum[1],
  125. N - 1 if position_cum[N] > x,
  126. i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
  127. {
  128. unsigned long i, j, k;
  129. i = 1; j = N;
  130. while (i < j) {
  131. k = (i + j) / 2;
  132. if (position_cum[k] > x) i = k + 1; else j = k;
  133. }
  134. return i - 1;
  135. }
  136. static int Decode(unsigned char *srcbuf, unsigned char *dstbuf, unsigned long srclen,
  137. unsigned long dstlen) /* Just the reverse of Encode(). */
  138. {
  139. unsigned long i, r, j, k, c, range, sym;
  140. unsigned char *ip, *op;
  141. unsigned char *srcend = srcbuf + srclen;
  142. unsigned char *dstend = dstbuf + dstlen;
  143. unsigned char buffer = 0;
  144. unsigned char mask = 0;
  145. unsigned long low = 0;
  146. unsigned long high = Q4;
  147. unsigned long value = 0;
  148. ip = srcbuf;
  149. op = dstbuf;
  150. for (i = 0; i < M + 2; i++) {
  151. value *= 2;
  152. if ((mask >>= 1) == 0) {
  153. buffer = (ip >= srcend) ? 0 : *(ip++);
  154. mask = 128;
  155. }
  156. value += ((buffer & mask) != 0);
  157. }
  158. StartModel();
  159. for (i = 0; i < N - F; i++) text_buf[i] = ' ';
  160. r = N - F;
  161. while (op < dstend) {
  162. range = high - low;
  163. sym = BinarySearchSym((unsigned long)
  164. (((value - low + 1) * sym_cum[0] - 1) / range));
  165. high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  166. low += (range * sym_cum[sym ]) / sym_cum[0];
  167. for ( ; ; ) {
  168. if (low >= Q2) {
  169. value -= Q2; low -= Q2; high -= Q2;
  170. } else if (low >= Q1 && high <= Q3) {
  171. value -= Q1; low -= Q1; high -= Q1;
  172. } else if (high > Q2) break;
  173. low += low; high += high;
  174. value *= 2;
  175. if ((mask >>= 1) == 0) {
  176. buffer = (ip >= srcend) ? 0 : *(ip++);
  177. mask = 128;
  178. }
  179. value += ((buffer & mask) != 0);
  180. }
  181. c = sym_to_char[sym];
  182. UpdateModel(sym);
  183. if (c < 256) {
  184. if (op >= dstend) return -1;
  185. *(op++) = c;
  186. text_buf[r++] = c;
  187. r &= (N - 1);
  188. } else {
  189. j = c - 255 + THRESHOLD;
  190. range = high - low;
  191. i = BinarySearchPos((unsigned long)
  192. (((value - low + 1) * position_cum[0] - 1) / range));
  193. high = low + (range * position_cum[i ]) / position_cum[0];
  194. low += (range * position_cum[i + 1]) / position_cum[0];
  195. for ( ; ; ) {
  196. if (low >= Q2) {
  197. value -= Q2; low -= Q2; high -= Q2;
  198. } else if (low >= Q1 && high <= Q3) {
  199. value -= Q1; low -= Q1; high -= Q1;
  200. } else if (high > Q2) break;
  201. low += low; high += high;
  202. value *= 2;
  203. if ((mask >>= 1) == 0) {
  204. buffer = (ip >= srcend) ? 0 : *(ip++);
  205. mask = 128;
  206. }
  207. value += ((buffer & mask) != 0);
  208. }
  209. i = (r - i - 1) & (N - 1);
  210. for (k = 0; k < j; k++) {
  211. c = text_buf[(i + k) & (N - 1)];
  212. if (op >= dstend) return -1;
  213. *(op++) = c;
  214. text_buf[r++] = c;
  215. r &= (N - 1);
  216. }
  217. }
  218. }
  219. return 0;
  220. }
  221. int lzari_decompress(unsigned char *data_in, unsigned char *cpage_out,
  222. u32 srclen, u32 destlen)
  223. {
  224. return Decode(data_in, cpage_out, srclen, destlen);
  225. }