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 struct rubin_state { 25 unsigned long p; 26 unsigned long q; 27 unsigned long rec_q; 28 long bit_number; 29 struct pushpull pp; 30 int bit_divider; 31 int bits[8]; 32 }; 33 34 #define BIT_DIVIDER_MIPS 1043 35 static int bits_mips[8] = { 277,249,290,267,229,341,212,241}; /* mips32 */ 36 37 #include <linux/errno.h> 38 39 struct pushpull { 40 unsigned char *buf; 41 unsigned int buflen; 42 unsigned int ofs; 43 unsigned int reserve; 44 }; 45 46 47 static inline void init_pushpull(struct pushpull *pp, char *buf, unsigned buflen, unsigned ofs, 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 61 if (bit) { 62 pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs &7))); 63 } 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 static inline int pulledbits(struct pushpull *pp) 88 { 89 return pp->ofs; 90 } 91 92 93 static void init_rubin(struct rubin_state *rs, int div, int *bits) 94 { 95 int c; 96 97 rs->q = 0; 98 rs->p = (long) (2 * UPPER_BIT_RUBIN); 99 rs->bit_number = (long) 0; 100 rs->bit_divider = div; 101 for (c=0; c<8; c++) 102 rs->bits[c] = bits[c]; 103 } 104 105 106 static int encode(struct rubin_state *rs, long A, long B, int symbol) 107 { 108 109 long i0, i1; 110 int ret; 111 112 while ((rs->q >= UPPER_BIT_RUBIN) || ((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; 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, unsigned long q) 166 { 167 register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN; 168 unsigned long rec_q; 169 int c, bits = 0; 170 171 /* 172 * First, work out how many bits we need from the input stream. 173 * Note that we have already done the initial check on this 174 * loop prior to calling this function. 175 */ 176 do { 177 bits++; 178 q &= lower_bits_rubin; 179 q <<= 1; 180 p <<= 1; 181 } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN)); 182 183 rs->p = p; 184 rs->q = q; 185 186 rs->bit_number += bits; 187 188 /* 189 * Now get the bits. We really want this to be "get n bits". 190 */ 191 rec_q = rs->rec_q; 192 do { 193 c = pullbit(&rs->pp); 194 rec_q &= lower_bits_rubin; 195 rec_q <<= 1; 196 rec_q += c; 197 } while (--bits); 198 rs->rec_q = rec_q; 199 } 200 201 static int decode(struct rubin_state *rs, long A, long B) 202 { 203 unsigned long p = rs->p, q = rs->q; 204 long i0, threshold; 205 int symbol; 206 207 if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN)) 208 __do_decode(rs, p, q); 209 210 i0 = A * rs->p / (A + B); 211 if (i0 <= 0) { 212 i0 = 1; 213 } 214 if (i0 >= rs->p) { 215 i0 = rs->p - 1; 216 } 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],rs->bits[i],byte&1); 240 if (ret) { 241 /* Failed. Restore old state */ 242 *rs = rs_copy; 243 return ret; 244 } 245 byte=byte>>1; 246 } 247 return 0; 248 } 249 250 static int in_byte(struct rubin_state *rs) 251 { 252 int i, result = 0, bit_divider = rs->bit_divider; 253 254 for (i = 0; i < 8; i++) 255 result |= decode(rs, bit_divider - rs->bits[i], 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, uint32_t *dstlen) 264 { 265 int outpos = 0; 266 int pos=0; 267 struct rubin_state rs; 268 269 init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32); 270 271 init_rubin(&rs, bit_divider, bits); 272 273 while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos])) 274 pos++; 275 276 end_rubin(&rs); 277 278 if (outpos > pos) { 279 /* We failed */ 280 return -1; 281 } 282 283 /* Tell the caller how much we managed to compress, 284 * and how much space it took */ 285 286 outpos = (pushedbits(&rs.pp)+7)/8; 287 288 if (outpos >= pos) 289 return -1; /* We didn't actually compress */ 290 *sourcelen = pos; 291 *dstlen = outpos; 292 return 0; 293 } 294 #if 0 295 /* _compress returns the compressed size, -1 if bigger */ 296 int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out, 297 uint32_t *sourcelen, uint32_t *dstlen, void *model) 298 { 299 return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen); 300 } 301 #endif 302 static int jffs2_dynrubin_compress(unsigned char *data_in, 303 unsigned char *cpage_out, 304 uint32_t *sourcelen, uint32_t *dstlen, 305 void *model) 306 { 307 int bits[8]; 308 unsigned char histo[256]; 309 int i; 310 int ret; 311 uint32_t mysrclen, mydstlen; 312 313 mysrclen = *sourcelen; 314 mydstlen = *dstlen - 8; 315 316 if (*dstlen <= 12) 317 return -1; 318 319 memset(histo, 0, 256); 320 for (i=0; i<mysrclen; i++) { 321 histo[data_in[i]]++; 322 } 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, &mydstlen); 351 if (ret) 352 return ret; 353 354 /* Add back the 8 bytes we took for the probabilities */ 355 mydstlen += 8; 356 357 if (mysrclen <= mydstlen) { 358 /* We compressed */ 359 return -1; 360 } 361 362 *sourcelen = mysrclen; 363 *dstlen = mydstlen; 364 return 0; 365 } 366 367 static void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in, 368 unsigned char *page_out, uint32_t srclen, uint32_t destlen) 369 { 370 int outpos = 0; 371 struct rubin_state rs; 372 373 init_pushpull(&rs.pp, cdata_in, srclen, 0, 0); 374 init_decode(&rs, bit_divider, bits); 375 376 while (outpos < destlen) { 377 page_out[outpos++] = in_byte(&rs); 378 } 379 } 380 381 382 static int jffs2_rubinmips_decompress(unsigned char *data_in, 383 unsigned char *cpage_out, 384 uint32_t sourcelen, uint32_t dstlen, 385 void *model) 386 { 387 rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen); 388 return 0; 389 } 390 391 static int jffs2_dynrubin_decompress(unsigned char *data_in, 392 unsigned char *cpage_out, 393 uint32_t sourcelen, uint32_t dstlen, 394 void *model) 395 { 396 int bits[8]; 397 int c; 398 399 for (c=0; c<8; c++) 400 bits[c] = data_in[c]; 401 402 rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen); 403 return 0; 404 } 405 406 static struct jffs2_compressor jffs2_rubinmips_comp = { 407 .priority = JFFS2_RUBINMIPS_PRIORITY, 408 .name = "rubinmips", 409 .compr = JFFS2_COMPR_DYNRUBIN, 410 .compress = NULL, /*&jffs2_rubinmips_compress,*/ 411 .decompress = &jffs2_rubinmips_decompress, 412 #ifdef JFFS2_RUBINMIPS_DISABLED 413 .disabled = 1, 414 #else 415 .disabled = 0, 416 #endif 417 }; 418 419 int jffs2_rubinmips_init(void) 420 { 421 return jffs2_register_compressor(&jffs2_rubinmips_comp); 422 } 423 424 void jffs2_rubinmips_exit(void) 425 { 426 jffs2_unregister_compressor(&jffs2_rubinmips_comp); 427 } 428 429 static struct jffs2_compressor jffs2_dynrubin_comp = { 430 .priority = JFFS2_DYNRUBIN_PRIORITY, 431 .name = "dynrubin", 432 .compr = JFFS2_COMPR_RUBINMIPS, 433 .compress = jffs2_dynrubin_compress, 434 .decompress = &jffs2_dynrubin_decompress, 435 #ifdef JFFS2_DYNRUBIN_DISABLED 436 .disabled = 1, 437 #else 438 .disabled = 0, 439 #endif 440 }; 441 442 int jffs2_dynrubin_init(void) 443 { 444 return jffs2_register_compressor(&jffs2_dynrubin_comp); 445 } 446 447 void jffs2_dynrubin_exit(void) 448 { 449 jffs2_unregister_compressor(&jffs2_dynrubin_comp); 450 } 451