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