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 } 378