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