]> git.saurik.com Git - wxWidgets.git/blame - utils/Install/packzip/unreduce.c
projects / wxWidgets.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
regenerated with tmake
[wxWidgets.git] / utils / Install / packzip / unreduce.c
CommitLineData
f6bcfd97
BP		 1/*---------------------------------------------------------------------------
2
3 unreduce.c
4
5 The Reducing algorithm is actually a combination of two distinct algorithms.
6 The first algorithm compresses repeated byte sequences, and the second al-
7 gorithm takes the compressed stream from the first algorithm and applies a
8 probabilistic compression method.
9
10 * Copyright 1989 Samuel H. Smith; All rights reserved
11 *
12 * Do not distribute modified versions without my permission.
13 * Do not remove or alter this notice or any other copyright notice.
14 * If you use this in your own program you must distribute source code.
15 * Do not use any of this in a commercial product.
16
17 See the accompanying file "COPYING" in UnZip source and binary distributions
18 for further information. This code is NOT used unless USE_SMITH_CODE is
19 explicitly defined (==> COPYRIGHT_CLEAN is not defined).
20
21 ---------------------------------------------------------------------------*/
22
23
24#define UNZIP_INTERNAL
25#include "unzip.h" /* defines COPYRIGHT_CLEAN by default */
26
27
28#ifndef COPYRIGHT_CLEAN
29
30/**************************************/
31/* UnReduce Defines, Typedefs, etc. */
32/**************************************/
33
34#define DLE 144
35
36typedef uch f_array[64]; /* for followers[256][64] */
37
38
39
40/******************************/
41/* UnReduce Local Functions */
42/******************************/
43
44static void LoadFollowers OF((__GPRO__ f_array *followers, uch *Slen));
45
46
47
48/*******************************/
49/* UnReduce Global Constants */
50/*******************************/
51
52static ZCONST shrint L_table[] =
53{0, 0x7f, 0x3f, 0x1f, 0x0f};
54
55static ZCONST shrint D_shift[] =
56{0, 0x07, 0x06, 0x05, 0x04};
57static ZCONST shrint D_mask[] =
58{0, 0x01, 0x03, 0x07, 0x0f};
59
60static ZCONST shrint B_table[] =
61{8, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5,
62 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6,
63 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
64 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7,
65 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
66 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
67 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
68 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
69 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
70 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
71 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
72 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
73 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
74 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
75 8, 8, 8, 8};
76
77
78
79
80
81/*************************/
82/* Function unreduce() */
83/*************************/
84
85void unreduce(__G) /* expand probabilistically reduced data */
86 __GDEF
87{
88 register int lchar = 0;
89 shrint nchar;
90 shrint ExState = 0;
91 shrint V = 0;
92 shrint Len = 0;
93 long s = G.ucsize; /* number of bytes left to decompress */
94 unsigned w = 0; /* position in output window slide[] */
95 unsigned u = 1; /* true if slide[] unflushed */
96 uch Slen[256];
97
98 f_array *followers = (f_array *)(slide + 0x4000);
99 int factor = G.lrec.compression_method - 1;
100
101 LoadFollowers(__G__ followers, Slen);
102
103 while (s > 0 /* && (!zipeof) */) {
104 if (Slen[lchar] == 0)
105 READBITS(8, nchar) /* ; */
106 else {
107 READBITS(1, nchar) /* ; */
108 if (nchar != 0)
109 READBITS(8, nchar) /* ; */
110 else {
111 shrint follower;
112 int bitsneeded = B_table[Slen[lchar]];
113
114 READBITS(bitsneeded, follower) /* ; */
115 nchar = followers[lchar][follower];
116 }
117 }
118 /* expand the resulting byte */
119 switch (ExState) {
120
121 case 0:
122 if (nchar != DLE) {
123 s--;
124 slide[w++] = (uch)nchar;
125 if (w == 0x4000) {
126 flush(__G__ slide, (ulg)w, 0);
127 w = u = 0;
128 }
129 }
130 else
131 ExState = 1;
132 break;
133
134 case 1:
135 if (nchar != 0) {
136 V = nchar;
137 Len = V & L_table[factor];
138 if (Len == L_table[factor])
139 ExState = 2;
140 else
141 ExState = 3;
142 } else {
143 s--;
144 slide[w++] = DLE;
145 if (w == 0x4000)
146 {
147 flush(__G__ slide, (ulg)w, 0);
148 w = u = 0;
149 }
150 ExState = 0;
151 }
152 break;
153
154 case 2:{
155 Len += nchar;
156 ExState = 3;
157 }
158 break;
159
160 case 3:{
161 register unsigned e;
162 register unsigned n = Len + 3;
163 register unsigned d = w - ((((V >> D_shift[factor]) &
164 D_mask[factor]) << 8) + nchar + 1);
165
166 s -= n;
167 do {
168 n -= (e = (e = 0x4000 - ((d &= 0x3fff) > w ? d : w)) > n ?
169 n : e);
170 if (u && w <= d)
171 {
172 memzero(slide + w, e);
173 w += e;
174 d += e;
175 }
176 else
177 if (w - d < e) /* (assume unsigned comparison) */
178 do { /* slow to avoid memcpy() overlap */
179 slide[w++] = slide[d++];
180 } while (--e);
181 else
182 {
183 memcpy(slide + w, slide + d, e);
184 w += e;
185 d += e;
186 }
187 if (w == 0x4000)
188 {
189 flush(__G__ slide, (ulg)w, 0);
190 w = u = 0;
191 }
192 } while (n);
193
194 ExState = 0;
195 }
196 break;
197 }
198
199 /* store character for next iteration */
200 lchar = nchar;
201 }
202
203 /* flush out slide */
204 flush(__G__ slide, (ulg)w, 0);
205}
206
207
208
209
210
211/******************************/
212/* Function LoadFollowers() */
213/******************************/
214
215static void LoadFollowers(__G__ followers, Slen)
216 __GDEF
217 f_array *followers;
218 uch *Slen;
219{
220 register int x;
221 register int i;
222
223 for (x = 255; x >= 0; x--) {
224 READBITS(6, Slen[x]) /* ; */
225 for (i = 0; (uch)i < Slen[x]; i++)
226 READBITS(8, followers[x][i]) /* ; */
227 }
228}
229
230#endif /* !COPYRIGHT_CLEAN */
wxWidgets (Impactor)