blob: e792e675d624eecb5fcabfd4dc33cebf7c527bfa [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * JFFS2 -- Journalling Flash File System, Version 2.
3 *
4 * Copyright (C) 2001, 2002 Red Hat, Inc.
5 *
6 * Created by Arjan van de Ven <arjanv@redhat.com>
7 *
8 * For licensing information, see the file 'LICENCE' in this directory.
9 *
10 * $Id: compr_rubin.c,v 1.20 2004/06/23 16:34:40 havasi Exp $
11 *
12 */
13
Linus Torvalds1da177e2005-04-16 15:20:36 -070014#include <linux/string.h>
15#include <linux/types.h>
16#include <linux/jffs2.h>
17#include "compr_rubin.h"
18#include "histo_mips.h"
19#include "compr.h"
20
21static void init_rubin(struct rubin_state *rs, int div, int *bits)
Thomas Gleixner182ec4e2005-11-07 11:16:07 +000022{
Linus Torvalds1da177e2005-04-16 15:20:36 -070023 int c;
24
25 rs->q = 0;
26 rs->p = (long) (2 * UPPER_BIT_RUBIN);
27 rs->bit_number = (long) 0;
28 rs->bit_divider = div;
29 for (c=0; c<8; c++)
30 rs->bits[c] = bits[c];
31}
32
33
34static int encode(struct rubin_state *rs, long A, long B, int symbol)
35{
36
37 long i0, i1;
38 int ret;
39
40 while ((rs->q >= UPPER_BIT_RUBIN) || ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
41 rs->bit_number++;
Thomas Gleixner182ec4e2005-11-07 11:16:07 +000042
Linus Torvalds1da177e2005-04-16 15:20:36 -070043 ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
44 if (ret)
45 return ret;
46 rs->q &= LOWER_BITS_RUBIN;
47 rs->q <<= 1;
48 rs->p <<= 1;
49 }
50 i0 = A * rs->p / (A + B);
51 if (i0 <= 0) {
52 i0 = 1;
53 }
54 if (i0 >= rs->p) {
55 i0 = rs->p - 1;
56 }
57 i1 = rs->p - i0;
58
59 if (symbol == 0)
60 rs->p = i0;
61 else {
62 rs->p = i1;
63 rs->q += i0;
64 }
65 return 0;
66}
67
68
69static void end_rubin(struct rubin_state *rs)
Thomas Gleixner182ec4e2005-11-07 11:16:07 +000070{
Linus Torvalds1da177e2005-04-16 15:20:36 -070071
72 int i;
73
74 for (i = 0; i < RUBIN_REG_SIZE; i++) {
75 pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);
76 rs->q &= LOWER_BITS_RUBIN;
77 rs->q <<= 1;
78 }
79}
80
81
82static void init_decode(struct rubin_state *rs, int div, int *bits)
83{
Thomas Gleixner182ec4e2005-11-07 11:16:07 +000084 init_rubin(rs, div, bits);
Linus Torvalds1da177e2005-04-16 15:20:36 -070085
86 /* behalve lower */
87 rs->rec_q = 0;
88
89 for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
90 ;
91}
92
93static void __do_decode(struct rubin_state *rs, unsigned long p, unsigned long q)
94{
95 register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
96 unsigned long rec_q;
97 int c, bits = 0;
98
99 /*
100 * First, work out how many bits we need from the input stream.
101 * Note that we have already done the initial check on this
102 * loop prior to calling this function.
103 */
104 do {
105 bits++;
106 q &= lower_bits_rubin;
107 q <<= 1;
108 p <<= 1;
109 } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
110
111 rs->p = p;
112 rs->q = q;
113
114 rs->bit_number += bits;
115
116 /*
117 * Now get the bits. We really want this to be "get n bits".
118 */
119 rec_q = rs->rec_q;
120 do {
121 c = pullbit(&rs->pp);
122 rec_q &= lower_bits_rubin;
123 rec_q <<= 1;
124 rec_q += c;
125 } while (--bits);
126 rs->rec_q = rec_q;
127}
128
129static int decode(struct rubin_state *rs, long A, long B)
130{
131 unsigned long p = rs->p, q = rs->q;
132 long i0, threshold;
133 int symbol;
134
135 if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN))
136 __do_decode(rs, p, q);
137
138 i0 = A * rs->p / (A + B);
139 if (i0 <= 0) {
140 i0 = 1;
141 }
142 if (i0 >= rs->p) {
143 i0 = rs->p - 1;
144 }
145
146 threshold = rs->q + i0;
147 symbol = rs->rec_q >= threshold;
148 if (rs->rec_q >= threshold) {
149 rs->q += i0;
150 i0 = rs->p - i0;
151 }
152
153 rs->p = i0;
154
155 return symbol;
156}
157
158
159
160static int out_byte(struct rubin_state *rs, unsigned char byte)
161{
162 int i, ret;
163 struct rubin_state rs_copy;
164 rs_copy = *rs;
165
166 for (i=0;i<8;i++) {
167 ret = encode(rs, rs->bit_divider-rs->bits[i],rs->bits[i],byte&1);
168 if (ret) {
169 /* Failed. Restore old state */
170 *rs = rs_copy;
171 return ret;
172 }
173 byte=byte>>1;
174 }
175 return 0;
176}
177
178static int in_byte(struct rubin_state *rs)
179{
180 int i, result = 0, bit_divider = rs->bit_divider;
181
182 for (i = 0; i < 8; i++)
183 result |= decode(rs, bit_divider - rs->bits[i], rs->bits[i]) << i;
184
185 return result;
186}
187
188
189
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000190static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191 unsigned char *cpage_out, uint32_t *sourcelen, uint32_t *dstlen)
192 {
193 int outpos = 0;
194 int pos=0;
195 struct rubin_state rs;
196
197 init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
198
199 init_rubin(&rs, bit_divider, bits);
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000200
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201 while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
202 pos++;
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000203
Linus Torvalds1da177e2005-04-16 15:20:36 -0700204 end_rubin(&rs);
205
206 if (outpos > pos) {
207 /* We failed */
208 return -1;
209 }
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000210
211 /* Tell the caller how much we managed to compress,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700212 * and how much space it took */
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000213
Linus Torvalds1da177e2005-04-16 15:20:36 -0700214 outpos = (pushedbits(&rs.pp)+7)/8;
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000215
Linus Torvalds1da177e2005-04-16 15:20:36 -0700216 if (outpos >= pos)
217 return -1; /* We didn't actually compress */
218 *sourcelen = pos;
219 *dstlen = outpos;
220 return 0;
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000221}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700222#if 0
223/* _compress returns the compressed size, -1 if bigger */
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000224int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700225 uint32_t *sourcelen, uint32_t *dstlen, void *model)
226{
227 return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
228}
229#endif
Adrian Bunk75c96f82005-05-05 16:16:09 -0700230static int jffs2_dynrubin_compress(unsigned char *data_in,
231 unsigned char *cpage_out,
232 uint32_t *sourcelen, uint32_t *dstlen,
233 void *model)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700234{
235 int bits[8];
236 unsigned char histo[256];
237 int i;
238 int ret;
239 uint32_t mysrclen, mydstlen;
240
241 mysrclen = *sourcelen;
242 mydstlen = *dstlen - 8;
243
244 if (*dstlen <= 12)
245 return -1;
246
247 memset(histo, 0, 256);
248 for (i=0; i<mysrclen; i++) {
249 histo[data_in[i]]++;
250 }
251 memset(bits, 0, sizeof(int)*8);
252 for (i=0; i<256; i++) {
253 if (i&128)
254 bits[7] += histo[i];
255 if (i&64)
256 bits[6] += histo[i];
257 if (i&32)
258 bits[5] += histo[i];
259 if (i&16)
260 bits[4] += histo[i];
261 if (i&8)
262 bits[3] += histo[i];
263 if (i&4)
264 bits[2] += histo[i];
265 if (i&2)
266 bits[1] += histo[i];
267 if (i&1)
268 bits[0] += histo[i];
269 }
270
271 for (i=0; i<8; i++) {
272 bits[i] = (bits[i] * 256) / mysrclen;
273 if (!bits[i]) bits[i] = 1;
274 if (bits[i] > 255) bits[i] = 255;
275 cpage_out[i] = bits[i];
276 }
277
278 ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen);
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000279 if (ret)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280 return ret;
281
282 /* Add back the 8 bytes we took for the probabilities */
283 mydstlen += 8;
284
285 if (mysrclen <= mydstlen) {
286 /* We compressed */
287 return -1;
288 }
289
290 *sourcelen = mysrclen;
291 *dstlen = mydstlen;
292 return 0;
293}
294
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000295static void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700296 unsigned char *page_out, uint32_t srclen, uint32_t destlen)
297{
298 int outpos = 0;
299 struct rubin_state rs;
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000300
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301 init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
302 init_decode(&rs, bit_divider, bits);
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000303
Linus Torvalds1da177e2005-04-16 15:20:36 -0700304 while (outpos < destlen) {
305 page_out[outpos++] = in_byte(&rs);
306 }
Thomas Gleixner182ec4e2005-11-07 11:16:07 +0000307}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308
309
Adrian Bunk75c96f82005-05-05 16:16:09 -0700310static int jffs2_rubinmips_decompress(unsigned char *data_in,
311 unsigned char *cpage_out,
312 uint32_t sourcelen, uint32_t dstlen,
313 void *model)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700314{
315 rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
316 return 0;
317}
318
Adrian Bunk75c96f82005-05-05 16:16:09 -0700319static int jffs2_dynrubin_decompress(unsigned char *data_in,
320 unsigned char *cpage_out,
321 uint32_t sourcelen, uint32_t dstlen,
322 void *model)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700323{
324 int bits[8];
325 int c;
326
327 for (c=0; c<8; c++)
328 bits[c] = data_in[c];
329
330 rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen);
331 return 0;
332}
333
334static struct jffs2_compressor jffs2_rubinmips_comp = {
335 .priority = JFFS2_RUBINMIPS_PRIORITY,
336 .name = "rubinmips",
337 .compr = JFFS2_COMPR_DYNRUBIN,
338 .compress = NULL, /*&jffs2_rubinmips_compress,*/
339 .decompress = &jffs2_rubinmips_decompress,
340#ifdef JFFS2_RUBINMIPS_DISABLED
341 .disabled = 1,
342#else
343 .disabled = 0,
344#endif
345};
346
347int jffs2_rubinmips_init(void)
348{
349 return jffs2_register_compressor(&jffs2_rubinmips_comp);
350}
351
352void jffs2_rubinmips_exit(void)
353{
354 jffs2_unregister_compressor(&jffs2_rubinmips_comp);
355}
356
357static struct jffs2_compressor jffs2_dynrubin_comp = {
358 .priority = JFFS2_DYNRUBIN_PRIORITY,
359 .name = "dynrubin",
360 .compr = JFFS2_COMPR_RUBINMIPS,
361 .compress = jffs2_dynrubin_compress,
362 .decompress = &jffs2_dynrubin_decompress,
363#ifdef JFFS2_DYNRUBIN_DISABLED
364 .disabled = 1,
365#else
366 .disabled = 0,
367#endif
368};
369
370int jffs2_dynrubin_init(void)
371{
372 return jffs2_register_compressor(&jffs2_dynrubin_comp);
373}
374
375void jffs2_dynrubin_exit(void)
376{
377 jffs2_unregister_compressor(&jffs2_dynrubin_comp);
378}