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(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 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(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 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(&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(&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, rs->bit_divider-rs->bits[i], 238 rs->bits[i], 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, bit_divider - rs->bits[i], 255 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(&rs.pp, cpage_out, *dstlen * 8, 0, 32); 271 272 init_rubin(&rs, bit_divider, bits); 273 274 while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos])) 275 pos++; 276 277 end_rubin(&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(&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(256, bits, data_in, cpage_out+8, &mysrclen, 351 &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(&rs.pp, cdata_in, srclen, 0, 0); 377 init_decode(&rs, bit_divider, bits); 378 379 while (outpos < destlen) 380 page_out[outpos++] = in_byte(&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_mips, data_in, 389 cpage_out, sourcelen, 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(256, bits, data_in+8, cpage_out, sourcelen-8, 404 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(&jffs2_rubinmips_comp); 424 } 425 426 void jffs2_rubinmips_exit(void) 427 { 428 jffs2_unregister_compressor(&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(&jffs2_dynrubin_comp); 447 } 448 449 void jffs2_dynrubin_exit(void) 450 { 451 jffs2_unregister_compressor(&jffs2_dynrubin_comp); 452 } 453