1 /* $FreeBSD$ */ 2 /* $NetBSD: unpack.c,v 1.3 2017/08/04 07:27:08 mrg Exp $ */ 3 4 /*- 5 * Copyright (c) 2009 Xin LI <delphij@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 * $FreeBSD$ 30 */ 31 32 /* This file is #included by gzip.c */ 33 34 /* 35 * pack(1) file format: 36 * 37 * The first 7 bytes is the header: 38 * 00, 01 - Signature (US, RS), we already validated it earlier. 39 * 02..05 - Uncompressed size 40 * 06 - Level for the huffman tree (<=24) 41 * 42 * pack(1) will then store symbols (leaf) nodes count in each huffman 43 * tree levels, each level would consume 1 byte (See [1]). 44 * 45 * After the symbol count table, there is the symbol table, storing 46 * symbols represented by corresponding leaf node. EOB is not being 47 * explicitly transmitted (not necessary anyway) in the symbol table. 48 * 49 * Compressed data goes after the symbol table. 50 * 51 * NOTES 52 * 53 * [1] If we count EOB into the symbols, that would mean that we will 54 * have at most 256 symbols in the huffman tree. pack(1) rejects empty 55 * file and files that just repeats one character, which means that we 56 * will have at least 2 symbols. Therefore, pack(1) would reduce the 57 * last level symbol count by 2 which makes it a number in 58 * range [0..254], so all levels' symbol count would fit into 1 byte. 59 */ 60 61 #define PACK_HEADER_LENGTH 7 62 #define HTREE_MAXLEVEL 24 63 64 /* 65 * unpack descriptor 66 * 67 * Represent the huffman tree in a similar way that pack(1) would 68 * store in a packed file. We store all symbols in a linear table, 69 * and store pointers to each level's first symbol. In addition to 70 * that, maintain two counts for each level: inner nodes count and 71 * leaf nodes count. 72 */ 73 typedef struct { 74 int symbol_size; /* Size of the symbol table */ 75 int treelevels; /* Levels for the huffman tree */ 76 77 int *symbolsin; /* Table of leaf symbols count in each 78 * level */ 79 int *inodesin; /* Table of internal nodes count in 80 * each level */ 81 82 char *symbol; /* The symbol table */ 83 char *symbol_eob; /* Pointer to the EOB symbol */ 84 char **tree; /* Decoding huffman tree (pointers to 85 * first symbol of each tree level */ 86 87 off_t uncompressed_size; /* Uncompressed size */ 88 FILE *fpIn; /* Input stream */ 89 FILE *fpOut; /* Output stream */ 90 } unpack_descriptor_t; 91 92 /* 93 * Release resource allocated to an unpack descriptor. 94 * 95 * Caller is responsible to make sure that all of these pointers are 96 * initialized (in our case, they all point to valid memory block). 97 * We don't zero out pointers here because nobody else would ever 98 * reference the memory block without scrubbing them. 99 */ 100 static void 101 unpack_descriptor_fini(unpack_descriptor_t *unpackd) 102 { 103 104 free(unpackd->symbolsin); 105 free(unpackd->inodesin); 106 free(unpackd->symbol); 107 free(unpackd->tree); 108 109 fclose(unpackd->fpIn); 110 fclose(unpackd->fpOut); 111 } 112 113 /* 114 * Recursively fill the internal node count table 115 */ 116 static void 117 unpackd_fill_inodesin(const unpack_descriptor_t *unpackd, int level) 118 { 119 120 /* 121 * The internal nodes would be 1/2 of total internal nodes and 122 * leaf nodes in the next level. For the last level there 123 * would be no internal node by definition. 124 */ 125 if (level < unpackd->treelevels) { 126 unpackd_fill_inodesin(unpackd, level + 1); 127 unpackd->inodesin[level] = (unpackd->inodesin[level + 1] + 128 unpackd->symbolsin[level + 1]) / 2; 129 } else 130 unpackd->inodesin[level] = 0; 131 } 132 133 /* 134 * Update counter for accepted bytes 135 */ 136 static void 137 accepted_bytes(off_t *bytes_in, off_t newbytes) 138 { 139 140 if (bytes_in != NULL) 141 (*bytes_in) += newbytes; 142 } 143 144 /* 145 * Read file header and construct the tree. Also, prepare the buffered I/O 146 * for decode routine. 147 * 148 * Return value is uncompressed size. 149 */ 150 static void 151 unpack_parse_header(int in, int out, char *pre, size_t prelen, off_t *bytes_in, 152 unpack_descriptor_t *unpackd) 153 { 154 unsigned char hdr[PACK_HEADER_LENGTH]; /* buffer for header */ 155 ssize_t bytesread; /* Bytes read from the file */ 156 int i, j, thisbyte; 157 158 if (prelen > sizeof hdr) 159 maybe_err("prelen too long"); 160 161 /* Prepend the header buffer if we already read some data */ 162 if (prelen != 0) 163 memcpy(hdr, pre, prelen); 164 165 /* Read in and fill the rest bytes of header */ 166 bytesread = read(in, hdr + prelen, PACK_HEADER_LENGTH - prelen); 167 if (bytesread < 0) 168 maybe_err("Error reading pack header"); 169 infile_newdata(bytesread); 170 171 accepted_bytes(bytes_in, PACK_HEADER_LENGTH); 172 173 /* Obtain uncompressed length (bytes 2,3,4,5) */ 174 unpackd->uncompressed_size = 0; 175 for (i = 2; i <= 5; i++) { 176 unpackd->uncompressed_size <<= 8; 177 unpackd->uncompressed_size |= hdr[i]; 178 } 179 180 /* Get the levels of the tree */ 181 unpackd->treelevels = hdr[6]; 182 if (unpackd->treelevels > HTREE_MAXLEVEL || unpackd->treelevels < 1) 183 maybe_errx("Huffman tree has insane levels"); 184 185 /* Let libc take care for buffering from now on */ 186 if ((unpackd->fpIn = fdopen(in, "r")) == NULL) 187 maybe_err("Can not fdopen() input stream"); 188 if ((unpackd->fpOut = fdopen(out, "w")) == NULL) 189 maybe_err("Can not fdopen() output stream"); 190 191 /* Allocate for the tables of bounds and the tree itself */ 192 unpackd->inodesin = 193 calloc(unpackd->treelevels, sizeof(*(unpackd->inodesin))); 194 unpackd->symbolsin = 195 calloc(unpackd->treelevels, sizeof(*(unpackd->symbolsin))); 196 unpackd->tree = 197 calloc(unpackd->treelevels, (sizeof(*(unpackd->tree)))); 198 if (unpackd->inodesin == NULL || unpackd->symbolsin == NULL || 199 unpackd->tree == NULL) 200 maybe_err("calloc"); 201 202 /* We count from 0 so adjust to match array upper bound */ 203 unpackd->treelevels--; 204 205 /* Read the levels symbol count table and calculate total */ 206 unpackd->symbol_size = 1; /* EOB */ 207 for (i = 0; i <= unpackd->treelevels; i++) { 208 if ((thisbyte = fgetc(unpackd->fpIn)) == EOF) 209 maybe_err("File appears to be truncated"); 210 unpackd->symbolsin[i] = (unsigned char)thisbyte; 211 unpackd->symbol_size += unpackd->symbolsin[i]; 212 } 213 accepted_bytes(bytes_in, unpackd->treelevels); 214 if (unpackd->symbol_size > 256) 215 maybe_errx("Bad symbol table"); 216 infile_newdata(unpackd->treelevels); 217 218 /* Allocate for the symbol table, point symbol_eob at the beginning */ 219 unpackd->symbol_eob = unpackd->symbol = calloc(1, unpackd->symbol_size); 220 if (unpackd->symbol == NULL) 221 maybe_err("calloc"); 222 223 /* 224 * Read in the symbol table, which contain [2, 256] symbols. 225 * In order to fit the count in one byte, pack(1) would offset 226 * it by reducing 2 from the actual number from the last level. 227 * 228 * We adjust the last level's symbol count by 1 here, because 229 * the EOB symbol is not being transmitted explicitly. Another 230 * adjustment would be done later afterward. 231 */ 232 unpackd->symbolsin[unpackd->treelevels]++; 233 for (i = 0; i <= unpackd->treelevels; i++) { 234 unpackd->tree[i] = unpackd->symbol_eob; 235 for (j = 0; j < unpackd->symbolsin[i]; j++) { 236 if ((thisbyte = fgetc(unpackd->fpIn)) == EOF) 237 maybe_errx("Symbol table truncated"); 238 *unpackd->symbol_eob++ = (char)thisbyte; 239 } 240 infile_newdata(unpackd->symbolsin[i]); 241 accepted_bytes(bytes_in, unpackd->symbolsin[i]); 242 } 243 244 /* Now, take account for the EOB symbol as well */ 245 unpackd->symbolsin[unpackd->treelevels]++; 246 247 /* 248 * The symbolsin table has been constructed now. 249 * Calculate the internal nodes count table based on it. 250 */ 251 unpackd_fill_inodesin(unpackd, 0); 252 } 253 254 /* 255 * Decode huffman stream, based on the huffman tree. 256 */ 257 static void 258 unpack_decode(const unpack_descriptor_t *unpackd, off_t *bytes_in) 259 { 260 int thislevel, thiscode, thisbyte, inlevelindex; 261 int i; 262 off_t bytes_out = 0; 263 const char *thissymbol; /* The symbol pointer decoded from stream */ 264 265 /* 266 * Decode huffman. Fetch every bytes from the file, get it 267 * into 'thiscode' bit-by-bit, then output the symbol we got 268 * when one has been found. 269 * 270 * Assumption: sizeof(int) > ((max tree levels + 1) / 8). 271 * bad things could happen if not. 272 */ 273 thislevel = 0; 274 thiscode = thisbyte = 0; 275 276 while ((thisbyte = fgetc(unpackd->fpIn)) != EOF) { 277 accepted_bytes(bytes_in, 1); 278 infile_newdata(1); 279 check_siginfo(); 280 281 /* 282 * Split one bit from thisbyte, from highest to lowest, 283 * feed the bit into thiscode, until we got a symbol from 284 * the tree. 285 */ 286 for (i = 7; i >= 0; i--) { 287 thiscode = (thiscode << 1) | ((thisbyte >> i) & 1); 288 289 /* Did we got a symbol? (referencing leaf node) */ 290 if (thiscode >= unpackd->inodesin[thislevel]) { 291 inlevelindex = 292 thiscode - unpackd->inodesin[thislevel]; 293 if (inlevelindex > unpackd->symbolsin[thislevel]) 294 maybe_errx("File corrupt"); 295 296 thissymbol = 297 &(unpackd->tree[thislevel][inlevelindex]); 298 if ((thissymbol == unpackd->symbol_eob) && 299 (bytes_out == unpackd->uncompressed_size)) 300 goto finished; 301 302 fputc((*thissymbol), unpackd->fpOut); 303 bytes_out++; 304 305 /* Prepare for next input */ 306 thislevel = 0; thiscode = 0; 307 } else { 308 thislevel++; 309 if (thislevel > unpackd->treelevels) 310 maybe_errx("File corrupt"); 311 } 312 } 313 } 314 315 finished: 316 if (bytes_out != unpackd->uncompressed_size) 317 maybe_errx("Premature EOF"); 318 } 319 320 /* Handler for pack(1)'ed file */ 321 static off_t 322 unpack(int in, int out, char *pre, size_t prelen, off_t *bytes_in) 323 { 324 unpack_descriptor_t unpackd; 325 326 in = dup(in); 327 if (in == -1) 328 maybe_err("dup"); 329 out = dup(out); 330 if (out == -1) 331 maybe_err("dup"); 332 333 unpack_parse_header(in, out, pre, prelen, bytes_in, &unpackd); 334 unpack_decode(&unpackd, bytes_in); 335 unpack_descriptor_fini(&unpackd); 336 337 /* If we reached here, the unpack was successful */ 338 return (unpackd.uncompressed_size); 339 } 340