Commit | Line | Data |
---|---|---|
3013fe88 NW |
1 | /* unpack.c -- decompress files in pack format. |
2 | * Copyright (C) 1992-1993 Jean-loup Gailly | |
3 | * This is free software; you can redistribute it and/or modify it under the | |
4 | * terms of the GNU General Public License, see the file COPYING. | |
5 | */ | |
6 | ||
7 | #ifndef lint | |
caed0dfe | 8 | static char rcsid[] = "$Id: unpack.c,v 1.4 1993/06/11 19:25:36 jloup Exp $"; |
3013fe88 NW |
9 | #endif |
10 | ||
3013fe88 NW |
11 | #include "tailor.h" |
12 | #include "gzip.h" | |
13 | #include "crypt.h" | |
14 | ||
15 | #define MIN(a,b) ((a) <= (b) ? (a) : (b)) | |
16 | /* The arguments must not have side effects. */ | |
17 | ||
18 | #define MAX_BITLEN 25 | |
19 | /* Maximum length of Huffman codes. (Minor modifications to the code | |
20 | * would be needed to support 32 bits codes, but pack never generates | |
21 | * more than 24 bits anyway.) | |
22 | */ | |
23 | ||
24 | #define LITERALS 256 | |
25 | /* Number of literals, excluding the End of Block (EOB) code */ | |
26 | ||
caed0dfe | 27 | #define MAX_PEEK 12 |
3013fe88 NW |
28 | /* Maximum number of 'peek' bits used to optimize traversal of the |
29 | * Huffman tree. | |
30 | */ | |
31 | ||
32 | local ulg orig_len; /* original uncompressed length */ | |
33 | local int max_len; /* maximum bit length of Huffman codes */ | |
34 | ||
35 | local uch literal[LITERALS]; | |
36 | /* The literal bytes present in the Huffman tree. The EOB code is not | |
37 | * represented. | |
38 | */ | |
39 | ||
40 | local int lit_base[MAX_BITLEN+1]; | |
41 | /* All literals of a given bit length are contiguous in literal[] and | |
42 | * have contiguous codes. literal[code+lit_base[len]] is the literal | |
43 | * for a code of len bits. | |
44 | */ | |
45 | ||
46 | local int leaves [MAX_BITLEN+1]; /* Number of leaves for each bit length */ | |
47 | local int parents[MAX_BITLEN+1]; /* Number of parents for each bit length */ | |
48 | ||
49 | local int peek_bits; /* Number of peek bits currently used */ | |
50 | ||
caed0dfe NW |
51 | /* local uch prefix_len[1 << MAX_PEEK]; */ |
52 | #define prefix_len outbuf | |
3013fe88 NW |
53 | /* For each bit pattern b of peek_bits bits, prefix_len[b] is the length |
54 | * of the Huffman code starting with a prefix of b (upper bits), or 0 | |
55 | * if all codes of prefix b have more than peek_bits bits. It is not | |
56 | * necessary to have a huge table (large MAX_PEEK) because most of the | |
57 | * codes encountered in the input stream are short codes (by construction). | |
58 | * So for most codes a single lookup will be necessary. | |
59 | */ | |
caed0dfe NW |
60 | #if 1<<MAX_PEEK > OUTBUFSIZ |
61 | error cannot overlay prefix_len and outbuf | |
62 | #endif | |
3013fe88 NW |
63 | |
64 | local ulg bitbuf; | |
65 | /* Bits are added on the low part of bitbuf and read from the high part. */ | |
66 | ||
67 | local int valid; /* number of valid bits in bitbuf */ | |
68 | /* all bits above the last valid bit are always zero */ | |
69 | ||
70 | /* Set code to the next 'bits' input bits without skipping them. code | |
71 | * must be the name of a simple variable and bits must not have side effects. | |
72 | * IN assertions: bits <= 25 (so that we still have room for an extra byte | |
73 | * when valid is only 24), and mask = (1<<bits)-1. | |
74 | */ | |
75 | #define look_bits(code,bits,mask) \ | |
76 | { \ | |
77 | while (valid < (bits)) bitbuf = (bitbuf<<8) | (ulg)get_byte(), valid += 8; \ | |
78 | code = (bitbuf >> (valid-(bits))) & (mask); \ | |
79 | } | |
80 | ||
81 | /* Skip the given number of bits (after having peeked at them): */ | |
82 | #define skip_bits(bits) (valid -= (bits)) | |
83 | ||
84 | #define clear_bitbuf() (valid = 0, bitbuf = 0) | |
85 | ||
86 | /* Local functions */ | |
87 | ||
88 | local void read_tree OF((void)); | |
89 | local void build_tree OF((void)); | |
90 | ||
91 | /* =========================================================================== | |
92 | * Read the Huffman tree. | |
93 | */ | |
94 | local void read_tree() | |
95 | { | |
96 | int len; /* bit length */ | |
97 | int base; /* base offset for a sequence of leaves */ | |
98 | int n; | |
99 | ||
100 | /* Read the original input size, MSB first */ | |
101 | orig_len = 0; | |
102 | for (n = 1; n <= 4; n++) orig_len = (orig_len << 8) | (ulg)get_byte(); | |
103 | ||
104 | max_len = (int)get_byte(); /* maximum bit length of Huffman codes */ | |
105 | if (max_len > MAX_BITLEN) { | |
106 | error("invalid compressed data -- Huffman code > 32 bits"); | |
107 | } | |
108 | ||
109 | /* Get the number of leaves at each bit length */ | |
110 | n = 0; | |
111 | for (len = 1; len <= max_len; len++) { | |
112 | leaves[len] = (int)get_byte(); | |
113 | n += leaves[len]; | |
114 | } | |
115 | if (n > LITERALS) { | |
116 | error("too many leaves in Huffman tree"); | |
117 | } | |
118 | Trace((stderr, "orig_len %ld, max_len %d, leaves %d\n", | |
119 | orig_len, max_len, n)); | |
120 | /* There are at least 2 and at most 256 leaves of length max_len. | |
121 | * (Pack arbitrarily rejects empty files and files consisting of | |
122 | * a single byte even repeated.) To fit the last leaf count in a | |
123 | * byte, it is offset by 2. However, the last literal is the EOB | |
124 | * code, and is not transmitted explicitly in the tree, so we must | |
125 | * adjust here by one only. | |
126 | */ | |
127 | leaves[max_len]++; | |
128 | ||
129 | /* Now read the leaves themselves */ | |
130 | base = 0; | |
131 | for (len = 1; len <= max_len; len++) { | |
132 | /* Remember where the literals of this length start in literal[] : */ | |
133 | lit_base[len] = base; | |
134 | /* And read the literals: */ | |
135 | for (n = leaves[len]; n > 0; n--) { | |
136 | literal[base++] = (uch)get_byte(); | |
137 | } | |
138 | } | |
139 | leaves[max_len]++; /* Now include the EOB code in the Huffman tree */ | |
140 | } | |
141 | ||
142 | /* =========================================================================== | |
143 | * Build the Huffman tree and the prefix table. | |
144 | */ | |
145 | local void build_tree() | |
146 | { | |
147 | int nodes = 0; /* number of nodes (parents+leaves) at current bit length */ | |
148 | int len; /* current bit length */ | |
149 | uch *prefixp; /* pointer in prefix_len */ | |
150 | ||
151 | for (len = max_len; len >= 1; len--) { | |
152 | /* The number of parent nodes at this level is half the total | |
153 | * number of nodes at parent level: | |
154 | */ | |
155 | nodes >>= 1; | |
156 | parents[len] = nodes; | |
157 | /* Update lit_base by the appropriate bias to skip the parent nodes | |
158 | * (which are not represented in the literal array): | |
159 | */ | |
160 | lit_base[len] -= nodes; | |
161 | /* Restore nodes to be parents+leaves: */ | |
162 | nodes += leaves[len]; | |
163 | } | |
164 | /* Construct the prefix table, from shortest leaves to longest ones. | |
165 | * The shortest code is all ones, so we start at the end of the table. | |
166 | */ | |
167 | peek_bits = MIN(max_len, MAX_PEEK); | |
168 | prefixp = &prefix_len[1<<peek_bits]; | |
169 | for (len = 1; len <= peek_bits; len++) { | |
170 | int prefixes = leaves[len] << (peek_bits-len); /* may be 0 */ | |
171 | while (prefixes--) *--prefixp = (uch)len; | |
172 | } | |
173 | /* The length of all other codes is unknown: */ | |
174 | while (prefixp > prefix_len) *--prefixp = 0; | |
175 | } | |
176 | ||
177 | /* =========================================================================== | |
178 | * Unpack in to out. This routine does not support the old pack format | |
179 | * with magic header \037\037. | |
180 | * | |
181 | * IN assertions: the buffer inbuf contains already the beginning of | |
182 | * the compressed data, from offsets inptr to insize-1 included. | |
183 | * The magic header has already been checked. The output buffer is cleared. | |
184 | */ | |
185 | int unpack(in, out) | |
186 | int in, out; /* input and output file descriptors */ | |
187 | { | |
188 | int len; /* Bit length of current code */ | |
189 | unsigned eob; /* End Of Block code */ | |
190 | register unsigned peek; /* lookahead bits */ | |
191 | unsigned peek_mask; /* Mask for peek_bits bits */ | |
192 | ||
193 | ifd = in; | |
194 | ofd = out; | |
195 | ||
196 | read_tree(); /* Read the Huffman tree */ | |
197 | build_tree(); /* Build the prefix table */ | |
198 | clear_bitbuf(); /* Initialize bit input */ | |
199 | peek_mask = (1<<peek_bits)-1; | |
200 | ||
201 | /* The eob code is the largest code among all leaves of maximal length: */ | |
202 | eob = leaves[max_len]-1; | |
203 | Trace((stderr, "eob %d %x\n", max_len, eob)); | |
204 | ||
205 | /* Decode the input data: */ | |
206 | for (;;) { | |
207 | /* Since eob is the longest code and not shorter than max_len, | |
208 | * we can peek at max_len bits without having the risk of reading | |
209 | * beyond the end of file. | |
210 | */ | |
211 | look_bits(peek, peek_bits, peek_mask); | |
212 | len = prefix_len[peek]; | |
213 | if (len > 0) { | |
214 | peek >>= peek_bits - len; /* discard the extra bits */ | |
215 | } else { | |
216 | /* Code of more than peek_bits bits, we must traverse the tree */ | |
217 | ulg mask = peek_mask; | |
218 | len = peek_bits; | |
219 | do { | |
220 | len++, mask = (mask<<1)+1; | |
221 | look_bits(peek, len, mask); | |
222 | } while (peek < parents[len]); | |
223 | /* loop as long as peek is a parent node */ | |
224 | } | |
225 | /* At this point, peek is the next complete code, of len bits */ | |
226 | if (peek == eob && len == max_len) break; /* end of file? */ | |
227 | put_ubyte(literal[peek+lit_base[len]]); | |
228 | Tracev((stderr,"%02d %04x %c\n", len, peek, | |
229 | literal[peek+lit_base[len]])); | |
230 | skip_bits(len); | |
231 | } /* for (;;) */ | |
232 | ||
233 | flush_window(); | |
234 | Trace((stderr, "bytes_out %ld\n", bytes_out)); | |
235 | if (orig_len != bytes_out) { | |
236 | error("invalid compressed data--length error"); | |
237 | } | |
238 | return OK; | |
239 | } |