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