1 /* $NetBSD: zuncompress.c,v 1.11 2011/08/16 13:55:02 joerg Exp $ */
2
3 /*-
4 * Copyright (c) 1985, 1986, 1992, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Diomidis Spinellis and James A. Woods, derived from original
9 * work by Spencer Thomas and Joseph Orost.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 *
35 * from: NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp
36 */
37
38 /* This file is #included by gzip.c */
39
40 static int zread(void *, char *, int);
41
42 #define tab_prefixof(i) (zs->zs_codetab[i])
43 #define tab_suffixof(i) ((char_type *)(zs->zs_htab))[i]
44 #define de_stack ((char_type *)&tab_suffixof(1 << BITS))
45
46 #define BITS 16 /* Default bits. */
47 #define HSIZE 69001 /* 95% occupancy */ /* XXX may not need HSIZE */
48 #define BIT_MASK 0x1f /* Defines for third byte of header. */
49 #define BLOCK_MASK 0x80
50 #define CHECK_GAP 10000 /* Ratio check interval. */
51 #define BUFSIZE (64 * 1024)
52
53 /*
54 * Masks 0x40 and 0x20 are free. I think 0x20 should mean that there is
55 * a fourth header byte (for expansion).
56 */
57 #define INIT_BITS 9 /* Initial number of bits/code. */
58
59 /*
60 * the next two codes should not be changed lightly, as they must not
61 * lie within the contiguous general code space.
62 */
63 #define FIRST 257 /* First free entry. */
64 #define CLEAR 256 /* Table clear output code. */
65
66
67 #define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
68
69 typedef long code_int;
70 typedef long count_int;
71 typedef u_char char_type;
72
73 static char_type magic_header[] =
74 {'\037', '\235'}; /* 1F 9D */
75
76 static char_type rmask[9] =
77 {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
78
79 /* XXX zuncompress global */
80 off_t total_compressed_bytes;
81 size_t compressed_prelen;
82 char *compressed_pre;
83
84 struct s_zstate {
85 FILE *zs_fp; /* File stream for I/O */
86 char zs_mode; /* r or w */
87 enum {
88 S_START, S_MIDDLE, S_EOF
89 } zs_state; /* State of computation */
90 int zs_n_bits; /* Number of bits/code. */
91 int zs_maxbits; /* User settable max # bits/code. */
92 code_int zs_maxcode; /* Maximum code, given n_bits. */
93 code_int zs_maxmaxcode; /* Should NEVER generate this code. */
94 count_int zs_htab [HSIZE];
95 u_short zs_codetab [HSIZE];
96 code_int zs_hsize; /* For dynamic table sizing. */
97 code_int zs_free_ent; /* First unused entry. */
98 /*
99 * Block compression parameters -- after all codes are used up,
100 * and compression rate changes, start over.
101 */
102 int zs_block_compress;
103 int zs_clear_flg;
104 long zs_ratio;
105 count_int zs_checkpoint;
106 int zs_offset;
107 long zs_in_count; /* Length of input. */
108 long zs_bytes_out; /* Length of compressed output. */
109 long zs_out_count; /* # of codes output (for debugging). */
110 char_type zs_buf[BITS];
111 union {
112 struct {
113 long zs_fcode;
114 code_int zs_ent;
115 code_int zs_hsize_reg;
116 int zs_hshift;
117 } w; /* Write parameters */
118 struct {
119 char_type *zs_stackp;
120 int zs_finchar;
121 code_int zs_code, zs_oldcode, zs_incode;
122 int zs_roffset, zs_size;
123 char_type zs_gbuf[BITS];
124 } r; /* Read parameters */
125 } u;
126 };
127
128 static code_int getcode(struct s_zstate *zs);
129
130 static off_t
zuncompress(FILE * in,FILE * out,char * pre,size_t prelen,off_t * compressed_bytes)131 zuncompress(FILE *in, FILE *out, char *pre, size_t prelen,
132 off_t *compressed_bytes)
133 {
134 off_t bin, bout = 0;
135 char *buf;
136
137 buf = malloc(BUFSIZE);
138 if (buf == NULL)
139 return -1;
140
141 /* XXX */
142 compressed_prelen = prelen;
143 if (prelen != 0)
144 compressed_pre = pre;
145 else
146 compressed_pre = NULL;
147
148 while ((bin = fread(buf, 1, sizeof(buf), in)) != 0) {
149 if (tflag == 0 && (off_t)fwrite(buf, 1, bin, out) != bin) {
150 free(buf);
151 return -1;
152 }
153 bout += bin;
154 }
155
156 if (compressed_bytes)
157 *compressed_bytes = total_compressed_bytes;
158
159 free(buf);
160 return bout;
161 }
162
163 static int
zclose(void * zs)164 zclose(void *zs)
165 {
166 free(zs);
167 /* We leave the caller to close the fd passed to zdopen() */
168 return 0;
169 }
170
171 FILE *
zdopen(int fd)172 zdopen(int fd)
173 {
174 struct s_zstate *zs;
175
176 if ((zs = calloc(1, sizeof(struct s_zstate))) == NULL)
177 return (NULL);
178
179 zs->zs_state = S_START;
180
181 /* XXX we can get rid of some of these */
182 zs->zs_hsize = HSIZE; /* For dynamic table sizing. */
183 zs->zs_free_ent = 0; /* First unused entry. */
184 zs->zs_block_compress = BLOCK_MASK;
185 zs->zs_clear_flg = 0; /* XXX we calloc()'d this structure why = 0? */
186 zs->zs_ratio = 0;
187 zs->zs_checkpoint = CHECK_GAP;
188 zs->zs_in_count = 1; /* Length of input. */
189 zs->zs_out_count = 0; /* # of codes output (for debugging). */
190 zs->u.r.zs_roffset = 0;
191 zs->u.r.zs_size = 0;
192
193 /*
194 * Layering compress on top of stdio in order to provide buffering,
195 * and ensure that reads and write work with the data specified.
196 */
197 if ((zs->zs_fp = fdopen(fd, "r")) == NULL) {
198 free(zs);
199 return NULL;
200 }
201
202 return funopen(zs, zread, NULL, NULL, zclose);
203 }
204
205 /*
206 * Decompress read. This routine adapts to the codes in the file building
207 * the "string" table on-the-fly; requiring no table to be stored in the
208 * compressed file. The tables used herein are shared with those of the
209 * compress() routine. See the definitions above.
210 */
211 static int
zread(void * cookie,char * rbp,int num)212 zread(void *cookie, char *rbp, int num)
213 {
214 u_int count, i;
215 struct s_zstate *zs;
216 u_char *bp, header[3];
217
218 if (num == 0)
219 return (0);
220
221 zs = cookie;
222 count = num;
223 bp = (u_char *)rbp;
224 switch (zs->zs_state) {
225 case S_START:
226 zs->zs_state = S_MIDDLE;
227 break;
228 case S_MIDDLE:
229 goto middle;
230 case S_EOF:
231 goto eof;
232 }
233
234 /* Check the magic number */
235 for (i = 0; i < 3 && compressed_prelen; i++, compressed_prelen--)
236 header[i] = *compressed_pre++;
237
238 if (fread(header + i, 1, sizeof(header) - i, zs->zs_fp) !=
239 sizeof(header) - i ||
240 memcmp(header, magic_header, sizeof(magic_header)) != 0) {
241 errno = EFTYPE;
242 return (-1);
243 }
244 total_compressed_bytes = 0;
245 zs->zs_maxbits = header[2]; /* Set -b from file. */
246 zs->zs_block_compress = zs->zs_maxbits & BLOCK_MASK;
247 zs->zs_maxbits &= BIT_MASK;
248 zs->zs_maxmaxcode = 1L << zs->zs_maxbits;
249 if (zs->zs_maxbits > BITS || zs->zs_maxbits < 12) {
250 errno = EFTYPE;
251 return (-1);
252 }
253 /* As above, initialize the first 256 entries in the table. */
254 zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS);
255 for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0; zs->u.r.zs_code--) {
256 tab_prefixof(zs->u.r.zs_code) = 0;
257 tab_suffixof(zs->u.r.zs_code) = (char_type) zs->u.r.zs_code;
258 }
259 zs->zs_free_ent = zs->zs_block_compress ? FIRST : 256;
260
261 zs->u.r.zs_oldcode = -1;
262 zs->u.r.zs_stackp = de_stack;
263
264 while ((zs->u.r.zs_code = getcode(zs)) > -1) {
265
266 if ((zs->u.r.zs_code == CLEAR) && zs->zs_block_compress) {
267 for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0;
268 zs->u.r.zs_code--)
269 tab_prefixof(zs->u.r.zs_code) = 0;
270 zs->zs_clear_flg = 1;
271 zs->zs_free_ent = FIRST;
272 zs->u.r.zs_oldcode = -1;
273 continue;
274 }
275 zs->u.r.zs_incode = zs->u.r.zs_code;
276
277 /* Special case for KwKwK string. */
278 if (zs->u.r.zs_code >= zs->zs_free_ent) {
279 if (zs->u.r.zs_code > zs->zs_free_ent ||
280 zs->u.r.zs_oldcode == -1) {
281 /* Bad stream. */
282 errno = EINVAL;
283 return (-1);
284 }
285 *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar;
286 zs->u.r.zs_code = zs->u.r.zs_oldcode;
287 }
288 /*
289 * The above condition ensures that code < free_ent.
290 * The construction of tab_prefixof in turn guarantees that
291 * each iteration decreases code and therefore stack usage is
292 * bound by 1 << BITS - 256.
293 */
294
295 /* Generate output characters in reverse order. */
296 while (zs->u.r.zs_code >= 256) {
297 *zs->u.r.zs_stackp++ = tab_suffixof(zs->u.r.zs_code);
298 zs->u.r.zs_code = tab_prefixof(zs->u.r.zs_code);
299 }
300 *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar = tab_suffixof(zs->u.r.zs_code);
301
302 /* And put them out in forward order. */
303 middle: do {
304 if (count-- == 0)
305 return (num);
306 *bp++ = *--zs->u.r.zs_stackp;
307 } while (zs->u.r.zs_stackp > de_stack);
308
309 /* Generate the new entry. */
310 if ((zs->u.r.zs_code = zs->zs_free_ent) < zs->zs_maxmaxcode &&
311 zs->u.r.zs_oldcode != -1) {
312 tab_prefixof(zs->u.r.zs_code) = (u_short) zs->u.r.zs_oldcode;
313 tab_suffixof(zs->u.r.zs_code) = zs->u.r.zs_finchar;
314 zs->zs_free_ent = zs->u.r.zs_code + 1;
315 }
316
317 /* Remember previous code. */
318 zs->u.r.zs_oldcode = zs->u.r.zs_incode;
319 }
320 zs->zs_state = S_EOF;
321 eof: return (num - count);
322 }
323
324 /*-
325 * Read one code from the standard input. If EOF, return -1.
326 * Inputs:
327 * stdin
328 * Outputs:
329 * code or -1 is returned.
330 */
331 static code_int
getcode(struct s_zstate * zs)332 getcode(struct s_zstate *zs)
333 {
334 code_int gcode;
335 int r_off, bits, i;
336 char_type *bp;
337
338 bp = zs->u.r.zs_gbuf;
339 if (zs->zs_clear_flg > 0 || zs->u.r.zs_roffset >= zs->u.r.zs_size ||
340 zs->zs_free_ent > zs->zs_maxcode) {
341 /*
342 * If the next entry will be too big for the current gcode
343 * size, then we must increase the size. This implies reading
344 * a new buffer full, too.
345 */
346 if (zs->zs_free_ent > zs->zs_maxcode) {
347 zs->zs_n_bits++;
348 if (zs->zs_n_bits == zs->zs_maxbits) /* Won't get any bigger now. */
349 zs->zs_maxcode = zs->zs_maxmaxcode;
350 else
351 zs->zs_maxcode = MAXCODE(zs->zs_n_bits);
352 }
353 if (zs->zs_clear_flg > 0) {
354 zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS);
355 zs->zs_clear_flg = 0;
356 }
357 /* XXX */
358 for (i = 0; i < zs->zs_n_bits && compressed_prelen; i++, compressed_prelen--)
359 zs->u.r.zs_gbuf[i] = *compressed_pre++;
360 zs->u.r.zs_size = fread(zs->u.r.zs_gbuf + i, 1, zs->zs_n_bits - i, zs->zs_fp);
361 zs->u.r.zs_size += i;
362 if (zs->u.r.zs_size <= 0) /* End of file. */
363 return (-1);
364 zs->u.r.zs_roffset = 0;
365
366 total_compressed_bytes += zs->u.r.zs_size;
367
368 /* Round size down to integral number of codes. */
369 zs->u.r.zs_size = (zs->u.r.zs_size << 3) - (zs->zs_n_bits - 1);
370 }
371 r_off = zs->u.r.zs_roffset;
372 bits = zs->zs_n_bits;
373
374 /* Get to the first byte. */
375 bp += (r_off >> 3);
376 r_off &= 7;
377
378 /* Get first part (low order bits). */
379 gcode = (*bp++ >> r_off);
380 bits -= (8 - r_off);
381 r_off = 8 - r_off; /* Now, roffset into gcode word. */
382
383 /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
384 if (bits >= 8) {
385 gcode |= *bp++ << r_off;
386 r_off += 8;
387 bits -= 8;
388 }
389
390 /* High order bits. */
391 gcode |= (*bp & rmask[bits]) << r_off;
392 zs->u.r.zs_roffset += zs->zs_n_bits;
393
394 return (gcode);
395 }
396