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