gnu/usr.bin/gzip/unpack.c

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