Style
[oweals/busybox.git] / archival / libunarchive / decompress_uncompress.c
1 #include "config.h"
2 #include "libbb.h"
3
4 #if defined CONFIG_UNCOMPRESS || defined CONFIG_FEATURE_GUNZIP_UNCOMPRESS
5
6 /* uncompress for busybox -- (c) 2002 Robert Griebl
7  *
8  * based on the original compress42.c source 
9  * (see disclaimer below)
10  */
11
12
13 /* (N)compress42.c - File compression ala IEEE Computer, Mar 1992.
14  *
15  * Authors:
16  *   Spencer W. Thomas   (decvax!harpo!utah-cs!utah-gr!thomas)
17  *   Jim McKie           (decvax!mcvax!jim)
18  *   Steve Davies        (decvax!vax135!petsd!peora!srd)
19  *   Ken Turkowski       (decvax!decwrl!turtlevax!ken)
20  *   James A. Woods      (decvax!ihnp4!ames!jaw)
21  *   Joe Orost           (decvax!vax135!petsd!joe)
22  *   Dave Mack           (csu@alembic.acs.com)
23  *   Peter Jannesen, Network Communication Systems
24  *                       (peter@ncs.nl)
25  *
26  * marc@suse.de : a small security fix for a buffer overflow
27  *
28  * [... History snipped ...]
29  *
30  */
31 #include <stdio.h>
32 #include <string.h>
33 #include <unistd.h>
34
35 /* Defailt input buffer size */
36 #define IBUFSIZ 2048
37
38 /* Default output buffer size */
39 #define OBUFSIZ 2048
40
41 /* Defines for third byte of header */
42 #define MAGIC_1         (char_type)'\037'       /* First byte of compressed file               */
43 #define MAGIC_2         (char_type)'\235'       /* Second byte of compressed file              */
44 #define BIT_MASK        0x1f    /* Mask for 'number of compresssion bits'       */
45                                                         /* Masks 0x20 and 0x40 are free.                */
46                                                         /* I think 0x20 should mean that there is       */
47                                                         /* a fourth header byte (for expansion).        */
48 #define BLOCK_MODE      0x80    /* Block compresssion if table is full and      */
49                         /* compression rate is dropping flush tables    */
50                         /* the next two codes should not be changed lightly, as they must not   */
51                         /* lie within the contiguous general code space.                        */
52 #define FIRST   257             /* first free entry                             */
53 #define CLEAR   256             /* table clear output code                      */
54
55 #define INIT_BITS 9             /* initial number of bits/code */
56
57
58 /* machine variants which require cc -Dmachine:  pdp11, z8000, DOS */
59 #define FAST
60
61 #define HBITS           17      /* 50% occupancy */
62 #define HSIZE      (1<<HBITS)
63 #define HMASK      (HSIZE-1)
64 #define HPRIME           9941
65 #define BITS               16
66 #undef  MAXSEG_64K
67 #define MAXCODE(n)      (1L << (n))
68
69 /* Block compress mode -C compatible with 2.0 */
70 int block_mode = BLOCK_MODE;
71
72 /* user settable max # bits/code */
73 int maxbits = BITS;
74
75 /* Exitcode of compress (-1 no file compressed) */
76 int exit_code = -1;
77
78 /* Input buffer */
79 unsigned char inbuf[IBUFSIZ + 64];
80
81 /* Output buffer */
82 unsigned char outbuf[OBUFSIZ + 2048];
83
84
85 long int htab[HSIZE];
86 unsigned short codetab[HSIZE];
87
88 #define htabof(i)                               htab[i]
89 #define codetabof(i)                    codetab[i]
90 #define tab_prefixof(i)                 codetabof(i)
91 #define tab_suffixof(i)                 ((unsigned char *)(htab))[i]
92 #define de_stack                                ((unsigned char *)&(htab[HSIZE-1]))
93 #define clear_htab()                    memset(htab, -1, sizeof(htab))
94 #define clear_tab_prefixof()    memset(codetab, 0, 256);
95
96
97 /*
98  * Decompress stdin to stdout.  This routine adapts to the codes in the
99  * file building the "string" table on-the-fly; requiring no table to
100  * be stored in the compressed file.  The tables used herein are shared
101  * with those of the compress() routine.  See the definitions above.
102  */
103
104 extern int uncompress(int fd_in, int fd_out)
105 {
106         unsigned char *stackp;
107         long int code;
108         int finchar;
109         long int oldcode;
110         long int incode;
111         int inbits;
112         int posbits;
113         int outpos;
114         int insize;
115         int bitmask;
116         long int free_ent;
117         long int maxcode;
118         long int maxmaxcode;
119         int n_bits;
120         int rsize = 0;
121
122         insize = 0;
123
124         inbuf[0] = xread_char(fd_in);
125
126         maxbits = inbuf[0] & BIT_MASK;
127         block_mode = inbuf[0] & BLOCK_MODE;
128         maxmaxcode = MAXCODE(maxbits);
129
130         if (maxbits > BITS) {
131                 error_msg("compressed with %d bits, can only handle %d bits", maxbits,
132                                   BITS);
133                 return -1;
134         }
135
136         maxcode = MAXCODE(n_bits = INIT_BITS) - 1;
137         bitmask = (1 << n_bits) - 1;
138         oldcode = -1;
139         finchar = 0;
140         outpos = 0;
141         posbits = 0 << 3;
142
143         free_ent = ((block_mode) ? FIRST : 256);
144
145         /* As above, initialize the first 256 entries in the table. */
146         clear_tab_prefixof();
147
148         for (code = 255; code >= 0; --code) {
149                 tab_suffixof(code) = (unsigned char) code;
150         }
151
152         do {
153           resetbuf:;
154                 {
155                         int i;
156                         int e;
157                         int o;
158
159                         e = insize - (o = (posbits >> 3));
160
161                         for (i = 0; i < e; ++i)
162                                 inbuf[i] = inbuf[i + o];
163
164                         insize = e;
165                         posbits = 0;
166                 }
167
168                 if (insize < (int) sizeof(inbuf) - IBUFSIZ) {
169                         rsize = read(fd_in, inbuf + insize, IBUFSIZ);
170                         insize += rsize;
171                 }
172
173                 inbits = ((rsize > 0) ? (insize - insize % n_bits) << 3 :
174                                   (insize << 3) - (n_bits - 1));
175
176                 while (inbits > posbits) {
177                         if (free_ent > maxcode) {
178                                 posbits =
179                                         ((posbits - 1) +
180                                          ((n_bits << 3) -
181                                           (posbits - 1 + (n_bits << 3)) % (n_bits << 3)));
182                                 ++n_bits;
183                                 if (n_bits == maxbits) {
184                                         maxcode = maxmaxcode;
185                                 } else {
186                                         maxcode = MAXCODE(n_bits) - 1;
187                                 }
188                                 bitmask = (1 << n_bits) - 1;
189                                 goto resetbuf;
190                         }
191                         {
192                                 unsigned char *p = &inbuf[posbits >> 3];
193
194                                 code =
195                                         ((((long) (p[0])) | ((long) (p[1]) << 8) |
196                                           ((long) (p[2]) << 16)) >> (posbits & 0x7)) & bitmask;
197                         }
198                         posbits += n_bits;
199
200
201                         if (oldcode == -1) {
202                                 outbuf[outpos++] = (unsigned char) (finchar =
203                                                                                                 (int) (oldcode = code));
204                                 continue;
205                         }
206
207                         if (code == CLEAR && block_mode) {
208                                 clear_tab_prefixof();
209                                 free_ent = FIRST - 1;
210                                 posbits =
211                                         ((posbits - 1) +
212                                          ((n_bits << 3) -
213                                           (posbits - 1 + (n_bits << 3)) % (n_bits << 3)));
214                                 maxcode = MAXCODE(n_bits = INIT_BITS) - 1;
215                                 bitmask = (1 << n_bits) - 1;
216                                 goto resetbuf;
217                         }
218
219                         incode = code;
220                         stackp = de_stack;
221
222                         /* Special case for KwKwK string. */
223                         if (code >= free_ent) {
224                                 if (code > free_ent) {
225                                         unsigned char *p;
226
227                                         posbits -= n_bits;
228                                         p = &inbuf[posbits >> 3];
229
230                                         error_msg
231                                                 ("insize:%d posbits:%d inbuf:%02X %02X %02X %02X %02X (%d)",
232                                                  insize, posbits, p[-1], p[0], p[1], p[2], p[3],
233                                                  (posbits & 07));
234                                         error_msg("uncompress: corrupt input");
235                                         return -1;
236                                 }
237
238                                 *--stackp = (unsigned char) finchar;
239                                 code = oldcode;
240                         }
241
242                         /* Generate output characters in reverse order */
243                         while ((long int) code >= (long int) 256) {
244                                 *--stackp = tab_suffixof(code);
245                                 code = tab_prefixof(code);
246                         }
247
248                         *--stackp = (unsigned char) (finchar = tab_suffixof(code));
249
250                         /* And put them out in forward order */
251                         {
252                                 int i;
253
254                                 if (outpos + (i = (de_stack - stackp)) >= OBUFSIZ) {
255                                         do {
256                                                 if (i > OBUFSIZ - outpos) {
257                                                         i = OBUFSIZ - outpos;
258                                                 }
259
260                                                 if (i > 0) {
261                                                         memcpy(outbuf + outpos, stackp, i);
262                                                         outpos += i;
263                                                 }
264
265                                                 if (outpos >= OBUFSIZ) {
266                                                         write(fd_out, outbuf, outpos);
267                                                         outpos = 0;
268                                                 }
269                                                 stackp += i;
270                                         } while ((i = (de_stack - stackp)) > 0);
271                                 } else {
272                                         memcpy(outbuf + outpos, stackp, i);
273                                         outpos += i;
274                                 }
275                         }
276
277                         /* Generate the new entry. */
278                         if ((code = free_ent) < maxmaxcode) {
279                                 tab_prefixof(code) = (unsigned short) oldcode;
280                                 tab_suffixof(code) = (unsigned char) finchar;
281                                 free_ent = code + 1;
282                         }
283
284                         /* Remember previous code.  */
285                         oldcode = incode;
286                 }
287
288         } while (rsize > 0);
289
290         if (outpos > 0) {
291                 write(fd_out, outbuf, outpos);
292         }
293
294         return 0;
295 }
296
297
298 #endif