diff options
Diffstat (limited to 'file_cmds/gzip/zuncompress.c')
| -rw-r--r-- | file_cmds/gzip/zuncompress.c | 396 |
1 files changed, 396 insertions, 0 deletions
diff --git a/file_cmds/gzip/zuncompress.c b/file_cmds/gzip/zuncompress.c new file mode 100644 index 0000000..06df597 --- /dev/null +++ b/file_cmds/gzip/zuncompress.c @@ -0,0 +1,396 @@ +/* $NetBSD: zuncompress.c,v 1.11 2011/08/16 13:55:02 joerg Exp $ */ + +/*- + * Copyright (c) 1985, 1986, 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Diomidis Spinellis and James A. Woods, derived from original + * work by Spencer Thomas and Joseph Orost. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * from: NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp + * $FreeBSD: src/usr.bin/gzip/zuncompress.c,v 1.7 2012/10/19 14:49:42 ed Exp $ + */ + +/* This file is #included by gzip.c */ + +static int zread(void *, char *, int); + +#define tab_prefixof(i) (zs->zs_codetab[i]) +#define tab_suffixof(i) ((char_type *)(zs->zs_htab))[i] +#define de_stack ((char_type *)&tab_suffixof(1 << BITS)) + +#define BITS 16 /* Default bits. */ +#define HSIZE 69001 /* 95% occupancy */ /* XXX may not need HSIZE */ +#define BIT_MASK 0x1f /* Defines for third byte of header. */ +#define BLOCK_MASK 0x80 +#define CHECK_GAP 10000 /* Ratio check interval. */ +#define BUFSIZE (64 * 1024) + +/* + * Masks 0x40 and 0x20 are free. I think 0x20 should mean that there is + * a fourth header byte (for expansion). + */ +#define INIT_BITS 9 /* Initial number of bits/code. */ + +/* + * the next two codes should not be changed lightly, as they must not + * lie within the contiguous general code space. + */ +#define FIRST 257 /* First free entry. */ +#define CLEAR 256 /* Table clear output code. */ + + +#define MAXCODE(n_bits) ((1 << (n_bits)) - 1) + +typedef long code_int; +typedef long count_int; +typedef u_char char_type; + +static char_type magic_header[] = + {'\037', '\235'}; /* 1F 9D */ + +static char_type rmask[9] = + {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff}; + +static off_t total_compressed_bytes; +static size_t compressed_prelen; +static char *compressed_pre; + +struct s_zstate { + FILE *zs_fp; /* File stream for I/O */ + char zs_mode; /* r or w */ + enum { + S_START, S_MIDDLE, S_EOF + } zs_state; /* State of computation */ + int zs_n_bits; /* Number of bits/code. */ + int zs_maxbits; /* User settable max # bits/code. */ + code_int zs_maxcode; /* Maximum code, given n_bits. */ + code_int zs_maxmaxcode; /* Should NEVER generate this code. */ + count_int zs_htab [HSIZE]; + u_short zs_codetab [HSIZE]; + code_int zs_hsize; /* For dynamic table sizing. */ + code_int zs_free_ent; /* First unused entry. */ + /* + * Block compression parameters -- after all codes are used up, + * and compression rate changes, start over. + */ + int zs_block_compress; + int zs_clear_flg; + long zs_ratio; + count_int zs_checkpoint; + int zs_offset; + long zs_in_count; /* Length of input. */ + long zs_bytes_out; /* Length of compressed output. */ + long zs_out_count; /* # of codes output (for debugging). */ + char_type zs_buf[BITS]; + union { + struct { + long zs_fcode; + code_int zs_ent; + code_int zs_hsize_reg; + int zs_hshift; + } w; /* Write parameters */ + struct { + char_type *zs_stackp; + int zs_finchar; + code_int zs_code, zs_oldcode, zs_incode; + int zs_roffset, zs_size; + char_type zs_gbuf[BITS]; + } r; /* Read parameters */ + } u; +}; + +static code_int getcode(struct s_zstate *zs); + +static off_t +zuncompress(FILE *in, FILE *out, char *pre, size_t prelen, + off_t *compressed_bytes) +{ + off_t bin, bout = 0; + char *buf; + + buf = malloc(BUFSIZE); + if (buf == NULL) + return -1; + + /* XXX */ + compressed_prelen = prelen; + if (prelen != 0) + compressed_pre = pre; + else + compressed_pre = NULL; + + while ((bin = fread(buf, 1, BUFSIZE, in)) != 0) { + if (tflag == 0 && (off_t)fwrite(buf, 1, bin, out) != bin) { + free(buf); + return -1; + } + bout += bin; + } + + if (compressed_bytes) + *compressed_bytes = total_compressed_bytes; + + free(buf); + return bout; +} + +static int +zclose(void *zs) +{ + free(zs); + /* We leave the caller to close the fd passed to zdopen() */ + return 0; +} + +FILE * +zdopen(int fd) +{ + struct s_zstate *zs; + + if ((zs = calloc(1, sizeof(struct s_zstate))) == NULL) + return (NULL); + + zs->zs_state = S_START; + + /* XXX we can get rid of some of these */ + zs->zs_hsize = HSIZE; /* For dynamic table sizing. */ + zs->zs_free_ent = 0; /* First unused entry. */ + zs->zs_block_compress = BLOCK_MASK; + zs->zs_clear_flg = 0; /* XXX we calloc()'d this structure why = 0? */ + zs->zs_ratio = 0; + zs->zs_checkpoint = CHECK_GAP; + zs->zs_in_count = 1; /* Length of input. */ + zs->zs_out_count = 0; /* # of codes output (for debugging). */ + zs->u.r.zs_roffset = 0; + zs->u.r.zs_size = 0; + + /* + * Layering compress on top of stdio in order to provide buffering, + * and ensure that reads and write work with the data specified. + */ + if ((zs->zs_fp = fdopen(fd, "r")) == NULL) { + free(zs); + return NULL; + } + + return funopen(zs, zread, NULL, NULL, zclose); +} + +/* + * Decompress read. This routine adapts to the codes in the file building + * the "string" table on-the-fly; requiring no table to be stored in the + * compressed file. The tables used herein are shared with those of the + * compress() routine. See the definitions above. + */ +static int +zread(void *cookie, char *rbp, int num) +{ + u_int count, i; + struct s_zstate *zs; + u_char *bp, header[3]; + + if (num == 0) + return (0); + + zs = cookie; + count = num; + bp = (u_char *)rbp; + switch (zs->zs_state) { + case S_START: + zs->zs_state = S_MIDDLE; + break; + case S_MIDDLE: + goto middle; + case S_EOF: + goto eof; + } + + /* Check the magic number */ + for (i = 0; i < 3 && compressed_prelen; i++, compressed_prelen--) + header[i] = *compressed_pre++; + + if (fread(header + i, 1, sizeof(header) - i, zs->zs_fp) != + sizeof(header) - i || + memcmp(header, magic_header, sizeof(magic_header)) != 0) { + errno = EFTYPE; + return (-1); + } + total_compressed_bytes = 0; + zs->zs_maxbits = header[2]; /* Set -b from file. */ + zs->zs_block_compress = zs->zs_maxbits & BLOCK_MASK; + zs->zs_maxbits &= BIT_MASK; + zs->zs_maxmaxcode = 1L << zs->zs_maxbits; + if (zs->zs_maxbits > BITS || zs->zs_maxbits < 12) { + errno = EFTYPE; + return (-1); + } + /* As above, initialize the first 256 entries in the table. */ + zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS); + for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0; zs->u.r.zs_code--) { + tab_prefixof(zs->u.r.zs_code) = 0; + tab_suffixof(zs->u.r.zs_code) = (char_type) zs->u.r.zs_code; + } + zs->zs_free_ent = zs->zs_block_compress ? FIRST : 256; + + zs->u.r.zs_oldcode = -1; + zs->u.r.zs_stackp = de_stack; + + while ((zs->u.r.zs_code = getcode(zs)) > -1) { + + if ((zs->u.r.zs_code == CLEAR) && zs->zs_block_compress) { + for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0; + zs->u.r.zs_code--) + tab_prefixof(zs->u.r.zs_code) = 0; + zs->zs_clear_flg = 1; + zs->zs_free_ent = FIRST; + zs->u.r.zs_oldcode = -1; + continue; + } + zs->u.r.zs_incode = zs->u.r.zs_code; + + /* Special case for KwKwK string. */ + if (zs->u.r.zs_code >= zs->zs_free_ent) { + if (zs->u.r.zs_code > zs->zs_free_ent || + zs->u.r.zs_oldcode == -1) { + /* Bad stream. */ + errno = EINVAL; + return (-1); + } + *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar; + zs->u.r.zs_code = zs->u.r.zs_oldcode; + } + /* + * The above condition ensures that code < free_ent. + * The construction of tab_prefixof in turn guarantees that + * each iteration decreases code and therefore stack usage is + * bound by 1 << BITS - 256. + */ + + /* Generate output characters in reverse order. */ + while (zs->u.r.zs_code >= 256) { + *zs->u.r.zs_stackp++ = tab_suffixof(zs->u.r.zs_code); + zs->u.r.zs_code = tab_prefixof(zs->u.r.zs_code); + } + *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar = tab_suffixof(zs->u.r.zs_code); + + /* And put them out in forward order. */ +middle: do { + if (count-- == 0) + return (num); + *bp++ = *--zs->u.r.zs_stackp; + } while (zs->u.r.zs_stackp > de_stack); + + /* Generate the new entry. */ + if ((zs->u.r.zs_code = zs->zs_free_ent) < zs->zs_maxmaxcode && + zs->u.r.zs_oldcode != -1) { + tab_prefixof(zs->u.r.zs_code) = (u_short) zs->u.r.zs_oldcode; + tab_suffixof(zs->u.r.zs_code) = zs->u.r.zs_finchar; + zs->zs_free_ent = zs->u.r.zs_code + 1; + } + + /* Remember previous code. */ + zs->u.r.zs_oldcode = zs->u.r.zs_incode; + } + zs->zs_state = S_EOF; +eof: return (num - count); +} + +/*- + * Read one code from the standard input. If EOF, return -1. + * Inputs: + * stdin + * Outputs: + * code or -1 is returned. + */ +static code_int +getcode(struct s_zstate *zs) +{ + code_int gcode; + int r_off, bits, i; + char_type *bp; + + bp = zs->u.r.zs_gbuf; + if (zs->zs_clear_flg > 0 || zs->u.r.zs_roffset >= zs->u.r.zs_size || + zs->zs_free_ent > zs->zs_maxcode) { + /* + * If the next entry will be too big for the current gcode + * size, then we must increase the size. This implies reading + * a new buffer full, too. + */ + if (zs->zs_free_ent > zs->zs_maxcode) { + zs->zs_n_bits++; + if (zs->zs_n_bits == zs->zs_maxbits) /* Won't get any bigger now. */ + zs->zs_maxcode = zs->zs_maxmaxcode; + else + zs->zs_maxcode = MAXCODE(zs->zs_n_bits); + } + if (zs->zs_clear_flg > 0) { + zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS); + zs->zs_clear_flg = 0; + } + /* XXX */ + for (i = 0; i < zs->zs_n_bits && compressed_prelen; i++, compressed_prelen--) + zs->u.r.zs_gbuf[i] = *compressed_pre++; + zs->u.r.zs_size = fread(zs->u.r.zs_gbuf + i, 1, zs->zs_n_bits - i, zs->zs_fp); + zs->u.r.zs_size += i; + if (zs->u.r.zs_size <= 0) /* End of file. */ + return (-1); + zs->u.r.zs_roffset = 0; + + total_compressed_bytes += zs->u.r.zs_size; + + /* Round size down to integral number of codes. */ + zs->u.r.zs_size = (zs->u.r.zs_size << 3) - (zs->zs_n_bits - 1); + } + r_off = zs->u.r.zs_roffset; + bits = zs->zs_n_bits; + + /* Get to the first byte. */ + bp += (r_off >> 3); + r_off &= 7; + + /* Get first part (low order bits). */ + gcode = (*bp++ >> r_off); + bits -= (8 - r_off); + r_off = 8 - r_off; /* Now, roffset into gcode word. */ + + /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ + if (bits >= 8) { + gcode |= *bp++ << r_off; + r_off += 8; + bits -= 8; + } + + /* High order bits. */ + gcode |= (*bp & rmask[bits]) << r_off; + zs->u.r.zs_roffset += zs->zs_n_bits; + + return (gcode); +} + |