1 /* unlzw.c -- decompress files in LZW format.
2 * The code in this file is directly derived from the public domain 'compress'
3 * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
4 * Ken Turkowski, Dave Mack and Peter Jannesen.
6 * This is a temporary version which will be rewritten in some future version
7 * to accommodate in-memory decompression.
19 typedef unsigned char char_type;
20 typedef long code_int;
21 typedef unsigned long count_int;
22 typedef unsigned short count_short;
23 typedef unsigned long cmp_code_int;
25 #define MAXCODE(n) (1L << (n))
48 # define REG1 register
52 # define REG2 register
56 # define REG3 register
60 # define REG4 register
64 # define REG5 register
68 # define REG6 register
72 # define REG7 register
76 # define REG8 register
80 # define REG9 register
84 # define REG10 register
88 # define REG11 register
92 # define REG12 register
96 # define REG13 register
100 # define REG14 register
104 # define REG15 register
108 # define REG16 register
112 # define BYTEORDER 0000
123 #if BYTEORDER == 4321
129 #if BYTEORDER == 1234
142 #if BYTEORDER == 4321 && NOALLIGN == 1
143 # define input(b,o,c,n,m){ \
144 (c) = (*(long *)(&(b)[(o)>>3])>>((o)&0x7))&(m); \
148 # define input(b,o,c,n,m){ \
149 REG1 char_type *p = &(b)[(o)>>3]; \
150 (c) = ((((long)(p[0]))|((long)(p[1])<<8)| \
151 ((long)(p[2])<<16))>>((o)&0x7))&(m); \
157 /* DECLARE(ush, tab_prefix, (1<<BITS)); -- prefix code */
158 # define tab_prefixof(i) tab_prefix[i]
159 # define clear_tab_prefixof() memzero(tab_prefix, 256);
161 /* DECLARE(ush, tab_prefix0, (1<<(BITS-1)); -- prefix for even codes */
162 /* DECLARE(ush, tab_prefix1, (1<<(BITS-1)); -- prefix for odd codes */
164 # define tab_prefixof(i) tab_prefix[(i)&1][(i)>>1]
165 # define clear_tab_prefixof() \
166 memzero(tab_prefix0, 128), \
167 memzero(tab_prefix1, 128);
169 #define de_stack ((char_type *)(&d_buf[DIST_BUFSIZE-1]))
170 #define tab_suffixof(i) tab_suffix[i]
172 int block_mode = BLOCK_MODE; /* block compress mode -C compatible with 2.0 */
174 /* ============================================================================
175 * Decompress in to out. This routine adapts to the codes in the
176 * file building the "string" table on-the-fly; requiring no table to
177 * be stored in the compressed file.
178 * IN assertions: the buffer inbuf contains already the beginning of
179 * the compressed data, from offsets iptr to insize-1 included.
180 * The magic header has already been checked and skipped.
181 * bytes_in and bytes_out have been initialized.
184 int in, out; /* input and output file descriptors */
186 REG2 char_type *stackp;
189 REG5 code_int oldcode;
190 REG6 code_int incode;
194 /* REG10 int insize; (global) */
195 REG11 unsigned bitmask;
196 REG12 code_int free_ent;
197 REG13 code_int maxcode;
198 REG14 code_int maxmaxcode;
203 tab_prefix[0] = tab_prefix0;
204 tab_prefix[1] = tab_prefix1;
206 maxbits = get_byte();
207 block_mode = maxbits & BLOCK_MODE;
208 if ((maxbits & LZW_RESERVED) != 0) {
209 WARN((stderr, "\n%s: %s: warning, unknown flags 0x%x\n",
210 program_name, ifname, maxbits & LZW_RESERVED));
213 maxmaxcode = MAXCODE(maxbits);
215 if (maxbits > BITS) {
217 "\n%s: %s: compressed with %d bits, can only handle %d bits\n",
218 program_name, ifname, maxbits, BITS);
223 maxcode = MAXCODE(n_bits = INIT_BITS)-1;
224 bitmask = (1<<n_bits)-1;
230 free_ent = ((block_mode) ? FIRST : 256);
232 clear_tab_prefixof(); /* Initialize the first 256 entries in the table. */
234 for (code = 255 ; code >= 0 ; --code) {
235 tab_suffixof(code) = (char_type)code;
244 e = o <= insize ? insize - o : 0;
246 for (i = 0 ; i < e ; ++i) {
247 inbuf[i] = inbuf[i+o];
252 if (insize < INBUF_EXTRA) {
253 rsize = read_buffer (in, (char *) inbuf + insize, INBUFSIZ);
258 bytes_in += (off_t)rsize;
260 inbits = ((rsize != 0) ? ((long)insize - insize%n_bits)<<3 :
261 ((long)insize<<3)-(n_bits-1));
263 while (inbits > posbits) {
264 if (free_ent > maxcode) {
265 posbits = ((posbits-1) +
266 ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3)));
268 if (n_bits == maxbits) {
269 maxcode = maxmaxcode;
271 maxcode = MAXCODE(n_bits)-1;
273 bitmask = (1<<n_bits)-1;
276 input(inbuf,posbits,code,n_bits,bitmask);
277 Tracev((stderr, "%d ", code));
281 gzip_error ("corrupt input.");
282 outbuf[outpos++] = (char_type)(finchar = (int)(oldcode=code));
285 if (code == CLEAR && block_mode) {
286 clear_tab_prefixof();
287 free_ent = FIRST - 1;
288 posbits = ((posbits-1) +
289 ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3)));
290 maxcode = MAXCODE(n_bits = INIT_BITS)-1;
291 bitmask = (1<<n_bits)-1;
297 if (code >= free_ent) { /* Special case for KwKwK string. */
298 if (code > free_ent) {
303 p = &inbuf[posbits>>3];
305 "code:%ld free_ent:%ld n_bits:%d insize:%u\n",
306 code, free_ent, n_bits, insize);
308 "posbits:%ld inbuf:%02X %02X %02X %02X %02X\n",
309 posbits, p[-1],p[0],p[1],p[2],p[3]);
311 if (!test && outpos > 0) {
312 write_buf(out, (char*)outbuf, outpos);
313 bytes_out += (off_t)outpos;
315 gzip_error (to_stdout
317 : "corrupt input. Use zcat to recover some data.");
319 *--stackp = (char_type)finchar;
323 while ((cmp_code_int)code >= (cmp_code_int)256) {
324 /* Generate output characters in reverse order */
325 *--stackp = tab_suffixof(code);
326 code = tab_prefixof(code);
328 *--stackp = (char_type)(finchar = tab_suffixof(code));
330 /* And put them out in forward order */
334 if (outpos+(i = (de_stack-stackp)) >= OUTBUFSIZ) {
336 if (i > OUTBUFSIZ-outpos) i = OUTBUFSIZ-outpos;
339 memcpy(outbuf+outpos, stackp, i);
342 if (outpos >= OUTBUFSIZ) {
344 write_buf(out, (char*)outbuf, outpos);
345 bytes_out += (off_t)outpos;
350 } while ((i = (de_stack-stackp)) > 0);
352 memcpy(outbuf+outpos, stackp, i);
357 if ((code = free_ent) < maxmaxcode) { /* Generate the new entry. */
359 tab_prefixof(code) = (unsigned short)oldcode;
360 tab_suffixof(code) = (char_type)finchar;
363 oldcode = incode; /* Remember previous code. */
365 } while (rsize != 0);
367 if (!test && outpos > 0) {
368 write_buf(out, (char*)outbuf, outpos);
369 bytes_out += (off_t)outpos;