usr.bin/gzip/unpack.c

   1 /*      $FreeBSD: head/usr.bin/gzip/unpack.c 194579 2009-06-21 09:39:43Z delphij $      */
   2 /*      $NetBSD$        */
   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
  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 coresponding 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 similiar 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  * Release resource allocated to an unpack descriptor.
  92  *
  93  * Caller is responsible to make sure that all of these pointers are
  94  * initialized (in our case, they all point to valid memory block).
  95  * We don't zero out pointers here because nobody else would ever
  96  * reference the memory block without scrubing them.
  97  */
  98 static void
  99 unpack_descriptor_fini(unpack_descriptor_t *unpackd)
 100 {
 101
 102         free(unpackd->symbolsin);
 103         free(unpackd->inodesin);
 104         free(unpackd->symbol);
 105         free(unpackd->tree);
 106
 107         fclose(unpackd->fpIn);
 108         fclose(unpackd->fpOut);
 109 }
 110
 111 /*
 112  * Recursively fill the internal node count table
 113  */
 114 static void
 115 unpackd_fill_inodesin(const unpack_descriptor_t *unpackd, int level)
 116 {
 117
 118         /*
 119          * The internal nodes would be 1/2 of total internal nodes and
 120          * leaf nodes in the next level.  For the last level there
 121          * would be no internal node by defination.
 122          */
 123         if (level < unpackd->treelevels) {
 124                 unpackd_fill_inodesin(unpackd, level + 1);
 125                 unpackd->inodesin[level] = (unpackd->inodesin[level + 1] +
 126                                           unpackd->symbolsin[level + 1]) / 2;
 127         } else
 128                 unpackd->inodesin[level] = 0;
 129 }
 130
 131 /*
 132  * Update counter for accepted bytes
 133  */
 134 static void
 135 accepted_bytes(off_t *bytes_in, off_t newbytes)
 136 {
 137
 138         if (bytes_in != NULL)
 139                 (*bytes_in) += newbytes;
 140 }
 141
 142 /*
 143  * Read file header and construct the tree.  Also, prepare the buffered I/O
 144  * for decode rountine.
 145  *
 146  * Return value is uncompressed size.
 147  */
 148 static void
 149 unpack_parse_header(int in, int out, char *pre, size_t prelen, off_t *bytes_in,
 150     unpack_descriptor_t *unpackd)
 151 {
 152         unsigned char hdr[PACK_HEADER_LENGTH];  /* buffer for header */
 153         ssize_t bytesread;              /* Bytes read from the file */
 154         int i, j, thisbyte;
 155
 156         /* Prepend the header buffer if we already read some data */
 157         if (prelen != 0)
 158                 memcpy(hdr, pre, prelen);
 159
 160         /* Read in and fill the rest bytes of header */
 161         bytesread = read(in, hdr + prelen, PACK_HEADER_LENGTH - prelen);
 162         if (bytesread < 0)
 163                 maybe_err("Error reading pack header");
 164
 165         accepted_bytes(bytes_in, PACK_HEADER_LENGTH);
 166
 167         /* Obtain uncompressed length (bytes 2,3,4,5)*/
 168         unpackd->uncompressed_size = 0;
 169         for (i = 2; i <= 5; i++) {
 170                 unpackd->uncompressed_size <<= 8;
 171                 unpackd->uncompressed_size |= hdr[i];
 172         }
 173
 174         /* Get the levels of the tree */
 175         unpackd->treelevels = hdr[6];
 176         if (unpackd->treelevels > HTREE_MAXLEVEL || unpackd->treelevels < 1)
 177                 maybe_errx("Huffman tree has insane levels");
 178
 179         /* Let libc take care for buffering from now on */
 180         if ((unpackd->fpIn = fdopen(in, "r")) == NULL)
 181                 maybe_err("Can not fdopen() input stream");
 182         if ((unpackd->fpOut = fdopen(out, "w")) == NULL)
 183                 maybe_err("Can not fdopen() output stream");
 184
 185         /* Allocate for the tables of bounds and the tree itself */
 186         unpackd->inodesin =
 187             calloc(unpackd->treelevels, sizeof(*(unpackd->inodesin)));
 188         unpackd->symbolsin =
 189             calloc(unpackd->treelevels, sizeof(*(unpackd->symbolsin)));
 190         unpackd->tree =
 191             calloc(unpackd->treelevels, (sizeof (*(unpackd->tree))));
 192         if (unpackd->inodesin == NULL || unpackd->symbolsin == NULL ||
 193             unpackd->tree == NULL)
 194                 maybe_err("calloc");
 195
 196         /* We count from 0 so adjust to match array upper bound */
 197         unpackd->treelevels--;
 198
 199         /* Read the levels symbol count table and caculate total */
 200         unpackd->symbol_size = 1;               /* EOB */
 201         for (i = 0; i <= unpackd->treelevels; i++) {
 202                 if ((thisbyte = fgetc(unpackd->fpIn)) == EOF)
 203                         maybe_err("File appears to be truncated");
 204                 unpackd->symbolsin[i] = (unsigned char)thisbyte;
 205                 unpackd->symbol_size += unpackd->symbolsin[i];
 206         }
 207         accepted_bytes(bytes_in, unpackd->treelevels);
 208         if (unpackd->symbol_size > 256)
 209                 maybe_errx("Bad symbol table");
 210
 211         /* Allocate for the symbol table, point symbol_eob at the beginning */
 212         unpackd->symbol_eob = unpackd->symbol = calloc(1, unpackd->symbol_size);
 213         if (unpackd->symbol == NULL)
 214                 maybe_err("calloc");
 215
 216         /*
 217          * Read in the symbol table, which contain [2, 256] symbols.
 218          * In order to fit the count in one byte, pack(1) would offset
 219          * it by reducing 2 from the actual number from the last level.
 220          *
 221          * We adjust the last level's symbol count by 1 here, because
 222          * the EOB symbol is not being transmitted explicitly.  Another
 223          * adjustment would be done later afterward.
 224          */
 225         unpackd->symbolsin[unpackd->treelevels]++;
 226         for (i = 0; i <= unpackd->treelevels; i++) {
 227                 unpackd->tree[i] = unpackd->symbol_eob;
 228                 for (j = 0; j < unpackd->symbolsin[i]; j++) {
 229                         if ((thisbyte = fgetc(unpackd->fpIn)) == EOF)
 230                                 maybe_errx("Symbol table truncated");
 231                         *unpackd->symbol_eob++ = (char)thisbyte;
 232                 }
 233                 accepted_bytes(bytes_in, unpackd->symbolsin[i]);
 234         }
 235
 236         /* Now, take account for the EOB symbol as well */
 237         unpackd->symbolsin[unpackd->treelevels]++;
 238
 239         /*
 240          * The symbolsin table has been constructed now.
 241          * Caculate the internal nodes count table based on it.
 242          */
 243         unpackd_fill_inodesin(unpackd, 0);
 244 }
 245
 246 /*
 247  * Decode huffman stream, based on the huffman tree.
 248  */
 249 static void
 250 unpack_decode(const unpack_descriptor_t *unpackd, off_t *bytes_in)
 251 {
 252         int thislevel, thiscode, thisbyte, inlevelindex;
 253         int i;
 254         off_t bytes_out = 0;
 255         const char *thissymbol; /* The symbol pointer decoded from stream */
 256
 257         /*
 258          * Decode huffman.  Fetch every bytes from the file, get it
 259          * into 'thiscode' bit-by-bit, then output the symbol we got
 260          * when one has been found.
 261          *
 262          * Assumption: sizeof(int) > ((max tree levels + 1) / 8).
 263          * bad things could happen if not.
 264          */
 265         thislevel = 0;
 266         thiscode = thisbyte = 0;
 267
 268         while ((thisbyte = fgetc(unpackd->fpIn)) != EOF) {
 269                 accepted_bytes(bytes_in, 1);
 270
 271                 /*
 272                  * Split one bit from thisbyte, from highest to lowest,
 273                  * feed the bit into thiscode, until we got a symbol from
 274                  * the tree.
 275                  */
 276                 for (i = 7; i >= 0; i--) {
 277                         thiscode = (thiscode << 1) | ((thisbyte >> i) & 1);
 278
 279                         /* Did we got a symbol? (referencing leaf node) */
 280                         if (thiscode >= unpackd->inodesin[thislevel]) {
 281                                 inlevelindex =
 282                                     thiscode - unpackd->inodesin[thislevel];
 283                                 if (inlevelindex > unpackd->symbolsin[thislevel])
 284                                         maybe_errx("File corrupt");
 285
 286                                 thissymbol =
 287                                     &(unpackd->tree[thislevel][inlevelindex]);
 288                                 if ((thissymbol == unpackd->symbol_eob) &&
 289                                     (bytes_out == unpackd->uncompressed_size))
 290                                         goto finished;
 291
 292                                 fputc((*thissymbol), unpackd->fpOut);
 293                                 bytes_out++;
 294
 295                                 /* Prepare for next input */
 296                                 thislevel = 0; thiscode = 0;
 297                         } else {
 298                                 thislevel++;
 299                                 if (thislevel > unpackd->treelevels)
 300                                         maybe_errx("File corrupt");
 301                         }
 302                 }
 303         }
 304
 305 finished:
 306         if (bytes_out != unpackd->uncompressed_size)
 307                 maybe_errx("Premature EOF");
 308 }
 309
 310 /* Handler for pack(1)'ed file */
 311 static off_t
 312 unpack(int in, int out, char *pre, size_t prelen, off_t *bytes_in)
 313 {
 314         unpack_descriptor_t     unpackd;
 315
 316         unpack_parse_header(dup(in), dup(out), pre, prelen, bytes_in, &unpackd);
 317         unpack_decode(&unpackd, bytes_in);
 318         unpack_descriptor_fini(&unpackd);
 319
 320         /* If we reached here, the unpack was successful */
 321         return (unpackd.uncompressed_size);
 322 }
 323