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