fs/jffs2/mini_inflate.c

   1 /*-------------------------------------------------------------------------
   2  * Filename:      mini_inflate.c
   3  * Version:       $Id: mini_inflate.c,v 1.3 2002/01/24 22:58:42 rfeany Exp $
   4  * Copyright:     Copyright (C) 2001, Russ Dill
   5  * Author:        Russ Dill <Russ.Dill@asu.edu>
   6  * Description:   Mini inflate implementation (RFC 1951)
   7  *-----------------------------------------------------------------------*/
   8 /*
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 of the License, or
  13  * (at your option) any later version.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software
  22  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23  *
  24  */
  25
  26 #include <config.h>
  27
  28 #if (CONFIG_COMMANDS & CFG_CMD_JFFS2)
  29
  30 #include <jffs2/mini_inflate.h>
  31
  32 /* The order that the code lengths in section 3.2.7 are in */
  33 static unsigned char huffman_order[] = {16, 17, 18,  0,  8,  7,  9,  6, 10,  5,
  34                                         11,  4, 12,  3, 13,  2, 14,  1, 15};
  35
  36 inline void cramfs_memset(int *s, const int c, size n)
  37 {
  38         n--;
  39         for (;n > 0; n--) s[n] = c;
  40         s[0] = c;
  41 }
  42
  43 /* associate a stream with a block of data and reset the stream */
  44 static void init_stream(struct bitstream *stream, unsigned char *data,
  45                         void *(*inflate_memcpy)(void *, const void *, size))
  46 {
  47         stream->error = NO_ERROR;
  48         stream->memcpy = inflate_memcpy;
  49         stream->decoded = 0;
  50         stream->data = data;
  51         stream->bit = 0;        /* The first bit of the stream is the lsb of the
  52                                  * first byte */
  53
  54         /* really sorry about all this initialization, think of a better way,
  55          * let me know and it will get cleaned up */
  56         stream->codes.bits = 8;
  57         stream->codes.num_symbols = 19;
  58         stream->codes.lengths = stream->code_lengths;
  59         stream->codes.symbols = stream->code_symbols;
  60         stream->codes.count = stream->code_count;
  61         stream->codes.first = stream->code_first;
  62         stream->codes.pos = stream->code_pos;
  63
  64         stream->lengths.bits = 16;
  65         stream->lengths.num_symbols = 288;
  66         stream->lengths.lengths = stream->length_lengths;
  67         stream->lengths.symbols = stream->length_symbols;
  68         stream->lengths.count = stream->length_count;
  69         stream->lengths.first = stream->length_first;
  70         stream->lengths.pos = stream->length_pos;
  71
  72         stream->distance.bits = 16;
  73         stream->distance.num_symbols = 32;
  74         stream->distance.lengths = stream->distance_lengths;
  75         stream->distance.symbols = stream->distance_symbols;
  76         stream->distance.count = stream->distance_count;
  77         stream->distance.first = stream->distance_first;
  78         stream->distance.pos = stream->distance_pos;
  79
  80 }
  81
  82 /* pull 'bits' bits out of the stream. The last bit pulled it returned as the
  83  * msb. (section 3.1.1)
  84  */
  85 inline unsigned long pull_bits(struct bitstream *stream,
  86                                const unsigned int bits)
  87 {
  88         unsigned long ret;
  89         int i;
  90
  91         ret = 0;
  92         for (i = 0; i < bits; i++) {
  93                 ret += ((*(stream->data) >> stream->bit) & 1) << i;
  94
  95                 /* if, before incrementing, we are on bit 7,
  96                  * go to the lsb of the next byte */
  97                 if (stream->bit++ == 7) {
  98                         stream->bit = 0;
  99                         stream->data++;
 100                 }
 101         }
 102         return ret;
 103 }
 104
 105 inline int pull_bit(struct bitstream *stream)
 106 {
 107         int ret = ((*(stream->data) >> stream->bit) & 1);
 108         if (stream->bit++ == 7) {
 109                 stream->bit = 0;
 110                 stream->data++;
 111         }
 112         return ret;
 113 }
 114
 115 /* discard bits up to the next whole byte */
 116 static void discard_bits(struct bitstream *stream)
 117 {
 118         if (stream->bit != 0) {
 119                 stream->bit = 0;
 120                 stream->data++;
 121         }
 122 }
 123
 124 /* No decompression, the data is all literals (section 3.2.4) */
 125 static void decompress_none(struct bitstream *stream, unsigned char *dest)
 126 {
 127         unsigned int length;
 128
 129         discard_bits(stream);
 130         length = *(stream->data++);
 131         length += *(stream->data++) << 8;
 132         pull_bits(stream, 16);  /* throw away the inverse of the size */
 133
 134         stream->decoded += length;
 135         stream->memcpy(dest, stream->data, length);
 136         stream->data += length;
 137 }
 138
 139 /* Read in a symbol from the stream (section 3.2.2) */
 140 static int read_symbol(struct bitstream *stream, struct huffman_set *set)
 141 {
 142         int bits = 0;
 143         int code = 0;
 144         while (!(set->count[bits] && code < set->first[bits] +
 145                                              set->count[bits])) {
 146                 code = (code << 1) + pull_bit(stream);
 147                 if (++bits > set->bits) {
 148                         /* error decoding (corrupted data?) */
 149                         stream->error = CODE_NOT_FOUND;
 150                         return -1;
 151                 }
 152         }
 153         return set->symbols[set->pos[bits] + code - set->first[bits]];
 154 }
 155
 156 /* decompress a stream of data encoded with the passed length and distance
 157  * huffman codes */
 158 static void decompress_huffman(struct bitstream *stream, unsigned char *dest)
 159 {
 160         struct huffman_set *lengths = &(stream->lengths);
 161         struct huffman_set *distance = &(stream->distance);
 162
 163         int symbol, length, dist, i;
 164
 165         do {
 166                 if ((symbol = read_symbol(stream, lengths)) < 0) return;
 167                 if (symbol < 256) {
 168                         *(dest++) = symbol; /* symbol is a literal */
 169                         stream->decoded++;
 170                 } else if (symbol > 256) {
 171                         /* Determine the length of the repitition
 172                          * (section 3.2.5) */
 173                         if (symbol < 265) length = symbol - 254;
 174                         else if (symbol == 285) length = 258;
 175                         else {
 176                                 length = pull_bits(stream, (symbol - 261) >> 2);
 177                                 length += (4 << ((symbol - 261) >> 2)) + 3;
 178                                 length += ((symbol - 1) % 4) <<
 179                                           ((symbol - 261) >> 2);
 180                         }
 181
 182                         /* Determine how far back to go */
 183                         if ((symbol = read_symbol(stream, distance)) < 0)
 184                                 return;
 185                         if (symbol < 4) dist = symbol + 1;
 186                         else {
 187                                 dist = pull_bits(stream, (symbol - 2) >> 1);
 188                                 dist += (2 << ((symbol - 2) >> 1)) + 1;
 189                                 dist += (symbol % 2) << ((symbol - 2) >> 1);
 190                         }
 191                         stream->decoded += length;
 192                         for (i = 0; i < length; i++) {
 193                                 *dest = dest[-dist];
 194                                 dest++;
 195                         }
 196                 }
 197         } while (symbol != 256); /* 256 is the end of the data block */
 198 }
 199
 200 /* Fill the lookup tables (section 3.2.2) */
 201 static void fill_code_tables(struct huffman_set *set)
 202 {
 203         int code = 0, i, length;
 204
 205         /* fill in the first code of each bit length, and the pos pointer */
 206         set->pos[0] = 0;
 207         for (i = 1; i < set->bits; i++) {
 208                 code = (code + set->count[i - 1]) << 1;
 209                 set->first[i] = code;
 210                 set->pos[i] = set->pos[i - 1] + set->count[i - 1];
 211         }
 212
 213         /* Fill in the table of symbols in order of their huffman code */
 214         for (i = 0; i < set->num_symbols; i++) {
 215                 if ((length = set->lengths[i]))
 216                         set->symbols[set->pos[length]++] = i;
 217         }
 218
 219         /* reset the pos pointer */
 220         for (i = 1; i < set->bits; i++) set->pos[i] -= set->count[i];
 221 }
 222
 223 static void init_code_tables(struct huffman_set *set)
 224 {
 225         cramfs_memset(set->lengths, 0, set->num_symbols);
 226         cramfs_memset(set->count, 0, set->bits);
 227         cramfs_memset(set->first, 0, set->bits);
 228 }
 229
 230 /* read in the huffman codes for dynamic decoding (section 3.2.7) */
 231 static void decompress_dynamic(struct bitstream *stream, unsigned char *dest)
 232 {
 233         /* I tried my best to minimize the memory footprint here, while still
 234          * keeping up performance. I really dislike the _lengths[] tables, but
 235          * I see no way of eliminating them without a sizable performance
 236          * impact. The first struct table keeps track of stats on each bit
 237          * length. The _length table keeps a record of the bit length of each
 238          * symbol. The _symbols table is for looking up symbols by the huffman
 239          * code (the pos element points to the first place in the symbol table
 240          * where that bit length occurs). I also hate the initization of these
 241          * structs, if someone knows how to compact these, lemme know. */
 242
 243         struct huffman_set *codes = &(stream->codes);
 244         struct huffman_set *lengths = &(stream->lengths);
 245         struct huffman_set *distance = &(stream->distance);
 246
 247         int hlit = pull_bits(stream, 5) + 257;
 248         int hdist = pull_bits(stream, 5) + 1;
 249         int hclen = pull_bits(stream, 4) + 4;
 250         int length, curr_code, symbol, i, last_code;
 251
 252         last_code = 0;
 253
 254         init_code_tables(codes);
 255         init_code_tables(lengths);
 256         init_code_tables(distance);
 257
 258         /* fill in the count of each bit length' as well as the lengths
 259          * table */
 260         for (i = 0; i < hclen; i++) {
 261                 length = pull_bits(stream, 3);
 262                 codes->lengths[huffman_order[i]] = length;
 263                 if (length) codes->count[length]++;
 264
 265         }
 266         fill_code_tables(codes);
 267
 268         /* Do the same for the length codes, being carefull of wrap through
 269          * to the distance table */
 270         curr_code = 0;
 271         while (curr_code < hlit) {
 272                 if ((symbol = read_symbol(stream, codes)) < 0) return;
 273                 if (symbol == 0) {
 274                         curr_code++;
 275                         last_code = 0;
 276                 } else if (symbol < 16) { /* Literal length */
 277                         lengths->lengths[curr_code] =  last_code = symbol;
 278                         lengths->count[symbol]++;
 279                         curr_code++;
 280                 } else if (symbol == 16) { /* repeat the last symbol 3 - 6
 281                                             * times */
 282                         length = 3 + pull_bits(stream, 2);
 283                         for (;length; length--, curr_code++)
 284                                 if (curr_code < hlit) {
 285                                         lengths->lengths[curr_code] =
 286                                                 last_code;
 287                                         lengths->count[last_code]++;
 288                                 } else { /* wrap to the distance table */
 289                                         distance->lengths[curr_code - hlit] =
 290                                                 last_code;
 291                                         distance->count[last_code]++;
 292                                 }
 293                 } else if (symbol == 17) { /* repeat a bit length 0 */
 294                         curr_code += 3 + pull_bits(stream, 3);
 295                         last_code = 0;
 296                 } else { /* same, but more times */
 297                         curr_code += 11 + pull_bits(stream, 7);
 298                         last_code = 0;
 299                 }
 300         }
 301         fill_code_tables(lengths);
 302
 303         /* Fill the distance table, don't need to worry about wrapthrough
 304          * here */
 305         curr_code -= hlit;
 306         while (curr_code < hdist) {
 307                 if ((symbol = read_symbol(stream, codes)) < 0) return;
 308                 if (symbol == 0) {
 309                         curr_code++;
 310                         last_code = 0;
 311                 } else if (symbol < 16) {
 312                         distance->lengths[curr_code] = last_code = symbol;
 313                         distance->count[symbol]++;
 314                         curr_code++;
 315                 } else if (symbol == 16) {
 316                         length = 3 + pull_bits(stream, 2);
 317                         for (;length; length--, curr_code++) {
 318                                 distance->lengths[curr_code] =
 319                                         last_code;
 320                                 distance->count[last_code]++;
 321                         }
 322                 } else if (symbol == 17) {
 323                         curr_code += 3 + pull_bits(stream, 3);
 324                         last_code = 0;
 325                 } else {
 326                         curr_code += 11 + pull_bits(stream, 7);
 327                         last_code = 0;
 328                 }
 329         }
 330         fill_code_tables(distance);
 331
 332         decompress_huffman(stream, dest);
 333 }
 334
 335 /* fill in the length and distance huffman codes for fixed encoding
 336  * (section 3.2.6) */
 337 static void decompress_fixed(struct bitstream *stream, unsigned char *dest)
 338 {
 339         /* let gcc fill in the initial values */
 340         struct huffman_set *lengths = &(stream->lengths);
 341         struct huffman_set *distance = &(stream->distance);
 342
 343         cramfs_memset(lengths->count, 0, 16);
 344         cramfs_memset(lengths->first, 0, 16);
 345         cramfs_memset(lengths->lengths, 8, 144);
 346         cramfs_memset(lengths->lengths + 144, 9, 112);
 347         cramfs_memset(lengths->lengths + 256, 7, 24);
 348         cramfs_memset(lengths->lengths + 280, 8, 8);
 349         lengths->count[7] = 24;
 350         lengths->count[8] = 152;
 351         lengths->count[9] = 112;
 352
 353         cramfs_memset(distance->count, 0, 16);
 354         cramfs_memset(distance->first, 0, 16);
 355         cramfs_memset(distance->lengths, 5, 32);
 356         distance->count[5] = 32;
 357
 358
 359         fill_code_tables(lengths);
 360         fill_code_tables(distance);
 361
 362
 363         decompress_huffman(stream, dest);
 364 }
 365
 366 /* returns the number of bytes decoded, < 0 if there was an error. Note that
 367  * this function assumes that the block starts on a byte boundry
 368  * (non-compliant, but I don't see where this would happen). section 3.2.3 */
 369 long decompress_block(unsigned char *dest, unsigned char *source,
 370                       void *(*inflate_memcpy)(void *, const void *, size))
 371 {
 372         int bfinal, btype;
 373         struct bitstream stream;
 374
 375         init_stream(&stream, source, inflate_memcpy);
 376         do {
 377                 bfinal = pull_bit(&stream);
 378                 btype = pull_bits(&stream, 2);
 379                 if (btype == NO_COMP) decompress_none(&stream, dest + stream.decoded);
 380                 else if (btype == DYNAMIC_COMP)
 381                         decompress_dynamic(&stream, dest + stream.decoded);
 382                 else if (btype == FIXED_COMP) decompress_fixed(&stream, dest + stream.decoded);
 383                 else stream.error = COMP_UNKNOWN;
 384         } while (!bfinal && !stream.error);
 385
 386 #if 0
 387         putstr("decompress_block start\r\n");
 388         putLabeledWord("stream.error = ",stream.error);
 389         putLabeledWord("stream.decoded = ",stream.decoded);
 390         putLabeledWord("dest = ",dest);
 391         putstr("decompress_block end\r\n");
 392 #endif
 393         return stream.error ? -stream.error : stream.decoded;
 394 }
 395
 396 #endif /* CFG_CMD_JFFS2 */