1 /* $NetBSD: zuncompress.c,v 1.7 2009/04/12 10:31:14 lukem Exp $ */ 2 /* $DragonFly: src/usr.bin/gzip/zuncompress.c,v 1.1 2004/10/26 11:19:31 joerg Exp $ */ 3 4 /*- 5 * Copyright (c) 1985, 1986, 1992, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 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. 11 * 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. 23 * 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. 35 * 36 * from: NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp 37 */ 38 39 /* This file is #included by gzip.c */ 40 41 static int zread(void *, char *, int); 42 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)) 46 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) 53 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. */ 59 60 /* 61 * the next two codes should not be changed lightly, as they must not 62 * lie within the contiguous general code space. 63 */ 64 #define FIRST 257 /* First free entry. */ 65 #define CLEAR 256 /* Table clear output code. */ 66 67 68 #define MAXCODE(n_bits) ((1 << (n_bits)) - 1) 69 70 typedef long code_int; 71 typedef long count_int; 72 typedef u_char char_type; 73 74 static char_type magic_header[] = 75 {'\037', '\235'}; /* 1F 9D */ 76 77 static char_type rmask[9] = 78 {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff}; 79 80 /* XXX zuncompress global */ 81 off_t total_compressed_bytes; 82 size_t compressed_prelen; 83 char *compressed_pre; 84 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. */ 99 /* 100 * Block compression parameters -- after all codes are used up, 101 * and compression rate changes, start over. 102 */ 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; 127 }; 128 129 static code_int getcode(struct s_zstate *zs); 130 131 static off_t 132 zuncompress(FILE *in, FILE *out, char *pre, size_t prelen, 133 off_t *compressed_bytes) 134 { 135 off_t bin, bout = 0; 136 char *buf; 137 138 buf = malloc(BUFSIZE); 139 if (buf == NULL) 140 return -1; 141 142 /* XXX */ 143 compressed_prelen = prelen; 144 if (prelen != 0) 145 compressed_pre = pre; 146 else 147 compressed_pre = NULL; 148 149 while ((bin = fread(buf, 1, sizeof(buf), in)) != 0) { 150 if (tflag == 0 && (off_t)fwrite(buf, 1, bin, out) != bin) { 151 free(buf); 152 return -1; 153 } 154 bout += bin; 155 } 156 157 if (compressed_bytes) 158 *compressed_bytes = total_compressed_bytes; 159 160 free(buf); 161 return bout; 162 } 163 164 static int 165 zclose(void *zs) 166 { 167 free(zs); 168 /* We leave the caller to close the fd passed to zdopen() */ 169 return 0; 170 } 171 172 FILE * 173 zdopen(int fd) 174 { 175 struct s_zstate *zs; 176 177 if ((zs = calloc(1, sizeof(struct s_zstate))) == NULL) 178 return (NULL); 179 180 zs->zs_state = S_START; 181 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; 193 194 /* 195 * Layering compress on top of stdio in order to provide buffering, 196 * and ensure that reads and write work with the data specified. 197 */ 198 if ((zs->zs_fp = fdopen(fd, "r")) == NULL) { 199 free(zs); 200 return NULL; 201 } 202 203 return funopen(zs, zread, NULL, NULL, zclose); 204 } 205 206 /* 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. 211 */ 212 static int 213 zread(void *cookie, char *rbp, int num) 214 { 215 u_int count, i; 216 struct s_zstate *zs; 217 u_char *bp, header[3]; 218 219 if (num == 0) 220 return (0); 221 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; 233 } 234 235 /* Check the magic number */ 236 for (i = 0; i < 3 && compressed_prelen; i++, compressed_prelen--) 237 header[i] = *compressed_pre++; 238 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); 244 } 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); 253 } 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; 259 } 260 zs->zs_free_ent = zs->zs_block_compress ? FIRST : 256; 261 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 */ 265 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; 270 271 while ((zs->u.r.zs_code = getcode(zs)) > -1) { 272 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; 281 } 282 zs->u.r.zs_incode = zs->u.r.zs_code; 283 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; 288 } 289 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); 294 } 295 *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar = tab_suffixof(zs->u.r.zs_code); 296 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); 303 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; 309 } 310 311 /* Remember previous code. */ 312 zs->u.r.zs_oldcode = zs->u.r.zs_incode; 313 } 314 zs->zs_state = S_EOF; 315 eof: return (num - count); 316 } 317 318 /*- 319 * Read one code from the standard input. If EOF, return -1. 320 * Inputs: 321 * stdin 322 * Outputs: 323 * code or -1 is returned. 324 */ 325 static code_int 326 getcode(struct s_zstate *zs) 327 { 328 code_int gcode; 329 int r_off, bits, i; 330 char_type *bp; 331 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) { 335 /* 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. 339 */ 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); 346 } 347 if (zs->zs_clear_flg > 0) { 348 zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS); 349 zs->zs_clear_flg = 0; 350 } 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; 359 360 total_compressed_bytes += zs->u.r.zs_size; 361 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); 364 } 365 r_off = zs->u.r.zs_roffset; 366 bits = zs->zs_n_bits; 367 368 /* Get to the first byte. */ 369 bp += (r_off >> 3); 370 r_off &= 7; 371 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. */ 376 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; 382 } 383 384 /* High order bits. */ 385 gcode |= (*bp & rmask[bits]) << r_off; 386 zs->u.r.zs_roffset += zs->zs_n_bits; 387 388 return (gcode); 389 } 390