fs/jffs2/compr_rubin.c

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