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}; /* mips32 */ 26 27 #include <linux/errno.h> 28 29 struct pushpull { 30 unsigned char *buf; 31 unsigned int buflen; 32 unsigned int ofs; 33 unsigned int reserve; 34 }; 35 36 struct rubin_state { 37 unsigned long p; 38 unsigned long q; 39 unsigned long rec_q; 40 long bit_number; 41 struct pushpull pp; 42 int bit_divider; 43 int bits[8]; 44 }; 45 46 static inline void init_pushpull(struct pushpull *pp, char *buf, unsigned buflen, unsigned ofs, 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 60 if (bit) { 61 pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs &7))); 62 } 63 else { 64 pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs &7))); 65 } 66 pp->ofs++; 67 68 return 0; 69 } 70 71 static inline int pushedbits(struct pushpull *pp) 72 { 73 return pp->ofs; 74 } 75 76 static inline int pullbit(struct pushpull *pp) 77 { 78 int bit; 79 80 bit = (pp->buf[pp->ofs >> 3] >> (7-(pp->ofs & 7))) & 1; 81 82 pp->ofs++; 83 return bit; 84 } 85 86 static inline int pulledbits(struct pushpull *pp) 87 { 88 return pp->ofs; 89 } 90 91 92 static void init_rubin(struct rubin_state *rs, int div, int *bits) 93 { 94 int c; 95 96 rs->q = 0; 97 rs->p = (long) (2 * UPPER_BIT_RUBIN); 98 rs->bit_number = (long) 0; 99 rs->bit_divider = div; 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) || ((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; rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp))) 161 ; 162 } 163 164 static void __do_decode(struct rubin_state *rs, unsigned long p, 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 217 threshold = rs->q + i0; 218 symbol = rs->rec_q >= threshold; 219 if (rs->rec_q >= threshold) { 220 rs->q += i0; 221 i0 = rs->p - i0; 222 } 223 224 rs->p = i0; 225 226 return symbol; 227 } 228 229 230 231 static int out_byte(struct rubin_state *rs, unsigned char byte) 232 { 233 int i, ret; 234 struct rubin_state rs_copy; 235 rs_copy = *rs; 236 237 for (i=0;i<8;i++) { 238 ret = encode(rs, rs->bit_divider-rs->bits[i],rs->bits[i],byte&1); 239 if (ret) { 240 /* Failed. Restore old state */ 241 *rs = rs_copy; 242 return ret; 243 } 244 byte=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], rs->bits[i]) << i; 255 256 return result; 257 } 258 259 260 261 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) 263 { 264 int outpos = 0; 265 int pos=0; 266 struct rubin_state rs; 267 268 init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32); 269 270 init_rubin(&rs, bit_divider, bits); 271 272 while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos])) 273 pos++; 274 275 end_rubin(&rs); 276 277 if (outpos > pos) { 278 /* We failed */ 279 return -1; 280 } 281 282 /* Tell the caller how much we managed to compress, 283 * and how much space it took */ 284 285 outpos = (pushedbits(&rs.pp)+7)/8; 286 287 if (outpos >= pos) 288 return -1; /* We didn't actually compress */ 289 *sourcelen = pos; 290 *dstlen = outpos; 291 return 0; 292 } 293 #if 0 294 /* _compress returns the compressed size, -1 if bigger */ 295 int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out, 296 uint32_t *sourcelen, uint32_t *dstlen, void *model) 297 { 298 return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen); 299 } 300 #endif 301 static int jffs2_dynrubin_compress(unsigned char *data_in, 302 unsigned char *cpage_out, 303 uint32_t *sourcelen, uint32_t *dstlen, 304 void *model) 305 { 306 int bits[8]; 307 unsigned char histo[256]; 308 int i; 309 int ret; 310 uint32_t mysrclen, mydstlen; 311 312 mysrclen = *sourcelen; 313 mydstlen = *dstlen - 8; 314 315 if (*dstlen <= 12) 316 return -1; 317 318 memset(histo, 0, 256); 319 for (i=0; i<mysrclen; i++) { 320 histo[data_in[i]]++; 321 } 322 memset(bits, 0, sizeof(int)*8); 323 for (i=0; i<256; i++) { 324 if (i&128) 325 bits[7] += histo[i]; 326 if (i&64) 327 bits[6] += histo[i]; 328 if (i&32) 329 bits[5] += histo[i]; 330 if (i&16) 331 bits[4] += histo[i]; 332 if (i&8) 333 bits[3] += histo[i]; 334 if (i&4) 335 bits[2] += histo[i]; 336 if (i&2) 337 bits[1] += histo[i]; 338 if (i&1) 339 bits[0] += histo[i]; 340 } 341 342 for (i=0; i<8; i++) { 343 bits[i] = (bits[i] * 256) / mysrclen; 344 if (!bits[i]) bits[i] = 1; 345 if (bits[i] > 255) bits[i] = 255; 346 cpage_out[i] = bits[i]; 347 } 348 349 ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen); 350 if (ret) 351 return ret; 352 353 /* Add back the 8 bytes we took for the probabilities */ 354 mydstlen += 8; 355 356 if (mysrclen <= mydstlen) { 357 /* We compressed */ 358 return -1; 359 } 360 361 *sourcelen = mysrclen; 362 *dstlen = mydstlen; 363 return 0; 364 } 365 366 static void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in, 367 unsigned char *page_out, uint32_t srclen, uint32_t destlen) 368 { 369 int outpos = 0; 370 struct rubin_state rs; 371 372 init_pushpull(&rs.pp, cdata_in, srclen, 0, 0); 373 init_decode(&rs, bit_divider, bits); 374 375 while (outpos < destlen) { 376 page_out[outpos++] = in_byte(&rs); 377 } 378 } 379 380 381 static int jffs2_rubinmips_decompress(unsigned char *data_in, 382 unsigned char *cpage_out, 383 uint32_t sourcelen, uint32_t dstlen, 384 void *model) 385 { 386 rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen); 387 return 0; 388 } 389 390 static int jffs2_dynrubin_decompress(unsigned char *data_in, 391 unsigned char *cpage_out, 392 uint32_t sourcelen, uint32_t dstlen, 393 void *model) 394 { 395 int bits[8]; 396 int c; 397 398 for (c=0; c<8; c++) 399 bits[c] = data_in[c]; 400 401 rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen); 402 return 0; 403 } 404 405 static struct jffs2_compressor jffs2_rubinmips_comp = { 406 .priority = JFFS2_RUBINMIPS_PRIORITY, 407 .name = "rubinmips", 408 .compr = JFFS2_COMPR_DYNRUBIN, 409 .compress = NULL, /*&jffs2_rubinmips_compress,*/ 410 .decompress = &jffs2_rubinmips_decompress, 411 #ifdef JFFS2_RUBINMIPS_DISABLED 412 .disabled = 1, 413 #else 414 .disabled = 0, 415 #endif 416 }; 417 418 int jffs2_rubinmips_init(void) 419 { 420 return jffs2_register_compressor(&jffs2_rubinmips_comp); 421 } 422 423 void jffs2_rubinmips_exit(void) 424 { 425 jffs2_unregister_compressor(&jffs2_rubinmips_comp); 426 } 427 428 static struct jffs2_compressor jffs2_dynrubin_comp = { 429 .priority = JFFS2_DYNRUBIN_PRIORITY, 430 .name = "dynrubin", 431 .compr = JFFS2_COMPR_RUBINMIPS, 432 .compress = jffs2_dynrubin_compress, 433 .decompress = &jffs2_dynrubin_decompress, 434 #ifdef JFFS2_DYNRUBIN_DISABLED 435 .disabled = 1, 436 #else 437 .disabled = 0, 438 #endif 439 }; 440 441 int jffs2_dynrubin_init(void) 442 { 443 return jffs2_register_compressor(&jffs2_dynrubin_comp); 444 } 445 446 void jffs2_dynrubin_exit(void) 447 { 448 jffs2_unregister_compressor(&jffs2_dynrubin_comp); 449 } 450