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.
23 typedef unsigned char char_type;
24 typedef long code_int;
25 typedef unsigned long count_int;
26 typedef unsigned short count_short;
27 typedef unsigned long cmp_code_int;
29 #define MAXCODE(n) (1L << (n))
52 # define REG1 register
56 # define REG2 register
60 # define REG3 register
64 # define REG4 register
68 # define REG5 register
72 # define REG6 register
76 # define REG7 register
80 # define REG8 register
84 # define REG9 register
88 # define REG10 register
92 # define REG11 register
96 # define REG12 register
100 # define REG13 register
104 # define REG14 register
108 # define REG15 register
112 # define REG16 register
116 # define BYTEORDER 0000
127 #if BYTEORDER == 4321
133 #if BYTEORDER == 1234
146 #if BYTEORDER == 4321 && NOALLIGN == 1
147 # define input(b,o,c,n,m){ \
148 (c) = (*(long *)(&(b)[(o)>>3])>>((o)&0x7))&(m); \
152 # define input(b,o,c,n,m){ \
153 REG1 char_type *p = &(b)[(o)>>3]; \
154 (c) = ((((long)(p[0]))|((long)(p[1])<<8)| \
155 ((long)(p[2])<<16))>>((o)&0x7))&(m); \
161 /* DECLARE(ush, tab_prefix, (1<<BITS)); -- prefix code */
162 # define tab_prefixof(i) tab_prefix[i]
163 # define clear_tab_prefixof() memzero(tab_prefix, 256);
165 /* DECLARE(ush, tab_prefix0, (1<<(BITS-1)); -- prefix for even codes */
166 /* DECLARE(ush, tab_prefix1, (1<<(BITS-1)); -- prefix for odd codes */
168 # define tab_prefixof(i) tab_prefix[(i)&1][(i)>>1]
169 # define clear_tab_prefixof() \
170 memzero(tab_prefix0, 128), \
171 memzero(tab_prefix1, 128);
173 #define de_stack ((char_type *)(&d_buf[DIST_BUFSIZE-1]))
174 #define tab_suffixof(i) tab_suffix[i]
176 int block_mode = BLOCK_MODE; /* block compress mode -C compatible with 2.0 */
178 /* ============================================================================
179 * Decompress in to out. This routine adapts to the codes in the
180 * file building the "string" table on-the-fly; requiring no table to
181 * be stored in the compressed file.
182 * IN assertions: the buffer inbuf contains already the beginning of
183 * the compressed data, from offsets iptr to insize-1 included.
184 * The magic header has already been checked and skipped.
185 * bytes_in and bytes_out have been initialized.
188 int in, out; /* input and output file descriptors */
190 REG2 char_type *stackp;
193 REG5 code_int oldcode;
194 REG6 code_int incode;
198 /* REG10 int insize; (global) */
199 REG11 unsigned bitmask;
200 REG12 code_int free_ent;
201 REG13 code_int maxcode;
202 REG14 code_int maxmaxcode;
207 tab_prefix[0] = tab_prefix0;
208 tab_prefix[1] = tab_prefix1;
210 maxbits = get_byte();
211 block_mode = maxbits & BLOCK_MODE;
212 if ((maxbits & LZW_RESERVED) != 0) {
213 WARN((stderr, "\n%s: %s: warning, unknown flags 0x%x\n",
214 program_name, ifname, maxbits & LZW_RESERVED));
217 maxmaxcode = MAXCODE(maxbits);
219 if (maxbits > BITS) {
221 "\n%s: %s: compressed with %d bits, can only handle %d bits\n",
222 program_name, ifname, maxbits, BITS);
227 maxcode = MAXCODE(n_bits = INIT_BITS)-1;
228 bitmask = (1<<n_bits)-1;
234 free_ent = ((block_mode) ? FIRST : 256);
236 clear_tab_prefixof(); /* Initialize the first 256 entries in the table. */
238 for (code = 255 ; code >= 0 ; --code) {
239 tab_suffixof(code) = (char_type)code;
247 e = insize-(o = (posbits>>3));
249 for (i = 0 ; i < e ; ++i) {
250 inbuf[i] = inbuf[i+o];
255 if (insize < INBUF_EXTRA) {
256 rsize = read_buffer (in, (char *) inbuf + insize, INBUFSIZ);
261 bytes_in += (off_t)rsize;
263 inbits = ((rsize != 0) ? ((long)insize - insize%n_bits)<<3 :
264 ((long)insize<<3)-(n_bits-1));
266 while (inbits > posbits) {
267 if (free_ent > maxcode) {
268 posbits = ((posbits-1) +
269 ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3)));
271 if (n_bits == maxbits) {
272 maxcode = maxmaxcode;
274 maxcode = MAXCODE(n_bits)-1;
276 bitmask = (1<<n_bits)-1;
279 input(inbuf,posbits,code,n_bits,bitmask);
280 Tracev((stderr, "%d ", code));
284 gzip_error ("corrupt input.");
285 outbuf[outpos++] = (char_type)(finchar = (int)(oldcode=code));
288 if (code == CLEAR && block_mode) {
289 clear_tab_prefixof();
290 free_ent = FIRST - 1;
291 posbits = ((posbits-1) +
292 ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3)));
293 maxcode = MAXCODE(n_bits = INIT_BITS)-1;
294 bitmask = (1<<n_bits)-1;
300 if (code >= free_ent) { /* Special case for KwKwK string. */
301 if (code > free_ent) {
306 p = &inbuf[posbits>>3];
308 "code:%ld free_ent:%ld n_bits:%d insize:%u\n",
309 code, free_ent, n_bits, insize);
311 "posbits:%ld inbuf:%02X %02X %02X %02X %02X\n",
312 posbits, p[-1],p[0],p[1],p[2],p[3]);
314 if (!test && outpos > 0) {
315 write_buf(out, (char*)outbuf, outpos);
316 bytes_out += (off_t)outpos;
318 gzip_error (to_stdout
320 : "corrupt input. Use zcat to recover some data.");
322 *--stackp = (char_type)finchar;
326 while ((cmp_code_int)code >= (cmp_code_int)256) {
327 /* Generate output characters in reverse order */
328 *--stackp = tab_suffixof(code);
329 code = tab_prefixof(code);
331 *--stackp = (char_type)(finchar = tab_suffixof(code));
333 /* And put them out in forward order */
337 if (outpos+(i = (de_stack-stackp)) >= OUTBUFSIZ) {
339 if (i > OUTBUFSIZ-outpos) i = OUTBUFSIZ-outpos;
342 memcpy(outbuf+outpos, stackp, i);
345 if (outpos >= OUTBUFSIZ) {
347 write_buf(out, (char*)outbuf, outpos);
348 bytes_out += (off_t)outpos;
353 } while ((i = (de_stack-stackp)) > 0);
355 memcpy(outbuf+outpos, stackp, i);
360 if ((code = free_ent) < maxmaxcode) { /* Generate the new entry. */
362 tab_prefixof(code) = (unsigned short)oldcode;
363 tab_suffixof(code) = (char_type)finchar;
366 oldcode = incode; /* Remember previous code. */
368 } while (rsize != 0);
370 if (!test && outpos > 0) {
371 write_buf(out, (char*)outbuf, outpos);
372 bytes_out += (off_t)outpos;