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 *-----------------------------------------------------------------------*/
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.
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.
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
28 #if defined(CONFIG_CMD_JFFS2)
30 #include <jffs2/mini_inflate.h>
32 /* The order that the code lengths in section 3.2.7 are in */
33 static unsigned char huffman_order
[] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
34 11, 4, 12, 3, 13, 2, 14, 1, 15};
36 inline void cramfs_memset(int *s
, const int c
, size n
)
39 for (;n
> 0; n
--) s
[n
] = c
;
43 /* associate a stream with a block of data and reset the stream */
44 static void init_stream(struct bitstream
*stream
, unsigned char *data
,
45 void *(*inflate_memcpy
)(void *, const void *, size
))
47 stream
->error
= NO_ERROR
;
48 stream
->memcpy
= inflate_memcpy
;
51 stream
->bit
= 0; /* The first bit of the stream is the lsb of the
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
;
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
;
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
;
82 /* pull 'bits' bits out of the stream. The last bit pulled it returned as the
83 * msb. (section 3.1.1)
85 inline unsigned long pull_bits(struct bitstream
*stream
,
86 const unsigned int bits
)
92 for (i
= 0; i
< bits
; i
++) {
93 ret
+= ((*(stream
->data
) >> stream
->bit
) & 1) << i
;
95 /* if, before incrementing, we are on bit 7,
96 * go to the lsb of the next byte */
97 if (stream
->bit
++ == 7) {
105 inline int pull_bit(struct bitstream
*stream
)
107 int ret
= ((*(stream
->data
) >> stream
->bit
) & 1);
108 if (stream
->bit
++ == 7) {
115 /* discard bits up to the next whole byte */
116 static void discard_bits(struct bitstream
*stream
)
118 if (stream
->bit
!= 0) {
124 /* No decompression, the data is all literals (section 3.2.4) */
125 static void decompress_none(struct bitstream
*stream
, unsigned char *dest
)
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 */
134 stream
->decoded
+= length
;
135 stream
->memcpy(dest
, stream
->data
, length
);
136 stream
->data
+= length
;
139 /* Read in a symbol from the stream (section 3.2.2) */
140 static int read_symbol(struct bitstream
*stream
, struct huffman_set
*set
)
144 while (!(set
->count
[bits
] && code
< set
->first
[bits
] +
146 code
= (code
<< 1) + pull_bit(stream
);
147 if (++bits
> set
->bits
) {
148 /* error decoding (corrupted data?) */
149 stream
->error
= CODE_NOT_FOUND
;
153 return set
->symbols
[set
->pos
[bits
] + code
- set
->first
[bits
]];
156 /* decompress a stream of data encoded with the passed length and distance
158 static void decompress_huffman(struct bitstream
*stream
, unsigned char *dest
)
160 struct huffman_set
*lengths
= &(stream
->lengths
);
161 struct huffman_set
*distance
= &(stream
->distance
);
163 int symbol
, length
, dist
, i
;
166 if ((symbol
= read_symbol(stream
, lengths
)) < 0) return;
168 *(dest
++) = symbol
; /* symbol is a literal */
170 } else if (symbol
> 256) {
171 /* Determine the length of the repitition
173 if (symbol
< 265) length
= symbol
- 254;
174 else if (symbol
== 285) length
= 258;
176 length
= pull_bits(stream
, (symbol
- 261) >> 2);
177 length
+= (4 << ((symbol
- 261) >> 2)) + 3;
178 length
+= ((symbol
- 1) % 4) <<
179 ((symbol
- 261) >> 2);
182 /* Determine how far back to go */
183 if ((symbol
= read_symbol(stream
, distance
)) < 0)
185 if (symbol
< 4) dist
= symbol
+ 1;
187 dist
= pull_bits(stream
, (symbol
- 2) >> 1);
188 dist
+= (2 << ((symbol
- 2) >> 1)) + 1;
189 dist
+= (symbol
% 2) << ((symbol
- 2) >> 1);
191 stream
->decoded
+= length
;
192 for (i
= 0; i
< length
; i
++) {
197 } while (symbol
!= 256); /* 256 is the end of the data block */
200 /* Fill the lookup tables (section 3.2.2) */
201 static void fill_code_tables(struct huffman_set
*set
)
203 int code
= 0, i
, length
;
205 /* fill in the first code of each bit length, and the pos pointer */
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];
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
;
219 /* reset the pos pointer */
220 for (i
= 1; i
< set
->bits
; i
++) set
->pos
[i
] -= set
->count
[i
];
223 static void init_code_tables(struct huffman_set
*set
)
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
);
230 /* read in the huffman codes for dynamic decoding (section 3.2.7) */
231 static void decompress_dynamic(struct bitstream
*stream
, unsigned char *dest
)
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. */
243 struct huffman_set
*codes
= &(stream
->codes
);
244 struct huffman_set
*lengths
= &(stream
->lengths
);
245 struct huffman_set
*distance
= &(stream
->distance
);
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
;
254 init_code_tables(codes
);
255 init_code_tables(lengths
);
256 init_code_tables(distance
);
258 /* fill in the count of each bit length' as well as the lengths
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
]++;
266 fill_code_tables(codes
);
268 /* Do the same for the length codes, being carefull of wrap through
269 * to the distance table */
271 while (curr_code
< hlit
) {
272 if ((symbol
= read_symbol(stream
, codes
)) < 0) return;
276 } else if (symbol
< 16) { /* Literal length */
277 lengths
->lengths
[curr_code
] = last_code
= symbol
;
278 lengths
->count
[symbol
]++;
280 } else if (symbol
== 16) { /* repeat the last symbol 3 - 6
282 length
= 3 + pull_bits(stream
, 2);
283 for (;length
; length
--, curr_code
++)
284 if (curr_code
< hlit
) {
285 lengths
->lengths
[curr_code
] =
287 lengths
->count
[last_code
]++;
288 } else { /* wrap to the distance table */
289 distance
->lengths
[curr_code
- hlit
] =
291 distance
->count
[last_code
]++;
293 } else if (symbol
== 17) { /* repeat a bit length 0 */
294 curr_code
+= 3 + pull_bits(stream
, 3);
296 } else { /* same, but more times */
297 curr_code
+= 11 + pull_bits(stream
, 7);
301 fill_code_tables(lengths
);
303 /* Fill the distance table, don't need to worry about wrapthrough
306 while (curr_code
< hdist
) {
307 if ((symbol
= read_symbol(stream
, codes
)) < 0) return;
311 } else if (symbol
< 16) {
312 distance
->lengths
[curr_code
] = last_code
= symbol
;
313 distance
->count
[symbol
]++;
315 } else if (symbol
== 16) {
316 length
= 3 + pull_bits(stream
, 2);
317 for (;length
; length
--, curr_code
++) {
318 distance
->lengths
[curr_code
] =
320 distance
->count
[last_code
]++;
322 } else if (symbol
== 17) {
323 curr_code
+= 3 + pull_bits(stream
, 3);
326 curr_code
+= 11 + pull_bits(stream
, 7);
330 fill_code_tables(distance
);
332 decompress_huffman(stream
, dest
);
335 /* fill in the length and distance huffman codes for fixed encoding
337 static void decompress_fixed(struct bitstream
*stream
, unsigned char *dest
)
339 /* let gcc fill in the initial values */
340 struct huffman_set
*lengths
= &(stream
->lengths
);
341 struct huffman_set
*distance
= &(stream
->distance
);
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;
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;
359 fill_code_tables(lengths
);
360 fill_code_tables(distance
);
363 decompress_huffman(stream
, dest
);
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 */
369 long decompress_block(unsigned char *dest
, unsigned char *source
,
370 void *(*inflate_memcpy
)(void *, const void *, size
))
373 struct bitstream stream
;
375 init_stream(&stream
, source
, inflate_memcpy
);
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
);
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");
393 return stream
.error
? -stream
.error
: stream
.decoded
;