unpack.c

   1 /* unpack.c -- decompress files in pack format.
   2
   3    Copyright (C) 1997, 1999, 2006, 2009-2024 Free Software Foundation, Inc.
   4    Copyright (C) 1992-1993 Jean-loup Gailly
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  18
  19 #include <config.h>
  20 #include "tailor.h"
  21 #include "gzip.h"
  22
  23 #define MIN(a,b) ((a) <= (b) ? (a) : (b))
  24 /* The arguments must not have side effects. */
  25
  26 #define MAX_BITLEN 25
  27 /* Maximum length of Huffman codes. (Minor modifications to the code
  28  * would be needed to support 32 bits codes, but pack never generates
  29  * more than 24 bits anyway.)
  30  */
  31
  32 #define LITERALS 256
  33 /* Number of literals, excluding the End of Block (EOB) code */
  34
  35 #define MAX_PEEK 12
  36 /* Maximum number of 'peek' bits used to optimize traversal of the
  37  * Huffman tree.
  38  */
  39
  40 static ulg orig_len;       /* original uncompressed length */
  41 static int max_len;        /* maximum bit length of Huffman codes */
  42
  43 static uch literal[LITERALS];
  44 /* The literal bytes present in the Huffman tree. The EOB code is not
  45  * represented.
  46  */
  47
  48 static int lit_base[MAX_BITLEN+1];
  49 /* All literals of a given bit length are contiguous in literal[] and
  50  * have contiguous codes. literal[code+lit_base[len]] is the literal
  51  * for a code of len bits.
  52  */
  53
  54 static int leaves [MAX_BITLEN+1]; /* Number of leaves for each bit length */
  55 static int parents[MAX_BITLEN+1]; /* Number of parents for each bit length */
  56
  57 static int peek_bits; /* Number of peek bits currently used */
  58
  59 /* static uch prefix_len[1 << MAX_PEEK]; */
  60 #define prefix_len outbuf
  61 /* For each bit pattern b of peek_bits bits, prefix_len[b] is the length
  62  * of the Huffman code starting with a prefix of b (upper bits), or 0
  63  * if all codes of prefix b have more than peek_bits bits. It is not
  64  * necessary to have a huge table (large MAX_PEEK) because most of the
  65  * codes encountered in the input stream are short codes (by construction).
  66  * So for most codes a single lookup will be necessary.
  67  */
  68 #if (1<<MAX_PEEK) > OUTBUFSIZ
  69     error cannot overlay prefix_len and outbuf
  70 #endif
  71
  72 static ulg bitbuf;
  73 /* Bits are added on the low part of bitbuf and read from the high part. */
  74
  75 static int valid;                  /* number of valid bits in bitbuf */
  76 /* all bits above the last valid bit are always zero */
  77
  78 /* Read an input byte, reporting an error at EOF.  */
  79 static unsigned char
  80 read_byte (void)
  81 {
  82   int b = get_byte ();
  83   if (b < 0)
  84     gzip_error ("invalid compressed data -- unexpected end of file");
  85   return b;
  86 }
  87
  88 /* Set code to the next 'bits' input bits without skipping them. code
  89  * must be the name of a simple variable and bits must not have side effects.
  90  * IN assertions: bits <= 25 (so that we still have room for an extra byte
  91  * when valid is only 24), and mask = (1<<bits)-1.
  92  */
  93 #define look_bits(code,bits,mask) \
  94 { \
  95   while (valid < (bits)) bitbuf = (bitbuf<<8) | read_byte(), valid += 8; \
  96   code = (bitbuf >> (valid-(bits))) & (mask); \
  97 }
  98
  99 /* Skip the given number of bits (after having peeked at them): */
 100 #define skip_bits(bits)  (valid -= (bits))
 101
 102 #define clear_bitbuf() (valid = 0, bitbuf = 0)
 103
 104 /* Local functions */
 105
 106 static void read_tree (void);
 107 static void build_tree (void);
 108
 109 /* ===========================================================================
 110  * Read the Huffman tree.
 111  */
 112 static void
 113 read_tree ()
 114 {
 115     int len;  /* bit length */
 116     int base; /* base offset for a sequence of leaves */
 117     int n;
 118     int max_leaves = 1;
 119
 120     /* Read the original input size, MSB first */
 121     orig_len = 0;
 122     for (n = 1; n <= 4; n++)
 123       orig_len = (orig_len << 8) | read_byte ();
 124
 125     /* Read the maximum bit length of Huffman codes.  */
 126     max_len = read_byte ();
 127     if (! (0 < max_len && max_len <= MAX_BITLEN))
 128       gzip_error ("invalid compressed data -- "
 129                   "Huffman code bit length out of range");
 130
 131     /* Get the number of leaves at each bit length */
 132     n = 0;
 133     for (len = 1; len <= max_len; len++) {
 134         leaves[len] = read_byte ();
 135         if (max_leaves - (len == max_len) < leaves[len])
 136           gzip_error ("too many leaves in Huffman tree");
 137         max_leaves = (max_leaves - leaves[len] + 1) * 2 - 1;
 138         n += leaves[len];
 139     }
 140     if (LITERALS <= n) {
 141         gzip_error ("too many leaves in Huffman tree");
 142     }
 143     Trace((stderr, "orig_len %lu, max_len %d, leaves %d\n",
 144            orig_len, max_len, n));
 145     /* There are at least 2 and at most 256 leaves of length max_len.
 146      * (Pack arbitrarily rejects empty files and files consisting of
 147      * a single byte even repeated.) To fit the last leaf count in a
 148      * byte, it is offset by 2. However, the last literal is the EOB
 149      * code, and is not transmitted explicitly in the tree, so we must
 150      * adjust here by one only.
 151      */
 152     leaves[max_len]++;
 153
 154     /* Now read the leaves themselves */
 155     base = 0;
 156     for (len = 1; len <= max_len; len++) {
 157         /* Remember where the literals of this length start in literal[] : */
 158         lit_base[len] = base;
 159         /* And read the literals: */
 160         for (n = leaves[len]; n > 0; n--) {
 161             literal[base++] = read_byte ();
 162         }
 163     }
 164     leaves[max_len]++; /* Now include the EOB code in the Huffman tree */
 165 }
 166
 167 /* ===========================================================================
 168  * Build the Huffman tree and the prefix table.
 169  */
 170 static void
 171 build_tree ()
 172 {
 173     int nodes = 0; /* number of nodes (parents+leaves) at current bit length */
 174     int len;       /* current bit length */
 175     uch *prefixp;  /* pointer in prefix_len */
 176
 177     for (len = max_len; len >= 1; len--) {
 178         /* The number of parent nodes at this level is half the total
 179          * number of nodes at parent level:
 180          */
 181         nodes >>= 1;
 182         parents[len] = nodes;
 183         /* Update lit_base by the appropriate bias to skip the parent nodes
 184          * (which are not represented in the literal array):
 185          */
 186         lit_base[len] -= nodes;
 187         /* Restore nodes to be parents+leaves: */
 188         nodes += leaves[len];
 189     }
 190     if ((nodes >> 1) != 1)
 191       gzip_error ("too few leaves in Huffman tree");
 192
 193     /* Construct the prefix table, from shortest leaves to longest ones.
 194      * The shortest code is all ones, so we start at the end of the table.
 195      */
 196     peek_bits = MIN(max_len, MAX_PEEK);
 197     prefixp = &prefix_len[1<<peek_bits];
 198     for (len = 1; len <= peek_bits; len++) {
 199         int prefixes = leaves[len] << (peek_bits-len); /* may be 0 */
 200         while (prefixes--) *--prefixp = (uch)len;
 201     }
 202     /* The length of all other codes is unknown: */
 203     while (prefixp > prefix_len) *--prefixp = 0;
 204 }
 205
 206 /* ===========================================================================
 207  * Unpack in to out.  This routine does not support the old pack format
 208  * with magic header \037\037.
 209  *
 210  * IN assertions: the buffer inbuf contains already the beginning of
 211  *   the compressed data, from offsets inptr to insize-1 included.
 212  *   The magic header has already been checked. The output buffer is cleared.
 213  *
 214  * 'in' and 'out' are the input and output file descriptors.
 215  */
 216 int
 217 unpack (int in, int out)
 218 {
 219     int len;                /* Bit length of current code */
 220     unsigned eob;           /* End Of Block code */
 221     register unsigned peek; /* lookahead bits */
 222     unsigned peek_mask;     /* Mask for peek_bits bits */
 223     off_t orig_bytes_out = bytes_out;
 224
 225     ifd = in;
 226     ofd = out;
 227
 228     read_tree();     /* Read the Huffman tree */
 229     build_tree();    /* Build the prefix table */
 230     clear_bitbuf();  /* Initialize bit input */
 231     peek_mask = (1<<peek_bits)-1;
 232
 233     /* The eob code is the largest code among all leaves of maximal length: */
 234     eob = leaves[max_len]-1;
 235     Trace((stderr, "eob %d %x\n", max_len, eob));
 236
 237     /* Decode the input data: */
 238     for (;;) {
 239         /* Since eob is the longest code and not shorter than max_len,
 240          * we can peek at max_len bits without having the risk of reading
 241          * beyond the end of file.
 242          */
 243         look_bits(peek, peek_bits, peek_mask);
 244         len = prefix_len[peek];
 245         if (len > 0) {
 246             peek >>= peek_bits - len; /* discard the extra bits */
 247         } else {
 248             /* Code of more than peek_bits bits, we must traverse the tree */
 249             ulg mask = peek_mask;
 250             len = peek_bits;
 251
 252             /* Loop as long as peek is a parent node.  */
 253             while (peek < parents[len])
 254               {
 255                 len++, mask = (mask<<1)+1;
 256                 look_bits(peek, len, mask);
 257               }
 258         }
 259         /* At this point, peek is the next complete code, of len bits */
 260         if (peek == eob && len == max_len)
 261           break; /* End of file.  */
 262         put_ubyte(literal[peek+lit_base[len]]);
 263         Tracev((stderr,"%02d %04x %c\n", len, peek,
 264                 literal[peek+lit_base[len]]));
 265         skip_bits(len);
 266     } /* for (;;) */
 267
 268     flush_window();
 269     if (orig_len != (ulg)((bytes_out - orig_bytes_out) & 0xffffffff)) {
 270         gzip_error ("invalid compressed data--length error");
 271     }
 272     return OK;
 273 }