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