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