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