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
cramfs_memset(int * s,const int c,size n)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 */
init_stream(struct bitstream * stream,unsigned char * data,void * (* inflate_memcpy)(void *,const void *,size))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 */
pull_bits(struct bitstream * stream,const unsigned int bits)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
pull_bit(struct bitstream * stream)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 */
discard_bits(struct bitstream * stream)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) */
decompress_none(struct bitstream * stream,unsigned char * dest)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) */
read_symbol(struct bitstream * stream,struct huffman_set * set)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 */
decompress_huffman(struct bitstream * stream,unsigned char * dest)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) */
fill_code_tables(struct huffman_set * set)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
init_code_tables(struct huffman_set * set)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) */
decompress_dynamic(struct bitstream * stream,unsigned char * dest)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) */
decompress_fixed(struct bitstream * stream,unsigned char * dest)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 */
decompress_block(unsigned char * dest,unsigned char * source,void * (* inflate_memcpy)(void *,const void *,size))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