unpack.c

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