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