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