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, 14 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.