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