[people/ms/u-boot.git] / fs / jffs2 / mini_inflate.c

/*-------------------------------------------------------------------------
 * Filename:      mini_inflate.c
 * Version:       $Id: mini_inflate.c,v 1.3 2002/01/24 22:58:42 rfeany Exp $
 * Copyright:     Copyright (C) 2001, Russ Dill
 * Author:        Russ Dill <Russ.Dill@asu.edu>
 * Description:   Mini inflate implementation (RFC 1951)
 *-----------------------------------------------------------------------*/
/*
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */

#include <config.h>

#if defined(CONFIG_CMD_JFFS2)

#include <jffs2/mini_inflate.h>

/* The order that the code lengths in section 3.2.7 are in */
static unsigned char huffman_order[] = {16, 17, 18,  0,  8,  7,  9,  6, 10,  5,
					11,  4, 12,  3, 13,  2, 14,  1, 15};

inline void cramfs_memset(int *s, const int c, size n)
{
	n--;
	for (;n > 0; n--) s[n] = c;
	s[0] = c;
}

/* associate a stream with a block of data and reset the stream */
static void init_stream(struct bitstream *stream, unsigned char *data,
			void *(*inflate_memcpy)(void *, const void *, size))
{
	stream->error = NO_ERROR;
	stream->memcpy = inflate_memcpy;
	stream->decoded = 0;
	stream->data = data;
	stream->bit = 0;	/* The first bit of the stream is the lsb of the
				 * first byte */

	/* really sorry about all this initialization, think of a better way,
	 * let me know and it will get cleaned up */
	stream->codes.bits = 8;
	stream->codes.num_symbols = 19;
	stream->codes.lengths = stream->code_lengths;
	stream->codes.symbols = stream->code_symbols;
	stream->codes.count = stream->code_count;
	stream->codes.first = stream->code_first;
	stream->codes.pos = stream->code_pos;

	stream->lengths.bits = 16;
	stream->lengths.num_symbols = 288;
	stream->lengths.lengths = stream->length_lengths;
	stream->lengths.symbols = stream->length_symbols;
	stream->lengths.count = stream->length_count;
	stream->lengths.first = stream->length_first;
	stream->lengths.pos = stream->length_pos;

	stream->distance.bits = 16;
	stream->distance.num_symbols = 32;
	stream->distance.lengths = stream->distance_lengths;
	stream->distance.symbols = stream->distance_symbols;
	stream->distance.count = stream->distance_count;
	stream->distance.first = stream->distance_first;
	stream->distance.pos = stream->distance_pos;

}

/* pull 'bits' bits out of the stream. The last bit pulled it returned as the
 * msb. (section 3.1.1)
 */
inline unsigned long pull_bits(struct bitstream *stream,
			       const unsigned int bits)
{
	unsigned long ret;
	int i;

	ret = 0;
	for (i = 0; i < bits; i++) {
		ret += ((*(stream->data) >> stream->bit) & 1) << i;

		/* if, before incrementing, we are on bit 7,
		 * go to the lsb of the next byte */
		if (stream->bit++ == 7) {
			stream->bit = 0;
			stream->data++;
		}
	}
	return ret;
}

inline int pull_bit(struct bitstream *stream)
{
	int ret = ((*(stream->data) >> stream->bit) & 1);
	if (stream->bit++ == 7) {
		stream->bit = 0;
		stream->data++;
	}
	return ret;
}

/* discard bits up to the next whole byte */
static void discard_bits(struct bitstream *stream)
{
	if (stream->bit != 0) {
		stream->bit = 0;
		stream->data++;
	}
}

/* No decompression, the data is all literals (section 3.2.4) */
static void decompress_none(struct bitstream *stream, unsigned char *dest)
{
	unsigned int length;

	discard_bits(stream);
	length = *(stream->data++);
	length += *(stream->data++) << 8;
	pull_bits(stream, 16);	/* throw away the inverse of the size */

	stream->decoded += length;
	stream->memcpy(dest, stream->data, length);
	stream->data += length;
}

/* Read in a symbol from the stream (section 3.2.2) */
static int read_symbol(struct bitstream *stream, struct huffman_set *set)
{
	int bits = 0;
	int code = 0;
	while (!(set->count[bits] && code < set->first[bits] +
					     set->count[bits])) {
		code = (code << 1) + pull_bit(stream);
		if (++bits > set->bits) {
			/* error decoding (corrupted data?) */
			stream->error = CODE_NOT_FOUND;
			return -1;
		}
	}
	return set->symbols[set->pos[bits] + code - set->first[bits]];
}

/* decompress a stream of data encoded with the passed length and distance
 * huffman codes */
static void decompress_huffman(struct bitstream *stream, unsigned char *dest)
{
	struct huffman_set *lengths = &(stream->lengths);
	struct huffman_set *distance = &(stream->distance);

	int symbol, length, dist, i;

	do {
		if ((symbol = read_symbol(stream, lengths)) < 0) return;
		if (symbol < 256) {
			*(dest++) = symbol; /* symbol is a literal */
			stream->decoded++;
		} else if (symbol > 256) {
			/* Determine the length of the repitition
			 * (section 3.2.5) */
			if (symbol < 265) length = symbol - 254;
			else if (symbol == 285) length = 258;
			else {
				length = pull_bits(stream, (symbol - 261) >> 2);
				length += (4 << ((symbol - 261) >> 2)) + 3;
				length += ((symbol - 1) % 4) <<
					  ((symbol - 261) >> 2);
			}

			/* Determine how far back to go */
			if ((symbol = read_symbol(stream, distance)) < 0)
				return;
			if (symbol < 4) dist = symbol + 1;
			else {
				dist = pull_bits(stream, (symbol - 2) >> 1);
				dist += (2 << ((symbol - 2) >> 1)) + 1;
				dist += (symbol % 2) << ((symbol - 2) >> 1);
			}
			stream->decoded += length;
			for (i = 0; i < length; i++) {
				*dest = dest[-dist];
				dest++;
			}
		}
	} while (symbol != 256); /* 256 is the end of the data block */
}

/* Fill the lookup tables (section 3.2.2) */
static void fill_code_tables(struct huffman_set *set)
{
	int code = 0, i, length;

	/* fill in the first code of each bit length, and the pos pointer */
	set->pos[0] = 0;
	for (i = 1; i < set->bits; i++) {
		code = (code + set->count[i - 1]) << 1;
		set->first[i] = code;
		set->pos[i] = set->pos[i - 1] + set->count[i - 1];
	}

	/* Fill in the table of symbols in order of their huffman code */
	for (i = 0; i < set->num_symbols; i++) {
		if ((length = set->lengths[i]))
			set->symbols[set->pos[length]++] = i;
	}

	/* reset the pos pointer */
	for (i = 1; i < set->bits; i++) set->pos[i] -= set->count[i];
}

static void init_code_tables(struct huffman_set *set)
{
	cramfs_memset(set->lengths, 0, set->num_symbols);
	cramfs_memset(set->count, 0, set->bits);
	cramfs_memset(set->first, 0, set->bits);
}

/* read in the huffman codes for dynamic decoding (section 3.2.7) */
static void decompress_dynamic(struct bitstream *stream, unsigned char *dest)
{
	/* I tried my best to minimize the memory footprint here, while still
	 * keeping up performance. I really dislike the _lengths[] tables, but
	 * I see no way of eliminating them without a sizable performance
	 * impact. The first struct table keeps track of stats on each bit
	 * length. The _length table keeps a record of the bit length of each
	 * symbol. The _symbols table is for looking up symbols by the huffman
	 * code (the pos element points to the first place in the symbol table
	 * where that bit length occurs). I also hate the initization of these
	 * structs, if someone knows how to compact these, lemme know. */

	struct huffman_set *codes = &(stream->codes);
	struct huffman_set *lengths = &(stream->lengths);
	struct huffman_set *distance = &(stream->distance);

	int hlit = pull_bits(stream, 5) + 257;
	int hdist = pull_bits(stream, 5) + 1;
	int hclen = pull_bits(stream, 4) + 4;
	int length, curr_code, symbol, i, last_code;

	last_code = 0;

	init_code_tables(codes);
	init_code_tables(lengths);
	init_code_tables(distance);

	/* fill in the count of each bit length' as well as the lengths
	 * table */
	for (i = 0; i < hclen; i++) {
		length = pull_bits(stream, 3);
		codes->lengths[huffman_order[i]] = length;
		if (length) codes->count[length]++;

	}
	fill_code_tables(codes);

	/* Do the same for the length codes, being carefull of wrap through
	 * to the distance table */
	curr_code = 0;
	while (curr_code < hlit) {
		if ((symbol = read_symbol(stream, codes)) < 0) return;
		if (symbol == 0) {
			curr_code++;
			last_code = 0;
		} else if (symbol < 16) { /* Literal length */
			lengths->lengths[curr_code] =  last_code = symbol;
			lengths->count[symbol]++;
			curr_code++;
		} else if (symbol == 16) { /* repeat the last symbol 3 - 6
					    * times */
			length = 3 + pull_bits(stream, 2);
			for (;length; length--, curr_code++)
				if (curr_code < hlit) {
					lengths->lengths[curr_code] =
						last_code;
					lengths->count[last_code]++;
				} else { /* wrap to the distance table */
					distance->lengths[curr_code - hlit] =
						last_code;
					distance->count[last_code]++;
				}
		} else if (symbol == 17) { /* repeat a bit length 0 */
			curr_code += 3 + pull_bits(stream, 3);
			last_code = 0;
		} else { /* same, but more times */
			curr_code += 11 + pull_bits(stream, 7);
			last_code = 0;
		}
	}
	fill_code_tables(lengths);

	/* Fill the distance table, don't need to worry about wrapthrough
	 * here */
	curr_code -= hlit;
	while (curr_code < hdist) {
		if ((symbol = read_symbol(stream, codes)) < 0) return;
		if (symbol == 0) {
			curr_code++;
			last_code = 0;
		} else if (symbol < 16) {
			distance->lengths[curr_code] = last_code = symbol;
			distance->count[symbol]++;
			curr_code++;
		} else if (symbol == 16) {
			length = 3 + pull_bits(stream, 2);
			for (;length; length--, curr_code++) {
				distance->lengths[curr_code] =
					last_code;
				distance->count[last_code]++;
			}
		} else if (symbol == 17) {
			curr_code += 3 + pull_bits(stream, 3);
			last_code = 0;
		} else {
			curr_code += 11 + pull_bits(stream, 7);
			last_code = 0;
		}
	}
	fill_code_tables(distance);

	decompress_huffman(stream, dest);
}

/* fill in the length and distance huffman codes for fixed encoding
 * (section 3.2.6) */
static void decompress_fixed(struct bitstream *stream, unsigned char *dest)
{
	/* let gcc fill in the initial values */
	struct huffman_set *lengths = &(stream->lengths);
	struct huffman_set *distance = &(stream->distance);

	cramfs_memset(lengths->count, 0, 16);
	cramfs_memset(lengths->first, 0, 16);
	cramfs_memset(lengths->lengths, 8, 144);
	cramfs_memset(lengths->lengths + 144, 9, 112);
	cramfs_memset(lengths->lengths + 256, 7, 24);
	cramfs_memset(lengths->lengths + 280, 8, 8);
	lengths->count[7] = 24;
	lengths->count[8] = 152;
	lengths->count[9] = 112;

	cramfs_memset(distance->count, 0, 16);
	cramfs_memset(distance->first, 0, 16);
	cramfs_memset(distance->lengths, 5, 32);
	distance->count[5] = 32;


	fill_code_tables(lengths);
	fill_code_tables(distance);


	decompress_huffman(stream, dest);
}

/* returns the number of bytes decoded, < 0 if there was an error. Note that
 * this function assumes that the block starts on a byte boundry
 * (non-compliant, but I don't see where this would happen). section 3.2.3 */
long decompress_block(unsigned char *dest, unsigned char *source,
		      void *(*inflate_memcpy)(void *, const void *, size))
{
	int bfinal, btype;
	struct bitstream stream;

	init_stream(&stream, source, inflate_memcpy);
	do {
		bfinal = pull_bit(&stream);
		btype = pull_bits(&stream, 2);
		if (btype == NO_COMP) decompress_none(&stream, dest + stream.decoded);
		else if (btype == DYNAMIC_COMP)
			decompress_dynamic(&stream, dest + stream.decoded);
		else if (btype == FIXED_COMP) decompress_fixed(&stream, dest + stream.decoded);
		else stream.error = COMP_UNKNOWN;
	} while (!bfinal && !stream.error);

#if 0
	putstr("decompress_block start\r\n");
	putLabeledWord("stream.error = ",stream.error);
	putLabeledWord("stream.decoded = ",stream.decoded);
	putLabeledWord("dest = ",dest);
	putstr("decompress_block end\r\n");
#endif
	return stream.error ? -stream.error : stream.decoded;
}

#endif
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	/*
	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
dd60d122	28	#if defined(CONFIG_CMD_JFFS2)
ae644800 WD	29
	30	#include <jffs2/mini_inflate.h>
	31
	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};
	35
	36	inline 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 */
	44	static 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	*/
	85	inline 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
105	inline 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 */
116	static 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) */
125	static 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) */
140	static 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 */
158	static 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) */
201	static 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
223	static 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) */
231	static 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) */
337	static 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 */
369	long 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
f40a7f3e	396	#endif