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         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 }