blob: 2f13412f98b01df041b562cb1a7abab95abebb67 [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/*
Wolfgang Denk1a459662013-07-08 09:37:19 +02009 * SPDX-License-Identifier: GPL-2.0+
wdenkae644802002-03-08 23:11:41 +000010 */
11
12#include <config.h>
wdenkae644802002-03-08 23:11:41 +000013#include <jffs2/mini_inflate.h>
14
15/* The order that the code lengths in section 3.2.7 are in */
16static 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
19inline 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 */
27static 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 */
68inline 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
88inline 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 */
99static 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) */
108static 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) */
123static 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 */
141static 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) */
184static 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
206static 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) */
214static 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) */
320static 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 */
352long 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}