source: MondoRescue/branches/stable/mindi-busybox/archival/libunarchive/decompress_uncompress.c@ 821

Last change on this file since 821 was 821, checked in by Bruno Cornec, 18 years ago

Addition of busybox 1.2.1 as a mindi-busybox new package
This should avoid delivering binary files in mindi not built there (Fedora and Debian are quite serious about that)
File size: 6.9 KB
Line 
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 */
67static int block_mode = BLOCK_MODE;
68
69/* user settable max # bits/code */
70static int maxbits = BITS;
71
72/* Input buffer */
73static unsigned char inbuf[IBUFSIZ + 64];
74
75/* Output buffer */
76static unsigned char outbuf[OBUFSIZ + 2048];
77
78
79static unsigned char htab[HSIZE];
80static 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
98int 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}
Note: See TracBrowser for help on using the repository browser.