]> git.cworth.org Git - gzip/blob - unlzw.c
fix build-area spec in git-buildpackage config file
[gzip] / unlzw.c
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.
5  *
6  * This is a temporary version which will be rewritten in some future version
7  * to accommodate in-memory decompression.
8  */
9
10 #ifdef RCSID
11 static char rcsid[] = "$Id: unlzw.c,v 1.5 2006/12/11 18:54:39 eggert Exp $";
12 #endif
13
14 #include <config.h>
15 #include "tailor.h"
16
17 #ifdef HAVE_UNISTD_H
18 #  include <unistd.h>
19 #endif
20 #ifdef HAVE_FCNTL_H
21 #  include <fcntl.h>
22 #endif
23
24 #include "gzip.h"
25 #include "lzw.h"
26
27 typedef unsigned char   char_type;
28 typedef          long   code_int;
29 typedef unsigned long   count_int;
30 typedef unsigned short  count_short;
31 typedef unsigned long   cmp_code_int;
32
33 #define MAXCODE(n)      (1L << (n))
34
35 #ifndef REGISTERS
36 #       define  REGISTERS       2
37 #endif
38 #define REG1
39 #define REG2
40 #define REG3
41 #define REG4
42 #define REG5
43 #define REG6
44 #define REG7
45 #define REG8
46 #define REG9
47 #define REG10
48 #define REG11
49 #define REG12
50 #define REG13
51 #define REG14
52 #define REG15
53 #define REG16
54 #if REGISTERS >= 1
55 #       undef   REG1
56 #       define  REG1    register
57 #endif
58 #if REGISTERS >= 2
59 #       undef   REG2
60 #       define  REG2    register
61 #endif
62 #if REGISTERS >= 3
63 #       undef   REG3
64 #       define  REG3    register
65 #endif
66 #if REGISTERS >= 4
67 #       undef   REG4
68 #       define  REG4    register
69 #endif
70 #if REGISTERS >= 5
71 #       undef   REG5
72 #       define  REG5    register
73 #endif
74 #if REGISTERS >= 6
75 #       undef   REG6
76 #       define  REG6    register
77 #endif
78 #if REGISTERS >= 7
79 #       undef   REG7
80 #       define  REG7    register
81 #endif
82 #if REGISTERS >= 8
83 #       undef   REG8
84 #       define  REG8    register
85 #endif
86 #if REGISTERS >= 9
87 #       undef   REG9
88 #       define  REG9    register
89 #endif
90 #if REGISTERS >= 10
91 #       undef   REG10
92 #       define  REG10   register
93 #endif
94 #if REGISTERS >= 11
95 #       undef   REG11
96 #       define  REG11   register
97 #endif
98 #if REGISTERS >= 12
99 #       undef   REG12
100 #       define  REG12   register
101 #endif
102 #if REGISTERS >= 13
103 #       undef   REG13
104 #       define  REG13   register
105 #endif
106 #if REGISTERS >= 14
107 #       undef   REG14
108 #       define  REG14   register
109 #endif
110 #if REGISTERS >= 15
111 #       undef   REG15
112 #       define  REG15   register
113 #endif
114 #if REGISTERS >= 16
115 #       undef   REG16
116 #       define  REG16   register
117 #endif
118
119 #ifndef BYTEORDER
120 #       define  BYTEORDER       0000
121 #endif
122
123 #ifndef NOALLIGN
124 #       define  NOALLIGN        0
125 #endif
126
127
128 union   bytes {
129     long  word;
130     struct {
131 #if BYTEORDER == 4321
132         char_type       b1;
133         char_type       b2;
134         char_type       b3;
135         char_type       b4;
136 #else
137 #if BYTEORDER == 1234
138         char_type       b4;
139         char_type       b3;
140         char_type       b2;
141         char_type       b1;
142 #else
143 #       undef   BYTEORDER
144         int  dummy;
145 #endif
146 #endif
147     } bytes;
148 };
149
150 #if BYTEORDER == 4321 && NOALLIGN == 1
151 #  define input(b,o,c,n,m){ \
152      (c) = (*(long *)(&(b)[(o)>>3])>>((o)&0x7))&(m); \
153      (o) += (n); \
154    }
155 #else
156 #  define input(b,o,c,n,m){ \
157      REG1 char_type *p = &(b)[(o)>>3]; \
158      (c) = ((((long)(p[0]))|((long)(p[1])<<8)| \
159      ((long)(p[2])<<16))>>((o)&0x7))&(m); \
160      (o) += (n); \
161    }
162 #endif
163
164 #ifndef MAXSEG_64K
165    /* DECLARE(ush, tab_prefix, (1<<BITS)); -- prefix code */
166 #  define tab_prefixof(i) tab_prefix[i]
167 #  define clear_tab_prefixof()  memzero(tab_prefix, 256);
168 #else
169    /* DECLARE(ush, tab_prefix0, (1<<(BITS-1)); -- prefix for even codes */
170    /* DECLARE(ush, tab_prefix1, (1<<(BITS-1)); -- prefix for odd  codes */
171    ush *tab_prefix[2];
172 #  define tab_prefixof(i) tab_prefix[(i)&1][(i)>>1]
173 #  define clear_tab_prefixof()  \
174       memzero(tab_prefix0, 128), \
175       memzero(tab_prefix1, 128);
176 #endif
177 #define de_stack        ((char_type *)(&d_buf[DIST_BUFSIZE-1]))
178 #define tab_suffixof(i) tab_suffix[i]
179
180 int block_mode = BLOCK_MODE; /* block compress mode -C compatible with 2.0 */
181
182 /* ============================================================================
183  * Decompress in to out.  This routine adapts to the codes in the
184  * file building the "string" table on-the-fly; requiring no table to
185  * be stored in the compressed file.
186  * IN assertions: the buffer inbuf contains already the beginning of
187  *   the compressed data, from offsets iptr to insize-1 included.
188  *   The magic header has already been checked and skipped.
189  *   bytes_in and bytes_out have been initialized.
190  */
191 int unlzw(in, out)
192     int in, out;    /* input and output file descriptors */
193 {
194     REG2   char_type  *stackp;
195     REG3   code_int   code;
196     REG4   int        finchar;
197     REG5   code_int   oldcode;
198     REG6   code_int   incode;
199     REG7   long       inbits;
200     REG8   long       posbits;
201     REG9   int        outpos;
202 /*  REG10  int        insize; (global) */
203     REG11  unsigned   bitmask;
204     REG12  code_int   free_ent;
205     REG13  code_int   maxcode;
206     REG14  code_int   maxmaxcode;
207     REG15  int        n_bits;
208     REG16  int        rsize;
209
210 #ifdef MAXSEG_64K
211     tab_prefix[0] = tab_prefix0;
212     tab_prefix[1] = tab_prefix1;
213 #endif
214     maxbits = get_byte();
215     block_mode = maxbits & BLOCK_MODE;
216     if ((maxbits & LZW_RESERVED) != 0) {
217         WARN((stderr, "\n%s: %s: warning, unknown flags 0x%x\n",
218               program_name, ifname, maxbits & LZW_RESERVED));
219     }
220     maxbits &= BIT_MASK;
221     maxmaxcode = MAXCODE(maxbits);
222
223     if (maxbits > BITS) {
224         fprintf(stderr,
225                 "\n%s: %s: compressed with %d bits, can only handle %d bits\n",
226                 program_name, ifname, maxbits, BITS);
227         exit_code = ERROR;
228         return ERROR;
229     }
230     rsize = insize;
231     maxcode = MAXCODE(n_bits = INIT_BITS)-1;
232     bitmask = (1<<n_bits)-1;
233     oldcode = -1;
234     finchar = 0;
235     outpos = 0;
236     posbits = inptr<<3;
237
238     free_ent = ((block_mode) ? FIRST : 256);
239
240     clear_tab_prefixof(); /* Initialize the first 256 entries in the table. */
241
242     for (code = 255 ; code >= 0 ; --code) {
243         tab_suffixof(code) = (char_type)code;
244     }
245     do {
246         REG1 int i;
247         int  e;
248         int  o;
249
250     resetbuf:
251         e = insize-(o = (posbits>>3));
252
253         for (i = 0 ; i < e ; ++i) {
254             inbuf[i] = inbuf[i+o];
255         }
256         insize = e;
257         posbits = 0;
258
259         if (insize < INBUF_EXTRA) {
260             rsize = read_buffer (in, (char *) inbuf + insize, INBUFSIZ);
261             if (rsize == -1) {
262                 read_error();
263             }
264             insize += rsize;
265             bytes_in += (off_t)rsize;
266         }
267         inbits = ((rsize != 0) ? ((long)insize - insize%n_bits)<<3 :
268                   ((long)insize<<3)-(n_bits-1));
269
270         while (inbits > posbits) {
271             if (free_ent > maxcode) {
272                 posbits = ((posbits-1) +
273                            ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3)));
274                 ++n_bits;
275                 if (n_bits == maxbits) {
276                     maxcode = maxmaxcode;
277                 } else {
278                     maxcode = MAXCODE(n_bits)-1;
279                 }
280                 bitmask = (1<<n_bits)-1;
281                 goto resetbuf;
282             }
283             input(inbuf,posbits,code,n_bits,bitmask);
284             Tracev((stderr, "%d ", code));
285
286             if (oldcode == -1) {
287                 if (256 <= code)
288                   gzip_error ("corrupt input.");
289                 outbuf[outpos++] = (char_type)(finchar = (int)(oldcode=code));
290                 continue;
291             }
292             if (code == CLEAR && block_mode) {
293                 clear_tab_prefixof();
294                 free_ent = FIRST - 1;
295                 posbits = ((posbits-1) +
296                            ((n_bits<<3)-(posbits-1+(n_bits<<3))%(n_bits<<3)));
297                 maxcode = MAXCODE(n_bits = INIT_BITS)-1;
298                 bitmask = (1<<n_bits)-1;
299                 goto resetbuf;
300             }
301             incode = code;
302             stackp = de_stack;
303
304             if (code >= free_ent) { /* Special case for KwKwK string. */
305                 if (code > free_ent) {
306 #ifdef DEBUG
307                     char_type *p;
308
309                     posbits -= n_bits;
310                     p = &inbuf[posbits>>3];
311                     fprintf(stderr,
312                             "code:%ld free_ent:%ld n_bits:%d insize:%u\n",
313                             code, free_ent, n_bits, insize);
314                     fprintf(stderr,
315                             "posbits:%ld inbuf:%02X %02X %02X %02X %02X\n",
316                             posbits, p[-1],p[0],p[1],p[2],p[3]);
317 #endif
318                     if (!test && outpos > 0) {
319                         write_buf(out, (char*)outbuf, outpos);
320                         bytes_out += (off_t)outpos;
321                     }
322                     gzip_error (to_stdout
323                                 ? "corrupt input."
324                                 : "corrupt input. Use zcat to recover some data.");
325                 }
326                 *--stackp = (char_type)finchar;
327                 code = oldcode;
328             }
329
330             while ((cmp_code_int)code >= (cmp_code_int)256) {
331                 /* Generate output characters in reverse order */
332                 *--stackp = tab_suffixof(code);
333                 code = tab_prefixof(code);
334             }
335             *--stackp = (char_type)(finchar = tab_suffixof(code));
336
337             /* And put them out in forward order */
338             {
339                 REG1 int        i;
340
341                 if (outpos+(i = (de_stack-stackp)) >= OUTBUFSIZ) {
342                     do {
343                         if (i > OUTBUFSIZ-outpos) i = OUTBUFSIZ-outpos;
344
345                         if (i > 0) {
346                             memcpy(outbuf+outpos, stackp, i);
347                             outpos += i;
348                         }
349                         if (outpos >= OUTBUFSIZ) {
350                             if (!test) {
351                                 write_buf(out, (char*)outbuf, outpos);
352                                 bytes_out += (off_t)outpos;
353                             }
354                             outpos = 0;
355                         }
356                         stackp+= i;
357                     } while ((i = (de_stack-stackp)) > 0);
358                 } else {
359                     memcpy(outbuf+outpos, stackp, i);
360                     outpos += i;
361                 }
362             }
363
364             if ((code = free_ent) < maxmaxcode) { /* Generate the new entry. */
365
366                 tab_prefixof(code) = (unsigned short)oldcode;
367                 tab_suffixof(code) = (char_type)finchar;
368                 free_ent = code+1;
369             }
370             oldcode = incode;   /* Remember previous code.      */
371         }
372     } while (rsize != 0);
373
374     if (!test && outpos > 0) {
375         write_buf(out, (char*)outbuf, outpos);
376         bytes_out += (off_t)outpos;
377     }
378     return OK;
379 }