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