1 /* $FreeBSD: head/usr.bin/gzip/unpack.c 194579 2009-06-21 09:39:43Z delphij $ */ 2 /* $NetBSD: unpack.c,v 1.6 2026/01/10 00:48:44 mrg Exp $ */ 3 4 /*- 5 * Copyright (c) 2009 Xin LI <delphij (at) FreeBSD.org> 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 /* This file is #included by gzip.c */ 31 32 /* 33 * pack(1) file format: 34 * 35 * The first 7 bytes is the header: 36 * 00, 01 - Signature (US, RS), we already validated it earlier. 37 * 02..05 - Uncompressed size 38 * 06 - Level for the huffman tree (<=24) 39 * 40 * pack(1) will then store symbols (leaf) nodes count in each huffman 41 * tree levels, each level would consume 1 byte (See [1]). 42 * 43 * After the symbol count table, there is the symbol table, storing 44 * symbols represented by corresponding leaf node. EOB is not being 45 * explicitly transmitted (not necessary anyway) in the symbol table. 46 * 47 * Compressed data goes after the symbol table. 48 * 49 * NOTES 50 * 51 * [1] If we count EOB into the symbols, that would mean that we will 52 * have at most 256 symbols in the huffman tree. pack(1) rejects empty 53 * file and files that just repeats one character, which means that we 54 * will have at least 2 symbols. Therefore, pack(1) would reduce the 55 * last level symbol count by 2 which makes it a number in 56 * range [0..254], so all levels' symbol count would fit into 1 byte. 57 */ 58 59 #define PACK_HEADER_LENGTH 7 60 #define HTREE_MAXLEVEL 24 61 62 /* 63 * unpack descriptor 64 * 65 * Represent the huffman tree in a similar way that pack(1) would 66 * store in a packed file. We store all symbols in a linear table, 67 * and store pointers to each level's first symbol. In addition to 68 * that, maintain two counts for each level: inner nodes count and 69 * leaf nodes count. 70 */ 71 typedef struct { 72 int symbol_size; /* Size of the symbol table */ 73 int treelevels; /* Levels for the huffman tree */ 74 75 int *symbolsin; /* Table of leaf symbols count in 76 each level */ 77 int *inodesin; /* Table of internal nodes count in 78 each level */ 79 80 char *symbol; /* The symbol table */ 81 char *symbol_eob; /* Pointer to the EOB symbol */ 82 char **tree; /* Decoding huffman tree (pointers to 83 first symbol of each tree level */ 84 85 off_t uncompressed_size; /* Uncompressed size */ 86 FILE *fpIn; /* Input stream */ 87 FILE *fpOut; /* Output stream */ 88 } unpack_descriptor_t; 89 90 91 /* 92 * Simple wrapper around fgetc() to read the compressed data, that handles 93 * reading from the pre buffer. 94 * 95 * The pre/prelen are not part of unpack_descriptor_t{} as it is passed as 96 * const in one of the two callers. 97 */ 98 static int 99 unpack_fgetc_in(const unpack_descriptor_t *unpackd, 100 char **pre, size_t *prelen) 101 { 102 103 if (*prelen) { 104 (*prelen)--; 105 return (unsigned char)*((*pre)++); 106 } 107 return fgetc(unpackd->fpIn); 108 } 109 110 /* 111 * Release resource allocated to an unpack descriptor. 112 * 113 * Caller is responsible to make sure that all of these pointers are 114 * initialized (in our case, they all point to valid memory block). 115 * We don't zero out pointers here because nobody else would ever 116 * reference the memory block without scrubbing them. 117 */ 118 static void 119 unpack_descriptor_fini(unpack_descriptor_t *unpackd) 120 { 121 122 free(unpackd->symbolsin); 123 free(unpackd->inodesin); 124 free(unpackd->symbol); 125 free(unpackd->tree); 126 127 fclose(unpackd->fpIn); 128 fclose(unpackd->fpOut); 129 } 130 131 /* 132 * Recursively fill the internal node count table 133 */ 134 static void 135 unpackd_fill_inodesin(const unpack_descriptor_t *unpackd, int level) 136 { 137 138 /* 139 * The internal nodes would be 1/2 of total internal nodes and 140 * leaf nodes in the next level. For the last level there 141 * would be no internal node by definition. 142 */ 143 if (level < unpackd->treelevels) { 144 unpackd_fill_inodesin(unpackd, level + 1); 145 unpackd->inodesin[level] = (unpackd->inodesin[level + 1] + 146 unpackd->symbolsin[level + 1]) / 2; 147 } else 148 unpackd->inodesin[level] = 0; 149 } 150 151 /* 152 * Update counter for accepted bytes 153 */ 154 static void 155 accepted_bytes(off_t *bytes_in, off_t newbytes) 156 { 157 158 if (bytes_in != NULL) 159 (*bytes_in) += newbytes; 160 } 161 162 /* 163 * Read file header and construct the tree. Also, prepare the buffered I/O 164 * for decode routine. 165 * 166 * Return value is uncompressed size. 167 */ 168 static void 169 unpack_parse_header(int in, int out, char **pre, size_t *prelen, off_t *bytes_in, 170 unpack_descriptor_t *unpackd) 171 { 172 unsigned char hdr[PACK_HEADER_LENGTH]; /* buffer for header */ 173 ssize_t bytesread; /* Bytes read from the file */ 174 int i, j, thisbyte; 175 size_t copysize = 0; 176 177 /* Prepend the header buffer if we already read some data */ 178 if (*prelen != 0) { 179 copysize = MIN(*prelen, sizeof hdr); 180 memcpy(hdr, *pre, copysize); 181 (*pre) += copysize; 182 (*prelen) -= copysize; 183 if (*prelen == 0) 184 *pre = NULL; 185 } 186 187 /* Read in and fill the rest bytes of header */ 188 if (copysize < sizeof hdr) { 189 bytesread = read(in, hdr + copysize, PACK_HEADER_LENGTH - copysize); 190 if (bytesread < 0) 191 maybe_err("Error reading pack header"); 192 infile_newdata(bytesread); 193 } 194 195 accepted_bytes(bytes_in, PACK_HEADER_LENGTH); 196 197 /* Obtain uncompressed length (bytes 2,3,4,5)*/ 198 unpackd->uncompressed_size = 0; 199 for (i = 2; i <= 5; i++) { 200 unpackd->uncompressed_size <<= 8; 201 unpackd->uncompressed_size |= hdr[i]; 202 } 203 204 /* Get the levels of the tree */ 205 unpackd->treelevels = hdr[6]; 206 if (unpackd->treelevels > HTREE_MAXLEVEL || unpackd->treelevels < 1) 207 maybe_errx("Huffman tree has insane levels"); 208 209 /* Let libc take care for buffering from now on */ 210 if ((unpackd->fpIn = fdopen(in, "r")) == NULL) 211 maybe_err("Can not fdopen() input stream"); 212 if ((unpackd->fpOut = fdopen(out, "w")) == NULL) 213 maybe_err("Can not fdopen() output stream"); 214 215 /* Allocate for the tables of bounds and the tree itself */ 216 unpackd->inodesin = 217 calloc(unpackd->treelevels, sizeof(*(unpackd->inodesin))); 218 unpackd->symbolsin = 219 calloc(unpackd->treelevels, sizeof(*(unpackd->symbolsin))); 220 unpackd->tree = 221 calloc(unpackd->treelevels, (sizeof (*(unpackd->tree)))); 222 if (unpackd->inodesin == NULL || unpackd->symbolsin == NULL || 223 unpackd->tree == NULL) 224 maybe_err("calloc"); 225 226 /* We count from 0 so adjust to match array upper bound */ 227 unpackd->treelevels--; 228 229 /* Read the levels symbol count table and calculate total */ 230 unpackd->symbol_size = 1; /* EOB */ 231 for (i = 0; i <= unpackd->treelevels; i++) { 232 if ((thisbyte = unpack_fgetc_in(unpackd, pre, prelen)) == EOF) 233 maybe_err("File appears to be truncated"); 234 unpackd->symbolsin[i] = (unsigned char)thisbyte; 235 unpackd->symbol_size += unpackd->symbolsin[i]; 236 } 237 accepted_bytes(bytes_in, unpackd->treelevels); 238 if (unpackd->symbol_size > 256) 239 maybe_errx("Bad symbol table"); 240 infile_newdata(unpackd->treelevels); 241 242 /* Allocate for the symbol table, point symbol_eob at the beginning */ 243 unpackd->symbol_eob = unpackd->symbol = calloc(1, unpackd->symbol_size); 244 if (unpackd->symbol == NULL) 245 maybe_err("calloc"); 246 247 /* 248 * Read in the symbol table, which contain [2, 256] symbols. 249 * In order to fit the count in one byte, pack(1) would offset 250 * it by reducing 2 from the actual number from the last level. 251 * 252 * We adjust the last level's symbol count by 1 here, because 253 * the EOB symbol is not being transmitted explicitly. Another 254 * adjustment would be done later afterward. 255 */ 256 unpackd->symbolsin[unpackd->treelevels]++; 257 for (i = 0; i <= unpackd->treelevels; i++) { 258 unpackd->tree[i] = unpackd->symbol_eob; 259 for (j = 0; j < unpackd->symbolsin[i]; j++) { 260 thisbyte = unpack_fgetc_in(unpackd, pre, prelen); 261 if (thisbyte == EOF) 262 maybe_errx("Symbol table truncated"); 263 *unpackd->symbol_eob++ = (char)thisbyte; 264 } 265 infile_newdata(unpackd->symbolsin[i]); 266 accepted_bytes(bytes_in, unpackd->symbolsin[i]); 267 } 268 269 /* Now, take account for the EOB symbol as well */ 270 unpackd->symbolsin[unpackd->treelevels]++; 271 272 /* 273 * The symbolsin table has been constructed now. 274 * Calculate the internal nodes count table based on it. 275 */ 276 unpackd_fill_inodesin(unpackd, 0); 277 } 278 279 /* 280 * Decode huffman stream, based on the huffman tree. 281 */ 282 static void 283 unpack_decode(const unpack_descriptor_t *unpackd, char *pre, size_t prelen, 284 off_t *bytes_in) 285 { 286 int thislevel, thiscode, thisbyte, inlevelindex; 287 int i; 288 off_t bytes_out = 0; 289 const char *thissymbol; /* The symbol pointer decoded from stream */ 290 291 /* 292 * Decode huffman. Fetch every bytes from the file, get it 293 * into 'thiscode' bit-by-bit, then output the symbol we got 294 * when one has been found. 295 * 296 * Assumption: sizeof(int) > ((max tree levels + 1) / 8). 297 * bad things could happen if not. 298 */ 299 thislevel = 0; 300 thiscode = thisbyte = 0; 301 302 while ((thisbyte = unpack_fgetc_in(unpackd, &pre, &prelen)) != EOF) { 303 accepted_bytes(bytes_in, 1); 304 infile_newdata(1); 305 check_siginfo(); 306 307 /* 308 * Split one bit from thisbyte, from highest to lowest, 309 * feed the bit into thiscode, until we got a symbol from 310 * the tree. 311 */ 312 for (i = 7; i >= 0; i--) { 313 thiscode = (thiscode << 1) | ((thisbyte >> i) & 1); 314 315 /* Did we got a symbol? (referencing leaf node) */ 316 if (thiscode >= unpackd->inodesin[thislevel]) { 317 inlevelindex = 318 thiscode - unpackd->inodesin[thislevel]; 319 if (inlevelindex > unpackd->symbolsin[thislevel]) 320 maybe_errx("File corrupt"); 321 322 thissymbol = 323 &(unpackd->tree[thislevel][inlevelindex]); 324 if ((thissymbol == unpackd->symbol_eob) && 325 (bytes_out == unpackd->uncompressed_size)) 326 goto finished; 327 328 if (!tflag) 329 fputc((*thissymbol), unpackd->fpOut); 330 bytes_out++; 331 332 /* Prepare for next input */ 333 thislevel = 0; thiscode = 0; 334 } else { 335 thislevel++; 336 if (thislevel > unpackd->treelevels) 337 maybe_errx("File corrupt"); 338 } 339 } 340 } 341 342 finished: 343 if (bytes_out != unpackd->uncompressed_size) 344 maybe_errx("Premature EOF"); 345 } 346 347 /* Handler for pack(1)'ed file */ 348 static off_t 349 unpack(int in, int out, char *pre, size_t prelen, off_t *bytes_in) 350 { 351 unpack_descriptor_t unpackd; 352 353 unpack_parse_header(dup(in), dup(out), &pre, &prelen, bytes_in, &unpackd); 354 unpack_decode(&unpackd, pre, prelen, bytes_in); 355 unpack_descriptor_fini(&unpackd); 356 357 /* If we reached here, the unpack was successful */ 358 return (unpackd.uncompressed_size); 359 } 360 361
Indexes created Sun Oct 25 00:26:45 UTC 2026