diff options
author | Lachlan McIlroy <lachlan@redback.melbourne.sgi.com> | 2009-01-14 00:29:08 -0500 |
---|---|---|
committer | Lachlan McIlroy <lachlan@redback.melbourne.sgi.com> | 2009-01-14 00:29:08 -0500 |
commit | c088f4e9da74b901f7ed1749ad697d77622ed0f9 (patch) | |
tree | 84cddf20369f82f10c1c3712e6cce20dd1b9d863 /fs/jffs2/compr_rubin.c | |
parent | ce79735c12d62c3cda38eb31762cf98e87c7b087 (diff) | |
parent | a6525042bfdfcab128bd91fad264de10fd24a55e (diff) |
Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6
Diffstat (limited to 'fs/jffs2/compr_rubin.c')
-rw-r--r-- | fs/jffs2/compr_rubin.c | 120 |
1 files changed, 64 insertions, 56 deletions
diff --git a/fs/jffs2/compr_rubin.c b/fs/jffs2/compr_rubin.c index c73fa89b5f8a..170d289ac785 100644 --- a/fs/jffs2/compr_rubin.c +++ b/fs/jffs2/compr_rubin.c | |||
@@ -22,9 +22,7 @@ | |||
22 | 22 | ||
23 | 23 | ||
24 | #define BIT_DIVIDER_MIPS 1043 | 24 | #define BIT_DIVIDER_MIPS 1043 |
25 | static int bits_mips[8] = { 277,249,290,267,229,341,212,241}; /* mips32 */ | 25 | static int bits_mips[8] = { 277, 249, 290, 267, 229, 341, 212, 241}; |
26 | |||
27 | #include <linux/errno.h> | ||
28 | 26 | ||
29 | struct pushpull { | 27 | struct pushpull { |
30 | unsigned char *buf; | 28 | unsigned char *buf; |
@@ -43,7 +41,9 @@ struct rubin_state { | |||
43 | int bits[8]; | 41 | int bits[8]; |
44 | }; | 42 | }; |
45 | 43 | ||
46 | static inline void init_pushpull(struct pushpull *pp, char *buf, unsigned buflen, unsigned ofs, unsigned reserve) | 44 | static inline void init_pushpull(struct pushpull *pp, char *buf, |
45 | unsigned buflen, unsigned ofs, | ||
46 | unsigned reserve) | ||
47 | { | 47 | { |
48 | pp->buf = buf; | 48 | pp->buf = buf; |
49 | pp->buflen = buflen; | 49 | pp->buflen = buflen; |
@@ -53,16 +53,14 @@ static inline void init_pushpull(struct pushpull *pp, char *buf, unsigned buflen | |||
53 | 53 | ||
54 | static inline int pushbit(struct pushpull *pp, int bit, int use_reserved) | 54 | static inline int pushbit(struct pushpull *pp, int bit, int use_reserved) |
55 | { | 55 | { |
56 | if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve)) { | 56 | if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve)) |
57 | return -ENOSPC; | 57 | return -ENOSPC; |
58 | } | ||
59 | 58 | ||
60 | if (bit) { | 59 | if (bit) |
61 | pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs &7))); | 60 | pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs & 7))); |
62 | } | 61 | else |
63 | else { | 62 | pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs & 7))); |
64 | pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs &7))); | 63 | |
65 | } | ||
66 | pp->ofs++; | 64 | pp->ofs++; |
67 | 65 | ||
68 | return 0; | 66 | return 0; |
@@ -97,6 +95,7 @@ static void init_rubin(struct rubin_state *rs, int div, int *bits) | |||
97 | rs->p = (long) (2 * UPPER_BIT_RUBIN); | 95 | rs->p = (long) (2 * UPPER_BIT_RUBIN); |
98 | rs->bit_number = (long) 0; | 96 | rs->bit_number = (long) 0; |
99 | rs->bit_divider = div; | 97 | rs->bit_divider = div; |
98 | |||
100 | for (c=0; c<8; c++) | 99 | for (c=0; c<8; c++) |
101 | rs->bits[c] = bits[c]; | 100 | rs->bits[c] = bits[c]; |
102 | } | 101 | } |
@@ -108,7 +107,8 @@ static int encode(struct rubin_state *rs, long A, long B, int symbol) | |||
108 | long i0, i1; | 107 | long i0, i1; |
109 | int ret; | 108 | int ret; |
110 | 109 | ||
111 | while ((rs->q >= UPPER_BIT_RUBIN) || ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) { | 110 | while ((rs->q >= UPPER_BIT_RUBIN) || |
111 | ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) { | ||
112 | rs->bit_number++; | 112 | rs->bit_number++; |
113 | 113 | ||
114 | ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0); | 114 | ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0); |
@@ -119,12 +119,12 @@ static int encode(struct rubin_state *rs, long A, long B, int symbol) | |||
119 | rs->p <<= 1; | 119 | rs->p <<= 1; |
120 | } | 120 | } |
121 | i0 = A * rs->p / (A + B); | 121 | i0 = A * rs->p / (A + B); |
122 | if (i0 <= 0) { | 122 | if (i0 <= 0) |
123 | i0 = 1; | 123 | i0 = 1; |
124 | } | 124 | |
125 | if (i0 >= rs->p) { | 125 | if (i0 >= rs->p) |
126 | i0 = rs->p - 1; | 126 | i0 = rs->p - 1; |
127 | } | 127 | |
128 | i1 = rs->p - i0; | 128 | i1 = rs->p - i0; |
129 | 129 | ||
130 | if (symbol == 0) | 130 | if (symbol == 0) |
@@ -157,11 +157,13 @@ static void init_decode(struct rubin_state *rs, int div, int *bits) | |||
157 | /* behalve lower */ | 157 | /* behalve lower */ |
158 | rs->rec_q = 0; | 158 | rs->rec_q = 0; |
159 | 159 | ||
160 | for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp))) | 160 | for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; |
161 | rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp))) | ||
161 | ; | 162 | ; |
162 | } | 163 | } |
163 | 164 | ||
164 | static void __do_decode(struct rubin_state *rs, unsigned long p, unsigned long q) | 165 | static void __do_decode(struct rubin_state *rs, unsigned long p, |
166 | unsigned long q) | ||
165 | { | 167 | { |
166 | register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN; | 168 | register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN; |
167 | unsigned long rec_q; | 169 | unsigned long rec_q; |
@@ -207,12 +209,11 @@ static int decode(struct rubin_state *rs, long A, long B) | |||
207 | __do_decode(rs, p, q); | 209 | __do_decode(rs, p, q); |
208 | 210 | ||
209 | i0 = A * rs->p / (A + B); | 211 | i0 = A * rs->p / (A + B); |
210 | if (i0 <= 0) { | 212 | if (i0 <= 0) |
211 | i0 = 1; | 213 | i0 = 1; |
212 | } | 214 | |
213 | if (i0 >= rs->p) { | 215 | if (i0 >= rs->p) |
214 | i0 = rs->p - 1; | 216 | i0 = rs->p - 1; |
215 | } | ||
216 | 217 | ||
217 | threshold = rs->q + i0; | 218 | threshold = rs->q + i0; |
218 | symbol = rs->rec_q >= threshold; | 219 | symbol = rs->rec_q >= threshold; |
@@ -234,14 +235,15 @@ static int out_byte(struct rubin_state *rs, unsigned char byte) | |||
234 | struct rubin_state rs_copy; | 235 | struct rubin_state rs_copy; |
235 | rs_copy = *rs; | 236 | rs_copy = *rs; |
236 | 237 | ||
237 | for (i=0;i<8;i++) { | 238 | for (i=0; i<8; i++) { |
238 | ret = encode(rs, rs->bit_divider-rs->bits[i],rs->bits[i],byte&1); | 239 | ret = encode(rs, rs->bit_divider-rs->bits[i], |
240 | rs->bits[i], byte & 1); | ||
239 | if (ret) { | 241 | if (ret) { |
240 | /* Failed. Restore old state */ | 242 | /* Failed. Restore old state */ |
241 | *rs = rs_copy; | 243 | *rs = rs_copy; |
242 | return ret; | 244 | return ret; |
243 | } | 245 | } |
244 | byte=byte>>1; | 246 | byte >>= 1 ; |
245 | } | 247 | } |
246 | return 0; | 248 | return 0; |
247 | } | 249 | } |
@@ -251,7 +253,8 @@ static int in_byte(struct rubin_state *rs) | |||
251 | int i, result = 0, bit_divider = rs->bit_divider; | 253 | int i, result = 0, bit_divider = rs->bit_divider; |
252 | 254 | ||
253 | for (i = 0; i < 8; i++) | 255 | for (i = 0; i < 8; i++) |
254 | result |= decode(rs, bit_divider - rs->bits[i], rs->bits[i]) << i; | 256 | result |= decode(rs, bit_divider - rs->bits[i], |
257 | rs->bits[i]) << i; | ||
255 | 258 | ||
256 | return result; | 259 | return result; |
257 | } | 260 | } |
@@ -259,7 +262,8 @@ static int in_byte(struct rubin_state *rs) | |||
259 | 262 | ||
260 | 263 | ||
261 | static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in, | 264 | static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in, |
262 | unsigned char *cpage_out, uint32_t *sourcelen, uint32_t *dstlen) | 265 | unsigned char *cpage_out, uint32_t *sourcelen, |
266 | uint32_t *dstlen) | ||
263 | { | 267 | { |
264 | int outpos = 0; | 268 | int outpos = 0; |
265 | int pos=0; | 269 | int pos=0; |
@@ -295,7 +299,8 @@ static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in, | |||
295 | int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out, | 299 | int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out, |
296 | uint32_t *sourcelen, uint32_t *dstlen, void *model) | 300 | uint32_t *sourcelen, uint32_t *dstlen, void *model) |
297 | { | 301 | { |
298 | return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen); | 302 | return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, |
303 | cpage_out, sourcelen, dstlen); | ||
299 | } | 304 | } |
300 | #endif | 305 | #endif |
301 | static int jffs2_dynrubin_compress(unsigned char *data_in, | 306 | static int jffs2_dynrubin_compress(unsigned char *data_in, |
@@ -316,9 +321,8 @@ static int jffs2_dynrubin_compress(unsigned char *data_in, | |||
316 | return -1; | 321 | return -1; |
317 | 322 | ||
318 | memset(histo, 0, 256); | 323 | memset(histo, 0, 256); |
319 | for (i=0; i<mysrclen; i++) { | 324 | for (i=0; i<mysrclen; i++) |
320 | histo[data_in[i]]++; | 325 | histo[data_in[i]]++; |
321 | } | ||
322 | memset(bits, 0, sizeof(int)*8); | 326 | memset(bits, 0, sizeof(int)*8); |
323 | for (i=0; i<256; i++) { | 327 | for (i=0; i<256; i++) { |
324 | if (i&128) | 328 | if (i&128) |
@@ -346,7 +350,8 @@ static int jffs2_dynrubin_compress(unsigned char *data_in, | |||
346 | cpage_out[i] = bits[i]; | 350 | cpage_out[i] = bits[i]; |
347 | } | 351 | } |
348 | 352 | ||
349 | ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen); | 353 | ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, |
354 | &mydstlen); | ||
350 | if (ret) | 355 | if (ret) |
351 | return ret; | 356 | return ret; |
352 | 357 | ||
@@ -363,8 +368,10 @@ static int jffs2_dynrubin_compress(unsigned char *data_in, | |||
363 | return 0; | 368 | return 0; |
364 | } | 369 | } |
365 | 370 | ||
366 | static void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in, | 371 | static void rubin_do_decompress(int bit_divider, int *bits, |
367 | unsigned char *page_out, uint32_t srclen, uint32_t destlen) | 372 | unsigned char *cdata_in, |
373 | unsigned char *page_out, uint32_t srclen, | ||
374 | uint32_t destlen) | ||
368 | { | 375 | { |
369 | int outpos = 0; | 376 | int outpos = 0; |
370 | struct rubin_state rs; | 377 | struct rubin_state rs; |
@@ -372,9 +379,8 @@ static void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata | |||
372 | init_pushpull(&rs.pp, cdata_in, srclen, 0, 0); | 379 | init_pushpull(&rs.pp, cdata_in, srclen, 0, 0); |
373 | init_decode(&rs, bit_divider, bits); | 380 | init_decode(&rs, bit_divider, bits); |
374 | 381 | ||
375 | while (outpos < destlen) { | 382 | while (outpos < destlen) |
376 | page_out[outpos++] = in_byte(&rs); | 383 | page_out[outpos++] = in_byte(&rs); |
377 | } | ||
378 | } | 384 | } |
379 | 385 | ||
380 | 386 | ||
@@ -383,7 +389,8 @@ static int jffs2_rubinmips_decompress(unsigned char *data_in, | |||
383 | uint32_t sourcelen, uint32_t dstlen, | 389 | uint32_t sourcelen, uint32_t dstlen, |
384 | void *model) | 390 | void *model) |
385 | { | 391 | { |
386 | rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen); | 392 | rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, |
393 | cpage_out, sourcelen, dstlen); | ||
387 | return 0; | 394 | return 0; |
388 | } | 395 | } |
389 | 396 | ||
@@ -398,52 +405,53 @@ static int jffs2_dynrubin_decompress(unsigned char *data_in, | |||
398 | for (c=0; c<8; c++) | 405 | for (c=0; c<8; c++) |
399 | bits[c] = data_in[c]; | 406 | bits[c] = data_in[c]; |
400 | 407 | ||
401 | rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen); | 408 | rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, |
409 | dstlen); | ||
402 | return 0; | 410 | return 0; |
403 | } | 411 | } |
404 | 412 | ||
405 | static struct jffs2_compressor jffs2_rubinmips_comp = { | 413 | static struct jffs2_compressor jffs2_rubinmips_comp = { |
406 | .priority = JFFS2_RUBINMIPS_PRIORITY, | 414 | .priority = JFFS2_RUBINMIPS_PRIORITY, |
407 | .name = "rubinmips", | 415 | .name = "rubinmips", |
408 | .compr = JFFS2_COMPR_DYNRUBIN, | 416 | .compr = JFFS2_COMPR_DYNRUBIN, |
409 | .compress = NULL, /*&jffs2_rubinmips_compress,*/ | 417 | .compress = NULL, /*&jffs2_rubinmips_compress,*/ |
410 | .decompress = &jffs2_rubinmips_decompress, | 418 | .decompress = &jffs2_rubinmips_decompress, |
411 | #ifdef JFFS2_RUBINMIPS_DISABLED | 419 | #ifdef JFFS2_RUBINMIPS_DISABLED |
412 | .disabled = 1, | 420 | .disabled = 1, |
413 | #else | 421 | #else |
414 | .disabled = 0, | 422 | .disabled = 0, |
415 | #endif | 423 | #endif |
416 | }; | 424 | }; |
417 | 425 | ||
418 | int jffs2_rubinmips_init(void) | 426 | int jffs2_rubinmips_init(void) |
419 | { | 427 | { |
420 | return jffs2_register_compressor(&jffs2_rubinmips_comp); | 428 | return jffs2_register_compressor(&jffs2_rubinmips_comp); |
421 | } | 429 | } |
422 | 430 | ||
423 | void jffs2_rubinmips_exit(void) | 431 | void jffs2_rubinmips_exit(void) |
424 | { | 432 | { |
425 | jffs2_unregister_compressor(&jffs2_rubinmips_comp); | 433 | jffs2_unregister_compressor(&jffs2_rubinmips_comp); |
426 | } | 434 | } |
427 | 435 | ||
428 | static struct jffs2_compressor jffs2_dynrubin_comp = { | 436 | static struct jffs2_compressor jffs2_dynrubin_comp = { |
429 | .priority = JFFS2_DYNRUBIN_PRIORITY, | 437 | .priority = JFFS2_DYNRUBIN_PRIORITY, |
430 | .name = "dynrubin", | 438 | .name = "dynrubin", |
431 | .compr = JFFS2_COMPR_RUBINMIPS, | 439 | .compr = JFFS2_COMPR_RUBINMIPS, |
432 | .compress = jffs2_dynrubin_compress, | 440 | .compress = jffs2_dynrubin_compress, |
433 | .decompress = &jffs2_dynrubin_decompress, | 441 | .decompress = &jffs2_dynrubin_decompress, |
434 | #ifdef JFFS2_DYNRUBIN_DISABLED | 442 | #ifdef JFFS2_DYNRUBIN_DISABLED |
435 | .disabled = 1, | 443 | .disabled = 1, |
436 | #else | 444 | #else |
437 | .disabled = 0, | 445 | .disabled = 0, |
438 | #endif | 446 | #endif |
439 | }; | 447 | }; |
440 | 448 | ||
441 | int jffs2_dynrubin_init(void) | 449 | int jffs2_dynrubin_init(void) |
442 | { | 450 | { |
443 | return jffs2_register_compressor(&jffs2_dynrubin_comp); | 451 | return jffs2_register_compressor(&jffs2_dynrubin_comp); |
444 | } | 452 | } |
445 | 453 | ||
446 | void jffs2_dynrubin_exit(void) | 454 | void jffs2_dynrubin_exit(void) |
447 | { | 455 | { |
448 | jffs2_unregister_compressor(&jffs2_dynrubin_comp); | 456 | jffs2_unregister_compressor(&jffs2_dynrubin_comp); |
449 | } | 457 | } |