]> git.saurik.com Git - wxWidgets.git/blob - utils/Install/packzip/unshrink.c
changed version number
[wxWidgets.git] / utils / Install / packzip / unshrink.c
1 /*---------------------------------------------------------------------------
2
3 unshrink.c version 1.21 23 Nov 95
4
5
6 NOTE: This code may or may not infringe on the so-called "Welch
7 patent" owned by Unisys. (From reading the patent, it appears
8 that a pure LZW decompressor is *not* covered, but this claim has
9 not been tested in court, and Unisys is reported to believe other-
10 wise.) It is therefore the responsibility of the user to acquire
11 whatever license(s) may be required for legal use of this code.
12
13 THE INFO-ZIP GROUP DISCLAIMS ALL LIABILITY FOR USE OF THIS CODE
14 IN VIOLATION OF APPLICABLE PATENT LAW.
15
16
17 Shrinking is basically a dynamic LZW algorithm with allowed code sizes of
18 up to 13 bits; in addition, there is provision for partial clearing of
19 leaf nodes. PKWARE uses the special code 256 (decimal) to indicate a
20 change in code size or a partial clear of the code tree: 256,1 for the
21 former and 256,2 for the latter. [Note that partial clearing can "orphan"
22 nodes: the parent-to-be can be cleared before its new child is added,
23 but the child is added anyway (as an orphan, as though the parent still
24 existed). When the tree fills up to the point where the parent node is
25 reused, the orphan is effectively "adopted." Versions prior to 1.05 were
26 affected more due to greater use of pointers (to children and siblings
27 as well as parents).]
28
29 This replacement version of unshrink.c was written from scratch. It is
30 based only on the algorithms described in Mark Nelson's _The Data Compres-
31 sion Book_ and in Terry Welch's original paper in the June 1984 issue of
32 IEEE _Computer_; no existing source code, including any in Nelson's book,
33 was used.
34
35 Memory requirements have been reduced in this version and are now no more
36 than the original Sam Smith code. This is still larger than any of the
37 other algorithms: at a minimum, 8K+8K+16K (stack+values+parents) assuming
38 16-bit short ints, and this does not even include the output buffer (the
39 other algorithms leave the uncompressed data in the work area, typically
40 called slide[]). For machines with a 64KB data space this is a problem,
41 particularly when text conversion is required and line endings have more
42 than one character. UnZip's solution is to use two roughly equal halves
43 of outbuf for the ASCII conversion in such a case; the "unshrink" argument
44 to flush() signals that this is the case.
45
46 For large-memory machines, a second outbuf is allocated for translations,
47 but only if unshrinking and only if translations are required.
48
49 | binary mode | text mode
50 ---------------------------------------------------
51 big mem | big outbuf | big outbuf + big outbuf2 <- malloc'd here
52 small mem | small outbuf | half + half small outbuf
53
54 Copyright 1994, 1995 Greg Roelofs. See the accompanying file "COPYING"
55 in UnZip 5.20 (or later) source or binary distributions.
56
57 ---------------------------------------------------------------------------*/
58
59
60 #define UNZIP_INTERNAL
61 #include "unzip.h" /* defines LZW_CLEAN by default */
62
63
64 #ifndef LZW_CLEAN
65
66 static void partial_clear OF((__GPRO));
67
68 #ifdef DEBUG
69 # define OUTDBG(c) \
70 if ((c)<32 || (c)>=127) pipeit("\\x%02x",(c)); else { }
71 #else
72 # define OUTDBG(c)
73 #endif
74
75 /* HSIZE is defined as 2^13 (8192) in unzip.h */
76 #define BOGUSCODE 256
77 #define FLAG_BITS parent /* upper bits of parent[] used as flag bits */
78 #define CODE_MASK (HSIZE - 1) /* 0x1fff (lower bits are parent's index) */
79 #define FREE_CODE HSIZE /* 0x2000 (code is unused or was cleared) */
80 #define HAS_CHILD (HSIZE << 1) /* 0x4000 (code has a child--do not clear) */
81
82 #define parent G.area.shrink.Parent
83 #define Value G.area.shrink.value /* "value" conflicts with Pyramid ioctl.h */
84 #define stack G.area.shrink.Stack
85
86
87 /***********************/
88 /* Function unshrink() */
89 /***********************/
90
91 int unshrink(__G)
92 __GDEF
93 {
94 int offset = (HSIZE - 1);
95 uch *stacktop = stack + offset;
96 register uch *newstr;
97 int codesize=9, len, KwKwK, error;
98 shrint code, oldcode, freecode, curcode;
99 shrint lastfreecode;
100 unsigned int outbufsiz;
101 #if (defined(DLL) && !defined(NO_SLIDE_REDIR))
102 /* Normally realbuf and outbuf will be the same. However, if the data
103 * are redirected to a large memory buffer, realbuf will point to the
104 * new location while outbuf will remain pointing to the malloc'd
105 * memory buffer. */
106 uch *realbuf = G.outbuf;
107 #else
108 # define realbuf G.outbuf
109 #endif
110
111
112 /*---------------------------------------------------------------------------
113 Initialize various variables.
114 ---------------------------------------------------------------------------*/
115
116 lastfreecode = BOGUSCODE;
117
118 #ifndef VMS /* VMS uses its own buffer scheme for textmode flush(). */
119 #ifndef SMALL_MEM
120 /* non-memory-limited machines: allocate second (large) buffer for
121 * textmode conversion in flush(), but only if needed */
122 if (G.pInfo->textmode && !G.outbuf2 &&
123 (G.outbuf2 = (uch *)malloc(TRANSBUFSIZ)) == (uch *)NULL)
124 return PK_MEM3;
125 #endif
126 #endif /* !VMS */
127
128 for (code = 0; code < BOGUSCODE; ++code) {
129 Value[code] = (uch)code;
130 parent[code] = BOGUSCODE;
131 }
132 for (code = BOGUSCODE+1; code < HSIZE; ++code)
133 parent[code] = FREE_CODE;
134
135 #if (defined(DLL) && !defined(NO_SLIDE_REDIR))
136 if (G.redirect_slide) { /* use normal outbuf unless we're a DLL routine */
137 realbuf = G.redirect_buffer;
138 outbufsiz = G.redirect_size;
139 } else
140 #endif
141 #ifdef DLL
142 if (G.pInfo->textmode && !G.redirect_data)
143 #else
144 if (G.pInfo->textmode)
145 #endif
146 outbufsiz = RAWBUFSIZ;
147 else
148 outbufsiz = OUTBUFSIZ;
149 G.outptr = realbuf;
150 G.outcnt = 0L;
151
152 /*---------------------------------------------------------------------------
153 Get and output first code, then loop over remaining ones.
154 ---------------------------------------------------------------------------*/
155
156 READBITS(codesize, oldcode)
157 if (!G.zipeof) {
158 *G.outptr++ = (uch)oldcode;
159 OUTDBG((uch)oldcode)
160 ++G.outcnt;
161 }
162
163 do {
164 READBITS(codesize, code)
165 if (G.zipeof)
166 break;
167 if (code == BOGUSCODE) { /* possible to have consecutive escapes? */
168 READBITS(codesize, code)
169 if (code == 1) {
170 ++codesize;
171 Trace((stderr, " (codesize now %d bits)\n", codesize));
172 } else if (code == 2) {
173 Trace((stderr, " (partial clear code)\n"));
174 partial_clear(__G); /* clear leafs (nodes with no children) */
175 Trace((stderr, " (done with partial clear)\n"));
176 lastfreecode = BOGUSCODE; /* reset start of free-node search */
177 }
178 continue;
179 }
180
181 /*-----------------------------------------------------------------------
182 Translate code: traverse tree from leaf back to root.
183 -----------------------------------------------------------------------*/
184
185 newstr = stacktop;
186 curcode = code;
187
188 if (parent[curcode] == FREE_CODE) {
189 /* or (FLAG_BITS[curcode] & FREE_CODE)? */
190 KwKwK = TRUE;
191 Trace((stderr, " (found a KwKwK code %d; oldcode = %d)\n", code,
192 oldcode));
193 --newstr; /* last character will be same as first character */
194 curcode = oldcode;
195 } else
196 KwKwK = FALSE;
197
198 do {
199 *newstr-- = Value[curcode];
200 curcode = (shrint)(parent[curcode] & CODE_MASK);
201 } while (curcode != BOGUSCODE);
202
203 len = (int)(stacktop - newstr++);
204 if (KwKwK)
205 *stacktop = *newstr;
206
207 /*-----------------------------------------------------------------------
208 Write expanded string in reverse order to output buffer.
209 -----------------------------------------------------------------------*/
210
211 Trace((stderr, "code %4d; oldcode %4d; char %3d (%c); string [", code,
212 oldcode, (int)(*newstr), (*newstr<32 || *newstr>=127)? ' ':*newstr));
213
214 {
215 register uch *p;
216
217 for (p = newstr; p < newstr+len; ++p) {
218 *G.outptr++ = *p;
219 OUTDBG(*p)
220 if (++G.outcnt == outbufsiz) {
221 Trace((stderr, "doing flush(), outcnt = %lu\n", G.outcnt));
222 if ((error = flush(__G__ realbuf, G.outcnt, TRUE)) != 0)
223 pipeit("unshrink: flush() error (%d)\n",
224 error);
225 Trace((stderr, "done with flush()\n"));
226 G.outptr = realbuf;
227 G.outcnt = 0L;
228 }
229 }
230 }
231
232 /*-----------------------------------------------------------------------
233 Add new leaf (first character of newstr) to tree as child of oldcode.
234 -----------------------------------------------------------------------*/
235
236 /* search for freecode */
237 freecode = (shrint)(lastfreecode + 1);
238 /* add if-test before loop for speed? */
239 while (parent[freecode] != FREE_CODE)
240 ++freecode;
241 lastfreecode = freecode;
242 Trace((stderr, "]; newcode %d\n", freecode));
243
244 Value[freecode] = *newstr;
245 parent[freecode] = oldcode;
246 oldcode = code;
247
248 } while (!G.zipeof);
249
250 /*---------------------------------------------------------------------------
251 Flush any remaining data and return to sender...
252 ---------------------------------------------------------------------------*/
253
254 if (G.outcnt > 0L) {
255 Trace((stderr, "doing final flush(), outcnt = %lu\n", G.outcnt));
256 if ((error = flush(__G__ realbuf, G.outcnt, TRUE)) != 0)
257 pipeit("unshrink: flush() error (%d)\n", error);
258 Trace((stderr, "done with flush()\n"));
259 }
260
261 return PK_OK;
262
263 } /* end function unshrink() */
264
265
266
267
268
269 /****************************/
270 /* Function partial_clear() */ /* no longer recursive... */
271 /****************************/
272
273 static void partial_clear(__G)
274 __GDEF
275 {
276 register shrint code;
277
278 /* clear all nodes which have no children (i.e., leaf nodes only) */
279
280 /* first loop: mark each parent as such */
281 for (code = BOGUSCODE+1; code < HSIZE; ++code) {
282 register shrint cparent = (shrint)(parent[code] & CODE_MASK);
283
284 if (cparent > BOGUSCODE && cparent != FREE_CODE)
285 FLAG_BITS[cparent] |= HAS_CHILD; /* set parent's child-bit */
286 }
287
288 /* second loop: clear all nodes *not* marked as parents; reset flag bits */
289 for (code = BOGUSCODE+1; code < HSIZE; ++code) {
290 if (FLAG_BITS[code] & HAS_CHILD) /* just clear child-bit */
291 FLAG_BITS[code] &= ~HAS_CHILD;
292 else { /* leaf: lose it */
293 Trace((stderr, "%d\n", code));
294 parent[code] = FREE_CODE;
295 }
296 }
297
298 return;
299 }
300
301 #endif /* !LZW_CLEAN */