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 */ 397