1 /* $NetBSD: zuncompress.c,v 1.4 2004/05/25 04:34:40 mrg 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 paramenters */ 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 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[BUFSIZE]; 136 137 /* XXX */ 138 compressed_prelen = prelen; 139 if (prelen != 0) 140 compressed_pre = pre; 141 else 142 compressed_pre = NULL; 143 144 while ((bin = fread(buf, 1, sizeof(buf), in)) != 0) { 145 if (fwrite(buf, 1, bin, out) != bin) 146 return -1; 147 bout += bin; 148 } 149 150 if (compressed_bytes) 151 *compressed_bytes = total_compressed_bytes; 152 153 return bout; 154 } 155 156 FILE * 157 zopen(const char *fname, FILE *preopen) 158 { 159 struct s_zstate *zs; 160 161 if ((zs = calloc(1, sizeof(struct s_zstate))) == NULL) 162 return (NULL); 163 164 zs->zs_state = S_START; 165 166 /* XXX we can get rid of some of these */ 167 zs->zs_hsize = HSIZE; /* For dynamic table sizing. */ 168 zs->zs_free_ent = 0; /* First unused entry. */ 169 zs->zs_block_compress = BLOCK_MASK; 170 zs->zs_clear_flg = 0; /* XXX we calloc()'d this structure why = 0? */ 171 zs->zs_ratio = 0; 172 zs->zs_checkpoint = CHECK_GAP; 173 zs->zs_in_count = 1; /* Length of input. */ 174 zs->zs_out_count = 0; /* # of codes output (for debugging). */ 175 zs->u.r.zs_roffset = 0; 176 zs->u.r.zs_size = 0; 177 178 /* 179 * Layering compress on top of stdio in order to provide buffering, 180 * and ensure that reads and write work with the data specified. 181 */ 182 if ((zs->zs_fp = preopen) == NULL && 183 (zs->zs_fp = fopen(fname, "r")) == NULL) { 184 free(zs); 185 return NULL; 186 } 187 188 return fropen(zs, zread); 189 } 190 191 /* 192 * Decompress read. This routine adapts to the codes in the file building 193 * the "string" table on-the-fly; requiring no table to be stored in the 194 * compressed file. The tables used herein are shared with those of the 195 * compress() routine. See the definitions above. 196 */ 197 static int 198 zread(void *cookie, char *rbp, int num) 199 { 200 u_int count, i; 201 struct s_zstate *zs; 202 u_char *bp, header[3]; 203 204 if (num == 0) 205 return (0); 206 207 zs = cookie; 208 count = num; 209 bp = (u_char *)rbp; 210 switch (zs->zs_state) { 211 case S_START: 212 zs->zs_state = S_MIDDLE; 213 break; 214 case S_MIDDLE: 215 goto middle; 216 case S_EOF: 217 goto eof; 218 } 219 220 /* Check the magic number */ 221 for (i = 0; i < 3 && compressed_prelen; i++, compressed_prelen--) 222 header[i] = *compressed_pre++; 223 224 if (fread(header + i, 1, sizeof(header) - i, zs->zs_fp) != 225 sizeof(header) - i || 226 memcmp(header, magic_header, sizeof(magic_header)) != 0) { 227 errno = EFTYPE; 228 return (-1); 229 } 230 total_compressed_bytes = 0; 231 zs->zs_maxbits = header[2]; /* Set -b from file. */ 232 zs->zs_block_compress = zs->zs_maxbits & BLOCK_MASK; 233 zs->zs_maxbits &= BIT_MASK; 234 zs->zs_maxmaxcode = 1L << zs->zs_maxbits; 235 if (zs->zs_maxbits > BITS) { 236 errno = EFTYPE; 237 return (-1); 238 } 239 /* As above, initialize the first 256 entries in the table. */ 240 zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS); 241 for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0; zs->u.r.zs_code--) { 242 tab_prefixof(zs->u.r.zs_code) = 0; 243 tab_suffixof(zs->u.r.zs_code) = (char_type) zs->u.r.zs_code; 244 } 245 zs->zs_free_ent = zs->zs_block_compress ? FIRST : 256; 246 247 zs->u.r.zs_finchar = zs->u.r.zs_oldcode = getcode(zs); 248 if (zs->u.r.zs_oldcode == -1) /* EOF already? */ 249 return (0); /* Get out of here */ 250 251 /* First code must be 8 bits = char. */ 252 *bp++ = (u_char)zs->u.r.zs_finchar; 253 count--; 254 zs->u.r.zs_stackp = de_stack; 255 256 while ((zs->u.r.zs_code = getcode(zs)) > -1) { 257 258 if ((zs->u.r.zs_code == CLEAR) && zs->zs_block_compress) { 259 for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0; 260 zs->u.r.zs_code--) 261 tab_prefixof(zs->u.r.zs_code) = 0; 262 zs->zs_clear_flg = 1; 263 zs->zs_free_ent = FIRST - 1; 264 if ((zs->u.r.zs_code = getcode(zs)) == -1) /* O, untimely death! */ 265 break; 266 } 267 zs->u.r.zs_incode = zs->u.r.zs_code; 268 269 /* Special case for KwKwK string. */ 270 if (zs->u.r.zs_code >= zs->zs_free_ent) { 271 *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar; 272 zs->u.r.zs_code = zs->u.r.zs_oldcode; 273 } 274 275 /* Generate output characters in reverse order. */ 276 while (zs->u.r.zs_code >= 256) { 277 *zs->u.r.zs_stackp++ = tab_suffixof(zs->u.r.zs_code); 278 zs->u.r.zs_code = tab_prefixof(zs->u.r.zs_code); 279 } 280 *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar = tab_suffixof(zs->u.r.zs_code); 281 282 /* And put them out in forward order. */ 283 middle: do { 284 if (count-- == 0) 285 return (num); 286 *bp++ = *--zs->u.r.zs_stackp; 287 } while (zs->u.r.zs_stackp > de_stack); 288 289 /* Generate the new entry. */ 290 if ((zs->u.r.zs_code = zs->zs_free_ent) < zs->zs_maxmaxcode) { 291 tab_prefixof(zs->u.r.zs_code) = (u_short) zs->u.r.zs_oldcode; 292 tab_suffixof(zs->u.r.zs_code) = zs->u.r.zs_finchar; 293 zs->zs_free_ent = zs->u.r.zs_code + 1; 294 } 295 296 /* Remember previous code. */ 297 zs->u.r.zs_oldcode = zs->u.r.zs_incode; 298 } 299 zs->zs_state = S_EOF; 300 eof: return (num - count); 301 } 302 303 /*- 304 * Read one code from the standard input. If EOF, return -1. 305 * Inputs: 306 * stdin 307 * Outputs: 308 * code or -1 is returned. 309 */ 310 static code_int 311 getcode(struct s_zstate *zs) 312 { 313 code_int gcode; 314 int r_off, bits, i; 315 char_type *bp; 316 317 bp = zs->u.r.zs_gbuf; 318 if (zs->zs_clear_flg > 0 || zs->u.r.zs_roffset >= zs->u.r.zs_size || 319 zs->zs_free_ent > zs->zs_maxcode) { 320 /* 321 * If the next entry will be too big for the current gcode 322 * size, then we must increase the size. This implies reading 323 * a new buffer full, too. 324 */ 325 if (zs->zs_free_ent > zs->zs_maxcode) { 326 zs->zs_n_bits++; 327 if (zs->zs_n_bits == zs->zs_maxbits) /* Won't get any bigger now. */ 328 zs->zs_maxcode = zs->zs_maxmaxcode; 329 else 330 zs->zs_maxcode = MAXCODE(zs->zs_n_bits); 331 } 332 if (zs->zs_clear_flg > 0) { 333 zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS); 334 zs->zs_clear_flg = 0; 335 } 336 /* XXX */ 337 for (i = 0; i < zs->zs_n_bits && compressed_prelen; i++, compressed_prelen--) 338 zs->u.r.zs_gbuf[i] = *compressed_pre++; 339 zs->u.r.zs_size = fread(zs->u.r.zs_gbuf + i, 1, zs->zs_n_bits - i, zs->zs_fp); 340 zs->u.r.zs_size += i; 341 if (zs->u.r.zs_size <= 0) /* End of file. */ 342 return (-1); 343 zs->u.r.zs_roffset = 0; 344 345 total_compressed_bytes += zs->u.r.zs_size; 346 347 /* Round size down to integral number of codes. */ 348 zs->u.r.zs_size = (zs->u.r.zs_size << 3) - (zs->zs_n_bits - 1); 349 } 350 r_off = zs->u.r.zs_roffset; 351 bits = zs->zs_n_bits; 352 353 /* Get to the first byte. */ 354 bp += (r_off >> 3); 355 r_off &= 7; 356 357 /* Get first part (low order bits). */ 358 gcode = (*bp++ >> r_off); 359 bits -= (8 - r_off); 360 r_off = 8 - r_off; /* Now, roffset into gcode word. */ 361 362 /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ 363 if (bits >= 8) { 364 gcode |= *bp++ << r_off; 365 r_off += 8; 366 bits -= 8; 367 } 368 369 /* High order bits. */ 370 gcode |= (*bp & rmask[bits]) << r_off; 371 zs->u.r.zs_roffset += zs->zs_n_bits; 372 373 return (gcode); 374 } 375