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