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