fs/jffs2/compr_rubin.c

   1 /*
   2  * JFFS2 -- Journalling Flash File System, Version 2.
   3  *
   4  * Copyright (C) 2001 Red Hat, Inc.
   5  *
   6  * Created by Arjan van de Ven <arjanv@redhat.com>
   7  *
   8  * The original JFFS, from which the design for JFFS2 was derived,
   9  * was designed and implemented by Axis Communications AB.
  10  *
  11  * The contents of this file are subject to the Red Hat eCos Public
  12  * License Version 1.1 (the "Licence"); you may not use this file
  13  * except in compliance with the Licence.  You may obtain a copy of
  14  * the Licence at http://www.redhat.com/
  15  *
  16  * Software distributed under the Licence is distributed on an "AS IS"
  17  * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.
  18  * See the Licence for the specific language governing rights and
  19  * limitations under the Licence.
  20  *
  21  * The Original Code is JFFS2 - Journalling Flash File System, version 2
  22  *
  23  * Alternatively, the contents of this file may be used under the
  24  * terms of the GNU General Public License version 2 (the "GPL"), in
  25  * which case the provisions of the GPL are applicable instead of the
  26  * above.  If you wish to allow the use of your version of this file
  27  * only under the terms of the GPL and not to allow others to use your
  28  * version of this file under the RHEPL, indicate your decision by
  29  * deleting the provisions above and replace them with the notice and
  30  * other provisions required by the GPL.  If you do not delete the
  31  * provisions above, a recipient may use your version of this file
  32  * under either the RHEPL or the GPL.
  33  *
  34  * $Id: compr_rubin.c,v 1.13 2001/09/23 10:06:05 rmk Exp $
  35  *
  36  */
  37
  38
  39 #include <linux/string.h>
  40 #include <linux/types.h>
  41 #include "compr_rubin.h"
  42 #include "histo_mips.h"
  43
  44
  45
  46 void init_rubin(struct rubin_state *rs, int div, int *bits)
  47 {
  48         int c;
  49
  50         rs->q = 0;
  51         rs->p = (long) (2 * UPPER_BIT_RUBIN);
  52         rs->bit_number = (long) 0;
  53         rs->bit_divider = div;
  54         for (c=0; c<8; c++)
  55                 rs->bits[c] = bits[c];
  56 }
  57
  58
  59 int encode(struct rubin_state *rs, long A, long B, int symbol)
  60 {
  61
  62         long i0, i1;
  63         int ret;
  64
  65         while ((rs->q >= UPPER_BIT_RUBIN) || ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
  66                 rs->bit_number++;
  67
  68                 ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
  69                 if (ret)
  70                         return ret;
  71                 rs->q &= LOWER_BITS_RUBIN;
  72                 rs->q <<= 1;
  73                 rs->p <<= 1;
  74         }
  75         i0 = A * rs->p / (A + B);
  76         if (i0 <= 0) {
  77                 i0 = 1;
  78         }
  79         if (i0 >= rs->p) {
  80                 i0 = rs->p - 1;
  81         }
  82         i1 = rs->p - i0;
  83
  84         if (symbol == 0)
  85                 rs->p = i0;
  86         else {
  87                 rs->p = i1;
  88                 rs->q += i0;
  89         }
  90         return 0;
  91 }
  92
  93
  94 void end_rubin(struct rubin_state *rs)
  95 {
  96
  97         int i;
  98
  99         for (i = 0; i < RUBIN_REG_SIZE; i++) {
 100                 pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);
 101                 rs->q &= LOWER_BITS_RUBIN;
 102                 rs->q <<= 1;
 103         }
 104 }
 105
 106
 107 void init_decode(struct rubin_state *rs, int div, int *bits)
 108 {
 109         init_rubin(rs, div, bits);
 110
 111         /* behalve lower */
 112         rs->rec_q = 0;
 113
 114         for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
 115                 ;
 116 }
 117
 118 static void __do_decode(struct rubin_state *rs, unsigned long p, unsigned long q)
 119 {
 120         register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
 121         unsigned long rec_q;
 122         int c, bits = 0;
 123
 124         /*
 125          * First, work out how many bits we need from the input stream.
 126          * Note that we have already done the initial check on this
 127          * loop prior to calling this function.
 128          */
 129         do {
 130                 bits++;
 131                 q &= lower_bits_rubin;
 132                 q <<= 1;
 133                 p <<= 1;
 134         } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
 135
 136         rs->p = p;
 137         rs->q = q;
 138
 139         rs->bit_number += bits;
 140
 141         /*
 142          * Now get the bits.  We really want this to be "get n bits".
 143          */
 144         rec_q = rs->rec_q;
 145         do {
 146                 c = pullbit(&rs->pp);
 147                 rec_q &= lower_bits_rubin;
 148                 rec_q <<= 1;
 149                 rec_q += c;
 150         } while (--bits);
 151         rs->rec_q = rec_q;
 152 }
 153
 154 int decode(struct rubin_state *rs, long A, long B)
 155 {
 156         unsigned long p = rs->p, q = rs->q;
 157         long i0, threshold;
 158         int symbol;
 159
 160         if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN))
 161                 __do_decode(rs, p, q);
 162
 163         i0 = A * rs->p / (A + B);
 164         if (i0 <= 0) {
 165                 i0 = 1;
 166         }
 167         if (i0 >= rs->p) {
 168                 i0 = rs->p - 1;
 169         }
 170
 171         threshold = rs->q + i0;
 172         symbol = rs->rec_q >= threshold;
 173         if (rs->rec_q >= threshold) {
 174                 rs->q += i0;
 175                 i0 = rs->p - i0;
 176         }
 177
 178         rs->p = i0;
 179
 180         return symbol;
 181 }
 182
 183
 184
 185 static int out_byte(struct rubin_state *rs, unsigned char byte)
 186 {
 187         int i, ret;
 188         struct rubin_state rs_copy;
 189         rs_copy = *rs;
 190
 191         for (i=0;i<8;i++) {
 192                 ret = encode(rs, rs->bit_divider-rs->bits[i],rs->bits[i],byte&1);
 193                 if (ret) {
 194                         /* Failed. Restore old state */
 195                         *rs = rs_copy;
 196                         return ret;
 197                 }
 198                 byte=byte>>1;
 199         }
 200         return 0;
 201 }
 202
 203 static int in_byte(struct rubin_state *rs)
 204 {
 205         int i, result = 0, bit_divider = rs->bit_divider;
 206
 207         for (i = 0; i < 8; i++)
 208                 result |= decode(rs, bit_divider - rs->bits[i], rs->bits[i]) << i;
 209
 210         return result;
 211 }
 212
 213
 214
 215 int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
 216                       unsigned char *cpage_out, __u32 *sourcelen, __u32 *dstlen)
 217         {
 218         int outpos = 0;
 219         int pos=0;
 220         struct rubin_state rs;
 221
 222         init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
 223
 224         init_rubin(&rs, bit_divider, bits);
 225
 226         while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
 227                 pos++;
 228
 229         end_rubin(&rs);
 230
 231         if (outpos > pos) {
 232                 /* We failed */
 233                 return -1;
 234         }
 235
 236         /* Tell the caller how much we managed to compress,
 237          * and how much space it took */
 238
 239         outpos = (pushedbits(&rs.pp)+7)/8;
 240
 241         if (outpos >= pos)
 242                 return -1; /* We didn't actually compress */
 243         *sourcelen = pos;
 244         *dstlen = outpos;
 245         return 0;
 246 }
 247 #if 0
 248 /* _compress returns the compressed size, -1 if bigger */
 249 int rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
 250                    __u32 *sourcelen, __u32 *dstlen)
 251 {
 252         return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
 253 }
 254 #endif
 255 int dynrubin_compress(unsigned char *data_in, unsigned char *cpage_out,
 256                    __u32 *sourcelen, __u32 *dstlen)
 257 {
 258         int bits[8];
 259         unsigned char histo[256];
 260         int i;
 261         int ret;
 262         __u32 mysrclen, mydstlen;
 263
 264         mysrclen = *sourcelen;
 265         mydstlen = *dstlen - 8;
 266
 267         if (*dstlen <= 12)
 268                 return -1;
 269
 270         memset(histo, 0, 256);
 271         for (i=0; i<mysrclen; i++) {
 272                 histo[data_in[i]]++;
 273         }
 274         memset(bits, 0, sizeof(int)*8);
 275         for (i=0; i<256; i++) {
 276                 if (i&128)
 277                         bits[7] += histo[i];
 278                 if (i&64)
 279                         bits[6] += histo[i];
 280                 if (i&32)
 281                         bits[5] += histo[i];
 282                 if (i&16)
 283                         bits[4] += histo[i];
 284                 if (i&8)
 285                         bits[3] += histo[i];
 286                 if (i&4)
 287                         bits[2] += histo[i];
 288                 if (i&2)
 289                         bits[1] += histo[i];
 290                 if (i&1)
 291                         bits[0] += histo[i];
 292         }
 293
 294         for (i=0; i<8; i++) {
 295                 bits[i] = (bits[i] * 256) / mysrclen;
 296                 if (!bits[i]) bits[i] = 1;
 297                 if (bits[i] > 255) bits[i] = 255;
 298                 cpage_out[i] = bits[i];
 299         }
 300
 301         ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen);
 302         if (ret)
 303                 return ret;
 304
 305         /* Add back the 8 bytes we took for the probabilities */
 306         mydstlen += 8;
 307
 308         if (mysrclen <= mydstlen) {
 309                 /* We compressed */
 310                 return -1;
 311         }
 312
 313         *sourcelen = mysrclen;
 314         *dstlen = mydstlen;
 315         return 0;
 316 }
 317
 318 void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in,
 319                          unsigned char *page_out, __u32 srclen, __u32 destlen)
 320 {
 321         int outpos = 0;
 322         struct rubin_state rs;
 323
 324         init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
 325         init_decode(&rs, bit_divider, bits);
 326
 327         while (outpos < destlen) {
 328                 page_out[outpos++] = in_byte(&rs);
 329         }
 330 }
 331
 332
 333 void rubinmips_decompress(unsigned char *data_in, unsigned char *cpage_out,
 334                    __u32 sourcelen, __u32 dstlen)
 335 {
 336         rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
 337 }
 338
 339 void dynrubin_decompress(unsigned char *data_in, unsigned char *cpage_out,
 340                    __u32 sourcelen, __u32 dstlen)
 341 {
 342         int bits[8];
 343         int c;
 344
 345         for (c=0; c<8; c++)
 346                 bits[c] = data_in[c];
 347
 348         rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen);
 349 }