1// SPDX-License-Identifier: GPL-2.0+
2/*-------------------------------------------------------------------------
3 * Filename:      mini_inflate.c
4 * Version:       $Id: mini_inflate.c,v 1.3 2002/01/24 22:58:42 rfeany Exp $
5 * Copyright:     Copyright (C) 2001, Russ Dill
6 * Author:        Russ Dill <Russ.Dill@asu.edu>
7 * Description:   Mini inflate implementation (RFC 1951)
8 *-----------------------------------------------------------------------*/
9
10#include <config.h>
11#include <jffs2/mini_inflate.h>
12
13/* The order that the code lengths in section 3.2.7 are in */
14static unsigned char huffman_order[] = {16, 17, 18,  0,  8,  7,  9,  6, 10,  5,
15					11,  4, 12,  3, 13,  2, 14,  1, 15};
16
17static inline void cramfs_memset(int *s, const int c, size n)
18{
19	n--;
20	for (;n > 0; n--) s[n] = c;
21	s[0] = c;
22}
23
24/* associate a stream with a block of data and reset the stream */
25static void init_stream(struct bitstream *stream, unsigned char *data,
26			void *(*inflate_memcpy)(void *, const void *, size))
27{
28	stream->error = NO_ERROR;
29	stream->memcpy = inflate_memcpy;
30	stream->decoded = 0;
31	stream->data = data;
32	stream->bit = 0;	/* The first bit of the stream is the lsb of the
33				 * first byte */
34
35	/* really sorry about all this initialization, think of a better way,
36	 * let me know and it will get cleaned up */
37	stream->codes.bits = 8;
38	stream->codes.num_symbols = 19;
39	stream->codes.lengths = stream->code_lengths;
40	stream->codes.symbols = stream->code_symbols;
41	stream->codes.count = stream->code_count;
42	stream->codes.first = stream->code_first;
43	stream->codes.pos = stream->code_pos;
44
45	stream->lengths.bits = 16;
46	stream->lengths.num_symbols = 288;
47	stream->lengths.lengths = stream->length_lengths;
48	stream->lengths.symbols = stream->length_symbols;
49	stream->lengths.count = stream->length_count;
50	stream->lengths.first = stream->length_first;
51	stream->lengths.pos = stream->length_pos;
52
53	stream->distance.bits = 16;
54	stream->distance.num_symbols = 32;
55	stream->distance.lengths = stream->distance_lengths;
56	stream->distance.symbols = stream->distance_symbols;
57	stream->distance.count = stream->distance_count;
58	stream->distance.first = stream->distance_first;
59	stream->distance.pos = stream->distance_pos;
60
61}
62
63/* pull 'bits' bits out of the stream. The last bit pulled it returned as the
64 * msb. (section 3.1.1)
65 */
66static inline unsigned long pull_bits(struct bitstream *stream,
67				      const unsigned int bits)
68{
69	unsigned long ret;
70	int i;
71
72	ret = 0;
73	for (i = 0; i < bits; i++) {
74		ret += ((*(stream->data) >> stream->bit) & 1) << i;
75
76		/* if, before incrementing, we are on bit 7,
77		 * go to the lsb of the next byte */
78		if (stream->bit++ == 7) {
79			stream->bit = 0;
80			stream->data++;
81		}
82	}
83	return ret;
84}
85
86static inline int pull_bit(struct bitstream *stream)
87{
88	int ret = ((*(stream->data) >> stream->bit) & 1);
89	if (stream->bit++ == 7) {
90		stream->bit = 0;
91		stream->data++;
92	}
93	return ret;
94}
95
96/* discard bits up to the next whole byte */
97static void discard_bits(struct bitstream *stream)
98{
99	if (stream->bit != 0) {
100		stream->bit = 0;
101		stream->data++;
102	}
103}
104
105/* No decompression, the data is all literals (section 3.2.4) */
106static void decompress_none(struct bitstream *stream, unsigned char *dest)
107{
108	unsigned int length;
109
110	discard_bits(stream);
111	length = *(stream->data++);
112	length += *(stream->data++) << 8;
113	pull_bits(stream, 16);	/* throw away the inverse of the size */
114
115	stream->decoded += length;
116	stream->memcpy(dest, stream->data, length);
117	stream->data += length;
118}
119
120/* Read in a symbol from the stream (section 3.2.2) */
121static int read_symbol(struct bitstream *stream, struct huffman_set *set)
122{
123	int bits = 0;
124	int code = 0;
125	while (!(set->count[bits] && code < set->first[bits] +
126					     set->count[bits])) {
127		code = (code << 1) + pull_bit(stream);
128		if (++bits > set->bits) {
129			/* error decoding (corrupted data?) */
130			stream->error = CODE_NOT_FOUND;
131			return -1;
132		}
133	}
134	return set->symbols[set->pos[bits] + code - set->first[bits]];
135}
136
137/* decompress a stream of data encoded with the passed length and distance
138 * huffman codes */
139static void decompress_huffman(struct bitstream *stream, unsigned char *dest)
140{
141	struct huffman_set *lengths = &(stream->lengths);
142	struct huffman_set *distance = &(stream->distance);
143
144	int symbol, length, dist, i;
145
146	do {
147		if ((symbol = read_symbol(stream, lengths)) < 0) return;
148		if (symbol < 256) {
149			*(dest++) = symbol; /* symbol is a literal */
150			stream->decoded++;
151		} else if (symbol > 256) {
152			/* Determine the length of the repitition
153			 * (section 3.2.5) */
154			if (symbol < 265) length = symbol - 254;
155			else if (symbol == 285) length = 258;
156			else {
157				length = pull_bits(stream, (symbol - 261) >> 2);
158				length += (4 << ((symbol - 261) >> 2)) + 3;
159				length += ((symbol - 1) % 4) <<
160					  ((symbol - 261) >> 2);
161			}
162
163			/* Determine how far back to go */
164			if ((symbol = read_symbol(stream, distance)) < 0)
165				return;
166			if (symbol < 4) dist = symbol + 1;
167			else {
168				dist = pull_bits(stream, (symbol - 2) >> 1);
169				dist += (2 << ((symbol - 2) >> 1)) + 1;
170				dist += (symbol % 2) << ((symbol - 2) >> 1);
171			}
172			stream->decoded += length;
173			for (i = 0; i < length; i++) {
174				*dest = dest[-dist];
175				dest++;
176			}
177		}
178	} while (symbol != 256); /* 256 is the end of the data block */
179}
180
181/* Fill the lookup tables (section 3.2.2) */
182static void fill_code_tables(struct huffman_set *set)
183{
184	int code = 0, i, length;
185
186	/* fill in the first code of each bit length, and the pos pointer */
187	set->pos[0] = 0;
188	for (i = 1; i < set->bits; i++) {
189		code = (code + set->count[i - 1]) << 1;
190		set->first[i] = code;
191		set->pos[i] = set->pos[i - 1] + set->count[i - 1];
192	}
193
194	/* Fill in the table of symbols in order of their huffman code */
195	for (i = 0; i < set->num_symbols; i++) {
196		if ((length = set->lengths[i]))
197			set->symbols[set->pos[length]++] = i;
198	}
199
200	/* reset the pos pointer */
201	for (i = 1; i < set->bits; i++) set->pos[i] -= set->count[i];
202}
203
204static void init_code_tables(struct huffman_set *set)
205{
206	cramfs_memset(set->lengths, 0, set->num_symbols);
207	cramfs_memset(set->count, 0, set->bits);
208	cramfs_memset(set->first, 0, set->bits);
209}
210
211/* read in the huffman codes for dynamic decoding (section 3.2.7) */
212static void decompress_dynamic(struct bitstream *stream, unsigned char *dest)
213{
214	/* I tried my best to minimize the memory footprint here, while still
215	 * keeping up performance. I really dislike the _lengths[] tables, but
216	 * I see no way of eliminating them without a sizable performance
217	 * impact. The first struct table keeps track of stats on each bit
218	 * length. The _length table keeps a record of the bit length of each
219	 * symbol. The _symbols table is for looking up symbols by the huffman
220	 * code (the pos element points to the first place in the symbol table
221	 * where that bit length occurs). I also hate the initization of these
222	 * structs, if someone knows how to compact these, lemme know. */
223
224	struct huffman_set *codes = &(stream->codes);
225	struct huffman_set *lengths = &(stream->lengths);
226	struct huffman_set *distance = &(stream->distance);
227
228	int hlit = pull_bits(stream, 5) + 257;
229	int hdist = pull_bits(stream, 5) + 1;
230	int hclen = pull_bits(stream, 4) + 4;
231	int length, curr_code, symbol, i, last_code;
232
233	last_code = 0;
234
235	init_code_tables(codes);
236	init_code_tables(lengths);
237	init_code_tables(distance);
238
239	/* fill in the count of each bit length' as well as the lengths
240	 * table */
241	for (i = 0; i < hclen; i++) {
242		length = pull_bits(stream, 3);
243		codes->lengths[huffman_order[i]] = length;
244		if (length) codes->count[length]++;
245
246	}
247	fill_code_tables(codes);
248
249	/* Do the same for the length codes, being carefull of wrap through
250	 * to the distance table */
251	curr_code = 0;
252	while (curr_code < hlit) {
253		if ((symbol = read_symbol(stream, codes)) < 0) return;
254		if (symbol == 0) {
255			curr_code++;
256			last_code = 0;
257		} else if (symbol < 16) { /* Literal length */
258			lengths->lengths[curr_code] =  last_code = symbol;
259			lengths->count[symbol]++;
260			curr_code++;
261		} else if (symbol == 16) { /* repeat the last symbol 3 - 6
262					    * times */
263			length = 3 + pull_bits(stream, 2);
264			for (;length; length--, curr_code++)
265				if (curr_code < hlit) {
266					lengths->lengths[curr_code] =
267						last_code;
268					lengths->count[last_code]++;
269				} else { /* wrap to the distance table */
270					distance->lengths[curr_code - hlit] =
271						last_code;
272					distance->count[last_code]++;
273				}
274		} else if (symbol == 17) { /* repeat a bit length 0 */
275			curr_code += 3 + pull_bits(stream, 3);
276			last_code = 0;
277		} else { /* same, but more times */
278			curr_code += 11 + pull_bits(stream, 7);
279			last_code = 0;
280		}
281	}
282	fill_code_tables(lengths);
283
284	/* Fill the distance table, don't need to worry about wrapthrough
285	 * here */
286	curr_code -= hlit;
287	while (curr_code < hdist) {
288		if ((symbol = read_symbol(stream, codes)) < 0) return;
289		if (symbol == 0) {
290			curr_code++;
291			last_code = 0;
292		} else if (symbol < 16) {
293			distance->lengths[curr_code] = last_code = symbol;
294			distance->count[symbol]++;
295			curr_code++;
296		} else if (symbol == 16) {
297			length = 3 + pull_bits(stream, 2);
298			for (;length; length--, curr_code++) {
299				distance->lengths[curr_code] =
300					last_code;
301				distance->count[last_code]++;
302			}
303		} else if (symbol == 17) {
304			curr_code += 3 + pull_bits(stream, 3);
305			last_code = 0;
306		} else {
307			curr_code += 11 + pull_bits(stream, 7);
308			last_code = 0;
309		}
310	}
311	fill_code_tables(distance);
312
313	decompress_huffman(stream, dest);
314}
315
316/* fill in the length and distance huffman codes for fixed encoding
317 * (section 3.2.6) */
318static void decompress_fixed(struct bitstream *stream, unsigned char *dest)
319{
320	/* let gcc fill in the initial values */
321	struct huffman_set *lengths = &(stream->lengths);
322	struct huffman_set *distance = &(stream->distance);
323
324	cramfs_memset(lengths->count, 0, 16);
325	cramfs_memset(lengths->first, 0, 16);
326	cramfs_memset(lengths->lengths, 8, 144);
327	cramfs_memset(lengths->lengths + 144, 9, 112);
328	cramfs_memset(lengths->lengths + 256, 7, 24);
329	cramfs_memset(lengths->lengths + 280, 8, 8);
330	lengths->count[7] = 24;
331	lengths->count[8] = 152;
332	lengths->count[9] = 112;
333
334	cramfs_memset(distance->count, 0, 16);
335	cramfs_memset(distance->first, 0, 16);
336	cramfs_memset(distance->lengths, 5, 32);
337	distance->count[5] = 32;
338
339
340	fill_code_tables(lengths);
341	fill_code_tables(distance);
342
343
344	decompress_huffman(stream, dest);
345}
346
347/* returns the number of bytes decoded, < 0 if there was an error. Note that
348 * this function assumes that the block starts on a byte boundry
349 * (non-compliant, but I don't see where this would happen). section 3.2.3 */
350long decompress_block(unsigned char *dest, unsigned char *source,
351		      void *(*inflate_memcpy)(void *, const void *, size))
352{
353	int bfinal, btype;
354	struct bitstream stream;
355
356	init_stream(&stream, source, inflate_memcpy);
357	do {
358		bfinal = pull_bit(&stream);
359		btype = pull_bits(&stream, 2);
360		if (btype == NO_COMP) decompress_none(&stream, dest + stream.decoded);
361		else if (btype == DYNAMIC_COMP)
362			decompress_dynamic(&stream, dest + stream.decoded);
363		else if (btype == FIXED_COMP) decompress_fixed(&stream, dest + stream.decoded);
364		else stream.error = COMP_UNKNOWN;
365	} while (!bfinal && !stream.error);
366
367#if 0
368	putstr("decompress_block start\r\n");
369	putLabeledWord("stream.error = ",stream.error);
370	putLabeledWord("stream.decoded = ",stream.decoded);
371	putLabeledWord("dest = ",dest);
372	putstr("decompress_block end\r\n");
373#endif
374	return stream.error ? -stream.error : stream.decoded;
375}
376