xref: /freebsd/usr.bin/gzip/unpack.c (revision 56e53cb8ef000c3ef72337a4095987a932cdedef)
1 /*	$FreeBSD$	*/
2 /*	$NetBSD: unpack.c,v 1.3 2017/08/04 07:27:08 mrg Exp $	*/
3 
4 /*-
5  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
6  *
7  * Copyright (c) 2009 Xin LI <delphij@FreeBSD.org>
8  * All rights reserved.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29  * SUCH DAMAGE.
30  *
31  * $FreeBSD$
32  */
33 
34 /* This file is #included by gzip.c */
35 
36 /*
37  * pack(1) file format:
38  *
39  * The first 7 bytes is the header:
40  *	00, 01 - Signature (US, RS), we already validated it earlier.
41  *	02..05 - Uncompressed size
42  *	    06 - Level for the huffman tree (<=24)
43  *
44  * pack(1) will then store symbols (leaf) nodes count in each huffman
45  * tree levels, each level would consume 1 byte (See [1]).
46  *
47  * After the symbol count table, there is the symbol table, storing
48  * symbols represented by corresponding leaf node.  EOB is not being
49  * explicitly transmitted (not necessary anyway) in the symbol table.
50  *
51  * Compressed data goes after the symbol table.
52  *
53  * NOTES
54  *
55  * [1] If we count EOB into the symbols, that would mean that we will
56  * have at most 256 symbols in the huffman tree.  pack(1) rejects empty
57  * file and files that just repeats one character, which means that we
58  * will have at least 2 symbols.  Therefore, pack(1) would reduce the
59  * last level symbol count by 2 which makes it a number in
60  * range [0..254], so all levels' symbol count would fit into 1 byte.
61  */
62 
63 #define	PACK_HEADER_LENGTH	7
64 #define	HTREE_MAXLEVEL		24
65 
66 /*
67  * unpack descriptor
68  *
69  * Represent the huffman tree in a similar way that pack(1) would
70  * store in a packed file.  We store all symbols in a linear table,
71  * and store pointers to each level's first symbol.  In addition to
72  * that, maintain two counts for each level: inner nodes count and
73  * leaf nodes count.
74  */
75 typedef struct {
76 	int	symbol_size;		/* Size of the symbol table */
77 	int	treelevels;		/* Levels for the huffman tree */
78 
79 	int    *symbolsin;		/* Table of leaf symbols count in each
80 					 * level */
81 	int    *inodesin;		/* Table of internal nodes count in
82 					 * each level */
83 
84 	char   *symbol;			/* The symbol table */
85 	char   *symbol_eob;		/* Pointer to the EOB symbol */
86 	char  **tree;			/* Decoding huffman tree (pointers to
87 					 * first symbol of each tree level */
88 
89 	off_t	uncompressed_size;	/* Uncompressed size */
90 	FILE   *fpIn;			/* Input stream */
91 	FILE   *fpOut;			/* Output stream */
92 } unpack_descriptor_t;
93 
94 /*
95  * Release resource allocated to an unpack descriptor.
96  *
97  * Caller is responsible to make sure that all of these pointers are
98  * initialized (in our case, they all point to valid memory block).
99  * We don't zero out pointers here because nobody else would ever
100  * reference the memory block without scrubbing them.
101  */
102 static void
103 unpack_descriptor_fini(unpack_descriptor_t *unpackd)
104 {
105 
106 	free(unpackd->symbolsin);
107 	free(unpackd->inodesin);
108 	free(unpackd->symbol);
109 	free(unpackd->tree);
110 
111 	fclose(unpackd->fpIn);
112 	fclose(unpackd->fpOut);
113 }
114 
115 /*
116  * Recursively fill the internal node count table
117  */
118 static void
119 unpackd_fill_inodesin(const unpack_descriptor_t *unpackd, int level)
120 {
121 
122 	/*
123 	 * The internal nodes would be 1/2 of total internal nodes and
124 	 * leaf nodes in the next level.  For the last level there
125 	 * would be no internal node by definition.
126 	 */
127 	if (level < unpackd->treelevels) {
128 		unpackd_fill_inodesin(unpackd, level + 1);
129 		unpackd->inodesin[level] = (unpackd->inodesin[level + 1] +
130 		    unpackd->symbolsin[level + 1]) / 2;
131 	} else
132 		unpackd->inodesin[level] = 0;
133 }
134 
135 /*
136  * Update counter for accepted bytes
137  */
138 static void
139 accepted_bytes(off_t *bytes_in, off_t newbytes)
140 {
141 
142 	if (bytes_in != NULL)
143 		(*bytes_in) += newbytes;
144 }
145 
146 /*
147  * Read file header and construct the tree.  Also, prepare the buffered I/O
148  * for decode routine.
149  *
150  * Return value is uncompressed size.
151  */
152 static void
153 unpack_parse_header(int in, int out, char *pre, size_t prelen, off_t *bytes_in,
154     unpack_descriptor_t *unpackd)
155 {
156 	unsigned char hdr[PACK_HEADER_LENGTH];	/* buffer for header */
157 	ssize_t bytesread;		/* Bytes read from the file */
158 	int i, j, thisbyte;
159 
160 	if (prelen > sizeof hdr)
161 		maybe_err("prelen too long");
162 
163 	/* Prepend the header buffer if we already read some data */
164 	if (prelen != 0)
165 		memcpy(hdr, pre, prelen);
166 
167 	/* Read in and fill the rest bytes of header */
168 	bytesread = read(in, hdr + prelen, PACK_HEADER_LENGTH - prelen);
169 	if (bytesread < 0)
170 		maybe_err("Error reading pack header");
171 	infile_newdata(bytesread);
172 
173 	accepted_bytes(bytes_in, PACK_HEADER_LENGTH);
174 
175 	/* Obtain uncompressed length (bytes 2,3,4,5) */
176 	unpackd->uncompressed_size = 0;
177 	for (i = 2; i <= 5; i++) {
178 		unpackd->uncompressed_size <<= 8;
179 		unpackd->uncompressed_size |= hdr[i];
180 	}
181 
182 	/* Get the levels of the tree */
183 	unpackd->treelevels = hdr[6];
184 	if (unpackd->treelevels > HTREE_MAXLEVEL || unpackd->treelevels < 1)
185 		maybe_errx("Huffman tree has insane levels");
186 
187 	/* Let libc take care for buffering from now on */
188 	if ((unpackd->fpIn = fdopen(in, "r")) == NULL)
189 		maybe_err("Can not fdopen() input stream");
190 	if ((unpackd->fpOut = fdopen(out, "w")) == NULL)
191 		maybe_err("Can not fdopen() output stream");
192 
193 	/* Allocate for the tables of bounds and the tree itself */
194 	unpackd->inodesin =
195 	    calloc(unpackd->treelevels, sizeof(*(unpackd->inodesin)));
196 	unpackd->symbolsin =
197 	    calloc(unpackd->treelevels, sizeof(*(unpackd->symbolsin)));
198 	unpackd->tree =
199 	    calloc(unpackd->treelevels, (sizeof(*(unpackd->tree))));
200 	if (unpackd->inodesin == NULL || unpackd->symbolsin == NULL ||
201 	    unpackd->tree == NULL)
202 		maybe_err("calloc");
203 
204 	/* We count from 0 so adjust to match array upper bound */
205 	unpackd->treelevels--;
206 
207 	/* Read the levels symbol count table and calculate total */
208 	unpackd->symbol_size = 1;	/* EOB */
209 	for (i = 0; i <= unpackd->treelevels; i++) {
210 		if ((thisbyte = fgetc(unpackd->fpIn)) == EOF)
211 			maybe_err("File appears to be truncated");
212 		unpackd->symbolsin[i] = (unsigned char)thisbyte;
213 		unpackd->symbol_size += unpackd->symbolsin[i];
214 	}
215 	accepted_bytes(bytes_in, unpackd->treelevels);
216 	if (unpackd->symbol_size > 256)
217 		maybe_errx("Bad symbol table");
218 	infile_newdata(unpackd->treelevels);
219 
220 	/* Allocate for the symbol table, point symbol_eob at the beginning */
221 	unpackd->symbol_eob = unpackd->symbol = calloc(1, unpackd->symbol_size);
222 	if (unpackd->symbol == NULL)
223 		maybe_err("calloc");
224 
225 	/*
226 	 * Read in the symbol table, which contain [2, 256] symbols.
227 	 * In order to fit the count in one byte, pack(1) would offset
228 	 * it by reducing 2 from the actual number from the last level.
229 	 *
230 	 * We adjust the last level's symbol count by 1 here, because
231 	 * the EOB symbol is not being transmitted explicitly.  Another
232 	 * adjustment would be done later afterward.
233 	 */
234 	unpackd->symbolsin[unpackd->treelevels]++;
235 	for (i = 0; i <= unpackd->treelevels; i++) {
236 		unpackd->tree[i] = unpackd->symbol_eob;
237 		for (j = 0; j < unpackd->symbolsin[i]; j++) {
238 			if ((thisbyte = fgetc(unpackd->fpIn)) == EOF)
239 				maybe_errx("Symbol table truncated");
240 			*unpackd->symbol_eob++ = (char)thisbyte;
241 		}
242 		infile_newdata(unpackd->symbolsin[i]);
243 		accepted_bytes(bytes_in, unpackd->symbolsin[i]);
244 	}
245 
246 	/* Now, take account for the EOB symbol as well */
247 	unpackd->symbolsin[unpackd->treelevels]++;
248 
249 	/*
250 	 * The symbolsin table has been constructed now.
251 	 * Calculate the internal nodes count table based on it.
252 	 */
253 	unpackd_fill_inodesin(unpackd, 0);
254 }
255 
256 /*
257  * Decode huffman stream, based on the huffman tree.
258  */
259 static void
260 unpack_decode(const unpack_descriptor_t *unpackd, off_t *bytes_in)
261 {
262 	int thislevel, thiscode, thisbyte, inlevelindex;
263 	int i;
264 	off_t bytes_out = 0;
265 	const char *thissymbol;	/* The symbol pointer decoded from stream */
266 
267 	/*
268 	 * Decode huffman.  Fetch every bytes from the file, get it
269 	 * into 'thiscode' bit-by-bit, then output the symbol we got
270 	 * when one has been found.
271 	 *
272 	 * Assumption: sizeof(int) > ((max tree levels + 1) / 8).
273 	 * bad things could happen if not.
274 	 */
275 	thislevel = 0;
276 	thiscode = thisbyte = 0;
277 
278 	while ((thisbyte = fgetc(unpackd->fpIn)) != EOF) {
279 		accepted_bytes(bytes_in, 1);
280 		infile_newdata(1);
281 		check_siginfo();
282 
283 		/*
284 		 * Split one bit from thisbyte, from highest to lowest,
285 		 * feed the bit into thiscode, until we got a symbol from
286 		 * the tree.
287 		 */
288 		for (i = 7; i >= 0; i--) {
289 			thiscode = (thiscode << 1) | ((thisbyte >> i) & 1);
290 
291 			/* Did we got a symbol? (referencing leaf node) */
292 			if (thiscode >= unpackd->inodesin[thislevel]) {
293 				inlevelindex =
294 				    thiscode - unpackd->inodesin[thislevel];
295 				if (inlevelindex > unpackd->symbolsin[thislevel])
296 					maybe_errx("File corrupt");
297 
298 				thissymbol =
299 				    &(unpackd->tree[thislevel][inlevelindex]);
300 				if ((thissymbol == unpackd->symbol_eob) &&
301 				    (bytes_out == unpackd->uncompressed_size))
302 					goto finished;
303 
304 				fputc((*thissymbol), unpackd->fpOut);
305 				bytes_out++;
306 
307 				/* Prepare for next input */
308 				thislevel = 0; thiscode = 0;
309 			} else {
310 				thislevel++;
311 				if (thislevel > unpackd->treelevels)
312 					maybe_errx("File corrupt");
313 			}
314 		}
315 	}
316 
317 finished:
318 	if (bytes_out != unpackd->uncompressed_size)
319 		maybe_errx("Premature EOF");
320 }
321 
322 /* Handler for pack(1)'ed file */
323 static off_t
324 unpack(int in, int out, char *pre, size_t prelen, off_t *bytes_in)
325 {
326 	unpack_descriptor_t unpackd;
327 
328 	in = dup(in);
329 	if (in == -1)
330 		maybe_err("dup");
331 	out = dup(out);
332 	if (out == -1)
333 		maybe_err("dup");
334 
335 	unpack_parse_header(in, out, pre, prelen, bytes_in, &unpackd);
336 	unpack_decode(&unpackd, bytes_in);
337 	unpack_descriptor_fini(&unpackd);
338 
339 	/* If we reached here, the unpack was successful */
340 	return (unpackd.uncompressed_size);
341 }
342