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.
11 static char rcsid
[] = "$Id: unlzw.c,v 0.15 1993/06/10 13:28:35 jloup Exp $";
14 #include <sys/types.h>
28 typedef unsigned char char_type
;
29 typedef long code_int
;
30 typedef unsigned long count_int
;
31 typedef unsigned short count_short
;
32 typedef unsigned long cmp_code_int
;
34 #define MAXCODE(n) (1L << (n))
57 # define REG1 register
61 # define REG2 register
65 # define REG3 register
69 # define REG4 register
73 # define REG5 register
77 # define REG6 register
81 # define REG7 register
85 # define REG8 register
89 # define REG9 register
93 # define REG10 register
97 # define REG11 register
101 # define REG12 register
105 # define REG13 register
109 # define REG14 register
113 # define REG15 register
117 # define REG16 register
121 # define BYTEORDER 0000
132 #if BYTEORDER == 4321
138 #if BYTEORDER == 1234
151 #if BYTEORDER == 4321 && NOALLIGN == 1
152 # define input(b,o,c,n,m){ \
153 (c) = (*(long *)(&(b)[(o)>>3])>>((o)&0x7))&(m); \
157 # define input(b,o,c,n,m){ \
158 REG1 char_type *p = &(b)[(o)>>3]; \
159 (c) = ((((long)(p[0]))|((long)(p[1])<<8)| \
160 ((long)(p[2])<<16))>>((o)&0x7))&(m); \
166 /* DECLARE(ush, tab_prefix, (1<<BITS)); -- prefix code */
167 # define tab_prefixof(i) tab_prefix[i]
168 # define clear_tab_prefixof() memzero(tab_prefix, 256);
170 /* DECLARE(ush, tab_prefix0, (1<<(BITS-1)); -- prefix for even codes */
171 /* DECLARE(ush, tab_prefix1, (1<<(BITS-1)); -- prefix for odd codes */
173 # define tab_prefixof(i) tab_prefix[(i)&1][(i)>>1]
174 # define clear_tab_prefixof() \
175 memzero(tab_prefix0, 128), \
176 memzero(tab_prefix1, 128);
178 #define de_stack ((char_type *)(&d_buf[DIST_BUFSIZE-1]))
179 #define tab_suffixof(i) tab_suffix[i]
181 int block_mode
= BLOCK_MODE
; /* block compress mode -C compatible with 2.0 */
183 /* ============================================================================
184 * Decompress in to out. This routine adapts to the codes in the
185 * file building the "string" table on-the-fly; requiring no table to
186 * be stored in the compressed file.
187 * IN assertions: the buffer inbuf contains already the beginning of
188 * the compressed data, from offsets iptr to insize-1 included.
189 * The magic header has already been checked and skipped.
190 * bytes_in and bytes_out have been initialized.
193 int in
, out
; /* input and output file descriptors */
195 REG2 char_type
*stackp
;
198 REG5 code_int oldcode
;
199 REG6 code_int incode
;
203 /* REG10 int insize; (global) */
204 REG11
unsigned bitmask
;
205 REG12 code_int free_ent
;
206 REG13 code_int maxcode
;
207 REG14 code_int maxmaxcode
;
211 maxbits
= get_byte();
212 block_mode
= maxbits
& BLOCK_MODE
;
213 if ((maxbits
& LZW_RESERVED
) != 0) {
214 WARN((stderr
, "\n%s: %s: warning, unknown flags 0x%x\n",
215 progname
, ifname
, maxbits
& LZW_RESERVED
));
218 maxmaxcode
= MAXCODE(maxbits
);
220 if (maxbits
> BITS
) {
222 "\n%s: %s: compressed with %d bits, can only handle %d bits\n",
223 progname
, ifname
, maxbits
, BITS
);
228 maxcode
= MAXCODE(n_bits
= INIT_BITS
)-1;
229 bitmask
= (1<<n_bits
)-1;
235 free_ent
= ((block_mode
) ? FIRST
: 256);
237 clear_tab_prefixof(); /* Initialize the first 256 entries in the table. */
239 for (code
= 255 ; code
>= 0 ; --code
) {
240 tab_suffixof(code
) = (char_type
)code
;
248 e
= insize
-(o
= (posbits
>>3));
250 for (i
= 0 ; i
< e
; ++i
) {
251 inbuf
[i
] = inbuf
[i
+o
];
256 if (insize
< INBUF_EXTRA
) {
257 if ((rsize
= read(in
, (char*)inbuf
+insize
, INBUFSIZ
)) == EOF
) {
261 bytes_in
+= (ulg
)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
));
283 if (code
>= 256) error("corrupt input.");
284 outbuf
[outpos
++] = (char_type
)(finchar
= (int)(oldcode
=code
));
287 if (code
== CLEAR
&& block_mode
) {
288 clear_tab_prefixof();
289 free_ent
= FIRST
- 1;
290 posbits
= ((posbits
-1) +
291 ((n_bits
<<3)-(posbits
-1+(n_bits
<<3))%(n_bits
<<3)));
292 maxcode
= MAXCODE(n_bits
= INIT_BITS
)-1;
293 bitmask
= (1<<n_bits
)-1;
299 if (code
>= free_ent
) { /* Special case for KwKwK string. */
300 if (code
> free_ent
) {
305 p
= &inbuf
[posbits
>>3];
307 "code:%ld free_ent:%ld n_bits:%d insize:%u\n",
308 code
, free_ent
, n_bits
, insize
);
310 "posbits:%ld inbuf:%02X %02X %02X %02X %02X\n",
311 posbits
, p
[-1],p
[0],p
[1],p
[2],p
[3]);
315 if (!test
&& outpos
> 0) {
316 write_buf(out
, (char*)outbuf
, outpos
);
317 bytes_out
+= (ulg
)outpos
;
320 error(to_stdout
? "corrupt input." :
321 "corrupt input. Use zcat to recover some data.");
323 *--stackp
= (char_type
)finchar
;
327 while ((cmp_code_int
)code
>= (cmp_code_int
)256) {
328 /* Generate output characters in reverse order */
329 *--stackp
= tab_suffixof(code
);
330 code
= tab_prefixof(code
);
332 *--stackp
= (char_type
)(finchar
= tab_suffixof(code
));
334 /* And put them out in forward order */
338 if (outpos
+(i
= (de_stack
-stackp
)) >= outbuflen
) {
340 if (i
> outbuflen
-outpos
) i
= outbuflen
-outpos
;
343 memcpy(outbuf
+outpos
, stackp
, i
);
346 if (outpos
>= outbuflen
) {
349 write_buf(out
, (char*)outbuf
, outpos
);
350 bytes_out
+= (ulg
)outpos
;
353 fprintf(stderr
, "Error: Chamber overflow!\n");
357 } while ((i
= (de_stack
-stackp
)) > 0);
359 memcpy(outbuf
+outpos
, stackp
, i
);
364 if ((code
= free_ent
) < maxmaxcode
) { /* Generate the new entry. */
366 tab_prefixof(code
) = (unsigned short)oldcode
;
367 tab_suffixof(code
) = (char_type
)finchar
;
370 oldcode
= incode
; /* Remember previous code. */
372 } while (rsize
!= 0);
374 if (!test
&& outpos
> 0) {
375 write_buf(out
, (char*)outbuf
, outpos
);
376 bytes_out
+= (ulg
)outpos
;