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