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