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