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