usr.bin/gzip/unpack.c

   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         /* Prepend the header buffer if we already read some data */
 160         if (prelen != 0)
 161                 memcpy(hdr, pre, prelen);
 162
 163         /* Read in and fill the rest bytes of header */
 164         bytesread = read(in, hdr + prelen, PACK_HEADER_LENGTH - prelen);
 165         if (bytesread < 0)
 166                 maybe_err("Error reading pack header");
 167         infile_newdata(bytesread);
 168
 169         accepted_bytes(bytes_in, PACK_HEADER_LENGTH);
 170
 171         /* Obtain uncompressed length (bytes 2,3,4,5) */
 172         unpackd->uncompressed_size = 0;
 173         for (i = 2; i <= 5; i++) {
 174                 unpackd->uncompressed_size <<= 8;
 175                 unpackd->uncompressed_size |= hdr[i];
 176         }
 177
 178         /* Get the levels of the tree */
 179         unpackd->treelevels = hdr[6];
 180         if (unpackd->treelevels > HTREE_MAXLEVEL || unpackd->treelevels < 1)
 181                 maybe_errx("Huffman tree has insane levels");
 182
 183         /* Let libc take care for buffering from now on */
 184         if ((unpackd->fpIn = fdopen(in, "r")) == NULL)
 185                 maybe_err("Can not fdopen() input stream");
 186         if ((unpackd->fpOut = fdopen(out, "w")) == NULL)
 187                 maybe_err("Can not fdopen() output stream");
 188
 189         /* Allocate for the tables of bounds and the tree itself */
 190         unpackd->inodesin =
 191             calloc(unpackd->treelevels, sizeof(*(unpackd->inodesin)));
 192         unpackd->symbolsin =
 193             calloc(unpackd->treelevels, sizeof(*(unpackd->symbolsin)));
 194         unpackd->tree =
 195             calloc(unpackd->treelevels, (sizeof(*(unpackd->tree))));
 196         if (unpackd->inodesin == NULL || unpackd->symbolsin == NULL ||
 197             unpackd->tree == NULL)
 198                 maybe_err("calloc");
 199
 200         /* We count from 0 so adjust to match array upper bound */
 201         unpackd->treelevels--;
 202
 203         /* Read the levels symbol count table and calculate total */
 204         unpackd->symbol_size = 1;       /* EOB */
 205         for (i = 0; i <= unpackd->treelevels; i++) {
 206                 if ((thisbyte = fgetc(unpackd->fpIn)) == EOF)
 207                         maybe_err("File appears to be truncated");
 208                 unpackd->symbolsin[i] = (unsigned char)thisbyte;
 209                 unpackd->symbol_size += unpackd->symbolsin[i];
 210         }
 211         accepted_bytes(bytes_in, unpackd->treelevels);
 212         if (unpackd->symbol_size > 256)
 213                 maybe_errx("Bad symbol table");
 214         infile_newdata(unpackd->treelevels);
 215
 216         /* Allocate for the symbol table, point symbol_eob at the beginning */
 217         unpackd->symbol_eob = unpackd->symbol = calloc(1, unpackd->symbol_size);
 218         if (unpackd->symbol == NULL)
 219                 maybe_err("calloc");
 220
 221         /*
 222          * Read in the symbol table, which contain [2, 256] symbols.
 223          * In order to fit the count in one byte, pack(1) would offset
 224          * it by reducing 2 from the actual number from the last level.
 225          *
 226          * We adjust the last level's symbol count by 1 here, because
 227          * the EOB symbol is not being transmitted explicitly.  Another
 228          * adjustment would be done later afterward.
 229          */
 230         unpackd->symbolsin[unpackd->treelevels]++;
 231         for (i = 0; i <= unpackd->treelevels; i++) {
 232                 unpackd->tree[i] = unpackd->symbol_eob;
 233                 for (j = 0; j < unpackd->symbolsin[i]; j++) {
 234                         if ((thisbyte = fgetc(unpackd->fpIn)) == EOF)
 235                                 maybe_errx("Symbol table truncated");
 236                         *unpackd->symbol_eob++ = (char)thisbyte;
 237                 }
 238                 infile_newdata(unpackd->symbolsin[i]);
 239                 accepted_bytes(bytes_in, unpackd->symbolsin[i]);
 240         }
 241
 242         /* Now, take account for the EOB symbol as well */
 243         unpackd->symbolsin[unpackd->treelevels]++;
 244
 245         /*
 246          * The symbolsin table has been constructed now.
 247          * Calculate the internal nodes count table based on it.
 248          */
 249         unpackd_fill_inodesin(unpackd, 0);
 250 }
 251
 252 /*
 253  * Decode huffman stream, based on the huffman tree.
 254  */
 255 static void
 256 unpack_decode(const unpack_descriptor_t *unpackd, off_t *bytes_in)
 257 {
 258         int thislevel, thiscode, thisbyte, inlevelindex;
 259         int i;
 260         off_t bytes_out = 0;
 261         const char *thissymbol; /* The symbol pointer decoded from stream */
 262
 263         /*
 264          * Decode huffman.  Fetch every bytes from the file, get it
 265          * into 'thiscode' bit-by-bit, then output the symbol we got
 266          * when one has been found.
 267          *
 268          * Assumption: sizeof(int) > ((max tree levels + 1) / 8).
 269          * bad things could happen if not.
 270          */
 271         thislevel = 0;
 272         thiscode = thisbyte = 0;
 273
 274         while ((thisbyte = fgetc(unpackd->fpIn)) != EOF) {
 275                 accepted_bytes(bytes_in, 1);
 276                 infile_newdata(1);
 277                 check_siginfo();
 278
 279                 /*
 280                  * Split one bit from thisbyte, from highest to lowest,
 281                  * feed the bit into thiscode, until we got a symbol from
 282                  * the tree.
 283                  */
 284                 for (i = 7; i >= 0; i--) {
 285                         thiscode = (thiscode << 1) | ((thisbyte >> i) & 1);
 286
 287                         /* Did we got a symbol? (referencing leaf node) */
 288                         if (thiscode >= unpackd->inodesin[thislevel]) {
 289                                 inlevelindex =
 290                                     thiscode - unpackd->inodesin[thislevel];
 291                                 if (inlevelindex > unpackd->symbolsin[thislevel])
 292                                         maybe_errx("File corrupt");
 293
 294                                 thissymbol =
 295                                     &(unpackd->tree[thislevel][inlevelindex]);
 296                                 if ((thissymbol == unpackd->symbol_eob) &&
 297                                     (bytes_out == unpackd->uncompressed_size))
 298                                         goto finished;
 299
 300                                 fputc((*thissymbol), unpackd->fpOut);
 301                                 bytes_out++;
 302
 303                                 /* Prepare for next input */
 304                                 thislevel = 0; thiscode = 0;
 305                         } else {
 306                                 thislevel++;
 307                                 if (thislevel > unpackd->treelevels)
 308                                         maybe_errx("File corrupt");
 309                         }
 310                 }
 311         }
 312
 313 finished:
 314         if (bytes_out != unpackd->uncompressed_size)
 315                 maybe_errx("Premature EOF");
 316 }
 317
 318 /* Handler for pack(1)'ed file */
 319 static off_t
 320 unpack(int in, int out, char *pre, size_t prelen, off_t *bytes_in)
 321 {
 322         unpack_descriptor_t unpackd;
 323
 324         in = dup(in);
 325         if (in == -1)
 326                 maybe_err("dup");
 327         out = dup(out);
 328         if (out == -1)
 329                 maybe_err("dup");
 330
 331         unpack_parse_header(in, out, pre, prelen, bytes_in, &unpackd);
 332         unpack_decode(&unpackd, bytes_in);
 333         unpack_descriptor_fini(&unpackd);
 334
 335         /* If we reached here, the unpack was successful */
 336         return (unpackd.uncompressed_size);
 337 }