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