Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * JFFS2 -- Journalling Flash File System, Version 2. | |
3 | * | |
c00c310e | 4 | * Copyright © 2001-2007 Red Hat, Inc. |
6088c058 | 5 | * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org> |
1da177e4 LT |
6 | * |
7 | * Created by Arjan van de Ven <arjanv@redhat.com> | |
8 | * | |
9 | * For licensing information, see the file 'LICENCE' in this directory. | |
10 | * | |
1da177e4 LT |
11 | */ |
12 | ||
5a528957 JP |
13 | #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt |
14 | ||
1da177e4 LT |
15 | #include <linux/string.h> |
16 | #include <linux/types.h> | |
17 | #include <linux/jffs2.h> | |
c00c310e | 18 | #include <linux/errno.h> |
1da177e4 LT |
19 | #include "compr.h" |
20 | ||
c00c310e DW |
21 | |
22 | #define RUBIN_REG_SIZE 16 | |
23 | #define UPPER_BIT_RUBIN (((long) 1)<<(RUBIN_REG_SIZE-1)) | |
24 | #define LOWER_BITS_RUBIN ((((long) 1)<<(RUBIN_REG_SIZE-1))-1) | |
25 | ||
26 | ||
c00c310e | 27 | #define BIT_DIVIDER_MIPS 1043 |
0bc4382a | 28 | static int bits_mips[8] = { 277, 249, 290, 267, 229, 341, 212, 241}; |
c00c310e DW |
29 | |
30 | struct pushpull { | |
31 | unsigned char *buf; | |
32 | unsigned int buflen; | |
33 | unsigned int ofs; | |
34 | unsigned int reserve; | |
35 | }; | |
36 | ||
f6449f4e AM |
37 | struct rubin_state { |
38 | unsigned long p; | |
39 | unsigned long q; | |
40 | unsigned long rec_q; | |
41 | long bit_number; | |
42 | struct pushpull pp; | |
43 | int bit_divider; | |
44 | int bits[8]; | |
45 | }; | |
c00c310e | 46 | |
0bc4382a DW |
47 | static inline void init_pushpull(struct pushpull *pp, char *buf, |
48 | unsigned buflen, unsigned ofs, | |
49 | unsigned reserve) | |
c00c310e DW |
50 | { |
51 | pp->buf = buf; | |
52 | pp->buflen = buflen; | |
53 | pp->ofs = ofs; | |
54 | pp->reserve = reserve; | |
55 | } | |
56 | ||
57 | static inline int pushbit(struct pushpull *pp, int bit, int use_reserved) | |
58 | { | |
0bc4382a | 59 | if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve)) |
c00c310e | 60 | return -ENOSPC; |
c00c310e | 61 | |
0bc4382a DW |
62 | if (bit) |
63 | pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs & 7))); | |
64 | else | |
65 | pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs & 7))); | |
66 | ||
c00c310e DW |
67 | pp->ofs++; |
68 | ||
69 | return 0; | |
70 | } | |
71 | ||
72 | static inline int pushedbits(struct pushpull *pp) | |
73 | { | |
74 | return pp->ofs; | |
75 | } | |
76 | ||
77 | static inline int pullbit(struct pushpull *pp) | |
78 | { | |
79 | int bit; | |
80 | ||
81 | bit = (pp->buf[pp->ofs >> 3] >> (7-(pp->ofs & 7))) & 1; | |
82 | ||
83 | pp->ofs++; | |
84 | return bit; | |
85 | } | |
86 | ||
87 | static inline int pulledbits(struct pushpull *pp) | |
88 | { | |
89 | return pp->ofs; | |
90 | } | |
91 | ||
92 | ||
1da177e4 | 93 | static void init_rubin(struct rubin_state *rs, int div, int *bits) |
182ec4ee | 94 | { |
1da177e4 LT |
95 | int c; |
96 | ||
97 | rs->q = 0; | |
98 | rs->p = (long) (2 * UPPER_BIT_RUBIN); | |
99 | rs->bit_number = (long) 0; | |
100 | rs->bit_divider = div; | |
0bc4382a | 101 | |
1da177e4 LT |
102 | for (c=0; c<8; c++) |
103 | rs->bits[c] = bits[c]; | |
104 | } | |
105 | ||
106 | ||
107 | static int encode(struct rubin_state *rs, long A, long B, int symbol) | |
108 | { | |
109 | ||
110 | long i0, i1; | |
111 | int ret; | |
112 | ||
0bc4382a DW |
113 | while ((rs->q >= UPPER_BIT_RUBIN) || |
114 | ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) { | |
1da177e4 | 115 | rs->bit_number++; |
182ec4ee | 116 | |
1da177e4 LT |
117 | ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0); |
118 | if (ret) | |
119 | return ret; | |
120 | rs->q &= LOWER_BITS_RUBIN; | |
121 | rs->q <<= 1; | |
122 | rs->p <<= 1; | |
123 | } | |
124 | i0 = A * rs->p / (A + B); | |
0bc4382a | 125 | if (i0 <= 0) |
1da177e4 | 126 | i0 = 1; |
0bc4382a DW |
127 | |
128 | if (i0 >= rs->p) | |
1da177e4 | 129 | i0 = rs->p - 1; |
0bc4382a | 130 | |
1da177e4 LT |
131 | i1 = rs->p - i0; |
132 | ||
133 | if (symbol == 0) | |
134 | rs->p = i0; | |
135 | else { | |
136 | rs->p = i1; | |
137 | rs->q += i0; | |
138 | } | |
139 | return 0; | |
140 | } | |
141 | ||
142 | ||
143 | static void end_rubin(struct rubin_state *rs) | |
182ec4ee | 144 | { |
1da177e4 LT |
145 | |
146 | int i; | |
147 | ||
148 | for (i = 0; i < RUBIN_REG_SIZE; i++) { | |
149 | pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1); | |
150 | rs->q &= LOWER_BITS_RUBIN; | |
151 | rs->q <<= 1; | |
152 | } | |
153 | } | |
154 | ||
155 | ||
156 | static void init_decode(struct rubin_state *rs, int div, int *bits) | |
157 | { | |
182ec4ee | 158 | init_rubin(rs, div, bits); |
1da177e4 LT |
159 | |
160 | /* behalve lower */ | |
161 | rs->rec_q = 0; | |
162 | ||
0bc4382a DW |
163 | for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; |
164 | rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp))) | |
1da177e4 LT |
165 | ; |
166 | } | |
167 | ||
0bc4382a DW |
168 | static void __do_decode(struct rubin_state *rs, unsigned long p, |
169 | unsigned long q) | |
1da177e4 LT |
170 | { |
171 | register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN; | |
172 | unsigned long rec_q; | |
173 | int c, bits = 0; | |
174 | ||
175 | /* | |
176 | * First, work out how many bits we need from the input stream. | |
177 | * Note that we have already done the initial check on this | |
178 | * loop prior to calling this function. | |
179 | */ | |
180 | do { | |
181 | bits++; | |
182 | q &= lower_bits_rubin; | |
183 | q <<= 1; | |
184 | p <<= 1; | |
185 | } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN)); | |
186 | ||
187 | rs->p = p; | |
188 | rs->q = q; | |
189 | ||
190 | rs->bit_number += bits; | |
191 | ||
192 | /* | |
193 | * Now get the bits. We really want this to be "get n bits". | |
194 | */ | |
195 | rec_q = rs->rec_q; | |
196 | do { | |
197 | c = pullbit(&rs->pp); | |
198 | rec_q &= lower_bits_rubin; | |
199 | rec_q <<= 1; | |
200 | rec_q += c; | |
201 | } while (--bits); | |
202 | rs->rec_q = rec_q; | |
203 | } | |
204 | ||
205 | static int decode(struct rubin_state *rs, long A, long B) | |
206 | { | |
207 | unsigned long p = rs->p, q = rs->q; | |
208 | long i0, threshold; | |
209 | int symbol; | |
210 | ||
211 | if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN)) | |
212 | __do_decode(rs, p, q); | |
213 | ||
214 | i0 = A * rs->p / (A + B); | |
0bc4382a | 215 | if (i0 <= 0) |
1da177e4 | 216 | i0 = 1; |
0bc4382a DW |
217 | |
218 | if (i0 >= rs->p) | |
1da177e4 | 219 | i0 = rs->p - 1; |
1da177e4 LT |
220 | |
221 | threshold = rs->q + i0; | |
222 | symbol = rs->rec_q >= threshold; | |
223 | if (rs->rec_q >= threshold) { | |
224 | rs->q += i0; | |
225 | i0 = rs->p - i0; | |
226 | } | |
227 | ||
228 | rs->p = i0; | |
229 | ||
230 | return symbol; | |
231 | } | |
232 | ||
233 | ||
234 | ||
235 | static int out_byte(struct rubin_state *rs, unsigned char byte) | |
236 | { | |
237 | int i, ret; | |
238 | struct rubin_state rs_copy; | |
239 | rs_copy = *rs; | |
240 | ||
0bc4382a DW |
241 | for (i=0; i<8; i++) { |
242 | ret = encode(rs, rs->bit_divider-rs->bits[i], | |
243 | rs->bits[i], byte & 1); | |
1da177e4 LT |
244 | if (ret) { |
245 | /* Failed. Restore old state */ | |
246 | *rs = rs_copy; | |
247 | return ret; | |
248 | } | |
0bc4382a | 249 | byte >>= 1 ; |
1da177e4 LT |
250 | } |
251 | return 0; | |
252 | } | |
253 | ||
254 | static int in_byte(struct rubin_state *rs) | |
255 | { | |
256 | int i, result = 0, bit_divider = rs->bit_divider; | |
257 | ||
258 | for (i = 0; i < 8; i++) | |
0bc4382a DW |
259 | result |= decode(rs, bit_divider - rs->bits[i], |
260 | rs->bits[i]) << i; | |
1da177e4 LT |
261 | |
262 | return result; | |
263 | } | |
264 | ||
265 | ||
266 | ||
182ec4ee | 267 | static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in, |
0bc4382a DW |
268 | unsigned char *cpage_out, uint32_t *sourcelen, |
269 | uint32_t *dstlen) | |
1da177e4 LT |
270 | { |
271 | int outpos = 0; | |
272 | int pos=0; | |
273 | struct rubin_state rs; | |
274 | ||
275 | init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32); | |
276 | ||
277 | init_rubin(&rs, bit_divider, bits); | |
182ec4ee | 278 | |
1da177e4 LT |
279 | while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos])) |
280 | pos++; | |
182ec4ee | 281 | |
1da177e4 LT |
282 | end_rubin(&rs); |
283 | ||
284 | if (outpos > pos) { | |
285 | /* We failed */ | |
286 | return -1; | |
287 | } | |
182ec4ee TG |
288 | |
289 | /* Tell the caller how much we managed to compress, | |
1da177e4 | 290 | * and how much space it took */ |
182ec4ee | 291 | |
1da177e4 | 292 | outpos = (pushedbits(&rs.pp)+7)/8; |
182ec4ee | 293 | |
1da177e4 LT |
294 | if (outpos >= pos) |
295 | return -1; /* We didn't actually compress */ | |
296 | *sourcelen = pos; | |
297 | *dstlen = outpos; | |
298 | return 0; | |
182ec4ee | 299 | } |
1da177e4 LT |
300 | #if 0 |
301 | /* _compress returns the compressed size, -1 if bigger */ | |
182ec4ee | 302 | int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out, |
088bd455 | 303 | uint32_t *sourcelen, uint32_t *dstlen) |
1da177e4 | 304 | { |
0bc4382a DW |
305 | return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, |
306 | cpage_out, sourcelen, dstlen); | |
1da177e4 LT |
307 | } |
308 | #endif | |
75c96f85 AB |
309 | static int jffs2_dynrubin_compress(unsigned char *data_in, |
310 | unsigned char *cpage_out, | |
088bd455 | 311 | uint32_t *sourcelen, uint32_t *dstlen) |
1da177e4 LT |
312 | { |
313 | int bits[8]; | |
314 | unsigned char histo[256]; | |
315 | int i; | |
316 | int ret; | |
317 | uint32_t mysrclen, mydstlen; | |
318 | ||
319 | mysrclen = *sourcelen; | |
320 | mydstlen = *dstlen - 8; | |
321 | ||
322 | if (*dstlen <= 12) | |
323 | return -1; | |
324 | ||
325 | memset(histo, 0, 256); | |
0bc4382a | 326 | for (i=0; i<mysrclen; i++) |
1da177e4 | 327 | histo[data_in[i]]++; |
1da177e4 LT |
328 | memset(bits, 0, sizeof(int)*8); |
329 | for (i=0; i<256; i++) { | |
330 | if (i&128) | |
331 | bits[7] += histo[i]; | |
332 | if (i&64) | |
333 | bits[6] += histo[i]; | |
334 | if (i&32) | |
335 | bits[5] += histo[i]; | |
336 | if (i&16) | |
337 | bits[4] += histo[i]; | |
338 | if (i&8) | |
339 | bits[3] += histo[i]; | |
340 | if (i&4) | |
341 | bits[2] += histo[i]; | |
342 | if (i&2) | |
343 | bits[1] += histo[i]; | |
344 | if (i&1) | |
345 | bits[0] += histo[i]; | |
346 | } | |
347 | ||
348 | for (i=0; i<8; i++) { | |
349 | bits[i] = (bits[i] * 256) / mysrclen; | |
350 | if (!bits[i]) bits[i] = 1; | |
351 | if (bits[i] > 255) bits[i] = 255; | |
352 | cpage_out[i] = bits[i]; | |
353 | } | |
354 | ||
0bc4382a DW |
355 | ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, |
356 | &mydstlen); | |
182ec4ee | 357 | if (ret) |
1da177e4 LT |
358 | return ret; |
359 | ||
360 | /* Add back the 8 bytes we took for the probabilities */ | |
361 | mydstlen += 8; | |
362 | ||
363 | if (mysrclen <= mydstlen) { | |
364 | /* We compressed */ | |
365 | return -1; | |
366 | } | |
367 | ||
368 | *sourcelen = mysrclen; | |
369 | *dstlen = mydstlen; | |
370 | return 0; | |
371 | } | |
372 | ||
0bc4382a DW |
373 | static void rubin_do_decompress(int bit_divider, int *bits, |
374 | unsigned char *cdata_in, | |
375 | unsigned char *page_out, uint32_t srclen, | |
376 | uint32_t destlen) | |
1da177e4 LT |
377 | { |
378 | int outpos = 0; | |
379 | struct rubin_state rs; | |
182ec4ee | 380 | |
1da177e4 LT |
381 | init_pushpull(&rs.pp, cdata_in, srclen, 0, 0); |
382 | init_decode(&rs, bit_divider, bits); | |
182ec4ee | 383 | |
0bc4382a | 384 | while (outpos < destlen) |
1da177e4 | 385 | page_out[outpos++] = in_byte(&rs); |
182ec4ee | 386 | } |
1da177e4 LT |
387 | |
388 | ||
75c96f85 AB |
389 | static int jffs2_rubinmips_decompress(unsigned char *data_in, |
390 | unsigned char *cpage_out, | |
088bd455 | 391 | uint32_t sourcelen, uint32_t dstlen) |
1da177e4 | 392 | { |
0bc4382a DW |
393 | rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, |
394 | cpage_out, sourcelen, dstlen); | |
ef53cb02 | 395 | return 0; |
1da177e4 LT |
396 | } |
397 | ||
75c96f85 AB |
398 | static int jffs2_dynrubin_decompress(unsigned char *data_in, |
399 | unsigned char *cpage_out, | |
088bd455 | 400 | uint32_t sourcelen, uint32_t dstlen) |
1da177e4 LT |
401 | { |
402 | int bits[8]; | |
403 | int c; | |
404 | ||
405 | for (c=0; c<8; c++) | |
406 | bits[c] = data_in[c]; | |
407 | ||
0bc4382a DW |
408 | rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, |
409 | dstlen); | |
ef53cb02 | 410 | return 0; |
1da177e4 LT |
411 | } |
412 | ||
413 | static struct jffs2_compressor jffs2_rubinmips_comp = { | |
0bc4382a DW |
414 | .priority = JFFS2_RUBINMIPS_PRIORITY, |
415 | .name = "rubinmips", | |
416 | .compr = JFFS2_COMPR_DYNRUBIN, | |
417 | .compress = NULL, /*&jffs2_rubinmips_compress,*/ | |
418 | .decompress = &jffs2_rubinmips_decompress, | |
1da177e4 | 419 | #ifdef JFFS2_RUBINMIPS_DISABLED |
0bc4382a | 420 | .disabled = 1, |
1da177e4 | 421 | #else |
0bc4382a | 422 | .disabled = 0, |
1da177e4 LT |
423 | #endif |
424 | }; | |
425 | ||
426 | int jffs2_rubinmips_init(void) | |
427 | { | |
0bc4382a | 428 | return jffs2_register_compressor(&jffs2_rubinmips_comp); |
1da177e4 LT |
429 | } |
430 | ||
431 | void jffs2_rubinmips_exit(void) | |
432 | { | |
0bc4382a | 433 | jffs2_unregister_compressor(&jffs2_rubinmips_comp); |
1da177e4 LT |
434 | } |
435 | ||
436 | static struct jffs2_compressor jffs2_dynrubin_comp = { | |
0bc4382a DW |
437 | .priority = JFFS2_DYNRUBIN_PRIORITY, |
438 | .name = "dynrubin", | |
439 | .compr = JFFS2_COMPR_RUBINMIPS, | |
440 | .compress = jffs2_dynrubin_compress, | |
441 | .decompress = &jffs2_dynrubin_decompress, | |
1da177e4 | 442 | #ifdef JFFS2_DYNRUBIN_DISABLED |
0bc4382a | 443 | .disabled = 1, |
1da177e4 | 444 | #else |
0bc4382a | 445 | .disabled = 0, |
1da177e4 LT |
446 | #endif |
447 | }; | |
448 | ||
449 | int jffs2_dynrubin_init(void) | |
450 | { | |
0bc4382a | 451 | return jffs2_register_compressor(&jffs2_dynrubin_comp); |
1da177e4 LT |
452 | } |
453 | ||
454 | void jffs2_dynrubin_exit(void) | |
455 | { | |
0bc4382a | 456 | jffs2_unregister_compressor(&jffs2_dynrubin_comp); |
1da177e4 | 457 | } |