blob: 4f511ec1a479e8d5fa93e5ea87c559102cfd2de1 [file] [log] [blame]
wdenkae644802002-03-08 23:11:41 +00001/*-------------------------------------------------------------------------
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 */
33static 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
36inline 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 */
44static 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 */
85inline 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
105inline 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 */
116static 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) */
125static 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) */
140static 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 */
158static 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) */
201static 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
223static 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) */
231static 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) */
337static 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 */
369long 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 */