zuncompress.c revision 225827
1222210Sdelphij/* $NetBSD: zuncompress.c,v 1.8 2010/11/06 21:42:32 mrg Exp $ */ 2166255Sdelphij 3166255Sdelphij/*- 4166255Sdelphij * Copyright (c) 1985, 1986, 1992, 1993 5166255Sdelphij * The Regents of the University of California. All rights reserved. 6166255Sdelphij * 7166255Sdelphij * This code is derived from software contributed to Berkeley by 8166255Sdelphij * Diomidis Spinellis and James A. Woods, derived from original 9166255Sdelphij * work by Spencer Thomas and Joseph Orost. 10166255Sdelphij * 11166255Sdelphij * Redistribution and use in source and binary forms, with or without 12166255Sdelphij * modification, are permitted provided that the following conditions 13166255Sdelphij * are met: 14166255Sdelphij * 1. Redistributions of source code must retain the above copyright 15166255Sdelphij * notice, this list of conditions and the following disclaimer. 16166255Sdelphij * 2. Redistributions in binary form must reproduce the above copyright 17166255Sdelphij * notice, this list of conditions and the following disclaimer in the 18166255Sdelphij * documentation and/or other materials provided with the distribution. 19166255Sdelphij * 3. Neither the name of the University nor the names of its contributors 20166255Sdelphij * may be used to endorse or promote products derived from this software 21166255Sdelphij * without specific prior written permission. 22166255Sdelphij * 23166255Sdelphij * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24166255Sdelphij * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25166255Sdelphij * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26166255Sdelphij * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27166255Sdelphij * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28166255Sdelphij * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29166255Sdelphij * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30166255Sdelphij * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31166255Sdelphij * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32166255Sdelphij * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33166255Sdelphij * SUCH DAMAGE. 34166255Sdelphij * 35166255Sdelphij * from: NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp 36166255Sdelphij * $FreeBSD: head/usr.bin/gzip/zuncompress.c 225827 2011-09-28 08:47:17Z bz $ 37166255Sdelphij */ 38166255Sdelphij 39166255Sdelphij/* This file is #included by gzip.c */ 40166255Sdelphij 41166255Sdelphijstatic int zread(void *, char *, int); 42166255Sdelphij 43166255Sdelphij#define tab_prefixof(i) (zs->zs_codetab[i]) 44166255Sdelphij#define tab_suffixof(i) ((char_type *)(zs->zs_htab))[i] 45166255Sdelphij#define de_stack ((char_type *)&tab_suffixof(1 << BITS)) 46166255Sdelphij 47166255Sdelphij#define BITS 16 /* Default bits. */ 48166255Sdelphij#define HSIZE 69001 /* 95% occupancy */ /* XXX may not need HSIZE */ 49166255Sdelphij#define BIT_MASK 0x1f /* Defines for third byte of header. */ 50166255Sdelphij#define BLOCK_MASK 0x80 51166255Sdelphij#define CHECK_GAP 10000 /* Ratio check interval. */ 52166255Sdelphij#define BUFSIZE (64 * 1024) 53166255Sdelphij 54166255Sdelphij/* 55166255Sdelphij * Masks 0x40 and 0x20 are free. I think 0x20 should mean that there is 56166255Sdelphij * a fourth header byte (for expansion). 57166255Sdelphij */ 58166255Sdelphij#define INIT_BITS 9 /* Initial number of bits/code. */ 59166255Sdelphij 60166255Sdelphij/* 61166255Sdelphij * the next two codes should not be changed lightly, as they must not 62166255Sdelphij * lie within the contiguous general code space. 63166255Sdelphij */ 64166255Sdelphij#define FIRST 257 /* First free entry. */ 65166255Sdelphij#define CLEAR 256 /* Table clear output code. */ 66166255Sdelphij 67166255Sdelphij 68166255Sdelphij#define MAXCODE(n_bits) ((1 << (n_bits)) - 1) 69166255Sdelphij 70166255Sdelphijtypedef long code_int; 71166255Sdelphijtypedef long count_int; 72166255Sdelphijtypedef u_char char_type; 73166255Sdelphij 74166255Sdelphijstatic char_type magic_header[] = 75166255Sdelphij {'\037', '\235'}; /* 1F 9D */ 76166255Sdelphij 77166255Sdelphijstatic char_type rmask[9] = 78166255Sdelphij {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff}; 79166255Sdelphij 80166255Sdelphij/* XXX zuncompress global */ 81166255Sdelphijoff_t total_compressed_bytes; 82166255Sdelphijsize_t compressed_prelen; 83166255Sdelphijchar *compressed_pre; 84166255Sdelphij 85166255Sdelphijstruct s_zstate { 86166255Sdelphij FILE *zs_fp; /* File stream for I/O */ 87166255Sdelphij char zs_mode; /* r or w */ 88166255Sdelphij enum { 89166255Sdelphij S_START, S_MIDDLE, S_EOF 90166255Sdelphij } zs_state; /* State of computation */ 91166255Sdelphij int zs_n_bits; /* Number of bits/code. */ 92166255Sdelphij int zs_maxbits; /* User settable max # bits/code. */ 93166255Sdelphij code_int zs_maxcode; /* Maximum code, given n_bits. */ 94166255Sdelphij code_int zs_maxmaxcode; /* Should NEVER generate this code. */ 95166255Sdelphij count_int zs_htab [HSIZE]; 96166255Sdelphij u_short zs_codetab [HSIZE]; 97166255Sdelphij code_int zs_hsize; /* For dynamic table sizing. */ 98166255Sdelphij code_int zs_free_ent; /* First unused entry. */ 99166255Sdelphij /* 100166255Sdelphij * Block compression parameters -- after all codes are used up, 101166255Sdelphij * and compression rate changes, start over. 102166255Sdelphij */ 103166255Sdelphij int zs_block_compress; 104166255Sdelphij int zs_clear_flg; 105166255Sdelphij long zs_ratio; 106166255Sdelphij count_int zs_checkpoint; 107166255Sdelphij int zs_offset; 108166255Sdelphij long zs_in_count; /* Length of input. */ 109166255Sdelphij long zs_bytes_out; /* Length of compressed output. */ 110166255Sdelphij long zs_out_count; /* # of codes output (for debugging). */ 111166255Sdelphij char_type zs_buf[BITS]; 112166255Sdelphij union { 113166255Sdelphij struct { 114166255Sdelphij long zs_fcode; 115166255Sdelphij code_int zs_ent; 116166255Sdelphij code_int zs_hsize_reg; 117166255Sdelphij int zs_hshift; 118213927Sbcr } w; /* Write parameters */ 119166255Sdelphij struct { 120166255Sdelphij char_type *zs_stackp; 121166255Sdelphij int zs_finchar; 122166255Sdelphij code_int zs_code, zs_oldcode, zs_incode; 123166255Sdelphij int zs_roffset, zs_size; 124166255Sdelphij char_type zs_gbuf[BITS]; 125166255Sdelphij } r; /* Read parameters */ 126166255Sdelphij } u; 127166255Sdelphij}; 128166255Sdelphij 129166255Sdelphijstatic code_int getcode(struct s_zstate *zs); 130166255Sdelphij 131166255Sdelphijstatic off_t 132166255Sdelphijzuncompress(FILE *in, FILE *out, char *pre, size_t prelen, 133166255Sdelphij off_t *compressed_bytes) 134166255Sdelphij{ 135166255Sdelphij off_t bin, bout = 0; 136166255Sdelphij char *buf; 137166255Sdelphij 138166255Sdelphij buf = malloc(BUFSIZE); 139166255Sdelphij if (buf == NULL) 140166255Sdelphij return -1; 141166255Sdelphij 142166255Sdelphij /* XXX */ 143166255Sdelphij compressed_prelen = prelen; 144166255Sdelphij if (prelen != 0) 145166255Sdelphij compressed_pre = pre; 146166255Sdelphij else 147166255Sdelphij compressed_pre = NULL; 148166255Sdelphij 149166255Sdelphij while ((bin = fread(buf, 1, sizeof(buf), in)) != 0) { 150194916Sdelphij if (tflag == 0 && (off_t)fwrite(buf, 1, bin, out) != bin) { 151166255Sdelphij free(buf); 152166255Sdelphij return -1; 153166255Sdelphij } 154166255Sdelphij bout += bin; 155166255Sdelphij } 156166255Sdelphij 157166255Sdelphij if (compressed_bytes) 158166255Sdelphij *compressed_bytes = total_compressed_bytes; 159166255Sdelphij 160166255Sdelphij free(buf); 161166255Sdelphij return bout; 162166255Sdelphij} 163166255Sdelphij 164166255Sdelphijstatic int 165166255Sdelphijzclose(void *zs) 166166255Sdelphij{ 167166255Sdelphij free(zs); 168166255Sdelphij /* We leave the caller to close the fd passed to zdopen() */ 169166255Sdelphij return 0; 170166255Sdelphij} 171166255Sdelphij 172166255SdelphijFILE * 173166255Sdelphijzdopen(int fd) 174166255Sdelphij{ 175166255Sdelphij struct s_zstate *zs; 176166255Sdelphij 177166255Sdelphij if ((zs = calloc(1, sizeof(struct s_zstate))) == NULL) 178166255Sdelphij return (NULL); 179166255Sdelphij 180166255Sdelphij zs->zs_state = S_START; 181166255Sdelphij 182166255Sdelphij /* XXX we can get rid of some of these */ 183166255Sdelphij zs->zs_hsize = HSIZE; /* For dynamic table sizing. */ 184166255Sdelphij zs->zs_free_ent = 0; /* First unused entry. */ 185166255Sdelphij zs->zs_block_compress = BLOCK_MASK; 186166255Sdelphij zs->zs_clear_flg = 0; /* XXX we calloc()'d this structure why = 0? */ 187166255Sdelphij zs->zs_ratio = 0; 188166255Sdelphij zs->zs_checkpoint = CHECK_GAP; 189166255Sdelphij zs->zs_in_count = 1; /* Length of input. */ 190166255Sdelphij zs->zs_out_count = 0; /* # of codes output (for debugging). */ 191166255Sdelphij zs->u.r.zs_roffset = 0; 192166255Sdelphij zs->u.r.zs_size = 0; 193166255Sdelphij 194166255Sdelphij /* 195166255Sdelphij * Layering compress on top of stdio in order to provide buffering, 196166255Sdelphij * and ensure that reads and write work with the data specified. 197166255Sdelphij */ 198166255Sdelphij if ((zs->zs_fp = fdopen(fd, "r")) == NULL) { 199166255Sdelphij free(zs); 200166255Sdelphij return NULL; 201166255Sdelphij } 202166255Sdelphij 203166255Sdelphij return funopen(zs, zread, NULL, NULL, zclose); 204166255Sdelphij} 205166255Sdelphij 206166255Sdelphij/* 207166255Sdelphij * Decompress read. This routine adapts to the codes in the file building 208166255Sdelphij * the "string" table on-the-fly; requiring no table to be stored in the 209166255Sdelphij * compressed file. The tables used herein are shared with those of the 210166255Sdelphij * compress() routine. See the definitions above. 211166255Sdelphij */ 212166255Sdelphijstatic int 213166255Sdelphijzread(void *cookie, char *rbp, int num) 214166255Sdelphij{ 215166255Sdelphij u_int count, i; 216166255Sdelphij struct s_zstate *zs; 217166255Sdelphij u_char *bp, header[3]; 218166255Sdelphij 219166255Sdelphij if (num == 0) 220166255Sdelphij return (0); 221166255Sdelphij 222166255Sdelphij zs = cookie; 223166255Sdelphij count = num; 224166255Sdelphij bp = (u_char *)rbp; 225166255Sdelphij switch (zs->zs_state) { 226166255Sdelphij case S_START: 227166255Sdelphij zs->zs_state = S_MIDDLE; 228166255Sdelphij break; 229166255Sdelphij case S_MIDDLE: 230166255Sdelphij goto middle; 231166255Sdelphij case S_EOF: 232166255Sdelphij goto eof; 233166255Sdelphij } 234166255Sdelphij 235166255Sdelphij /* Check the magic number */ 236166255Sdelphij for (i = 0; i < 3 && compressed_prelen; i++, compressed_prelen--) 237166255Sdelphij header[i] = *compressed_pre++; 238166255Sdelphij 239166255Sdelphij if (fread(header + i, 1, sizeof(header) - i, zs->zs_fp) != 240166255Sdelphij sizeof(header) - i || 241166255Sdelphij memcmp(header, magic_header, sizeof(magic_header)) != 0) { 242166255Sdelphij errno = EFTYPE; 243166255Sdelphij return (-1); 244166255Sdelphij } 245166255Sdelphij total_compressed_bytes = 0; 246166255Sdelphij zs->zs_maxbits = header[2]; /* Set -b from file. */ 247166255Sdelphij zs->zs_block_compress = zs->zs_maxbits & BLOCK_MASK; 248166255Sdelphij zs->zs_maxbits &= BIT_MASK; 249166255Sdelphij zs->zs_maxmaxcode = 1L << zs->zs_maxbits; 250225827Sbz if (zs->zs_maxbits > BITS || zs->zs_maxbits < 12) { 251166255Sdelphij errno = EFTYPE; 252166255Sdelphij return (-1); 253166255Sdelphij } 254166255Sdelphij /* As above, initialize the first 256 entries in the table. */ 255166255Sdelphij zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS); 256166255Sdelphij for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0; zs->u.r.zs_code--) { 257166255Sdelphij tab_prefixof(zs->u.r.zs_code) = 0; 258166255Sdelphij tab_suffixof(zs->u.r.zs_code) = (char_type) zs->u.r.zs_code; 259166255Sdelphij } 260166255Sdelphij zs->zs_free_ent = zs->zs_block_compress ? FIRST : 256; 261166255Sdelphij 262225827Sbz zs->u.r.zs_oldcode = -1; 263166255Sdelphij zs->u.r.zs_stackp = de_stack; 264166255Sdelphij 265166255Sdelphij while ((zs->u.r.zs_code = getcode(zs)) > -1) { 266166255Sdelphij 267166255Sdelphij if ((zs->u.r.zs_code == CLEAR) && zs->zs_block_compress) { 268166255Sdelphij for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0; 269166255Sdelphij zs->u.r.zs_code--) 270166255Sdelphij tab_prefixof(zs->u.r.zs_code) = 0; 271166255Sdelphij zs->zs_clear_flg = 1; 272225827Sbz zs->zs_free_ent = FIRST; 273225827Sbz zs->u.r.zs_oldcode = -1; 274225827Sbz continue; 275166255Sdelphij } 276166255Sdelphij zs->u.r.zs_incode = zs->u.r.zs_code; 277166255Sdelphij 278166255Sdelphij /* Special case for KwKwK string. */ 279166255Sdelphij if (zs->u.r.zs_code >= zs->zs_free_ent) { 280225827Sbz if (zs->u.r.zs_code > zs->zs_free_ent || 281225827Sbz zs->u.r.zs_oldcode == -1) { 282225827Sbz /* Bad stream. */ 283225827Sbz errno = EINVAL; 284225827Sbz return (-1); 285225827Sbz } 286166255Sdelphij *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar; 287166255Sdelphij zs->u.r.zs_code = zs->u.r.zs_oldcode; 288166255Sdelphij } 289225827Sbz /* 290225827Sbz * The above condition ensures that code < free_ent. 291225827Sbz * The construction of tab_prefixof in turn guarantees that 292225827Sbz * each iteration decreases code and therefore stack usage is 293225827Sbz * bound by 1 << BITS - 256. 294225827Sbz */ 295166255Sdelphij 296166255Sdelphij /* Generate output characters in reverse order. */ 297166255Sdelphij while (zs->u.r.zs_code >= 256) { 298166255Sdelphij *zs->u.r.zs_stackp++ = tab_suffixof(zs->u.r.zs_code); 299166255Sdelphij zs->u.r.zs_code = tab_prefixof(zs->u.r.zs_code); 300166255Sdelphij } 301166255Sdelphij *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar = tab_suffixof(zs->u.r.zs_code); 302166255Sdelphij 303166255Sdelphij /* And put them out in forward order. */ 304166255Sdelphijmiddle: do { 305166255Sdelphij if (count-- == 0) 306166255Sdelphij return (num); 307166255Sdelphij *bp++ = *--zs->u.r.zs_stackp; 308166255Sdelphij } while (zs->u.r.zs_stackp > de_stack); 309166255Sdelphij 310166255Sdelphij /* Generate the new entry. */ 311225827Sbz if ((zs->u.r.zs_code = zs->zs_free_ent) < zs->zs_maxmaxcode && 312225827Sbz zs->u.r.zs_oldcode != -1) { 313166255Sdelphij tab_prefixof(zs->u.r.zs_code) = (u_short) zs->u.r.zs_oldcode; 314166255Sdelphij tab_suffixof(zs->u.r.zs_code) = zs->u.r.zs_finchar; 315166255Sdelphij zs->zs_free_ent = zs->u.r.zs_code + 1; 316166255Sdelphij } 317166255Sdelphij 318166255Sdelphij /* Remember previous code. */ 319166255Sdelphij zs->u.r.zs_oldcode = zs->u.r.zs_incode; 320166255Sdelphij } 321166255Sdelphij zs->zs_state = S_EOF; 322166255Sdelphijeof: return (num - count); 323166255Sdelphij} 324166255Sdelphij 325166255Sdelphij/*- 326166255Sdelphij * Read one code from the standard input. If EOF, return -1. 327166255Sdelphij * Inputs: 328166255Sdelphij * stdin 329166255Sdelphij * Outputs: 330166255Sdelphij * code or -1 is returned. 331166255Sdelphij */ 332166255Sdelphijstatic code_int 333166255Sdelphijgetcode(struct s_zstate *zs) 334166255Sdelphij{ 335166255Sdelphij code_int gcode; 336166255Sdelphij int r_off, bits, i; 337166255Sdelphij char_type *bp; 338166255Sdelphij 339166255Sdelphij bp = zs->u.r.zs_gbuf; 340166255Sdelphij if (zs->zs_clear_flg > 0 || zs->u.r.zs_roffset >= zs->u.r.zs_size || 341166255Sdelphij zs->zs_free_ent > zs->zs_maxcode) { 342166255Sdelphij /* 343166255Sdelphij * If the next entry will be too big for the current gcode 344166255Sdelphij * size, then we must increase the size. This implies reading 345166255Sdelphij * a new buffer full, too. 346166255Sdelphij */ 347166255Sdelphij if (zs->zs_free_ent > zs->zs_maxcode) { 348166255Sdelphij zs->zs_n_bits++; 349166255Sdelphij if (zs->zs_n_bits == zs->zs_maxbits) /* Won't get any bigger now. */ 350166255Sdelphij zs->zs_maxcode = zs->zs_maxmaxcode; 351166255Sdelphij else 352166255Sdelphij zs->zs_maxcode = MAXCODE(zs->zs_n_bits); 353166255Sdelphij } 354166255Sdelphij if (zs->zs_clear_flg > 0) { 355166255Sdelphij zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS); 356166255Sdelphij zs->zs_clear_flg = 0; 357166255Sdelphij } 358166255Sdelphij /* XXX */ 359166255Sdelphij for (i = 0; i < zs->zs_n_bits && compressed_prelen; i++, compressed_prelen--) 360166255Sdelphij zs->u.r.zs_gbuf[i] = *compressed_pre++; 361166255Sdelphij zs->u.r.zs_size = fread(zs->u.r.zs_gbuf + i, 1, zs->zs_n_bits - i, zs->zs_fp); 362166255Sdelphij zs->u.r.zs_size += i; 363166255Sdelphij if (zs->u.r.zs_size <= 0) /* End of file. */ 364166255Sdelphij return (-1); 365166255Sdelphij zs->u.r.zs_roffset = 0; 366166255Sdelphij 367166255Sdelphij total_compressed_bytes += zs->u.r.zs_size; 368166255Sdelphij 369166255Sdelphij /* Round size down to integral number of codes. */ 370166255Sdelphij zs->u.r.zs_size = (zs->u.r.zs_size << 3) - (zs->zs_n_bits - 1); 371166255Sdelphij } 372166255Sdelphij r_off = zs->u.r.zs_roffset; 373166255Sdelphij bits = zs->zs_n_bits; 374166255Sdelphij 375166255Sdelphij /* Get to the first byte. */ 376166255Sdelphij bp += (r_off >> 3); 377166255Sdelphij r_off &= 7; 378166255Sdelphij 379166255Sdelphij /* Get first part (low order bits). */ 380166255Sdelphij gcode = (*bp++ >> r_off); 381166255Sdelphij bits -= (8 - r_off); 382166255Sdelphij r_off = 8 - r_off; /* Now, roffset into gcode word. */ 383166255Sdelphij 384166255Sdelphij /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ 385166255Sdelphij if (bits >= 8) { 386166255Sdelphij gcode |= *bp++ << r_off; 387166255Sdelphij r_off += 8; 388166255Sdelphij bits -= 8; 389166255Sdelphij } 390166255Sdelphij 391166255Sdelphij /* High order bits. */ 392166255Sdelphij gcode |= (*bp & rmask[bits]) << r_off; 393166255Sdelphij zs->u.r.zs_roffset += zs->zs_n_bits; 394166255Sdelphij 395166255Sdelphij return (gcode); 396166255Sdelphij} 397166255Sdelphij 398