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