]>
Commit | Line | Data |
---|---|---|
ae644800 WD |
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 | /* | |
1a459660 | 9 | * SPDX-License-Identifier: GPL-2.0+ |
ae644800 WD |
10 | */ |
11 | ||
12 | #include <config.h> | |
ae644800 WD |
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 | } |