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 int jffs2_dynrubin_compress(unsigned char *data_in, unsigned char *cpage_out, 232 uint32_t *sourcelen, uint32_t *dstlen, void *model) 233 { 234 int bits[8]; 235 unsigned char histo[256]; 236 int i; 237 int ret; 238 uint32_t mysrclen, mydstlen; 239 240 mysrclen = *sourcelen; 241 mydstlen = *dstlen - 8; 242 243 if (*dstlen <= 12) 244 return -1; 245 246 memset(histo, 0, 256); 247 for (i=0; i<mysrclen; i++) { 248 histo[data_in[i]]++; 249 } 250 memset(bits, 0, sizeof(int)*8); 251 for (i=0; i<256; i++) { 252 if (i&128) 253 bits[7] += histo[i]; 254 if (i&64) 255 bits[6] += histo[i]; 256 if (i&32) 257 bits[5] += histo[i]; 258 if (i&16) 259 bits[4] += histo[i]; 260 if (i&8) 261 bits[3] += histo[i]; 262 if (i&4) 263 bits[2] += histo[i]; 264 if (i&2) 265 bits[1] += histo[i]; 266 if (i&1) 267 bits[0] += histo[i]; 268 } 269 270 for (i=0; i<8; i++) { 271 bits[i] = (bits[i] * 256) / mysrclen; 272 if (!bits[i]) bits[i] = 1; 273 if (bits[i] > 255) bits[i] = 255; 274 cpage_out[i] = bits[i]; 275 } 276 277 ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen); 278 if (ret) 279 return ret; 280 281 /* Add back the 8 bytes we took for the probabilities */ 282 mydstlen += 8; 283 284 if (mysrclen <= mydstlen) { 285 /* We compressed */ 286 return -1; 287 } 288 289 *sourcelen = mysrclen; 290 *dstlen = mydstlen; 291 return 0; 292 } 293 294 static void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in, 295 unsigned char *page_out, uint32_t srclen, uint32_t destlen) 296 { 297 int outpos = 0; 298 struct rubin_state rs; 299 300 init_pushpull(&rs.pp, cdata_in, srclen, 0, 0); 301 init_decode(&rs, bit_divider, bits); 302 303 while (outpos < destlen) { 304 page_out[outpos++] = in_byte(&rs); 305 } 306 } 307 308 309 int jffs2_rubinmips_decompress(unsigned char *data_in, unsigned char *cpage_out, 310 uint32_t sourcelen, uint32_t dstlen, void *model) 311 { 312 rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen); 313 return 0; 314 } 315 316 int jffs2_dynrubin_decompress(unsigned char *data_in, unsigned char *cpage_out, 317 uint32_t sourcelen, uint32_t dstlen, void *model) 318 { 319 int bits[8]; 320 int c; 321 322 for (c=0; c<8; c++) 323 bits[c] = data_in[c]; 324 325 rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen); 326 return 0; 327 } 328 329 static struct jffs2_compressor jffs2_rubinmips_comp = { 330 .priority = JFFS2_RUBINMIPS_PRIORITY, 331 .name = "rubinmips", 332 .compr = JFFS2_COMPR_DYNRUBIN, 333 .compress = NULL, /*&jffs2_rubinmips_compress,*/ 334 .decompress = &jffs2_rubinmips_decompress, 335 #ifdef JFFS2_RUBINMIPS_DISABLED 336 .disabled = 1, 337 #else 338 .disabled = 0, 339 #endif 340 }; 341 342 int jffs2_rubinmips_init(void) 343 { 344 return jffs2_register_compressor(&jffs2_rubinmips_comp); 345 } 346 347 void jffs2_rubinmips_exit(void) 348 { 349 jffs2_unregister_compressor(&jffs2_rubinmips_comp); 350 } 351 352 static struct jffs2_compressor jffs2_dynrubin_comp = { 353 .priority = JFFS2_DYNRUBIN_PRIORITY, 354 .name = "dynrubin", 355 .compr = JFFS2_COMPR_RUBINMIPS, 356 .compress = jffs2_dynrubin_compress, 357 .decompress = &jffs2_dynrubin_decompress, 358 #ifdef JFFS2_DYNRUBIN_DISABLED 359 .disabled = 1, 360 #else 361 .disabled = 0, 362 #endif 363 }; 364 365 int jffs2_dynrubin_init(void) 366 { 367 return jffs2_register_compressor(&jffs2_dynrubin_comp); 368 } 369 370 void jffs2_dynrubin_exit(void) 371 { 372 jffs2_unregister_compressor(&jffs2_dynrubin_comp); 373 } 374