1 /*
2 * D e c o m p r e s s
3 *
4 * Data decompression program for LZW compression
5 *
6 */
7
8 /* Get the usual include files */
9
10 #include <stdio.h>
11 #include <ctype.h>
12 #include <types.h>
13 #include <stat.h>
14
15 /* Define some useful constants */
16
17 #define BITS 16
18 #define HSIZE 69001 /* 95% occupancy */
19 #define BIT_MASK 0x1F
20 #define INIT_BITS 9 /* initial number of bits/code */
21 #define BLOCK_MASK 0x80
22 #define FIRST 257 /* first free entry */
23 #define CLEAR 256 /* table clear output code */
24 #ifndef VMS
25 #define GOOD_EXIT 0
26 #define BAD_EXIT 1
27 #else
28 #define GOOD_EXIT 1
29 #define BAD_EXIT 0
30 #endif
31
32 /* Define some useful macros */
33
34 #define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
35 #define htabof(i) htab[i]
36 #define codetabof(i) codetab[i]
37 #define tab_prefixof(i) codetabof (i)
38 #define tab_suffixof(i) ((char_type *) (htab))[i]
39 #define de_stack ((char_type *) &tab_suffixof (1 << BITS))
40
41 /* Set up our typedefs */
42
43 typedef long int code_int;
44 typedef long int count_int;
45 typedef unsigned char char_type;
46
47 /* Declare the global variables */
48
49 char_type magic_header[] = {"\037\235"}; /* 1F 9D */
50 char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF};
51
52 int n_bits; /* number of bits/code */
53 int maxbits = BITS; /* user settable max # bits/code */
54 code_int maxcode; /* maximum code, given n_bits */
55 code_int maxmaxcode = 1 << BITS; /* should NEVER generate this code */
56
57 count_int htab [HSIZE];
58 unsigned short codetab [HSIZE];
59
60 code_int free_ent = 0; /* first unused entry */
61
62 /* Define our function prototypes */
63
64 code_int getcode ( );
65
66 /*
67 * Block compression parameters -- after all codes are used up,
68 * and compression rate changes, start over.
69 *
70 */
71
72 int block_compress = BLOCK_MASK;
73 int clear_flg = 0;
74 char ofname [100];
75
76 /*
77 * m a i n
78 *
79 * Algorithm from "A Technique for High Performance Data Compression",
80 * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
81 *
82 * Algorithm:
83 *
84 * Modified Lempel-Ziv method (LZW). Basically finds common
85 * substrings and replaces them with a variable size code. This is
86 * deterministic, and can be done on the fly. Thus, the decompression
87 * procedure needs no input table, but tracks the way the table was built.
88 *
89 */
90
main(argc,argv)91 int main (argc, argv)
92
93 int argc;
94 char *argv[];
95
96 {
97 char tempname[100];
98 char *fileptr;
99
100 if (argc != 2) {
101 printf ("Usage: decompress filename.\n");
102 exit (BAD_EXIT);
103 }
104
105 /* Get input file (no extension) */
106
107 fileptr = argv[1];
108
109 /* Add .Z suffix */
110
111 strcpy (tempname, fileptr);
112 strcat (tempname, ".Z");
113 fileptr = tempname;
114
115 /* Open input file */
116
117 if ((freopen (fileptr, "r", stdin)) == NULL) {
118 perror (fileptr);
119 exit (BAD_EXIT);
120 }
121
122 /* Check the magic number */
123
124 if ((getchar ( ) != (magic_header[0] & 0xFF)) ||
125 (getchar ( ) != (magic_header[1] & 0xFF))) {
126 fprintf (stderr, "%s: not in compressed format\n", fileptr);
127 exit (BAD_EXIT);
128 }
129
130 maxbits = getchar ( ); /* set bits from file */
131 block_compress = maxbits & BLOCK_MASK;
132 maxbits &= BIT_MASK;
133 maxmaxcode = 1 << maxbits;
134
135 if (maxbits > BITS) {
136 fprintf (stderr, "%s: compressed with %d bits, can only handle %d bits\n",
137 fileptr, maxbits, BITS);
138 exit (BAD_EXIT);
139 }
140
141 /* Generate output filename */
142
143 strcpy (ofname, fileptr);
144 ofname[strlen (fileptr) - 2] = '\0'; /* Strip off .Z */
145
146 /* Open output file */
147
148 if (freopen (ofname, "w", stdout) == NULL) {
149 perror (ofname);
150 exit (BAD_EXIT);
151 }
152
153 /* Actually do the decompression */
154
155 decompress ( );
156
157 fclose (stdout);
158 exit (GOOD_EXIT);
159 }
160
writeerr()161 writeerr ( )
162 {
163 perror (ofname);
164 exit (BAD_EXIT);
165 }
166
167 /*
168 * d e c o m p r e s s
169 *
170 * Decompress stdin to stdout. This routine adapts to the codes in the
171 * file building the "string" table on-the-fly; requiring no table to
172 * be stored in the compressed file.
173 *
174 */
175
decompress()176 decompress ( )
177 {
178 register char_type *stackp;
179 register int finchar;
180 register code_int code, oldcode, incode;
181
182 /* Initialize the first 256 entries in the table */
183
184 maxcode = MAXCODE (n_bits = INIT_BITS);
185
186 for (code = 255; code >= 0; code--) {
187 tab_prefixof (code) = 0;
188 tab_suffixof (code) = (char_type) code;
189 }
190
191 free_ent = ((block_compress) ? FIRST : 256);
192
193 finchar = oldcode = getcode ( );
194
195 if (oldcode == -1) /* EOF already? */
196 return; /* Get out of here */
197
198 putchar ((char) finchar); /* first code must be 8 bits = char */
199
200 if (ferror (stdout)) /* Crash if can't write */
201 writeerr ( );
202
203 stackp = de_stack;
204
205 while ((code = getcode ( )) > -1) {
206
207 if ((code == CLEAR) && block_compress) {
208
209 for (code = 255; code >= 0; code--)
210 tab_prefixof (code) = 0;
211
212 clear_flg = 1;
213 free_ent = FIRST - 1;
214
215 if ((code = getcode ( )) == -1) /* O, untimely death! */
216 break;
217 }
218
219 incode = code;
220
221 /* Special case for KwKwK string */
222
223 if (code >= free_ent) {
224 *stackp++ = finchar;
225 code = oldcode;
226 }
227
228 /* Generate output characters in reverse order */
229
230 while (code >= 256) {
231 *stackp++ = tab_suffixof (code);
232 code = tab_prefixof (code);
233 }
234
235 *stackp++ = finchar = tab_suffixof (code);
236
237 /* And put them out in forward order */
238
239 do {
240 putchar (*--stackp);
241 } while (stackp > de_stack);
242
243 /* Generate the new entry */
244
245 if ((code = free_ent) < maxmaxcode) {
246 tab_prefixof (code) = (unsigned short) oldcode;
247 tab_suffixof (code) = finchar;
248 free_ent = code + 1;
249 }
250
251 /* Remember previous code */
252
253 oldcode = incode;
254 }
255
256 fflush (stdout);
257
258 if (ferror (stdout))
259 writeerr ( );
260 }
261
262 /*
263 * g e t c o d e
264 *
265 * Read one code from the standard input. If EOF, return -1.
266 *
267 */
268
getcode()269 code_int getcode ( )
270 {
271 register code_int code;
272 static int offset = 0, size = 0;
273 static char_type buf[BITS];
274 register int r_off, bits;
275 register char_type *bp = buf;
276
277 if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
278
279 /*
280 * If the next entry will be too big for the current code
281 * size, then we must increase the size. This implies reading
282 * a new buffer full, too.
283 *
284 */
285
286 if (free_ent > maxcode) {
287 n_bits++;
288
289 if (n_bits == maxbits)
290 maxcode = maxmaxcode; /* Won't get any bigger now */
291 else
292 maxcode = MAXCODE (n_bits);
293 }
294
295 if (clear_flg > 0) {
296 maxcode = MAXCODE (n_bits = INIT_BITS);
297 clear_flg = 0;
298 }
299
300 size = fread (buf, 1, n_bits, stdin);
301
302 if (size <= 0)
303 return (-1); /* End of file */
304
305 offset = 0;
306
307 /* Round size down to an integral number of codes */
308
309 size = (size << 3) - (n_bits - 1);
310 }
311
312 r_off = offset;
313 bits = n_bits;
314
315 /* Get to the first byte */
316
317 bp += (r_off >> 3);
318 r_off &= 7;
319
320 /* Get first part (low order bits) */
321
322 code = (*bp++ >> r_off);
323 bits -= (8 - r_off);
324 r_off = 8 - r_off; /* Now, offset into code word */
325
326 /* Get any 8 bit parts in the middle (<=1 for up to 16 bits) */
327
328 if (bits >= 8) {
329 code |= *bp++ << r_off;
330 r_off += 8;
331 bits -= 8;
332 }
333
334 /* Handle the high order bits */
335
336 code |= (*bp & rmask[bits]) << r_off;
337 offset += n_bits;
338
339 return (code);
340 }
341