fs/jffs2/compr_rubin.c

   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 }