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