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