fs/jffs2/compr_rubin.c

0001 /*
0002  * JFFS2 -- Journalling Flash File System, Version 2.
0003  *
0004  * Copyright © 2001-2007 Red Hat, Inc.
0005  * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
0006  *
0007  * Created by Arjan van de Ven <arjanv@redhat.com>
0008  *
0009  * For licensing information, see the file 'LICENCE' in this directory.
0010  *
0011  */
0012
0013 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
0014
0015 #include <linux/string.h>
0016 #include <linux/types.h>
0017 #include <linux/jffs2.h>
0018 #include <linux/errno.h>
0019 #include "compr.h"
0020
0021
0022 #define RUBIN_REG_SIZE   16
0023 #define UPPER_BIT_RUBIN    (((long) 1)<<(RUBIN_REG_SIZE-1))
0024 #define LOWER_BITS_RUBIN   ((((long) 1)<<(RUBIN_REG_SIZE-1))-1)
0025
0026
0027 #define BIT_DIVIDER_MIPS 1043
0028 static int bits_mips[8] = { 277, 249, 290, 267, 229, 341, 212, 241};
0029
0030 struct pushpull {
0031     unsigned char *buf;
0032     unsigned int buflen;
0033     unsigned int ofs;
0034     unsigned int reserve;
0035 };
0036
0037 struct rubin_state {
0038     unsigned long p;
0039     unsigned long q;
0040     unsigned long rec_q;
0041     long bit_number;
0042     struct pushpull pp;
0043     int bit_divider;
0044     int bits[8];
0045 };
0046
0047 static inline void init_pushpull(struct pushpull *pp, char *buf,
0048                  unsigned buflen, unsigned ofs,
0049                  unsigned reserve)
0050 {
0051     pp->buf = buf;
0052     pp->buflen = buflen;
0053     pp->ofs = ofs;
0054     pp->reserve = reserve;
0055 }
0056
0057 static inline int pushbit(struct pushpull *pp, int bit, int use_reserved)
0058 {
0059     if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve))
0060         return -ENOSPC;
0061
0062     if (bit)
0063         pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs & 7)));
0064     else
0065         pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs & 7)));
0066
0067     pp->ofs++;
0068
0069     return 0;
0070 }
0071
0072 static inline int pushedbits(struct pushpull *pp)
0073 {
0074     return pp->ofs;
0075 }
0076
0077 static inline int pullbit(struct pushpull *pp)
0078 {
0079     int bit;
0080
0081     bit = (pp->buf[pp->ofs >> 3] >> (7-(pp->ofs & 7))) & 1;
0082
0083     pp->ofs++;
0084     return bit;
0085 }
0086
0087
0088 static void init_rubin(struct rubin_state *rs, int div, int *bits)
0089 {
0090     int c;
0091
0092     rs->q = 0;
0093     rs->p = (long) (2 * UPPER_BIT_RUBIN);
0094     rs->bit_number = (long) 0;
0095     rs->bit_divider = div;
0096
0097     for (c=0; c<8; c++)
0098         rs->bits[c] = bits[c];
0099 }
0100
0101
0102 static int encode(struct rubin_state *rs, long A, long B, int symbol)
0103 {
0104
0105     long i0, i1;
0106     int ret;
0107
0108     while ((rs->q >= UPPER_BIT_RUBIN) ||
0109            ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
0110         rs->bit_number++;
0111
0112         ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
0113         if (ret)
0114             return ret;
0115         rs->q &= LOWER_BITS_RUBIN;
0116         rs->q <<= 1;
0117         rs->p <<= 1;
0118     }
0119     i0 = A * rs->p / (A + B);
0120     if (i0 <= 0)
0121         i0 = 1;
0122
0123     if (i0 >= rs->p)
0124         i0 = rs->p - 1;
0125
0126     i1 = rs->p - i0;
0127
0128     if (symbol == 0)
0129         rs->p = i0;
0130     else {
0131         rs->p = i1;
0132         rs->q += i0;
0133     }
0134     return 0;
0135 }
0136
0137
0138 static void end_rubin(struct rubin_state *rs)
0139 {
0140
0141     int i;
0142
0143     for (i = 0; i < RUBIN_REG_SIZE; i++) {
0144         pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);
0145         rs->q &= LOWER_BITS_RUBIN;
0146         rs->q <<= 1;
0147     }
0148 }
0149
0150
0151 static void init_decode(struct rubin_state *rs, int div, int *bits)
0152 {
0153     init_rubin(rs, div, bits);
0154
0155     /* behalve lower */
0156     rs->rec_q = 0;
0157
0158     for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE;
0159          rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
0160         ;
0161 }
0162
0163 static void __do_decode(struct rubin_state *rs, unsigned long p,
0164             unsigned long q)
0165 {
0166     register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
0167     unsigned long rec_q;
0168     int c, bits = 0;
0169
0170     /*
0171      * First, work out how many bits we need from the input stream.
0172      * Note that we have already done the initial check on this
0173      * loop prior to calling this function.
0174      */
0175     do {
0176         bits++;
0177         q &= lower_bits_rubin;
0178         q <<= 1;
0179         p <<= 1;
0180     } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
0181
0182     rs->p = p;
0183     rs->q = q;
0184
0185     rs->bit_number += bits;
0186
0187     /*
0188      * Now get the bits.  We really want this to be "get n bits".
0189      */
0190     rec_q = rs->rec_q;
0191     do {
0192         c = pullbit(&rs->pp);
0193         rec_q &= lower_bits_rubin;
0194         rec_q <<= 1;
0195         rec_q += c;
0196     } while (--bits);
0197     rs->rec_q = rec_q;
0198 }
0199
0200 static int decode(struct rubin_state *rs, long A, long B)
0201 {
0202     unsigned long p = rs->p, q = rs->q;
0203     long i0, threshold;
0204     int symbol;
0205
0206     if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN))
0207         __do_decode(rs, p, q);
0208
0209     i0 = A * rs->p / (A + B);
0210     if (i0 <= 0)
0211         i0 = 1;
0212
0213     if (i0 >= rs->p)
0214         i0 = rs->p - 1;
0215
0216     threshold = rs->q + i0;
0217     symbol = rs->rec_q >= threshold;
0218     if (rs->rec_q >= threshold) {
0219         rs->q += i0;
0220         i0 = rs->p - i0;
0221     }
0222
0223     rs->p = i0;
0224
0225     return symbol;
0226 }
0227
0228
0229
0230 static int out_byte(struct rubin_state *rs, unsigned char byte)
0231 {
0232     int i, ret;
0233     struct rubin_state rs_copy;
0234     rs_copy = *rs;
0235
0236     for (i=0; i<8; i++) {
0237         ret = encode(rs, rs->bit_divider-rs->bits[i],
0238                  rs->bits[i], byte & 1);
0239         if (ret) {
0240             /* Failed. Restore old state */
0241             *rs = rs_copy;
0242             return ret;
0243         }
0244         byte >>= 1 ;
0245     }
0246     return 0;
0247 }
0248
0249 static int in_byte(struct rubin_state *rs)
0250 {
0251     int i, result = 0, bit_divider = rs->bit_divider;
0252
0253     for (i = 0; i < 8; i++)
0254         result |= decode(rs, bit_divider - rs->bits[i],
0255                  rs->bits[i]) << i;
0256
0257     return result;
0258 }
0259
0260
0261
0262 static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
0263                  unsigned char *cpage_out, uint32_t *sourcelen,
0264                  uint32_t *dstlen)
0265     {
0266     int outpos = 0;
0267     int pos=0;
0268     struct rubin_state rs;
0269
0270     init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
0271
0272     init_rubin(&rs, bit_divider, bits);
0273
0274     while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
0275         pos++;
0276
0277     end_rubin(&rs);
0278
0279     if (outpos > pos) {
0280         /* We failed */
0281         return -1;
0282     }
0283
0284     /* Tell the caller how much we managed to compress,
0285      * and how much space it took */
0286
0287     outpos = (pushedbits(&rs.pp)+7)/8;
0288
0289     if (outpos >= pos)
0290         return -1; /* We didn't actually compress */
0291     *sourcelen = pos;
0292     *dstlen = outpos;
0293     return 0;
0294 }
0295 #if 0
0296 /* _compress returns the compressed size, -1 if bigger */
0297 int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
0298            uint32_t *sourcelen, uint32_t *dstlen)
0299 {
0300     return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in,
0301                  cpage_out, sourcelen, dstlen);
0302 }
0303 #endif
0304 static int jffs2_dynrubin_compress(unsigned char *data_in,
0305                    unsigned char *cpage_out,
0306                    uint32_t *sourcelen, uint32_t *dstlen)
0307 {
0308     int bits[8];
0309     unsigned char histo[256];
0310     int i;
0311     int ret;
0312     uint32_t mysrclen, mydstlen;
0313
0314     mysrclen = *sourcelen;
0315     mydstlen = *dstlen - 8;
0316
0317     if (*dstlen <= 12)
0318         return -1;
0319
0320     memset(histo, 0, 256);
0321     for (i=0; i<mysrclen; i++)
0322         histo[data_in[i]]++;
0323     memset(bits, 0, sizeof(int)*8);
0324     for (i=0; i<256; i++) {
0325         if (i&128)
0326             bits[7] += histo[i];
0327         if (i&64)
0328             bits[6] += histo[i];
0329         if (i&32)
0330             bits[5] += histo[i];
0331         if (i&16)
0332             bits[4] += histo[i];
0333         if (i&8)
0334             bits[3] += histo[i];
0335         if (i&4)
0336             bits[2] += histo[i];
0337         if (i&2)
0338             bits[1] += histo[i];
0339         if (i&1)
0340             bits[0] += histo[i];
0341     }
0342
0343     for (i=0; i<8; i++) {
0344         bits[i] = (bits[i] * 256) / mysrclen;
0345         if (!bits[i]) bits[i] = 1;
0346         if (bits[i] > 255) bits[i] = 255;
0347         cpage_out[i] = bits[i];
0348     }
0349
0350     ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen,
0351                 &mydstlen);
0352     if (ret)
0353         return ret;
0354
0355     /* Add back the 8 bytes we took for the probabilities */
0356     mydstlen += 8;
0357
0358     if (mysrclen <= mydstlen) {
0359         /* We compressed */
0360         return -1;
0361     }
0362
0363     *sourcelen = mysrclen;
0364     *dstlen = mydstlen;
0365     return 0;
0366 }
0367
0368 static void rubin_do_decompress(int bit_divider, int *bits,
0369                 unsigned char *cdata_in,
0370                 unsigned char *page_out, uint32_t srclen,
0371                 uint32_t destlen)
0372 {
0373     int outpos = 0;
0374     struct rubin_state rs;
0375
0376     init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
0377     init_decode(&rs, bit_divider, bits);
0378
0379     while (outpos < destlen)
0380         page_out[outpos++] = in_byte(&rs);
0381 }
0382
0383
0384 static int jffs2_rubinmips_decompress(unsigned char *data_in,
0385                       unsigned char *cpage_out,
0386                       uint32_t sourcelen, uint32_t dstlen)
0387 {
0388     rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in,
0389                 cpage_out, sourcelen, dstlen);
0390     return 0;
0391 }
0392
0393 static int jffs2_dynrubin_decompress(unsigned char *data_in,
0394                      unsigned char *cpage_out,
0395                      uint32_t sourcelen, uint32_t dstlen)
0396 {
0397     int bits[8];
0398     int c;
0399
0400     for (c=0; c<8; c++)
0401         bits[c] = data_in[c];
0402
0403     rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8,
0404                 dstlen);
0405     return 0;
0406 }
0407
0408 static struct jffs2_compressor jffs2_rubinmips_comp = {
0409     .priority = JFFS2_RUBINMIPS_PRIORITY,
0410     .name = "rubinmips",
0411     .compr = JFFS2_COMPR_DYNRUBIN,
0412     .compress = NULL, /*&jffs2_rubinmips_compress,*/
0413     .decompress = &jffs2_rubinmips_decompress,
0414 #ifdef JFFS2_RUBINMIPS_DISABLED
0415     .disabled = 1,
0416 #else
0417     .disabled = 0,
0418 #endif
0419 };
0420
0421 int jffs2_rubinmips_init(void)
0422 {
0423     return jffs2_register_compressor(&jffs2_rubinmips_comp);
0424 }
0425
0426 void jffs2_rubinmips_exit(void)
0427 {
0428     jffs2_unregister_compressor(&jffs2_rubinmips_comp);
0429 }
0430
0431 static struct jffs2_compressor jffs2_dynrubin_comp = {
0432     .priority = JFFS2_DYNRUBIN_PRIORITY,
0433     .name = "dynrubin",
0434     .compr = JFFS2_COMPR_RUBINMIPS,
0435     .compress = jffs2_dynrubin_compress,
0436     .decompress = &jffs2_dynrubin_decompress,
0437 #ifdef JFFS2_DYNRUBIN_DISABLED
0438     .disabled = 1,
0439 #else
0440     .disabled = 0,
0441 #endif
0442 };
0443
0444 int jffs2_dynrubin_init(void)
0445 {
0446     return jffs2_register_compressor(&jffs2_dynrubin_comp);
0447 }
0448
0449 void jffs2_dynrubin_exit(void)
0450 {
0451     jffs2_unregister_compressor(&jffs2_dynrubin_comp);
0452 }