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